Kryptologie: Zurechtrücken der Begleitalphabete

Kryptologie

Zurechtrücken der Begleitalphabete

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

Wiederholung

Bei der Beschreibung der PORTA-Chiffre war

f_s,k = f_s ° f_e,k'.

mit k' = f_s^-1(k).

Das wurde bei der Kryptoanalyse aber gar nicht benützt, sondern eine ähnliche Formel der Gestalt:

f_s,k = g ° f_s,

wobei g ein Verrücken und g^-1 das Zurechtrücken der Begleitalphabete bedeutete.

Eine mathematische Beschreibung von g ist gesucht.

Die Alphabet-Tafel war

s₀	s₁	s₂	...	s_n-1

t₀	t₁	t₂	...	t_n-1
t₁	t₂	t₃	...	t₀
.	.	.		.
t_n-1	t₀	t₁	...	t_n-2

mit t_i = s(s_i) für 0 £ i £ l-1, s die Permutation zum Primäralphabet.

Verschiebungen im Primäralphabet

Sei das Alphabet S = {s₀,...,s_n-1} wieder mit Z/nZ identifiziert. Die Indizes werden mod n addiert.

Verschiebungen im Standard- und im Primäralphabet werden dann mathematisch so beschrieben:

t = Verschiebung um 1 im Standardalphabet, t(s_i) = s_i+1.
t^k = Verschiebung um k im Standardalphabet, t^k(s_i) = s_i+k.
sts^-1 = Verschiebung um 1 im Primäralphabet,

.
st^ks^-1 = (sts^-1)^k = Verschiebung um k im Primäralphabet.

Damit läßt sich die alte Formel in die gesuchte umrechnen, zunächst buchstabenweise:

f_s,k(a_i) = st^k_i'(a_i) = (st^k_i's^-1)(sa_i)

Wird mit b Î S^r das monoalphabetische Bild von a bezeichnet, also b_i = s(a_i), so sieht man, dass die gesuchte Funktion g die »Verrückung um k_i' des Primäralphabets« f_k^s ist und die Beschreibung

b_i ® (st^k_i's^-1)(b_i)

hat. Besser gesagt ist es eine Folge von Verrückungen des Primäralphabets.

Mit dieser Überlegung ist gezeigt:

Satz (Kryptoanalyse der PORTA-Chiffre bei bekannter Periode). Die PORTA-Chiffre f_s,k entsteht aus der monoalphabetischen Chiffre f_s durch die Folge f_k^s von Verrückungen des Primäralphabets.

Zusammenfassung

Die kanonische Kryptoanalyse der PORTA-Chiffre f_s,k besteht aus den Schritten:

Bestimmung der Periode.
Zurechtrücken der Begleitalphabete - das ist möglich, ohne das Primäralphabet, also s, zu kennen.
Kryptoanalyse der monoalphabetischen Substitution f_s ohne vorherige Kenntnis von s.

Der Aufwand für die Kryptoanalyse ist übrigens im wesentlichen von der Schlüssellänge unabhängig! Allerdings sinkt die Erfolgswahrscheinlichkeit bei längerer Periode:

Die Wahrscheinlichkeit, nicht-zufällige Parallelstellen zu finden, sinkt.
Die Chance, in den Kolonnen brauchbare Häufigkeitsverteilungen zu finden, sinkt.

Und als Fazit dieser Erkenntnisse für die Sicherheit polyalphabetischer Chiffren:

Je größer die Periode, desto besser die Sicherheit.
Die Wahl von unabhängigen Alphabeten bringt bessere Sicherheit.

Beides führt aber auch zu umständlicherer Handhabung und wurde in der Geschichte der Kryptographie daher oft vermieden.

Autor: Klaus Pommerening, 13. Februar 2000; letzte Änderung: 12. August 2002.

E-Mail an Pommerening@imsd.uni-mainz.de.