Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

23.3 An Attack on RSA

Alice wants to send Bob a message of the form

T h e a n s w e r i s * *

$T h e a n s w e r i s * *$

T h e p a s s w o r d f o r y o u r n e w a c c o u n t i s * * * * * * * * .

$T h e p a s s w o r d f o r y o u r n e w a c c o u n t i s * * * * * * * * .$

In these cases, the message is of the form

m = B + x, where B is fixed and | x | \leq Y

$m = B + x, where B is fixed and | x | \leq Y$

for some integer $Y$ $Y$ . We’ll present an attack that works when the encryption exponent is small.

Suppose Bob has public RSA key $(n, e) = (n, 3)$ $(n, e) = (n, 3)$ . Then the ciphertext is

c \equiv (B + x)^{3} (mod n) .

$c \equiv (B + x)^{3} (mod n) .$

We assume that Eve knows $B, Y$ $B, Y$ , and $n$ $n$ , so she only needs to find $x$ $x$ . She forms the polynomial

\begin{array}{l} f (T) & = & ​ {(B + T)}^{3} - c = T^{3} + 3 B T^{2} + 3 B^{2} T + B^{3} - c \\ \equiv & T^{3} + a_{2} T^{2} + a_{1} T + a_{0} (mod n) . \end{array}

$\begin{array}{l} f (T) & = & {(B + T)}^{3} - c = T^{3} + 3 B T^{2} + 3 B^{2} T + B^{3} - c \\ \equiv & T^{3} + a_{2} T^{2} + a_{1} T + a_{0} (mod n) . \end{array}$

Eve is looking for $| x | \leq Y$ $| x | \leq Y$ such that $f (x) \equiv 0 (mod n)$ $f (x) \equiv 0 (mod n)$ . In other words, she is looking for a small solution to a polynomial congruence $f (T) \equiv 0 (mod n)$ $f (T) \equiv 0 (mod n)$ .

Eve applies the LLL algorithm to the lattice generated by the vectors

\begin{matrix} v_{1} = (n, 0, 0, 0), v_{2} = (0, Y n, 0, 0), v_{3} = (0, 0, Y^{2} n, 0), \\ v_{4} = (a_{0}, a_{1} Y, a_{2} Y^{2}, Y^{3}) . \end{matrix}

$\begin{matrix} v_{1} = (n, 0, 0, 0), v_{2} = (0, Y n, 0, 0), v_{3} = (0, 0, Y^{2} n, 0), \\ v_{4} = (a_{0}, a_{1} Y, a_{2} Y^{2}, Y^{3}) . \end{matrix}$

This yields a new basis $b_{1}, \dots, b_{4}$ $b_{1}, \dots, b_{4}$ , but we need only $b_{1}$ $b_{1}$ . The theorem in Subsection 23.2.2 tells us that

\begin{array}{l} ∥ b_{1} ∥ ​ ​ & \leq & ​ ​ 2^{3 / 4} \det {(v_{1}, \dots, v_{4})}^{1 / 4} \end{array}

$\begin{array}{l} ∥ b_{1} ∥ & \leq & 2^{3 / 4} \det {(v_{1}, \dots, v_{4})}^{1 / 4} \end{array}$ (23.2)

\begin{array}{l} = & ​ ​ 2^{3 / 4} {(n^{3} Y^{6})}^{1 / 4} = 2^{3 / 4} n^{3 / 4} Y^{3 / 2} . \end{array}

$\begin{array}{l} = & 2^{3 / 4} {(n^{3} Y^{6})}^{1 / 4} = 2^{3 / 4} n^{3 / 4} Y^{3 / 2} . \end{array}$ (23.3)

We can write

b_{1} = c_{1} v_{1} + \dots + c_{4} v_{4} = (e_{0}, Y e_{1}, Y^{2} e_{2}, Y^{3} e_{3})

$b_{1} = c_{1} v_{1} + \dots + c_{4} v_{4} = (e_{0}, Y e_{1}, Y^{2} e_{2}, Y^{3} e_{3})$

with integers $c_{i}$ $c_{i}$ and with

\begin{array}{l} e_{0} & = & c_{1} n + c_{4} a_{0} \\ e_{1} & = & c_{2} n + c_{4} a_{1} \\ e_{2} & = & c_{3} n + c_{4} a_{2} \\ e_{3} & = & c_{4} . \end{array}

$\begin{array}{l} e_{0} & = & c_{1} n + c_{4} a_{0} \\ e_{1} & = & c_{2} n + c_{4} a_{1} \\ e_{2} & = & c_{3} n + c_{4} a_{2} \\ e_{3} & = & c_{4} . \end{array}$

It is easy to see that

