Solution de maxbekh pour AdveRSArial Crypto (Infant)

On remarque dans le code fourni, que l’algorithme utilisé ressemble à du RSA, mais au lieu d’utiliser p et q premiers, il génère directement n premier.

Le chiffrement RSA fonctionne comme cela :

1. On choisit deux nombres premiers p et q.
2. Leur produit n = p * q est le module de chiffrement.
3. phi(n) = (p - 1) × (q - 1).
4. On choisit e (dans notre cas e = 2 ** 16 + 1).
5. L’exposant de déchiffrement d est l’inverse de e modulo phi(n).
6. On retrouve le message par : pow(ciphertext, d, n).

Pour déchiffrer le message, il faut calculer phi(n) = (p-1) * (q-1) or, nous n’avons pas p et q.

Si l’on choisit p = n et q = 1, on se retrouve avec phi(n) = 0.

Comme phi(n) représente le nombre d’entiers premiers avec n et que n est premier, on trouve phi(n) = n-1.

On peut alors déchiffrer :

def rsa_decrypt(ciphertext, p, q, e):
    n = p * q
    phi = n - 1
    # Calculate the private exponent d
    d = pow(e, -1, phi)
    # Decrypt the message
    plaintext = pow(ciphertext, d, n)
    return long_to_bytes(plaintext)

print(rsa_decrypt(c, n, 1, e))
# Output: b'FCSC{d0bf88291bcd488f28a809c9ae79d53da9caefc85b3790f57615e61c70a45f3c}'