Just to establish notation with respect to the RSA protocol, let n = p q be the

Question

Just to establish notation with respect to the RSA protocol, let n = p q be the product of two large primes and let e and d be the public and private exponents, respectively (e is the inverse of d mod ?(n)). Given a plaintext message m, we obtain the ciphertext c = me mod n; we subsequently decrypt the ciphertext by calculating cd mod n.

Suppose I'm trying to implement RSA on a device with low computational power, and these exponentiations take too long. I decide to make my implementation run faster by choosing small values for e and d (e.g. in the tens or hundreds).

Are there efficient attacks against such an implementation?

Explanation / Answer

First I must state that a secure RSA encryption must use an appropriate padding, which includes some randomness. See PKCS#1 for details.

That being said, d is the "private exponent" and knowledge of d and n is sufficient to decrypt messages. n is public (by construction) so d must be kept private at all costs. If it is very small then an attacker can simply try values for d exhaustively. On a more general basis, if the size of d is lower than 0.29 times the size of n (in bits) then there exists an efficient key recovery attack. The accepted wisdom is that trying to get a d much smaller than n is a bad idea for security.

On the other hand, there is no problem in having a small e, down to e=3. Actually, with RSA as you describe, there is a problem with a very small e: if you use e=3 and encrypt the very same message m with three distinct public keys, then an attacker can recover m. But that's not really due to using a small e; rather, it is due to not applying a proper padding.

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

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