MeePwn CTF 2017: Simpler RSA (100)

Tue 18 July 2017 · 2 min read

We are given two files: one is simple.py, which used to do an encryption, and pubkey.txt, which is the generated public key when encrypting with simple.py. Here's the content of simpe.py.

from Crypto.Util.number import *
import random
# from flag import FLAG

def generate(nbits):
    p = getPrime(nbits)
    q = getPrime(nbits)
    n = p * q * p
    g = random.randint(1, n)
    h = pow(g, n, n)
    return (n, g, h)

def encrypt(m, n, g, h):
    r = random.randint(1, n)
    c = pow(pow(g, m, n) * pow(h, r, n), 1, n)
    return c

m = [ord(char) for char in FLAG]
n, g, h = generate(90)
open("pubkey.txt", "w").write("{0}:{1}:{2}".format(n, g, h))

c = [encrypt(mi, n, g, h) for mi in m]
open("enc.txt", "w").write(str(c))

From this code, we can see that the value of n will be about 270 bits, which is quite small to be factorized. Let's try factorize n.

The best factorization algorithm that I know of is quadratic sieve, which apparently could factorize 270 bits integer quite fast. Looking for good implementation quadratic sieve, I came across msieve. The README says it is appropriate for integers with less than 100 digits. Running msieve yield p = 1057817919251064684989791981 and q = 1103935256393984899021164397.

To decrypt each number in c, we need find m which is passed to encrypt function. Since m will be in [1-255], this can be done by brute-forcing m and then validate if it is the right byte. But, how can we validate m?

Doing pow(x,1,n) basically means \(x \pmod n\), so we have two terms for the encryption, pow(g, m, n) and pow(h, r, n). We can cancel out pow(g, m, n) by multiplying c with inverse modulo \(g^{m} \pmod n\). This leave us with pow(h, r, n). At initialization, h = pow(g, n, n) means pow(h, r, n) is the same as pow(g, n*r, n). Now, to cancel this term, we need to multiply it with inverse modulo of \(g^{nr}\). But the r is chosen randomly when encrypting, so we don't know the value of \(g^{nr}\).

To cancel \(g^{nr}\), we don't need to find the inverse modulo, we can instead find \(x\) such that \(g^{xnr} \equiv 1 \pmod n\). From Euler's theorem, we know that if \((xnr) \equiv 0 \pmod{\phi{( n )}}\), then \(g^{xnr} \equiv 1 \pmod n\). Thus, \(x\) is \(\phi{( n )}/gcd(\phi{(n)}, n)\).

