ebCTF 2013 | Cry200 « One to many » [Write Up]

« We identified some unground operatives that are using RSA to exchange messages with each other. We managed to incercept some, can you decrypt them? »

In this crypto challenge, we were given 4096 text files containing n, the modulus, and encrypted_msg, the… encrypted message in RSA, for example:

n=26333310450538018922754780999390656095778306505676845060884655684478963575905092939966192922376766245967309992100280702615117131138195189023050716261277390713184585025013592148731617238278466419556014293931469225194083420265498838149763602571145878257236032831071521289223583847157078683743105416431459498519
encrypted_msg=21983969140803822325609213682371677541118366642566464975674011162870371196612604552460072048535005351156255126305641515072642135238027309663447856364083298135213217815730193596676216908753565067409744644956134819221664959634996396447196797120347921449971545943005770238545266454147582069821248555801239065167<br>

The modulus in each file were clearly impossible to factorize into prime numbers (actually they are factorizable… but not in a reasonable time I guess). We are not in possession of the e exponent too, but we guess it is 2¹⁶ + 1 since it’s the most common exponent used in RSA encryption.

The attack here was to find the primes p and q for some ciphertext, assuming there is, in all the 4096 moduli n, at least two n which have a common prime factor.

We can do that by calculating the GCD for two numbers n : if their prime factors are different, the GCD will equal 1. Otherwise, it will be equal to… the prime factor they share! Here is our brute-force written in python. It returns the two files and their common prime factor in less than one or two hours:

import os
def pgcd(a, b):
    if not a % b: return b
    else: return pgcd(b, a % b)

s = [] # Extract the 4096 moduli in this list
for f in os.listdir(os.getcwd()):
    if f.endswith('.txt'):
        a = open(f, 'rb')
        n = int(a.read().split('\n')[0][2:])
        s.append(n)

for a in s:
    for b in s:
        if a <> b:
            if pgcd(a, b) <> 1:
                print "Modulus 1 : %s\n" % a
                print "Modulus 2 : %s\n" % b
                print "Share this prime factor : %s" % (pgcd(a, b))
                raw_input()
 
raw_input('end')

Result:

Modulus 1 : 44773042548742702474295335995949427035022417431933052602449899044058381350186934487451001127255473051273961879797200659847079357397126796343844819335863268551823184240856883126066618151894961863328400597387177023085260437202127320012971938731240640813038294863503629203250803235566797963451028654216202761019

Modulus 2 : 94411733223408329382133158037163790542444846846237588800669469956095363765357730934881112049411254123920922190838444307250255142732585516688207447515408599581116991882364669243229002019328795373173040521072598151716223244770473235244943526093596413424286906986535811009153754627662686316876294300583601667051

Share this prime factor : 10425079766382366420625494866767568875370400467976574956525983652357684133387986157895827317253539750222139144079507972326197750248804720295152321770469893

Nice! With a little search, we find that the first modulus comes from message763.txt :

n=44773042548742702474295335995949427035022417431933052602449899044058381350186934487451001127255473051273961879797200659847079357397126796343844819335863268551823184240856883126066618151894961863328400597387177023085260437202127320012971938731240640813038294863503629203250803235566797963451028654216202761019
encrypted_msg=19630044458840643114271155032712382827110852052850817560572656865545146506507970544423117217918442687886855421278192074553141563189813465427308616253732539857042185557180064721689108815897519646854608798517275109189582925292927220045808576291870458570854691347760343137635010316699780762764045417418389606358

n = p * q, we know n and p (or q ?) – n / p should give us q. We have factorized our modulus 😀

>>> n = 44773042548742702474295335995949427035022417431933052602449899044058381350186934487451001127255473051273961879797200659847079357397126796343844819335863268551823184240856883126066618151894961863328400597387177023085260437202127320012971938731240640813038294863503629203250803235566797963451028654216202761019
(...)
>>> p = 10425079766382366420625494866767568875370400467976574956525983652357684133387986157895827317253539750222139144079507972326197750248804720295152321770469893
(...)
>>> n / p
4294743402647317145901262628653422288185392672235165936634294900008837422649404484498636063264036230502676976313274980808216755990091568561444682687544383L

We know now p and q, we know n, and we know e (2¹⁶ + 1). Let’s decipher the RSA! Cryptool does it well. Here is our deciphered message :

00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001654017007658187682426965875188341341359219601909526572443862465890875159782041540616891058011142001461707130926616696387145792755411207550357557176317751248779555876794766099329795150247750405408919140477

Converting this number into string (or decimal -> hex -> string) gives us the deciphered plaintext.

This is a secret message, for your eyes only: ebCTF{b517aba29f132c52c9426a177952a2d8}

Enjoy.