Foreword

I was struggling a lot with lattices in CTF challenges, so I spent some time learning about what are lattices and how to use them in solving CTF Challenges.

Great resource to get started

The following will be about this paper: Recovering cryptographic keys from partial information, by example which heavily employs lattices for recovering cryptographic secrets. The header name reflects the corresponding header in the paper.

Small unrelated nugget

From TSJ CTF challenge Signature, also mentioned in Lightweight Introduction to Lattices.

Two nuggets:

$$ a \oplus b = a + b - 2 (a \land b) $$

For two n bits integer $a,b$,

$$ a \land b = \sum_{i=0}^{n-1} 2^i a_i b_i $$

where $a_i$ and $b_i$ is their n-th bit.

This serves the conversion of the problem into a Hidden Number problem.

Relationships between RSA Key Elements

Implementation resources

Recover RSA values

It is mentioned in the paper that any of the secret values $p, q, d, d_p, d_q$ or $q_{inv}$ suffices to compute all of the other values when the public key $(N, e)$ is known

  • Knowing $p, q$, it is trivial to calculate the rest.
  • Knowing $d$, refer to this article for recovering $p, q$
  • Knowing $dp, dq$, refer to this article for recovering $p, q$
  • Knowing $q_{inv}$, we can recover $p, q$ by the relation $q ^2 * q_{inv} - q \equiv 0 \mod N$, as mentioned in the paper.

Factorization from consecutive bits of p

  • Instead of the lattice presented in the paper, which works perfectly fine, we can use a Coppersmith script for the job. I use the Coppersmith implementation from defund.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

# From Defund's Coppersmith
def small_roots(f, bounds, m=1, d=None):
    ...

N = 0x4d14933399708b4a5276373cb5b756f312f023c43d60b323ba24cee670f5
a = 0x68323401cb3a10959e7bfdc0000000

R = 2 ^ 30 

P.<x> = PolynomialRing(Zmod(N), 1)
f = a + x 

print(small_roots(f, bounds=(R,), m=2, d=4))

Note that Coppersmith does not only solve for equation $\mod N$, but also for $\mod N^{\beta}$ too ($\beta > 0.5$).

Partial recovery of RSA $d_p$

Why do we multiply the entire equation with $e ^ {-1} \mod N$? We have from Equation 4:

$$ e(a + r) - 1 + k_p \equiv 0 \mod p $$

We also have $e \times e^{-1} \equiv 1 \mod N$, or $e \times e^{-1} = 1 + m N$

Hence, multiplying Equation 4 with $e ^ {-1} \mod N$, we have:

$$ ee^{-1} (a + r) + e ^ {-1}(k_p - 1) \equiv 0 \mod p $$ $$ (1 + mN)(a + r) + e ^ {-1}(k_p - 1) \equiv 0 \mod p $$

Since N divides p, we have:

$$ a + r + e ^ {-1}(k_p - 1) \equiv 0 \mod p $$

which is the equation from the paper.

In a somewhat similar manner, this is an explanation for the multiplication of $2 ^ {-l}$ in RSA key recovery from least significant bits of p portion of the paper.

For the code, the following “should” work. Again the parameter $m, d$ should be changed for different number

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

# From Defund's Coppersmith
def small_roots(f, bounds, m=1, d=None):
    ...

N = 0x4d14933399708b4a5276373cb5b756f312f023c43d60b323ba24cee670f5
e = 65537

a = 0x25822d06984a06be5596fcc0000000
P.<x> = PolynomialRing(Zmod(N), 1)
for i in range(1, 65537):
	print(i)
	f = a + x + pow(e, -1, N) * (i - 1)
	roots = small_roots(f, bounds=(2 ^ 30,), m=2, d=4)
	if roots:
		print(roots)