CRYPTANALYSE DE RSA Abderrahmane Nitaj Laboratoire de Math´ ematiques Nicolas O

CRYPTANALYSE DE RSA Abderrahmane Nitaj Laboratoire de Math´ ematiques Nicolas Oresme Universit´ e de Caen, France http://www.math.unicaen.fr/~nitaj nitaj@math.unicaen.fr c ⃝Version du 28 juin 2009 Table des mati` eres Contenu i Pr´ eface 1 1 Introduction au cryptosyst` eme RSA 3 1.1 Principe de RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.1 Le module RSA . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.2 Les cl´ es publiques et priv´ ees . . . . . . . . . . . . . . . . . . . 5 1.1.3 Envoi d’un message . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.4 D´ echiffrement d’un message . . . . . . . . . . . . . . . . . . . 8 1.1.5 Signature d’un message . . . . . . . . . . . . . . . . . . . . . . 9 1.1.6 Preuve de RSA . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2 Un exemple d’utilisation de RSA . . . . . . . . . . . . . . . . . . . . 12 1.2.1 Transformation d’un texte en nombres . . . . . . . . . . . . . 12 1.2.2 L’exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.3 Cryptanalyses ´ el´ ementaires de RSA . . . . . . . . . . . . . . . . . . 15 1.3.1 Cryptanalyse de RSA connaissant ϕ(N) . . . . . . . . . . . . 15 1.3.2 Utilisation du mˆ eme module et deux exposants diff´ erents . . . 16 1.3.3 Utilisation de modules diff´ erents pour le mˆ eme message. . . . 18 1.3.4 Cryptanalyse de RSA si |p −q| < cN 1/4 : M´ ethode de Fermat 21 2 Cryptanalyse de RSA par les fractions continues 25 2.1 Les fractions continues . . . . . . . . . . . . . . . . . . . . . . . . . . 25 i ii TABLE DES MATI` ERES 2.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.1.2 D´ efinitions et propri´ et´ es . . . . . . . . . . . . . . . . . . . . . 26 2.2 Cryptanalyse de RSA par les fractions continues . . . . . . . . . . . . 37 2.2.1 L’attaque de Wiener . . . . . . . . . . . . . . . . . . . . . . . 38 3 Cryptanalyse de RSA par l’algorithme LLL 43 3.1 L’algorithme LLL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.1.1 Introduction aux r´ eseaux . . . . . . . . . . . . . . . . . . . . . 43 3.1.2 L’algorithme LLL . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.2 Cryptanalyse de RSA par la r´ eduction des r´ eseaux . . . . . . . . . . . 59 3.2.1 La m´ ethode de Coppersmith : polynˆ omes ` a une variable . . . 59 3.2.2 Factorisation de N . . . . . . . . . . . . . . . . . . . . . . . . 69 Bibliographie 73 Pr´ eface Si vous enseignez ` a un homme, vous n’enseignez qu’` a une personne. Si vous enseignez ` a une femme, vous enseignez ` a toute une famille. .   éÊ K A «  IÒ  Ê« Y  ® ¯   è @QÓ@  IÒ  Ê« @ X@ A  Ó @ ,@ XQ ¯  IÒ  Ê« Y  ® ¯ C  g . P  IÒ  Ê« @ X@ La cryptographie moderne est bas´ ee sur les math´ ematiques pour s´ ecuriser l’infor- mation. On distingue deux types de protocoles cryptographiques : la cryptographie ` a cl´ e priv´ ee et la cryptographie ` a cl´ e publique. La cryptographie ` a cl´ e publique ` a ´ et´ e introduite par Whitfield Diffie et Martin Hellman en 1976, marquant ainsi la nais- sance de la cryptographie moderne. Le principe de la cryptographie ` a cl´ e publique repose sur deux types de cl´ es : une cl´ e publique et une cl´ e priv´ ee. Pour chiffrer un message, on utilise la cl´ e publique de son destinataire. Alors, seul le destinataire peut d´ echiffrer le message re¸ cu avec sa propre cl´ e priv´ ee. En 1978, Ronald Rivest, Adi Shamir et Leonard Adleman ont propos´ e le premier cryptosyst` eme ` a cl´ e publique, appel´ e RSA. Ce cryptosyst` eme est devenu le plus r´ epandu dans le monde car il est facile ` a r´ ealiser mais tr` es difficile ` a casser. En effet, sa s´ ecurit´ e repose sur l’un des probl` emes les plus difficiles en math´ ematiques : la factorisation des grand nombres. Dans ce travail, nous introduisons les principes g´ en´ eraux du cryptosyst` eme RSA ainsi que certaines attaques permettant de le casser, si les param` etres de s´ ecurit´ e sont mal choisis ou s’il v´ erifient des relations permettant ` a un attaquant d’en tirer profit. Dans le chapitre 1, nous donnons les principes g´ en´ eraux du cryptosyst` eme RSA et nous pr´ esentons quelques attaques ´ el´ ementaires permettant de le casser. Dans le chapitre 2, nous pr´ esentons une introduction ` a la th´ eorie des fractions continues et leur utilisation pour attaquer le cryptosyst` eme RSA dans certains cas. Dans le chapitre 3, nous pr´ esentons quelques aspects de la r´ eduction des r´ eseaux, plus pr´ ecis´ ement l’algorithme LLL et son utilisation pour attaquer le cryptosyst` eme RSA grˆ ace ` a la m´ ethode de Coppersmith. Dans ce travail, la plupart des r´ esultats sont illustr´ es par des algorithmes pro- gramm´ es ` a l’aide des syst` emes de calcul Maple 12 et Magama dont un calculateur 1 2 TABLE DES MATI` ERES en ligne est ` a l’adresse http://magma.maths.usyd.edu.au/calc/. Chapitre 1 Introduction au cryptosyst` eme RSA Celui qui n’aime pas gravir les montagnes, vivra toute sa vie dans les trous. Abou Al Qasim Achabi .Q ® mÌ'@ á K. Q ë  YË@ Y K. @  ª K È A J.m. Ì'@ Xñ ª “  I . m  ' B á Ó ð ú  G.A  ‚Ë@ Õæ A  ®Ë@ ñ K.@ 1.1 Principe de RSA Toutes les op´ eration du cryptosyst` eme RSA se passe dans un ensemble de nombre entiers. Soient p et q deux nombres premiers assez grands. On note N = pq. Le nombre N est appel´ e module RSA. Supposons que deux personnes A et B veulent communiquer de fa¸ con sˆ ure en utilisant le cryptosyst` eme RSA. Pour cela, ils doivent, chacun de son cot´ e pr´ eparer un module RSA, deux cl´ es e et d, ex´ ecuter une proc´ edure de chiffrement et de signature et une proc´ edure de d´ echiffrement et de v´ erification de la signature. 1.1.1 Le module RSA Avant tout, pour utiliser le cryptosyst` eme RSA, chacun des intervenants A et B doit fabriquer son propre module RSA. L’algorithme 1 peut ˆ etre alors utilis´ e. 3 4 CHAPITRE 1. INTRODUCTION AU CRYPTOSYST` EME RSA Algorithme 1 : Fabrication du module Entr´ ee : Une taille t pour le module du cryptosyt` eme RSA. Sortie : Un module RSA N de taille t. 1: Prendre un nombre premier al´ eatoire p dans l’intervalle h 2 t 2, 2 t+1 2 i . 2: Prendre un nombre premier al´ eatoire q dans l’intervalle h 2 t 2, 2 t+1 2 i . 3: Si p = q alors 4: Aller ` uploads/Management/ crypt-rsa.pdf

