**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*e*1 and*e*2 that are relatively prime to ø(*n*). So <*e*1,*e*2,*n*> becomes the public key. She tells people to encrypt message*M*by computing*C*1=*M*^{e}^{1}mod*n*and then*C*=*C*1*e*2 mod*n*, finally sending just*C* - Show the decryption process (i.e., how Alice can obtain the plain text
*M*from the final ciphertext*C*).

- 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*e*1 and*e*2 in the reverse order (i.e., Charlie uses*C*1=*M*^{e}^{2}mod*n*then*C*=*C*1*e*1 mod*n*). What would happen when Alice, unaware of Charlie’s error, triesto decipher the ciphertext using her usual procedure?