もう日が経ってしまったけど、HITCON CTF 2022のcrypto問題のwriteupです。難しい問題は解けなかったけど簡単な問題も楽しかったです。あらゆるところで言ってるけど、mapleとlyxがめちゃめちゃ信用できる。
Baby SSS
from random import SystemRandom
from Crypto.Cipher import AES
from hashlib import sha256
from secret import flag
rand = SystemRandom()
def polyeval(poly, x):
return sum([a * x**i for i, a in enumerate(poly)])
DEGREE = 128
SHARES_FOR_YOU = 8
poly = [rand.getrandbits(64) for _ in range(DEGREE + 1)]
shares = []
for _ in range(SHARES_FOR_YOU):
x = rand.getrandbits(16)
y = polyeval(poly, x)
shares.append((x, y))
print(shares)
secret = polyeval(poly, 0x48763)
key = sha256(str(secret).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_CTR)
print(cipher.encrypt(flag))
print(cipher.nonce)
とりあえずひと目見てわかることを整理します。
- 一見Shamir's Secret Sharing
- 多項式を復元して
を代入した値が得られればOK
- 128次の多項式なのに対して、8個しかシェアが与えられていないので、通常は解けなさそう
とっていないのが怪しい
とりあえず一式から多項式全部を復元できないかを考えますが、多項式の係数は64bitであるのに対して、各シェアの
は16bitなので、たとえばもらっている
に対して
とかをとっても、0次の係数に関しては1/4しか復元できなさそうです。
しかし今回は8個のシェアが与えられているので、それぞれのシェアで
を取ると、係数の定数項を中国剰余で復元できそうです。定数項（仮に
とします）がわかれば、
なので 
となり、次々に係数が求まります。
実装するとこう
import ast
from hashlib import sha256
from Crypto.Cipher import AES
with open("output.txt") as f:
shares = ast.literal_eval(f.readline())
ciphertext = ast.literal_eval(f.readline())
nonce = ast.literal_eval(f.readline())
def polyeval(poly, x):
return sum([a * x**i for i, a in enumerate(poly)])
DEGREE = 128
SHARES_FOR_YOU = 8
coeffs = []
for d in range(DEGREE + 1):
pairs = []
values = []
mods = []
for i in range(len(shares)):
x, y = shares[i]
s = y - polyeval(coeffs, x)
values.append(s // x**d)
mods.append(x)
c = CRT(values, mods)
coeffs.append(c)
secret = polyeval(coeffs, int(0x48763))
key = sha256(str(secret).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_CTR, nonce=nonce)
print(cipher.decrypt(ciphertext))
ptrlibのCRTメソッドは各
が厳密に互いに素であることを要求してきたので今回はSagemathを使いました。そのうち治したい。
Secret
問題はこう
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)
唯一の
のもとで、64個の
を用いて
という暗号化をしているRSAです。一見Common Moudulus Attack典型のような形をしていますが、が不明なので、まずを求める必要がありそうです。
これについては最近N1CTF 2022で出題されたBrand new checkinという問題で似たような要求があったことを思い出し、出題者であるmapleさんのwriteupを見に行ったところ、さらに過去にmapleさんが出題した問題の解説がありました。
github.com
これによれば、以下のような理屈で
と
の複数の組からが求まります。
複数の数の組
を仮定して、
となるとき、
なので、
となり、このようなと同様の
を用意して、
となることが期待できます*1。
さて、
からそのようなを求めるのはLLLの得意とするところで、
という行列のLLLでそのような係数が複数求まります*2。
今回は少し発展して
の場合について考える必要があるので一筋縄ではいかない、というかこれをLLLで解くのは無理じゃないか……？ と思っていましたが、なんか実験していたら適当なスケーリングでなんとかなりました……。なんで……？ LLLのこと何もわかりません*3。
下のプログラムでが求まります。あとはCommon Modulus Attackをやるだけなので省略。ptrlibでできます。
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)))
L = M.LLL()
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()
r = gcd(S.numerator() - S.denominator(), T.numerator() - T.denominator())
print(r)
Superprime
from Crypto.Util.number import getPrime, isPrime, bytes_to_long
def getSuperPrime(nbits):
while True:
p = getPrime(nbits)
pp = bytes_to_long(str(p).encode())
if isPrime(pp):
return p, pp
p1, q1 = getSuperPrime(512)
p2, q2 = getSuperPrime(512)
p3, q3 = getSuperPrime(512)
p4, q4 = getSuperPrime(512)
p5, q5 = getSuperPrime(512)
n1 = p1 * q1
n2 = p2 * p3
n3 = q2 * q3
n4 = p4 * q5
n5 = p5 * q4
e = 65537
c = bytes_to_long(open("flag.txt", "rb").read().strip())
for n in sorted([n1, n2, n3, n4, n5]):
c = pow(c, e, n)
print(f"{n1 = }")
print(f"{n2 = }")
print(f"{n3 = }")
print(f"{n4 = }")
print(f"{n5 = }")
print(f"{e = }")
print(f"{c = }")
5重のRSAですが素数の生成が特殊で、素数
と対になる
は「の文字列をバイト列だと思って解釈し直したときの数値」です。つまり、が
なら
です。これらの
が様々に組み合わされて
ができています。
結論から言えば、これらの合成数はその成り立ちが特異なので全てDFSやBFSで枝刈りをしながら素数の候補を狭めていく方法で素因数分解できますが、今回はケースによって少しずつ違う解き方をしたのでそれらを紹介します。勘が良ければ一気呵成に全部を素因数分解する方法も思いつけるのかも。
まず第一に
は、以前SECCON 2020 Qualsで出題されたThis is RSAという問題と同じネタなので、この方法で解けます。素因数のどちらも
という形になっているので4bitを全探索しながら、上位の
と合わせつつ、
の下位bitの探索結果の積と素因数分解の対象のの下位bitとが一致するかを確認します。
こういう感じ
def dfs(N, p, q, depth):
for x in range(10):
for y in range(10):
if depth == 0 and y < x:
continue
ps = str(x).encode().hex() + p
qs = str(y).encode().hex() + q
pp = int(ps, 16)
qq = int(qs, 16)
if (pp*qq) % (2**((depth+1) * 8)) == N % (2**((depth + 1) * 8)):
if N % pp == 0:
return [pp, N // pp]
r = dfs(N, ps, qs, depth + 1)
if r is not None:
return r
q2, q3 = dfs(n3, "", "", 0)
assert n3 == q2 * q3
続いて
は
と
の間に関連性があるので、のある桁を決めると自動的に対応するの桁が決まります。これを使って、今度は上位から探索する方法をとります。だいたいと同じ大きさの
を用意すれば
で、上位の桁は一致することが期待できるので、の上位を決めながら
の結果の上位の桁がと一致しているかを確認しました。
こう
def dfs2(N, s, l):
if l == 0 and N % int(s, 16) == 0:
return int(s, 16), N // int(s, 16)
for x in range(10):
prefix = s + str(x).encode().hex()
d = bytes.fromhex(prefix).decode()
q_ = int(prefix + "0" * (l-2), 16)
p_ = N // q_
if str(p_).startswith(d):
r = dfs2(N, prefix, l-2)
if r:
return r
L = ((n1.bit_length() - 512) + 3) // 4
p1, q1 = dfs2(n1, "", L)
assert n1 == p1 * q1
そして最後に
ですが、今度は
の素因数である
を決めると
の素因数である
が決まる、といった具合で２つの合成数にまたがった関係があります。とはいえの場合と同様にやって、と
を同時に探索しながら、対応する
がそれぞれ
と上位の桁で一致するかを確認しながら決めていけばなんとかなりました。今回は上位から決めていった関係で桁数の見積もりをミスっていると素因数分解できないため、桁数は探索してます。
def dfs3(N1, N2, s1, s2, l1, l2):
if l1 == 0:
q1 = int(s1, 16)
if N1 % q1 == 0:
return (q1, N1 // q1)
if N2 % q1 == 0:
return (q1, N2 // q1)
if l2 == 0:
q2 = int(s2, 16)
if N1 % q2 == 0:
return (q2, N1 // q2)
if N2 % q2 == 0:
return (q2, N2 // q2)
for x in range(10):
for y in range(10):
s1_ = s1 + str(x).encode().hex()
s2_ = s2 + str(y).encode().hex()
d1 = bytes.fromhex(s1).decode()
d2 = bytes.fromhex(s2).decode()
q1_ = int(s1_ + "0" * (l1-2), 16)
q2_ = int(s2_ + "0" * (l2-2), 16)
p1_ = N1 // q2_
p2_ = N2 // q1_
if str(p1_).startswith(d1) and str(p2_).startswith(d2):
r = dfs3(N1, N2, s1_, s2_, l1-2, l2-2)
if r:
return r
found = False
for d1 in range(0, 5, 2):
for d2 in range(0, 5, 2):
r = dfs3(n4, n5, "", "", L + d1, L+d2)
if r:
q4, p5 = r
p4 = int(bytes.fromhex(hex(q4)[2:]))
q5 = n4 // p4
found = True
break
if found:
break
assert n4 == p4 * q5
assert n5 == p5 * q4
素因数分解できたらあとはRSAを復号しておわりです。This is RSAを見たときにはやを思いつかなかったのが悔しいですね*4。
