RSA

Généralités :
C’est l’algorithme à clé publique le plus répandu, et le plus populaire. Il a été inventé en 1977 par Ron Rivest, Adi Shamir et Leonard Adleman (le GCHQ anglais aurait eu en fait un peu d’avance).

Cet algorithme peut être utilisé pour :

- la confidentialité
- la signature électronique
- l’échange de clés symétriques.

Sa sécurité repose sur la difficulté de factoriser les grands nombres (bien que ça ne soit pas mathématiquement prouvé, ce n’est qu’une conjecture).

Une longueur de clé de 512 bits n’est aujourd’hui plus vraiment suffisante, on lui préférera du 1024 ou du 2048 bits. A vrai dire, même le 1024 commence à vieillir...
Mais des longueurs de clé telles que 2048 mettent probablement RSA à l’abri pour encore bien des années.
Ce qui pourrait complètement compromettre la sécurité de RSA serait une avancée mathématique qui aurait pour conséquence de faciliter la factorisation des grands nombres (mais il est possible qu’une telle avancée soit mathématiquement interdite). Ou bien la construction de "machines à factoriser" révolutionnaires.

Principe :
Choisir deux grands nombres premiers (au moins 200 chiffres, chacun d’une longueur d’à peu près la moitié de la taille de clé voulue, voir Miller-Rabin pour un test de primalité probabiliste) :

p et q

Calculer :

n = p*q

Pour obtenir la clé publique de chiffrement : choisir e tel que :

e et (p-1)(q-1) soient premiers entre eux.
phi(n) = (p-1)(q-1) est la fonction d’Euler qui donne le nombre d’entiers premiers à n et inférieurs à n)

Pour obtenir la clé privée de déchiffrement : choisir d tel que :

ed = 1mod[(p-1)(q-1)]

(ou encore d tel que (ed-1) soit divisible par (p-1)(q-1))

soit : d = e^(-1)mod[(p-1)(q-1)]

(on utilise pour cela l’algorithme d’Euclide étendu)

La clé publique est constituée de : e et n
(c’est la longueur en bits de n qui donne la longueur de la clé RSA utilisée)

La clé privée est : d et n

Chiffrement et signature sont mathématiquement les mêmes opérations, ce n’est que par convention que l’on choisit que telle clé sera celle de chiffrement et telle autre celle de déchiffrement.

Pour chiffrer un message m, on le découpe en blocs de taille plus petite que la clé et tels qu’ils aient une représentation unique modulo n
(en binaire on pourra prendre la plus grande puissance de 2 inférieure à n)
Les blocs Ci de texte chiffré se calculent à partir des blocs Mi du texte clair par (ils auront la même taille que la clé) :

Ci = (Mi^e)mod(n)

Pour déchiffrer les blocs chiffrés Ci, il suffit de les exponentier par d :

Mi = (Ci^d)mod(n)

Un démo de RSA en javascript

Utilisation dans la pratique :
Utilisation de certificats :
Afin de s’assurer de l’appartenance d’une clé publique on utilisera souvent des certificats X.509v3, bien que PGP et GPG (autres formats, et non signés par une Autorité) en soient des contre-exemples de poids. Le certificat contient une clé publique, et la signature d’une autorité reconnue par les protagonistes. Cette clé pourra aussi bien être une clé de chiffrement, une clé de vérification ou bien une clé qui remplira les deux fonctions.

Chiffrement :
Dans la pratique (voir plus bas) on utilise souvent une combinaison de RSA et d’un algorithme symétrique. On chiffre tout d’abord les données à l’aide d’une clé symétrique aléatoire, puis on chiffre cette clef à l’aide de la clé publique du destinataire et on joint enfin cette clé symétrique chiffrée aux données chiffrées. Le destinataire déchiffrera cette clé symétrique à l’aide de sa clé asymétrique privée, puis déchiffrera les données à l’aide de la clé symétrique.
S’il y a plusieurs destinataires, chacun aura sa copie de la clé symétrique chiffrées avec sa clé publique. Voir la page sur le chiffrement mixte.

