[JoGu]

Kryptologie

Ansätze zur Kryptoanalyse von Rotor-Maschinen

a7Hzq .#5r<
kÜ\as TâÆK$
ûj(Ö2 ñw%h:
Úk{4R f~`z8
¤˜Æ+Ô „&¢Dø

Die Kryptoanalyse ist sehr komplex und von den Details der jeweiligen Maschine abhängig. Hier werden nur einige allgemeine Ansätze behandelt. Für eine ausführliche Darstellung sei auf das Buch von Deavours und Kruh im Literaturverzeichnis verwiesen.


Superimposition

… ist anwendbar, wenn mehrere Geheimtexte vorliegen, die mit dem gleichen Schlüssel erstellt wurden. Diese werden untereinander geschrieben. Dabei entstehen monoalphabetisch verschlüsselte Kolonnen.

In der Praxis wird dies durch den mit jeder Nachricht wechselnden Spruchschlüssel (= variabler Anfangszustand) verhindert. Aber auch dann treten bei hohem Nachrichtenaufkommen immer wieder Abschnitte in verschiedenen Nachrichten auf, die mit dem gleichem Schlüssel verschlüsselt wurden. Mit Zeichenkoinzidenz-Bestimmung werden solche Abschnitte zuverlässig erkannt.

Dieser Ansatz benötigt so weit keinen bekannten Klartext.


Erkennen eines schnellen Ausgangsrotors

Hier wird angenommen, dass die Menge der Rotoren, also der Walzenkorb, bekannt ist, aber nicht die verwendete Auswahl von Rotoren. Bekannter Klartext wird nicht benötigt.

Der Angriff ist durchführbar, wenn der Ausgangsrotor sich bei jedem Schritt um eine Position weiterdreht, die anderen Rotoren wesentlich seltener.

Die Rotoren seien von 1 (= Eingangsrotor) bis q (= Ausgangsrotor) nummeriert; in dieser Reihenfolge sollen sie auch durchquert werden.

Nun sei ein Abschnitt der Länge m gegeben, in dem nur der Rotor q bewegt wird. Die Substitution μ, die von den Rotoren 1 bis q-1 bewirkt wird, ist dann in diesem Abschnitt konstant. Die Verschlüsselung folgt, wenn die Indizes der Einfachheit halber in diesem Abschnitt als 1 bis m gewählt werden, dann dem Schema

[Zählwerk]

a1 b1 := μ(a1) ρq(z1)μ(a1) = c1
a2 b2 := μ(a2) ρq(z1+1)μ(a2) = c2
am bm := μ(am) ρq(z1+m-1)μ(am) = cm

Somit ist b = (b1,…,bm) ∈ Σm monoalphabetisches Bild von (a1,…,am). Es ist aber auch

b1 = [ρq(z1)]-1(c1),
b2 = [ρq(z1+1)]-1(c2),
bm = [ρq(z1+m-1)]-1(cm).

Damit lässt sich eine reduzierte Exhaustion für den Rotor q mit p Möglichkeiten und seine Anfangsstellung z1 im betrachteten Abschnitt mit jeweils n Möglichkeiten durchführen.

Damit ist der Ausgangsrotor und sein Zustand im betrachteten Abschnitt identifiziert. Der Aufwand hierzu bestand aus np Bestimmungen von Koinzidenzindizes von Texten der Länge m.

Bemerkungen

  1. Die Methode wird in der Regel am Anfang eines Textes angewendet.
  2. Falls im gewählten Abschnitt nicht alle anderen Rotoren still stehen, aber doch nur ein weiterer Rotor genau einmal die Position ändert, besteht b aus zwei verschiedenen monoalphabetischen Stücken. Auch dies ist in der Regel noch am Koinzidenzindex φ(b) erkennbar.

Weiterführung des Angriffs

Sobald der schnelle Rotor identifiziert ist, kann man den durch ihn bewirkten Effekt wie eine Überverschlüsselung abstreifen. Der oben verwendetete »Zwischen-Geheimtext« b1, …, bm wird dadurch zu einem Geheimtext c' ∈ Σr verlängert, der mit einer wesentlich einfacheren Maschine erstellt wurde.

Ist die Steuerlogik z. B. ein Zählwerk und der Text lang genug (etwa mindestens ≈ n2), so lassen sich sukzessiv weitere Rotoren erkennen und abstreifen.

Oder man versucht, die monoalphabetischen Stücke, aus denen c' zusammengesetzt ist, einzeln zu dechiffrieren. Das sind z. B. ⌊r/n⌋ Stücke der Länge n und ein Reststück der Länge r mod n.


Angriff mit bekanntem Klartext

(oder mit wahrscheinlichem Wort)

Erkennen eines schnellen Ausgangsrotors

… ist damit wie oben, aber ohne Berechnung von Koinzidenzindizes, möglich: Man prüft, ob b1, …, bm dasselbe numerische Muster zeigt wie a1, …, am.

Die Angriffsmethode, einen Zwischenschritt einer Verschlüsselung von beiden Seiten aus zu betrachten, nennt man auch »Meet in the Middle«.

Erkennen eines schnellen Eingangsrotors

Analog zu oben ist die Situation hier:

[inverses Zählwerk]

a1 b1 := ρ1(z1) (a1) μ(b1) = c1
a2 b2 := ρ1(z1+1) (a2) μ(b2) = c2
am bm := ρ1(z1+m-1) (am) μ(bm) = cm

Damit ist (b1,…,bm) monoalphabetisches Bild von (c1,…,cm).

Also hat man nur alle p Rotoren mit jeweils allen n Anfangsstellungen durchzuprobieren, bis die numerischen Muster von (b1,…,bm) und (c1,…,cm) übereinstimmen. Da Texte mit gleichem numerischen Muster auch »Isomorphe« genannt werden, nennt man dieses Vorgehen »Methode der Isomorphe«.


Autor: Klaus Pommerening, 13. Februar 2000; letzte Änderung: 22. Dezember 2007.