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-ZVerfahren | Z | ld Z | Anmerkungen | |
---|---|---|---|---|
Cäsar | 26 | 4.7 | ||
Monoalphabetische Substitution | 4.03 * 1026 | 88.38 | ohne Einsatz von Homophonen oder Blendern | |
Monoalphabetische Substitution, involutorisch | 7.91 * 1012 | 42.85 | involutorisch meint, dass es nur ein Algorithmus für Ver- und Entschöüsslung gibt (wie bspw. ROT13, Enigma) | |
Playfair | 1.55 * 1025 | 83.68 | nur 25 Buchstaben, I=J | |
Vigenere | 1.41 * 1014 (bei einer Schlüsselwortlänge von 10) | 47 | allg.: Z = 26L und ld Z = 4.7 * L, wobei L = Schlüssellänge | |
Anagramme / Transpositionen | 3.6 * 106 (bei einer Textlänge von 10) | 21.79 | allg. n!, wobei n=Textlänge. Mehrere Klartexte in Lösungsmenge möglich. |