Criptografía (CXLV): Solución Reto picoCTF 2018 "rsa-madlibs"

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

En esta ocasión la solución al décimo de ellos, que, en mi opinión, presenta un nivel de dificultad muy fácil (★☆☆☆☆).

Este desafío es introductorio a los retos de criptografía moderna en los que se ve involucrado el criptosistema de clave pública (criptografía asimétrica) más utilizado actualmente, RSA, y consiste en responder correctamente a las preguntas que se formulan sobre él.

- rsa-madlibs - Points: 250:

Su enunciado dice lo siguiente: 'We ran into some weird puzzles we think may mean something, can you help me solve one? Connect with nc 2018shell.picoctf .com 50652'.

Solución: me conecto al servidor.

En la primera pregunta me dan q y p (los dos factores primos del módulo n), piden que conteste si es o no posible y factible obtener el módulo (n), y, en caso positivo, que indique el valor de n.

La respuesta correcta es que sí ('Y'). El módulo (n) es igual al producto de ambos factores primos (q y p). Es decir, n = q * p = 93187 * 94603 = 8815769761.

En la segunda pregunta me dan p (uno de los dos factores primos del módulo n) y el módulo (n), piden que conteste si es o no posible y factible obtener el otro factor primo (q) de n, y, en caso positivo, que indique el valor de éste.

Evidentemente, la respuesta correcta es que sí ('Y'). q = n / p = 6315400919 * 81203 = 77773

En la tercera pregunta me dan e (el exponente de la clave pública) y el módulo (n), piden que conteste si es o no posible y factible obtener ambos factores primos (q y p) de n, y, en caso positivo, que indique los valores de éstos.

En principio, salvo que sea posible factorizar n en un tiempo razonable (si es lo suficientemente grande no es posible. Precisamente en esto radica la seguridad del cifrado RSA) la respuesta correcta es que no ('N').

En la cuarta pregunta me dan q y p (los dos factores primos del módulo n), piden que conteste si es o no posible y factible obtener phi(n), y, en caso positivo, que indique su valor.

La respuesta correcta es que sí ('Y'). phi(n) es igual al producto de (q-1) y (p-1). Es decir, phi(n) = (78203-1) * (79999-1) = 78202 * 79998 = 6256003596.

En la quinta pregunta me dan m (mensaje en texto en claro), e (el exponente de la clave pública) y el módulo (n), piden que conteste si es o no posible y factible obtener c (criptograma correspondiente al texto en claro), y, en caso positivo, que indique el valor de c.

La respuesta correcta es que sí ('Y'). Para calcular c preparo un pequeño script en python;  c=m**e mod(n):

m = 1815907181716474805136452061793917684000871911998851410864797078911161933431337632774829806207517001958179617856720738101327521552576351369691667910371502971480153619360010341709624631317220940851114914911751279825748
e = 3
n = 29129463609326322559521123136222078780585451208149138547799121083622333250646678767769126248182207478527881025116332742616201890576280859777513414460842754045651093593251726785499360828237897586278068419875517543013545369871704159718105354690802726645710699029936754265654381929650494383622583174075805797766685192325859982797796060391271817578087472948205626257717479858369754502615173773514087437504532994142632207906501079835037052797306690891600559321673928943158514646572885986881016569647357891598545880304236145548059520898133142087545369179876065657214225826997676844000054327141666320553082128424707948750331
c = pow(m,e,n)

print c

En la sexta pregunta me dan c (criptograma), e (el exponente de la clave pública) y el módulo (n), piden que conteste si es o no posible y factible obtener m (mensaje en texto en claro), y, en caso positivo, que indique el valor de m.

La respuesta correcta es que no ('N'). Para calcular m (mensaje en texto en claro), salvo que sea posible realizar un ataque con éxito, necesito d (exponente de la clave privada);  m=c**d mod(n):

En la séptima pregunta me dan q y p (los dos factores primos del módulo n) y e (el exponente de la clave pública), piden que conteste si es o no posible y factible obtener d (el exponente de la clave privada), y, en caso positivo, que indique el valor de éste.

La respuesta correcta es que sí ('Y'). Para calcular d preparo un pequeño script en python. Con p y q puedo calcular phi, de la forma que he indicado anteriormente, y d es el inverso multiplicativo de e modulo phi:

import Crypto.Util.number

print''
print'*** Calcular phi(n)'

q = 92092076805892533739724722602668675840671093008520241548191914215399824020372076186460768206814914423802230398410980218741906960527104568970225804374404612617736579286959865287226538692911376507934256844456333236362669879347073756238894784951597211105734179388300051579994253565459304743059533646753003894559
p = 97846775312392801037224396977012615848433199640105786119757047098757998273009741128821931277074555731813289423891389911801250326299324018557072727051765547115514791337578758859803890173153277252326496062476389498019821358465433398338364421624871010292162533041884897182597065662521825095949253625730631876637
e = 65537

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

print 'phi(n) .......:', phi

print''
print'*** Calcular d'

d = Crypto.Util.number.inverse(e,phi)

print 'd ...........:', d

En la octava y última pregunta me dan p (uno de los dos factores primos del módulo n), c  (criptograma), e (el exponente de la clave pública) y el módulo (n), piden que conteste si es o no posible y factible obtener m (mensaje en texto en claro).

La respuesta correcta es que sí ('Y'). Para calcular d preparo un pequeño script en python. Dividiendo el módulo (n) entre p (uno de los dos factores primos de n) obtengo q (el otro factor primo de n); con p y q puedo calcular phi, de la forma que he indicado anteriormente, y d es el inverso multiplicativo de e modulo phi; finalmente, m=c**d mod(n)

import Crypto.Util.number

p = 153143042272527868798412612417204434156935146874282990942386694020462861918068684561281763577034706600608387699148071015194725533394126069826857182428660427818277378724977554365910231524827258160904493774748749088477328204812171935987088715261127321911849092207070653272176072509933245978935455542420691737433
c = 14699632914289984358210582075909309608817619615764122409514577850253033131275996955127394794512801987443786025277031557775238937388086632327611216460613138074110905840487213116627139558528011448028813522809156509374602431319619052803531008581645459969997969897966475478980398396687104746302415391434104278327526947341073215599683555703818611403510483832532921625745935543818100178607417658929607435582550913918895885596025822532531372429301293588416086854338617700672628239475365045267537032531973594689061842791028000992635092519215619497247452814483357403667400283975070444902253349175045305073603687442947532925780
e = 65537
n = 23952937352643527451379227516428377705004894508566304313177880191662177061878993798938496818120987817049538365206671401938265663712351239785237507341311858383628932183083145614696585411921662992078376103990806989257289472590902167457302888198293135333083734504191910953238278860923153746261500759411620299864395158783509535039259714359526738924736952759753503357614939203434092075676169179112452620687731670534906069845965633455748606649062394293289967059348143206600765820021392608270528856238306849191113241355842396325210132358046616312901337987464473799040762271876389031455051640937681745409057246190498795697239

q = n/p

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

d = Crypto.Util.number.inverse(e,phi)

m = pow(c, d, n)

print''
print 'm ...........:', m

Después de incluir las 9 respuestas correctas se muestra el siguiente mensaje:

Con un pequeño script en python convierto a ASCII el texto en claro obtenido en el paso anterior:

import Crypto.Util.number

m = 240109877286251840533272915662757983981706320845661471802585807564915966910385147086109038271870589

print''
print 'm (ascii) ...:', Crypto.Util.number.long_to_bytes(m)

Con lo que la solución a este reto es: picoCTF{d0_u_kn0w_th3_w@y_2_RS@_c6724916}.