Kryptologie Die monoalphabetische Substitution

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

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:

f_s(a₁,...,a_r) : = (sa₁,...,sa_r)  für  a = (a₁,...,a_r) Î S^r.

Definition: Eine monoalphabetische Chiffre über S ist eine Familie F = (f_s)_sÎ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.
3. Oft wird aber tatsächlich nur eine eingeschränkte Auswahl von Schlüsseln verwendet, z. B. nach der Regel: Nimm ein Schlüsselwort, streiche alle Buchstaben, die schon weiter vorne vorgekommen sind, und hänge alle nicht benutzten Buchstaben in alphabetischer Reihenfolge an.

Beispiel für diese Regel, die Schlüsselpermutation zu bilden:

   UNIVERSITAET
   UNIVERSTA
   UNIVERSTABCDFGHJKLMOPQWXYZ

Im Beispiel gibt man die Schlüsselpermutation in der Gestalt

   ABCDEFGHIJKLMNOPQRSTUVWXYZ
   UNIVERSTABCDFGHJKLMOPQWXYZ

   PFING STEND ASLIE BLICH EFEST WARGE KOMME N
   JRAGS MOEGV UMDAE NDAIT EREMO WULSE CHFFE G

Für die Entschlüsselung braucht man die Umkehrpermutation

   ABCDEFGHIJKLMNOPQRSTUVWXYZ
   IJKLEMNOCPQRSBTUVFGHADWXYZ

Anwendung

Verschlüsselung und Entschlüsselung per WWW-Formular.

Die effektive Schlüssellänge

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

d(F) = ²log(n!) ³ n × [²log(n) - ²log(e)] » n × ²log(n)

Im Falle n = 26 ist beispielweise

n! » 4 × 10²⁶,   d(F) = ²log(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).

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