e_{i} \equiv c_{4} a_{i} (mod n), 0 \leq i \leq 2.

$e_{i} \equiv c_{4} a_{i} (mod n), 0 \leq i \leq 2.$

Form the polynomial

g (T) = e_{3} T^{3} + e_{2} T^{2} + e_{1} T + e_{0} .

$g (T) = e_{3} T^{3} + e_{2} T^{2} + e_{1} T + e_{0} .$

Then, since the integer $x$ $x$ satisfies $f (x) \equiv 0 (mod n)$ $f (x) \equiv 0 (mod n)$ and since the coefficients of $c_{4} f (T)$ $c_{4} f (T)$ and $g (T)$ $g (T)$ are congruent mod $n$ $n$ ,

0 \equiv c_{4} f (x) \equiv g (x) (mod n) .

$0 \equiv c_{4} f (x) \equiv g (x) (mod n) .$

Assume now that

\begin{array}{rcl} Y < 2^{- 7 / 6} n^{1 / 6} . \end{array}

$\begin{array}{rcl} Y < 2^{- 7 / 6} n^{1 / 6} . \end{array}$ (23.4)

Then

\begin{array}{l} | g (x) | & \leq & | e_{0} | + | e_{1} x | + | e_{2} x^{2} | + | e_{3} x^{3} | \\ \leq & | e_{0} | + | e_{1} | Y + | e_{2} | Y^{2} + | e_{3} | Y^{3} \\ = & (1, 1, 1, 1) \cdot (| e_{0} |, | e_{1} Y |, | e_{2} Y^{2} |, | e_{3} Y^{3} |) \\ \leq & ∥ (1, 1, 1, 1) ∥ ((| e_{0} |, \dots, | e_{3} Y^{3} |)) \\ = & 2 ∥ b_{1} ∥, \end{array}

$\begin{array}{l} | g (x) | & \leq & | e_{0} | + | e_{1} x | + | e_{2} x^{2} | + | e_{3} x^{3} | \\ \leq & | e_{0} | + | e_{1} | Y + | e_{2} | Y^{2} + | e_{3} | Y^{3} \\ = & (1, 1, 1, 1) \cdot (| e_{0} |, | e_{1} Y |, | e_{2} Y^{2} |, | e_{3} Y^{3} |) \\ \leq & ∥ (1, 1, 1, 1) ∥ ((| e_{0} |, \dots, | e_{3} Y^{3} |)) \\ = & 2 ∥ b_{1} ∥, \end{array}$

where the last inequality used the Cauchy-Schwarz inequality for dot products (that is, $v \cdot w \leq ∥ v ∥ ∥ w ∥$ $v \cdot w \leq ∥ v ∥ ∥ w ∥$ ). Since, by (17.3) and (17.4),

∥ b_{1} ∥ \leq 2^{3 / 4} n^{3 / 4} Y^{3 / 2} < 2^{3 / 4} n^{3 / 4} {(2^{- 7 / 6} n^{1 / 6})}^{3 / 2} = 2^{- 1} n,

$∥ b_{1} ∥ \leq 2^{3 / 4} n^{3 / 4} Y^{3 / 2} < 2^{3 / 4} n^{3 / 4} {(2^{- 7 / 6} n^{1 / 6})}^{3 / 2} = 2^{- 1} n,$

we obtain

| g (x) | < n .

$| g (x) | < n .$

Since $g (x) \equiv 0 (mod n)$ $g (x) \equiv 0 (mod n)$ , we must have $g (x) = 0$ $g (x) = 0$ . The zeros of $g (T)$ $g (T)$ may be determined numerically, and we obtain at most three candidates for $x$ $x$ . Each of these may be tried to see if it gives the correct ciphertext. Therefore, Eve can find $x$ $x$ .

Note that the above method replaces the problem of finding a solution to the congruence $f (T) \equiv 0 (mod n)$ $f (T) \equiv 0 (mod n)$ with the exact, non-congruence, equation $g (T) = 0$ $g (T) = 0$ . Solving a congruence often requires factoring $n$ $n$ , but solving exact equations can be done by numerical procedures such as Newton’s method.

In exactly the same way, we can find small solutions (if they exist) to a polynomial congruence of degree $d$ $d$ , using a lattice of dimension $d + 1$ $d + 1$ . Of course, $d$ $d$ must be small enough that LLL will run in a reasonable time. Improvements to this method exist. Coppersmith ([Coppersmith2]) gave an algorithm using higher-dimensional lattices that looks for small solutions $x$ $x$ to a monic (that is, the highest-degree coefficient equals 1) polynomial equation $f (T) \equiv 0 (mod n)$ $f (T) \equiv 0 (mod n)$ of degree $d$ $d$ . If $| x | \leq n^{1 / d}$ $| x | \leq n^{1 / d}$ , then the algorithm runs in time polynomial in $log n$ $log n$ and $d$ $d$ .

