s
19 708 Pages

cryptanalyse
La machine à chiffrer Lorenz-SZ42

à cryptanalyse (à partir de grec kryptos, « Caché », et analýein, "Factoring"), ou cryptanalyse, est l'étude des méthodes permettant d'obtenir le sens de l'information crypté sans avoir accès à des informations secrètes qui est habituellement nécessaire pour effectuer l'opération. En général, il vient de trouver un clé secrète. Cryptanalyse est la « contrepartie » de cryptographie, à savoir l'étude des techniques pour cacher un message, et forment ensemble la cryptologie, la science des dossiers cachés.

avec cryptanalyse Se réfère non seulement aux méthodes de porter atteinte à un chiffre, mais toute tentative de contourner la sécurité des algorithmes et cryptographique protocoles cryptographique. Bien que la cryptanalyse exclut généralement des méthodes d'attaque qui ne sont pas dirigées vers les faiblesses inhérentes à la méthode ne respecte pas, comme le corruption, la la contrainte physique, la vol, l 'ingénierie sociale, ces types d'attaques, souvent plus productives de la cryptanalyse traditionnelle, il est néanmoins un élément important.

Même si la fin est toujours la même, les méthodes et les techniques de cryptanalyse ont radicalement changé au cours de l'histoire de la cryptographie, l'adaptation à accroître en permanence l'efficacité de cryptographie, en commençant par les méthodes de stylo et à la version papier du passé, à travers les machines de chiffrement comme 'énigme de Guerre mondiale, pour se rendre à base sur les modèles ordinateur de la présente. Ensemble, ils ont aussi changé les résultats de cryptanalyse: il est plus possible d'atteindre le succès illimité en violation des codes et attire donc une liste des résultats obtenus par les attaques. Au milieu des années soixante-dix a été introduit un nouveau cryptage de classe: la chiffrement asymétrique. Les méthodes de violation de cette classe sont très différents de ceux utilisés dans le passé et impliquent généralement la résolution de problèmes mathématiciens très complexe, comme le bien connu décomposer en nombres premiers.

Histoire de cryptanalyse

icône Loupe mgx2.svg Le même sujet en détail: Histoire de la cryptographie.

La cryptanalyse a évolué de pair avec le cryptage: nouveaux chiffrements ont été introduites pour remplacer ceux qui sont violés, et de nouvelles techniques de cryptanalyse ont été inventés pour violer les nouveaux régimes. Dans la pratique, il y a deux faces d'une même pièce: afin de créer une technique cryptographique sécurisée doit penser capable de résister à la cryptanalyse.

cryptanalyse classique

cryptanalyse
La première page du manuscrit de Al-Kindi la neuvième siècle intitulé Manuscrit sur le décryptage des messages cryptés

Bien que le mot "cryptanalyse« Est relativement récente (il a été inventé par William Friedman en 1920), Les méthodes pour briser le code crypté et le chiffrement cryptographique sont beaucoup plus âgés. La première explication écrite connue de la cryptanalyse date de neuvième siècle et est le travail de génie arabe Abu Yusuf Yaqub ibn Ishaq al-Sabbah Al-Kindi (Connu également en Europe latinisé de Alchindus): Ceci est la Manuscrit sur le décryptage des messages cryptés. Ce traité comprend une description d'une méthode de Analyse de fréquence (Ibrahim Al-Kadi, 1992- ref-3).

L'analyse de fréquence est une méthode de base de violer de nombreux classiques chiffrements. Dans les langues naturelles, certaines lettres de 'alphabet Ils apparaissent plus fréquemment que d'autres. Par exemple, dans italien les lettres "A« Et »et« Je suis ceux qui apparaissent le plus souvent dans tous les message clair: il est juste de supposer que si un message a été chiffré avec chiffrement de substitution monoalphabétique (Où chaque lettre est simplement remplacée par une autre), il est raisonnable de supposer que les lettres les plus fréquentes qui apparaissent dans le texte chiffré sont candidats pour le « A » ou « E ».

Dans la pratique, l'analyse de fréquence est basée sur la connaissance linguistique car elle repose sur statistiques, mais comme les mathématiques sont devenues chiffrements plus complexes sont devenues plus importantes dans la cryptanalyse. Ce changement a été particulièrement évidente au cours de la Seconde Guerre mondiale, lorsque les tentatives de fissure de chiffrements axe Ils ont exigé de nouveaux niveaux de sophistication mathématique. De plus, l'automatisation a été introduit pour la première fois à la cryptanalyse à cette époque avec l'ordinateur polonais bombe, avec l'utilisation de dispositifs cartes perforées et colosse, l'un des premier ordinateur (peut-être le premier ordinateur numérique électronique programmable).

