An RSA challenge with leakage of MSB from the CRT exponents of the private key. The parameters allow an attack described in a paper by May (hinted by the title), Nowakowski and Sarkar leveraging the Coppersmith method to recover the key.
Challenge Description
The challenge setting is quite simple. We have a Crypto class defining some parameters:
1self.bits = bits
2self.alpha = 1/9
3self.delta = 1/4
4self.known = int(self.bits*self.delta)
The class then generates an RSA instance using CRT exponents:
1while True:
2 p, q = [getPrime(self.bits//2) for _ in '__']
3 self.e = getPrime(int(self.bits*self.alpha))
4 print(f'{self.e.bit_length() = }')
5 φ = (p-1)*(q-1)
6 try:
7 dp = pow(self.e, -1, p-1)
8 dq = pow(self.e, -1, q-1)
9 self.n = p*q
10 break
11 except:
12 pass
The challenge is run with bits = 2048 (which means p and q are both 1024 bits). We are given the public key together with a leak of the MSB of the CRT exponents:
1dp = f'0x{(dp >> (rsa.bits//2 - rsa.known)):x}'
2dq = f'0x{(dq >> (rsa.bits//2 - rsa.known)):x}'
Solution
The solution is explained in great detail here. This attack works in general, but is even more efficient for $e \sim N^{1/12}$ (in our case is self.bits*self.alpha so roughly $N^{1/9}$; this unusual choice is already extremely suspicious). First, we write
$$ d_p = d_p^M 2^i + d_p^L $$
and the same for $d_q$. We know $d_p^M$ from the leak, and in our case $i = 512$. Section 3.1 gives us a way to compute $k$ and $l$, where $ed_p = k(p - 1) + 1$. First, we need to compute $A$:
1i = 512
2dpM = dp
3dqM = dq
4A = (pow(2, 2*i) * pow(e, 2) * dpM * dqM)//N + 1
Then, notice that in our case (with the paper notation)
$$ \delta = \frac{1}{4} < \frac{1}{2} - \frac{2}{9} \sim 0.27 $$
so we are just inside the bounds. Then we can recover $k$ and $l$ as roots of the appropriate polynomial:
1x = PolynomialRing(RationalField(), 'x').gen()
2C = (1 - A*(N-1)) % e
3f = x**2 - C*x + A
4roots = f.roots()
5if roots == []:
6 f = x**2 - (C + e)*x + A
7 roots = f.roots()
8k = roots[0][0]
9l = roots[1][0]
10assert k*l == A
Finally, given $k$, we can go to Section 3.3. Here a bit of trial and error is required, since we do not know if $k$ is actually associated to $d_p$ or $d_q$, but this is not a big effort. Notice that we do our computation modulo $kN$ (the paper mention $kp$, which may be somewhat confusing). Here applying Coppersmith method for small roots we can find a factor for $N$.
1x = PolynomialRing(Zmod(k*N), 'x', implementation='NTL').gen()
2# Assume k is the coefficient of dp
3a_small = (e * dpM * (2**i) + k - 1) * inverse_mod(e, k*N)
4a_small = int(a_small)
5f = x + a_small
6my_dpL = f.small_roots(X=2**i-1, beta=0.5)
7
8# Is actually with dq
9if my_dpL == []:
10 a_small = (e * dqM * (2**i) + k - 1) * inverse_mod(e, k*N)
11 a_small = int(a_small)
12 f = x + a_small
13 my_dqL = f.small_roots(X=2**i-1, beta=0.5)[0]
14 p = gcd(f.subs(x=my_dqL), N)
15 print(f'{p = }')
16
17else:
18 my_dpL = my_dpL[0]
19 print(my_dpL == dpL)
20 print(f'{p = }')
Finally, with the factorization we can decrypt the flag: HTB{f4ct0r1ng_w1th_just_4_f3w_b1ts_0f_th3_CRT_3xp0n3nts!https://eprint.iacr.org/2022/271.pdf}. With no surprise, it points again at the paper we’ve been using through all the challenge!
Solve Script
The full solution script can be found here