Frequenzanalyse - Frequency analysis

Für andere Verwendungen siehe Frequenzanalyse (Begriffsklärung) .
Eine typische Verteilung von Buchstaben in englischsprachigem Text. Schwache Chiffren maskieren die Verteilung nicht ausreichend, und dies kann von einem Kryptoanalytiker zum Lesen der Nachricht ausgenutzt werden.

In der Kryptoanalyse ist die Frequenzanalyse (auch als Zählen von Buchstaben bekannt ) die Untersuchung der Häufigkeit von Buchstaben oder Buchstabengruppen in einem Chiffretext . Die Methode wird als Hilfsmittel zum Brechen klassischer Chiffren verwendet .

Die Frequenzanalyse basiert auf der Tatsache, dass in einem bestimmten Abschnitt der Schriftsprache bestimmte Buchstaben und Buchstabenkombinationen mit unterschiedlichen Häufigkeiten vorkommen. Darüber hinaus gibt es eine charakteristische Verteilung von Buchstaben, die für fast alle Stichproben dieser Sprache ungefähr gleich ist. Zum Beispiel, wenn ein Abschnitt der englischen Sprache gegeben ist , E. , T. , EIN und Ö sind die häufigsten, während Z. , Q. , X. und J. sind selten. Gleichfalls, TH , ER , AUF , und EIN sind die häufigsten Buchstabenpaare ( Bigrams oder Digraphen genannt ), und SS , EE , TT , und FF sind die häufigsten Wiederholungen. Der Unsinn " ETAOIN SHRDLU " repräsentiert die 12 häufigsten Buchstaben in typisch englischsprachigem Text.

In einigen Chiffren bleiben solche Eigenschaften des Klartextes in natürlicher Sprache im Chiffretext erhalten, und diese Muster können bei einem Nur-Chiffretext-Angriff ausgenutzt werden .

Frequenzanalyse für einfache Substitutions-Chiffren

Bei einer einfachen Substitutions-Chiffre wird jeder Buchstabe des Klartextes durch einen anderen ersetzt, und jeder bestimmte Buchstabe im Klartext wird immer in denselben Buchstaben im Chiffretext umgewandelt. Zum Beispiel, wenn alle Vorkommen des Briefes e in den Brief verwandeln X. , eine Chiffretextnachricht, die zahlreiche Instanzen des Briefes enthält X. würde einem Kryptoanalytiker das vorschlagen X. repräsentiert e .

Die grundlegende Verwendung der Frequenzanalyse besteht darin, zuerst die Häufigkeit von Chiffretextbuchstaben zu zählen und ihnen dann erratene Klartextbuchstaben zuzuordnen. Mehr X. s im Chiffretext als alles andere deutet darauf hin X. entspricht e im Klartext, aber das ist nicht sicher; t und ein sind auch in Englisch sehr verbreitet, so X. könnte auch einer von ihnen sein. Es ist unwahrscheinlich, dass es sich um einen Klartext handelt z oder q die sind weniger verbreitet. Daher muss der Kryptoanalytiker möglicherweise mehrere Kombinationen von Zuordnungen zwischen Chiffretext- und Klartextbuchstaben ausprobieren.

Eine komplexere Verwendung von Statistiken kann ins Auge gefasst werden, beispielsweise die Berücksichtigung der Anzahl von Buchstabenpaaren ( Bigrams ), Tripletts ( Trigramme ) usw. Dies geschieht, um dem Kryptoanalytiker weitere Informationen bereitzustellen, z. Q. und U. treten fast immer zusammen in dieser Reihenfolge auf Englisch auf, obwohl Q. selbst ist selten.

Ein Beispiel

Angenommen, Eve hat das folgende Kryptogramm abgefangen , und es ist bekannt, dass es mit einer einfachen Substitutionsverschlüsselung wie folgt verschlüsselt wird: 

