1. Let n be the product of 2 large primes. Alice wants to send a message m to bob, where gcd(m,n)=1. Alice and Bob choose integers a, and b relatively prime to phi(n). Alice computes C is congruent to m^a (mod n) and sends c to bob. Bob computes d congruent to c^b (mod n) and sends d back to alice. Since Alice aknows a, she finds a^-1 such that aa^-1=1 (mod phi (n) )

Then she computes e congruent to d^(a^-1) (mod n) and sends e to bob. Explain what bob must now do to obtain m, and show that this works.

2. Let p=7919 and q=17389. Let e= 66906025. A calculation shows that e^2 is congruent to 1 (mod (p-1)(q-1) ). alice decides to encrypt the message m=12345 using RSA with modulas n=pq and exponent e. Since she wants the encryption to be very secure she encrypts the ciphertext again using n and e (so she has double encrypted the original plaintext) What is the final ciphertext that she sends? Justify your answer without using a calc.



I appreciate all help! Thank you MHF!