[JoGu]

Kryptologie

Die monoalphabetische Substitution

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

Einleitendes Beispiel

Man verwendet als Schlüssel eine Permutation des Alphabets (ein »Tauschalphabet«), etwa konkret in der Gestalt

   ABCDEFGHIJKLMNOPQRSTUVWXYZ
   UNIVERSTABCDFGHJKLMOPQWXYZ
Verschlüsselt wird ein Klartext, indem jeder Buchstabe in der ersten Zeile aufgesucht und durch den darunter stehenden ersetzt wird, im Beispiel so:
   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
die man durch Umsortieren der Schlüsselpermutation erhält.

In der Geschichte der Kryptographie wurden oft als Geheimtextzeichen geheimnisvolle Symbole verwendet (wie z. B. solche). Das ist eine »illusorische Komplikation«, d. h., es erhöht die Sicherheit nicht nennenswert:

FAQ: Wird ein Verschlüsselungsverfahren nicht sicherer, wenn man statt normaler Buchstaben unverständliche Zeichen verwendet?


Mathematische Beschreibung

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

Mathematischer Exkurs über Permutationen: PDF.

Eine monoalphabetische Substitution (oder Buchstabentausch) entsteht aus einer Permutation σ ∈ S(Σ) durch buchstabenweise Anwendung:

fσ(a1,...,ar) : = (σa1,...,σar)  für  a = (a1,...,ar) ∈ Σr.

Definition: Eine monoalphabetische Chiffre über Σ ist eine Familie F = (fσ)σ∈K von monoalphabetischen Substitutionen mit einem Schlüsselraum KS(Σ).


Beispiele

  1. Die Verschiebechiffre mit K = Menge der Rechtstranslationen.
  2. Die allgemeine monoalphabetische Chiffre; hier ist K = S(Σ), also #K = n!, wenn n = #Σ.
  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 [ARGENTI ca. 1580].

Beispiel für diese Regel, die Schlüsselpermutation zu bilden, die im einleitenden Beispiel verwendet wurde:

   UNIVERSITAET
   UNIVERSTA
   UNIVERSTABCDFGHJKLMOPQWXYZ
Fragen: Was ist an diesem Schlüssel schlecht? Wie kann man diese Schwäche vermeiden?

Anwendung

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

Übungsaufgabe: Verschlüssle und entschlüssle ein paar Texte mit Hilfe dieses WWW-Dienstes.

[Die Programme werden auf der nächsten Seite beschrieben und als lokal ausführbare Versionen zum Herunterladen angeboten.]


Die effektive Schlüssellänge

Bei der allgemeinen monoalphabetischen Chiffre ist die Exhaustion, also die vollständige Schlüsselsuche, nicht erfolgversprechend (auch nicht mit Computerhilfe), 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).


Autor: Klaus Pommerening, 29. September 1999; letzte Änderung: 30. Januar 2008.