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 = #S.
• 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 t Î S(S) gekennzeichnet.
  • Die Menge der Scheiben ist also als Familie (q-Tupel) (T₁, ..., T_q) Î S(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 (t₀, ..., t_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

1. JEFFERSON: l = q = 36, #K = 36!, effektive Schlüssellänge » 138.
2. BAZERIES: l = q = 20, #K = 20!, effektive Schlüssellänge » 61.
3. M-94: l = q = 25, #K = 25!, effektive Schlüssellänge » 84.
4. 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 t Î S(S) darf nicht mit dem durch die Scheibe definierten Substitutionsalphabet s Î S(S) verwechselt werden. Der Zusammenhang zwischen beiden wird gleich erklärt.

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

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

Also ist

c_i = t_i(x+1) = t_i(t_i^-1a_i + 1),

a_i = t_i(t_i^-1c_i - 1).

Diese Überlegungen werden zusammengefasst zu:

Satz (von der Zylinder-Chiffrierung). Der Zusammenhang zwischen der Permutation t Î S(S), die eine Scheibe beschreibt, und der Permutation s Î S(S), die die zugehörige Substitution beschreibt, ist s(a) = t(t-1a + 1). s-1(c) = t(t-1c - 1). Anders ausgedrückt: s ist eine zyklische Permutation und t ist die Zykeldarstellung von s.

Es gibt (n-1)! verschiedene Zyklen der Länge n. Je n Scheibenbeschreibungen t Î S(S) liefern dieselbe zyklische Permutation s Î S(S). Daher die Einschränkung q £ (n-1)! oben.

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

t = QWERTZUIOPASDFGHJKLYXCVBNM.

       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