Some basic RSA challenges in CTF — Part 1: Some basic math on RSA

A collection of some basic RSA challenges usually seen in Capture the Flag

1. Weird RSA (Pico2017) — RSA decryption given dp and dq

Given:

c: 95272795986475189505518980251137003509292621140166383887854853863720692420204142448424074834657149326853553097626486371206617513769930277580823116437975487148956107509247564965652417450550680181691869432067892028368985007229633943149091684419834136214793476910417359537696632874045272326665036717324623992885
p: 11387480584909854985125335848240384226653929942757756384489381242206157197986555243995335158328781970310603060671486688856263776452654268043936036556215243
q: 12972222875218086547425818961477257915105515705982283726851833508079600460542479267972050216838604649742870515200462359007315431848784163790312424462439629
dp: 8191957726161111880866028229950166742224147653136894248088678244548815086744810656765529876284622829884409590596114090872889522887052772791407131880103961
dq: 3570695757580148093370242608506191464756425954703930236924583065811730548932270595568088372441809535917032142349986828862994856575730078580414026791444659

The basic technique of solving RSA with dp and dq. Wikipedia: https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Example

Simple approach using Sage Math:

sage: d = inverse_mod(65537,phi)
sage: qi = pow(q,-1,p)
sage: m1 = pow(c,dp,p)
sage: m2 = pow(c,dq,q)
sage: h = (qi*(int(m1)-int(m2)))%p
sage: m = int(m2) + h*q
sage: hex(int(m))[2:-1].decode("hex")
'Theres_more_than_one_way_to_RSA'

2. BabyRSA (UIUCTF2017) — e and m too small for a large public key

#! /usr/bin/env python2
from Crypto.PublicKey import RSA
key = RSA.generate(4096, e=5)
msg = "welcome to uiuctf!\nyour super secret flag is: XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"
m = int(msg.encode("hex"), 16)
c = pow(m, key.e, key.n)
f = open("babyrsa.txt", "w")
print >> f, "n = {}".format(key.n)
print >> f, "e = {}".format(key.e)
print >> f, "c = {}".format(c)
n = 826280450476795403105390383916395625701073920777162153138597185953056944510888027904354828464602421249363674719063026424044747076553321187265165775178889032794638105579799203345357910166892700405175658568627675449699540840288382597105404255643311670752496397923267416409538484199324051251779098290351314013642933189000153869540797043267546151497242578717464980825955180662199508957183411268811625401646070827084944007483568527240194185553478349118552388947992831458170444492412952312967110446929914832061366940165718329077289379496793520793044453012845571593091239615903167358140251268988719634075550032402744471298472559374963794796831888972573597223883502207025864412727194467531305956804869282127211781893423868568924921460804452906287133831167209340798856323714333552031073990953099946860260440120550744737264831895097569281340675979651355169393606387485601024283179141075124116079680183641040638005340147490312370291020282845417263785200481799143148652902589069064306494803532124234850362800892646823909347208346956741220877224626765444423081432186871792825772139369254830825377015531518313838382717867736340509229694011716101360463757629023320658921011843627332643744464724204771008866440681008984222122706436344770910544932757
e = 5
c = 199037898049081148054548566008626493558290050160287889209057083223407180156125399899465196611255722303390874101982934954388936179424024104549780651688160499201410108321518752502957346260593418668796624999582838387982430520095732090601546001755571395014548912727418182188910950322763678024849076083148030838828924108260083080562081253547377722180347372948445614953503124471116393560745613311509380885545728947236076476736881439654048388176520444109172092029548244462475513941506675855751026925250160078913809995564374674278235553349778352067191820570404315381746499936539482369231372882062307188454140330786512148310245052484671692280269741146507675933518321695623680547732771867757371698350343979932499637752314262246864787150534170586075473209768119198889190503283212208200005176410488476529948013610803040328568552414972234514746292014601094331465138374210925373263573292609023829742634966280579621843784216908520325876171463017051928049668240295956697023793952538148945070686999838223927548227156965116574566365108818752174755077045394837234760506722554542515056441166987424547451245495248956829984641868331576895415337336145024631773347254905002735757

First look at the code encryption, e is quite small for a large n, a 4096-bit key. Yet the message is not very long, 96 chars.

m^e ~ ((2^8)^96)^5 = 2^(8*96*5) = 2^3840 < 2^4096 ~ N
=> m^e < N

So, there is no way this m^e could exceed N

sage: m = pow(c, 1/5)
sage: hex(int(m))[2:-1].decode('hex')
'welcome to uiuctf!\nyour super secret flag is: flag{c4n_w3_get_s0m3b0dy_t0_sm1th_some_c0pper_pls}'

3. Complex RSA (BackdoorCTF20217) — Double encryption with identical N with large e

The problem gave us a cipher that was encrypted twice by 2 public keys. Let’s have a look at those 2 keys.

from Crypto.PublicKey import RSA
f1 = open("pubkey1.txt", "r")
key = RSA.importKey(f1.read())
print "n1 =", key.n
print "e1 =", key.e
f2 = open("pubkey1.txt", "r")
key = RSA.importKey(f1.read())
print "n1 =", key.n
print "e1 =", key.e
f3 = open("flag.enc", "r")
print f3.read().encode('hex')

We have:

