Playfair

Der Erfinder der Playfair-Verschlüsselung Sir Charles Wheatstone

Die Playfair-Verschlüsselung ist eine 1854 von Charles Wheatstone erfundene klassische Verschlüsselungsmethode, bei der jedes Buchstabenpaar des Klartextes durch ein anderes Buchstabenpaar ersetzt wird. Sie gehört damit zur Klasse der bigraphischen monoalphabetischen Substitutionsverfahren.

Berühmt wurde sie unter dem Namen eines guten Bekannten von Wheatstone, Lyon Playfair, der diese Methode zur Benutzung beim britischen Militär empfahl.

Geschichte

Die Playfair-Verschlüsselung wurde erstmals im Krimkrieg (1853–1856) eingesetzt und war bis zum Ersten Weltkrieg (1914–1918), in modifizierter Form sogar noch während des Zweiten Weltkriegs (1939–1945), in Gebrauch.

Zum Zeitpunkt ihrer Erfindung war die Playfair-Verschlüsselung im Vergleich zu den damals üblichen, auf der Verschlüsselung von Einzelzeichen basierenden Methoden ein sehr sicheres Verfahren. Dies änderte sich jedoch im frühen 20. Jahrhundert. So konnten ab Mitte 1915 die von den Briten mit Playfair verschlüsselten Nachrichten von der deutschen Gegenseite häufig entziffert werden, umgekehrt brachen britische Codeknacker im englischen Bletchley Park die von deutschen Militärs etwas abgewandelten Playfair-Verschlüsselungen im Zweiten Weltkrieg.

In der heutigen Zeit muss sie als ein äußerst unsicheres Verschlüsselungsverfahren bezeichnet werden. So gelingt es, selbst extrem kurze Texte, deren Länge kaum oberhalb der Unizitätslänge von 23 Buchstaben liegt,[1] mithilfe moderner computergestützter Methoden relativ mühelos zu brechen.[2]

Verfahren

Lyon Playfair, unter dessen Namen diese Verschlüsselungs-Methode bekannt wurde

Bei der Playfair-Methode handelt es sich um eine Substitution, die monoalphabetisch und bigraphisch ist, das heißt, es kommt nur ein einziges (mono von griechisch monos für „allein“ oder „einzig“) festes Alphabet zur Anwendung (Gegensatz: Polyalphabetische Substitution) und als zu verschlüsselnde Symbole werden Bigramme, also jeweils ein Paar (zwei) Buchstaben benutzt (Gegensatz: Monographische Verfahren, die auf Einzelzeichen beruhen).

Vorbereitung des Klartextes

Als Beispiel wird ein englischer Klartext verschlüsselt, der aus dem amerikanischen Spielfilm Das Vermächtnis des geheimen Buches stammt. Er lautet:

Laboulaye lady will lead to Cibola temples of gold“.

(Deutsch: „Die Laboulaye-Dame wird [dich] zu den Cibola-Tempeln aus Gold führen.“)

Der obige Klartext wird zum Zwecke der Verschlüsselung in Bigrammen geschrieben. Man verwendet nur Großbuchstaben, etwaige Umlaute werden aufgelöst und Leerzeichen sowie Satzzeichen werden weggelassen. „J“ wird zu „I“ umgewandelt. Bei der Bildung der Bigramme wird darauf geachtet, dass keine aus zwei identischen Buchstaben entstehen, wie beispielsweise „LL“. Um dies zu vermeiden, wird gegebenenfalls ein „X“ (oder ein anderer seltener Buchstabe wie beispielsweise „Q“) eingefügt. Tritt am Ende des Textes ein einziger Buchstabe allein auf, so wird er durch Anhängen eines weiteren „X“ (oder „Q“) zu einem Bigramm erweitert. Der zur Verschlüsselung vorbereitete Klartext hat damit die folgende Form:

LA BO UL AY EL AD YW IL LX LE AD TO CI BO LA TE MP LE SO FG OL DX

Playfair-Quadrat

