2a. Kryptographische Basistechniken

Die monoalphabetische Substitution


Mit S(S) wird die Gruppe der Permutationen des Alphabets S bezeichnet, also die »volle symmetrische Gruppe«.

Eine monoalphabetische Substitution entsteht aus einer Permutation s Î S(S) durch buchstabenweise Anwendung:

fs(a1,...,ar) : = (sa1,...,sar)  für  a = (a1,...,ar) Î Sr.

Definition: Eine monoalphabetische Chiffre über S ist eine Familie F = (fs)K von monoalphabetischen Substitutionen mit einem Schlüsselraum K Í S(S).


Beispiele

  1. Die Verschiebechiffre mit K = Menge der Rechtstranslationen.
  2. Die allgemeine monoalphabetische Chiffre; hier ist K = S(S), also #K = n!, wenn n = #S.

Bei der allgemeinen monoalphabetischen Chiffre ist die vollständige Schlüsselsuche (auch mit Computerhilfe) nicht erfolgversprechend, da

d(F) = 2log(n!) ³ n × [2log(n) - 2log(e)] » n × 2log(n)
nach der STIRLING-Formel.

Im Falle n = 26 ist beispielweise

n! » 4 × 1026,   d(F) = 2log(26!) » 88.38.

Anmerkung. Falls nicht alle Buchstaben im Geheimtext vorkommen, ist der Suchaufwand entsprechend kleiner, da nicht der gesamte Schlüssel bestimmt werden muss (und kann).


Polyalphabetische Substitution

[Verbesserung der monoalphabetischen Substitution]

Eine Folge von Permutationen

s = (s1, s2, ..., sr), si Î S(S),
wird buchstabenweise angewendet (evtl. periodisch wiederholt):
fs(a1, ...,ar) : = (s1a1, ...,srar)  für a = (a1,...,ar) Î Sr.
Das nennt man polyalphabetische Substitution.

Definition: Eine polyalphabetische Chiffre über S ist eine Familie

F = (fs)K
von polyalphabetischen Substitutionen mit einem Schlüsselraum K Í (S(S))r.

[Je nachdem, ob r endlich oder unendlich ist, spricht man von »periodischer« oder »aperiodischer« polyalphabetischer Chiffre.]

Beispiel: XOR mit »fortlaufendem« Schlüssel.


Vorlesung Datenschutz und Datensicherheit
Autoren: Klaus Pommerening, Marita Sergl, 29. September 1999; letzte Änderung: 20. Mai 2004.
E-Mail an
Pommerening »AT« imbei.uni-mainz.de.