Signature et intégrité :
Pour la signature et l’intégrité on passera tout d’abord les données à signer au travers d’une fonction de condensation (ou de hachage), puis on chiffrera à l’aide de la clé privée RSA le résultat (condensât ou "hashcode"). Ce dernier résultat sera ajouté aux données, ainsi par exemple que le certificat associé à la clé publique. Le destinataire déchiffrera ce résultat à l’aide de la clé publique, passera les données au travers de la même fonction de condensation, et comparera les deux résultats obtenus : s’ils sont égaux il aura l’assurance que les données n’ont pas été modifiées et que l’identité inscrite sur le certificat de l’expéditeur est bien la même que celle qui à signé.
Voir la page sur la signature.

Vitesse :
La vitesse de RSA, qui est imposée par la vitesse des exponentiations modulaires, est au mieux environ 1000 plus faible qu’un DES réalisé en matériel (si le DES est en soft, RSA est environ 100 fois plus lent).

Doubler la taille de la clé :

multiplie par 4 le temps des opérations utilisant la clé publique
multiplie par 8 le temps des opérations utilisant la clé privée
multiplie par 16 le temps de génération des clés (et dans les cartes à puces à microprocesseur, ça se sent...)

Si RSA est réalisé sur des cartes à puce, il sera encore plus lent (notamment la génération).

La faible vitesse de RSA le rend peu propice au chiffrement de grandes quantités de données, c’est pourquoi on adoptera souvent des cryptosystèmes mixtes constitués de la combinaison d’un algorithme symétrique et d’un algorithme asymétrique.

Pour augmenter la vitesse des processus, on peut choisir certaines valeurs particulières de e :
3, 17 ou 65537 par exemple.
Cette dernière valeur est celle recommandée par la norme X509.
Il n’y a aucune faiblesse connue à choisir ces données arbitraires de e (qui peuvent être partagées entre tout un groupe d’utilisateurs). Il faudra cependant veiller à ce que les p-1 et q-1 ne soient pas des multiples de la valeur choisie.

Trouver des nombres premiers est lent. La plupart des implémentations ont donc recours à des algorithmes probabilistes de test de primalité pour déterminer p et q, comme le test de primalité de Miller-Rabin. Les nombres p et q ont alors une probabilité d’être premiers. Il est possible de rendre cette probabilité aussi faible que l’on veut. Seul peu de nombres échouent aux tests de primalité : ce sont les nombres de Carmichael, il y en a peu et on peut facilement les écarter.

Sécurité et attaques :
La sécurité d’une clé RSA et d’une clé DES symétrique de même taille n’est pas comparable.

Il peut aussi être vulnérable si la même paire de clé est utilisée à la fois pour chiffrer et pour signer : l’attaquant peut faire signer à la victime des données, ce qui mathématiquement est équivalent à un chiffrement et disposer ainsi d’un texte clair connu... ce qui peut permettre certaines attaques... en théorie.

Bien que le nombre de nombres premiers soit infini, le nombre disponible pour une longueur de clé fixé est limité. Mais pour une clé de 512 bits par exemple, il y en a à peu près 10^150 de longueur égale ou inférieure, ce qui rend une attaque par essai exhaustif des nombres premiers... longue, très longue.

Standards et protocoles :
RSA est une composante de nombreux protocoles ou spécifications :

SSL/TLS
IPSec
S/MIME
Certains PKCS
...

RSA fait partie de nombreux staldards comme :

ISO 9796
ITU-T X.509 (standard sécurité)
ETEBAC 5 (standard français du secteur bancaire et financier)
ANSI X9.31 rDSA
X9.44 draft (standard américain du secteur bancaire et financier)
AS2805.6.5.3 (standard de gestion des clés australien)
SWIFT (standard interbancaire international)