LIVITCSWPIYVEWHEVSRIQMXLEYVEOIEWHRXEXIPFEMVEWHKVSTYLXZIXLIKIIXPIJVSZEYPERRGERIM
WQLMGLMXQERIWGPSRIHMXQEREKIETXMJTPRGEVEKEITREWHEXXLEXXMZITWAWSQWXSWEXTVEPMRXRSJ
GSTVRIEYVIEXCVMUIMWERGMIWXMJMGCSMWXSJOMIQXLIVIQIVIXQSVSTWHKPEGARCSXRWIEVSWIIBXV
IZMXFSJXLIKEGAEWHEPSWYSWIWIEVXLISXLIVXLIRGEPIRQIVIIBGIIHMWYPFLEVHEWHYPSRRFQMXLE
PPXLIECCIEVEWGISJKTVWMRLIHYSPHXLIQIMYLXSJXLIMWRIGXQEROIVFVIZEVAEKPIEWHXEAMWYEPP
XLMWYRMWXSGSWRMHIVEXMSWMGSTPHLEVHPFKPEZINTCMXIVJSVLMRSCMWMSWVIRCIGXMWYMX

In diesem Beispiel werden Großbuchstaben verwendet, um Chiffretext zu bezeichnen, Kleinbuchstaben werden verwendet, um Klartext zu bezeichnen (oder Vermutungen an solchen), und X. ~ t wird verwendet, um eine Vermutung dieses Chiffretextbuchstabens auszudrücken X. repräsentiert den Klartextbuchstaben t .

Eve könnte eine Frequenzanalyse verwenden, um die Nachricht folgendermaßen zu lösen: Die Anzahl der Buchstaben im Kryptogramm zeigt dies ich ist der häufigste Einzelbuchstabe, XL am häufigsten Bigram , und XLI ist das häufigste Trigramm . e ist der häufigste Buchstabe in der englischen Sprache, th ist das häufigste Bigram und das ist das häufigste Trigramm. Dies deutet stark darauf hin X. ~ t , L. ~ h und ich ~ e . Der zweithäufigste Buchstabe im Kryptogramm ist E. ;; seit dem ersten und zweithäufigsten Buchstaben in englischer Sprache, e und t werden vermutet, das vermutet Eve E. ~ ein , der dritthäufigste Brief. Wenn diese Annahmen vorläufig getroffen werden, wird die folgende teilweise entschlüsselte Nachricht erhalten. 

heVeTCSWPeYVaWHaVSReQMthaYVaOeaWHRtatePFaMVaWHKVSTYhtZetheKeetPeJVSZaYPaRRGaReM
WQhMGhMtQaReWGPSReHMtQaRaKeaTtMJTPRGaVaKaeTRaWHatthattMZeTWAWSQWtSWatTVaPMRtRSJ
GSTVReaYVeatCVMUeMWaRGMeWtMJMGCSMWtSJOMeQtheVeQeVetQSVSTWHKPaGARCStRWeaVSWeeBtV
eZMtFSJtheKaGAaWHaPSWYSWeWeaVtheStheVtheRGaPeRQeVeeBGeeHMWYPFhaVHaWHYPSRRFQMtha
PPtheaCCeaVaWGeSJKTVWMRheHYSPHtheQeMYhtSJtheMWReGtQaROeVFVeZaVAaKPeaWHtaAMWYaPP
thMWYRMWtSGSWRMHeVatMSWMGSTPHhaVHPFKPaZeNTCMteVJSVhMRSCMWMSWVeRCeGtMWYMt

Mit diesen ersten Vermutungen kann Eve Muster erkennen, die ihre Entscheidungen bestätigen, wie z. Das ". Darüber hinaus deuten andere Muster auf weitere Vermutungen hin." Rtate " könnte sein " Zustand ", was bedeuten würde R. ~ s . Ähnlich " atthattMZe "könnte erraten werden als" zu dieser Zeit ", nachgebend M. ~ ich und Z. ~ m . Außerdem, " heVe " könnte sein " Hier ", geben V. ~ r . Eve füllt diese Vermutungen aus und erhält: 

hereTCSWPeYraWHarSseQithaYraOeaWHstatePFairaWHKrSTYhtmetheKeetPeJrSmaYPassGasei
WQhiGhitQaseWGPSseHitQasaKeaTtiJTPsGaraKaeTsaWHatthattimeTWAWSQWtSWatTraPistsSJ
GSTrseaYreatCriUeiWasGieWtiJiGCSiWtSJOieQthereQeretQSrSTWHKPaGAsCStsWearSWeeBtr
emitFSJtheKaGAaWHaPSWYSWeWeartheStherthesGaPesQereeBGeeHiWYPFharHaWHYPSssFQitha
PPtheaCCearaWGeSJKTrWisheHYSPHtheQeiYhtSJtheiWseGtQasOerFremarAaKPeaWHtaAiWYaPP
thiWYsiWtSGSWsiHeratiSWiGSTPHharHPFKPameNTCiterJSrhisSCiWiSWresCeGtiWYit

