Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Repères – Comprendre RSA nico34 – buﬀer 13 avril 2011 Table des matières 1 Intr

Repères – Comprendre RSA nico34 – buﬀer 13 avril 2011 Table des matières 1 Introduction 2 1.1 L’évolution de la cryptographie d’un point de vue non-technique 2 1.2 Notions à propos du système RSA . . . . . . . . . . . . . . . . . 4 1.3 Où réside la force du cryptosystème RSA ? . . . . . . . . . . . . . 4 1.4 Un peu d’histoire... . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Comprendre les fondements mathématiques de RSA 6 2.1 Notion de nombres premiers . . . . . . . . . . . . . . . . . . . . . 6 2.1.1 Déﬁnition . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1.2 Décomposition en facteurs premiers . . . . . . . . . . . . 6 2.2 Calcul modulaire et division euclidienne . . . . . . . . . . . . . . 6 2.3 Notion de Plus Grand Commun Diviseur . . . . . . . . . . . . . . 7 2.4 Primalité de deux nombres . . . . . . . . . . . . . . . . . . . . . 7 2.5 Identité de Bézout . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.6 Indicatrice d’Euler . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.7 Théorèmes divers . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.7.1 Théorème d’Euler . . . . . . . . . . . . . . . . . . . . . . 8 2.7.2 Théorème de Fermat . . . . . . . . . . . . . . . . . . . . . 8 2.7.3 Théorème des restes chinois . . . . . . . . . . . . . . . . . 9 3 RSA 10 3.1 Choix du module et des exposants ; éléments de sécurisation . . . 10 3.1.1 Choix du module . . . . . . . . . . . . . . . . . . . . . . . 10 3.1.2 Choix de l’exposant public . . . . . . . . . . . . . . . . . 11 3.1.3 Choix de l’exposant privé . . . . . . . . . . . . . . . . . . 12 3.2 Applications RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2.1 Chiﬀrement . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2.2 Déchiﬀrement . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2.3 Pourquoi ça marche ? – Théorème RSA . . . . . . . . . . 13 3.2.4 Signature électronique et RSA . . . . . . . . . . . . . . . 14 3.3 Propriétés applicatives remarquables et comparatives de RSA . . 16 3.4 Exemple d’application . . . . . . . . . . . . . . . . . . . . . . . . 17 4 Chiﬀrement 19 4.1 Fonction du schéma de chiﬀrement OAEP . . . . . . . . . . . . . 19 4.2 Implémentation de OAEP dans Scapy . . . . . . . . . . . . . . . 20 5 Conclusion 23 1 Chapitre 1 Introduction RSA est un algorithme cryptographique qui fait partie de la catégorie des algortihmes à clés publiques ou systèmes asymétriques. L’acronyme RSA, créé en 1977, vient du nom de ses trois inventeurs (Rivest, Shamir et Adleman). Ce chiﬀrement est le plus connu en termes d’algorithmes cryptographiques de type asymétrique. Nous le retrouvons beaucoup dans le e-commerce pour ef- fectuer le paiement en ligne. Mais RSA est aussi utilisé dans les systèmes ban- caires (cartes bleues). Ce chiﬀrement est également présent dans les signatures numériques de documents (clé PGP1) et dans les réseaux avec les connexions ssh (Security Shell) via des logiciels comme OpenSSL très connu dans les systèmes de type Unix. Tout d’abord, il est nécessaire de préciser quelques points pour les person- nes qui ne sont pas adeptes de cryptographie. Nous avons parlé de système asymétrique, c’est-à-dire de sytème mettant en oeuvre une clé publique et une clé privé qui servent respectivement à chiﬀrer et déchiﬀrer. A l’opposé, les sys- tèmes symétriques ou à clé secrète utilisent une seule clé servant à chiﬀrer et à déchiﬀrer, ce qui, à taille de clé comparable, rend l’information plus vulnérable. 1.1 L’évolution de la cryptographie d’un point de vue non-technique Jusqu’en 1999 la loi française interdisait toute utilisation de logiciels de chiﬀrement de données, ceux-ci étant considérés comme des armes de guerre de 2ème catégorie. Plus tard, la loi s’est assouplie grâce à Lionel Jospin en autorisant l’utilisation de la cryptographie aux particuliers notamment pour fa- voriser le commerce électronique2. Il faut savoir que depuis le 11 septembre 2001, l’utilisation de la cryptographie a fait débat après que les médias ont déclaré que certains terroristes utilisaient la cryptographie pour communiquer et organiser des attentats. Suite à l’augmentation de l’utilisation, ou plutôt la démocratisation des tech- nique de surveillance, les particuliers s’intéressent de plus en plus à la sécurité de 1Pretty Good Privacy 2SSL : http://www.signelec.com/news/1030778870/index_html 2 leurs données. Néanmoins, le fait que les particuliers protègent leurs données via des techniques de cryptographie n’arrange pas les gouvernements qui se doivent de contrôler toutes les informations transitant entre les pays. Par contre, suite aux échos de l’aﬀaire Echelon3 et à la sensibilisation faite auprès des entreprises françaises, les industriels se sont mis à chiﬀrer leurs don- nées considérées comme conﬁdentielles pour éviter l’espionnage industriel4. De plus, depuis la sortie de la loi Hadopi, les Etats-Unis reprochent à la France de parer à la cybersurveillance des internautes en les incitants à chiﬀrer leurs données de communication5. En revanche le gouvernement s’autorise d’après l’article 434-15-2 du code pénal6, de demander la clé ayant servi à chiﬀrer des messages susceptibles d’avoir été en relation avec un crime ou un délit. "Est puni de trois ans d’emprisonnement et de 45 000 euros d’amende le fait, pour quiconque ayant connaissance de la convention secrète de déchiﬀrement d’un moyen de cryptologie susceptible d’avoir été utilisé pour préparer, faciliter ou commettre un crime ou un délit, de refuser de remettre ladite convention aux autorités judiciaires ou de la mettre en oeuvre, sur les réquisitions de ces autorités délivrées en application des titres II et III du livre Ier du code de procédure pénale. Fig. 1.1 – Pas de Libertés sans Vie Privée Si le refus est opposé alors que la remise ou la mise en oeuvre de la convention aurait permis d’éviter la commission d’un crime ou d’un délit ou d’en limiter les eﬀets, la peine est portée à cinq ans d’emprisonnement et à 75 000 euros d’amende." Par ailleurs, un organisme gouvernemental connu sous le nom de Centre Technique d’Assistance (CTA), peut, dans le cadre d’une enquète et si le mot de passe de l’expéditeur n’est pas divulgé, recourir à une cryptanalyse des données du disque dur de cette même personne. Cette organisation est protégée par le secret défense7 ; c’est-à-dire à partir du moment où une communication en 3http://www.projet22.com/histoire-29/les-services-de-renseignements/article/ echelon-un-reseau-d-ecoute-mondial 4http://video.google.fr/videoplay?docid=1319842311215805304 5http://bugbrother.blog.lemonde.fr/2010/10/02/frenchelon-la-dgse-est-en-1ere-division/ 6http://www.legifrance.gouv.fr/affichCode.do?idArticle= LEGIARTI000006418637&idSectionTA=LEGISCTA000006165379&cidTexte= LEGITEXT000006070719&dateTexte=vig 7http://www.zdnet.fr/actualites/cryptographie-le-droit-au-secret-chamboule-par-les-decrets-de-la-lsq-212257 htm 3 rapport avec l’enquête a été interceptée puis rapportée au CTA, et que celle-ci présente un délit ou un crime, il ne peut pas y avoir de contre-expertise. 1.2 Notions à propos du système RSA La première clé est la clé publique, elle est visible par tout le monde et est composée de deux nombres distincts : un module – lui-même le produit de deux nombres premiers – et un exposant public, que l’on appelera, respectivement, dans cet article, n et e. La clé publique sert à chiﬀrer le message. La deuxième clé de la paire est appelée clé privée, elle sert à déchiﬀrer le message. Celle si est connue par le créateur de uploads/S4/ reperes-rsa 1 .pdf