cryptanalyse moderne

cryptanalyse
Réplique d'un ordinateur bombe

Le calcul appliqué avec un grand profit à la cryptanalyse pendant la Seconde Guerre mondiale a poussé la production de nouvelles techniques de cryptographie plusieurs ordres de grandeur plus complexe qu'auparavant. Pris dans son ensemble, la cryptographie moderne est devenu beaucoup plus difficile à crittanalizzare avec les systèmes de papier-stylo du passé, de sorte que la fin prend lentement sur la cryptanalyse pure.

l'historien David Kahn stipule que « Cryptosystèmes offert aujourd'hui par des centaines de fournisseurs autour qui ne peuvent être violés par l'une des méthodes connues de cryptanalyse ils sont nombreux. En fait, même sur les systèmes de texte clair choisi attaque, dans lequel un message clair spécifiquement sélectionné est comparé au cryptogramme équivalent, il ne permet pas de récupérer la clé qui déverrouille d'autres messages. Dans un sens, alors, cryptanalyse est mort. Mais ce n'est pas la fin de l'histoire: cryptanalyse peut être mort, mais, pour utiliser une métaphore de mon, il y a plus d'une façon à la peau d'un chat "[1]. Kahn continue de mentionner les possibilités accrues interception, la bogues (ou bogues), Le les attaques à canal latéral et cryptographie quantique Ils sont des substituts valables pour significations traditionnelles de cryptanalyse.

Peut-être que Kahn était trop hâtive à donner aux cryptanalyse morts: les faibles chiffres sont loin d'avoir disparu, et les méthodes de cryptanalyse employées par les agences intelligence Ils restent pour la plupart inconnus de partie. Dans le domaine universitaire, de nombreux chercheurs ont régulièrement de nouveaux systèmes cryptographiques, qui sont souvent violés rapidement: la chiffrement par bloc Madryga, publié en 1984 Il a été trouvé sensible à Les attaques ne cryptogramme en 1998; la FEAL-4, proposé en remplacement de DES, Il a été démoli par une série d'attaques de la communauté universitaire, dont beaucoup sont tout à fait réalisables dans la pratique.

Même dans 'industrie beaucoup de chiffrements ne sont pas sans faiblesses: par exemple, les algorithmes A5 / 1, A5 / 2 et CAEM, utilisé dans la technologie de téléphone portable, Ils peuvent être violés en heures, minutes ou même temps réel l'utilisation des ordinateurs à la portée de beaucoup. en 2001 il a été montré que le protocole WEP, utilisé pour établir des connexions sécurisées Wi-Fi, était dangereux et attaque liée à la clé pourrait être récupéré par ce dernier en quelques heures. en 2005 Il a même trouvé un moyen de casser un accès protégé par WEP en moins d'une minute[2].

Les résultats de cryptanalyse

cryptanalyse
la télégramme Zimmermann déchiffré.

Plusieurs fois les succès de cryptanalyse ont influencé l'histoire: la capacité de lire les pensées présumées et les plans secrets des autres peut être un avantage décisif, il se révèle, en particulier en temps de guerre. pendant, par exemple, Première Guerre mondiale, la violation de télégramme Zimmermann entrée accélérée dans le conflit de États-Unis d'Amérique. Dans la Seconde Guerre mondiale, la cryptanalyse des chiffrements allemands, y compris le machine Enigma et l'algorithme de chiffrement Lorenz, est connu pour les chercheurs l'un des points qui ont raccourci de plusieurs mois la fin du conflit en Europe (voir ULTRA). Les Etats-Unis ont également bénéficié de la cryptanalyse en raison du fait que, il était en mesure de déchiffrer la plupart des communications militaires secrètes japonais, qu'ils ont été chiffrés par une machine appelée PURPLE par les Américains (l'équivalent japonais de l'énigme allemande).