Diese Vermutungen deuten wiederum auf andere hin (zum Beispiel " remarA " könnte sein " Anmerkung ", impliziert EIN ~ k ) und so weiter, und es ist relativ einfach, den Rest der Buchstaben abzuleiten, um schließlich den Klartext zu erhalten. 

hereuponlegrandarosewithagraveandstatelyairandbroughtmethebeetlefromaglasscasei
nwhichitwasencloseditwasabeautifulscarabaeusandatthattimeunknowntonaturalistsof
courseagreatprizeinascientificpointofviewthereweretworoundblackspotsnearoneextr
emityofthebackandalongoneneartheotherthescaleswereexceedinglyhardandglossywitha
lltheappearanceofburnishedgoldtheweightoftheinsectwasveryremarkableandtakingall
thingsintoconsiderationicouldhardlyblamejupiterforhisopinionrespectingit

An dieser Stelle wäre es für Eve eine gute Idee, Leerzeichen und Interpunktion einzufügen: 

Hereupon Legrand arose, with a grave and stately air, and brought me the beetle
from a glass case in which it was enclosed. It was a beautiful scarabaeus, and, at
that time, unknown to naturalists—of course a great prize in a scientific point
of view. There were two round black spots near one extremity of the back, and a
long one near the other. The scales were exceedingly hard and glossy, with all the
appearance of burnished gold. The weight of the insect was very remarkable, and,
taking all things into consideration, I could hardly blame Jupiter for his opinion
respecting it.

In diesem Beispiel aus The Gold-Bug waren Eves Vermutungen alle richtig. Dies wäre jedoch nicht immer der Fall; Die Variation der Statistiken für einzelne Klartexte kann dazu führen, dass anfängliche Vermutungen falsch sind. Es kann notwendig sein , um denselben Weg zurückverfolgen falsche Vermutungen oder die verfügbaren Statistiken in viel mehr Tiefe als die etwas vereinfachte Begründungen in dem obigen Beispiel gegeben zu analysieren.

Es ist auch möglich, dass der Klartext nicht die erwartete Verteilung der Buchstabenhäufigkeiten aufweist. Kürzere Nachrichten weisen wahrscheinlich mehr Variationen auf. Es ist auch möglich, künstlich verzerrte Texte zu konstruieren. Zum Beispiel wurden ganze Romane geschrieben, in denen der Buchstabe " e "Insgesamt - eine Form der Literatur, die als Lipogramm bekannt ist .

Geschichte und Nutzung

Erste Seite von Al-Kindis Manuskript aus dem 9. Jahrhundert über die Entschlüsselung kryptografischer Nachrichten
Arabische Buchstaben Häufigkeitsverteilung .

Die erste bekannte Erklärung der Frequenzanalyse (in der Tat für jede Art von Kryptoanalyse) wurde im 9. Jahrhundert von Al-Kindi , einem arabischen Polymathen , in einem Manuskript zur Entschlüsselung kryptografischer Nachrichten gegeben . Es wurde vermutet, dass eine genaue Textstudie des Korans zuerst ans Licht brachte, dass Arabisch eine charakteristische Buchstabenhäufigkeit hat. Seine Verwendung verbreitete sich, und ähnliche Systeme waren in der Zeit der Renaissance in europäischen Staaten weit verbreitet . Bis 1474 hatte Cicco Simonetta ein Handbuch zur Entschlüsselung von Verschlüsselungen lateinischen und italienischen Textes verfasst.

Kryptographen haben mehrere Schemata erfunden, um diese Schwäche bei einfachen Substitutionsverschlüsselungen zu beseitigen. Diese enthielten:

  • Homophone Substitution : Verwendung von Homophonen - verschiedene Alternativen zu den häufigsten Buchstaben in ansonsten monoalphabetischen Substitutions-Chiffren. Beispielsweise können für Englisch sowohl X- als auch Y-Chiffretext Klartext E bedeuten.
  • Polyalphabetische Substitution , dh die Verwendung mehrerer Alphabete - auf verschiedene, mehr oder weniger umständliche Weise ausgewählt ( Leone Alberti scheint dies als erster vorgeschlagen zu haben); und
  • Polygraphische Substitution , Schemata, bei denen Paare oder Tripletts von Klartextbuchstaben als Substitutionseinheiten und nicht als einzelne Buchstaben behandelt werden, beispielsweise die von Charles Wheatstone Mitte des 19. Jahrhunderts erfundene Playfair-Chiffre .