Example

Let

n = 1927841055428697487157594258917

$n = 1927841055428697487157594258917$

(which happens to be the product of the primes $p = 757285757575769$ $p = 757285757575769$ and $q = 2545724696579693$ $q = 2545724696579693$ , but Eve does not know this). Alice is sending the message

T h e a n s w e r i s * *,

$T h e a n s w e r i s * *,$

where ** denotes a two-digit number. Therefore the message is $m = B + x$ $m = B + x$ where $B = 200805000114192305180009190000$ $B = 200805000114192305180009190000$ and $0 \leq x < 100$ $0 \leq x < 100$ . Suppose Alice sends the ciphertext $c \equiv (B + x)^{3} \equiv 30326308498619648559464058932 (mod n)$ $c \equiv (B + x)^{3} \equiv 30326308498619648559464058932 (mod n)$ . Eve forms the polynomial

\begin{matrix} f (T) = {(B + T)}^{3} - c \equiv T^{3} + a_{2} T^{2} + a_{1} T + a_{0} & (mod n), \end{matrix}

$\begin{matrix} f (T) = {(B + T)}^{3} - c \equiv T^{3} + a_{2} T^{2} + a_{1} T + a_{0} & (mod n), \end{matrix}$

where

\begin{array}{l} a_{2} & = & 602415000342576915540027570000 \\ a_{1} & = & 1123549124004247469362171467964 \\ a_{0} & = & 587324114445679876954457927616. \end{array}

$\begin{array}{l} a_{2} & = & 602415000342576915540027570000 \\ a_{1} & = & 1123549124004247469362171467964 \\ a_{0} & = & 587324114445679876954457927616. \end{array}$

Note that $a_{0} \equiv B^{3} - c (mod n)$ $a_{0} \equiv B^{3} - c (mod n)$ .

Eve uses LLL to find a root of $f (T) (mod n)$ $f (T) (mod n)$ . She lets $Y = 100$ $Y = 100$ and forms the vectors

\begin{array}{l} \begin{matrix} v_{1} = (n, 0, 0, 0), & v_{2} = (0, 100 n, 0, 0), & v_{3} = (0, 0, 10^{4} n, 0) \end{matrix} \\ v_{4} = (a_{0}, 100 a_{1}, 10^{4}_{a 2}, 10^{6}) . \end{array}

$\begin{array}{l} \begin{matrix} v_{1} = (n, 0, 0, 0), & v_{2} = (0, 100 n, 0, 0), & v_{3} = (0, 0, 10^{4} n, 0) \end{matrix} \\ v_{4} = (a_{0}, 100 a_{1}, 10^{4}_{a 2}, 10^{6}) . \end{array}$

The LLL algorithm produces the vector

\begin{array}{rcl} 308331465484476402 v_{1} + 589837092377839611 v_{2} \\ + 316253828707108264 v_{3} - 1012071602751202635 v_{4} \\ = (246073430665887186108474, - 577816087453534232385300, \\ 405848565585194400880000, - 1012071602751202635000000) . \end{array}

$\begin{array}{rcl} 308331465484476402 v_{1} + 589837092377839611 v_{2} \\ + 316253828707108264 v_{3} - 1012071602751202635 v_{4} \\ = (246073430665887186108474, - 577816087453534232385300, \\ 405848565585194400880000, - 1012071602751202635000000) . \end{array}$

Eve then looks at the polynomial

\begin{array}{l} g (T) ​ ​ & = & ​ ​ - 1012071602751202635 T^{3} + 40584856558519440088 T^{2} \\ - 5778160874535342323853 T + 246073430665887186108474. \end{array}

$\begin{array}{l} g (T) & = & - 1012071602751202635 T^{3} + 40584856558519440088 T^{2} \\ - 5778160874535342323853 T + 246073430665887186108474. \end{array}$

The roots of $g (T)$ $g (T)$ are computed numerically to be

42.000000000, - 0.949612039 \pm 76.079608511 i .

$42.000000000, - 0.949612039 \pm 76.079608511 i .$

It is easily checked that $g (42) = 0$ $g (42) = 0$ , so the plaintext is

The answer is 42 .

$The answer is 42 .$

Of course, a brute force search through all possibilities for the two-digit number $x$ $x$ could have been used to find the answer in this case. However, if $n$ $n$ is taken to be a 200-digit number, then $Y$ $Y$ can have around 33 digits. A brute force search would usually not succeed in this situation.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 23.3 An Attack on RSA

Create new playlist

Sign In

Sign Up

Table of Contents for
23.3 An Attack on RSA