RSA (cryptosystem) (Français)

utilisation de L’algorithme chinois restemodifier

pour plus d’efficacité de nombreuses bibliothèques cryptographiques populaires (telles que OpenSSL, Java et.NET) utilisent l’optimisation suivante pour le déchiffrement et la signature basée sur le théorème chinois restment. Les valeurs suivantes sont précalculées et stockées dans le cadre de la clé privée:

ces valeurs permettent au destinataire de calculer l’exponentiation m = cd (mod pq) plus efficacement comme suit:

c’est plus efficace que de calculer l’exponentiation par quadrature même si deux exponentiations modulaires doivent être calculées., La raison en est que ces deux exponentiations modulaires utilisent toutes deux un exposant plus petit et un module plus petit.

factorisation D’entiers et RSA problemEdit

la sécurité du cryptosystème RSA repose sur deux problèmes mathématiques: le problème de l’affacturage de grands nombres et le problème RSA. Le déchiffrement complet d’un texte chiffré RSA est considéré comme infaisable en supposant que ces deux problèmes sont difficiles, c’est-à-dire qu’aucun algorithme efficace n’existe pour les résoudre., Fournir une sécurité contre le déchiffrement partiel peut nécessiter l’ajout d’un schéma de remplissage sécurisé.

le problème RSA est défini comme la tâche de prendre des racines eth modulo un composite n: récupérer une valeur m telle que c me me (mod n), Où (n, e) est une clé publique RSA et c est un texte chiffré RSA. Actuellement, l’approche la plus prometteuse pour résoudre le problème RSA consiste à factoriser le module n. avec la possibilité de récupérer des facteurs premiers, un attaquant peut calculer l’exposant secret d à partir d’une clé publique (n, e), puis déchiffrer c en utilisant la procédure standard. , Pour ce faire, un attaquant factorise n en p et q et calcule lcm(p − 1, q − 1) qui permet la détermination de d à partir de e. Aucune Méthode en temps polynomial pour factoriser de grands entiers sur un ordinateur classique n’a encore été trouvée, mais il n’a pas été prouvé qu’aucune n’existe. Voir factorisation d’entiers pour une discussion de ce problème.

Le tamis quadratique polynomial Multiple (MPQS) peut être utilisé pour factoriser le module public N.,

la première factorisation RSA-512 en 1999 utilisait des centaines d’Ordinateurs et nécessitait l’équivalent de 8 400 années MIPS, sur une période d’environ sept mois. En 2009, Benjamin Moody pouvait factoriser une clé RSA-512 bits en 73 jours en utilisant uniquement des logiciels publics (GGNFS) et son ordinateur de bureau (un Athlon64 dual-core avec un processeur 1,900 MHz). Un peu moins de cinq gigaoctets de stockage sur disque ont été nécessaires et environ 2,5 gigaoctets de RAM pour le processus de tamisage.,

Rivest, Shamir et Adleman ont noté que Miller a montré que – en supposant la vérité de L’hypothèse de Riemann étendue – trouver d à partir de n et e est aussi difficile que de factoriser n en p et q (jusqu’à une différence de temps polynomiale). Cependant, Rivest, Shamir et Adleman ont noté, dans la section IX / D de leur article, qu’ils n’avaient pas trouvé de preuve que l’inversion de RSA est aussi difficile que l’affacturage.

en 2020, le plus grand nombre RSA factorisé connu du public était de 829 bits (250 chiffres décimaux, RSA-250). Sa factorisation, par une implémentation distribuée de pointe, a pris environ 2700 années CPU., En pratique, les clés RSA ont généralement une longueur de 1024 à 4096 bits. En 2003, RSA Security a estimé que les clés 1024 bits étaient susceptibles de devenir fissurables d’ici 2010. En 2020, on ne sait pas si de telles clés peuvent être fissurées, mais les recommandations minimales sont passées à au moins 2048 bits. On suppose généralement que RSA est sécurisé si n est suffisamment grand, en dehors de l’informatique quantique.

Si n est 300 bits ou moins, il peut être factorisé en quelques heures dans un ordinateur personnel, en utilisant un logiciel déjà disponible gratuitement., Les clés de 512 bits se sont avérées pratiquement cassables en 1999 lorsque RSA-155 a été factorisé en utilisant plusieurs centaines d’Ordinateurs, et ceux-ci sont maintenant factorisés en quelques semaines en utilisant du matériel commun. Les Exploits utilisant des certificats de signature de code 512 bits qui peuvent avoir été factorisés ont été signalés en 2011. Un dispositif matériel théorique nommé TWIRL, décrit par Shamir et Tromer en 2003, a remis en question la sécurité des clés 1024 bits.,

