HackDef 2017 – Crypt 200 (writeup)

This challenge was about decrypting a ciphertext using factorization attack [1] against RSA, which basically consists on recovering d (of the private key), given the public key (e, n). The attack works when p or q are small.

GIVEN ELEMENTS

#Modulus
n = 22350864187126617681516266879559300309285462700621719016999112389047482157945941401520330806968575538251705687846165469874675796022815782056608806623799323697153132023123483650627596814530933658764879471320759653205629426847657964506527060285296024257624668532104396385873220527621763943956814719711072214771412402074606580947894540612538480116952967999992588573420475338090592837431796105740289

#Public exponent
e = 131071

#Cipher text
c = 12556472011722184782606236129763080056376976062726697347558469569176784192397886003785192366201367104182788647156445030564906899856310123929192162891297885014727321824428028872427079189743587315277193214326634455714276427097115737546285544633608128403858929934251769113549022554389413271819079696974037555170004965368768573367209938261164156923983603696589660839484549745438112551086044435480150
SOLUTION

We used ’primefac’, a python function to find p and q, since n = (p*q).

#!/usr/bin/env python

import primefac
import sys

n = int( sys.argv[1] )
factors = list( primefac.primefac(n) )

if len(factors) == 0:
        print ('\n\033[01;31m' + 'Not Found...' + '\033[00m')
else:
        print ('\n\033[01;32m' + 'Found!' + '\033[00m')

        print ('\n\033[02;37m' + 'Prime 1:' + '\033[00m')
        print factors[0]
        print ('\n\033[02;37m' + 'Prime 2:' + '\033[00m')
        print factors[1]

Running the script, we found the two prime numbers that multiplied give the value of n.

Now we have p and q. Following the RSA algorithm [2]:

  • Calculate Φ(n) = (p-1)(q-1)
Φ(n)= (2147483647-1)( 10407932194664399081925240327364085538615262247266704805319112350403608059673360298012239441732324184842421613954281007791383566248323464908139906605677320762924129509389220345773183349661583550472959420547689811211693677147548478866962501384438260291732348885311160828538416585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729087-1)

Φ(n)= 22350864176718685486851867797634059981921377162006456769732407583728369807542333341846970508956336096519381503003743855920394788231432215808285341715659417091475811260199354141238376468757750309103295920847800232657939615635964287358978581418333522873186408240372047500562059699083347358928559115044847382880493600227538358744754019585840044628220009971114537703684288437375872126876090789527556

Now that we have d, we can decrypt c, since m=c^d mod (n). Using another module of Erik Ramses´s program, we decrypt the flag.

Since we obtained the plain text as a big number, we need to code it into something that we are able to read, like ASCII.

And the flag is:
flag{RSA_Encryption_Matematicas__Odialas_Mas!}

[1] Factorization Attack to RSA
[2] RSA algorithm

:3

1 thought on “HackDef 2017 – Crypt 200 (writeup)”

Leave a Reply

Your email address will not be published. Required fields are marked *