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)

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)

 
 
 
 
 
 
Partager sur Twitter  |  Partager sur LinkedIn