RSA est basé sur l’opération mathématique d’exponentiation modulaire. Pour chiffrer un message $m$ avec la clé publique $(n, e)$, on calcule :
$$ c = m^e \pmod{n} $$
Dans notre cas :
- Le message m est un très grand nombre (308 chiffres)
- L’exposant $e = 65537$ (un nombre premier couramment utilisé en RSA
- Le module $n$ est aussi un très grand nombre (309 chiffres)
Le calcul demandé est donc : $m^{65537} \pmod{n}$
Voici un exemple de code en Julia pour résoudre cela:
# Message en clair
m = parse(BigInt, "29092715682136811148741896992216382887663205723233009270907036164616385404410946789697601633832261873953783070225717396137755866976801871184236363551686364362312702985660271388900637527644505521559662128091418418029535347788018938016105431888876506254626085450904980887492319714444847439547681555866496873380")
# Clé publique
n = parse(BigInt, "115835143529011985466946897371659768942707075251385995517214050122410566973563965811168663559614636580713282451012293945169200873869218782362296940822448735543079113463384249819134147369806470560382457164633045830912243978622870542174381898756721599280783431283777436949655777218920351233463535926738440504017")
e = BigInt(65537)
# Chiffrement: c = m^e mod n
c = powermod(m, e, n)
println("Flag: FCSC{$c}")
Voici pourquoi on utilise powermod() plutôt qu’un calcul direct :
- Un calcul direct de $m^{65537}$ donnerait un nombre gigantesque difficle à stocker
- L’algorithme
powermod()utilise la méthode “square-and-multiply” qui :- Évite de calculer le nombre complet
- Fait les réductions modulo n à chaque étape
- Est beaucoup plus efficace
La sécurité de RSA repose sur le fait que même si on connaît $c$, $n$ et $e$, il est très difficile de retrouver $m$ sans connaître la clé privée $d$ (qui est l’inverse modulaire de $e$ modulo $φ(n)$).