Attacks on RSA

RSA has several weaknesses called protocol failures. Protocol failures are not actually an exploit in the RSA algorithm. Instead, a protocol failure occurs when you perform inadvisable actions that give the attacker more information than they would otherwise have. The most common attack that results from a protocol failure is a direct mathematical attack that does not rely on breaking the normal strong point of RSA, the difficulty of factoring the product of two large prime numbers. Instead, the mathematical attack uses additional information from the protocol failure to bypass the protection without having to find the factorization.

Today, I'll talk about two protocol failures that occur when you send the message multiple times with different RSA parameters n and e.

The common modulus failure occurs when you send the same message M with the same modulus n but different values for the encryption exponent e. Suppose you send the message once with the exponent e and again with the exponent f. If e and f have no common factors, which is the case when both are prime numbers, then you can use the Euclidean algorithm to find values r and s where e*r + f*s = 1. The e and f values were public, so anyone can compute r and s. You've sent the encrypted values M^e mod n and M^f mod n over the wire. Unfortunately now, (M^e mod n)^r*(M^f mod n)^s=M^e*r+f*s mod n=M mod n, so it turns out to be quite trivial to figure out what the original message value was.

The small exponent failure occurs when you send the same message M with the same exponent e but different values for the modulus n. While the previous attack needed two messages, this attack needs e messages making it relatively hard to pull off if e is not a small value. Each message you send on the wire looks like M^e mod n_i for different moduluses n_i. Using the Chinese Remainder Theorem, you can compute a value M' such that M' is simultaneously congruent to M^e modulo n₁ and n₂ and all the way up to n_e. Since M must be smaller than each n_i for RSA to work, M^e is smaller than the product of all the n_i's, and therefore M' is not just congruent to M^e but exactly equal to it. The modulus is larger than the number we're trying to reduce so it has no effect. Figuring out the original message then simply requires taking the e-th root of M'.

Next time: A More Recent RSA Attack