2023年紅明谷CTF「It Takes Two！」問題の解法

競技中の問題

本問題は行列演算と暗号理論を組み合わせたクリプトグラフィ challenge です。競技中、行列除算の方向を間違えてしまい、時間切れとなりました。

問題のコード:

#task
from sage.all import *
from Crypto.Util.number import *
from os import urandom
from secret import flag

n = 16
bound = 2^15

A = [ZZ.random_element(-bound, bound) for _ in range(n*n)]
A = Matrix(ZZ, n, n, A)
        
B = [ZZ.random_element(-bound, bound) for _ in range(n*n)]
B = Matrix(ZZ, n, n, B)

res = []
for i in range(5):
    bound = 2^15
    S = [ZZ.random_element(-bound, bound) for _ in range(n*n)]
    S = Matrix(ZZ, n, n, S)
    
    tmp = []
    for i in range(0, 60):
        S = S* A + B
        bound = 2^(int(S[0, 0]).bit_length())
        if i % 3 == 2:
            tmp.append(Matrix(ZZ,n,n,[ZZ.random_element(-bound, bound) for _ in range(n*n)]))
            continue
        tmp.append(S)
    res.append(tmp)
    
e = A.LLL().determinant()

p = getPrime(512)
q = getPrime(512)
n = p * q
m = bytes_to_long(urandom(int(n).bit_length() // 8 - len(flag) - 1) + flag)
c = pow(m, e, n)
h1 = pow(p+q, e, n)
h2 = pow(p-q, e, n)

f = open('output.txt', 'w')
f.writelines(str(res)+'\n')
f.writelines(str(n)+'\n')
f.writelines(str(c)+'\n')
f.writelines(str(h1)+'\n')
f.writelines(str(h2)+'\n')
f.close()

データの読み取り:

出力ファイル 'output.txt' のコンマを改行文字に置換し、以下のようにデータを読み込みます:

f = open('output.txt', 'r')
res = []
for a in range(300):
    tmp = []
    for aa in range(16):
        line = f.readline().replace('[', '').replace(']', '')
        line = [int(i) for i in line.split()]
        tmp.append(line)
    res.append(tmp)
f.close()

問題分析:

コードを分析すると、3番目の行列セットがランダムな値に置き換えられていることがわかります。そのため、1, 2, 4, 5番目の行列セットを使用して行列Aを復元します。

行列の関係式は以下の通りです:

\(S_2=S_1*A+B\)

\(S_5=S_4*A+B\)

これから行列Aを計算できます:

\(A = (S_4-S_1)^{-1}*(S_5-S_2)\)

s1 = Matrix(ZZ,res[0])
s2 = Matrix(ZZ,res[1])
s4 = Matrix(ZZ,res[3])
s5 = Matrix(ZZ,res[4])
a = ((s4-s1)^(-1))*(s5-s2)
e = a.LLL().determinant()

次に素数p, qを求めます。h1, h2を変形すると:

\(h1 \equiv (p+q)^e \pmod{n}\)

\(h2\equiv (p-q)^e\pmod{n}\)

両式を加算すると:

\(h1+h2\equiv 2p^e \pmod{n}\)

\(h1-h2\equiv 2q^e \pmod{n}\)

したがって、nと(h1+h2)の最大公約数からpを、nと(h1-h2)の最大公約数からqを求めることができます。

さらに、\(gcd(e,\phi)=21\) であることがわかります。有限体での21乗根を求め、中国剰余定理を適用してフラグを復元します。

from gmpy2 import *
from Crypto.Util.number import *

n = 126930298936285661712486297662920895162569606037310367763354747221281175771655642407136326621695910623038808779778530112406355314071209370688157872928010633181351390724545013677593062556323119308457918805555312069055604237211117650220178416298165021603211366843640334616217695418858036626587483782452105122653
c = 113627841667808982839757084973426219545127121566516056267404541633803040730885409234473068650543791446730694746311695177758797711077000091232969424826171863685060090359260225102836081852105845748467870581394884564134418376982186965340367386781824886506478939204791426457255483148486730526127180397268053506840
h1 = 87021607670080656750728189202811647321664825322085967432146885995538140004901574830625347954724344331514731852873721100175299656618161173874818773415684739773055620673258848991693719847569489515642296650035465632567910004553054397894647697286044465567405142149926303968235362573821060105908856127568162452912
h2 = 70528801000055618659638315463133504198238507722722570127215098017082205934290867816695737682738831717228470799826957490782948760796844881508632060312080331264474968266753069687287034453036854258618280625776346633340081217397502423530180647548747144401922660710323623212890923488339464759360304751017490144695

# h1+h2 と n の最大公約数から p を求める
p = gcd(h1+h2, n)
q = n // p
phi = (p-1)*(q-1)
# e/21 と phi の逆元を求める
d = inverse(e//21, phi)
# 暗号文を復号
c_ = pow(c, d, n)

# 有限体で21乗根を求める
PR.<x> = PolynomialRing(Zmod(p))
f = x^21 - c_
f = f.monic()
roots_p = f.roots()

PR.<x> = PolynomialRing(Zmod(q))
f = x^21 - c_
f = f.monic()
roots_q = f.roots()

# 中国剰余定理で組み合わせ
for i in roots_p:
    for j in roots_q:
        m = CRT([int(i[0]), int(j[0])], [p, q])
        flag = long_to_bytes(m)
        if b'flag{' in flag:
            print(flag)

これにより、フラグが取得できます。