[JoGu]

Kryptologie

Schlüsselerzeuger mit langen Perioden

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

Schlüsselerzeuger

... sollen hier nicht eingehend behandelt werden. Man erzielt lange Perioden durch Überlagerung einiger paarweise teilerfremden kurzen Perioden, meist realisiert durch Zahnräder mit entsprechend vielen Zähnen, sogenannte Schlüsselräder. Ein gängiges Konstruktionsprinzip ist das Bolzenrad (Stiftwalze, pin wheel), mit einstellbaren Bolzen oder Stiften. Hier werden Bolzen nach links oder rechts geschoben; eine von beiden Positionen ist die aktive, bei der das Nachbarrad zum Weiterdrehen veranlasst wird, die andere Position ist die passive. Eine Illustration von der HAGELIN-Maschine M-209:

[Schlüsselrad]
wo die beiden abgebildeten Räder 26 und 23 verschiedene Positionen einnehmen können.

Die einstellbaren Bolzen können etwa direkt als gesetzte oder nicht gesetzte Bits gedeutet und bei geeigneter mechanischer oder elektrischer Konstruktion für eine XOR-Verschlüsselung verwendet werden.


Perioden

Gegeben seien q Räder die jeweils ni verschiedene Stellungen einnehmen können. Jedes Rad dreht sich bei jedem Verschlüsselungsschritt eine Position weiter. Wird der Zustand des Gesamtsystems durch das q-Tupel der Positionen beschrieben, so ist die Periode der Zustandsänderungen dieses Systems das kleinste gemeinsame Vielfache der einzelnen Perioden.

Die erste nachweisbare Idee, durch Kombination die Periode auf diese Weise zu verlängern, wird VERNAMs Kollegen MOREHOUSE zugeschrieben. VERNAM verwendete ja ursprünglich als Schlüssel einen als Schleife zusammengeklebten Lochstreifen als Schlüssel; MOREHOUSE schlug die Überlagerung mehrerer solcher Lochstreifen vor.

Die Erfindung der Bolzenräder sowie die Kombination mehrerer solcher Räder, deren Periode jeweis eine andere Primzahl ist, wird Parker HITT (1877-1971, amerikanischer Militärkryptologe im ersten Weltkrieg) zugeschrieben, der wohl auch als erster die Erkenntnis formulierte:

»No message is safe in cipher ... unless the key phrase is comparable in length with the message itself.«

Beispiele

Verwendet wurden in historischen Beispielen etwa

Man sieht: eine frühe Anwendung von Primzahlen in der Kryptologie. Allgemein ist die Periode einer Überlagerung das kleinste gemeinsame Vielfache der einzelnen Perioden.


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