Solution de guillp pour AdveRSArial Crypto (Infant)

En téléchargeant les inputs, on obtient le code Python suivant:

from Crypto.Util.number import getStrongPrime, bytes_to_long, long_to_bytes

n = getStrongPrime(2048)
e = 2 ** 16 + 1

flag = bytes_to_long(open("flag.txt", "rb").read())
c = pow(flag, e, n)

print(f"{n = }")
print(f"{e = }")
print(f"{c = }")

qui génère la sortie suivante :

n = 22914764349697556963541692665721076425490063991574936243571428156261302060328685591556514036751777776065771167330244010708082147401402002914377904950080486799957005111360365028092884367373338454223568447811216200859660057226322801828334633020895296785582519610777820724907394060126570265818769159991752144783469338557691407102432786644694590118176582000965124360500257946304028767088296724907062561163478654995994205065812479605136088813543435895840276066683243706020091519857275219422246006137390619897086478975872204136389082598585864385077220265194919486850918633328368814287347732293510186569121425821644289329813
e = 65537
c = 11189917160698738647911433493693285101538131455035611550077950709107429331298329502327358588774261161674422351739941120882289954400477590502272629693853242116507000433761914368814656180874783594812260498542390500221519883099478550863172147588922341571443502449435143090576514228274833316274013491937919397957017546671325357027765817692571583998487352090789855980131184451611087822399088669705683765370510052781742383736278295296012267794429263720509724794426552010741678342838319060084074826713065120930332229122961216786019982413982114571551833129932338204333681414465713448112309599140515483842800125894387412148599

c est ici le resultat de l’opération pow(flag, e, n) et il va donc être nécessaire de retrouver ce flag.

La fonction pow(base, exp, mod) de Python est décrite ici: https://docs.python.org/3.12/library/functions.html#pow. Elle renvoie le résultat de base élevé à la puisssance exp le tout modulo mod. Ça plus le titre du challenge, vous devriez vous douter que nous avons ici un chiffrement similaire à RSA.

Pour les novices en crypto, l’article Wikipedia sur RSA détaille la façon de générer des clés RSA: https://en.wikipedia.org/wiki/RSA_(cryptosystem)

Je cite :

Choose two large prime numbers p and q.
    To make factoring harder, p and q should be chosen at random, be both large and have a large difference.[1] For choosing them the standard method is to choose random integers and use a primality test until two primes are found.
    p and q should be kept secret.
Compute n = pq.
    n is used as the modulus for both the public and private keys. Its length, usually expressed in bits, is the key length.
    n is released as part of the public key.
Compute λ(n), where λ is Carmichael's totient function. Since n = pq, λ(n) = lcm(λ(p), λ(q)), and since p and q are prime, λ(p) = φ(p) = p − 1, and likewise λ(q) = q − 1. Hence λ(n) = lcm(p − 1, q − 1).
    The lcm may be calculated through the Euclidean algorithm, since lcm(a, b) = |ab|/gcd(a, b).
    λ(n) is kept secret.
Choose an integer e such that 1 < e < λ(n) and gcd(e, λ(n)) = 1; that is, e and λ(n) are coprime.
    e having a short bit-length and small Hamming weight results in more efficient encryption – the most commonly chosen value for e is 216 + 1 = 65537. The smallest (and fastest) possible value for e is 3, but such a small value for e has been shown to be less secure in some settings.[15]
    e is released as part of the public key.
Determine d as d ≡ e−1 (mod λ(n)); that is, d is the modular multiplicative inverse of e modulo λ(n).
    This means: solve for d the equation de ≡ 1 (mod λ(n)); d can be computed efficiently by using the extended Euclidean algorithm, since, thanks to e and λ(n) being coprime, said equation is a form of Bézout's identity, where d is one of the coefficients.
    d is kept secret as the private key exponent.

Mais ici, le code Python génère directement un n premier sans passer par la génération de p et q. C’est donc l’équivalent d’avoir n égal à p et q égal à 1.

On peut donc appliquer la suite de la recette avec ces valeurs :

Compute λ(n)

Quelques notions de Maths ou une lecture assidue de l’article Wikipédia s’imposent. Je cite le passage intéressant :

since p and q are prime, λ(p) = φ(p) = p − 1, and likewise λ(q) = q − 1

Ici notre n est le resultat de l’appel à la fonction getStrongPrime et est donc premier, donc λ(n) = n-1

Choose an integer e

e est ici généré dans le code Python et sa valeur est 65537 (valeur couramment utilisée avec RSA)

Determine d as d ≡ e^−1 (mod λ(n))

On connait déjà e et λ(n), il ne reste donc plus qu’à calculer d. En Python, le code équivalent est d = pow(e, -1, n-1).

Pour déchiffer le flag, on applique donc l’opération de déchiffrement:

flag = pow(c, d, n)

Ce qui donne un long entier, qui est la répresentation décimale de notre flag texte. On peut le reconvertir en ASCII avec l’opération inverse de bytes_to_long, qui n’est autre que long_to_bytes.

Voilà le code complet :

from Crypto.Util.number import long_to_bytes
n = 22914764349697556963541692665721076425490063991574936243571428156261302060328685591556514036751777776065771167330244010708082147401402002914377904950080486799957005111360365028092884367373338454223568447811216200859660057226322801828334633020895296785582519610777820724907394060126570265818769159991752144783469338557691407102432786644694590118176582000965124360500257946304028767088296724907062561163478654995994205065812479605136088813543435895840276066683243706020091519857275219422246006137390619897086478975872204136389082598585864385077220265194919486850918633328368814287347732293510186569121425821644289329813
e = 65537
c = 11189917160698738647911433493693285101538131455035611550077950709107429331298329502327358588774261161674422351739941120882289954400477590502272629693853242116507000433761914368814656180874783594812260498542390500221519883099478550863172147588922341571443502449435143090576514228274833316274013491937919397957017546671325357027765817692571583998487352090789855980131184451611087822399088669705683765370510052781742383736278295296012267794429263720509724794426552010741678342838319060084074826713065120930332229122961216786019982413982114571551833129932338204333681414465713448112309599140515483842800125894387412148599

d = pow(e, -1, n-1)

print(long_to_bytes(pow(c, d, n)).decode())