from Crypto.Util.number import *
flag = "UNKNOWN"
p = getPrime(2048)
q = getPrime(2048)
e = 3
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
N = p * q
a = getPrime(256)
b = getPrime(256)
flag = bytes_to_long(flag)
flag1 = a * flag + b
c1 = pow(flag1, e, N)
c2 = pow((flag), e, N)
assert(pow(c1, d, N) == flag1)
assert(pow(c2, d, N) == flag)
print(N)
print(e)
print(c1)
print(c2)
print(a)
print(b)
encrypt.py를 보면 내가 구하려는 것은 flag이기 때문에 주어진 6개의 요소 중 c1, a, b는 사용하지 않았다. 다운받은 enc.txt도 보면 e값이 3으로 매우 작은것을 알 수 있었고 낮은지수 공격을 이용하여 문제를 풀었다.
from gmpy2 import *
from Crypto.Util.number import *
import time
n = 317040651679373211203052920616005723678020156043628323332424772070975737453408838469787064188786011573404860315719531289497744855149648693106833220893566469137933367925417989088393428081488338940326190378085032657287146700415402636680277863355428263621630525484435545273639843015411759501613170657498993265825219268635185095788704667818488133253959599802463638649406699422719391733724583724025291694081932388296146208021483007849056796340521197771858162785429158848258434728868971277822370788477078046638988244145956273926422409006854446490844902097353140906585907615729831021135264713171213218099904040054190835213689864989036128553169219265026898127693711592592146507088549862468638817790078090116453255902533987667528301890465974635865742293209293806778416593653897850790336390681201239324555097941294112232117306893385741521626628689787545632725387549814767531756371737740572219769069441283585425896640819299563592008738345302900504187795287179485677802770486028077737997406541494777650298180989153685352404527946553530659987383623342371095072298448494604853114349302537264362538517244435429874419107749816127165211721817516961841383469631957904885678760629435470386620807103484614770446981317888580422731368821491703012190183243
c = 8297423020022584155011048994131832532824769074603023730133414978795876083975829767265894418737130405482092398749557510849356438382806334207752350424328189587538835124850818790342725062432577666660785216065345678061943982215620548836592472455231224905601436909814422212405387665285635705441455639510030326136599676781656710020740773913531981988901910524876336689922252137646035508407628715768925469851812056183896960489642237162363954459588105185425583983516407862459239754702318180363135870652414123417287108500334785797074965659493879646074666170795550533107295994421467507825853297020990968465269194425974012716422816703183529876173808423121297943817528992643716946584739099328084201918671645348445667073297906942267193317797356444500014074902610476607216717889696917598060829137189261664903853879838844091472012719908117333187156067157240412062289054821454999696908286081864861687576456825071844285971295647010885157801032909560332164820250910702287272446130959717
e = 3
with local_context() as ctx:
ctx.precision=3000
m=iroot(c,e)[0]
flag = long_to_bytes(m)
print(flag)
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점에 적당했던 것 같다. 웬만하면 겹치는 유형 없이 최대한 다양하게 문제를 출제하고 싶었는데 아쉽다...
저저번주 금요일(9/23)에 교내 해킹방어대회가 열렸다. hsoc 동아리 부원들이 문제를 출제하고 운영하는 대회이며 나같은 경우 이번에 씨텦 문제도 첨 만들어봐서 어려움을 좀 겪었다. 현재 hsoc의 암호학 분야에 속해있기 때문에 총 3문제를 만들었고 50, 100, 200점으로 최대한 다양하게 만들었다.
솔직히 문제를 만들기 전에는 3일 정도면 문제를 다 만들고도 남을줄 알았다..ㅎ 어림도 없었다. 생각보다 문제를 만드는데 처음에 내가 만들고자 했던것과 다르게 흘러가는 경우가 많았고 만들고보니까 너무 쉽게 만들어진 경우가 많아서 몇번을 갈아엎었는지 모르겠다. 안그래도 시간이 없는데 계속 갈아엎고 다시 만드느라 나중에는 라잇업이랑 열려있는 대회 사이트 여기저기에 다 들어가보면서 새로운 문제 유형을 계속 찾아봤던 것 같다. 그래서 아마 문제들을 보면 다른 대회에서 한번쯤은 나온 유형의 문제다,, 교외대회가 아닌 교내대회라 그나마 다행이라 해야할까... 암튼 좀 질좋은 문제를 만들어보고싶었는데 그닥 만족스럽지는 않다.
근데 당일날 대회를 진행하다보니 50, 100점 문제를 푼 사람이 많이 없어서 150, 200점 문제는 공개하지도 못했다. 그래도 이번에 문제를 출제하면서 새로운 문제 유형도 진짜 많이 보고 심도있게 공부할 수 있어서 유익하고 좋았다. 다음에 중학생 대상으로 하는 교외대회에서는 기간을 좀 넉넉하게 잡고 문제를 푸는분들이 알차고 질좋다고 느낄만한 문제를 출제하고싶다. 또 시간이 좀 남는다면 크립토 외에 다른 분야 문제도 공부해보고 출제해보고 싶다.
마지막으로 평일날 학교 끝나고 짧은시간 동안 진행했던 대회인데도 불구하고 끝까지 열심히 풀어주신 참가자분들께 너무 감사하고 계속 학교에 남아서 같이 문제를 출제했던 동아리 부원분들과 외부 강사님들께도 진짜 감사하다는 말씀드리고싶다. (특히 대회의 전반적인 부분들을 진행/운영해주신 선배님들 넘 감사드리고 존경합니다..)
easy RSA - 50점
대표적인 공개키 알고리즘인 RSA를 활용한 문제이다.
<시나리오> 한세가 비밀 문서를 보기 위해 잠금을 해제하려고 노력하고 있다. 노트북에 e, c, p, q 4개의 파일이 있다. 파일을 보니 안에 알 수 없는 숫자들이 있어서 메모장에 메모를 해 놓았다. 이 메모를 활용하여 잠금을 해제할 수 있을 것 같다.
from Crypto.Util.number import *
e = 257
p = getPrime(1024)
q = getPrime(1024)
n = p * q
flag = b"HSOC{????????????}"
c = pow(bytes_to_long(flag), e, n)
print(f"e = {e}")
print(f"c = {c}")
print(f"p = {p}")
print(f"q = {q}")
e = 257
c = 5170614309301223184388980439033937972958595751713320965808860175588790115219381694288306180451949710261512480304973718112228889626940113529439227149734487012037630024859786546305225093967154391890149077265714446582747768706411436149671496479109814775690406008776885497246411111989054712865047658076549493437166223452452855195649368804859350881162375200684571102147323943146082552216356213851098024600173550937621944196190441066471923633389014705391050788386027507663015531178749441167149946800122899769099206880827114130951143393000212588720045757847160070434793928195140628142207776720680351969286852634379093267395
p = 121082940632566084365045468274080389844245747988255783680486430339285622475938449072789554464746638386992904689290579744213300917014736134613903560443148772127353839823710670680986528534128280877375044770611360109829049475842435278969303947209412658556907276581778492754960030258658453902050691012787944153029
q = 93773260875800805924403007041088524372825300383500367049104233796459989047050929611151854646094506486446127494624906576319038878918384371070507039400233234869045356878874646585055502928435133167377331216852702026481058788799943840756755689058510106076276525924408876911194766461521214272472920976958554265097
위처럼 python 파일 하나와 txt 파일을 문제파일로 제공해주었다.
1. 문제를 보면 e, c, p, q 4개의 값이 주어졌는데 이는 각각 공개키, 암호문, 두 소수를 나타낸다. 우리가 구하고자 하는것은 플래그값인 M(평문)인데, 이를 구하기 위해서는 개인키인 d와 N이 필요하다. 참고로 마지막 식에서 N이 아닌 Φ(N)을 법으로 둔 이유는 지수들이 Zn*의 원소 자체가 아니고 원소의 색인으로 작용하기 때문이라 한다. (이제부터 Φ(N)을 phi라 하겠음) 위 식에 따라서 phi를 아는 공격자는 e의 역원을 계산해서 d를 쉽게 유도할 수 있고 그렇게 때문에 p와 q가 노출되면 안된다. phi = (p-1)*(q-1)이기 때문이다.
2. 주어진 문제에서는 p와 q가 주어졌기 때문에 이 값을 통해서 phi를 구할 수 있다. 주어진 p, q를 통해 N 또한 구할 수 있다. 구한 phi와 주어진 e를 이용하여 mod의 역원을 계산하여 d를 구할 수 있다. M을 구하는데 필요한 요소인 c, d, n을 통해 평문을 얻어낼 수 있다.
3. 최종적으로 코드를 작성해보면 아래와 같다.
from gmpy2 import *
p = 121082940632566084365045468274080389844245747988255783680486430339285622475938449072789554464746638386992904689290579744213300917014736134613903560443148772127353839823710670680986528534128280877375044770611360109829049475842435278969303947209412658556907276581778492754960030258658453902050691012787944153029
q = 93773260875800805924403007041088524372825300383500367049104233796459989047050929611151854646094506486446127494624906576319038878918384371070507039400233234869045356878874646585055502928435133167377331216852702026481058788799943840756755689058510106076276525924408876911194766461521214272472920976958554265097
e = 257
c = 5170614309301223184388980439033937972958595751713320965808860175588790115219381694288306180451949710261512480304973718112228889626940113529439227149734487012037630024859786546305225093967154391890149077265714446582747768706411436149671496479109814775690406008776885497246411111989054712865047658076549493437166223452452855195649368804859350881162375200684571102147323943146082552216356213851098024600173550937621944196190441066471923633389014705391050788386027507663015531178749441167149946800122899769099206880827114130951143393000212588720045757847160070434793928195140628142207776720680351969286852634379093267395
n = p * q
phi = (p-1) * (q-1)
d = invert(e, phi) # d = divm(1, e, phi)
print ('%x' % pow(c, d, n))
#출력결과: 48534f437b495f406d5f68756e6772797d
m = '48534f437b495f406d5f68756e6772797d'
print(bytes.fromhex(m))
#출력결과: HSOC{I_@m_hungry}
구한 요소들을 RSA 복호화 사이트에 넣어도 평문이 정상적으로 나온다. flag: HSOC{I_@m_hungry}
t1mmyt1m
