The following is an important and interesting chosen ciphertext attack against R
ID: 3602972 • 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 = me 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. (The answer is a short calculation; theorems that are used should be cited.)
Explanation / Answer
19down voteaccepted
In a chosen-ciphertext attack, the attacker is assumed to have a way to trick someone who knows the secret key into decrypting arbitrary message blocks and tell him the result. The attacker can choose some arbitrary nonsense as an "encrypted message" and ask to see the (usually) different nonsense it decrypts to, and he can do this a number of times.
Having this capability obviously already allows the attacker to read an intercepted message, since he can just ask to have it decrypted. But in this attack his goal is more ambitious than that: he wants to deduce what the secret key is, such that he can encrypt messages himself, and also keep decrypting after his access to having things decrypted for him vanishes.
The attack is successful if if an attacker has a significant chance of being able to deduce the key after having "relatively few" blocks decrypted and without doing so much work himself that he could just as well have brute-forced it.
The term "chosen-ciphertext attack" does not in itself say anything about how the attacker chooses the nonsense blocks he asks to have decrypted, or what kind of computations he does in order to recover the key from the responses.
As a concrete example, suppose General A is sending messages to General B using a Vigenère cipher with an unknown key. The enemy is somehow able to intercept a message and replace it with some completely random letters of his own choosing, say NLLCJOVFXXHMLY. General B decrypts this and gets AKRUWNBXKWNEYX which is nonsense. Bemused, and not thinking this nonsense is worth keeping secret, he picks up a non-secure phone and calls General A: "What the hell do you mean with AKRUWNBXKWNEYX? Did they change the key without telling me?" But the enemy is eavesdropping on the line and now knows that NLLCJOVFXXHMLY decrypts to AKRUWNBXKWNEYX. He can then subtract the two sets of nonsense to get MATHMATHMATHMA, and now he knows the key.
19down voteaccepted
In a chosen-ciphertext attack, the attacker is assumed to have a way to trick someone who knows the secret key into decrypting arbitrary message blocks and tell him the result. The attacker can choose some arbitrary nonsense as an "encrypted message" and ask to see the (usually) different nonsense it decrypts to, and he can do this a number of times.
Having this capability obviously already allows the attacker to read an intercepted message, since he can just ask to have it decrypted. But in this attack his goal is more ambitious than that: he wants to deduce what the secret key is, such that he can encrypt messages himself, and also keep decrypting after his access to having things decrypted for him vanishes.
The attack is successful if if an attacker has a significant chance of being able to deduce the key after having "relatively few" blocks decrypted and without doing so much work himself that he could just as well have brute-forced it.
The term "chosen-ciphertext attack" does not in itself say anything about how the attacker chooses the nonsense blocks he asks to have decrypted, or what kind of computations he does in order to recover the key from the responses.
As a concrete example, suppose General A is sending messages to General B using a Vigenère cipher with an unknown key. The enemy is somehow able to intercept a message and replace it with some completely random letters of his own choosing, say NLLCJOVFXXHMLY. General B decrypts this and gets AKRUWNBXKWNEYX which is nonsense. Bemused, and not thinking this nonsense is worth keeping secret, he picks up a non-secure phone and calls General A: "What the hell do you mean with AKRUWNBXKWNEYX? Did they change the key without telling me?" But the enemy is eavesdropping on the line and now knows that NLLCJOVFXXHMLY decrypts to AKRUWNBXKWNEYX. He can then subtract the two sets of nonsense to get MATHMATHMATHMA, and now he knows the key.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.