KryptologieRotor - Mathematische Beschreibung |
|
Das Alphabet S wird wieder mit Z/nZ, den ganzen Zahlen modulo n identifiziert.
Sei r die monoalphabetische Substitution, die durch die Grundstellung des Rotors bewirkt wird.
In der um eine Stelle rotierten Position (siehe obiges Beispiel) wird dann die Substitution
r(1)(a) = r(a-1) + 1ausgeführt. [Dies ergibt die Zeile 1 in der Substitutionstabelle.]
Bezeichnet man mit t die Verschiebung des Standard-Alphabets S = Z/nZ um 1 (also t(a) = a+1), so wird die Formel zu
r(1)(a) = trt-1(a).
Durch Induktion folgt sofort Teil (i) von:
Satz (von den Begleitalphabeten des Rotors).
(i) Bewirkt ein Rotor in
Grundstellung die Substitution mit dem Primäralphabet r,
so bewirkt er in der um t Stellen rotierten Position die
Substitution mit dem konjugierten Alphabet
r(t) = ttrt-t.Insbesondere sind alle Begleitalphabete vom gleichen Zykel-Typ. (ii) In der zugehörigen polyalphabetischen Substitutionstabelle enthalten die Diagonalen jeweils ein (zyklisch fortgesetztes) Standard-Alphabet. |
Der Beweis von Teil (ii) folgt direkt, wenn man die Aussage als Formel interpretiert:
r(i)(j) = tirt-i(j) = r(j-i) + i = r(i-1)(j-1) + 1.¨
Erläuterung zum »Zykel-Typ«: Jede Permutation lässt sich, eindeutig bis auf die Reihenfolge, als Produkt von disjunkten Zykeln = zyklischen Permutationen schreiben. Der Zykel-Typ ist das n-Tupel
(l1, ..., ln) mit li = Anzahl der Zykeln der Länge i,wobei n allgemein die Größe der zu permutierenden Menge, bei uns also das Alphabet S, ist.
[Insbesondere ist l1 + 2l2 + ... + nln = n.]
Hier gibt's ein Perl-Programm, das eine Ein-Rotor-Chiffre durchführt.