poka2019 writeup 1 - Lenstra-Lenstra-Lovász

I am not good at Linear Algebra : ( Can you tell me about Lenstra-Lenstra-Lovász lattice basis reduction algorithm? Add) e=151. This is for make challenge easy.

enc.txt

Lenstra-Lenstra-Lovász.sage

Notations

Before start, let’s make the notations clear.

• n : RSA modulus

  p,q : two distinct prime factor of n.

• e : RSA encryption exponent d : RSA decryption exponent

• dp = d % (p-1)

• bits : bit length of dp

• shiftbits = bits//2 - bits//10

• ct : ciphertext

• s,x : dp = s << shiftbits + x. i.e., shiftbits-length leaked dp is s and the remainder part is x.

Given values are n,e,ct,s. Of course, the objective is getting the plaintext of the RSA encryption.

Modular Arithmetics

Since $ed \equiv 1 \mod ((p-1)(q-1))$,

$ed_p \equiv 1 \mod (p-1).$

Let $ed_p = 1 + (p-1)k$. Then

$e(s \ll \texttt{shiftbits} + x ) = 1 + (p-1)k$

Range For bit and shiftbits

We have bit-length of secret which is approximately 6/10 bit-length of dp, which was 614. Therefore bits is either 1023 or 1024.

for bits in range (1010,1030):
	print(bits, bits - (bits//2 - bits//10))

...
1018 610
1019 611
1020 612
1021 613
1022 613
1023 614 (*)
1024 614 (*)
1025 615
1026 615
1027 616
1028 616
...

Also note that $ed_p = k (p-1)+1$ and d_p < p-1 $, so $k\le e=151. So bound of k and bit-length of dp is reasonable.

Polynomial Modulo p

We now have appropriate range for shiftbits and k to solve

$e(s \ll \texttt{shiftbits} + x ) -1 + k \equiv 0 \mod p$

I used small_roots in SageMath to use Coppersmith’s Method to solve above this.

$s \ll \texttt{shiftbits} + x + (k-1) e^{-1} \equiv 0 \mod N$

Where $e^{-1}$ is modular inverse of $e$ respect to $N$.

def coppersmith(shiftbits, k):
    F.<x> = PolynomialRing(Zmod(n))
    invE = inverse_mod(e, n)
    f = (s << shiftbits) + x + (k - 1) * invE   # make monic
    x0 = f.small_roots(X=2 ** shiftbits, beta=0.44, epsilon=1/32)
    return x0

Therefore I get dp and also p using $p = \frac {e d_p -1} k +1$. By processing a simple RSA decryption, flag is:

POKA{You_4r3_Crypt0_N00000B_XDD}

solve.sage is the full code.