Skip to content

Prime suspects

Description

Write Up: Tyron
Créateur: danihmds
Difficulté: easy
Points: 100
Format du flag: AMSI{}

Enoncé

  • Français: Les preuves sont devant vous. Les coupables se cachent parmi elles, attendant que vous les exposiez. Saurez-vous traquer les suspects et révéler leur secret ?
  • English: The evidences are in from of you. The culprits are hiding among them, waiting for you to expose them. Can you track down the suspects and reveal their secrets?

Pièce(s) jointe(s):

Solution détaillée

Il s'agit d'un challenge RSA basique avec une mauvaise génération des nombres premiers.

chall.py 
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes

def generate_rsa_key(bits=2048):
    p = getPrime(bits // 2)
    q = p
    n = p * q
    e = 3

    return {'n': n, 'e': e, 'p': p}

def encrypt(message, e, n):
    m = bytes_to_long(message)
    if m >= n:
        raise ValueError("Message is too large for the modulus.")
    c = pow(m, e, n)
    return c

def decrypt(ciphertext, d, n):
    m = pow(ciphertext, d, n)
    return long_to_bytes(m)

key = generate_rsa_key(bits=2048)

flag = b"AMSI{????????????????????}"
ciphertext = encrypt(flag, key['e'], key['n'])
print(f"Encrypted: {hex(ciphertext)[2:]}\n")

print(f"Modulus n: {hex(key['n'])[2:]}")
output.txt 
Encrypted: 43fc75436dbceec5346614f2e69fa96ec786fce0dcede2c1292b6b5e01b9e6b4f9455a07542be404adb5269dac863f402d7448bb1d3783d1e6fa79fcbc363b4c1d9f7d5e0b3685af10f6a004965La solution détaillée sans oubliée les retours a la ligne. Pas forcément a chaque phrase mais en tout cas avant chaque image.<br>

Modulus n: 70491c457dd252b77dedb78bad925972bee1e13dbcb60e357715947d708e4dca79de09039fedecfc46351aacb849f35b60357c4a5e348a436886482970c8eb2ca02b70c08b762d6c6ad9bb7a5b49c06a93c44a52dc956cbdf6a4e964db09f4592c6ea81aead7ea5b5c54ebef8340d057fe2e30d05dbf53f5a39e21215d6df8ad4ae39e2ef5d6caa40ba86af391d74b049d730b68f98b5af29294ee3e8c7fac02f241a4f924a06ca0321f197e869f27b80c286c80a3747366d5ff33146697baed142590f036503a7b221861758274563cbfcc508d8ee58eab40ed81da5c067863f1eddbd751f6846d90e3da2128be9e91241bb554a1d764caa45b331abe260471

En lisant le code source de challenge, on s'apercoit que $ p = q $ce qui signife que les deux nombres premiers sont égaux alors qu'ils devraient etre différents dans une implémentation correcte.

Ainsi, si $ p = q $, alors $ n = pq = pp = p^{2} $

Pour retrouver p il suffit de prendre la racine carrée de n.

Ensuite on aura plus qu'a calculer l'indicatrice d'Euler ou ϕ puis la clé d et enfin récupérer le message.

Pour calculer la racine carrée on aurait pu utiliser math.sqrt() mais les grands nombres sont mal gérés. Alors il faut plutot utiliser la fonction integer_nthroot de sympy.

Ensuite pour ϕ on a cette formule :

indicatrice d'euler

Pour \(p_{1}^{k_{1}-1}\), habituellement avec RSA, \(k_{1}\) vaut 1, car il s'agit du nombre de fois ou le nombre premier \(p_{1}\) apparait dans la decomposition en facteur premier de n.

Ce qui fait que : \(k_{1}-1=0\)
et donc : $p_{1}^0 = 1 $
et : $ ϕ = p_{1}^{k_{1}-1}(p_{1}-1) = 1 * (p-1)$
Et pour deux nombres premiers différents au total on a : $ ϕ = (p_{1}-1) * (p_{2}-1) = (p-1) * (q-1)$

Sauf qu'ici que dans ce challenge on a \(p_{1} = p_{2}\) donc \(k1 = 2\)
Donc : \(ϕ = p_{1}^{k_{1}-1}(p_{1}-1) = p_{1}^{1}(p_{1}-1)= (p) * (p-1)\)

Ainsi on obtient le script suivant :

solve.py 
from Crypto.Util.number import bytes_to_long, long_to_bytes, isPrime
import sympy

ct=0x43fc75436dbceec5346614f2e69fa96ec786fce0dcede2c1292b6b5e01b9e6b4f9455a07542be404adb5269dac863f402d7448bb1d3783d1e6fa79fcbc363b4c1d9f7d5e0b3685af10f6a004965

n=0x70491c457dd252b77dedb78bad925972bee1e13dbcb60e357715947d708e4dca79de09039fedecfc46351aacb849f35b60357c4a5e348a436886482970c8eb2ca02b70c08b762d6c6ad9bb7a5b49c06a93c44a52dc956cbdf6a4e964db09f4592c6ea81aead7ea5b5c54ebef8340d057fe2e30d05dbf53f5a39e21215d6df8ad4ae39e2ef5d6caa40ba86af391d74b049d730b68f98b5af29294ee3e8c7fac02f241a4f924a06ca0321f197e869f27b80c286c80a3747366d5ff33146697baed142590f036503a7b221861758274563cbfcc508d8ee58eab40ed81da5c067863f1eddbd751f6846d90e3da2128be9e91241bb554a1d764caa45b331abe260471

e=3

p = sympy.integer_nthroot(n, 2)[0]
print(f"{p = }")

assert p*p == n

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

d = pow(e, -1, phi)
m = pow(ct, d, n)

print(long_to_bytes(m))

FLAG: AMSI{l0ng_l1ve_...}

Retex

C'était un challenge facile mais qui m'a quand meme permi de mieux comprendre l'indicatrice d'euler.

Lien(s) utile(s)