Aus einem Schlüsselwort (oder Schlüsselsatz) wird ein permutiertes Alphabet mit 25 Buchstaben (ohne J) gewonnen. Dazu wird der Schlüssel buchstabenweise von oben links beginnend zeilenweise in eine 5×5-Matrix eingetragen, wobei bereits eingetragene Buchstaben im Folgenden ausgelassen werden. Danach werden die fehlenden Buchstaben in alphabetischer Reihenfolge ergänzt. So erhält man eine quadratische Anordnung aller 25 Buchstaben, die Playfair-Quadrat genannt wird.

Als Beispiel zur Erzeugung eines Playfair-Quadrats wird hier das Schlüsselwort „DEATH“ (deutsch: Tod) benutzt.

Schlüssel: DEATH
D E A T H  ← Eintragen des Schlüsselworts
B C F G I  ← Danach Auffüllen durch die restlichen Buchstaben
K L M N O
P Q R S U
V W X Y Z

Verschlüsselung

Grundlage für die Verschlüsselung ist das mithilfe des Kennworts (hier: DEATH) erzeugte Playfair-Quadrat und der in Bigramme zerlegte Klartext. Es werden immer Klartext-Bigramme in Geheimtext-Bigramme umgewandelt, also Buchstabenpaare als Buchstabenpaare verschlüsselt.

Stehen beide Buchstaben in derselben Spalte oder in derselben Zeile, werden jeweils die unteren beziehungsweise rechten Nachbarbuchstaben als Geheimbuchstaben genommen. Sollten die Buchstaben am Rand des Playfair-Quadrats stehen, wird einfach am anderen Rand fortgesetzt. Das Quadrat ist also links und rechts sowie oben und unten als verbunden anzunehmen, also topologisch auf einem Torus aufgewickelt zu denken.

Aus dem Klartext-Bigramm EL wird so, wie unten zu erkennen, das Geheimtext-Bigramm CQ (die beiden unteren Nachbarn von E und L). Analog wird AD als TE verschlüsselt (die beiden rechten Nachbarbuchstaben zu A und D).

* E * * *         D E A T *
* C * * *         * * * * *
* L * * *         * * * * *
* Q * * *         * * * * *
* * * * *         * * * * *
EL → CQ           AD → TE

Stehen die beiden Buchstaben des Klartext-Bigramms hingegen in unterschiedlichen Zeilen und Spalten, so ersetzt man den ersten Klarbuchstaben durch den in derselben Zeile, aber in der Spalte des zweiten liegenden. Der zweite Klarbuchstabe wird durch den in derselben Zeile, aber in der Spalte des ersten Klarbuchstabens ersetzt. Das Klartextpaar bildet also die diagonal gegenüber liegenden Ecken eines Rechtecks. Das Geheimtextpaar wird aus den übrigen beiden Ecken dieses Rechtecks erzeugt. Zum Beispiel bilden die beiden ersten Buchstaben LA des Klartextes im Playfair-Quadrat, wie unten zu erkennen, zwei Ecken eines Rechtecks, in dessen beiden übrigen Ecken die Buchstaben M und E stehen. Dies sind die gesuchten Geheimtext-Buchstaben.

* E A * *
* * * * *
* L M * *
* * * * *
* * * * *
LA → ME

Insgesamt ergibt sich im Beispielfall folgende Playfair-Verschlüsselung:

Klartext:   LA BO UL AY EL AD YW IL LX LE AD TO CI BO LA TE MP LE SO FG OL DX
Geheimtext: ME IK QO TX CQ TE ZX CO MW QC TE HN FB IK ME HA KR QC UN GI KM AV

Entschlüsselung

Die Entschlüsselung ist die Umkehrung der Verschlüsselung. Ebenso wie der Verschlüssler erzeugt auch der Entschlüssler mithilfe des ihm bekannten Kennworts, das den Schlüssel repräsentiert, das identische Playfair-Quadrat. Anschließend wird zur Entschlüsselung des Geheimtextes sinngemäß die gleiche Methode wie bei der Verschlüsselung des Klartextes verwendet. In den Fällen, bei denen beide Geheimtextbuchstaben in derselben Spalte oder Zeile des Quadrats stehen, wird allerdings der obere beziehungsweise linke Nachbar ausgewählt, um so den Verschlüsselungsschritt umzukehren. Im Fall des Überkreuz-Schrittes ist das Verfahren für die Entschlüsselung identisch mit der Verschlüsselung.

Entzifferung

