HackDef 2017 Quals Round - Crypto 200

By FinalBoss Team - IPN CIC

El reto consiste en un ataque al algoritmo RSA, en este caso consistió en factorizar n para obtener p y
q, una vez obtenidos estos valores se calcula d que es necesario para descifrar el mensaje que es la
bandera.

Como datos se tienen:

# Modulo de la llave pública y privada
n=
2235086418712661768151626687955930030928546270062171901699911
2389047482157945941401520330806968575538251705687846165469874
6757960228157820566088066237993236971531320231234836506275968
1453093365876487947132075965320562942684765796450652706028529
6024257624668532104396385873220527621763943956814719711072214
7714124020746065809478945406125384801169529679999925885734204
75338090592837431796105740289
# Exponente publico
e = 131071
# Bandera Encriptada
c =
1255647201172218478260623612976308005637697606272669734755846
9569176784192397886003785192366201367104182788647156445030564
9068998563101239291921628912978850147273218244280288724270791
8974358731527719321432663445571427642709711573754628554463360
8128403858929934251769113549022554389413271819079696974037555
1700049653687685733672099382611641569239836036965896608394845
49745438112551086044435480150

Para factorizar n y encontrar los valores de p y q, se utilizó la herramienta de https://factordb.com/, al
dar como entrada el valor de n, nos devuelve los valores que en este caso corresponden a p y q, como
se muestra en la Figura 1.

Una vez encontrados estos valores se realizó un script en python para calcular d y descifrar la

bandera. Se declaran los valores de p y q.

p = 2147483647
q =
104079321946643990819252403273640855386152622472667048053191
123504036080596733602980122394417323241848424216139542810077
913835662483234649081399066056773207629241295093892203457731
833496615835504729594205476898112116936771475484788669625013
844382602917323488853111608285384165850282556046662248318909
188018470682222031405210266984354887329580288780508697361869
00714720710555703168729087

Lo siguiente es calcular el valor Phi(n) = (p-1) (q-1)

# Se calcula el valor de phi

phi = ((p-1)*(q- 1))%n

Dicho valor es necesario para calcular d = e^-1 mod phi, lo cual es el resultado del siguiente código:

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)

def modinv(a, m):
   g, x, y = egcd(a, m)
   if g != 1:
      raise Exception('modular inverse does not exist')
   else:
      return x % m

d = modinv (e,phi)

Con el valor de d, ahora si podemos descifrar la bandera con m = c ^ d mod n, utilizando además una
librería que nos permite convertir de binario a ASCII.

m = pow (c,d,n)
print ('\n c^d Mod n')
print (format(m,'x'))
flag = str (format(m,'x'))
print("\nThe flag is: ")
print(binascii.unhexlify(flag))

El resultado obtenido del script, es como se muestra en la Figura 2.

Figura 2 - Ejecución de script para obtener la bandera.

Y se obtiene la bandera correspondiente al reto:

                                      flag{RSA_Encryption_Matematicas__Odialas_Mas!}