RSAd

Flag:

Challenge

Description

---

During your technical interview, the cryptography engineer leans back and smiles : Here's a little RSA encryption puzzle we like to give candidates. If you can recover the original message, the job is yours !

Challenge made by:

Solution

On commence par récupérer les valeurs de la clé publique :

from Crypto.PublicKey import RSA

with open('pub.key', 'rb') as f:
  key = RSA.import_key(f.read())
e = key.e
n = key.n

print(n)

3716988686903660069882200144593397220891733095113506351593605688140148007039485335211705258108910464894219203542907578145260135966195170704004891950321931

N est assez petit, on peut tenter de le factoriser, ici j'utilise dcode - Prime Factors Decomposition.

C'est un RSA multi facteurs. Ca fonctionne comme un RSA classique : on calcul le totient de N en multipliant tous les facteurs - 1.

from functools import reduce
from Crypto.Util.number import long_to_bytes

factors = [
  10919940107034605219,
  16447071910419953861,
  17241821787594740653,
  18012762597747138041,
  66637533603400409223323618618931228858113120065268982016035110037371109083233
]

phi = reduce(lambda acc,factor: acc*(factor-1), factors, 1)
d = pow(e, -1, phi)
print(long_to_bytes(d)[::-1])

I_l0ve_rSA_pRiV4t3_K3Y_t00