Les gouvernements des pays reconnaissent depuis longtemps les avantages incontestables de cryptanalyse dans le domaine de espionnage, les organismes militaires et diplomatiques, et établies ont voté spécifiquement aux codes de cryptage et d'autres nations chiffrements, comme le GCHQ Anglais ou l 'NSA États-Unis, les organisations sont encore actifs aujourd'hui. en 2004 Il a été divulgué les nouvelles que les Etats-Unis ont violé les chiffrements Iraniens (Bien qu'il reste inconnu qui n'a été utilisé cryptanalyse pur, ou même d'autres techniques moins orthodoxes)[3].

Caractérisation des attaques

Les attaques de cryptanalyse varient dans la force et la capacité de menacer cryptosystèmes monde réel. un faiblesse certifiable est une attaque théorique qui est peu susceptible d'être applicable dans une situation réelle; la majorité des résultats obtenus par crittanalitica modernes de recherche de ce type. Pour l'essentiel, l'importance pratique d'une attaque dépend des réponses aux questions suivantes:

  1. que les connaissances et les compétences sont nécessaires en tant que conditions préalables?
  2. Combien des informations secrètes supplémentaires est déduit?
  3. Combien d'efforts est nécessaire (c.-à-ce qu'il est le complexité de calcul)?

connaissances primaires: scénarios pour cryptanalyse

La cryptanalyse peut être effectuée sur un certain nombre d'hypothèses sur ce qui peut être observé ou découvert sur le système attaqué. En tant que base de départ suppose généralement que, aux fins d'analyse, le 'algorithme est connu en général: c'est le principe Kerckhoffs, qui stipule que l'ennemi connaît le système. Le principe Kerckhoffs est une hypothèse raisonnable, puisque l'histoire montre d'innombrables cas d'algorithmes secrets considérés comme sûrs se sont révélés inviolables dès dans le domaine public, parce que, par exemple, espionnage, trahison et L'ingénierie inverse (De temps en temps chiffrements ont été reconstruits par la simple déduction: par exemple, le mentionné ci-dessus Lorenz chiffrement et Code violet, en plus d'une variété de systèmes classiques).

D'autres hypothèses sont les suivantes:

  • seulement cryptogramme: L'attaquant a seulement accès à une collection de cryptogrammes.
  • Plaintext connu: L'attaquant dispose d'un ensemble de texte crypté qui connaît le texte brut correspondant.
  • Texte brut choisi (cryptogramme choisi): L'attaquant peut obtenir les cryptogrammes (plaintexts) correspondant à un ensemble arbitraire de plaintexts (cryptogrammes) de son choix.
  • Avec Adaptive choisi plaintext: En ce qui concerne l'attaque choisie plaintext, sauf que l'attaquant peut choisir de texte séquences clairement en fonction des informations obtenues à partir de l'analyse des messages chiffrés précédents. Semblable à cela est l'attaque adaptative choisi-cryptogramme.
  • Attaque liée à la clé: En ce qui concerne l'attaque choisie plaintext, sauf que l'attaquant peut obtenir des cryptogrammes chiffrées avec deux clés différentes. Les clés ne sont pas connues, mais la relation entre eux est connu: par exemple, deux clés qui ne diffèrent que par 1 bit.

Ces types d'attaques diffèrent sur la façon plausible les mettre en pratique. Alors que certaines attaques sont plus susceptibles que les autres, les cryptographes sont souvent confrontés au problème de la sécurité avec une approche conservatrice et d'imaginer le pire des cas où des algorithmes conception, le raisonnement que si un système est également sans danger contre les menaces alors irréalistes devraient résister aux plus bien à la cryptanalyse du monde réel.

Les hypothèses sont souvent plus réalistes que vous imaginez à première vue. Pour une attaque texte clair connu, le décrypteur peut savoir, ou être en mesure de prendre possession, une partie du texte brut, comme une lettre chiffrée qui commence par « Cher Monsieur » ou une session terminal commençant par "LOGIN:. « Une attaque choisie est moins-plaintext susceptibles que les autres attaques, mais est souvent plausible: par exemple, vous pourriez trouver quelqu'un pour vous envoyer un message que vous leur avez donné, mais sous forme chiffrée liée à des attaques Les clés sont principalement théoriques. , même si elles peuvent être très réalistes dans certaines situations: par exemple, quand il est utilisé chiffrement par bloc pour réaliser une fonction de hachis.

Cryptanalyse succès dans la classification

