[HITCON 2022] - SuperPrime

마찬가지로 거두절미하고 바로 코드로 들어가보자. 이 문제는 스스로..는 못 풀고 친구에게 조금의 힌트를 받고 푼 문제이다. 앞으로 더욱 노력해야겠다고 생각한 계기...

🖲️ Code Analysis

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 = }")

이 코드도 암호화 알고리즘 자체는 비교적 간단하다.

 

먼저, getSuperPrime 함수는 한번에 소수 2개를 구하는 것이다.

 

첫번째로 512 비트 짜리 소수를 구하고, 이 소수를 10진수 형태로 string, bytes 으로 만듬으로써 다시 int 로 변환해주게 된다. 예를 들어서 ‘113’ 이라는 소수를 구했다면, 이를 bytes 으로 바꾸어서 b’\x31\x31\x33’ 으로 변환해준 뒤에, int 로 바꿔주게 된다. (0x313133 이 되는데, 신기한 소수 생성이네,,)

 

따라서 이렇게 구한 int 도 소수라면, 두 소수를 출력해주게 되고, 이렇게 구한 n1 ~ n5 들을 이용해서 각각의 n 들로 flag 를 암호화해주게 된다. (누가봐도 인수분해 문제)

💡 Main Idea

이 문제의 핵심은 당연하게도 각각의 n1 ~ n5들을 이용해서 p1 ~ p5, q1 ~ q5 들을 다시 구해내는 것이다. n 들을 소인수분해 하게 되면, 손쉽게 rsa 복호화를 통해서 문제를 해결할 수 있다.

 

코드를 보면 눈치챘겠지만, 단순하게 n 들이 곱해져 있지 않다.

n1 = p1 * q1
n2 = p2 * p3
n3 = q2 * q3
n4 = p4 * q5
n5 = p5 * q4

이렇게 교차되어 곱해지는 경우도 있기 때문에 문제를 풀기 위해서는 크게 3가지 틀로 나누어 보아야 한다. n1, (n2, n3),  (n4, n5) 총 3가지로 나누어 문제를 살펴보도록 하자.

 

Factoring n1 

n1 에서는 기본적인 이분 탐색을 이용해서 n1을 소인수분해 할 수 있다.

 

중요한 것은 p 가 증가한다면 bytes_to_long(p) 또한 증가한다는 것이다. 각각의 숫자 ( 0 ~ 9 ) 들은 \x3? 에 대응되는데, 숫자가 높아질수록 hex 값도 높아지게 된다.

 

따라서 각각의 숫자가 커짐에 따라서 bytes 로 바꿔 int 로 바꾼 소수의 값 또한 커지게 된다. 따라서 이를 이분탐색으로 구할 수 있을 것이다.

 

Factoring n2 & n3

n2, n3 는 GoN 대회에서 출제한 pprintable 이라는 문제와 유사하게 해결할 수 있다.

 

두 소수의 곱, 그리고 두 소수를 각각 hex int 로 바꾼 값들의 곱을 알고 있다면, 0 부터 차례대로 일의자리수부터 각각 p 값들을 유추해낼 수 있을 것이다.

 

Factoring n4 & n5

이 부분은 사실 문제를 풀었음에도 불구하고 100% 되는 방식이라고 확신할 수 없다..

 

일단 설명해보자면, p4 를 임의로 정하고, p4 를 통해서 p5, q4, q5 를 모두 구해낼 수 있다. 그 후에, p5, q5 사이에 관계를 이용해서 p4 를 계속 이동시켜주면 된다.

 

p5 를 hex int 로 변환한게 q5 이기 때문에 이 두 값의 대소를 비교해주면 된다. (이분탐색은 아니고,, 그냥 차례대로 더해가면서 값 비교해주는 느낌..?? 코드 보면 이해할 수 있을 것..ㅎㅎ)

 

📖 Exploit Code

코드가 상당히 길어서 나누어서 보도록 하자. 먼저 data 정의 부분이다. 

n1 = 132240475872174910020944408159013384770525986234801028624784519134365862704105251340824787510945183963356820885920367304711310957365047441178683686926111455575911962257698539064559510444855775549001648292058855493337857073693460061212792795075263084221929517773754699732129582794061997056827998985829666251060653380798686353779510948629280009197715644814616657550158740378670095210797455828266323922570838468050733341304227070902756780052159113811360169205531739117518635829837403006788948761106892086004133969899267757339921
n2 = 95063555614573541810575593850289506856925979977609991181205616159125089261546784721154599484613262518469706157215924537125160406418217535531993036958388330505871763176297570429533467696205928686731756713059807727405313286020007347211892135226632724359291407913539632339885950358476265995466145680878334722001
n3 = 59077122528757446350604269162079270359932342538938986760275099248290981958441838384256597839386787448447136083450980256330743221155636885358548541847176342745397373638152767362253944731433134474562146358334422503033973244936835557423934491676324297243326613498319086748647812745223753746779568080090592100960499863677438403657325762852705171109382084916335379889394829715777901290096314487661584614712488781379507151355301063123233880909931925363322846957197537676660047824476129446066149857051131731840540157488590899311381370266592295206055792990886734933291304077440476730373491475852882163732120626849448728573574411786320772125534383707413572678316508826450778346723441956945169297689138799298561759843280317867927205551400065163199599457
n4 = 24589423756497058585126900932611669798817346035509889383925628660158156567930038333401661451846451875869437263666365776498658699865323180836374906288949824205543130261556051807217164348291174483234810669420041361857307271050079366739157441129916338485838528114129985080841445467007786565727910355311119650431197742495274527401569906785121880408809802492383216836691265423297722021017515667257863302820657924121913047547741420413553737917632809270380269758313556777803344394624408862183672919570479289614998783678080936272369083
n5 = 185885020243714550225131939334004568560534422416697599024696590344782893162219788079305752632863387855011040772104676488940707663157284194641170875157382507202789029285286466326803699701161968587945867047101502048926016515139728368809523009828247173096909917611001113266938209226483162533302629909322412013492978440863258135181226831155024690292336026753678424906151360739424148666951389956182136072508650529271179749569637083537783283360860102371562796635391549934474381821125255176073752645643893294533330184238070085333427
e = 65537
c = 44836759088389215801662306050375432910426695023654894661152471598197009644316944364461563733708795401026569460109604554622161444073404474265330567406370705019579756826106816505952084633979876247266812002057927154389274998399825703196810049647324831928277737068842860115202258059693760003397831075633707611377854322143735834890385706873765241863615950449707047454133596389612468366465634011925228326638487664313491916754929381088396403448356901628825906815317934440495749705736715790281606858736722493438754469493049523175471903946974639097168758949520143915621139415847104585816466890751841858540120267543411140490236193353524030168152197407408753865346510476692347085048554088639428645948051171829012753631844379643600528027854258899402371612
from Crypto.Util.number import *
from gmpy2 import iroot

