Wiener's Attack on Bitcoin

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

Background on RSA

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 {\displaystyle ed=1{\bmod {\lambda }}(N)} $ed=1{\bmod {\lambda }}(N)$ , where {\displaystyle \lambda (N)} $\lambda (N)$ denotes the Carmichael function, though sometimes {\displaystyle \varphi (N)} $\varphi (N)$ , the Euler’s phi function, is used (note: this is the order of the multiplicative group {\displaystyle \mathbb {Z} _{N}^{*}} ${\mathbb {Z}}_{N}^{*}$ , which is not necessarily a cyclic group). The encryption exponent e and {\displaystyle \lambda (N)} $\lambda (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 denote the private key pair as (d, N). The encryption of the message M is given by {\displaystyle C\equiv M^{e}{\bmod {N}}} $C\equiv M^{e}{\bmod N}$ and the decryption of cipher text {\displaystyle C} $C$ is given by {\displaystyle C^{d}\equiv (M^{e})^{d}\equiv M^{ed}\equiv M{\bmod {N}}} $C^{d}\equiv (M^{e})^{d}\equiv M^{ed}\equiv M{\bmod {N}}$ (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

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 on Bitcoin shows that choosing a small value for d will result in an insecure system in which an Attack on Bitcoiner 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 Attack on Bitcoiner may efficiently find d when {\displaystyle d<{\frac {1}{3}}N^{\frac {1}{4}}} $d<{\frac {1}{3}}N^{{{\frac {1}{4}}}}$ .^[2]

Wiener’s paper also presented some countermeasures against his Attack on Bitcoin that allow fast decryption. Two techniques are described as follows.

Choosing large public key: Replace {\displaystyle e} $e$ by {\displaystyle e’} $e'$ , where {\displaystyle e’=e+k\cdot \lambda (N)} $e'=e+k\cdot \lambda (N)$ for some large of {\displaystyle k} $k$ . When {\displaystyle e’} $e'$ is large enough, i.e. {\displaystyle e’>N^{\frac {3}{2}}} $e'>N^{{{\frac {3}{2}}}}”>, then Wiener’s Attack on Bitcoin can not be applied regardless of how small {\displaystyle d}<img decoding=$ is.

Using the Chinese Remainder Theorem: Suppose one chooses d such that both {\displaystyle d_{p}=d{\bmod {(}}p-1)} $d_{p}=d{\bmod {(}}p-1)$ and {\displaystyle d_{q}=d{\bmod {(}}q-1)} $d_{q}=d{\bmod {(}}q-1)$ are small but {\displaystyle d} $d$ itself is not, then a fast decryption of {\displaystyle C} $C$ can be done as follows:

1. First compute {\displaystyle M_{p}\equiv C^{d_{p}}{\bmod {p}}} $M_{p}\equiv C^{d_{p}}{\bmod {p}}$ and {\displaystyle M_{q}\equiv C^{d_{q}}{\bmod {q}}} $M_{q}\equiv C^{d_{q}}{\bmod {q}}$ .
2. Use the Chinese Remainder Theorem to compute the unique value of {\displaystyle M\in \mathbb {Z_{N}} } $M\in {\mathbb {Z_{N}}}$ which satisfies {\displaystyle M\equiv M_{p}{\bmod {p}}} $M\equiv M_{p}{\bmod {p}}$ and {\displaystyle M\equiv M_{q}{\bmod {q}}} $M\equiv M_{q}{\bmod {q}}$ . The result of {\displaystyle M} $M$ satisfies {\displaystyle M\equiv C^{d}{\bmod {N}}} $M\equiv C^{d}{\bmod {N}}$ as needed. The point is that Wiener’s Attack on Bitcoin does not apply here because the value of {\displaystyle d{\bmod {\lambda }}(N)} $d{\bmod {\lambda }}(N)$ can be large.^[3]

How Wiener’s Attack on Bitcoin works

Note that{\displaystyle \lambda (N)=\operatorname {lcm} (p-1,q-1)={\frac {(p-1)(q-1)}{G}}={\frac {\varphi (N)}{G}}} $\lambda (N)=\operatorname {lcm} (p-1,q-1)={\frac {(p-1)(q-1)}{G}}={\frac {\varphi (N)}{G}}$

where {\displaystyle G=\gcd(p-1,q-1)} $G=\gcd(p-1,q-1)$

Since{\displaystyle ed\equiv 1{\pmod {\lambda (N)}}} $ed\equiv 1{\pmod {\lambda (N)}}$ ,

there exists an integer K such that{\displaystyle ed=K\times \lambda (N)+1} $ed=K\times \lambda (N)+1$ {\displaystyle ed={\frac {K}{G}}(p-1)(q-1)+1} $ed={\frac {K}{G}}(p-1)(q-1)+1$

Defining {\displaystyle k={\frac {K}{\gcd(K,G)}}} $k={\frac {K}{\gcd(K,G)}}$ and {\displaystyle g={\frac {G}{\gcd(K,G)}}} $g={\frac {G}{\gcd(K,G)}}$ , and substituting into the above gives:{\displaystyle ed={\frac {k}{g}}(p-1)(q-1)+1} $ed={\frac {k}{g}}(p-1)(q-1)+1$ .

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

So, {\displaystyle {\frac {e}{pq}}} ${\frac {e}{pq}}$ is slightly smaller than {\displaystyle {\frac {k}{dg}}} ${\frac {k}{dg}}$ , 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

Let {\displaystyle \ N=pq} $\ N=pq$ with {\displaystyle \ q<p<2q} $\ q<p<2q$ . Let {\displaystyle d<{\frac {1}{3}}N^{\frac {1}{4}}} $d<{\frac {1}{3}}N^{{{\frac {1}{4}}}}$ .
Given {\displaystyle \left\langle N,e\right\rangle } $\left\langle N,e\right\rangle$ with {\displaystyle ed\equiv 1\ (\mathrm {mod} \ \lambda (N))} $ed\equiv 1\ (\mathrm {mod} \ \lambda (N))$ , the Attack on Bitcoiner can efficiently recover {\displaystyle d} $d$ .^[2]^{[failed verification]}

Example

Suppose that the public keys are {\displaystyle \left\langle N,e\right\rangle =\left\langle 90581,17993\right\rangle } $\left\langle N,e\right\rangle =\left\langle 90581,17993\right\rangle$
The Attack on Bitcoin shall determine {\displaystyle d} $d$ .
By using Wiener’s Theorem and continued fractions to approximate {\displaystyle d} $d$ , first we try to find the continued fractions expansion of {\displaystyle {\frac {e}{N}}} ${\frac {e}{N}}$ . Note that this algorithm finds fractions in their lowest terms. We know that{\displaystyle {\frac {e}{N}}={\frac {17993}{90581}}={\cfrac {1}{5+{\cfrac {1}{29+\dots +{\cfrac {1}{3}}}}}}=\left[0,5,29,4,1,3,2,4,3\right]} ${\frac {e}{N}}={\frac {17993}{90581}}={\cfrac {1}{5+{\cfrac {1}{29+\dots +{\cfrac {1}{3}}}}}}=\left[0,5,29,4,1,3,2,4,3\right]$

According to the continued fractions expansion of {\displaystyle {\frac {e}{N}}} ${\frac {e}{N}}$ , all convergents {\displaystyle {\frac {k}{d}}} ${\frac {k}{d}}$ are:{\displaystyle {\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}}} ${\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 convergent does not produce a factorization of {\displaystyle N} $N$ . However, the convergent {\displaystyle {\frac {1}{5}}} ${\frac {1}{5}}$ yields{\displaystyle \varphi (N)={\frac {ed-1}{k}}={\frac {17993\times 5-1}{1}}=89964} $\varphi (N)={\frac {ed-1}{k}}={\frac {17993\times 5-1}{1}}=89964$

Now, if we solve the equation{\displaystyle x^{2}-\left(\left(N-\varphi (N)\right)+1\right)x+N=0} $x^{2}-\left(\left(N-\varphi (N)\right)+1\right)x+N=0$ {\displaystyle x^{2}-\left(\left(90581-89964\right)+1\right)x+90581=0} $x^{2}-\left(\left(90581-89964\right)+1\right)x+90581=0$ {\displaystyle x^{2}-618x+90581=0} $x^{2}-618x+90581=0$

then we find the roots which are {\displaystyle x=379;239} $x=379;239$ . Therefore we have found the factorization{\displaystyle N=90581=379\times 239=p\times q} $N=90581=379\times 239=p\times q$ .

Notice that, for the modulus {\displaystyle N=90581} $N=90581$ , Wiener’s Theorem will work if
{\displaystyle d<{\frac {N^{\frac {1}{4}}}{3}}\approx 5.7828} $d<{\frac {N^{{{\frac {1}{4}}}}}{3}}\approx 5.7828$ .

Proof of Wiener’s theorem

The proof is based on approximations using continued fractions.^[2]^[4]
Since {\displaystyle ed=1{\bmod {\lambda }}(N)} $ed=1{\bmod {\lambda }}(N)$ , there exists a {\displaystyle {\mathit {k}}} ${\mathit {k}}$ such that {\displaystyle ed-k\lambda (N)=1} $ed-k\lambda (N)=1$ . Therefore{\displaystyle \left|{\frac {e}{\lambda (N)}}-{\frac {k}{d}}\right\vert ={\frac {1}{d\lambda (N)}}} $\left|{\frac {e}{\lambda (N)}}-{\frac {k}{d}}\right\vert ={\frac {1}{d\lambda (N)}}$ .

Let {\displaystyle G=\gcd(p-1,q-1)} $G=\gcd(p-1,q-1)$ ; note that if {\displaystyle \varphi (N)} $\varphi (N)$ is used instead of {\displaystyle \lambda (N)} $\lambda (N)$ , then the proof can be replaced with {\displaystyle G=1} $G=1$ and {\displaystyle \varphi (N)} $\varphi (N)$ replaced with {\displaystyle \lambda (N)} $\lambda (N)$ .

Then multiplying by {\displaystyle {\frac {1}{G}}} ${\frac {1}{G}}$ ,{\displaystyle \left|{\frac {e}{\varphi (N)}}-{\frac {k}{Gd}}\right\vert ={\frac {1}{d\varphi (N)}}} $\left|{\frac {e}{\varphi (N)}}-{\frac {k}{Gd}}\right\vert ={\frac {1}{d\varphi (N)}}$

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

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

Using {\displaystyle N} $N$ in place of {\displaystyle \varphi (N)} $\varphi (N)$ we obtain:{\displaystyle {\begin{aligned}\left\vert {\frac {e}{N}}-{\frac {k}{Gd}}\right\vert &=\left\vert {\frac {edG-kN}{NGd}}\right\vert \\&=\left\vert {\frac {edG-k\varphi (N)-kN+k\varphi (N)}{NGd}}\right\vert \\&=\left\vert {\frac {1-k(N-\varphi (N))}{NGd}}\right\vert \\&\leq \left\vert {\frac {3k{\sqrt {N}}}{NGd}}\right\vert ={\frac {3k{\sqrt {N}}}{{\sqrt {N}}{\sqrt {N}}Gd}}\leq {\frac {3k}{d{\sqrt {N}}}}\end{aligned}}} ${\begin{aligned}\left\vert {\frac {e}{N}}-{\frac {k}{Gd}}\right\vert &=\left\vert {\frac {edG-kN}{NGd}}\right\vert \\&=\left\vert {\frac {edG-k\varphi (N)-kN+k\varphi (N)}{NGd}}\right\vert \\&=\left\vert {\frac {1-k(N-\varphi (N))}{NGd}}\right\vert \\&\leq \left\vert {\frac {3k{\sqrt {N}}}{NGd}}\right\vert ={\frac {3k{\sqrt {N}}}{{\sqrt {N}}{\sqrt {N}}Gd}}\leq {\frac {3k}{d{\sqrt {N}}}}\end{aligned}}$

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

Since {\displaystyle k<d} $k<d$ and {\displaystyle d<{\frac {1}{3}}N^{\frac {1}{4}}} $d<{\frac {1}{3}}N^{\frac {1}{4}}$ . Hence we obtain:(1) {\displaystyle \left\vert {\frac {e}{N}}-{\frac {k}{Gd}}\right\vert \leq {\frac {1}{dN^{\frac {1}{4}}}}} $\left\vert {\frac {e}{N}}-{\frac {k}{Gd}}\right\vert \leq {\frac {1}{dN^{\frac {1}{4}}}}$

Since {\displaystyle d<{\frac {1}{3}}N^{\frac {1}{4}},2d<3d,} $d<{\frac {1}{3}}N^{{{\frac {1}{4}}}},2d<3d,$ then {\displaystyle 2d<3d<N^{\frac {1}{4}}} $2d<3d<N^{\frac {1}{4}}$ , we obtain:{\displaystyle 2d<N^{\frac {1}{4}}} $2d<N^{\frac {1}{4}}$ , so (2) {\displaystyle {\frac {1}{2d}}>{\frac {1}{N^{\frac {1}{4}}}}} ${\displaystyle {\frac {1}{2d}}>{\frac {1}{N^{\frac {1}{4}}}}}”></p> <p>From (1) and (2), we can conclude that{\displaystyle \left\vert {\frac {e}{N}}-{\frac {k}{Gd}}\right\vert \leq {\frac {3k}{d{\sqrt {N}}}}<{\frac {1}{d\cdot 2d}}={\frac {1}{2d^{2}}}}<img decoding=$

If {\displaystyle \left\vert x-{\frac {a}{b}}\right\vert <{\frac {1}{2b^{2}}}} $\left\vert x-{\frac {a}{b}}\right\vert <{\frac {1}{2b^{2}}}$ , then {\displaystyle {\frac {a}{b}}} ${\frac {a}{b}}$ is a convergent of {\displaystyle x} $x$ , thus {\displaystyle {\frac {k}{Gd}}} ${\frac {k}{Gd}}$ appears among the convergents of {\displaystyle {\frac {e}{N}}} ${\frac {e}{N}}$ . Therefore the algorithm will indeed eventually find {\displaystyle {\frac {k}{Gd}}} ${\frac {k}{Gd}}$ .^{[further explanation needed]}