2. Public-key encryption, also known as asymmetric key encryption, uses a key forencryption and a different key for decryption (therefore the name asymmetric). An individual (person A) using public-key encryption first needs to create a pair of keys, E(for encryption) and D (for decryption), using an algorithm such as the RSA algorithm. The individual (person A) makes the encryption key E public while keeping the decryption key D secret. Anyone wishing to send a message P (plaintext) to person A insecret would encrypt the message using As public key, resulting in a ciphertext C = E(P), expressed here using the function notation. When person A received the ciphertext C, applying the decryption D would result in D(C) = D(E(P)) = P, the plaintext. Since person A is the only person that knows the decryption key D, this encryption method is secure (even if the encrypted message C is captured by an attacker). The well-known RSA algorithm for public-key encryption basically uses two large primes to generate the keys, keeping the two large primes secret while making their product public. The security of RSA is dependent on the fact that there are currently no known efficient (polynomial-time) algorithms for factoring large numbers.

Answer the below questions which demonstrate the basic ideas of how the RSA algorithm works.

Consider two primes p = 157 and q = 23. (These are very small primes, used here for demonstration purposes.). Define n = pq = (157)(23) = 3611.

(a) Compute (pq) where () is Eulers Totient function.

(b) Determine a number E, 2 E (pq), so that GCD(E, (pq)) = 1. (Hint: Try E = 5, or

use randomly generated values for E until finding one that works.)

(c) For E selected from (b) find its multiplicative inverse D such that DE 1 mod (pq).

(Hint: use the Extended Euclids GCD algorithm on pages 40, 41 of the notes.)

(d) For each value of P, P = 25, 40, and 355, compute C = PE mod n, then compute CD

mod n, where n = pq = 3611. What is your conclusion?

(e) Similar to (d), for each value of P = 25, 40, and 355, compute C = PD mod n, then

compute CE mod n, where n = pq = 3611. What is your conclusion?