Le cryptosystème RSA 2/2

Le cryptosystème RSA 2/2

1. Introduction

Le gros inconvénient des cryptosystèmes précédents (dits à clé symétrique) est caractérisé par le fait que la connaissance de la clé de chiffrement permet ipso facto de déchiffrer. Impossible alors de transmettre, par exemple, une clé sur internet afin de chiffrer sans que personne ne puisse la déchiffrer.

C'est ici qu'interviennent trois mathématiciens Ron RIVEST, Adi SHAMIR et Len ADELMAN. Ils ont mis au point le protocole cryptographique le plus utilisé de nos jours. Une différence notable est l'utilisation de deux clés de chiffrement distinctes, de telle sorte que, même une personne ayant chiffré à l'aide de la clé de chiffrement (dite publique) est dans l'incapacité de déchiffrer son propre message !

Il est possible de déchiffrer uniquement si l'on possède une seconde clé, dite publique. Ainsi ce type de chiffrement est dit à clé asymétrique. Cette petite différence fondamentale change tout. Il devient possible de transmettre une clé de chiffrement sur l'internet ou tout autre canal non sécurisé.

Imaginons qu'Alice ait un message à envoyer à Bob via internet sans qu'Oscar ne puisse en connaître le contenu. A l'aide du RSA, Bob crée un couple de clés publique/privé (A et B). Il diffuse sa clé publique sur le réseau, ainsi tout le monde peut la connaître et chiffrer un message. Alice peut ainsi chiffrer un message à l'aide de cette clé et le transmettre via l'internet. Étant donné qu'il est impossible de déchiffrer à l'aide de la clé publique, le contenu du message restera secret. Bob peut déchiffrer à l'aide de la clé privée qu'il est le seul à connaître. Mais «Oscar peut envoyer un message chiffré en se faisant passer pour Alice » me direz-vous ! Pour éviter ce problème il existe des protocoles de signature numérique (basés sur le ...RSA ).

2. Fiabilité

Comment peut-on avoir une clé (privée) quasi-indéterminable en ayant une clé distribuée à tous ? C'est l'objet principal de cet article...

Est-ce fiable ?

Il est possible de répondre partiellement à cette question par un petit exemple. En 1977 un mathématicien coda la phrase « The magic words are squeamish ossifrage » (Les mots magiques sont orfraie dégoutée) à l'aide du RSA. Il défia le monde de le déchiffrer. Bien entendu la communauté scientifique étant friande de ce type d'énigme s'organisa, regroupant d'immenses réseaux d'ordinateurs et supercalculateurs d'universités célèbres, afin de partager le travail. Malgré cette profusion de moyens et d'énergie, il aura fallu 17 ans pour que le message soit déchiffré. Pourtant les nombres utilisés étaient de l'ordre de 10^60 (^ signifiant puissance), ce qui peut paraître grand mais de nos jours des nombres de l'ordre 10^350 (soit 10^700 si l'on en multiplié 2) sont utilisés pour les échanges sur internet, le codage des codes de carte bancaire ... Ainsi même en utilisant la puissance de millions d'ordinateurs parmi les plus puissants, la cryptanalyse par la force brute, de ce type de code se compte en millions d'années.

Pour aller encore plus loin, les nombres les plus grands que nous connaissons demanderaient pour être « cassés » un temps plus grand que l'age de l'univers...

Les seuls ordinateurs capables de telles prouesses sont les ordinateurs à états quantiques qui n'existent pas encore …. et n'existeront peut être jamais !

3. Une histoire de nombres premiers

Bien entendu il existe une limite à la taille des clés, limite sans cesse repoussée et dont les enjeux sont colossaux.