이제 n1 을 인수분해 해야 하는데, Main Idea 에서 말한 것처럼 이분탐색을 진행하면 된다. 이분탐색은 기본적인 알고리즘이기에 따로 부가 설명은 생략하겠다.

# Factoring N1

low = 0
high = pow(2,513)
while True:
    mid = (low + high) // 2
    res = mid * bytes_to_long(str(mid).encode())
    if res == n1:
        print(mid)
        break
    elif res > n1:
        high = mid
    elif res < n1:
        low = mid

p1 = mid
assert n1 % p1 == 0
q1 = n1 // p1

 

다음은 n1 과 n2 를 구하는 것인데, 아래 바이트부터 차례대로 브루트 포싱 해가면서 찾아내면 된다. 

일종의 dfs, 즉 깊이 우선 탐색 알고리즘으로 탐색을 진행했다. 

# Factoring N2 and N3

strint = [str(i) for i in range(10)]

def find(a,b):
    length = len(a)
    if length != 0:
        if int(a).bit_length() >= 512:
            p2 = a
            return 0
    for i in strint:
        for j in strint:
            tmp_a = i + a
            tmp_b = j + b
            if (int(tmp_b) * int(tmp_a) - n2)%pow(10,length+1) == 0 and (bytes_to_long(tmp_a.encode()) * bytes_to_long(tmp_b.encode()) - n3) % pow(16,(length)*2 +1) == 0:
                find(tmp_a, tmp_b)

print(find('',''))

p3 = n2 // p2
assert p2 * p3 == n2

q2 = bytes_to_long(str(p2).encode())
q3 = bytes_to_long(str(p3).encode())

 

마지막으로 n4 와 n5 의 인수분해이다. 이 코드는 살짝 난잡할 수도 있는데, 일단 한번 살펴보자. 

# Factoring N4 and N5

init = 6759224677971298549787012499102923063739682910296196688861780721860882015036773488400937149083451713845015929093243025426876941405973284973216824503042048
gap = 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
while True:
    if gap == 0:
        break
    ii = bytes_to_long(str(init).encode())
    res = bytes_to_long(str(n5//ii).encode()) * init - n4
    if res > 0:
        print('up')
        init = init-gap
        gap //= 10
    elif res < 0:
        print('down')
    elif res == 0:
        print(init) 
        # 여기서 계속 init 이 출력될 때, 그 값을 p4 라고 정의했다.
        # 어차피 정확한 값은 아니더라도 그 부근이 될 것은 확실하기 때문에,,
        # 물론 더 정확하게 짤 수는 있었겠지만 CTF 라는 게 뭐.. ㅎㅎ 
        break
    init += gap

p4 = 6759224678814800913204473280361658486772650199941114505283409645622497866148765146601841353932633241398607040792961131806556756943022446601137737571037341
q5 = n4//p4
p5 = int(long_to_bytes(q5).decode())
q4 = bytes_to_long(str(p4).encode())

이렇게 gap 이라는 변수를 만들어 이분 탐색처럼 진행했다. 실제로 이분 탐색을 진행하게 되면 무언가 맞지 않아서 이상하게 변하는 것을 볼 수 있는데, 왜 그런지는 수학적으로 접근해보면 알 수 있을 것 같다. ㅎㅎ

 

여튼 이렇게 N 들을 모두 소인수분해 할 수 있었고, 이제 남은 코드는 식은 죽 먹기 > <

# RSA Decryption 

assert p1 * q1 == n1
assert p2 * p3 == n2
assert q2 * q3 == n3
assert p4 * q5 == n4
assert p5 * q4 == n5
phi_1 = (p1-1)*(q1-1)
phi_2 = (p2-1)*(p3-1)
phi_3 = (q2-1)*(q3-1)
phi_4 = (p4-1)*(q5-1)
phi_5 = (p5-1)*(q4-1)
c = pow(c,inverse(e,phi_3),n3)
c = pow(c,inverse(e,phi_4),n4)
c = pow(c,inverse(e,phi_5),n5)
c = pow(c,inverse(e,phi_1),n1)
c = pow(c,inverse(e,phi_2),n2)

print(long_to_bytes(c).decode())

결국 인수분해가 관건이였던 문제 ㅠ

 

 

Flag : hitcon{using_different_combinations_of_primes_still_doesn't_make_this_bad_prime_generation_method_any_safer...}