HSOC 교내 해킹방어대회 100점 문제 writeup

번역 오류 - RSA

RSA의 두 소수인 p,q를 sexy prime으로 정하여 암호화를 진행했다.
Python 코드를 보고 sexy prime을 이용했다는 사실을 알아내면 쉽게 풀 수 있다.

시나리오
한세가 해외에 있는 친구에게 CTF 문제를 받았다.
영어를 잘 못하는 한세는 번역기를 이용하여 지문을 한글로 번역했는데 '섹시한 전성기' 라는 좀 특이한 말이 나왔다.
한세: 번역 오류인가…?

#암호화 과정에 사용되는 코드의 일부분이다.

from Crypto.Util.number import *

def ????????????(n=512):

    while True:
        p = getPrime(n)
        if isPrime(p+6):
            return p, p+6

n = 110067413853034446062166180561085174675399800582469231501542989197861609958093709113059409812123926927649400547645425688314111465956694491992808266505385887197537236890045002512110096093657023204771106498999090554885456993590436056036537949671172783152946638256190164744404184125578953567094329952157689357147
e = 4294967297
c = 6430247517459839550819948528043546662220213283222011078853709086595801980582952628540465603132800123118448644982850090295098382544235129216039103121116669154107985284621853508059922122931259093211612076479073223996615242648597460278767826566208475843728873065225999150624847387541305731206359041053619452936

위와 같이 python 코드와 n, e, c 값이 있는 txt 파일을 주었다.
우선 python 코드 파일을 보면 전에 봤던 50점짜리 RSA 문제와는 p, q 값이 다르게 주어졌다는 것을 알 수 있다.
좀 더 자세히 코드를 보면 p, q가 6씩 차이나는 소수라는 것을 알 수 있는데 이처럼 두 수 간의 차이가 6인 소수 쌍을 sexy prime이라고 한다.
sexy prime:
https://ko.wikipedia.org/wiki/%EC%84%B9%EC%8B%9C_%EC%86%8C%EC%88%98
따라서 우리는 문제 python 코드를 통해 p, q가 sexy prime이라는 것을 알 수 있다. 이 방법 말고도 시나리오에 나와있는 '섹시한 전성기'라는 말을 번역하면 sexy prime이 되는데 '섹시한 전성기'라는 단어에 집중해보면 sexy prime을 유추해낼 수 있다.

이 방법의 경우 만약 이 문제를 풀기 전에 RSA 문제를 풀어봤다면 N이 소수인 p, q로 이루어져있다는 것을 알고있을 것이다.
그럼 이 문제에서 sexy prime을 과연 어디에 적용했을지에 대해 생각해보면 p, q에 적용했다는 것을 짐작할 수 있다.
* 참고로 주어진 python 파일에 코드 일부분을 ???????????? 와 같이 물음표로 처리한 이유는 그 부분에 쓰이는 함수가 getSexyPrime이기 때문이다.
 
그럼 대충 어떤식으로 두 소수를 구할지 알아보자

sexy prime이 6씩 차이나는 소수라는 점을 감안하면 위와 같이 생각해볼 수 있다.

 
위에 작성한 식을 응용하여 풀이 코드를 작성해보면 여러 방향으로 작성해볼 수 있는데

(1) 위 식을 활용해서 p, q 먼저 구하고 그 값을 통해 복호화 진행하기
출력결과에서 먼저 출력해주는 q 값이 음수로 나올것이다. 근데 python 코드에도 나와있듯이 sexy prime을 이용한 것이기 때문에 음수로 나오는 값은 무시했다..

from sympy.solvers import solve
from sympy import Symbol

n = 110067413853034446062166180561085174675399800582469231501542989197861609958093709113059409812123926927649400547645425688314111465956694491992808266505385887197537236890045002512110096093657023204771106498999090554885456993590436056036537949671172783152946638256190164744404184125578953567094329952157689357147

x = Symbol('x')
q = (x+6)-n/x
p = x
print(solve(q, p))

