Der Schlüsselraum
Ein zentrales Konzept der Kryptoanalyse ist der Schlüsselraum. Dieser Begriff bezeichnet die Anzahl möglicher Schlüssel, die bei einem bestimmten Verschlüsselungsverfahren möglich sind.
Die Grösse des Schlüsselraums wird entweder als Anzahl möglicher Schlüssel oder als Wert in angegeben. Gibt es beispielsweise mögliche Schlüssel, so sprechen wir von einem grossen Schlüsselraum.
Das Bit ist die kleinste Einheit in der Informatik. Für jedes Bit gibt es genau zwei Werte, nämlich und . Für eine Zahl, die aus nur einem Bit besteht, gibt es also auch genau diese beiden Werte. Bei einem grossen Schlüsselraum gibt es demnach ebenfalls genau mögliche Schlüssel.
Besteht eine Zahl aber nun beispielsweise aus 5 Bits, dann kann sie verschiedene Werte haben. Umgekehrt können wir fragen: "2 hoch was gibt 32?", oder "Wie oft müssen wir mit sich selbst multiplizieren, um zu erhalten? Die Antwort finden wir mithilfe des binären Logarithmus, .
Bei möglichen Schlüsseln hätten wir demnach einen Schlüsselraum von , denn .
Sie erinnern sich an die Funktionsweise der 👉 Caesar-Chiffre: Wir verschieben das Alphabet um eine fixe Anzahl stellen, repräsentiert durch einen einzelnen Buchstaben als Schlüssel. Die Caesar-Chiffre hat damit also einen Schlüsselraum der Grösse (respektive , wenn wir den Schlüssel A nicht erlauben, da dieser keinen Effekt hat). Sofern ein Angreifer das Verschlüsselungsverfahren kennt, benötigt er also lediglich 26 (oder 25) Versuche, um einen Caesar-verschlüsselten Text ohne Kenntnis des Schlüssels zu knacken.
Wie gross ist der Schlüsselraum der Caesar-Chiffre in ?
Die Caesar-Chiffre ist eine stark eingeschränkte Sonderform der 👉 monoalphabetischen Substitution. Wie viele Schlüsselmöglichkeiten gibt es also bei der allgemeinen Form, bei der wir das Alphabet beliebig umstellen können? Dazu können wir uns vorstellen, dass wir sämtliche Buchstaben von A bis Z je auf einen Zettel schreiben, diese Zettel in eine Urne geben, und sie in zufälliger Reihenfolge Stück für Stück wieder herausziehen.
Beim ersten Zug haben wir Möglichkeiten. Sobald der erste Zettel gezogen ist, haben wir für den zweiten Zug noch Möglichkeiten, dann , und so weiter. Aus den Gesetzen der 👉 Kombinatorik wissen wir, dass wir diese 26 Zettel also in möglichen Reihenfolgen ziehen können. Die mathematische Kurznotation wird als "26 Fakultät" ausgesprochen.
Der Schlüsselraum der monoalphabetischen Substitution hat also eine Grösse von möglichen Schlüsseln (respektive rund , da ).
Wie viele mögliche Schlüssel gibt es bei der 👉 Polybios-Chiffre?
Geben Sie eine Schätzung ab und dokumentieren Sie Ihre Überlegungen. Gehen Sie davon aus, dass wir das lateinische Alphabet ohne die Buchstaben J und V auf ein 5x5 Polybios-Quadrat verteilen, wobei ein Feld leer bleibt.
Wir versuchen ein kryptographisches Verfahren mit der Brute-Force-Methode zu knacken. Angenommen, ein leistungsstarker Computer kann pro Mikrosekunde (ein Millionstel einer Sekunde) einen Schlüssel ausprobieren.
Beurteilen Sie die Machbarkeit dieses Brute-Force-Angriffs, für ein Verfahren, dessen Schlüsselraum 100 Milliarden mögliche Schlüssel erlaubt. Lässt sie sich sinnvoll umsetzen? Begründen Sie Ihre Antwort.