[CyKor 23-2 Recruiting CTF] Simple RSA

동아리 내 CTF에서 처음으로 문제를 출제해보았다. (개인적으로 문제를 꽤 잘 낸 것 같다.😙😙)

chall

from Crypto.Util.number import *

while(1):
    p = getPrime(1024)
    q = getPrime(1024)
    n = p*q
    d = n - 4*q
    try:
        e = inverse(d, (p-1)*(q-1))
        break
    except ValueError:
        pass
flag = bytes_to_long(open('flag','rb').read())

print("n =", n)
print("e =", e)
print("c =", pow(flag, e, n))

생각만 잘하면 간단한 수식을 통해 $q$를 구할 수 있다. 그 과정은 다음과 같다.

exploit code

from Crypto.Util.number import *

n = 23227703334552340801591254677839992755052896278341298099140999166222807912056043689910277974020861987645341244728989375471841664840671685368283972482755401096052236583100621323190324793386456651910390950379840866238154877486227963389909762457182742460453301831214355283455140805820124030517319290948258659719392098816614155842244431229239674735455966463880442018191338390795922317114099663452860640320130600117133001718864250556257031640760476820543944939228727314849758736059114243743591047937038877169173340726774379901571968873347188280340861217581420521814503332180406537457991447178310769032962121065472013709651
e = 4373353859644052880053601123541971144486675849755087474336579343143055715363655193192422529167837413677879623545319654523794435025165998576831560734037164506953891872537776980095078654910057274994768440402868913533293635958435403449709888067625731144692092716258276414082171300720408899964855718957328664904418458313605354700755615203003991193374366344115688135212696034899163494365037476008675626524913156014205450411495429119659266418975455415289332901398985250173856208531671045290969260317180283260705186108650960565290678214728679185667629566698783737552316583665257838141140073605663066033521981906520022454063
c = 8563748679350139570576541533121412308399674625108528155043880549519084527098231671929280082993104631645824210919168759391834974690976519605105746621663542141636470834838333940325255943497430057632720883282667476369884765951719510128080646821171335310034153541306118514505961970161882087967287971474582057460330424346501946516525558655231931170982814746263225213956688078498526324335965748006974277217385000705214910131017277050727273477106003079860579708232448617579435975765270793378371342033180510511021605791657986015683888067920908127489013313158480184196738756516223573175182163625814062905817908835598283302575

q = GCD(pow(2, e*n, n)-pow(2, 4*e+1, n), n)
print(long_to_bytes(pow(c, n-4*q, n)).decode())

CyKor{w4s_1t_3n0ugh_t0_5timu1a7e_yOur_brAin?}


솔버들에게 박수를👏👏