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 :

( 1 ) Création des clés

( 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 :

( 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 :

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 >>

Page exécutée en 0.226619 secondes.