Navigation
A propos
2. Le RSA
Le principe
Le premier système à clé publique solide à avoir été inventé, et le plus utilisé actuellement, est le système RSA. Publié en 1977 par Ron Rivest, Adi Shamir et Leonard Adleman de l'Institut de technologie du Massachusetts (MIT), le RSA est fondé sur la difficulté de factoriser des grands nombres, et la fonction à sens unique utilisée est une fonction "puissance".
L'algorithme de chiffrement
Départ :
- Il est facile de fabriquer de grands nombres premiers p et q (+- 100 chiffres)
- Etant donné un nombre entier n = pq, il est très difficile de retrouver les facteurs p et q
( 1 ) Création des clés
- La clé secrète : 2 grands nombres premiers p et q
- La clé publique : n = pq ; un entier e premier avec (p-1)(q-1)
( 2 ) Chiffrement : le chiffrement d'un message M en un message codé C se fait suivant la transformation suivante :
C = Me mod n
( 3 ) Déchiffrement : il s'agit de calculer la fonction réciproque
M = Cd mod n
tel que e.d = 1 mod [(p-1)(q-1)]
La signature électronique
Après la confidentialité de la transmission d'un message subsiste un problème : son authenticité. Alice voudrait
bien envoyer un message M à Bob de telle façon que celui-ci soit sûr qu'elle est réellement l'émettrice du message,
et qu'un intrus ne tente pas de venir semer la confusion.
Le système RSA fournit une solution à ce problème :
Rappelons les données :
- Alice seule détient la clé secrète d et diffuse la clé publique (n,e)
- Alice va se servir de la clé publique pour chiffrer le message M
( 1 ) Alice accompagne son message chiffré de sa signature, qui correspond à :
Md
( 2 ) Bob va donc voir si l'égalité (Md)e mod n = M est vérifiée. Si c'est le cas, Alice est bien l'émettrice du message.
Sécurité du système : primalité, factorisation
Comme pour les protocoles fondés sur le logarithme discret, la sécurité du système RSA est calculatoire : elle dépend essentiellement de la difficulté de factoriser un entier qui est le produit de deux grands nombres premiers. Si on sait factoriser n, il est facile de trouver d. Il est à noter qu'il est conseiller d'utiliser des clés de 1024 bits (+- 309 chiffres décimaux).
Le principal objet des attaques est l'implémentation, la mise en oeuvre du RSA. C'est la manière de se servir du système qui peut poser problème, pas le système lui-même (par exemple, prendre une clé trop petite...).
Signalons enfin que le réel problème du RSA (et des autres systèmes à clé publique) n'est pas la sécurité, mais la lenteur. Tous les algorithmes à clé publique sont 100 à 1000 fois plus lents que les algorithmes à clé secrète, quelle que soit leur implémentation (logicielle ou matérielle) !
Exemple : chiffrer BONJOUR
1) Alice crée ses clés :
- La clé secrète : p = 53 , q = 97 (Note : en réalité, p et q devraient comporter plus de 100 chiffres !)
- La clé publique : e = 7 (premier avec 52*96), n = 53*97 = 5141
2) Alice diffuse sa clé publique (par exemple, dans un annuaire).
3) Bob ayant trouvé le couple (n,e), il sait qu'il doit l'utiliser pour chiffrer son message. Il va tout d'abord remplacer chaque lettre du
mot BONJOUR par le nombre correspondant à sa position dans l'alphabet :
B = 2, O = 15, N = 14, J = 10, U = 21, R = 18
BONJOUR = 2 15 14 10 15 21 18
4) Ensuite, Bob découpe son message chiffré en blocs de même longueur représentant chacun un nombre plus petit que n. Cette opération est essentielle, car si on ne faisait pas des blocs assez longs (par exemple, si on laissait des blocs de 2 chiffres), on retomberait sur un simple chiffre de substitution que l'on pourrait attaquer par l'analyse des fréquences (Voir chiffre de César).
BONJOUR = 002 151 410 152 118
5) Bob chiffre chacun des blocs que l'on note B par la transformation C = Bemod n (où C est le bloc chiffré) :
C1 = 27mod 5141 = 128
C2 = 1517mod 5141 = 800
C3 = 4107mod 5141 = 3761
C4 = 1527mod 5141 = 660
C5 = 1187mod 5141 = 204
On obtient donc le message chiffré C : 128 800 3761 660 204.
<< Chapitre précédent - Chapitre suivant >>