InCTF 2017- Multi-Layer RSA writeup

Author: s0rc3r3r

Points: 100

Intended Solution

This is probably the easiest challenge in the Crypto section in InCTF.  The encryption script:

from Crypto.Util.number import *

flag = open("flag.txt").read()
flag = int(flag.encode("hex"),16)

p = getPrime(512)
q = getPrime(512)
n = p*q
phin = (p-1)*(q-1)

encryption_keys = [34961, 3617491, 68962801, 293200159531, 1191694878666066510321450623792489136756229172407332230462797663298426983932272792657383336660801913848162204216417540955677965706955404313949733712340714861638106185597684745174398501025724130404133569866642454996521744281284226124355987843894614599718553178595963014434904833]

for i in encryption_keys:
    assert GCD(i,phin) == 1

for i in encryption_keys:
    flag = pow(flag, i, n)

flag = hex(flag)[2:].replace("L","")

obj1 = open("ciphertext.txt",'w')
obj1.write(flag)

As we can see, the encryption is layered, after the message is encrypted using the first public key i.e. first element of ‘encryption_keys‘, the result is then encrypted with the next public key i.e. second element of ‘encryption_keys‘ and so on. We can write it mathematically as:

c1 = m ** e1 % n

c2 = c1 ** e2 % n

…

c5 = c4 ** e5 % n

c5 = m ** (e1 * e2 * e3 * e4 * e5) % n

Here e1, e2, …, e5 elements of ‘encryption_keys‘; c1, c2, …, c5 are the ciphertexts for each iteration.

The result of multiplication of e1, e2, e3, e4, e5 becomes quite large and can be checked for Wiener’s Attack.

e = 3047442173541658754667464233797118324917469250436575767227172319344577259865313428705759330024959317716760816959590728238918140105663188172228696589411452947738069773833351725455888549656717874059636289036277785342126992626060696063089487811946920569580454880169977542532087635095357205433679009382368108273

The final exploit (Implementation of Wiener’s Attack in python/sage)

from sage.all import *

encryption_keys = [34961, 3617491, 68962801, 293200159531, 1191694878666066510321450623792489136756229172407332230462797663298426983932272792657383336660801913848162204216417540955677965706955404313949733712340714861638106185597684745174398501025724130404133569866642454996521744281284226124355987843894614599718553178595963014434904833]

e = 1
for i in encryption_keys:
    e *= i
n = 135568509670260054049994954417860747085442883428459182441559553532993752593294067458983143521109377661295622146963670193783017382697726454953197805014428888491744355387957923382241961401063461549210355871385000347645387907568135032087942016502668629010859519249039662555733548461551175133582871220209515648241

c = int("5d695edb47b81a303d162611f7d407579160ef8818929031e1e13ca20cb7094eddbb0658d95980e1753182c5d5c529fb45062891bb5da573c618e35df0103233ded582a53ed807846b19ea82be427f2bbc63e5c7eb685d8a22b2b7539cf45d4ad93bbf5b892b66288b568b6bbff6bb263d809475e6f0aa3cfd01539d8364c243", 16)

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

Which will give us the flag: inctf{w13n3r’s_4774ck_s0lv3d_17_4ll_r1gh7?}