Die Playfair-Verschlüsselung stellt eine Substitution für Buchstaben-Paare dar. Es handelt sich um eine bigraphische monoalphabetische Methode. Ähnlich wie bei der einfachen (monographischen) Buchstabensubstitution beruhen Methoden zur Entzifferung von Playfair im Wesentlichen auf einer Analyse der Häufigkeitsverteilung hier der Buchstabenpaare (Bigramme). In der deutschen Sprache beispielsweise sind die Bigramme „er“, „en“ und „ch“ sehr häufig. Im Beispieltext fallen die „Doppler“ (also Bigramm-Wiederholungen) ME…ME, IK…IK, QC…QC und TE…TE sowie die „Reversen“ (Wiederholung eines umgedrehten Bigramms) CQ…QC auf, die sich in gleicher Weise im englischen Klartext wiederfinden.

Da kein Buchstabe mit sich selbst gepaart wird, gibt es nur 600 (25×24) mögliche Buchstabenkombinationen, die substituiert werden. Überdies gibt es eine Reihe von Symmetrien, die teilweise schon am obigen Beispieltext erkannt werden können. So hilft der erwähnte Klartext-Geheimtext-Zusammenhang EL ↔ CQ und LE ↔ QC beim Bruch des Textes. Ist nämlich ein Bigramm geknackt, dann ist auch sofort das reverse (umgedrehte) Bigramm bekannt. In den Fällen des Überkreuz-Schrittes gibt es darüber hinaus noch weitere Beziehungen zwischen den vier auftretenden Buchstaben in der Art (vgl. beispielsweise obere linke Ecke des Quadrats) DC ↔ EB, CD ↔ BE, EB ↔ DC sowie BE ↔ CD, die der Angreifer zur Entzifferung ausnutzen kann. Ferner hat auch die geschilderte Methode zur Erzeugung des Playfair-Quadrats Schwächen, denn es endet häufig – wie auch im Beispiel – auf „XYZ“.

Die Playfair-Verschlüsselung ist somit weit entfernt von einer allgemeinen bigraphischen Methode mit völlig willkürlicher Zuordnung der Buchstabenpaare und stellt in der heutigen Zeit kein sicheres Verschlüsselungsverfahren mehr dar. So lassen sich mit modernen Mitteln auch relativ kurze Playfair-Texte in sehr kurzer Zeit brechen.

Die erste Veröffentlichung zur Entzifferung von Playfair stammt aus dem Jahr 1914 und wurde vom US-amerikanischen Kryptoanalytiker Joseph O. Mauborgne verfasst.

Eine literarische Darstellung der Playfair-Verschlüsselung und ihrer Entzifferung findet sich im Kriminalroman „Have His Carcase“ (deutsch: „Zur fraglichen Stunde“) von Dorothy L. Sayers.

Literatur

  • Elonka Dunin, Magnus Ekhall, Konstantin Hamidullin, Nils Kopal, George Lasry, Klaus Schmeh: How we set new world records in breaking Playfair ciphertexts. Cryptologia, 2021, doi:10.1080/01611194.2021.1905734.
  • Rudolf Kippenhahn: Verschlüsselte Botschaften. Geheimschrift, Enigma und Chipkarte (= Rororo 60807 Sachbuch. rororo science). Rowohlt-Taschenbuch-Verlag, Reinbek bei Hamburg 1999, ISBN 3-499-60807-3.
  • Fred B. Wrixon: Codes, Chiffren & andere Geheimsprachen. Von den ägyptischen Hieroglyphen bis zur Computerkryptologie. Könemann, Köln 2000, ISBN 3-8290-3888-7, S. 217ff.

Weblinks

  • Handbuch 34-40-2 der US-Armee enthält in Kapitel 7 auch Anleitungen zur Entzifferung der Playfair-Verschlüsselung und verwandter Verfahren (englisch)

Einzelnachweise

  1. Cipher A. Deavours: Unicity Points in Cryptanalysis. Cryptologia, 1 (1), Jan. 1977, S. 49
  2. Elonka Dunin, Magnus Ekhall, Konstantin Hamidullin, Nils Kopal, George Lasry, Klaus Schmeh: How we set new world records in breaking Playfair ciphertexts. Cryptologia, 2021, doi:10.1080/01611194.2021.1905734.

Auf dieser Seite verwendete Medien