USA: +1(669)289-8683 
Sign in
Homework 3 (100 pts)Rule: Finish all of the following on your own.
Submit your solution in PDF format.
1. Compute the following with detailed steps. (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)
(9) ø(999866001989) for the graduate session only.
2. Write a computer program to implement the extended Euclid’s algorithm, use your
code to compute the following. Submit your code and results.
a. GCD(10012012,2314213)
b. GCD(28176412,29108188)
c. GCD(38172,23812188)
d. The multiplicative inverse of 12091 mod 24123123.
e. The multiplicative inverse of 28173928 mod 129182771.
f. GCD(381723029127918237717233210002,23812188332813212739187261) for
the graduate session only.
3.
4.
5.
6.
Prove that a=n-1 is always a solution to a2=1 mod n.
What are the differences between symmetric and asymmetric key crypto.
Explain the feasibility and security of RSA.
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 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 to her.
a. Show the decryption process (i.e., how Alice can obtain the plaintext M from
the final ciphertext C).
b. Is the double-RSA cipher more secure, less secure, or just as secure as the
regular RSA cipher with the same modulus n but only one encryption exponent?
Why?
c. 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, tries
to decipher the ciphertext using her usual procedure?