Les résultats de cryptanalyse peuvent également varier en utilité. Par exemple, cryptographe Lars Knudsen (1998) Classified différents types d'attaques sur chiffrements par blocs selon la quantité et la qualité des informations secrètes qui a été découvert:

  • violation totale: L'attaquant de la clé secrète déduit;
  • déduction globale: L'attaquant découvre une algorithme fonctionnellement équivalent pour le chiffrement et le déchiffrement, mais sans la clé;
  • déduction locale: L'attaquant découvre plaintexts (ou ciphertexts) pas précédemment connu supplémentaire;
  • déduction de l'information: L'attaquant gagne quelques-uns informations Shannon sur plaintexts (ou sur ciphertexts) non connu précédemment;
  • algorithme discriminante: L'attaquant peut distinguer le chiffrement à partir d'un permutation au hasard.

Des considérations similaires sont applicables à des attaques sur d'autres types d'algorithmes de chiffrement.

complexité

Les attaques peuvent également être caractérisées par la quantité des ressources dont ils ont besoin. Ceux-ci peuvent être sous forme de:

  • Heure: le nombre de opérations primitives qui doit être effectué. Ce chiffre est assez générique: les opérations primitives pourraient être des instructions informatiques de base, telles que l'addition, XOR, décalages de bits et ainsi de suite, comme des entiers méthodes de cryptage;
  • Mémoire: La quantité d'espace de stockage nécessaire pour effectuer l'attaque.
  • Données: quantité des textes simples et textes chiffrés nécessaires.

dans le cryptage universitaire un faiblesse ou rupture dans un régime, il est généralement défini dans une assez conservatrice. Bruce Schneier résumant cette approche: "Briser un chiffre signifie simplement trouver une faiblesse qui peut être exploitée dans le même avec moins de complexité force brute. Peu importe que la force brute nécessite 2128 chiffrements: une attaque qui nécessiterait 2110 chiffrements seraient considérés comme une pause ... tout simplement, une pause peut être simplement une faiblesse certifiable: la preuve que le chiffre ne se comporte pas comme prévu.« (Schneier, 2000).

Cryptanalyse de cryptographie asymétrique

la chiffrement asymétrique ou cryptographie à clé publique est un type de cryptage qui est basé sur l'utilisation de deux clés, une privée et une publique. Ces chiffres fondent toute leur sécurité des problèmes mathématiques difficiles à résoudre si un point évident d'attaque est de développer des méthodes pour résoudre ces problèmes. La sécurité de chiffrement asymétriques deux clés dépend des questions mathématiques qui ne sont généralement pas pris en compte par la clé de cryptage unique, et se connecte par conséquent, la recherche mathématique cryptanalyse d'une manière nouvelle.

Les motifs asymétriques sont dessinés sur la difficulté (conjecturé) pour résoudre divers problèmes mathématiques. Si vous trouvez un meilleur algorithme qui peut résoudre le problème, le système est affaibli. Par exemple, la sécurité des système d'échange de clés Diffie-Hellman Cela dépend de la difficulté de calculer une logarithme discret. en 1983 Don Coppersmith Il a conçu un moyen plus rapide pour trouver des logarithmes discrets (dans certains groupes), forçant ainsi cryptographes à utiliser des groupes plus importants (ou différents types de groupes). La sécurité des 'RSA Cela dépend (en partie) par la difficulté de factorisation grand Les nombres premiers: Un pas en avant dans le problème d'affacturage érode la sécurité RSA.

en 1980 Il pourrait factoriser un nombre à 50 chiffres à un coût de 1012 opérations élémentaires. en 1984 progrès dans l'art de l'écriture aux algorithmes de factorisation avait atteint un tel point que la même opération pourrait factoriser un nombre de 75 chiffres. De plus, l'art, vous permettant d'effectuer le même nombre d'opérations beaucoup plus rapidement. la La loi de Moore Il prédit que la vitesse de l'ordinateur augmente de façon constante: les techniques de factorisation feront la même chose, mais sera également basée sur la créativité et l'intuition mathématique, dont aucune ne peut être prédit avec succès. Les numéros 150 bits, utilisés un temps RSA, ont été pris en compte: était plus grande qu'on ne l'imaginait l'effort, mais il était certainement pas au-delà de la portée des ordinateurs rapides et modernes. En fait, au début de XXI siècle, Les chiffres de 150 chiffres ne sont plus assez longtemps pour les clés RSA. Les nombres avec plusieurs centaines de chiffres sont encore considérés comme difficiles à être prises en compte, bien que les méthodes continueront probablement d'améliorer au fil du temps, ce qui nécessite longueurs de clé capable de résister aux nouveaux algorithmes qui seront utilisés.

