Homework 2
Rule: Finish all of the following on your own.
- (Hints: Use Fermat Theorem, Euler Theorem, properties of totient functions, etc, or write program code as assistance)
(1) 123416 mod 17
(2) 5451 mod 17
(3) ø(51)
(4) gcd(33, 121)
(5) 2-1 mod 17 (i.e., multiplicative inverse of 2 mod 17) (6)ind2,5(4)
(7) ø(8000)
(8) ø(98803519)
- Write a computer program to implement the extended Euclid’s algorithm, use your code to compute the following. Submit your code and results.
- GCD (10012012,2314213) b. GCD(28176412,29108188) c.GCD(38172,23812188)
- The multiplicative inverse of 12091 mod24123123.
- The multiplicative inverse of 28173928 mod129182771.
- Prove that a=n-1 is always a solution to a2=1 mod n.
- What are the differences between symmetric and asymmetric keycrypto.
- Explain the feasibility and security ofRSA.
- Alice designs a double-RSA cipher. She first generates two secret primes p and q, and compute n=p*q, then choose two public encryption exponents e1 and e2 that are relatively prime to ø(n). So <e1, e2, n> becomes the public key. She tells people to encrypt message M by computing C1=M e1 mod n and then C= C1e2 mod n, finally sending just C
- Show the decryption process (i.e., how Alice can obtain the plain text M from the final ciphertextC).
- Is the double-RSA cipher more secure, less secure, or just as secure as the regular RSA cipherwith the same modulus n but only one encryption exponent? Why?
- Charlie got Alice’s instructions confused, and encrypt message M for Alice using e1 and e2 in the reverse order (i.e., Charlie uses C1=M e2 mod n then C= C1e1 mod n). What would happen when Alice, unaware of Charlie’s error, triesto decipher the ciphertext using her usual procedure?