Criptografía (CXLVII): Solución Reto picoCTF 2018 "Super Safe RSA 2"

Solución a otro reto de criptografía de la plataforma picoCTF 2018.

Continúo con la solución a otro de los retos en los que se ve involucrado el criptosistema de clave pública (criptografía asimétrica) más utilizado actualmente, RSA, y que, en mi opinión, presenta un nivel de dificultad medio (★★★☆☆).

- Super Safe RSA 2 - Points: 425:

Su enunciado dice lo siguiente: 'Wow, he made the exponent really large so the encryption MUST be safe, right?! Connect with nc 2018shell.picoctf. com 56543'.

Solución: A la vista de los datos que se proporcionan: un criptograma (c), el módulo (n) y el exponente de la clave pública (e), puedo ver que, efectivamente, éste último tiene un tamaño mucho más grande de lo habitual, lo que, al contrario de lo que puede parecer, no sólo no hace más seguro el cifrado, sino que puede hacerlo vulnerable al dejar comprometido al exponente de la clave privada (ver ataque de Wiener), ya que, en consecuencia, este último tendrá un tamaño pequeño para lo que se considera seguro.

La pista que se da en la pestaña 'Hints' ('What is the usual value for e?' ) va en esa misma línea (el valor habitual del exponente de la clave pública es 65537 - el número 4 de Fermat -, aunque no únicamente por esta razón, es decir, no sólo para que el exponente de la clave privada tenga un tamaño similar al módulo).

Pruebo entonces a implementar el citado ataque mediante un pequeño script en python:

import owiener

# Ataque de Wiener

print('')
print ('*** Ataque de Wiener')

e = 78997126001201235623371144758465713816651772551831779543244522027032144683614326130938144323129539813040378851330164370487721888450503276078602511546881060824688118409897901245969608045701531074109259330407770535368176141864338317509547431392547354295810602373187933927158351257844503392498364628709181477953
n = 116347580716902453572045366399289125048359639033875664882143382625861963821520789510613806564451001184934768052038855282229624464096827569876474735926287586934104874340882630147675701423489783085181533636422854972985536236852763887624931044764039978304638048762048387456900966174403486895461779640402317268357
d = owiener.attack(e, n)

print ('d ...........:', d)

# Descifrado

print('')
print ('*** Descifrado')

c = 99205452408574371231637908091826281435327094214978689701248737086823238762703293206507391768569311523180423396567539672090226660245593766646856696109968933146864137262649417169897625815664497306667687808079309715685883294888402890875589586745107327124652489292909787099709761794806092740759486157262370245817

m = pow(c, d, n)

print ('c ...........:', c)
print('')
print ('m ...........:', m)

mh = hex(m)

print('')
print ('m (hex) .....:', mh)

# Representacion ascii del texto en claro en hexadecimal

print('')
print ('*** Flag')

ma = bytearray.fromhex(mh[2:]).decode()

print('m (ascii) ...:', ma)

Lo ejecuto y obtengo lo siguiente:

Con lo que la solución a este reto es: picoCTF{w@tch_y0ur_Xp0n3nt$_c@r3fu11y_7042479}.

Como se ve el exponente de la clave privada (d) es el número cuatro de Fermat (65537), es decir, parece que se han intercambiado los valores de ambos exponentes (e y d), lo que ha dado como resultado un cifrado vulnerable :).