en 1994, Peter Shor a montré qu’un ordinateur quantique – si jamais on pouvait créer pratiquement à cet effet – serait capable de factoriser en temps polynomial, brisant RSA; voir l’algorithme de Shor.

Faulty key generationEdit

trouver les grands nombres premiers p et q se fait généralement en testant des nombres aléatoires de taille correcte avec des tests de primalité probabilistes qui éliminent rapidement

Les Nombres p et q ne doivent pas être « trop proches », de peur que la factorisation de Fermat pour n ne réussisse., Si p − q est inférieur à 2N1 / 4 (n = p * q, Qui même pour de petites valeurs de 1024 bits de n est 3×1077) résoudre pour p et q est trivial. De plus, si p − 1 ou q − 1 n’a que de petits facteurs premiers, n peut être factorisé rapidement par L’algorithme P − 1 de Pollard, et donc de telles valeurs de p ou q doivent être ignorées.

Il est important que l’exposant Privé d soit suffisamment grand. Michael J. Wiener a montré que si p est entre q et 2Q (ce qui est assez typique) et d < n1/4/3, alors d peut être calculé efficacement à partir de n et E.,

Il n’y a pas d’attaque connue contre de petits exposants publics tels que e = 3, à condition que le remplissage approprié soit utilisé. L’attaque de Coppersmith a de nombreuses applications pour attaquer RSA spécifiquement si l’exposant public e est petit et si le message crypté est court et non rembourré. 65537 est une valeur couramment utilisée pour e; cette valeur peut être considérée comme un compromis entre éviter les attaques potentielles de petits exposants et permettre des chiffrages efficaces (ou vérification de signature)., La Publication spéciale du NIST sur la sécurité informatique (SP 800-78 Rev 1 d’août 2007) n’autorise pas les exposants publics e inférieurs à 65537, mais n’indique pas de raison pour cette restriction.

en octobre 2017, une équipe de chercheurs de L’Université Masaryk a annoncé la vulnérabilité ROCA, qui affecte les clés RSA générées par un algorithme incorporé dans une bibliothèque D’Infineon connue sous le nom de RSALib. Un grand nombre de cartes à puce et de modules de plate-forme de confiance (TPMs) ont été affectés. Les clés RSA vulnérables sont facilement identifiées à l’aide d’un programme de test publié par l’équipe.,

Importance de la génération de nombres aléatoires fortesmodifier

Un générateur de nombres aléatoires cryptographiquement fort, qui a été correctement ensemencé avec une entropie adéquate, doit être utilisé pour générer les nombres premiers p et Q. Une analyse comparant des millions de clés publiques collectées sur Internet a été réalisée début 2012 par Arjen K. Lenstra, James P. Hughes, Maxime Augier, Joppe W. Bos, Thorsten Kleinjung et Christophe Wachter. Ils ont pu factoriser 0,2% des clés en utilisant uniquement L’algorithme D’Euclide.

ils exploitaient une faiblesse propre aux cryptosystèmes basés sur la factorisation d’entiers., Si n = pq est une clé publique et n’ = p’Q’ en est une autre, alors si par hasard p = p’ (mais q n’est pas égal à q’), alors un simple calcul de gcd(n,n’) = p factorise n et n’, compromettant totalement les deux clés. Lenstra et coll. notez que ce problème peut être minimisé en utilisant une graine aléatoire forte de longueur de bit deux fois le niveau de sécurité prévu, ou en utilisant une fonction déterministe pour choisir q donné p, au lieu de choisir P et q indépendamment.

Nadia Heninger faisait partie d’un groupe qui a fait une expérience similaire. Ils ont utilisé une idée de Daniel J., Bernstein pour calculer le GCD de chaque clé RSA n contre le produit de toutes les autres clés n’ qu’ils avaient trouvées (un nombre de 729 millions de chiffres), au lieu de calculer chaque gcd(n,n’) séparément, réalisant ainsi une accélération très significative car après une grande division, le problème GCD est de taille normale.

