Alice has a RSA public key (e,n) with corresponding private key d. n=pq for dist

Question

Alice has a RSA public key (e,n) with corresponding private key d. n=pq for distinct large primes p & q. If Alice does not discard p and q after computer n and phi(n), she can employ an alternative decryption procedure as described below. For a given ciphertext C (1 <= C <= n-1, gcd(C,n)=1), she proceeds as follows: 1) i) Compute d_p congruent d (mod p-1) , 0 <= d_p <= p-2; ii)d_q congruent d (mod q-1) , 0 <= d_q <= q-2; 2) i) Compute M_p congruent C^(d_p) (mod p) , 1 <= M_p <= p-1; ii) M_q congruent C^(d_q) (mod q) , 1 <= M_q <= q-1; 3) Use extended euclidean algorithm to find x and y such that px + qy = 1 (such integers exist because gcd(p,q)=1); 4) Set M congruent pxM_q + qyM_p (mod n) , 1 <= M <= n-1. Prove that if C congruent M^e (mod n) is a ciphertext obtained by encrypting a message M, then the above procedure decrypts C correctly. That is, if M' is the result of applying the procedure above to C, then M' = M.

Explanation / Answer

Key generation RSA involves a public key and a private key. The public key can be known to everyone and is used for encrypting messages. Messages encrypted with the public key can only be decrypted using the private key. The keys for the RSA algorithm are generated the following way: Choose two distinct prime numbers p and q. For security purposes, the integers p and q should be chosen at random, and should be of similar bit-length. Prime integers can be efficiently found using a primality test. Compute n = pq. n is used as the modulus for both the public and private keys Compute f(n) = (p?–?1)(q?–?1), where f is Euler's totient function. Choose an integer e such that 1

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.