Recent Developments in Cryptography:

What is ”breaking RSA”? J.H. Davenport University of Bath

         jhd@maths.bath.ac.uk

Conventions

• Use classical arithmetic, e.g. multiplying n-bit integers takes O(n^{2}).

• Vector spaces generally have dimension d.

• ||a|| = √∑_{i=1}^{d} a_{i}^{2}; || ∑_{i=0}^{d} a_{i}x^{i}|| = √∑_{i=0}^{d} a_{i}^{2}.

• “choose” means “chooses carefully, avoiding many well-known weaknesses”.

Lattices (simply)

• A lattice L is a discrete additive subgroup of R^{d}.

• For simplicity, assume L ⊆ Z^{d} and dim L = d.

• L is generated by a basis (b_{1}, …, b_{d}): b_{i} ∈ Z^{d}.

• Many bases generate the same L, but

det (L) = | det (b_{1}, …, b_{d})|

is an invariant. Example: (2, 5) and (3, 8) generate a lattice of determinant 1, but this lattice can also be generated by (0, 1) and (1, 0).

Short vectors (theoretically)

Define λ_{1}(L) to be min _{{v≠0 \atop v∈L}} ||v||. Define λ_{2}(L) = min_{{dim ⟨v1,v2⟩=2 \atop v1,v2∈L}} max (||v_{1}||, ||v_{2}||), and

so on. Minkowski: λ_{1}(L) ≤ √d(det (L))^{1/d} and, more generally,

r ; ∏ ; i=1 λ_{i}(L) ≤ d^{r/2}(det (L))^{r/d}.

However, we know no efficient ways to compute these. Consider L = ⟨(1, 0), (0, 100)⟩: det (L) = 100. λ_{1} = ||(1, 0)|| = 1 < √2 · 10; λ_{2} = ||(0, 100)|| = 100 < 2 · 10^{2}.

Gram-Schmidt orthogonalisation of basis (b_{1}, …, b_{d}).

Define (recursively)

• b_{i}^{∗} = b_{i} − ∑_{j=1}^{i−1} μ_{i,j}b_{j}^{∗};

• μ_{i,j} = (b_{i} · b_{j}^{∗})/||b_{j}^{∗}||^{2}. The (b_{i}^{∗}) form an orthogonal basis for the same lattice over Q, but not, normally, over Z.

Lenstra–Lenstra–Lovács reduction

The basis (b_{1}, …, b_{d}) is LLL-reduced if (were one to apply Gram-Schmidt to it!)

1. |μ_{i,j}| ≤ \frac{1}{2}, 1 ≤ j < i ≤ d (else reduce b_{i} by an integral multiple of b_{j})

2. ||b_{i}^{∗} + μ_{i,i−1}b_{i−1}^{∗}||^{2} ≥ \frac{3}{4}||b_{i−1}^{∗}||^{2} (else swap b_{i} and b_{i−1})

This process terminates in polynomial time:

O(d^{6} log^{3} max |b_{i,j}|).

Any number in [\frac{1}{4}, 1) will do instead of \frac{3}{4}.

What properties?

• Certainly not canonical!

• ||b_{1}|| ≤ 2^{(d−1)/4} det (L)^{1/d}.

• ||b_{i}|| ≤ 2^{(d−1)/2} λ_{i}(L).

• ∏_{i=1}^{d} ||b_{i}|| ≤ 2^{d(d−1)/4} det (L).

• Often we do much better than this.

• Many variants/improvements.

• Still a black art.

Small modular roots (Coppersmith; Howgrave-Graham)

Given a monic p(x) of degree k, with a root x_{0} mod N, with |x_{0}| ≤ X. For i in 1 … hk, define v = ⌊(i − 1)/k⌋ and u = (i − 1) − kv, and

q_{i}(x) = q_{u,v}(x) = N^{h−1−v}x^{u}(p(x))^{v}.

Note q_{i}(x_{0}) ≡ 0 (mod N^{h−1}). Treat the coefficients of each q_{i} (multiplying the coefficent of x^{j} by X^{j}) as entries of a (lower-triangular) (hk)^{2} matrix M.

An example

x^{2} + 14x + 19 ≡ 0 (mod 35).

Take X = 2 and h = 3.

(N^{2} xN^{2} Np Nxp p^{2} xp^{2})^{T} =

(\begin{matrix}35^{2} \\ 0 & 35^{2} · 2 \\ 35 · 19 & 35 · 14 · 2 & 35 · 2^{2} \\ 0 & 35 · 19 · 2 & 35 · 14 · 2^{2} & 35 · 2^{3} \\ 361 & 532 · 2 & 234 · 2^{2} & 28 · 2^{3} & 2^{4} \\ 0 & 361 · 2 & 532 · 2^{2} & 234 · 2^{3} & 28 · 2^{4} & 2^{5} \end{matrix} )

Theory (continued)

Since M is lower triangular,

det (M) = X^{hk(hk−1)/2} N^{hk(h−1)/2} .

If b is the first vector in LLL-reduced M, then

||b|| ≤ 2^{(hk−1)/4} X^{(hk−1)/2} N^{(h−1)/2} .

Dividing b_{j} by X^{j−1} (which we can do) gives a polynomial r(x) over Z, an integral multiple of the q_{i}, so r(x_{0}) ≡ 0 (mod N^{h−1}). For |x| ≤ X, |r(x)| ≤ ∑ |b_{i}| ≤ √hk||b||. So |r(x)| ≤ (2^{(hk−1)/4} √hk) X^{(hk−1)/2} N^{(h−1)/2} . Choosing

X = ⌈(2^{−1/2} (hk)^{−1/(hk−1)} ) N^{(h−1)/(hk−1)} ⌉ − 1

