The following is an important and interesting chosen ciphertext attack against R
ID: 3604764 • Letter: T
Question
The following is an important and interesting chosen ciphertext attack against RSA (i.e., plain RSA, without further precautions added). Let n = pq (where p and q are two large private primes), with public RSA key (n, e) and private key (n, d). Let m be any message, and let c = m e mod n be the corresponding ciphertext, encrypted by the receiver’s public key. A spy can intercept c when c is sent to the receiver. The spy would like to find the message m = c d mod n (but d is private). For an attack, the spy picks an integer r in [2, n 2] randomly, and computes x = r e · c mod n , and t = r 1 mod n. The number x is the spy’s chosen ciphertext for the attack. Note that x will look rather random. Next, assume that the spy gets the receiver to sign x (by RSA signature with the receiver’s private key d); alternatively, the spy gets the receiver to decrypt x. In any case, x gets decrypted, so y = x d mod n is returned to the spy. Show how the spy can use the information now available to find m.
Explanation / Answer
Message M is given. Ciphertext C is calculated as c= m e mod n. this is sent to receiver. But in between , c is intercepted by Spy. Now Spy calculated m= c d mod n, but d is private. so Spy choses random numbers to calculate. An x is generated using x=r e c mod n.This x is sent to receiver to sign on. Receiver sign on x with its private key assuming that x was sent by sender not by spy. Now x is decrypted by receiver and sent back to spy in the form of y. Spy now knows the private key from which it was decrypted. Using d, spy calculates m= c d mod n. This way spy uses information and generates m.
To implement RSA algorithm:
1) Choose two random prime numbers.
2) Find first part of public key by n=p*q
3) Find other part of public key by phi=(p-1)*(q-1)
4) For decryption choose d such that it satisfies d*e = 1 + k * totient
d = (1 + (k * phi)) / e
5) Encryption c = (msg e ) % n
6) Decryption m = (c d) % n
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.