Kryptologie: Mathematische Beschreibung der Zylinder

Kryptologie

Mathematische Beschreibung der Zylinder-Chiffriergeräte

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

Den mathematischen Hintergrund über Permutationen findet man hier als PDF.

Parameter

Zahl der Buchstaben des Alphabets = n = #Σ.
Zahl der Scheiben = q mit 1 ≤ q;
falls alle Scheiben verschieden sein sollen, ist q ≤ (n-1)!.
[Die Erklärung, warum hier nicht etwa n! steht, folgt unten.]
- Jede Scheibe ist durch eine Permutation τ ∈ S(Σ) gekennzeichnet.
- Die Menge der Scheiben ist also als Familie (q-Tupel) (T₁, ..., T_q) ∈ S(Σ)^q beschreibbar.
  (Die Scheiben werden meist mit Nummern versehen; der Schlüssel wird dann durch die entsprechende Nummernfolge beschrieben.)
Zahl der ausgewählten Scheiben = l mit 1 ≤ l ≤ q.
- Ein Schlüssel ist also eine Folge (τ₀, ..., τ_l-1) aus verschiedenen Scheiben der Familie (T₁, ..., T_q).
- Es gibt dafür
  #K = q× (q-1)… (q-l+1) = q!/(q-l)!
  Möglichkeiten (von denen einige identisch sein können, falls es gleiche Scheiben gibt).

Beispiele

JEFFERSON: l = q = 36, #K = 36!, effektive Schlüssellänge ≈ 138.
BAZERIES: l = q = 20, #K = 20!, effektive Schlüssellänge ≈ 61.
M-94: l = q = 25, #K = 25!, effektive Schlüssellänge ≈ 84.
M-138-A: l = 30, q = 100, #K = 100!/70!, effektive Schlüssellänge ≈ 190.

Ver- und Entschlüsselung

Die Verschlüsselung ist polyalphabetisch mit der Periode l.

Achtung: Die Scheiben-beschreibende Permutation τ ∈ S(Σ) darf nicht mit dem durch die Scheibe definierten Substitutionsalphabet σ ∈ S(Σ) verwechselt werden. Der Zusammenhang zwischen beiden wird gleich erklärt.

Ist das Standard-Alphabet Σ wie so oft mit Z/nZ identifiziert, so sieht die Verschlüsselung eines Klartextblocks so aus (bei Verwendung der 1. Generatrix):

a₀	…	a_i		…	a_l-1
		τ_i(0)
		…
Suche Eintrag x mit		τ_i(x)	= a_i
		τ_i(x+1)	= c_i	zugehöriger Geheimtextbuchstabe
		…
		τ_i(n-1)

wobei die mittlere Spalte τ_i(0), …, τ_i(n-1) die Beschriftung der Scheibe Nummer i darstellt.

Also ist

c_i = τ_i(x+1) = τ_iτ_i^-1a_i + 1),

und die zugehörige Entschlüsselungsfunktion wird beschrieben durch

a_i = τ_i(τ_i^-1c_i - 1).

Diese Überlegungen werden zusammengefasst zu:

Satz (von der Zylinder-Chiffrierung). Der Zusammenhang zwischen der Permutation τ ∈ S(Σ), die eine Scheibe beschreibt, und der Permutation σ ∈ S(Σ), die die zugehörige Substitution beschreibt, ist

σ(a) = τ(τ^-1a + 1).

σ^-1(c) = τ(τ^-1c - 1).

Anders ausgedrückt: σ ist eine zyklische Permutation und τ ist die Zykeldarstellung von σ.

Es gibt (n-1)! verschiedene Zyklen der Länge n. Je n Scheibenbeschreibungen τ ∈ S(Σ) liefern dieselbe zyklische Permutation σ ∈ S(Σ). Daher die Einschränkung q ≤ (n-1)! oben.

Beispiel: Sei Σ = {A,…,Z} und eine Scheibe beschrieben durch

τ = QWERTZUIOPASDFGHJKLYXCVBNM.

Dann ist σ die Permutation

       a b c d e f g h i j k l m n o p q r s t u v w x y z
       S N V F R G H J O K L Y Q M P A W T D Z I B E C X U

Autor: Klaus Pommerening, 3. Dezember 1999; letzte Änderung: 9. Januar 2008.