Chiffrement RSA

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

1. Choisir p et q, deux nombres premiers distincts ;
2. calculer leur produit n = pq, appelé module de chiffrement ;
3. calculer φ(n) = (p - 1)(q - 1) (c'est la valeur de l'indicatrice d'Euler en n) ;
4. choisir un entier naturel e premier avec φ(n) et strictement inférieur à φ(n), appelé exposant de chiffrement ;
5. 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, ${\displaystyle \lambda (n)}$, qui divise φ(n).

Le couple (n, e) — ou (e, n)[3] — est la clé publique du chiffrement, alors que sa clé privée est[4] le nombre d, sachant que l'opération de déchiffrement ne demande que la clef 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)[3] ou le triplet (p, q, d)[5]).

Si M est un entier naturel strictement inférieur à n représentant un message, alors le message chiffré sera représenté par

${\displaystyle C\equiv M^{e}{\pmod {n}},}$

l'entier naturel C étant strictement inférieur à n.

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

${\displaystyle M\equiv C^{d}{\pmod {n}}.}$

Un exemple avec de petits nombres premiers (en pratique il faut de très grands nombres premiers[6]) :

1. on choisit deux nombres premiers p = 3, q = 11 ;
2. leur produit n = 3 × 11 = 33 est le module de chiffrement ;
3. φ(n) = (3 – 1) × (11 – 1) = 2 × 10 = 20 ;
4. on choisit e= 3 (premier avec 20) comme exposant de chiffrement ;
5. 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.

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 :

${\displaystyle M^{p-1}\equiv 1{\pmod {p}}\ ,\ \ M^{q-1}\equiv 1{\pmod {q}}.}$

En effet

${\displaystyle C^{d}\equiv (M^{e})^{d}\equiv M^{ed}{\pmod {n}}.}$

Or

${\displaystyle ed\equiv 1{\pmod {(p-1)(q-1)}}}$

ce qui signifie qu'il existe un entier k tel que

${\displaystyle ed=1+k(p-1)(q-1)}$

donc, si M n'est pas multiple de p d'après le petit théorème de Fermat

${\displaystyle M^{ed}\equiv M^{1+k(p-1)(q-1)}\equiv M\cdot \left(M^{p-1}\right)^{k(q-1)}\equiv M{\pmod {p}}}$

et de même, si M n'est pas multiple de q

${\displaystyle M^{ed}\equiv M{\pmod {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 ${\displaystyle M^{ed}-M}$ 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).

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.

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)

${\displaystyle M^{ed}\equiv M^{1+k\varphi (n)}\equiv M{\pmod {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[7] (la démonstration est essentiellement celle faite ci-dessus pour RSA, dans le cas particulier où n est un produit de deux nombres premiers).

Le couple de clefs 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[8] ou une variante[9]. Un tel test ne garantit pas exactement que le nombre soit premier, mais seulement une (très) forte probabilité qu'il le soit.

Pour éviter les failles de sécurité, les deux nombres premiers ${\displaystyle p}$ et ${\displaystyle q}$ choisis pour construire le couple de clefs doivent satisfaire les propriétés suivantes[10]:

• ${\displaystyle p}$ et ${\displaystyle q}$ doivent être suffisamment grands pour que l'algorithme rho de Pollard ne puisse trouver le plus petit facteur ;
• ${\displaystyle \delta =|p-q|}$ doit être grand car trouver un facteur de ${\displaystyle pq}$ en testant tous les nombres entre ${\displaystyle {\sqrt {pq}}-\delta }$ et ${\displaystyle \delta }$ a une complexité ${\displaystyle {\mathcal {O}}(\delta )}$ ;
• ${\displaystyle p-1}$ et ${\displaystyle q-1}$ ne doivent pas être friables pour empêcher l'utilisation de l'algorithme p – 1 de Pollard ;
• ${\displaystyle p+1}$ et ${\displaystyle q+1}$ doivent avoir au moins un grand facteur premier pour éviter l'algorithme de factorisation de Williams (en) ;
• 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 ${\displaystyle e}$ choisi doit quant à lui vérifier les propriétés suivantes[10]:

• Deux utilisateurs différents ne doivent pas utiliser le même module ${\displaystyle n}$ avec des exposants ${\displaystyle e_{1}}$ et ${\displaystyle e_{2}}$ distincts car un message envoyé simultanément aux deux destinataires peut être déchiffré ;
• ${\displaystyle e}$ doit être suffisamment grand pour éviter l'attaque de Håstad (voir infra) ;
• ${\displaystyle e}$ doit être tel que le ${\displaystyle d}$ associé soit supérieur à ${\displaystyle {\frac {1}{3}}N^{\frac {1}{4}}}$ pour éviter l'attaque de Wiener.

Le calcul de ${\displaystyle \scriptstyle M=c^{d}\mod {n}}$ ne peut se faire en calculant d'abord c^d, 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.

Il faut distinguer les attaques par la force brute, qui consistent à retrouver p et q sur la base de la connaissance de n uniquement, et les attaques sur la base de la connaissance de n mais aussi de la manière dont p et q ont été générés, du logiciel de cryptographie utilisé, d'un ou plusieurs messages éventuellement interceptés etc.

La sécurité de l'algorithme RSA contre les attaques par la force brute repose sur deux conjectures[10]:

1. « casser » RSA de cette manière nécessite la factorisation du nombre n en le produit initial des nombres p et q,
2. avec les algorithmes classiques, le temps que prend cette factorisation croît exponentiellement avec la longueur de la clé.

Il est possible que l'une des deux conjectures soit fausse, voire les deux. Jusqu'à présent, ce qui fait le succès du RSA est qu'il n'existe pas d'algorithme connu de la communauté scientifique pour réaliser une attaque force brute avec des ordinateurs classiques.

Le 2 décembre 2019, le plus grand nombre factorisé par ce moyen, en utilisant une méthode de calculs distribués, était long de 795 bits. Les clés RSA sont habituellement de longueur comprise entre 1 024 et 2 048 bits. Quelques experts croient possible que des clés de 1 024 bits seront cassées dans un proche avenir (bien que ce soit controversé), mais peu voient un moyen de casser de cette manière des clés de 4 096 bits dans un avenir prévisible. On peut néanmoins présumer que RSA reste sûr si la taille de la clé est suffisamment grande. On peut trouver la factorisation d'une clé de taille inférieure à 256 bits en quelques minutes sur un ordinateur individuel, en utilisant des logiciels librement disponibles[11]. Pour une taille allant jusqu'à 512 bits, et depuis 1999, il faut faire travailler conjointement plusieurs centaines d'ordinateurs. Par sûreté, il est couramment recommandé que la taille des clés RSA soit au moins de 2 048 bits.

Si une personne possède un moyen « rapide » de factoriser le nombre n, tous les algorithmes de chiffrement fondés sur ce principe seraient remis en cause ainsi que toutes les données chiffrées dans le passé à l'aide de ces algorithmes.

En 1994, un algorithme permettant de factoriser les nombres en un temps non exponentiel a été écrit pour les ordinateurs quantiques. Il s'agit de l'algorithme de Shor. Les applications des ordinateurs quantiques permettent théoriquement de casser le RSA par la force brute, ce qui a activé la recherche sur ce sujet ; mais actuellement ces ordinateurs génèrent des erreurs aléatoires qui les rendent inefficaces.

Les autres types d'attaques (voir ci-dessous), beaucoup plus efficaces, visent la manière dont les nombres premiers p et q ont été générés, comment e a été choisi, si l'on dispose de messages codés ou de toute autre information qui peut être utilisée. Une partie de la recherche sur ce sujet est publiée mais les techniques les plus récentes développées par les entreprises de cryptanalyse et les organismes de renseignement comme la NSA restent secrètes.

Il faut enfin noter que casser une clé par factorisation du nombre n ne nécessite pas d'attendre d'avoir un message chiffré à disposition. Cette opération peut débuter sur la base de la connaissance de la clé publique seulement, qui est généralement libre d'accès. Dans ces conditions, si n est factorisé, la clé privée s'en déduit immédiatement. Les conséquences de cette observation sont également qu'un code peut être cassé avant même son utilisation.

Plusieurs attaques ont été proposées pour casser le chiffrement RSA[12].

L'attaque de Wiener (1989) est exploitable si l'exposant secret d est inférieur à ${\displaystyle {\frac {1}{3}}N^{\frac {1}{4}}}$[13]. On peut retrouver dans ce cas l'exposant secret à l'aide du développement en fractions continues de ${\displaystyle {\frac {e}{N}}}$[14] - [10].

L'attaque de Håstad, l'une des premières attaques découvertes (en 1985), repose sur la possibilité que l'exposant public e soit suffisamment petit. En interceptant le même message envoyé à au moins ${\displaystyle e}$ destinataires différents, il est possible de retrouver le message originel à l'aide du théorème des restes chinois[15] - [10].

Paul Kocher a décrit en 1995 une nouvelle attaque contre RSA : en supposant que l’attaquante Ève en connaisse suffisamment sur les documents d'Alice et soit capable de mesurer les temps de déchiffrement de plusieurs documents chiffrés, elle serait en mesure d’en déduire rapidement la clef de déchiffrement. Il en irait de même pour la signature.

En 2003, Boneh et Brumley ont montré une attaque plus pratique permettant de retrouver la factorisation RSA sur une connexion réseau (SSL) en s’appuyant sur les informations que laissent filtrer certaines optimisations appliquées au théorème des restes chinois. Une façon de contrecarrer ces attaques est d'assurer que l'opération de déchiffrement prend un temps constant. Cependant, cette approche peut en réduire significativement la performance. C'est pourquoi la plupart des implémentations (mises en œuvre) RSA utilisent plutôt une technique différente connue sous le nom d'« aveuglement cryptographique » (blinding).

L'aveuglement se sert des propriétés multiplicatives de RSA en insérant dans le calcul une valeur secrète aléatoire dont l'effet peut être annulé. Cette valeur étant différente à chaque chiffrement, le temps de déchiffrement n'est plus directement corrélé aux données à chiffrer, ce qui met en échec l'attaque par chronométrage : au lieu de calculer ${\displaystyle \scriptstyle c^{d}{\pmod {n}}}$, Alice choisit d'abord une valeur aléatoire secrète r et calcule ${\displaystyle \scriptstyle (r^{e}c)^{d}{\pmod {n}}}$. Le résultat de ce calcul est ${\displaystyle \scriptstyle rm{\pmod {n}}}$ et donc l'effet de r peut être annulé en multipliant par son inverse.

Tel que décrit dans cet article, RSA est un chiffrement déterministe, et ne peut donc pas être sémantiquement sûr. Une contremesure est l’utilisation d’un schéma de remplissage probabiliste de manière telle qu'aucune valeur de message, une fois chiffré, ne donne un résultat peu sûr, par exemple si C = M^e ≤ N, une attaque simple est le calcul direct de la racine e-ième de C, qui n’aura pas été réduite modulo N.

En 1998, Daniel Bleichenbacher décrit la première attaque pratique de type « chiffré choisi adaptable » contre des messages RSA[16]. En raison de défauts dans le schéma de remplissage PKCS #1 v1, il fut capable de récupérer des clefs de session SSL. À la suite de ce travail, les cryptographes recommandent maintenant l'utilisation de méthodes de remplissage formellement sûres, telles que OAEP, et les laboratoires RSA ont publié de nouvelles versions de PKCS #1 résistantes à ces attaques[17].

• [Stinson 2003] Douglas Stinson, Cryptographie, théorie et pratique, Vuibert, 2003, 2^e éd.
• [Schneier 2001] Bruce Schneier (trad. de l'anglais), Cryptographie appliquée : protocoles, algorithmes et codes source en C, Paris, Vuibert, 2001, 2^e éd., 846 p. (ISBN 2-7117-8676-5)
• [Barthélemy et al. 2005] Pierre Barthélemy, Robert Rolland, Pascal Véron et Hermes Lavoisier, Cryptographie, principes et mises en œuvre, Paris, Hermès science publications, 2005, 414 p. (ISBN 2-7462-1150-5)
• [Demazure 2008] Michel Demazure, Cours d'algèbre. Primalité Divisibilité. Codes, 2008 [détail de l’édition]
• [Bleichenbacher 1998] (en) Daniel Bleichenbacher, « Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1 », Crypto,‎ 1998 (DOI 10.1007/BFb0055716)
• [Rivest, Shamir et Adleman 1978] (en) Ronald Rivest, Adi Shamir et Leonard Adleman, « A method for obtaining digital signatures and public-key cryptosystems », Communications of the ACM, vol. 21, n^o 2,‎ 1978, p. 120–126 (lire en ligne [PDF])
• [Menezes, van Oorschot et Vanstone 1996] (en) Alfred J. Menezes, Paul C. van Oorschot et Scott A. Vanstone, Handbook of Applied Cryptography, Boca Raton, CRC Press, 1996, 780 p. (ISBN 0-8493-8523-7, lire en ligne)

• Authentification
• Signature numérique
• Digital Signature Algorithm (DSA)
• Compétition de factorisation RSA (Défi RSA)
• Nombre RSA