n1 = 554264859105764813308660999731057971935100899008191382001838196926947542874512190874402841957978974562758951331436856029517893995971179950228409634742368823490858553015862605452077729540463185207987338059905256552215054036643656077780363670065154151957507791559734841291875379738678210733333998195096643491711
e1 = 37507589401
n2 = 554264859105764813308660999731057971935100899008191382001838196926947542874512190874402841957978974562758951331436856029517893995971179950228409634742368823490858553015862605452077729540463185207987338059905256552215054036643656077780363670065154151957507791559734841291875379738678210733333998195096643491711
e2 = 4268405784672563577566143285906824408738650526784746749170468318123056940297449811287105187623419766934370809781249030117023876215912795037797160740003478418767197450012472858547143622542113157392499087427939336504102036205305906052998841826136038160560099357503377453502865716581429205507834478651
c = 0x02acd7d7f075333f571c1e342ccfdee05d9262beef9398e54d25f0c3a72d4817ce61971e546923bf5726299be22fd8a74fba6e39ca6b4c2cac7d88480a10f32c26ab5f84bc772c763094e7d4ad81a4d8b8c03bf19045303713ef53cf162fce89ca73ca6376bd73d808d9e9818a160c6be205591583032871127cbb363946812527

Looks like we have 2 identical N in both public key, and also a pretty large public exponential in the second key, this is when RSA breaks.
We know from the hint that the message was encrypted twice.

c1 = m ^e1 (mod N1)
c2 = c1^e2 (mod N2)

But with N1 = N2,

c = m^(e1*e2) (mod N)

As mentioned, a large e (as size of N) suggests a small value of private exponential d. From here we can use Wiener’s Attack

| k/d is somewhere among the convergents of e/N

lst = continued_fraction(e/n)
conv = lst.convergents()
for i in conv:
k = i.numerator()
    d = i.denominator()
try:
    m = hex(int(pow(c,d,n)))[2:-1].decode("hex")
    if "CTF" in m:
        print m
    except:
        continue

And we have the flag:

CTF{c0n6r47zzz_y0u_f0und_0ur_h1dd3n_w13n3r!!}

4. SmallSign (Pico2017) — Some scripting involved

We have to forge a RSA signature of a challenge in 60 sec, given the ability to query signature of any number we want, before the challenge appears/or we run out of time.

Here is the idea,
let s[i] be the signature of m[i], ignore the fact that there’s hashing, the encryption should be like: s[i] = m[i]^d mod N

So, the challenge give us a m, ask us for s, then if we have all the prime factors of m and their signatures, we can surely reconstruct s.
| m = m[1]m[2]*m[3]…​m[n]
then
| s = ( s[1]*s[2]*s[3]…​*s[n] ) mod N

Since the challenge gave us 60s (I think it’s actually 30s :( ), we have to query all the possible signatures of primes we can (about ~600 primes), and wish for a smooth number as our “challenge” Here is my script:

from pwn import *
lstPrime[] = ['''<list of first 600 primes here>''']
test_data = 600
while (True):
    host, port = "shell2017.picoctf.com", 5596
    r = remote(host, port)
    rule = re.compile('[0-9]')
    data = r.readuntil("(-1 to stop):")
    data = rule.findall(data)
    data = "".join(data)
    data = data[2:-6]
    n = int(data)
    lstSign = []
    count = 0
    print "start collecting data"
    try:
        while count<=test_data:
            r.writeline(str(lstPrime[count]))
            data = r.readuntil("(-1 to stop):")
            # print data
            chal = rule.findall(data)[:-1]
            chal = "".join(chal)
            chal = int(chal)
            lstSign.append(chal)
            count += 1

    except:
        print "query out of time"
        test_data -= 10
        print "try smaller test data", test_data
        continue
    print "finish colelcting data"
    r.writeline("-1")
    data = r.readuntil("challenge:")
    print data
    chal = rule.findall(data)
    chal = "".join(chal)
    chal = int(chal)
    print "challenge:", chal
    i = 0
    s = 1
    found = True
    print ""
    while (chal<>1):
            if i>=count:
                print "not found"
                found = False
                break
            if (chal % lstPrime[i] == 0):
                s = s * lstSign[i]
                chal = chal/lstPrime[i]
                print lstPrime[i], lstSign[i]
            else:
                i += 1
                continue
    if (not found):
        r.close()
        print "Cannot find sign of divisor, try again ..."
    else:
        print "N: ", n
        sign = s%n
        print "\n", sign
        r.writeline(str(sign))
        print r.readall()
        break

5. weirderRSA (Pico2017) — Reconstructing RSA private key

e = 65537
n = 496571011226095672657697935970290122845548574135822714162203053330028397027391799830065542357718437892607999951493838719088043590226363768080694596432812846416609931341466073290348107743487085049372709724346227540312466046276838198966923883497262807979518431395518170834562987181070094776689001327513574222439
dp = 3229249396565645680932270225067863220868604476746998731543638523417926260889330866970981867504130463063281063059451886197327583778327232473279705448033663
c = 452485095307755005831994042945640010410414848841226969198697428278561362704426163650275614756516275579898413304604980708420498838480366781698595865992378270949519740759098267615290172414058023074724373555894258721891682651859150617615574298229391657384246470524794556014502304299044260463333868568833548662447

The method is called Reconstruction RSA Private Key. Here is a brief explanation. We have:

dp = d mod p-1

and:

e*d = phi(N) + 1

mod both sides by p-1, we have

e*dp = 1 (mod p-1)
=> e*dp = kp*(p-1) + 1

it is proven that 0 < kp < e (by some awesome dudes), so, we surely can brute the value of kp

sage: for kp in range(1,e):
....:     x = (e*dp-1)/kp+1
....:     if (x in ZZ):
....:         if (n/x) in ZZ:
....:             p = x
....:             break
sage: q = n/p
sage: phi = (p-1)*(q-1)
sage: d = inverse_mod(e,phi)
sage: m = int(pow(c,d,n))
sage: hex(m)[2:-1].decode("hex")
'flag{wow_leaking_dp_breaks_rsa?_53102681769}'