User:Wiener's Attack

Introduction

The system of RSA is frequently used for security application such as email, credit card payments, login network access, etc. One of RSA attacks is suggested by Michael Wiener. He uses continued fraction method to exploit an error made in the use of RSA. The example of situation is when we are doing transactions using credit card or for mobile devices such as phone.

Before we discuss how Wiener's attack works, first we will explain how RSA works briefly. Let Alice and Bob be two people who want to make communication securely. In more specific, 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 which is public and together with the encryption exponent e will form the public key pair (e,N). By making this information public, it will allow anyone to encrypt the message. The decryption exponent d is satisfied $ed=1mod\varphi (N)$, where $\varphi (N)=(p-1)(q-1)$, Euler’s phi function (note: this is the order of multiplicative group $\mathbb {Z} _{N}^{*}$). The encryption exponent e and $\varphi (N)$ 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 can the private key pair as (d, N). Using Chinese Remainder Theorem, one can efficiently recover the secret key d if (s)he knows the factorization of N. By having the secret key d, one can efficiently factor the modulus of N.

In RSA Cryptosystem, the one who sends the message might tend to use a small value of d, rather than a large random number to improve the RSA decryption performance in the matter of running-time. However, by using Wiener’s attack, we can see that choosing a small value for d will result an insecure system in which we can recover all secret information. Another person, called “the attacker” will break the RSA system. This break is based on Wiener’s Theorem, which in general provides a small value of d. Wiener has proved that the attacker may efficiently find d when $d<{\frac {1}{3}}N^{\frac {1}{4}}$.
In addition to Wiener's finding in RSA-attack, he also found a number of techniques that allow fast decryption and does not apply to his attack. Two sampling techniques are described as follows.
Choosing large public key: By replacing $e$ by $e'$, where $e'=e+k.\varphi (N)$ for some large of $k$. When $e'$ is large enough, i.e. $e'>N^{\frac {1}{2}}$, then Wiener’s attack can not be installed regardless of how small $d$ is.
Using Chinese Remainder Theorem: Suppose one chooses d such that both $d_{p}=d{\bmod {\ }}(p-1)$and $d_{q}=d{\bmod {\ }}(q-1)$ are small, then a fast decryption of $C$ can be done as follows:
1. First compute $M_{p}=C^{dp}{\bmod {\ }}p$ and $M_{q}=C^{dq}{\bmod {\ }}q$.
2. Use the Chinese Remainder Theorem to compute the unique value of $M\in \mathbb {Z_{N}}$ which satisfies $M=M_{p}{\bmod {\ }}p$ and $M=M_{q}{\bmod {\ }}q$. The result of $M$ satisfies $M=C^{d}{\bmod {\ }}N$ as needed. The point is that the attack by Wiener’s attack does not apply here because the value of $d{\bmod {\ }}\varphi (N)$ can be large.

How Wiener's Attack Works

Since

$ed=1(mod(p-1)(q-1))$,

There exist an integer K such that

$ed=K.(p-1)(q-1)+1$

Define $G=gcd(p-1,q-1)$ to be included in the equation above which gives:

$ed={\frac {K}{G}}(p-1)(q-1)+1$

Defining $k={\frac {K}{gcd(K,G)}}$ and $g={\frac {G}{gcd(K,G)}}$, and substituting into the above gives:

$ed={\frac {k}{g}}(p-1)(q-1)+1$.

Divided by $dpq$:

${\frac {e}{pq}}={\frac {k}{dg}}(1-\delta )$, where $\delta ={\frac {p+q-1-{\frac {g}{k}}}{pq}}$.

So, ${\frac {e}{pq}}$ is close underestimate of ${\frac {k}{dg}}$, and the former is composed entirely of public information. Note that this algorithm finds fractions in their lowest terms. However, a method of checking a guess is still required. Assuming that $ed>pq$ (a reasonable asumption unles $G$ is large) the last equation above may be written as:

$edg=k.(p-1)(q-1)+g$

By using simple algebraic manipulation and identities, a guess can be checked for accuracy.

Example

Suppose that the public keys are $\left\langle N,e\right\rangle =\left\langle 90581,17993\right\rangle$
If we want to attack, we have to determine $d$.
By using Wiener Theorem and continued fractions to approx $d$, first we try to find the continued fractions of ${\frac {e}{N}}$.

We know that

${\frac {e}{N}}={\frac {17993}{90581}}={\cfrac {1}{5+{\cfrac {1}{29+...+{\cfrac {1}{3}}}}}}=\left[0,5,29,4,1,3,2,4,3\right]$

According to the continued fractions expansion of ${\frac {e}{N}}$, the all convergents ${\frac {k}{d}}$ are:

${\frac {k}{d}}=0,{\frac {1}{5}},{\frac {29}{146}},{\frac {117}{589}},{\frac {146}{735}},{\frac {555}{2794}},{\frac {1256}{6323}},{\frac {5579}{28086}},{\frac {17993}{90581}}$

