Challenge Points: 150
Challenge Description: 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 script:

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 key exponents \(e_1 = 9\) and \(e_2 = 123\) are being used to encrypt the same message and generate ciphertexts \(c_1\) and \(c_2\) respectively. By Extended Euclidean Algorithm, we can calculate coefficients of Bezout’s identity \(a, b\) as:
$$e_1*a + e_2*b = gcd(e_1, e_2)$$ $$(9*14) + (123*(-1)) = 3$$

We can use this property to compute the following: $$c_1^{14}\equiv m_1^{14e_1}\mod n$$ $$c_2^{-1}\equiv m_1^{-e_2}\mod n$$ $$c_1^{14}c_2^{-1}\equiv m^{9*14 - 123*1}\mod n = m^3\mod n$$

We got \(c’ \equiv m^3 \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 larger 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?}