#출력결과
#q = 10491301818794197956870533631920141403582366486363388796717340358676229364128532294712102202896995090338673728372102793882839671201902933776303545620582969
#p = 10491301818794197956870533631920141403582366486363388796717340358676229364128532294712102202896995090338673728372102793882839671201902933776303545620582963

from Crypto.Util.number import *

n = 110067413853034446062166180561085174675399800582469231501542989197861609958093709113059409812123926927649400547645425688314111465956694491992808266505385887197537236890045002512110096093657023204771106498999090554885456993590436056036537949671172783152946638256190164744404184125578953567094329952157689357147
e = 4294967297
c = 6430247517459839550819948528043546662220213283222011078853709086595801980582952628540465603132800123118448644982850090295098382544235129216039103121116669154107985284621853508059922122931259093211612076479073223996615242648597460278767826566208475843728873065225999150624847387541305731206359041053619452936

q = 10491301818794197956870533631920141403582366486363388796717340358676229364128532294712102202896995090338673728372102793882839671201902933776303545620582969
p = 10491301818794197956870533631920141403582366486363388796717340358676229364128532294712102202896995090338673728372102793882839671201902933776303545620582963

phi = (p-1)*(q-1)
d = inverse(e,phi)

flag = pow(c, d, n)

print(long_to_bytes(flag))

(2) 이진탐색 방식 - 다른 블로그 참고함

from Crypto.Util.number import *

n = 110067413853034446062166180561085174675399800582469231501542989197861609958093709113059409812123926927649400547645425688314111465956694491992808266505385887197537236890045002512110096093657023204771106498999090554885456993590436056036537949671172783152946638256190164744404184125578953567094329952157689357147
c = 6430247517459839550819948528043546662220213283222011078853709086595801980582952628540465603132800123118448644982850090295098382544235129216039103121116669154107985284621853508059922122931259093211612076479073223996615242648597460278767826566208475843728873065225999150624847387541305731206359041053619452936

low = 0
high = n
while(high - low > 1):
    mid = (high + low) // 2
    if(mid*(mid+6) >= n):
        high = mid
    else:
        low = mid

p = high
q = high + 6
e = 4294967297
phi = (p-1)*(q-1)
d = inverse(e,phi)

flag=pow(c,d,n)
print(long_to_bytes(flag))

(3) isqrt(n의 음이 아닌 정수 제곱근을 반환해줌) 사용 - 다른 블로그 참고함

from Crypto.Util.number import *
from math import isqrt

n = 110067413853034446062166180561085174675399800582469231501542989197861609958093709113059409812123926927649400547645425688314111465956694491992808266505385887197537236890045002512110096093657023204771106498999090554885456993590436056036537949671172783152946638256190164744404184125578953567094329952157689357147
e = 4294967297
c = 6430247517459839550819948528043546662220213283222011078853709086595801980582952628540465603132800123118448644982850090295098382544235129216039103121116669154107985284621853508059922122931259093211612076479073223996615242648597460278767826566208475843728873065225999150624847387541305731206359041053619452936


def fermat_method(N, attempt=None):
    a = isqrt(N) + 1
    while attempt != 0:
        b2 = a * a - N
        if isqrt(b2)**2 == b2:
            return (a - isqrt(b2), a + isqrt(b2))
        a += 1
        if attempt is not None:
            attempt -= 1
    return None

p, q = fermat_method(n)

phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, n)

print(long_to_bytes(m))

(4) x를 기준으로 p, q가 3씩 차이난다는 점을 이용

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

n = 110067413853034446062166180561085174675399800582469231501542989197861609958093709113059409812123926927649400547645425688314111465956694491992808266505385887197537236890045002512110096093657023204771106498999090554885456993590436056036537949671172783152946638256190164744404184125578953567094329952157689357147
e = 4294967297
c = 6430247517459839550819948528043546662220213283222011078853709086595801980582952628540465603132800123118448644982850090295098382544235129216039103121116669154107985284621853508059922122931259093211612076479073223996615242648597460278767826566208475843728873065225999150624847387541305731206359041053619452936