We can verify that the first convergents do not produce a factorizations of $N$. However, the convergent ${\frac {1}{5}}$ yield

$\varphi (N)={\frac {e.d-1}{k}}={\frac {17993.5-1}{1}}=89964$

Now, if we solve the equation

$x^{2}-\left(\left(N-\varphi (N)\right)+1\right)x+N=0$

$x^{2}-\left(\left(90581-89964\right)+1\right)x+90581=0$

$x^{2}-\left(618\right)x+90581=0$

Then we find the roots which are $x=379;239$. Therefore we have found the factorization.

$N=90581=379\times 239=p\times q$.

Notice that, for the modulus $N=90581$, the Wiener's Theorem will work if

$d<{\frac {N^{\frac {1}{4}}}{3}}\approx 5,783$.

Theorem (M. Wiener)

Let $\ N=pq$ with $\ q<p<2q$. Let $d<{\frac {1}{3}}N^{\frac {1}{4}}$.
Given $\left\langle N,e\right\rangle$ with $ed=1{\bmod {\ }}\varphi (N)$, the attacker can efficiently recover $d$.

Proof

The proof is based on approximations using continued fractions. Since $ed=1{\bmod {\varphi }}(N)$, there exists a ${\mathit {k}}$ such that $ed-k\varphi (N)=1$. Therefore

$\left|{\frac {e}{\varphi (N)}}-{\frac {k}{d}}\right\vert ={\frac {1}{d\varphi (N)}}$

Hence, ${\frac {k}{d}}$ is an approximation of ${\frac {e}{\varphi (N)}}$. Although the attacker does not know $\varphi (N)$, he may use $N$ to approximate it. Indeed, since

$\varphi (N)=N-p-q+1$ and $p+q-1<3{\sqrt {N}}$, we have:

$\left\vert p+q-1\right\vert <3{\sqrt {N}}$

$\left\vert N+1-\varphi (N)-1\right\vert <3{\sqrt {N}}$

Using N in place of $\varphi (N)$ we obtain:

$\left\vert {\frac {e}{N}}-{\frac {k}{d}}\right\vert =\left\vert {\frac {ed-kN}{Nd}}\right\vert$

$\qquad =\left\vert {\frac {ed-k\varphi (N)-kN+k\varphi (N)}{Nd}}\right\vert$

$=\left\vert {\frac {1-k(N+\varphi (N))}{Nd}}\right\vert$

$\leq \left\vert {\frac {3k{\sqrt {N}}}{Nd}}\right\vert ={\frac {3k{\sqrt {N}}}{{\sqrt {N}}{\sqrt {N}}d}}={\frac {3k}{d{\sqrt {N}}}}$

Now, $k\varphi (N)=ed-1<ed$, so $k\varphi (N)<ed$. Since $e<\varphi (N)$, so $k\varphi (N)<ed<\varphi (N)d$, then we obtain:

$k\varphi (N)<\varphi (N)d$

$k<d$

Since $k<d$ and $d<{\frac {1}{3}}N^{\frac {1}{4}}$. Hence we obtain:

$\left\vert {\frac {e}{N}}-{\frac {k}{d}}\right\vert \leq {\frac {1}{dN^{\frac {1}{4}}}}.......(1)$

Since $d<{\frac {1}{3}}N^{\frac {1}{4}},2d<3d,$ then $2d<3d<N^{\frac {1}{4}}$, we obtain:

$2d<N^{\frac {1}{4}},$, so ${\frac {1}{2d}}>{\frac {1}{N^{\frac {1}{4}}}}......(2)$

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

$\left\vert {\frac {e}{N}}-{\frac {k}{d}}\right\vert \leq {\frac {3k}{d{\sqrt {N}}}}<{\frac {1}{d.2d}}={\frac {1}{2d^{2}}}\blacksquare$

Notes

• Boneh, Dan (1999). Twenty Years of attacks on the RSA Cryptosystem. Notices of the American Mathematical Society (AMS) 46 (2).
  

• Coppersmith, Don (1996). Low-Exponent RSA with Related Messages. Springer-Verlag Berlin Heidelberg. <br\>

• Cui, Xiao-lei (2005). Attack On the RSA Cryptosystem.<br\>

• Khaled Salah, Imad (2006). Mathematical Attacks on RSA Cryptosystem. Journal of Computer Science 2 (8)). pp. 665-671.
  

• L. Render, Elaine (2007). Wiener's Attack on Short Secret Exponents.
  

• Jose, Justin (2010). Study of RSA and Proposed Variant Against Wiener's Attack. International Journal of Computer Applications.
  

• DUJELLA, ANDREJ (2004). CONTINUED FRACTIONS AND RSA WITH SMALL SECRET EXPONENT.
  

References

• R. Stinson, Douglas (2002). Cryptography Theory and Practice (2e ed.). A CRC Press Company. pp. 200–204. ISBN 1-58488-206-9.