Introduction

edit

Low Public Exponent Attack

In order to reduce encryption or signature-verification time, it is useful to use a small public exponent ( ). In practice, common choices for   are 3, 17 and 65537  .[1]. These are Fermat primes, sometimes referred to as   and   respectively  . They are chosen because they make the modular exponentiation operation faster. Also, having chosen  , it is simpler to test whether   and   while generating and testing the primes in step 1. Values of   or   that fail this test can be rejected there and then. (Even better: if e is prime and greater than 2 then you can do the less-expensive test   instead of  .
If the public exponent is small and the plaintext   is very short, then the RSA function may be easy to be inverted. However, it makes certain attacks possible. In order to defeat such attack, the value of public exponent   is recommended. When this value is used, signature-verification requires 17 multiplications, as opposed to roughly 1000 when a random is used. Unlike low private exponent (Wiener’s Attack), attacks that apply when a small   is used are far from a total break. The most powerful attacks on low public exponent RSA are based on the following theorem (Coppersmith).

Theorem 1 (Coppersmith)

edit
Let N be an integer and   be a monic polynomial of degree  . Set   for  . then, given   attacker, Eve, can efficiently find all integers   satisfying  . the running time is dominated by the time it takes to run the LLL algorithm on lattice of dimension   with  .
[2]

This theorem claims the existence of an algorithm which can efficiently find all roots of   modulo   that are less than  . As   gets smaller, the algorithm's runtime will decrease. This theorem's strength is the ability to find out all small roots of polynomials modulo a composite  .
This theorem has many applications on RSA attack specifically on low public exponent. We will explain some of these attacks and show how they work.

Håstad's Broadcast Attack

edit

At this moment, we will present an improvement to an attack the preceding Coppersmith's attack due to Håstad.
Suppose one sender will send an encrypted message   to a number of group of people  . Each using the same small public exponent  , say   = 3 , . Håstad showed that a linear-padding to   prior to encryption is insecure, and the attacker learns that   for  . If enough group of people are involved, the attacker can recover the plaintext   from all the ciphertext. Håstad’s discovery is applicable on the equations:  mod  . He proved that a system of univariate equations modulo relatively prime composites, such as   mod  , could be solved if many equations are provided sufficiently. This attack suggests that randomized padding should be used in RSA encryption.

How it works?

edit

suppose all public exponents   are equal to 3. A simple argument shows that as soon as  , the message   is no longer secure. Suppose Eve intercepts   , and   , where  0. We may assume   for all   (otherwise, it is possible to compute a factor of one of the Ni’s.) By the Chinese Remainder Theorem, she may compute   such that  . Then   ; however, since   for all  ', we have  . Thus   holds over the integers, and Eve can compute the cube root of   to obtain  .

Suppose Bob applies a pad to the message   prior to encrypt it so that the recipients receive slightly different messages. For instance, if   is   bits long, Bob might encrypt   and send this to the i-th recipient.
Unfortunately, Håstad showed that this linear padding is insecure. In fact, he proved that applying any fixed polynomial to the message prior to encryption does not prevent the attack.
Suppose before encrypting   and sending that to party  , Bob applies the polynomial   to   and encrypts  . Håstad showed that if enough parties are involved, Eve can recover the plaintext   from all the ciphertexts using the following theorem:

Theorem 2 (Håstad)

edit
Suppose   are relatively prime integers and set  . Let   be k polynomials of maximum degree  . Suppose there exists a unique   satisfying  (mod  ) for all  . Furthermore suppose  . There is an efficient algorithm which, given   for all  , computes  .

Proof:
Since   are relatively prime, Chinese Remainder Theorem might be used to compute coefficients   satisfying   and   mod   for all  . Setting   we know that   mod  . Since Ti are nonzero we have that   is not zero also. The degree of   is at most  . By Coppersmith’s Theorem, we may compute all integer roots   satisfying   mod   and  . However, we know that  , so   is a root.

This theorem can be applied to the problem of broadcast RSA such in the following manner: Suppose the i-th plaintext is padded with a polynomial  , so that   mod  . Then the polynomials   mod   satisfy that relation. The attack succceeds once  . The original result used the Håstad method instead of the full Coppersmith method. Its result was messages requiring   where  .

[3]

edit

Franklin-Reiter identified a new attack against RSA with public exponent  =3. If two messages differ only from a known fixed value of difference between the two messages and are RSA encrypted under the same RSA modulus  , then it is possible to recover both of them.

How it works?

edit

Let   be Alice's public key. Suppose   are two distinct messages satisfying   for some publicly known polynomial  . To send   and   to Alice, Bob may naively encrypt the messages and transmit the resulting ciphertexts  . We show that given  , Eve can easily recover   by using the following theorem:

Theorem 3 (Franklin-Reiter)

edit
Set   and let   be an RDA public key. Let   satisfy   for some linear polynomial   with  . Then, given  , attacker, Eve, can recover   in time quadratic in log  .

Proof:
Using an arbitrary   (rather than restricting to  , time quadratic in   and  ). Since  , we know that   is a root of the polynomial  . Similarly,   is a root of  . The linear factor   divides both polynomials. Therefore, Eve calculates the greatest common divisor (gcd) of   and  , if the gcd turns out to be linear,   is found. The gcd can be computed in quadratic time in   and  .  

Coppersmith’s Short Pad Attack

edit

Like the Hastad’s and Franklin-Reiter’s attack, this attack exploits a weakness of RSA with public exponent  . Coppersmith showed that if randomized padding suggested by Hastad is used improperly then RSA encryption is not secure.

How it works?

edit

Suppose Bob sends a message   to Alice using a small random padding before encrypting. An attacker, Eve, intercepts the ciphertext and prevents it from reaching its destination. Bob decides to resend   to Alice because Alice did not respond to his message. He randomly pads   again and transmits the resulting ciphertext. Eve now has two ciphertexts corresponding to two encryptions of the same message using two different random pads.
Even though Eve does not know the random pad being used, she still can recover the message   by using the following theorem, if the random paddding are too short.

Theorem 4 (Coppersmith)

edit
Let   be a public RSA key where   is  -bits long. Set  .Let   be a message of length at most   bits.Define   and  , where   and   are distinct integers with  . If Marvin is given   and the encryptions   of   (but is not given   or  , he can efficiently recover  

Proof
Define   and  . We know that when  , these polynomials have   as a common root. In other words,   is a root of the “resultant”  . Furthermore,  . Hence,   is a small root of   modulo  , and Marvin can efficiently find it using theorem 1 (Coppersmith). once   is known, the Franklin-Reiter attack can be used to recover   and consequently  .
[4]

References

edit