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

   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

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_σ(a₁,...,a_r) : = (σa₁,...,σa_r)  für  a = (a₁,...,a_r) ∈ Σ^r.

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

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

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) = ²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).