Kryptologie: Rotor-Maschinen

Kryptologie

Rotor-Maschinen

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

Allgemeine Beschreibung

Rotormaschinen sind elektromechanische Geräte, die aus mehreren, hintereinandergeschalteten Rotoren (oder »Walzen«) bestehen.

Eine Vorstellung vom Stromlauf durch eine solche Maschine vermittelt das Bild

oder die Seite Rotor Machine Basics von John Savard.

Nach jedem eingegebenen Buchstaben drehen sich die Rotoren unterschiedlich weiter, manche um einen Kontakt, manche vielleicht um mehrere, manche gar nicht.

Die kryptographische Sicherheit der Rotormaschinen beruht – neben der Anzahl der möglichen Rotoren und der Vielzahl der Einstellmöglichkeiten (also der Größe des Schlüsselraums) – auf der Komplexität des Weiterschaltmechanismus der Rotoren.

Bedienung: Eine Taste auf der Schreibmaschinen-Tastatur des Verschlüsselungsgeräts wird gedrückt (= Eingabe eines Klartextbuchstabens). Ein Lämpchen mit einem Buchstaben leuchtet auf (= Ausgabe des zugehörigen Geheimtextbuchstabens). [Aufwendigere Version: Ein Buchstabe wird gedruckt.] Gleichzeitig (etwa beim Loslassen der Taste) drehen sich die Rotoren.

Das geheimnisvoll unregelmäßig drehendende Räderwerk, das bei jedem Anschlag den Tisch erbeben lässt, macht diese Art von Geräten attraktiv – so etwas kann man einem Botschafter oder General als sichere Chiffriermaschine verkaufen.

Rotormaschinen sind der Stand der Verschlüsselungstechnik in der Periode etwa 1920–1960.

Mathematische Beschreibung

Diese abstrakte Beschreibung soll das Funktionsprinzip klar machen. Sie deckt konkrete, historische Rotor-Maschinen nicht notwendig in allen Details ab, da in diese oft individuelle Komplikationen eingebaut wurden.

Das Alphabet Σ wird wie üblich mit Z/nZ, den ganzen Zahlen modulo n, identifiziert. Dann kann man eine Rotor-Maschine durch folgende Parameter charakterisieren:

Eine Menge R ⊆ S(Σ) von p = #R Rotoren (der »Walzenkorb«), jeder davon durch ein Primäralphabet, also eine Permutation ρ_i ∈ S(Σ) beschrieben, die der inneren Verdrahtung des Rotors entspricht.
Eine Auswahl ρ = (ρ₁, ..., ρ_q) ∈ S(Σ)^q mit {ρ₁, ..., ρ_q} ⊆ R von q der Rotoren (»Walzenlage«), wofür es p ⋅ (p-1)…(p-q+1) Möglichkeiten gibt (falls alle Rotoren verschieden verdrahtet sind).
Diese Auswahl dient als »Primärschlüssel«, der für mehrere Nachrichten, z. B. einen Tag lang, ungeändert bleibt.
[Ganz formal ist die Auswahl eine injektive Abbildung des ganzzahligen Intervalls [1..q] nach R.]
Einen Zustandsvektor z = (z₁,...,z_q) ∈ Σ^q, der die aktuelle Rotorstellung beschreibt.
Als »Sekundärschlüssel« dient die Anfangsstellung z⁽⁰⁾, die oft, etwa für jede Nachricht, neu gewählt wird (»Spruchschlüssel«); dafür gibt es n^q Möglichkeiten.
Eine Zustandsänderungsfunktion
g: N × Σ^q → Σ^q,
die den Zustand z⁽ⁱ⁾, in dem der i-te Buchstabe verschlüsselt wird, in den Zustand
z⁽ⁱ⁺¹⁾ = g(i,z⁽ⁱ⁾)
überführt. (Weiterschalt-Mechanismus oder Steuerlogik, realisiert z. B. durch mehr oder weniger komplizierte Zahnradgetriebe.)
Die aktuelle Substitution im Zustand z:
σ_z = ρ_q^(z_q) °…° ρ₁^(z₁) ∈ S(Σ) mit ρ_j^(z_j) = τ^z_j ° ρ_j ° τ^-z_j.
Der Klartext a_i ∈ Σ^r wird also nach der Vorschrift
c_i = σ_z⁽ⁱ⁾(a_i)
verschlüsselt.

Ideal wäre es, wenn die Abbildung

Σ^q → S(Σ), z → σ_z,

injektiv wäre. Darüber gibt es allerdings keine brauchbaren allgemeinen Aussagen.

Ver- und Entschlüsselung

Ausführlich geschrieben sieht die Verschlüsselungsfunktion so aus:

c_i = τ^z_q⁽ⁱ⁾ ° ρ_q ° τ^{z_q-1⁽ⁱ⁾-z_q⁽ⁱ⁾} ° ... ° τ^{z₁⁽ⁱ⁾-z₂⁽ⁱ⁾} ° ρ₁ ° τ^{-z₁⁽ⁱ⁾} (a_i)

und die entsprechende Entschlüsselungsfunktion so:

a_i = τ^{z₁⁽ⁱ⁾} ° ρ₁^-1 ° τ^{z₂⁽ⁱ⁾-z₁⁽ⁱ⁾} ° ... ° τ^{z_q⁽ⁱ⁾-z_q-1⁽ⁱ⁾} ° ρ_q^-1 ° τ^{-z_q⁽ⁱ⁾} (c_i)

Die Entschlüsselung geschieht selbstverständlich einfach dadurch, daß der Strom in umgekehrter Richtung durch die Rotoren geschickt wird, d. h., Tastatur und Lampensatz müssen vertauscht angestöpselt werden; die Reihenfolge der Zustände ist die gleiche wie bei der Verschlüsselung.

Beschreibung als endlicher Automat

Abstrakt wird eine Rotor-Maschine so beschrieben:

Meist ist die Zustandsänderungsfunktion vom Schritt i unabhängig. D. h., wir können einfacher annehmen

g: Σ^q → Σ^q.

Einschub: Perioden von Zustandsänderungen

Der Schlüsselraum

Ein Schlüssel besteht nach der obigen Beschreibung aus

einer Auswahl der Rotoren,
einem Anfangszustand.

Die Größe des Schlüsselraums ist also

#K = n^q ⋅ p!/(p-q)!.

In einem typischen Fall (Hebern-Maschine) ist p = q = 5, n = 26, #K = 120⋅26⁵ = 712 882 560, und die effektive Schlüssellänge d(F) ≈ 29.4. Das war 1920 groß genug, ist gegen einen computerbesitzenden Angreifer aber völlig ungenügend.

Beispiele für die Steuerlogik

Autor: Klaus Pommerening, 31. Dezember 1999; letzte Änderung: 17. Dezember 2007.