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)sÎK von monoalphabetischen Substitutionen mit einem Schlüsselraum K Í S(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).
[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)sÎKvon 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.