SECCON CTF 2023 Quals Writeup

結構時間かけて書いたから電子の海の何処かに沈めることはできなかった.
運営に出したWriteup公開しても大丈夫だよね?

plai_n_rsa

$ed=k(p-1)(q-1)$であるが, $ed$のビット長が$2065$, $n$のビット長が$2048$であるから
$k$のビット長は高々17bitであることがわかる. よって$k$の値を$2^{18}$まで総当たりすればよい.

solve.py

from Crypto.Util.number import long_to_bytes, inverse
from output import e, d, hint, c

kphi = e * d - 1
s = kphi * hint  # k(pq(p+q)-(p+q)(p+q)+(p+q))
hint2 = hint * hint  # (p+q)^2

for k in range(1, 2**18):
    if s % k == 0:
        t = s // k + hint2 - hint  # pq(p+q)
        if t % hint == 0:
            n = t // hint
            m = pow(c, d, n)
            print(long_to_bytes(m))

RSA4.0

四元数$a+bi+cj+dk$は以下の形の行列$M_4(\mathbb{R})$と同型である.　

\begin{pmatrix}
a & b & c & d\\
-b & a & -d & c\\
-c & d & a & -b\\
-d & -c & b & a\\
\end{pmatrix}

この行列の$n$乗は

この行列で表現される四元数の$i,j,k$成分はそれぞれある定数$t$を用いて$bt,ct,dt$とあらわせる.
また

\begin{aligned}
a &= m\\
b &= 3m + p + 337q\\
c &= 3m + 13p + 37q\\
d &= 7m + 133p + 7q
\end{aligned}

より

\begin{aligned}
m &= -\frac{115b}{2132}+\frac{1067c}{2132}-\frac{181d}{3731}\\
p &= \frac{17b}{6396}-\frac{167c}{6396}+\frac{75d}{7462}\\
q&= \frac{11b}{3198}-\frac{7c}{1599}+\frac{3d}{7462}
\end{aligned}

となるので$mt,pt,qt$が求まる.

u:=(bt)^2+(ct)^2+(dt)^2=(b^2+c^2+d^2)t^2=\frac{\left(\sqrt{-b^2-c^2-d^2}\left(\left(a+\sqrt{-b^2-c^2-d^2}\right)^2-\left(a-\sqrt{-b^2-c^2-d^2}\right)^2\right)\right)^2}{4(b^2+c^2+d^2)}\\

より

\begin{aligned}
\frac{m^2}{b^2+c^2+d^2}&=\frac{(mt)^2}{u}\\
\frac{p^2}{b^2+c^2+d^2}&=\frac{(pt)^2}{u}\\
\frac{q^2}{b^2+c^2+d^2}&=\frac{(qt)^2}{u}
\end{aligned}

また

\newcommand{\a}{\frac{1}{4}\left(\left(a-\sqrt{-b^2-c^2-d^2}\right)^2+\left(a+\sqrt{-b^2-c^2-d^2}\right)^2\right)}
\begin{aligned}
c_1 &=\a\\
c_2 &=bt\\
c_3 &=ct\\
c_4 &=dt
\end{aligned}

とすると四元数のノルムの定義より

(a^2+b^2+c^2+d^2)^e=c_1^2+c_2^2+c_3^2+c_4^2

となり$a=m$であることに注意して

(b^2+c^2+d^2)^e=\frac{(a^2+b^2+c^2+d^2)^e}{\left(\frac{m^2}{b^2+c^2+d^2}+1\right)^e}

となる.
よって

m^{2e}=\left(\frac{m^2}{b^2+c^2+d^2}\right)^e(b^2+c^2+d^2)^e

同様にして$p^{2e},q^{2e}$も得られる.

\begin{aligned}
p&=\mathrm{gcd}(p^{2e},pt)\\
q &=\mathrm{gcd}(q^{2e},qt)
\end{aligned}

$p,q$が分かるの秘密鍵$d$が求まり$m^2$が得られる.
あとは$p,q$が分かっているので中国剰余定理で$m$が求められる.

solve.sage

