HITCON CTF 2022 | secret - crypto-writeup-public

#HITCON_CTF_2022

import random, os
from Crypto.Util.number import getPrime, bytes_to_long

p = getPrime(1024)
q = getPrime(1024)
n = p * q

flag = open('flag','rb').read()
pad_length = 256 - len(flag)
m = bytes_to_long(os.urandom(pad_length) + flag)
assert(m < n)
es = [random.randint(1, 2**512) for _ in range(64)]
cs = [pow(m, p + e, n) for e in es]
print(es)
print(cs)

RSAだが $c_i = m^{p + e_i} \mod n$ の形式になっていて、 $n$ 不明。 #nがわからないとき

$c_i = m^{e_i} \mod n$ のとき、 $e_0, e_1, \dots, e_n$ に対して、 $e_0a_0 + e_1a_1 + \dots + e_na_n \equiv 0 \mod \phi(n)$ となるような $a_0, a_1, \dots$ があれば

$\prod m^{a_ie_i} \equiv 1 \mod n$ すなわち $\prod c_i^{a_i} - 1 = kn$ となる。同じような $b_0, b_1, \dots$ も計算できれば $\prod c_i^{b_i} - 1 = ln$ なのでGCDを取れば $n$ が求まる

そしてこのような $a_0, a_1, \dots$ はLLLで計算できる

import ast

f = open("output.txt")
es = ast.literal_eval(f.readline())
cs = ast.literal_eval(f.readline())


K = 2**1024
M = matrix(QQ, len(es), len(es)+1)
M.set_block(0, 0, matrix(QQ, len(es), 1, [e + K for e in es]) * K)
M.set_block(0, 1, matrix.identity(len(es)))

print("LLL...")
t1 = cputime() 
L = M.LLL()
t2 = cputime() 
print(t2 - t1)

print("product...")
t1 = cputime()
S = product(int(c)**r for c, r in zip(cs, L[0][1:]))
T = product(int(c)**r for c, r in zip(cs, L[1][1:]))
t2 = cputime()
print(t2 - t1)

print("GCD...")
t1 = cputime()
r = gcd(S.numerator() - S.denominator(), T.numerator() - T.denominator()) 
t2 = cputime()
print(t2 - t1)

print(r)




# sum( e_i * a_i ) = 0
# product( m**(e_i * a_i) ) = 1 mod n

# v = [a_0, a_1, a_2, ...]
# M = [
#     [e_0 + K, 1],
#     [e_1 + K, 0, 1],
#     [e_2 + K, 0, 0, 1],
#     ...
# ]


# product( e_i * a_i + p * a_i ) = m**(a*p)