Pour rappel un nombre premier (dans la structure (N,+,.), N étant l'ensemble des entiers naturels) est un nombre divisible uniquement par lui-même et par un. Ainsi 0 n'est pas premier car non divisible par 0 et 1 n'est pas considéré comme premier car il n'a qu'un seul diviseur.

Schématiquement, RSA est basé sur la factorisation de deux nombres premiers. Ou plus précisément l'impossibilité pratique en connaissant un nombre « n » de le factoriser en deux entiers premiers « p » et « q » tels que « n=p.q ».

Mais comment ca ? Factoriser c'est facile pensez-vous (peut être ;-) ). Un exemple étant plus parlant, essayez de décomposer 15 en deux facteurs premiers. 5*3 = 15 me direz-vous. Comment êtes-vous parvenus à ce résultat ? Quelle est la démarche vous ayant permis de trouver instantanément la solution ? La réponse est simple vous avez simplement appris vos tables de multiplication par cœur. Maintenant essayez avec 143.

143 = 11*13, là c'est un peu moins rapide, puis 8051

8051 = 83*97 là il vous faut déjà essayer pas mal de combinaisons et il faut aussi savoir que 83 et 97 sont premiers.

Comment faire ? Comment déterminer à coup sûr la primalité d'un nombre sans en tester trop? Répondre de manière formelle à cette question ferait de vous un homme très riche.

On comprend mieux la nécessité de trouver toujours plus de nombres premiers toujours plus grands. Il en existe une infinité (le prouver formellement sortirait largement du carde de cet article) et on ne trouve aucune « règle », aucun algorithme « raisonnable » capable de savoir si un nombre est premier. Par « raisonnable » on entend algorithme en temps polynomial (dont la fonction du temps est du type ax^0+bx^1+...+cx^n).

Pour l'anecdote le plus grand nombre premier connu à ce jour comporte près de 13 millions de chiffres !

4. Les pré-requis mathématiques

Le lecteur allergique aux maths pourra sauter cette section.

Comprendre comment on détermine les clés nécessite quelques pré-requis. Dans un soucis de lisibilité et pour ne pas alourdir l'article les preuves et démonstrations seront omises.

Le théorème chinois des restes.

Ce théorème assure l'existence et l'unicité d'une classe modulaire étant solution d'un système d'équations congruentielles.

La fonction indicatrice d'Euler

Inversibilité :

L'inversibilité demanderait (comme beaucoup des notions abordées ici) un article complet. Un exemple étant plus parlant qu'un long discours.

Soit l'ensemble {-3,-2,-1,0,1,2,3} et l'opération d'addition « + », le nombre 0 est l'élément neutre, et tous les éléments sont inversibles car « un élément »+ « un autre élément » = « l'élément neutre ».

ainsi :

-3+3=0

-2+2=0

-1+1=0

0+0=0

donc tous les éléments sont inversibles.

Dans un corps Z/nZ, (Obligatoirement avec n premier) tous les éléments sont inversibles par « . ».

Le nombre de ces éléments noté Phi(n) est appelé fonction indicatrice d'Euler.

Les propriétés d'inversibilité des éléments de ce corps sont très importantes et utiles, les clés RSA sont prises parmi ces valeurs.

L'algorithme d'Euclide étendu.

Cet algorithme, que nous ne détaillerons pas ici, permet conceptuellement de déterminer un couple de coefficients de Bezout. Ainsi à l'aide de l'un des éléments de Phi(n), connaissant n, il est possible de déterminer son inverse. Dit autrement connaissant, n et l'une des deux clés, il est possible de déterminer l'autre.

5. Le RSA

Prenons deux nombres premiers très grands que nous appellerons « p » et « q ».

Multiplions « p » par « q » nous obtenons n = p.q.

Déjà, comme nous l'avons vu plus haut, il est très difficile, voire humainement impossible, de retrouver p et q à partir de n (pour des nombres suffisamment grands).

Nous avons Phi(n), le nombre de nombres premiers avec n qu'il est facile de déterminer à l'aide de la formule Phi(n) = (p-1)(q-1). Nous constatons que trouver Phi(n) sans p et q pose problème...

Afin de déterminer une clé (par exemple la publique) nous devons prendre une nombre « a » tel que ce nombre soit premier avec Phi(n), c'est à dire tel que le pgcd(Phi(n),a) = 1.

A l'aide de l'algorithme d'Euclide étendu nous pouvons déterminer un second nombre « b », inverse de « a » modulo Phi(n). Et oui souvenez-vous de la notion de congruence du chapitre 1 ;-) .

c'est à dire que a.b = 1 modulo(Phi(n))

Voilà, nous avons notre couple de clés a et b.

6. Chiffrement déchiffrement

Nous avons vu que tout message peut se ramener à un (ou plusieurs) nombre(s). Considérons alors le message x. Pour le chiffrer, il suffit de calculer x^a (mod n), soit x puissance a modulo n, appelons ce résultat « y ».

Nous pouvons vérifier (sur l'exemple suivant) qu'il est impossible de retrouver le nombre original sans la clé b.

Pour déchiffrer on effectue l'opération y^b (mod n).

Bien entendu vu la longueur des clés, calculer de telles nombres nécessite une bonne puissance de calcul, mais à l'aide de techniques d'exponentiation rapides, permettant de simplifier le calcul, c'est tout à fait à la portée de nos ordinateurs.

6. Un petit exemple simplifié

Si ces explications vous ont parues un peu obscures, un petit exemple très simplifié permettra d'y voir plus clair.

Prenons deux nombres premiers p=101 et q=113.

Calculer n est facile n=101*113=11413.

Attaquons nous maintenant à Phi(n), pour rappel il s'agit du nombre de nombres premiers avec n.

Phi(n)=(p-1)(q-1)=100*112=11200 soit 2^6 * 5^2 * 7

La clé a doit être choisie de telle sorte que le pgcd(Phi(n),a) = 1, donc « a » ne doit pas être multiple de 2,5 ou 7.

Prenons a=3533 (modulo Phi(n)).

L'algorithme d'Euclide étendu nous permet de trouver b= 6597(modulo Phi(n)).

Imaginons que notre message à coder soit x=10789.

Codons ce message, x^a = 10789^3533 = 4600 (modulo 11413)

Si nous essayons de déchiffrer avec la même clé nous avons 4600^3533 = 9482 (modulo 11413) ce qui ne correspond pas à notre message qui est 10789.

Si nous essayons de déchiffrer à l'aide de la clé privée « b » : 4600^6597= 10789 (modulo 11413). Le message est déchiffré

Votre calculatrice de poche ne pouvant peut-être pas procéder à de tels calculs le site suivant permet des calculs en exponentiation rapide : http://www.math.umn.edu/~garrett/crypto/a01/FastPow.html

7. implications - conclusion

La puissance de calcul nécessaire pour chiffrer en RSA étant relativement importante, ce cryptosystème est rarement utilisé tel quel, il est plus souvent mis en œuvre pour de petites quantités de données, des signatures numériques ou encore pour crypter des clés symétriques d'autres protocoles de cryptographie. Ainsi PGP, système libre et ouvert utilise un chiffrement à clé symétrique dont la clé est chiffré en RSA.

La recherche est autant active que secrète sur ce sujet passionnant qu'est la cryptologie (ensemble constitué de la cryptanalyse et de la cryptographie). Les services de renseignement de tous les pays riches y travaillent activement.

Le RSA étant breveté, le service de sécurité intérieur des états unis (NSA), a durant longtemps essayé de bloquer sa diffusion. Depuis 1999 un arrêt de la cour suprême des États Unis a permis de démocratiser son utilisation. Cependant l'usage de tels procédés reste interdit dans bon nombre de pays car les services secrets ne parviennent pas (officiellement) à déchiffrer ces messages. La cryptographie est toujours un enjeu majeur, considéré comme un arme tant dans le domaine militaire qu'économique.

De nombreuses personnes dans le monde travaillent à la cryptanalyse (afin de le « casser ») du RSA. S'il est avéré qu'il est illusoire de le casser en utilisant la « force brute » (un test exhaustif de toutes les possibilités), d'autres voies sont explorées. Il convient de rappeler que notre connaissance sur les nombres premiers est parcellaire et qu'un particulier ne peut pas générer tout seul une clé à plusieurs millions de chiffres. La distribution des clés étant assurée par un nombre limité d'intervenants.