def decrypt(n,e,c):

    x = isqrt(n+9)
    p = x+3
    q = x-3

    phi = (p-1)*(q-1)
    d = inverse(e, phi)
    flag = pow(c, d, n)
    
    return long_to_bytes(flag)

print(decrypt(n, e, c))

flag: HSOC{Th3_P@pag0_1s_1nnoc3nt}
(문제 제작에는 구글번역기를 사용했지만 문제에 알맞게 번역기 이름을 플래그에 넣고 싶었다. 번역기하면 파파고가 떠오르더라구요..)
 
위 4가지 방법 모두 출력결과로 플래그가 잘 나온다.
이 외에도 다른방식으로 코드를 작성할 수 있고 sexy prime의 특성만 이해하고 있다면 툴을 이용해서 n을 소인수분해한 다음 p, q를 구하고 복호화하거나(내가 했을 때는 소인수분해에 실패했다.) Python으로 p, q를 구하고 툴로 플래그를 얻어낼 수 있을 것이다.
또한 브루트포스를 이용하여 풀어도 플래그값이 나오기는 할 것 같다. 
 
처음에 설명한 것처럼 2가지 접근방법을 통해 sexy prime 이라는 것을 알 수 있도록 문제를 제작하였지만 사실 sexy prime이라는 것을 몰라도 p, q가 6씩 차이난다는 것을 활용하면 문제를 풀 수 있다.
주어진 값과 코드를 이용해서 RSA에 핵심적으로 이용되는 값들을 정리해보면 아래와 같다.

#주어진 값
n = 110067413853034446062166180561085174675399800582469231501542989197861609958093709113059409812123926927649400547645425688314111465956694491992808266505385887197537236890045002512110096093657023204771106498999090554885456993590436056036537949671172783152946638256190164744404184125578953567094329952157689357147
e = 4294967297
c = 6430247517459839550819948528043546662220213283222011078853709086595801980582952628540465603132800123118448644982850090295098382544235129216039103121116669154107985284621853508059922122931259093211612076479073223996615242648597460278767826566208475843728873065225999150624847387541305731206359041053619452936

#구할 수 있는 값
q = 10491301818794197956870533631920141403582366486363388796717340358676229364128532294712102202896995090338673728372102793882839671201902933776303545620582969
p = 10491301818794197956870533631920141403582366486363388796717340358676229364128532294712102202896995090338673728372102793882839671201902933776303545620582963
phi = 110067413853034446062166180561085174675399800582469231501542989197861609958093709113059409812123926927649400547645425688314111465956694491992808266505385866214933599301649088771042832253374216040038133772221497120204739641131707798971948525466766989162765960908733420538816418446236549761226777345066448191216
d = 15098229052637160358532865616389298506396159965552798705730231466638846621357610535466416013940312645793598912529231727525911386433046899145504172681621130407086662312734205341155034093231254932808853267354434062164601943943394941506606066039410904591461324161029868452303484330376860103353089292266012833025

 
원래는 처음에 만든 50점 RSA 문제 이후 다음 문제를 DES 문제로 만들려고 생각했었다. 근데 하다보니 뜻대로 안될때도 꽤 있었고 DES 문제를 만들려면 키를 weak key나 semi weak key를 사용해서 하려고했는데.. 문제를 만들다 중간에 검토해봤는데 뭔가 좀 마음에 안들어서 RSA 활용(?) 문제를 만들게되었다.

이 문제도 첫번째 50점 문제를 풀었으면 쉽게 풀 수 있는 문제라서 50점으로 바꿀까 고민을 했었다. 근데 다행히도 교내대회 100점에 적당했던 것 같다. 웬만하면 겹치는 유형 없이 최대한 다양하게 문제를 출제하고 싶었는데 아쉽다...

 

(sexy prime이 아닌 twin prime을 사용했을 경우에는..??)