[SECCON CTF 2021] pppp

 

from Crypto.Util.number import *
from flag import flag

p = getStrongPrime(512)
q = getStrongPrime(512)
n = p*q

mid = len(flag) // 2

e = 65537

m1 = int.from_bytes(flag[:mid], byteorder='big')
m2 = int.from_bytes(flag[mid:], byteorder='big')

assert m1 < 2**256
assert m2 < 2**256

m = [[p,p,p,p], [0,m1,m1,m1], [0,0,m2,m2],[0,0,0,1]]

# add padding
for i in range(4):
    for j in range(4):
        m[i][j] *= getPrime(768)

m = matrix(Zmod(p*q), m)

c = m^e

print("n =", n)
print("e =", e)
print("c =", list(c))]

 

문제를 보면 아래와 같은 행렬을 암호화하는 작업을 진행한다.

$$ \begin{matrix} p & p & p & p \\ 0 & m1 & m1 & m1 \\ 0 & 0 & m2 & m2 \\ 0 & 0 & 0 & 1 \end{matrix} $$

 

해당 행렬의 각 항에 임의 768bit Prime을 곱하고, Zmod(N) Ring 내에서 RSA처럼 e번 곱한다.

여기서 생각해야할 것은, 해당 행렬이 삼각행렬(triangular matrix)라는 것이다. 삼각행렬을 e번 곱하게 되면,  $m_{0,0}$ 값이 아래와 같이 변환된다.

$$ p * prime_{0,0} \rightarrow (p*prime_{0,0})^e $$

 

이는 $m_{0,0}$뿐만 아니라 $m_{n,n}$, 즉 대각선에 존재하는 값들을 모두 이와 같이 변환된다.

 

해당 연산은 Zmod(N) 위에서 일어나는 일이기 때문에 $m_{0,0}$이 변환된 $c_{0,0}$​또한 p의 배수임을 알 수 있다.

즉, $GCD(c_{0,0}, N) = p$라는 결과를 얻을 수 있을 것이다.

 

from Crypto.Util.number import *

n = 139167515668183984855584233262421636549219808362436809125322963984953234794207403032462532211718407628015534917936237180092470832870352873174416729863982860547330562153111496168661222608038945799305565324740297535609102402946273092600303759078983973524662838350143815732516927299895302494977521033451618509313
m_00 = 92641859227150025014514674882433433169736939888930400782213731523244191029744271714915087397818608658221982921496921528927873080896272971564627162670330785041427348269531449548757383647994986600796703130771466176972483905051546758332111818555173685323233367295631863710855125823503925281765070200264928761744

print(GCD(n,m_00))
#output : 12260270527500005140354303469557914031320743052940580181442343366352651136803519476311929752190095903543237842653732512701302765305896233466661576939731877

 

위의 과정을 통해 p, q를 얻어냈으니, RSA decryption 과정과 동일하게 private key d를 이용하여 평문 m을 복호화하는 것이 가능하다.

 

m을 복호화하였다면, 2번째 행과 3번째 행의 값들이 각각 m1 * prime , m2 * prime 꼴이기 때문에 GCD를 이용하여 손쉽게 m1, m2를 얻어낼 수 있다.

ans.sage

from Crypto.Util.number import *
n = 139167515668183984855584233262421636549219808362436809125322963984953234794207403032462532211718407628015534917936237180092470832870352873174416729863982860547330562153111496168661222608038945799305565324740297535609102402946273092600303759078983973524662838350143815732516927299895302494977521033451618509313
e = 65537
c = [(92641859227150025014514674882433433169736939888930400782213731523244191029744271714915087397818608658221982921496921528927873080896272971564627162670330785041427348269531449548757383647994986600796703130771466176972483905051546758332111818555173685323233367295631863710855125823503925281765070200264928761744, 1077078501560459546238096407664459657660011596619515007448272718633593622581663318232822694070053575817000584000976732545349394411037957356817674297166036371321332907845398174111343765006738074197964396832305908342965034091516961317164203682771449331094865994143953470394418754170915147984703343671839620070, 19878161032897109459692857500488708331148676837923170075630073845924376353394086221031683671854185288619608305138965881628353471119235227157715699650190844508727073649527735233175347600167954253143204293274253676829607434380971492999430389536409563073620686264607716424139208756197843637115228155976163983619, 122958657434560838063916316490126514822437273152981380647634868499620566657448363565613345650206126542999322277498960954804580159527199119604554047697342524367459283765958189416627623253226055220105627822118413649499651442079969872322463271891353808314530249098525814619479135297014148780695960117897387220659), (0, 85635304452753185796593135650704585992713419302092444931829191186284566226617686976975731459756968679710078670232999566062343743901469759277582454092882685887985731708244015567469990157564460035983017331880588783841581502687752495254387549274422591338211161917565559735193456411356422539814020979699927207024, 26528377397409932803048052918715873209845190225305139460936852681030879561522825277119360099719008486268731610926098705442795761739644784858085976938906030639986454157616558457541083641717564142619063815917161350343604401278251069255966146207538326575595944701499010180658631016268689550402326369924649514049, 17173480018007185616783556851363148729840100207266610547324632027095687866456613104465211034834604995290825437734467654701021261504226847008483339028335703977866796341754911432666568936460974103742649586111260163432789617417125379644939110280618415377202845096157056174169392363954229816964869557167190373166), (0, 0, 81417110160690915414859599923077760437964436481940074249510026432592954854440295980578313776441414052192070135409849396229653279814546498083873720679422968334818254076803899882280264290639872486915551889441082468560654475422089052988909565455596584407805229280743723696618903551087160338683566908533474596220, 88524270641123978066493517684012199807956329430551155649688209766850898125045959831704501988313531767120589113923546449704920649814085765896894870692227804052901254644766662594723181025793077392532746071480212649880063471693730914835259139038459097504431147211622052068997412540488201406879310193174863792764), (0, 0, 0, 130146806238985078905344376697263038970354607413027156915068014483770022716717215156189413217688976902906182579031431264733207976605553885314360422441780388319618199732296392330859801016851191010568169307878720202422104375360360029207688301496478751250969744747470242179561459045172707909287093959859681318497)]

C = matrix(Zmod(n), c)
p = int(GCD(n,int(C[0,0])))
q = n / p
assert p*q == n

e = 0x10001
phi = (p-1) * (q-1)
d = inverse(e,int(phi))
M = C ^ d
m1 = (long_to_bytes(GCD(int(M[1,1]),int(M[1,2]))))
m2 = (long_to_bytes(GCD(int(M[2,2]),int(M[2,3]))))
print(m1 + m2)
#FLAG : SECCON{C4n_y0u_prove_why_decryptable?}