N1CTF 2020 | easy RSA? - crypto-writeup-public

#n1ctf_2020

ここでは序盤の素因数分解パートだけを取り扱う。そのあとはLWEなので

from Crypto.Util.number import getRandomNBitInteger
import timeout_decorator

mark = 3**66

@timeout_decorator.timeout(1, use_signals=False, timeout_exception=TimeoutError)
def get_random_prime():
    total = 0
    for i in range(5):
        total += mark**i * getRandomNBitInteger(32)
    fac = str(factor(total)).split(" * ")
    return int(fac[-1])

while True:
    try:
        p = get_random_prime()
        break
    except TimeoutError:
        continue
while True:
    try:
        q = get_random_prime()
        break
    except TimeoutError:
        continue

N = p * q
e = 65537

with open("flag.txt", "rb") as f:
    flag = f.read().strip()

m = int(flag.hex(), 16)
c = pow(m, e, N)

print("N={}".format(N))
print("e={}".format(e))
print("c={}".format(c))

$p, q$ の生成方法が怪しいのでNを素因数分解する問題だろうと推測する。p, qがどのような値かというと、 $M = 3^{66}$ として $x_0 + x_1M + x_2M^2 + x_3M^3 + x_4M^4$ の最大の素因数。

なので下のように置く。

$ap = x_0 + x_1M + x_2M^2 + x_3M^3 + x_4M^4$

$bq = y_0 + y_1M + y_2M^2 + y_3M^3 + y_4M^4$

したがって、

$abN = x_4y_4M^8 + (x_4y_3 + x_3y_4)M^7 + \cdots + (x_1y_0 + x_0y_1)M + x_0y_0$

これを変形すると

$x_4y_4M^8 + (x_4y_3 + x_3y_4)M^7 + \cdots + (x_1y_0 + x_0y_1)M = - (x_0y_0 - ab)N$

したがって、次の等式を考えることができる

$\begin{pmatrix}x_1y_0 + x_0y_1 & \cdots & x_4y_3 + x_3y_4 & x_4y_4 & x_0y_0 - ab\end{pmatrix}\begin{pmatrix} 1 & & & & M \ & 1 & & & M^2 \ & & \ddots & & \vdots \ & & & 1 & M^8 \ & & & 0 & -N \ \end{pmatrix}\ = \begin{pmatrix}x_1y_0 + x_0y_1 & \cdots & x_4y_3 + x_3y_4 & x_4y_4 & 0 \end{pmatrix}$

したがって、係数のリスト $x_0y_0 , x_1y_0 + x_0y_1, \dots$ 　がLLLによって求まりそう。

（ちなみにこのLLLが成功するのは $x << M$ という関係になっているからで、3進数で表示するとスキマが大きく開いてることがわかる）

なぜか $x_4y_4M^8 + (x_4y_3 + x_3y_4)M^7 + \cdots + (x_1y_0 + x_0y_1)M + x_0y_0$ はきれいに

$x_0 + x_1M + x_2M^2 + x_3M^3 + x_4M^4$ と

$y_0 + y_1M + y_2M^2 + y_3M^3 + y_4M^4$ に因数分解できるので、 $gcd(N, ap) = p$ が求まる

f = open("output.txt").read().strip().split("\n")
N = int(f[0].split("=")[1])
e = int(f[1].split("=")[1])
c = int(f[2].split("=")[1])

M = 3**66

B = matrix(ZZ, 9, 9)
B.set_block(0, 0, matrix.identity(8))
B.set_block(0, 8, matrix(ZZ, 8, 1, [M ** (8 - i) for i in range(8)]))
B[8,8] = -N

L = B.LLL()
PR.<m> = PolynomialRing(ZZ)
f = sum(m^i * abs(xy) for i, xy in enumerate(L[0][::-1]))
f1, f2 = [ fk**e for fk, e in f.factor() ]

p = gcd(f1(M), N)
q = gcd(f2(M), N)

phi = (p-1)*(q-1)
d = inverse_mod(e, phi)

m = pow(c, d, N)
print(bytes.fromhex(hex(m)[2:]))

なぜか はきれいに

なぜか $x_4y_4M^8 + (x_4y_3 + x_3y_4)M^7 + \cdots + (x_1y_0 + x_0y_1)M + x_0y_0$ はきれいに