RSA — Cryptographie asymétrique
★★★★★
Les mathématiques RSA
n = p*q (p et q : grands nombres premiers secrets)
phi(n) = (p-1)*(q-1)
e = 65537 (exposant public)
d = e^(-1) mod phi(n) (exposant privé)
Chiffrement : c = m^e mod n
Déchiffrement : m = c^d mod n
Clé publique : (n, e)
Clé privée : d (ou p, q, d)Attaques classiques en CTF
# 1. n factorisable
factordb.com ou sympy.factorint(n)
# 2. e=3 + message petit (m^3 < n)
from gmpy2 import iroot
m, exact = iroot(c, 3)
# 3. Wiener (d trop petit)
from owiener import attack
d = attack(e, n)
# 4. Hastad (même message chiffré pour 3 personnes, e=3)
from sympy.ntheory.modular import crt
# 5. n en commun entre 2 clés
from math import gcd
p = gcd(n1, n2) # -> on a p !