n = 24872021325220256807454685550051664385270234794214413640899222873349265041897698942179745264628886444843936788046461273130347947293134447971213366009115689414264642605438643804813680767747014691971929645215382160557083245742340043385689944268138610186373780437485231877752933652320663858810427971106170059463601595006391073927194512124601928964813763052148657220845548046841237699017168286609835799813635564372682635612722890934578765797156432068449168053296617922489740666171866398517122799604532749283529271598232365042243492016089416298371516093933466381558297769513544950617454777689674801163035308121219081809467
e = 65537
enc = [
    3859728242860779998500245827824643011031182038976286035325209177561306523157077514772157957170475592309362631020979427907103610597898945426993614901767468098095010971836640454364234772978503167875298045774311291740824611786880849602974611016313651468361669338020331880259928969457255469579663017102640555015734482731890405522757985802082583300838209107911617815694578975817745782743203495107318667111104882994250616348383832987201616468973995462070255337923156614148218730987307161335625736122244817469974403678460213399052200814122255105544573927370423504309249212003649608881714115802854352284801298522985364992841,
    6689400988469336941290409439097720802889756496874465514203924923612416113717282667321908985103298019191113140239387801253466762593814350435047233088038044902433467651291903183405705080977679431528198024945921265445106468212962845547091599919008352051426009980329461007763212773358809391005850095961625042930422795445326743156495371981183105369799111219324695409896763869363969605501957524747716457126557615625815503861788352889135785579006785498195231741997934782780728866125488514068411960643904511224086647859058006472875473225695641287267610159704735294148907843394274092665622496223560673920367014991704447470344,
    1425535224682533054692632153056888664907065024789232886308473909082337416786879221014972907213731240332278899126018247174859147121923692024420221262194523422785798197856518206508716047860471557004098274123870337912664160290690918788335238938208868363602574049572982498078216870780634694750710402353203621500287688744360281985793220035763469368517282385600578060642616443360598043313771383051760844966304306373372936321033698037647769588864584716070117876256372995523669859957654373351077969273910814003682705611267982200795979916283790161349821926490496096284763527696746485527643315156665082531990553153495043841613,
    16939641902797542358954398454693773109828645853205801192220966778707379690160425812357360275630857752612391129705744211238057564114356027205464621658979245715243171261351328848491885377078864601014889472906967998503454246639030025900184373900964200415367983329654223213873342814827852864400395905048614694659842857369371845184915252563533413447471945691935551119149323541065035997716667873333295568018189682043599379592763126488255877418142891649422421776838694214872296853180292491137387225104189612300121323951103544193685306688963647668884425837634374966829437978854408218992213680164673972942664618735198830200420,
]
from Crypto.Util.number import isPrime, inverse, long_to_bytes
from sage.rings.finite_rings.integer_mod import square_root_mod_prime

Z = Zmod(n)
c = []
for i in range(4):
    c.append(Z(enc[i]))

bt = -Z(c[1])
ct = -Z(c[2])
dt = -Z(c[3])

mt = -Z(115) * bt / Z(2132) + Z(1067) * ct / Z(2132) - Z(181) * dt / Z(3731)
pt = Z(17) * bt / Z(6396) - Z(167) * ct / Z(6396) + Z(75) * dt / Z(7462)
qt = Z(11) * bt / Z(3198) - Z(7) * ct / Z(1599) + Z(3) * dt / Z(7462)
b2c2d2t = bt * bt + ct * ct + dt * dt
m2b2c2d2_pow_e = c[0] ^ 2 + c[1] ^ 2 + c[2] ^ 2 + c[3] ^ 2
m2divb2c2d2 = mt ^ 2 / b2c2d2t
p2divb2c2d2 = pt ^ 2 / b2c2d2t
q2divb2c2d2 = qt ^ 2 / b2c2d2t

b2c2d2_pow_e = m2b2c2d2_pow_e / ((m2divb2c2d2 + 1) ^ e)
m2_pow_e = (m2divb2c2d2 ^ e) * b2c2d2_pow_e
pt_pow_e = (p2divb2c2d2 ^ e) * b2c2d2_pow_e
qt_pow_e = (q2divb2c2d2 ^ e) * b2c2d2_pow_e
p = int(gcd(pt_pow_e, pt))
assert isPrime(p)
q = int(gcd(qt_pow_e, qt))
assert isPrime(q)
d = inverse(e, (p - 1) * (q - 1))
m2 = m2_pow_e ^ d % n
mp = square_root_mod_prime(GF(p)(m2))
mq = square_root_mod_prime(GF(q)(m2))

for i in range(2):
    for j in range(2):
        f = CRT([(1 - 2 * i) * int(mp), (1 - 2 * j) * int(mq)], [p, q])
        print(long_to_bytes(f))