[SECCON CTF 2021] CCC

 

from Crypto.Util.number import bytes_to_long, getPrime, getRandomInteger, isPrime
from secret import flag


def create_prime(p_bit_len, add_bit_len, a):
    p = getPrime(p_bit_len)
    p_bit_len2 = 2*p_bit_len // 3 + add_bit_len
    while True:
        b = getRandomInteger(p_bit_len2)
        _p = a * p
        q = _p**2 + 3*_p*b + 3*b**2
        if isPrime(q):
            print('b =',b)
            print('q = ',q)
            print('_p = ',_p)
            print('p =',p)
            return p, q


def encrypt(p_bit_len, add_bit_len, a, plain_text):
    p, q = create_prime(p_bit_len, add_bit_len, a)
    n = p*q
    e = 65537

    c = pow(plain_text, e, n)
    print(f"{n=}")
    print(f"{e=}")
    print(f"{c=}")
    print(f"{a=}")


if __name__ == "__main__":
    encrypt(1024, 9, 23, bytes_to_long(flag))

 

문제를 요약하면 아래와 같다.

 

$$ \_p = 23*p$$

$$q=\_p^2b+3\_pb*3b^2$$

 

여기서 수학적인 직관 및 눈치가 조금 있다면 알아챌 수 있는 사실은 다음과 같다.

 

$$ q*\_p+b^3=(\_p+b)^3=(23p+b)^3=23*n+b^3$$

 

즉 $23n+b^3$이 세제곱수임을 알게 되었고, 이를 이용하면 b를 빠르게 복호화할 수 있다.

 

문제 상황에서 n은 1024bit, b는 691bit이므로 $(23n)^{1/3}$을 시작으로 1씩 늘려가면서 $23n$과의 차이가 세제곱수일 때를 찾으면 b를 빠르게 구해낼 수 있다.

b를 복호화하게 되면, $(23p+b)^3=23n+b^3$을 이용하면 쉽게 p를 얻을 수 있고,

이를 이용해서 RSA decryption을 진행하면 FLAG를 얻을 수 있다.

 

ans.sage

from Crypto.Util.number import *
n=748951371882130931802035658643190843137768069094997532951877004804355999097514221898028746065708192401137682993520394304990274249486640341029596290845019123501455018318510517909188939742845359945051314320563879373308724866109205523358039610245817247396545225688131777569595375742563435181638557077287922855820814595617783963660715574123873253353153278155760187284507960974463459267090974567641539244100051157552969986630824060742455310593820406102161092521387627538070667222153082596080511347819692755067747768139661729133034101802879625296211575691192743381543325874828909504875804787273331727742295091555122604114378761875904742058873698555585850827391696126140112636986993317927401429541856267367473445998581503501399623438736593768742981259154547976308900931109837309595997322935859631651669260030950617914529080413885891792411413957578026402435702642249422813870751911884533018455112305024443548612214695005687499093470313
e=65537
c=144917864074015511935922816857363231541337762967562770119947985253463317126444931330942327334877580469990487497385196884757450691512323490753332323130997570096503070353477774210372799245361349305977816855197674562476707717312608963647587926329578332695523741999417967833032897169784927673730478114998147220953244488180240589904915102081692892506680654490941335587101027728447612331673649345499892499229553504426795996533332373684883271169670391774715307364853681369400205428259656028822679426328606371637153322224619471527480606421420141488512534130932537599855407350411776431197722318883451482159889911162752057786419942877600817298455386249064465557840145113456791121193853697366914932529401387170474843621810340519604877328113389161648132892104521737590843609044323838717403840588506498097350784386251597640755764921923426609290805256930846775003488315671785785091516760625958052962992811477229394815825903218592357864607501
a=23

tmp = 23 * n
t = int(tmp ** (1/3)) +1
b = 0
print('start')
while(1):
    a = int(t ** 3 - 23 * n)
    k = int( a ** (1/3))
    if(k ** 3 == a):
        b=k
        print("Recover b :",b)
        break
    t += 1

#23*n + b^3 = (23p+b)^3
#t = 23p+b
assert (t-b) % 23 == 0
p = (t-b) // 23
q = n // p
d = inverse(e,(p-1)*(q-1))
m = int(pow(c,d,n))
print(long_to_bytes(m))
#SECCON{CCC_means_Cubic_root_and_the_CTF_I_learnt_a_lot_about_fermat's_factorization_method}

 

Uploaded by Notion2Tistory v1.1.0