If we pick the wrong m (let's say guessed m is \(m'\) and the actual m is \(m\)), this leave the term \(g^{m'-m}\), which will not be equal to zero.

Here's the Python script to decrypt the ciphers:

import random

# public keys
n = 1235280093599323856390922798440377476467763531842392869674688408727824382702235317
g = 1110549711091392805024587195974719739929628997819528005374351081843256209971586072
h = 610466084395822279908554174354632326166097007218620288020807622478449585661028278
assert (pow(g,n,n) == h)

# primes of n
p = 1057817919251064684989791981
q = 1103935256393984899021164397
assert(p*p*q == n)

def gcd(a,b):
    if b == 0: return a
    return gcd(b, a % b)

totient = (p*(p-1)*(q-1))/gcd(p*(p-1),q-1)
cf = gcd(n,totient)
x = totient/cf

def invmod(a):
    return pow(a,totient-1,n)

for i in range(2, 200):
    assert( gcd(i, n) == 1 )
    assert( (i*invmod(i)) % n == 1 )

cipher = [1042684026433440609442082085056733059350277230855631475910449335289565957026925888L, 337451979363258259789969117391527857381178461709773977486124377788140579446959643L, 955044246855117318302069848746627916980637349888954523552188603828273408620783185L, 565084528151941455613387670829541401837686258558304725363697970401158298304784226L, 1217257199494998716855441753878986048959547533911751395319106679987808998530722005L, 500431401136979664818320806505265313829298163109190333815615071157569573408761776L, 918364738570517634370611128928418073524271175997413722821007998543195365584145047L, 1231818404429995719463458343454764290314747233553619629902141039984717307144020885L, 578663363706556074852662555903558050626510818844939214634690712022753850484044077L, 170573141141793020278685561667014942396340687197982787584671361315770701412232820L, 525046404028002961161648698133126471909762913783905233407759137018767422695415644L, 548918541683229869313458652944252600295112072416629330975730507209045241266103104L, 1097888538672145356012505481951969976746432194049237781078685846091302406138295450L, 467055824810727038529002950991149449402485370247343520114443047715384113252663243L, 379325228947504950566222318955652420189554769276755237788381017120582088704791796L, 808135517143354496893964869359259307455178022544381266003759602027195395780858971L, 232206696206622845104449934990777760916638497611027428059484100417419468488368534L, 611231502156630905749534239244947175924425232566020566839692916151929122262556160L, 266317680779170923895607136980535234290396471711461778811550899033797067803838490L, 458442169696983024890517742499158555610082173984048562536247204694360339657234325L, 173156860778775111311074302992389403207838028758953619505920477407616091727957249L, 327701451317276442403593523928518039719286029867533592333080575014882858204660392L, 1061889651976594791626195662010361995350291121541576461530446716234559629390059206L, 501107468516571472868902583880130438298825499145194993732906902954639206415408661L, 793462123972295663612808938124574874398657924694272939619742740367249265250881187L, 419580729971386599858472445685002497860174205402938481254320715563201540618526181L, 1095670842511297949652166375966107611580541850315423104099581710112461928501516645L, 1207404101728741308518114885496775915613418535791624006547396431596035842097919854L, 63257756791404477719948396035346460877053804738003821615924989712602434088623116L, 709743404772556668186521811311910146690879578711491970215935941312652194503904278L, 472145667401895260338686064243470672627707713552548730414485106260542589178719305L, 671679182553553455773258809387401495029229971280677124071355178172582087439182089L, 795683594959663064302728712706823881033923895027131034114737749301583410828859935L, 788511687111620345727088836755516496428115065618134997006646145097528302404655271L, 493455498376449391174132961453557751413575238351804592824587799692504725075730030L, 1071336432168555760392522471606603558083343440707490972056560901765084761996537479L, 76414279730707452882500835328589558586805800097281864786868179845530554318636818L, 1026789233929477564953495880177610952920067780854127113113934470636602509593246257L, 1220456099417710433363957577456670914480321272794999438920511570648408214807875401L, 831001855794529333359541390744984608592774868529241373516540331083225538929223854L, 406700540669900202178972508513521627652422698239818055618399192500676530118703988L, 535793870780869641948563592689023912632863260901941937211057060307409713921739965L, 908165522898293977370960880692560887898587015153655232763363739940417879927826149L, 916463042698051909403902218425035797085521743060997736870228165259059940402603712L, 1124064575055728289901493663250187815236366261544380516480084011806758657972869579L, 302544873761485689612490183241038411927316560916804219683347601892406383914571353L, 326809752614724517585542018284901481393260541798889339649409227233748588383860516L, 828292723696438834080952146252731883891295126479141546958923438287859173086057154L, 835877660712133206131980242990809426528248997858916518574414436451562226433887025L, 145587585798997332370407645289128453608803108424500991984349925153212212859373727L, 463948250139563696175107900326108271430940645044009515704115508942300583165355378L, 944242052057563352409261236875599145504153562928055236566287627433096232314943101L, 579193856270128178962709647899702648998261560149392089962175236519890756116448359L, 1167987057311285845643231967769257342900085143163437221731184706561190379437889873L]

ans = []
for c in cipher:
    for m in range(1,256):
        t = c * invmod(pow(g, m, n))
        if (pow(t, x, n) == 1):
            ans.append(chr(m))

print(''.join(ans))

Flag is: MeePwnCTF{well_is_fact0rizati0n_0nly_w4y_to_s0lve_it?}

Related Posts