vignette|upright|Ronald Rivest (2015). vignette|upright|Adi Shamir (2013). vignette|upright|Leonard Adleman (2010).
Le chiffrement RSA (nommé par les initiales de ses trois inventeurs) est un algorithme de cryptographie asymétrique, très utilisé dans le commerce électronique, et plus généralement pour échanger des données confidentielles sur Internet. Cet algorithme a été décrit en 1977 par Ronald Rivest, Adi Shamir et Leonard Adleman. RSA a été breveté esp@cenet document view. par le Massachusetts Institute of Technology (MIT) en 1983 aux États-Unis. Le brevet a expiré le 21 septembre 2000.
Fonctionnement général
Le chiffrement RSA est asymétrique : il utilise une paire de clés (des nombres entiers) composée d'une clé publique pour chiffrer et d'une clé privée pour déchiffrer des données confidentielles. Les deux clés sont créées par une personne, souvent nommée par convention Alice, qui souhaite que lui soient envoyées des données confidentielles. Alice rend la clé publique accessible. Cette clé est utilisée par ses correspondants (Bob, etc.) pour chiffrer les données qui lui sont envoyées. La clé privée est quant à elle réservée à Alice, et lui permet de déchiffrer ces données. La clé privée peut aussi être utilisée par Alice pour signer une donnée qu'elle envoie, la clé publique permettant à n'importe lequel de ses correspondants de vérifier la signature.
Une condition indispensable est qu'il soit « calculatoirement impossible » de déchiffrer à l'aide de la seule clé publique, en particulier de reconstituer la clé privée à partir de la clé publique, c'est-à-dire que les moyens de calcul disponibles et les méthodes connues au moment de l'échange (et le temps que le secret doit être conservé) ne le permettent pas.
Le chiffrement RSA est souvent utilisé pour communiquer une clé de chiffrement symétrique, qui permet alors de poursuivre l'échange de façon confidentielle : Bob envoie à Alice une clé de chiffrement symétrique qui peut ensuite être utilisée par Alice et Bob pour échanger des données.
Fonctionnement détaillé Ronald Rivest, Adi Shamir et Leonard Adleman ont publié leur chiffrement en 1978 dans A Method for Obtaining Digital Signatures and Public-key Cryptosystems. Ils utilisent les congruences sur les entiers et le petit théorème de Fermat, pour obtenir des fonctions à trappe.
Tous les calculs se font modulo un nombre entier n qui est le produit de deux nombres premiers. Le petit théorème de Fermat joue un rôle important dans la conception du chiffrement.
Les messages clairs et chiffrés sont des entiers inférieurs à l'entier n servant de base au chiffrementPar exemple .. Les opérations de chiffrement et de déchiffrement consistent à élever le message à une certaine puissance modulo n (c'est l'opération d'exponentiation modulaire).
La seule description des principes mathématiques sur lesquels repose l'algorithme RSA n'est pas suffisante. Sa mise en œuvre concrète demande de tenir compte d'autres questions qui sont essentielles pour la sécurité. Par exemple le couple (clé privée, clé publique) doit être engendré par un procédé vraiment aléatoire qui, même s'il est connu, ne permet pas de reconstituer la clé privée. Les données chiffrées ne doivent pas être trop courtes, pour que le déchiffrement demande vraiment un calcul modulaire, et complétées de façon convenable (par exemple par l').
Création des clés L'étape de création des clés est à la charge d'Alice. Elle n'intervient pas à chaque chiffrement car les clés peuvent être réutilisées. La difficulté première, que ne règle pas le chiffrement, est que Bob soit bien certain que la clé publique qu'il détient est celle d'Alice. Le renouvellement des clés n'intervient que si la clé privée est compromise, ou par précaution au bout d'un certain temps (qui peut se compter en années). Choisir p et q, deux nombres premiers distincts ; calculer leur produit n = pq, appelé module de chiffrement ; calculer φ(n) = (p - 1)(q - 1) (c'est la valeur de l'indicatrice d'Euler en n) ; choisir un entier naturel e premier avec φ(n) et strictement inférieur à φ(n), appelé exposant de chiffrement ; calculer l'entier naturel d, inverse modulaire de e pour la multiplication modulo φ(n) et strictement inférieur à φ(n), appelé exposant de déchiffrement ; d peut se calculer efficacement par l'algorithme d'Euclide étendu.
Comme e est premier avec φ(n), d'après le théorème de Bachet-Bézout il existe deux entiers d et k tels que ed = 1 + kφ(n), c'est-à-dire que ed ≡ 1 (mod φ(n)) : e est bien inversible modulo φ(n).
Dans tout le paragraphe précédent, on peut utiliser l’indicatrice de Carmichael, , qui divise φ(n).
Le couple (n, e) — ou (e, n) — est la clé publique du chiffrement, alors que sa clé privée est ; Schneier 1996, Applied Cryptography, p. 467. le nombre d, sachant que l'opération de déchiffrement ne demande que la clé privée d et l'entier n, connu par la clé publique (la clé privée est parfois aussi définie comme le couple (d, n). ou le triplet (p, q, d)Stinson 2006, Cryptography : Theory and Practice, p. 175.).
Chiffrement du message Si est un entier naturel strictement inférieur à n représentant un message, alors le message chiffré sera représenté par
l'entier naturel C étant strictement inférieur à n.
Déchiffrement du message Pour déchiffrer C, on utilise d, l'inverse de e modulo (p – 1)(q – 1), et l'on retrouve le message clair M par
Exemple Un exemple avec de petits nombres premiers (en pratique il faut de très grands nombres premiers) : on choisit deux nombres premiers p = 3, q = 11 ; leur produit n = 3 × 11 = 33 est le module de chiffrement ; φ(n) = (3 – 1) × (11 – 1) = 2 × 10 = 20 ; on choisit e= 3 (premier avec 20) comme exposant de chiffrement ; l'exposant de déchiffrement est d = 7, l'inverse de 3 modulo 20 (en effet ed = 3 × 7 ≡ 1 mod 20). La clé publique d'Alice est (n, e) = (33, 3), et sa clé privée est (n, d) = (33, 7). Bob transmet un message à Alice. Chiffrement de M = 4 par Bob avec la clé publique d'Alice : 4 ≡ 31 mod 33, le chiffré est C = 31 que Bob transmet à Alice ; Déchiffrement de C = 31 par Alice avec sa clé privée : 31 ≡ 4 mod 33, Alice retrouve le message initial M = 4. Le mécanisme de signature par Alice, à l'aide de sa clé privée, est analogue, en échangeant les clés.
Justification La démonstration repose sur le petit théorème de Fermat, à savoir que comme p et q sont deux nombres premiers, si M n'est pas un multiple de p on a la première égalité, et la seconde s'il n'est pas un multiple de q :
En effet
Or
ce qui signifie qu'il existe un entier k tel que
donc, si M n'est pas multiple de p d'après le petit théorème de Fermat
et de même, si M n'est pas multiple de q
Les deux égalités sont en fait réalisées pour n'importe quel entier M, car si M est un multiple de p, M et toutes ses puissances non nulles sont congrues à 0 modulo p. De même pour q.
L'entier est donc un multiple de p et de q, qui sont premiers distincts, donc de leur produit pq = n (on peut le voir comme une conséquence de l'unicité de la décomposition en facteurs premiers, ou plus directement du lemme de Gauss, sachant que p et q sont premiers entre eux, étant premiers et distincts).
Asymétrie On constate que pour chiffrer un message, il suffit de connaître e et n. En revanche pour déchiffrer, il faut d et n.
Pour calculer d à l'aide de e et n, il faut trouver l'inverse modulaire de e modulo (p – 1)(q – 1), ce que l'on ne sait pas faire sans connaître les entiers p et q, c'est-à-dire la décomposition de n en facteurs premiers.
Le chiffrement demande donc de pouvoir vérifier que de « très grands » nombres sont des nombres premiers, pour pouvoir trouver p et q, mais aussi que le produit de ces deux très grands nombres, ne soit pas factorisable pratiquement. En effet les algorithmes efficaces connus qui permettent de vérifier qu'un nombre n'est pas premier ne fournissent pas de factorisation.
Théorème d'Euler La valeur φ(n) de l'indicatrice d'Euler en n est l'ordre du groupe des éléments inversibles de l’anneau ℤ/nℤ. Ceci permet de voir immédiatement, par le théorème d'Euler (conséquence du théorème de Lagrange), que si M est premier avec n, donc inversible (ce qui est le cas de « la plupart » des entiers naturels M strictement inférieurs à n)
soit de justifier le chiffrement RSA (pour de tels M).
Il s'avère que quand n est un produit de nombres premiers distincts, l'égalité est vérifiée pour tout M (la démonstration est essentiellement celle faite ci-dessus pour RSA, dans le cas particulier où n est un produit de deux nombres premiers).
Implémentation Engendrer les clés Le couple de clés demande de choisir deux nombres premiers de grande taille, de façon qu'il soit calculatoirement impossible de factoriser leur produit.
Pour déterminer un nombre premier de grande taille, on utilise un procédé qui fournit à la demande un entier impair aléatoire d'une taille suffisante, un test de primalité permet de déterminer s'il est ou non premier, et on s'arrête dès qu'un nombre premier est obtenu. Le théorème des nombres premiers assure que l'on trouve un nombre premier au bout d'un nombre raisonnable d'essais.
La méthode demande cependant un test de primalité très rapide. En pratique on utilise un test probabiliste, le test de primalité de Miller-Rabin, chap 4. ou une varianteVoir les recommandations du NIST, décrites dans le standard FIPS 186-4, p. 69-71.. Un tel test ne garantit pas exactement que le nombre soit premier, mais seulement une (très) forte probabilité qu'il le soit.
Propriétés requises Pour éviter les failles de sécurité, les deux nombres premiers et choisis pour construire le couple de clés doivent satisfaire les propriétés suivantes.: et doivent être suffisamment grands pour que l'algorithme rho de Pollard ne puisse trouver le plus petit facteur ; doit être grand car trouver un facteur de en testant tous les nombres entre et a une complexité ; et ne doivent pas être friables pour empêcher l'utilisation de l'algorithme p – 1 de Pollard ; et doivent avoir au moins un grand facteur premier pour éviter l' ; Deux utilisateurs différents doivent générer des nombres premiers différents pour empêcher une attaque par calcul de PGCD des différentes clés.
L'exposant choisi doit quant à lui vérifier les propriétés suivantes: Deux utilisateurs différents ne doivent pas utiliser le même module avec des exposants et distincts car un message envoyé simultanément aux deux destinataires peut être déchiffré ; doit être suffisamment grand pour éviter l'attaque de Håstad ; doit être tel que le associé soit supérieur à pour éviter l'attaque de Wiener.
Chiffrer et déchiffrer Le calcul de ne peut se faire en calculant d'abord , puis le reste modulo n, car cela demanderait de manipuler des entiers beaucoup trop grands. Il existe des méthodes efficaces pour le calcul de l'exponentiation modulaire.
On peut conserver une forme différente de la clé privée pour permettre un déchiffrement plus rapide à l'aide du théorème des restes chinois.
Applications Lorsque deux personnes souhaitent s'échanger des informations numériques de façon confidentielle, sur Internet par exemple avec le commerce électronique, celles-ci doivent recourir à un mécanisme de chiffrement de ces données numériques. RSA étant un algorithme de chiffrement asymétrique, celui-ci hérite du domaine d'application de ces mécanismes de chiffrement. On citera : l'authentification des parties entrant en jeu dans l'échange d'informations chiffrées avec la notion de signature numérique ; le chiffrement des clés symétriques (nettement moins coûteuse en temps de calcul) utilisées lors du reste du processus d'échange d'informations numériques chiffrées.