InCTF 2017- ‘RSA 1s Fun’ Writeup

Author: s0rc3r3r

Points: 150

Mathematics and Crypto make a deadly combination!

Intended Solution

The challenge, as the description suggests, involves applying mathematics to solve the RSA based encryption system. The encryption code:

from Crypto.Util.number import *

e1 = 9
e2 = 123

def prime_gen():
    while True:
        p = getPrime(1024)
        q = getPrime(1024)
        n = p*q
        phin = (p-1)*(q-1)
        if GCD(e1, phin) == 1 and GCD(e2, phin) == 1:
            return (p, q, n)
p, q, n = prime_gen()

print "p: ", p
print "q: ", q
print "n: ", n

flag = bytes_to_long(open("flag.txt").read().strip())
assert flag < n  assert flag**9 > n

c1 = pow(flag, e1, n)
c2 = pow(flag, e2, n)

print "c1: ", c1
print "c2: ", c2

Two different public keys e1 = 9 and e2 = 123 are being used to encrypt the same message and generate ciphertexts c1 and c2 respectively. By Euclid’s Extended Algorithm, we can calculate coefficients of Bezout’s Identity(a, b) as:

(e1 * a) + (e2 * b) = gcd(e1, e2)

(9 * 14) + (123 * (-1)) = 3

We can use this to calculate the following:

c1 = m^e1 mod n,    c1¹⁴ = m^{e1 * 14} mod n

c2 = m^e2 mod n,    c2^-1 –> modular inverse of c2 over mod n

c1¹⁴ * c2^-1 = m^{9*14 – 123*1} mod n = m³ mod n

We got c’ = m³ mod n

The first approach to solving the challenge now is to simply calculate the cube root of c’ and get the message m (assuming that cube of the message m is not longer than n, so the mod n becomes insignificant), which will give us the flag! The final exploit here:

import gmpy2

def egcd(a, b):
  if (a == 0):
  	return (b, 0, 1)
  else:
  	g, y, x = egcd(b % a, a)
  	return (g, x - (b // a) * y, y)

e1 = 9
e2 = 123
gcd, a, b = egcd(e1, e2)

n = 20333254691880587307936337314043639948842015851766398721090407302956251747329178671065731363354242526918246592697537469440013326971933436283835869953205389270794974354649936678036319060756577261022556782132429409780897209149764199287410299784057084352324514504271696413494646839995519846723688986124055120364880326007695589111754397828528457250142219463380016968678118831245509936377859985508548247011183090952083546525956426331360929466685835043639197893823027068509935334942858316357902671524385521979877692725137825489358188564620960020623845798362737725511832599703350407211941298094845205725160096135130216181313
c1 =  2866791410300982209581160682590202727064178543076468723716078826950532969157774101954514922479283214185175373229881780072369520438740798302436630031675039672300318769368767955792505592752805860745234692545366181568007521937632340018956679380260500802782833711686141651664082139115158618826168145286856348145354753632046650620308808972739953286345861292290201731165641142066561682325108497439840996007817718867058397591772543642180750091195001088272756689038764789254056479422278248719908521586989566666627884968909640431124163896764204393560913490590077031435330210539197147863375903077038431543732467897239841303254
c2 =  4885380046320959173192546343078276684691332256383912605057298042587886299857925359111993638346079742855901548480637616739859552612594516195353274413384196031117800323365020227270534113077873495873427630043665909900269079429369278616380093363461750865151600963795982366459803668193824090785941635118091474660341873110737939523053889456794499981099067016285308979086542807431649241746997853017895403122499239437959257317791355670927392439947971693686626563871460473615495733407552262810140872942644864039949040024604157449691762976155356244948844966532675041107842219829093528089233085580060616519775692376829287486898

c2_inv = gmpy2.invert(c2, n)
c1 = pow(c1, 14, n)

cp = c1*c2_inv % n
m = gmpy2.iroot(cp, 3)
print m

Which will give us:

m = 247609674632147650090262257139521529731046191259209156960476300398052310578797937951890759519171888345244778365

Converting this to hex and hex-decoding it to a string will give us the flag: inctf{n07_s0_e4sy_70_expl01t_7h1s_RSA_orIsIt?}