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.

# 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

# 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)

Lattice usage in Cryptography