RSA

Cryptographie : Algorithmes

V) Le RSA

Soit deux nombres premiers p et q assez grands.

Posons N = pq
et N' = (p - 1)(q - 1)

D'après le "petit" théorème de Fermat :

x^r.s = 1 [mod N] si r.s =1 [mod N']

On obtient donc les algorithmes suivants :

C = T^r [mod N]

T = C^s [mod N]

D'après cet algorithme, n'importe qui peut crypter des messages. Mais même celui qui a crypté le message ne peut le décrypter s'il ne possède pas la clé privée.

Point faible du RSA : si quelqu'un parvenait à factoriser N, il aurait alors les nombres p et q, qui lui permettraient alors de retrouver s. C'est pourquoi p et q doivent être très grands, plus de cinquante chiffres, car au-delà de 150 chiffres, il n'est pas possible actuellement de factoriser N. A titre d'exemple, une équipe de 600 utilisateurs a mis six mois à casser un nombre de 129 chiffres ! Le RSA repose donc sur notre ignorance en ce qui concerne la factorisation des grands nombres.