rsa_rsa_rsa

Flag: ECW{c3ab8ff13720e8ad9047dd39466b3c8974e592c2fa383d4a3960714caef0c4f2}

Challenge

52KB

esna_FileEncryption.png

image

Ouvrir

Description

---

In this challenge, the participant's task is to decrypt a message that has been encoded in .png. The modulus N for RSA is also given, however no other information is given. Because the modulus is large and prime, prime factorization is not possible, so alternative methods must be used. Luckily, as the modulus is prime, the Euler totient of N is equal to N-1, hence the ciphertext can be decrypted. Sometimes you need multiple primes, sometimes you need only one.

Challenge made by Rufus from :

Solution

A la fin de l'image, on trouve des paramètres RSA.

Il y a 20 nombres premiers (p) et le ciphertext (C). On part sur python pour les extraire, calculer N (le produit de ces facteurs), le totient de N, retrouver d et déchiffrer le ciphertext. Evidemment, il faut une valeur pour le e, on part sur 65537 qui est le plus utilisé.

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

sys.set_int_max_str_digits(0)  # Pour convertir C, on a besoin de retirer la limite

with open('esna_FileEncryption.png','rb') as f:
  data = f.read()
  data = data[data.rfind(b'IEND')+8:] # On ne garde qu'arès l'image
  
  primes = []
  C = None
  for param in data.split(b'.'):
    v = int(param[3:])
    if param.startswith(b'~p='):
      primes.append(v)
    elif param.startswith(b'~C='):
      C = v

e = 65537
N = reduce(lambda a,b: a*b, primes, 1)
P = reduce(lambda a,b: a*(b-1), primes, 1)
d = pow(e, -1, P)
M = pow(C, d, N)
print(long_to_bytes(M))

C = 321820092380837650075502901554553740917669882504596498051700306408353335244201235073143359660273192195417546254118040290779156171623509695296575140144324327019048267114829 N = 388891390351190339486808537827923007434166077468787484562874545771559109089260400240540111721655076663134759163570606594727034649705238717956095821149283571571129301125071

On arrive à déchiffrer le ciphertext, et on obtient... un nouveau ciphertext et un N.

Sauf que ce N est un nombre premier, donc totient(N) = N-1. On peut donc inverser e dans N facilement pour retrouver d et déchiffrer le ciphertext.

C = 321820092380837650075502901554553740917669882504596498051700306408353335244201235073143359660273192195417546254118040290779156171623509695296575140144324327019048267114829
N = 388891390351190339486808537827923007434166077468787484562874545771559109089260400240540111721655076663134759163570606594727034649705238717956095821149283571571129301125071
P = N-1
d = pow(e, -1, P)
M = pow(C, d, N)
M = long_to_bytes(M)
print(M)

ECW{c3ab8ff13720e8ad9047dd39466b3c8974e592c2fa383d4a3960714caef0c4f2}