問題概要
picoCTF 2022の最難関Crypto問題である。
この問題では、以下の式からflagを求める必要がある。
$$ c = 3^{flag} \mod n $$
一般に、この問題は離散対数問題と呼ばれる。
解法
参考にした論文
ここでヒントを見てみよう。
Look for Mr. Wong's whitepaper... His work has helped so many cats!
この情報をもとに検索をしてみると、以下の論文を発見した。
https://eprint.iacr.org/2016/644.pdf
この論文をヒントに、この問題を解いてみよう。
小問題への分解
先の論文に、以下の図があった。
出典: https://eprint.iacr.org/2016/644.pdf (2022/4/2アクセス)
この図は
$$ g^x \mod n $$
からxを求めるという大きな問題を、
$$ g^x \mod p $$
$$ g^x \mod q $$
からxを求める問題へと分解し、中国剰余定理(Chinese Reminder Theorem)で元の問題の答えを導くことを示している。
また、上記の問題も、以下の小問題に分割できる。
出典: https://eprint.iacr.org/2016/644.pdf (2022/4/2アクセス)
要するに、pを法とした問題は、p-1の素因数を法とする小問題に分割できるということだ。
すなわち、次の目標はp-1、q-1をそれぞれ素因数分解することである。
p-1、q-1の素因数分解
では、巨大な数であるp-1、q-1をどのような方法で素因数分解すればよいのだろうか。
実は、以下のアルゴリズムで素因数分解が可能である。
出典: https://montoguequiz.com/electrical/rsa-public-key-pollard-algorithm/ (2022/4/2アクセス)
上記のアルゴリズムを実装した関数が以下である。
def find(n):
alpha = 2
beta = 2
while True:
alpha = pow(alpha, beta, n)
d = gmpy2.gcd(alpha - 1, n)
if 1 < d and d < n:
print(f"{d}, ", end="")
n //= d
if d == 1:
return
else:
find(n)
else:
beta += 1
この関数から得られたp-1、q-1の素因数をもとに、p-1、q-1を素因数分解した。
その結果を以下に示す。
p_factor_lst = [2, 33479, 35027, 35677, 35729, 35869, 35963, 37423, 37529, 37607, 38231, 38699, 40099, 40351, 41257, 41947, 42859, 43271, 43793, 44449, 44483, 45281, 45491, 46861, 47207, 47543, 48221, 48563, 50227, 50273, 50503, 50891, 50969, 52081, 53623, 53657, 54917, 55147, 56003, 56131, 56957, 56989, 57329, 58679, 59263, 60013, 60127, 60703, 63067, 63719, 63949, 64849, 65029, 457311223, 690080687, 1753837567, 1934186953, 2264412959, 2800733603, 3331168403]
q_factor_lst = [2, 25763, 27539, 68071, 68437, 69239, 69809, 71411, 71777, 74923, 75079, 77417, 78779, 79357, 83417, 83497, 83639, 85889, 86491, 86711, 87583, 88681, 88883, 89561, 89653, 89809, 95257, 95819, 98179, 99149, 103991, 104369, 104459, 105727, 106087, 106823, 109321, 109819, 110431, 110681, 111187, 111301, 112397, 114041, 118033, 120503, 120689, 122399, 123701, 124513, 127691, 6496959103, 7564474987, 9206469053, 11978812487, 12402637831, 15850128317]
小問題を解き、元の問題の答えを出す
さて、それぞれの素因数に対し、
$$ g^x \mod (素因数) $$
からxを求める小問題を解き、元の問題の答えを求めよう。
まず、p-1、q-1に対して以下のスクリプトを実行した。
なお、以下のスクリプトは自分で書いたものではなく、他人が書いたものをpython3用に改変したものである。
from functools import reduce
def egcd(m, n):
if n>0:
y,x,d = egcd(n, m%n)
return x, y-m//n*x, d
else:
return 1, 0, m
def modinv(a, m):
(inv, q, gcd_val) = egcd(a, m)
return inv % m
def chinese_remainder(Q, X):
P = reduce(lambda x,y: x*y, Q)
result = 0
for i in range(len(X)):
x, y, d = egcd(Q[i], P//Q[i])
result += y*(P//Q[i])*X[i]
return result % P
# Baby-step giant-step
def baby_step_giant_step(g, y, p, q):
m = int(q**0.5 + 1)
# Baby-step
baby = {}
b = 1
for j in range(m):
baby[b] = j
b = (b * g) % p
# Giant-step
gm = pow(modinv(g, p), m, p)
giant = y
for i in range(m):
if giant in baby:
x = i*m + baby[giant]
print("Found:", x)
return x
else:
giant = (giant * gm) % p
print("not found")
return -1
# Pohlig-Hellman algorithm
def pohlig_hellman(p, g, y, phi):
Q = phi
print("[+] Q:", Q)
X = []
for q in Q:
x = baby_step_giant_step(pow(g,(p-1)//q,p), pow(y,(p-1)//q,p), p, q)
X.append(x)
print("[+] X:", X)
x = chinese_remainder(Q, X)
return x
x_p = pohlig_hellman(p, g, c, p_factor_lst)
x_q = pohlig_hellman(q, g, c, q_factor_lst)
出典: https://sonickun.hatenablog.com/entry/2016/11/20/192743 (2022/4/2)
x_p、x_qにはそれぞれ
$$ g^x \mod p $$
$$ g^x \mod q $$
に対しての答えが入っている。
あとは、この二つの答えを中国剰余定理で統合すればよい。
from Crypto.Util.number import *
long_to_bytes(chinese_remainder([p, q], [x_p, x_q])).decode()
これにより、flagを求められた。
使用ライブラリ
- jupyter notebook
- gmpy2
- pycryptodome