Voir la source de Chiffrement RSA

{{Voir homonymes|RSA}}

[[Fichier:Ronald L Rivest photo.jpg|vignette|upright|Ronald Rivest (2015).]]
[[Fichier:Adi Shamir at TU Darmstadt (2013).jpg|vignette|upright|Adi Shamir (2013).]]
[[Fichier:Len-mankin-pic.jpg|vignette|upright|Leonard Adleman (2010).]]

Le '''chiffrement RSA''' (nommé par les initiales de ses trois inventeurs) est un [[Algorithmique|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é<ref name="brevet">{{en}} [http://v3.espacenet.com/textdoc?DB=EPODOC&IDX=US4405829 esp@cenet document view<!-- Titre généré automatiquement -->].</ref> par le [[Massachusetts Institute of Technology]] (MIT) en 1983 aux [[États-Unis]]. Le brevet a expiré le 21 septembre 2000.

== Fonctionnement général ==
{{article détaillé|Chiffrement asymétrique}}

Le [[chiffrement]] RSA est ''asymétrique'' : il utilise une paire de clés (des nombres entiers) composée d'une ''clé publique'' pour [[chiffrement|chiffrer]] et d'une ''clé privée'' pour [[chiffrement|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 [[signature|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 [[congruence sur les entiers|congruences sur les entiers]] et le [[petit théorème de Fermat]], pour obtenir des [[fonction à trappe|fonctions à trappe]].

Tous les calculs se font modulo un nombre entier ''n'' qui est le produit de deux [[nombre premier|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 chiffrement<ref>Par exemple {{harvsp|Menezes|van Oorschot|Vanstone|1996|loc=chap. 8, p. 287}}.</ref>. 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'{{lang|en|[[Optimal Asymmetric Encryption Padding]]}}).

=== 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 [[nombre premier|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'' [[Nombres premiers entre eux|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]], <math>\lambda(n)</math>, qui divise φ(''n''){{Référence souhaitée|date=17 mai 2021}}.

Le couple (''n'', ''e'') — ou (''e'', ''n'')<ref name=RSAp122/> — est la ''clé publique'' du chiffrement, alors que sa ''clé privée'' est<ref>{{harvsp|Menezes|van Oorschot|Vanstone|1996|loc=chap. 8, p. 286}} ; Schneier 1996, ''Applied Cryptography'', p. 467.</ref> 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'')<ref name=RSAp122>{{harvsp|Rivest|Shamir|Adleman|1978|p=122}}.</ref> ou le triplet (''p, q'', ''d'')<ref>Stinson 2006, ''Cryptography : Theory and Practice'', p. 175.</ref>).

=== Chiffrement du message ===
Si {{math|''M''}} est un [[entier naturel]] strictement inférieur à ''n'' représentant un message, alors le message chiffré sera représenté par
:<math> C\equiv M^e \pmod n,</math>
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
:<math>M\equiv C^d \pmod n.</math>

=== Exemple ===
Un exemple avec de petits nombres premiers (en pratique il faut de très grands nombres premiers<ref>{{Ouvrage|prénom1=Marc|nom1=Lipson|titre=Discrete mathematics|passage=472|éditeur=McGraw-Hill|date=2007|isbn=978-0-07-161586-0|isbn2=0-07-161586-5|oclc=837509096|lire en ligne=https://www.worldcat.org/oclc/837509096|consulté le=2022-06-08}}</ref>) :
# 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{{3}} ≡ 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{{7}} ≡ 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'' :
:<math>M^{p-1} \equiv 1 \pmod p\ ,\ \ M^{q-1} \equiv 1 \pmod q.</math>
En effet
:<math>C^d \equiv (M^e)^d \equiv M^{ed} \pmod n.</math>
Or
:<math>ed \equiv 1 \pmod{(p-1)(q-1)}</math>

ce qui signifie qu'il existe un entier ''k tel que''
:<math>ed = 1 + k(p-1)(q-1)</math>
donc, si ''M'' n'est pas multiple de ''p'' d'après le petit théorème de Fermat
: <math> 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</math>
et de même, si ''M'' n'est pas multiple de ''q''
:<math> M^{ed}\equiv M \pmod q.</math>
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 <math>M^{ed} - M</math> 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 d'Euclide#Lien entre PGCD et PPCM|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 (théorie des groupes)|ordre du groupe]] des éléments inversibles de l’[[anneau ℤ/nℤ]]. Ceci permet de voir immédiatement, par le [[théorème d'Euler (arithmétique)|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'')
: <math> M^{ed} \equiv M^{1+k \varphi(n)}\equiv M \pmod n</math>
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''{{sfn|Demazure|2008|p=63|loc=proposition 2.19}} (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]]<ref>{{harvsp|Menezes|van Oorschot|Vanstone|1996}}, chap 4.</ref> ou une variante<ref>Voir les recommandations du [[NIST]], décrites dans le standard [http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf FIPS 186-4], p. 69-71.</ref>. 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 [[Vulnérabilité (informatique)|failles de sécurité]], les deux nombres premiers <math>p</math> et <math>q</math> choisis pour construire le couple de clés doivent satisfaire les propriétés suivantes<ref name = "boyer">{{Ouvrage|langue = français|auteur = Pascal Boyer|titre = Petit compagnon des nombres et de leurs applications|éditeur = Calvage et Mounet|pages totales = 648|année = 2019 | isbn = 978-2-916352-75-6|partie = VI. Cryptographie|numéro chapitre = 4.|titre chapitre = RSA|passage = 529-534}}.</ref>:
* <math>p</math> et <math>q</math> doivent être suffisamment grands pour que l'[[algorithme rho de Pollard]] ne puisse trouver le plus petit facteur ;
* <math>\delta = |p - q|</math> doit être grand car trouver un facteur de <math>pq</math> en testant tous les nombres entre <math>\sqrt{pq} - \delta</math> et <math>\delta</math> a une complexité <math>\mathcal{O}(\delta)</math> ;
* <math>p - 1</math> et <math>q - 1</math> ne doivent pas être [[Entier friable|friable]]s pour empêcher l'utilisation de l'[[Algorithme p-1 de Pollard|algorithme p – 1 de Pollard]] ; 
* <math>p + 1</math> et <math>q + 1</math> doivent avoir au moins un grand facteur premier pour éviter l'{{Lien|trad = Williams's p + 1 algorithm
|fr = Algorithme p + 1 de Williams| texte = algorithme de factorisation de Williams}} ;
* 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 <math>e</math> choisi doit quant à lui vérifier les propriétés suivantes<ref name = "boyer"/>:
* Deux utilisateurs différents ne doivent pas utiliser le même module <math>n</math> avec des exposants <math>e_1</math> et <math>e_2</math> distincts car un message envoyé simultanément aux deux destinataires peut être déchiffré ;
* <math>e</math> doit être suffisamment grand pour éviter l'attaque de Håstad {{infra|Attaque de Håstad}} ;
* <math>e</math> doit être tel que le <math>d</math> associé soit supérieur à <math>\frac{1}{3}n^{\frac{1}{4}}</math> pour éviter l'[[attaque de Wiener]].

=== Chiffrer et déchiffrer ===
Le calcul de <math>\scriptstyle M = C^d \mod{n}</math> ne peut se faire en calculant d'abord <math>C^d</math>, 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 [[cryptographie|chiffrement]] de ces données numériques. RSA étant un algorithme de [[cryptographie asymétrique|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 [[Cryptographie symétrique|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.

Ce dernier est en fait intégré dans un mécanisme RSA. En effet, le problème des algorithmes symétriques est qu'il faut être sûr que la clé de chiffrement ne soit divulguée qu'aux personnes qui veulent partager un secret. RSA permet de communiquer cette clé symétrique de manière sûre. Pour ce faire, Alice va tout d'abord choisir une clé symétrique. Voulant échanger un secret avec Bob elle va lui transmettre cette clé symétrique en utilisant RSA. Elle va, pour cela, chiffrer la clé symétrique avec la clé publique (RSA) de Bob, ainsi elle sera sûre que seul Bob pourra déchiffrer cette clé symétrique. Une fois que Bob reçoit le message, il le déchiffre et peut alors utiliser la clé symétrique définie par Alice pour lui envoyer des messages chiffrés que seuls lui et Alice pourront alors déchiffrer.

== Sécurité ==
{{section à sourcer|date=avril 2017}}

=== Robustesse et failles possibles ===
Il faut distinguer les [[Attaque par force brute|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<ref name = "boyer"/>:
# « casser » RSA de cette manière nécessite la [[Décomposition en produit de facteurs premiers|factorisation]] du nombre ''n'' en le produit initial des nombres ''p'' et ''q'',
# 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 {{date-|2 décembre 2019}}, le plus grand nombre factorisé par ce moyen, en utilisant une méthode de calculs distribués, était long de {{unité|795|[[Bit (informatique)|bits]]}}. Les clés RSA sont habituellement de longueur comprise entre {{formatnum:1024}} et {{unité|2048|bits}}. Quelques experts croient possible que des clés de {{unité|1024|bits}} seront cassées dans un proche avenir (bien que ce soit controversé{{référence nécessaire}}), mais peu voient un moyen de casser de cette manière des clés de {{unité|4096|bits}} dans un avenir prévisible{{référence nécessaire}}. 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 à {{nobr|256 bits}} en quelques minutes sur un ordinateur individuel, en utilisant des logiciels librement disponibles<ref>[http://www.parlonssecurite.com/factoriser-cracke-une-cle-rsa/ Tutoriel sur le déchiffrement de clé privée].</ref>. Pour une taille allant jusqu'à {{nobr|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 {{unité|2048|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 [[Calculateur quantique|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<ref name = "gbm">{{Ouvrage|langue = français|titre = Arithmétique et cryptologie|auteur = Gilles Bailly-Maitre|éditeur = [[Éditions Ellipses|Ellipses]]|numéro édition = 2|isbn = 9782340046191|année = 2020|pages totales = 317|partie = III - Cryptologie moderne|numéro chapitre = 9|titre chapitre = Cryptographie à clé publique|passage = 216 - 220 et 223 - 225}}.</ref>.

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.

=== Attaques ===
Plusieurs attaques ont été proposées pour casser le chiffrement RSA<ref>Voir {{article|lang=en
 | lire en ligne = http://crypto.stanford.edu/~dabo/abstracts/RSAattack-survey.html
 | nom = Boneh | prénom = Dan  | lien auteur = Dan Boneh
 | titre = Twenty Years of attacks on the RSA Cryptosystem
 | périodique =[[Notices of the American Mathematical Society|Notices Amer. Math. Soc.]]
 | volume = 46 | numéro = 2
 | passage = 203-213 | année = 1999
}}.</ref>.

==== Attaque de Wiener ====
L'[[attaque de Wiener]] (1989) est exploitable si l'exposant secret {{math|''d''}} est inférieur à <math>\frac{1}{3}n^{\frac{1}{4}}</math><ref>{{Lien web|langue=Français|titre=Techniques de cryptanalyse de RSA|url=ftp://ftp.irisa.fr/local/caps/DEPOTS/BIBLIO2009/Grenier_Christophe.pdf|site=irisa.fr|date=28 janvier 2009|consulté le=21 janvier 2016}}.</ref>. On peut retrouver dans ce cas l'exposant secret à l'aide du développement en fractions continues de <math>\frac{e}{n}</math><ref name="wiener">http://www3.sympatico.ca/wienerfamily/Michael/MichaelPapers/ShortSecretExponents.pdf.</ref>{{,}}<ref name = "boyer"/>.

==== Attaque de Håstad ====
L'attaque de [[Johan Håstad|Håstad]], l'une des premières attaques découvertes (en 1985), repose sur la possibilité que l'exposant public {{math|''e''}} soit suffisamment petit. En interceptant le même message envoyé à au moins <math>e</math> destinataires différents, il est possible de retrouver le message originel à l'aide du [[théorème des restes chinois]]<ref>
{{chapitre|lang=en
 | prénom = Johan | nom = Håstad
 | titre chapitre = On using RSA with low exponent in a public key network
 | titre ouvrage = Advances in Cryptology – CRYPTO’85, Lecture Notes in Computer Science
 | volume =  218
 | éditeur = Springer
 | passage = 403-408
}}.</ref>{{,}}<ref name = "boyer"/>.

==== Attaque par chronométrage (''timing attacks'') ====
[[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 clé 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]] ([[Transport Layer Security|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 <math>\scriptstyle C^d \pmod n</math>, Alice choisit d'abord une valeur aléatoire secrète ''r'' et calcule <math>\scriptstyle (r^e C)^d \pmod n</math>. Le résultat de ce calcul est <math>\scriptstyle r M \pmod n</math> et donc l'effet de ''r'' peut être annulé en multipliant par son inverse.

==== Attaque à chiffrés choisis (''Adaptive chosen ciphertext attacks'') ====
Tel que décrit dans cet article, RSA est un chiffrement déterministe, et ne peut donc pas être [[sécurité sémantique|sémantiquement sûr]]. Une contremesure est l’utilisation d’un [[Remplissage (cryptographie)|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<sup>e</sup> ≤ 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{{sfn|Bleichenbacher|1998}}. En raison de défauts dans le schéma de remplissage [[PKCS]] #1 v1, il fut capable de récupérer des clés de session [[Transport Layer Security|SSL]]. {{refnec|À la suite de ce travail, les cryptographes recommandent maintenant l'utilisation de méthodes de remplissage formellement sûres}}, telles que [[Optimal Asymmetric Encryption Padding|OAEP]], et les laboratoires RSA ont publié de nouvelles versions de [[PKCS]] #1 résistantes à ces attaques{{RFC|3447|auteur=RSA Laboratory|titre=Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography|ref=oui}}.

== Notes et références ==
{{Références}}

== Annexes ==
=== Bibliographie ===
* {{Ouvrage|auteur1=Douglas Stinson|titre=Cryptographie, théorie et pratique|éditeur=Vuibert|année=2003|numéro d'édition=2|libellé=Stinson 2003}}
* {{Ouvrage|langue=fr|langue originale=en|auteur1=Bruce Schneier|lien auteur1=Bruce Schneier|titre=Cryptographie appliquée|sous-titre=protocoles, algorithmes et codes source en C|éditeur=Vuibert|lieu=Paris|année=2001|numéro d'édition=2|pages totales=846|isbn=2-7117-8676-5|libellé=Schneier 2001}}
* {{Ouvrage|langue=fr|auteur1=Pierre Barthélemy|auteur2=Robert Rolland|auteur3=Pascal Véron|auteur4=Hermes Lavoisier|titre=Cryptographie, principes et mises en œuvre|éditeur=Hermès science publications|lieu=Paris|année=2005|pages totales=414|isbn=2-7462-1150-5|libellé=Barthélemy {{et al.}} 2005}}
* {{Ouvrage|auteur1=[[Michel Demazure]]|titre=Cours d'algèbre. Primalité Divisibilité. Codes|année=2008|libellé=Demazure 2008|référence simplifiée=Référence:Cours d'algèbre (Demazure)}}
* {{article|auteur=Daniel Bleichenbacher|année=1998|titre=Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1|langue=en|doi=10.1007/BFb0055716|périodique=Crypto|libellé=Bleichenbacher 1998}}
* {{article|langue=en|auteur1=Ronald Rivest|auteur2=Adi Shamir|auteur3=Leonard Adleman|année=1978|périodique=Communications of the ACM|volume=21|numéro=2|pages=120–126|lire en ligne=http://people.csail.mit.edu/rivest/pubs/RSA78.pdf|format=PDF|titre=A method for obtaining digital signatures and public-key cryptosystems|libellé=Rivest, Shamir et Adleman 1978}}
* {{Ouvrage|langue=en|prénom1=Alfred J.|nom1=Menezes|lien auteur1=Alfred Menezes|prénom2=Paul C.|nom2=van Oorschot|prénom3=Scott A.|nom3=Vanstone|lien auteur3=Scott Vanstone|titre=Handbook of Applied Cryptography|éditeur=CRC Press|lieu=Boca Raton|année=1996|pages totales=780|pages=816|isbn=0-8493-8523-7|lire en ligne=http://cacr.uwaterloo.ca/hac/|libellé=Menezes, van Oorschot et Vanstone 1996}}

=== Articles connexes ===
* [[Authentification]]
* [[Signature numérique]]
* [[Digital Signature Algorithm]] (DSA)
* [[Compétition de factorisation RSA]] (Défi RSA)
* [[Nombre RSA]]


{{Palette|Défi RSA}}
{{Portail|cryptologie}}

[[Catégorie:Algorithme de cryptographie asymétrique]]
[[Catégorie:Défi RSA|*]]
[[Catégorie:Protocole cryptographique]]