crt rsa 풀이

문제 제목

문제 정보

문제 파일

from Crypto.Util.number import *
from sympy import nextprime

flag = b'DH{?????????????????????????????????????????}'

q = getPrime(1024)
p = nextprime(q + 1)
N = p * q
while True:
    e = getPrime(256)
    if GCD(e, (p - 1) * (q - 1)) == 1:
        d = inverse(e, (p - 1) * (q - 1))
        break
dp = d % (p - 1)
dq = d % (q - 1)
qinv = inverse(q, p)

print(f'N = {N}')
print(f'dp = {dp}')
print(f'dq = {dq}')
print(f'qinv = {qinv}')
print(f'encrypted flag = {pow(bytes_to_long(flag), e, N)}')

문제에서 nextprime()을 사용하고 있습니다.

이럴 때 페르마 알고리즘으로 p와 q를 구할 수 있습니다.

구한 p와 q를 이용해서 해당 코드의 복호화를 진행하면 됩니다.

 

from Crypto.Util.number import *

N = 17948511285493300329663323258195331982457673714893763358975757454357794146761942536199675910644737535032294253964049159842186570968056667266419619507719323804826081797783354299038931673298496646168795298615822384776794592701956268828621223628320062590681499024555165188845776312941921888481847930150352088584434287713759319039174076972358521882062581907001327041461753852165590069436051782982689919429945743791430940658535139007114572922551366414747565741651067931237209605722356132042146874857593069884900662975060486279544773904463552413406034744915949180453809434835855678058877284488397131613444109761571557646633
dp = 98114400169001425270235253505125148329227911350400520188412451867206808304346336008305883147024143514395029878587021422691040567826979869375902098867986143796698631261638820107831323604277224628842246260578730244819140369726085780281250206418068210442417957091854782556240651950329001236052564605568562297895
dq = 78494653554478468683961952382877541263477908662712358980641513207865638240344136847784536847517100747728442774613448344446632263470095707297560952059661928899577193377137800038198271334646646457202401674902481705009198397701496640570454164581614423923454906414335186100055079650194305843385501412374469122839
qinv = 74362464564378971051785266958812128007980003786731328239210134366495879644704539818322065775405881672014958630085896450475950792806867420193623468614911875434444962708263762418510745721394808966581324919134515005650349502310924127568080430769701716113377816633145828340258766887625001426514277456041350380498
encrypted_flag = 2690279597166359753788645610851420847574576441110347600203193597371956870780386418826735604853525198482381105494814410555393480327815791665543406566079340995789042470632098522811031149322651380694801731379198669984134134873970397610425874712312612134241510122536712579758121673037676460990207008588855704907842513769742780608754763631645664246738753391262463115794671479824761805811549371152824677457663982506047111069979712091297507882248121029731313738753027538605561082701193992063280256306057834517089920457919622701534748408675746312507646025700235249039064809932934331194491381354431847567260677105004286226333

a = b"133 972054 121347 636854 690883 100058 311049 229390 200223 733449 729786 311756 651799 574935 007808 118501 535529 446632 847719 618558 752600 104377 389316 102868 940940 775390 831881 895482 412743 293150 775391 755435 151811 106301 194794 622208 571139 049739 788240 551608 711735 226684 257881 750073 656827 465560 030424 890082 998974 784049 490046 797437"
b = b"133 972054 121347 636854 690883 100058 311049 229390 200223 733449 729786 311756 651799 574935 007808 118501 535529 446632 847719 618558 752600 104377 389316 102868 940940 775390 831881 895482 412743 293150 775391 755435 151811 106301 194794 622208 571139 049739 788240 551608 711735 226684 257881 750073 656827 465560 030424 890082 998974 784049 490046 798109"

a = int(a.replace(b" ", b""), 10)
b = int(b.replace(b" ", b""), 10)

print(GCD(a, b))
assert a * b == N, "Error"
q = a
p = b
m1 = pow(encrypted_flag, dp, p)
m2 = pow(encrypted_flag, dq, q)
h = (qinv * (m1 - m2)) % p
m = m2 + h * q

print(long_to_bytes(m))

FLAG 획득 완료

문제 풀이 성공