Ein Nachteil all dieser Versuche, Frequenzzählangriffe abzuwehren, besteht darin, dass die Verschlüsselung und Entschlüsselung komplizierter wird, was zu Fehlern führt. Bekanntlich soll ein britischer Außenminister die Playfair-Chiffre abgelehnt haben, denn selbst wenn Schuljungen erfolgreich zurechtkommen würden, wie Wheatstone und Playfair gezeigt hatten, "könnten unsere Attachés es nie lernen!".

Die Rotormaschinen der ersten Hälfte des 20. Jahrhunderts (zum Beispiel die Enigma-Maschine ) waren im Wesentlichen immun gegen eine einfache Frequenzanalyse. Andere Arten der Analyse ("Angriffe") haben jedoch Nachrichten von einigen dieser Computer erfolgreich dekodiert.

Buchstabenhäufigkeiten in Spanisch.

Die Frequenzanalyse erfordert nur ein grundlegendes Verständnis der Statistik der Klartext-Sprache und einige Fähigkeiten zur Problemlösung sowie, wenn sie von Hand durchgeführt wird, die Toleranz für eine umfassende Buchhaltung von Briefen. Während des Zweiten Weltkriegs (WWII) rekrutierten sowohl die Briten als auch die Amerikaner Codebrecher, indem sie Kreuzworträtsel in großen Zeitungen platzierten und Wettbewerbe veranstalteten, um herauszufinden, wer sie am schnellsten lösen könnte. Einige der von den Achsenmächten verwendeten Chiffren waren mithilfe der Frequenzanalyse zerbrechlich, beispielsweise einige der von den Japanern verwendeten konsularischen Chiffren. Mechanische Methoden zur Briefzählung und statistischen Analyse (im Allgemeinen Maschinen vom Typ IBM- Karte) wurden erstmals im Zweiten Weltkrieg eingesetzt, möglicherweise vom SIS der US-Armee . Heute ist die harte Arbeit der Brief Zählung und Analyse wurde ersetzt durch Computer - Software , die eine solche Analyse in Sekunden ausführen kann. Mit moderner Rechenleistung bieten klassische Chiffren wahrscheinlich keinen wirklichen Schutz für vertrauliche Daten.

Frequenzanalyse in der Fiktion

Teil des Kryptogramms in The Dancing Men

Die Frequenzanalyse wurde in der Fiktion beschrieben. Edgar Allan Poes " The Gold-Bug " und Sir Arthur Conan Doyles Sherlock Holmes- Geschichte " Das Abenteuer der tanzenden Männer " sind Beispiele für Geschichten, die die Verwendung der Frequenzanalyse zum Angriff auf einfache Substitutions-Chiffren beschreiben. Die Chiffre in der Poe-Geschichte ist mit mehreren Täuschungsmaßnahmen verkrustet, aber dies ist mehr ein literarisches Mittel als alles, was kryptografisch bedeutsam ist.

Siehe auch

Weiterführende Literatur

  • Helen Fouché Gaines, "Cryptanalysis", 1939, Dover. ISBN   0-486-20097-3
  • Abraham Sinkov , "Elementare Kryptoanalyse: Ein mathematischer Ansatz", The Mathematical Association of America, 1966. ISBN   0-88385-622-0 .

Verweise

  1. ^ Singh, Simon . "Die schwarze Kammer: Hinweise und Tipps" . Abgerufen am 26. Oktober 2010 .
  2. ^ "Ein funktionierendes Beispiel für die Methode aus Bills " A security site.com " " . Archiviert vom Original am 20.10.2013 . Abgerufen am 31.12.2012 .
  3. ^ Ibrahim A. Al-Kadi "Die Ursprünge der Kryptologie: Die arabischen Beiträge", Cryptologia , 16 (2) (April 1992), S. 97–126.
  4. ^ "In unserer Zeit: Kryptographie" . BBC Radio 4 . Abgerufen am 29. April 2012 .
  5. ^ Kahn, David L. (1996). Die Codebrecher: die Geschichte des geheimen Schreibens . New York: Scribner. ISBN   0-684-83130-9 .

Externe Links