The Wiener's attack, named after cryptologist Michael J. Wiener, is a type of cryptographic attack against RSA. The attack uses the continued fraction method to expose the private key d when d is small.

Background on RSA edit

Fictional characters Alice and Bob are people who want to communicate securely. More specifically, Alice wants to send a message to Bob which only Bob can read. First Bob chooses two primes p and q. Then he calculates the RSA modulus N = pq. This RSA modulus is made public together with the encryption exponent e. N and e form the public key pair (e, N). By making this information public, anyone can encrypt messages to Bob. The decryption exponent d satisfies  , where   denotes the Carmichael function, though sometimes  , the Euler’s phi function, is used (note: this is the order of the multiplicative group  , which is not necessarily a cyclic group). The encryption exponent e and   also must be relatively prime so that there is a modular inverse. The factorization of N and the private key d are kept secret, so that only Bob can decrypt the message. We denote the private key pair as (d, N). The encryption of the message M is given by   and the decryption of cipher text   is given by   (using Fermat's little theorem).

Using the Euclidean algorithm, one can efficiently recover the secret key d if one knows the factorization of N. By having the secret key d, one can efficiently factor the modulus of N.[1]

Small private key edit

In the RSA cryptosystem, Bob might tend to use a small value of d, rather than a large random number to improve the RSA decryption performance. However, Wiener’s attack shows that choosing a small value for d will result in an insecure system in which an attacker can recover all secret information, i.e., break the RSA system. This break is based on Wiener’s Theorem, which holds for small values of d. Wiener has proved that the attacker may efficiently find d when  .[2]

Wiener's paper also presented some countermeasures against his attack that allow fast decryption. Two techniques are described as follows.

Choosing large public key: Replace   by  , where   for some large of  . When   is large enough, i.e.  , then Wiener’s attack can not be applied regardless of how small   is.

Using the Chinese Remainder Theorem: Suppose one chooses d such that both   and   are small but   itself is not, then a fast decryption of   can be done as follows:

1. First compute   and  .
2. Use the Chinese Remainder Theorem to compute the unique value of   which satisfies   and  . The result of   satisfies   as needed. The point is that Wiener’s attack does not apply here because the value of   can be large.[3]

How Wiener's attack works edit

Note that

 

where  

Since

 ,

there exists an integer K such that

 
 

Defining   and  , and substituting into the above gives:

 .

Divided by  :

 , where  .

So,   is slightly smaller than  , and the former is composed entirely of public information. However, a method of checking[clarification needed] and guess is still required.

By using simple algebraic manipulations and identities, a guess can be checked for accuracy.[1]

Wiener's theorem edit

Let   with  . Let  .
Given   with  , the attacker can efficiently recover  .[2][failed verification]

Example edit

Suppose that the public keys are  
The attack shall determine  .
By using Wiener's Theorem and continued fractions to approximate  , first we try to find the continued fractions expansion of  . Note that this algorithm finds fractions in their lowest terms. We know that

 

According to the continued fractions expansion of  , all convergents   are:

 

We can verify that the first convergent does not produce a factorization of  . However, the convergent   yields

 

Now, if we solve the equation

 
 
 

then we find the roots which are  . Therefore we have found the factorization

 .

Notice that, for the modulus  , Wiener's Theorem will work if

 .

Proof of Wiener's theorem edit

The proof is based on approximations using continued fractions.[2][4]
Since  , there exists a   such that  . Therefore

 .

Let  ; note that if   is used instead of  , then the proof can be replaced with   and   replaced with  .

Then multiplying by  ,

 

Hence,   is an approximation of  . Although the attacker does not know  , he may use   to approximate it. Indeed, since

  and  , we have:

 
 

Using   in place of   we obtain:

 

Now,  , so  . Since  , so  , then we obtain:

 
 

Since   and  . Hence we obtain:

(1)  

Since   then  , we obtain:

 , so (2)  

From (1) and (2), we can conclude that

 

If  , then   is a convergent of  , thus   appears among the convergents of  . Therefore the algorithm will indeed eventually find  .[further explanation needed]

References edit

  1. ^ a b L. Render, Elaine (2007). Wiener's Attack on Short Secret Exponents.[dead link]
  2. ^ a b c Boneh, Dan (1999). Twenty Years of attacks on the RSA Cryptosystem. Notices of the American Mathematical Society (AMS) 46 (2).
  3. ^ Cui, Xiao-lei (2005). Attacks On the RSA Cryptosystem.
  4. ^ Salah, Imad Khaled; Darwish, Abdullah; Oqeili, Saleh (2006). "Mathematical Attacks on RSA Cryptosystem" (PDF). Journal of Computer Science. 2 (8): 665–671. doi:10.3844/jcssp.2006.665.671.

Further reading edit