Kombinatorische Komplexität

Die Kombinatorische Komplexität gibt an, wieviele mögliche Permutationen es für den Schlüssel bei einem Verschlüsselungsverfahren gibt und stellt so die Mächtigkeit eines Verschlüsselungsverfahrens dar. Dieser Wert bezieht sich auf Dechiffrierungsversuche via Brute Force-Methode, also die oberste Grenze an nötigen Versuchen, um ein Verfahren zu knacken. Unabhängig davon gibt es natürlich noch andere Methoden der Kryptoanalyse, die sehr viel effizienter und mit weniger Versuchen auskommen. Diese Maximalversuchsanzahl stellt also den worst case (schlechstanzunehmender Fall) dar.

Abhängig von der kombinatorische Komplexität (Z) ist der in bit gemessene Informationsgehalt eines Verschlüsselungsverfahren (ld Z). Es gilt: Z = 2ld Z.

Typische Werte für die kombinatorische Komplexität für einige bekannte Verfahren

Voraussetzung ist die Verwendung eines lat. Alphabet mit 26 Buchstaben A-Z

VerfahrenZld ZAnmerkungen
Cäsar264.7
Monoalphabetische Substitution4.03 * 102688.38ohne Einsatz von Homophonen oder Blendern
Monoalphabetische Substitution, involutorisch7.91 * 101242.85involutorisch meint, dass es nur ein Algorithmus für Ver- und Entschöüsslung gibt (wie bspw. ROT13, Enigma)
Playfair1.55 * 102583.68nur 25 Buchstaben, I=J
Vigenere1.41 * 1014 (bei einer Schlüsselwortlänge von 10)47allg.: Z = 26L und ld Z = 4.7 * L, wobei L = Schlüssellänge
Anagramme / Transpositionen3.6 * 106 (bei einer Textlänge von 10)21.79allg. n!, wobei n=Textlänge. Mehrere Klartexte in Lösungsmenge möglich.


Quellen, Literaturverweise und weiterführende Links

Bauer, Friedrich L.: Entzifferte Geheimnisse, Springer Verlag 1995, S. 171