Documents similaires

Cours de : Gestion de la Force de vente Par Mr. NEJJAR Boubker 1 Introduction g 0 0

1 1 Université Sidi Mohammed Ben Abdellah Faculté des Sciences Juridiques Écono 0 0

p.1 Offre Matérielle TSX Micro et Premium p.2 Table des matières : Hardware TSX 0 0

N. Bramand Professeur des écoles P. Bramand Professeur agrégé É. Lafont Profess 0 0

1 Master en Management de Projets- 2ème édition 2004-2005 Mémoire de Projet Pro 0 0

3. Conduite de missions d’audit interne 2014-2015 M. Yazi Démarche générale 1. 0 0

Page 1/ ?? exercices de révisions Math - Classe de 6e Corrigé de l’exercice 1 C 0 0

PROGRAMME DE CONTROLE DES COMPTES 1 Programme Annuel de Contrôle des Comptes Ex 0 0

VÉRIFICATION DE MÉTHODES EN IMMUNO-ESSAIS RETOUR D’EXPERIENCE C. Hoche, B. Bail 0 0

c ⃝Christophe Bertault - MPSI Arithmétique des entiers relatifs 1 Division dans 0 0

• Détails
• Publié le Jul 29, 2022
• Catégorie Management
• Langue French
• Taille du fichier 0.4022MB