gives |r(x)| < N^{h−1}. Hence r(x_{0}) = 0.

Example (continued)

This matrix reduces to

(\begin{matrix}3 & 8 · 2 & −24 · 2^{2} & −8 · 2^{3} & −1 · 2^{4} & 2 · 2^{5} \\ 49 & 50 · 2 & 0 & 20 · 2^{3} & 0 & 2 · 2^{5} \\ 115 & −83 · 2 & 4 · 2^{2} & 13 · 2^{3} & 6 · 2^{4} & 2 · 2^{5} \\ 61 & 16 · 2 & 36 · 2^{2} & −16 · 2^{3} & 3 · 2^{4} & 4 · 2^{5} \\ 21 & −37 · 2 & −14 · 2^{2} & 2 · 2^{3} & 14 · 2^{4} & −4 · 2^{5} \\ −201 & 4 · 2 & 33 · 2^{2} & −4 · 2^{3} & −3 · 2^{4} & 1 · 2^{5} \end{matrix} )

so r(x) = 2x^{5} − x^{4} − 8x^{3} − 24x^{2} + 8x + 3, and x_{0} = 3. x_{0} > X, but LLL sometimes over-performs.

Observations

• Can remove first row and column from M.

• Finds solutions up to O(N^{(h−1)/(hk−1)} ) → N^{1/k}.

• Time O(h^{9}k^{6} log^{3} N).

• For k = 3 we get

\begin{matrix}h = 2 & h = 3 & h = 4 & h = 5 & h = 6 & h = 67 \\ N^{0.2} & N^{0.25} & N^{0.27} & N^{0.286} & N^{0.294} & N^{0.33} \end{matrix}

• Since one normally uses with small d = hk, the sub-optimality of LLL w.r.t d is not a major problem.

RSA (as encryption)

B chooses p, q primes, and e coprime to (p − 1)(q − 1); computes N = pq and D such that De ≡ 1 (mod (p − 1)(q − 1)); publishes n-bit N and e.

A ⟶ B
c ≡ m^{e} (mod N) c m ≡ c^{D} (mod N)
↓
E

A and B have tasks O(n^{3}). What about E?

E’s options factoring N

⇕  O(n^{2})

ϕ(N) = (p − 1)(q − 1)

⇓  O(n^{2})

computing D

⇓  O(n^{3})

computing m from c

But there might be other ways, e.g. an O(n^{6}) means of computing roots directly.

“breaking RSA” = “factoring”?

• Define “completely breaking RSA” as having an algorithm which, given N, e and c, computes m.

• Then this is no harder than factoring: it may in fact be easier.

• “Breaking how system X uses RSA” depends very much on system X: if system X always chooses e = 1, it is trivial to break.

• Focus on case of “small” e, e.g. e = 3

+ used when A has less compute power than B.

One scenario (Coppersmith) almost known-plaintext

• The message is “withdraw £L from this account”, and I know everything (e.g. from a discarded receipt) except the PIN z.

• Assume (purely for notational simplicity) the PIN is at the end of the message.

• Then I know m_{0} (message if z = 0) and have to solve (m_{0} + z)^{e} ≡ c (mod N).

RSA — Mostly Known Messages

Suppose e is small (say e = 3) and the message m is mostly known, say m = m_{0} +m_{1} with |m_{1}| < N^{1/e}. Then solving (m_{0}+m_{1})^{e}−c ≡ 0 (mod N) gives m_{1}. Works if m_{1} is not at end of m, say m = m_{0} + 2^{s}m_{1}. Note that this does not “break N” in the sense of finding the decrypting exponent D. Some heuristic extensions for case where unknown part is in more than one piece.

RSA — Mostly Similar Messages

Suppose e is small (say e = 3) and the message m_{2} is mostly similar to message m_{1}. So m_{1}^{e} = c_{1} and (m_{1} + δ)^{e} = c_{2}. Using resultants (for e = 3)

δ^{9}+3(c_{1}−c_{2})δ^{6}+3(c_{1}^{2}+7c_{1}c_{2}+c_{2}^{2})δ^{3}+(c_{1}−c_{2})^{3}

≡ 0 (mod N)

Note this is an equation in δ^{3}, and should be solved as such. Finds |δ| < N^{1/e^{2}} .

gcd_{z} (z^{3} − c_{1}, (z + δ)^{3} − c_{2}) = z − m_{1}.

Note that increasing N increases δ findable.

IP packets encrypted with RSA

Assume (denial of service attack) that we can force A’s higher-level protocols to replay. This replay will differ in IP identification (16 bits) and in the effect of that on the checksum). Have to solve

m^{e} = c_{1}; (m + 2^{48} δ − δ − ±65535)^{e} = c_{2}

(where the ±65535 factor allows for the possibility of wrap-round in the checksum): again an e-degree equation in m^{e}.

Difficulty of solving — Estimates e = 3 512-bit RSA trivial: < 1 second. 1024-bit RSA: < 10 seconds. e=5 512-bit RSA needs h = 4: 20 × 20 lattice

with 2k-bit entries. δ in 11 bits h = 2, 10 × 10 lattice with 1k-bit

entries. 1024-bit RSA: 10 × 10 lattice with 2k-bit en-

tries.

Factoring N = p^{r}q

Boneh, Durfee, Howgrave-Graham

Choose (enumerate) P close to p, and solve for (P + x)^{r} ≡ 0 (mod p^{r}). p^{r} is unknown, but divides N. Time exp (\frac{c+1}{r+c} log p) r^{15} log^{3} N, where c = log q/ log p. Similar to ECM and NFS when r = √log p.