Une autre caractéristique des régimes asymétriques est que, à la différence des systèmes de chiffrement symétriques, toute cryptanalyse a la possibilité d'utiliser les connaissances acquises à partir de la clé publique.

Application des ordinateurs quantiques à cryptanalyse

la ordinateurs quantiques, qui sont encore dans les premières étapes du développement, serait utile dans la cryptanalyse. Par exemple, l 'L'algorithme de Shor Vous pouvez tenir un grand nombre dans un polynomiale, à-dire en pratique que vous pouvez violer certaines formes de cryptographie à clé publique.

En utilisant le 'algorithme de recherche de Grover sur un ordinateur quantique, la recherche d'une clé par la force brute peut être réalisée avec une vitesse qui est la place de celle exprimée par ordinateur normal. De toute évidence, cela pourrait être contrecarrée en augmentant la longueur de la clé.

techniques cryptanalyse

cryptanalyse classique:

algorithmes Symétrique:

Les fonctions de hachage:

Modèles d'attaque:

Les attaques de canal latéral:

  • Analyse de puissance
  • Time Attack

Les attaques sur les réseaux:

Les attaques externes:

notes

bibliographie

  • Helen Fouché Gaines, "cryptanalyse", 1939, Dover. ISBN 0-486-20097-3
  • Abraham Sinkov, Cryptanalyse élémentaire: une approche mathématique, Mathématique Association of America, 1966. ISBN 0-88385-622-0
  • Ibrahim A. Al-Kadi, "Les origines de la cryptologie: Les contributions arabes", Cryptologia, 16 (2), Avril 1992, pp. 97-126.
  • David Kahn, "Les Codebreakers - L'histoire de secret d'écriture", 1967. ISBN 0-684-83130-9
  • Lars R. Knudsen: Contemporain Bloc chiffrements. Conférences sur la sécurité des données de 1998: 105-126
  • Bruce Schneier, "Cours d'autoapprentissage Cipher Block cryptanalyse" Cryptologia, 24 (1), Janvier 2000, p. 18-34.
  • Friedrich L. Bauer: "Secrets déchiffrés". Springer, 2002. ISBN 3-540-42674-4
  • Friedman, William F., Cryptanalyse militaire, partie I, ISBN 0-89412-044-1
  • Friedman, William F., Cryptanalyse militaire, partie II, ISBN 0-89412-064-6
  • Friedman, William F., Cryptanalyse militaire, partie III, Simpler variétés de apériodiques systèmes de substitution, ISBN 0-89412-196-0
  • Friedman, William F., Cryptanalyse militaire, partie IV, et en fractionnant Transposition Systems, ISBN 0-89412-198-7
  • Friedman, William F. et D. Lambros Demetrios Callimahos, Cryptanalytics militaire, Partie I, Volume 1, ISBN 0-89412-073-5
  • Friedman, William F. et D. Lambros Demetrios Callimahos, Cryptanalytics militaire, Partie I, Volume 2, ISBN 0-89412-074-3
  • Friedman, William F. et D. Lambros Demetrios Callimahos, Cryptanalytics militaire, Partie II, Volume 1, ISBN 0-89412-075-1
  • Friedman, William F. et D. Lambros Demetrios Callimahos, Cryptanalytics militaire, Partie II, Volume 2, ISBN 0-89412-076-X

Articles connexes

général

  • Le chiffrement
  • cryptologie

cryptanalystes historique

  • Conel Alexander Hugh O'Donnel
  • Lambros Demetrios Callimahos
  • Alastair Denniston
  • Agnes Meyer Driscoll
  • Elizebeth Friedman
  • William F. Friedman, le père de la cryptologie moderne
  • Meredith Gardner
  • Dilly Knox
  • Solomon Kullback
  • Georges Painvin
  • Marian Rejewski
  • Frank Rowlett
  • Luigi Sacco
  • Abraham Sinkov
  • Giovanni Soro, la première cryptanalyst Renaissance
  • John Tiltman
  • Alan Turing
  • Herbert Yardley

D'autres projets

  • Il contribue à Wikimedia Commons Wikimedia Commons: Il contient des images ou d'autres fichiers cryptanalyse

liens externes

autorités de contrôle GND: (DE4830502-9