Le cryptosystème RSA à clés publiques - Free

Le cryptosystème RSA à clés publiques Plan Introduction
Principe de fonctionnement du RSA
1 Fabrication des clés
1. La clé publique 2. La clé secrète 2 Utilisation des clés
3. Le cryptage 4. Le décryptage 3 Variantes
5. Message et signature codés 6. Fonction de hachage 7. Les certificats
Les garanties du RSA
1 Il est « facile » de fabriquer des clés...
8. Un peu de théorie sur les nombres premiers 9. Les tests de primarité et leur complexité algorithmique 2 ...mais difficile, voire impossible de les « casser »
10. L'heuristique rho de Pollard 11. La courbe elliptique de Lenstra 12. Le crible quadratique Conclusion Introduction
La cryptographie( du grec kryptos, secret, Seconde Guerre Mondiale et
graphè, écriture) est l'ensemble des techniques permettant de protéger une
communication au moyen d'un code graphique secret (ou clé). De tous temps,
les militaires y ont eu recours. Une des machines de cryptage les plus
célèbres de l'histoire est sans nul doute Enigma utilisée par les allemands
pendant la Seconde Guerre Mondiale. C'est dans le but de casser son code
que les calculateurs électroniques virent le jour (le Kolossus de Türing).
Depuis, les besoins cryptographiques ont explosé et pas seulement pour les
militaires : les applications civiles du chiffrement (banques,
télécommunications, informatique, cartes bleues...) deviennent un moteur
fondamental de progrès. Différents procédés de cryptage ont été utilisés
puis abandonnés car devenus inefficaces. Mais il en est un qui semble
résister aux progrès techniques : le RSA.
Le système de cryptage RSA a été inventé par Ron Rivest, Adi Shamir et
Len Adleman en 1977. Ces trois auteurs avaient décidé de travailler
ensemble pour établir qu'un nouveau système de codage révolutionnaire,
dénommé « système à clé publique » que W.Diffie et M.Hellman venaient
d'inventer, présentait des failles. Ils échouèrent mais, paradoxalement,
découvrirent un nouveau système à clé publique qui supplanta vite le
premier.
RSA est devenu un système universel servant dans une multitude
d'applications : systèmes d'exploitation (Microsoft, Apple, Sun...), cartes
à puces bancaires et bien sûr le réseau Internet pour assurer la
confidentialité du courrier électronique et authentifier les utilisateurs.
Il est partout !
Nous expliquerons le principe de fonctionnement du cryptosystème RSA
puis nous tâcherons de mettre en évidence une dissymétrie qui sous-tendra
notre compréhension : il est facile de multiplier deux nombres premiers
ayant un nombre important de chiffres (>100) mais il est difficile, voire
impossible avec nos moyens actuels de déterminer les facteurs premiers
d'un autre nombre de cette taille dans un temps raisonnable. Principe de fonctionnement du RSA
Le système RSA est utilisé à la fois pour crypter des messages et pour les
signer. C'est un système à clé publique, ce qui signifie que :
. l'algorithme de calcul n'est pas caché, ni la clé de codage (appelée
de ce fait clé publique) ;
. la connaissance de la clé publique du destinataire permet à tous les
émetteurs de crypter les messages qui ne pourront être décryptés que
par le destinataire, grâce à sa clé secrète. Les clés publiques peuvent être publiées dans un annuaire ou obtenues, à la
demande, en contactant le propriétaire.
Ce type de systèmes possédant une clé de décodage différente de la clé de
codage (système dissymétrique) présente un avantage sur les systèmes
classiques (dits symétriques, la même clé servant à la fois pour le codage
et le décodage) car les deux interlocuteurs n'ont pas besoin de se
rencontrer pour convenir d'une clé secrète et encore moins de prendre le
risque de la faire circuler. Seule la clé publique, insuffisante pour le
décryptage, est connue préalablement aux échanges cryptés. Voir l'illustration ci-après : Illustration : Bob [1]souhaite envoyer un message à Alice
|Bob |Alice |
|[pic] |[pic] |
|Fabrication de la clé publique d'Alice qui permet de sceller le |
|message dans la boîte |
|Fabrication de la clé privée d'Alice qui ouvre le cadenas: |
|[pic] |Envoi du message crypté (scellé) grâce |
| |à la clé publique d'Alice [pic] |
|Alice va pouvoir décrypter le |[pic] |
|message (ouvrir le cadenas) | |
|grâce à sa clé privée | |
| |
|Personne n'a pu intercepter le message puisqu'elle seule pouvait |
|ouvrir le cadenas | Voyons à présent l'aspect technique :: 1 Fabrication des clés
13. La clé publique : Pour créer cette clé, il faut construire un quadruplet (p,q,e,d) tel
que :
. p et q sont deux grands nombres premiers (ils ne possèdent que deux
diviseurs : 1 et eux-mêmes) distincts.
. On pose n=pq
. e est un entier premier avec ?(n)= ?(p) ?(q) = (p-1)(q-1), ? étant
appelée l'indicatrice d'Euler (c'est le nombre d'entiers inférieurs et
premiers à n ; ?(pq)= ?(p)?(q) car p et q sont premiers entre eux ; si
p est premier alors ?(p)=p-1).
. Voici l'algorithme servant à déterminer e : Détermination_de_e(entier p, entier q) : entier
Début
?(n) ( (p-1)*(q-1)
/* e > 2 on peut spécifier une valeur minimale de e */
Pour e allant de 2 à ?(n)-1
si (pgcd(e, ?(n)) = 1) alors Retourner(e)
e ( e +1
finpour
Fin
14. La clé secrète . d est tel que ed=1 modulo ?(n). Autrement dit, ed-1 est un multiple
de ?(n). On peut fabriquer d à partir de e, p et q, en utilisant
l'algorithme d'inversion modulaire basé sur l'algorithme d'Euclide
étendu
. Algorithme servant à déterminer d : inversion_modulaire(entier e, entier ?(n)) : tableau d'entiers Début entier r ( e modulo ?(n)
entier q ( ?(n) / e
Bezout = tableau de 2 entiers si r = 0 { Bezout [0] ( 0
Bezout [1] ( 1
retourne Bezout } sinon { Bezout [0] ( inversion_modulaire(e,r)[1]
Bezout [1] ( inversion_modulaire(e,r)[0] - Bezout[0] * q } retourne Bezout;
Fin
2 Utilisation des clés
15. Le cryptage
. Bob, qui veut transmettre une information secrète à Alice, la
transforme en un nombre entier M, inférieur à n (ou en plusieurs,
si nécessaire comme dans l'exemple qui suit), en utilisant des
conventions connues de tous (provenant, par exemple, des codes
numériques des caractères typographiques, ou en prenant a=01,
b=02, etc...).
. Bob calcule ensuite C = M^e modulo n grâce à la méthode
d'exponentiation modulaire (voir l'algorithme suivant) puis
envoie C à Alice par un canal qui n'a pas besoin d'être protégé
(par exemple, le courrier électronique). . Algorithme d'exponentiation modulaire rapide : Exponentiation_modulaire(entier a, entier e, entier n) : entier
Début
entier p (1
Tant que e>=1 faire
si e modulo 2 ? 0
p ( (p*a) modulo n
a ( (a*a) modulo n
e ( e / 2
fin si
fin faire
retourner p // résultat de ae modulo n
Fin
16. Le décryptage . Alice décode C en calculant Cd modulo n = (Me)d modulo n = M
. Démonstration :
On a ed = 1 modulo ?(n) avec ?(n)= (p-1)(q-1)
Donc il existe un entier k tel que ed = 1 + k(p-1)(q-1).
D'où, si M ( 0 modulo p : Med = M(Mp-1)k (q-1) modulo p
D'après le petit théorème de Fermat (que l'on retrouvera dans la
2ème partie) :
Si p est premier, Mp-1-1 est divisible par p i.e. Mp-1 = 1 modulo
p quelque soit M entier, premier à p (c'est le cas puisque M ( 0
modulo p)
D'où Med = M(1)k (q-1) modulo p et donc Med = M modulo p
Et enfin, si M=0 modulo p, on a bien Med = M modulo p. CQFD 4 Variantes 17. Coder le message et la signature : Les algorithmes à clé publique sont assez lents. La méthode
généralement utilisée pour envoyer un message volumineux, est de
tirer au hasard une clé secrète, chiffrer le message avec un
algorithme à clé privée en utilisant cette clé, puis chiffrer cette
clé aléatoire elle-même avec la clé publique du destinataire. Ceci
permet d'avoir la sécurité des systèmes à clé publique, avec la
performance des systèmes à clé privée. Il existe un logiciel qui
effectue toutes ces opérations et de manière transparente, et qui,
de plus, est gratuit et téléchargeable à partir de dizaines de sites
de par le monde : le célèbre PGP de Phil Zimmermann. (Il y a
d'autres logiciels aussi performants, mais PGP est sûrement le plus
connu.). Correctement utilisé, il est sûr, même contre les meilleurs
cryptanalystes du monde (c'est d'ailleurs pour cette raison que son
utilisation est formellement interdite en France). 18. Fonctionnement du PGP
Le PGP (Pretty Good Privacy) est un algorithme de chiffrement à
destination des particuliers. Il est surtout utilisé pour chiffrer
des messages envoyés par