Heninger dit dans son blog que les mauvaises clés se sont produites presque entièrement dans les applications embarquées, y compris « les pare-feu, les routeurs, les périphériques VPN, les périphériques d’administration de serveur distant, les imprimantes, les projecteurs et les téléphones VOIP » de plus de 30 fabricants., Heninger explique que le problème d’un premier partagé découvert par les deux groupes résulte de situations où le générateur de nombres pseudorandomiques est mal ensemencé initialement, puis est réensemencé entre la génération des premier et deuxième nombres premiers. L’utilisation de graines d’entropie suffisamment élevée obtenue à partir de timings de course de touches ou de bruit de diode électronique ou de bruit atmosphérique provenant d’un récepteur radio réglé entre les stations devrait résoudre le problème.

une forte génération de nombres aléatoires est importante à chaque étape de la cryptographie à clé publique., Par exemple, si un générateur faible est utilisé pour les clés symétriques distribuées par RSA, alors une écoute pourrait contourner RSA et deviner directement les clés symétriques.

Timing attacksEdit

Kocher a décrit une nouvelle attaque sur RSA en 1995: si L’attaquant Eve connaît le matériel D’Alice de manière suffisamment détaillée et est capable de mesurer les temps de déchiffrement pour plusieurs textes chiffrés connus, Eve peut déduire la clé de déchiffrement d rapidement. Cette attaque peut également être appliquée contre le schéma de signature RSA., En 2003, Boneh et Brumley ont démontré une attaque plus pratique capable de récupérer les factorisations RSA sur une connexion réseau (par exemple, à partir d’un serveur web compatible SSL (Secure Sockets Layer)) cette attaque tire parti des informations divulguées par L’optimisation du théorème du reste Chinois utilisé par de nombreuses implémentations RSA.

Une façon de contrecarrer ces attaques est de s’assurer que l’opération de déchiffrement prend un temps constant pour chaque texte chiffré. Cependant, cette approche peut réduire considérablement les performances., Au lieu de cela, la plupart des implémentations RSA utilisent une technique alternative connue sous le nom d’aveuglement cryptographique. RSA blinding utilise la propriété multiplicative de RSA. Au lieu de calculer cd (mod n), Alice choisit d’abord une valeur aléatoire secrète r et calcule (rec)d (mod n). Le résultat de ce calcul, après l »application du théorème d » Euler, est rcd (mod n) et donc l  » effet de r peut être éliminé en multipliant par son inverse. Une nouvelle valeur de r est choisie pour chaque texte chiffré. Avec l’aveuglement appliqué, le temps de déchiffrement n’est plus corrélé à la valeur du texte chiffré d’entrée, et ainsi l’attaque de synchronisation échoue.,

adaptative chosen ciphertext attacksEdit

en 1998, Daniel Bleichenbacher a décrit la première attaque pratique adaptative chosed ciphertext, contre les messages chiffrés RSA en utilisant le schéma de remplissage PKCS #1 v1 (un schéma de remplissage randomise et ajoute de la structure à un message chiffré RSA, de sorte qu’il est possible de déterminer si un message déchiffré est valide). En raison de défauts avec le schéma PKCS #1, Bleichenbacher a pu monter une attaque pratique contre les implémentations RSA du protocole Secure Socket Layer et récupérer les clés de session., À la suite de ce travail, les cryptographes recommandent maintenant l’utilisation de schémas de remplissage prouvablement sécurisés tels que le remplissage de cryptage asymétrique Optimal, et RSA Laboratories a publié de nouvelles versions de PKCS #1 qui ne sont pas vulnérables à ces attaques.

attaques par analyse de canaux Latérauxmodifier

une attaque par canal latéral utilisant l’analyse de prédiction de branche (BPA) a été décrite. De nombreux processeurs utilisent un prédicteur de branche pour déterminer si une branche conditionnelle dans le flux d’instructions d’un programme est susceptible d’être prise ou non. Souvent, ces processeurs implémentent également le multithreading simultané (SMT)., Analyse de prédiction de branche les attaques utilisent un processus espion pour découvrir (statistiquement) la clé privée lorsqu’elles sont traitées avec ces processeurs.

Simple Branch Prediction Analysis (SBPA) prétend améliorer le BPA de manière non statistique. Dans leur article, « On the Power of simple Branch Prediction Analysis », les auteurs de SBPA (Onur Aciicmez et Cetin Kaya Koc) affirment avoir découvert 508 bits sur 512 d’une clé RSA en 10 itérations.

une attaque de panne d’alimentation sur les implémentations RSA a été décrite en 2010., L’auteur a récupéré la clé en faisant varier la tension D’alimentation du processeur en dehors des limites; cela a provoqué de multiples pannes d’alimentation sur le serveur.