Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


23. Kryptologie



Einfache Methoden

Zu den einfachsten (und ältesten) Verschlüsselungsmethoden gehört die Cäsar-Chiffre: Falls ein Buchstabe im Klartext der N-te Buchstabe im Alphabet ist, so ersetze man ihn durch den (N+K)-ten Buchstaben im Alphabet, wobei K eine gewisse feste Zahl ist (Cäsar benutzte K = 3). Die nachfolgende Tabelle zeigt, wie eine Botschaft ATTACK AT DAWN (Angriff in der Morgendämmerung) unter Verwendung dieser Methode mit K = 1 verschlüsselt wird:

      Klartext  :ATTACK AT DAWN
   Chiffretext  :BUUBDLABUAEBXO

Diese Methode ist unzuverlässig, da der Kryptoanalytiker nur den Wert von K zu erraten braucht: Wenn er jede der 26 in Frage kommenden Möglichkeiten ausprobiert, kann er sicher sein, daß er die Botschaft entschlüsseln wird.

Eine weit bessere Methode ist die Verwendung einer allgemeinen Tabelle, um die vorzunehmende Ersetzung zu definieren: Für jeden Buchstaben im Klartext wird in der Tabelle angegeben, welcher Buchstabe im Chiffretext zu verwenden ist. Wenn zum Beispiel in der Tabelle die Beziehung

    ABCDEFGHIJKLMNOPQRSTUVWXYZ
    THEQUICKBROWNFXJMPDVRLAZYG

vorgegeben wird, so wird die Botschaft wie folgt verschlüsselt:

      Klartext  :ATTACK AT DWN
   Chiffretext  :HVVH OTHVTQHAF

Dies ist eine viel leistungsstärkere Methode als die einfache Cäsar-Chiffre, da der Kryptoanalytiker wesentlich mehr (ungefähr 27! > 1028) Tabellen ausprobieren müßte, um eine sichere Entschlüsselung zu gewährleisten. Dennoch lassen sich Chiffren mit »einfacher Substitution« wie diese aufgrund der Häufigkeiten von Buchstaben, die die Sprache aufweist, leicht entschlüsseln. Da zum Beispiel in einem deutschen Text E der häufigste Buchstabe ist, könnte der Kryptoanalytiker beim Entschlüsseln der Botschaft einen guten Anfang finden, indem er den häufigsten Buchstaben im Chiffretext bestimmt und diesen durch E ersetzt. Auch wenn dies eine falsche Wahl sein kann, ist es sicher besser, als alle 26 Buchstaben blind auszuprobieren. Die Situation wird sogar noch günstiger (für den Kryptoanalytiker), wenn auch Kombinationen von zwei Buchstaben (»Digramme«) berücksichtigt werden: Manche Digramme (wie etwa QJ) treten in einem deutschen Text niemals auf, während andere (wie etwa ER) sehr oft vorkommen. Durch Untersuchung der Häufigkeiten von Buchstaben und Buchstabenkombinationen kann ein Kryptoanalytiker eine Chiffre mit einfacher Substitution sehr leicht entschlüsseln.

Eine Möglichkeit, diesen Weg zur Entschlüsselung zu erschweren, besteht in der Verwendung von mehr als einer Tabelle. Ein einfaches Beispiel hierfür ist eine Verallgemeinerung der Cäsar-Chiffre, die Vigenere-Chiffre genannt wird: Ein kurzer, sich wiederholender Schlüssel wird benutzt, um den Wert von K für jeden Buchstaben neu zu bestimmen. Bei jedem Schritt wird der Index des Buchstabens im Schlüssel zum Index des Buchstabens im Klartext addiert, um den Index des Buchstabens im Chiffretext zu bestimmen. Der Klartext aus unserem Beispiel läßt sich mit dem Schlüssel ABC wie folgt verschlüsseln:

     Schlüssel  :ABCABCABCABCAB
      Klartext  :ATTACK AT DAWN
   Chiffretext  :BVWBENACWAFDXP

Zum Beispiel ist der letzte Buchstabe des Chiffretextes ein P, der sechzehnte Buchstabe des Alphabets, da der entsprechende Buchstabe im Klartext ein N (der vierzehnte Buchstabe) und der entsprechende Buchstabe im Schlüssel ein B (der zweite Buchstabe) ist.

Die Vigenere-Chiffre läßt sich offensichtlich noch weiter komplizieren, indem man für jeden Buchstaben im Klartext unterschiedliche allgemeine Tabellen (anstelle einfacher Verschiebungen) verwendet. Ebenso ist es klar, daß die Methode um so besser ist, je länger der Schlüssel ist. Tatsächlich liegt, wenn der Schlüssel ebenso lang ist wie der Klartext, die Vernam-Chiffre vor, die häufiger als einmalige Überlagerung (one-time pad) bezeichnet wird. Dies ist das einzige bekannte nachweisbar sichere Kryptosystem, und es wird Gerüchten zufolge für den »heißen Draht« zwischen Washington und Moskau und andere lebenswichtige Anwendungen benutzt. Da jeder Buchstabe im Schlüssel nur einmal verwendet wird, hat der Kryptoanalytiker keine andere Möglichkeit, als für jede Position der Botschaft jeden möglichen Schlüsselbuchstaben auszuprobieren, was natürlich eine hoffnungslose Situation ist, da dies ebenso schwierig ist wie das Ausprobieren aller möglichen Botschaften. Allerdings führt die nur einmalige Benutzung jedes Buchstabens im Schlüssel offenbar zu einem ernsten Problem hinsichtlich der Verteilung des Schlüssels, und die einmalige Überlagerung ist nur für relativ kurze Botschaften von Nutzen, die selten gesendet werden sollen.

Wenn die Botschaft und der Schlüssel binär kodiert werden, besteht ein gebräuchlicheres Schema für die positionsweise Verschlüsselung in der Benutzung der XOR-Funktion (exklusives Oder): Um den Klartext zu verschlüsseln, wird er (Bit für Bit) mit dem Schlüssel XOR-verknüpft. Eine nützliche Eigenschaft dieser Methode ist, daß die Entschlüsselung die gleiche Operation ist wie die Verschlüsselung: Der Chiffretext ist das Ergebnis der XOR-Verknüpfung von Klartext und Schlüssel, doch eine erneute Anwendung der XOR-Verknüpfung von Chiffretext und Schlüssel liefert wieder den Klartext. Bemerkenswert ist, daß man bei XOR-Verknüpfung von Chiffretext und Klartext den Schlüssel erhält. Dies ist zunächst scheinbar überraschend, doch in Wirklichkeit haben viele kryptographische Systeme die Eigenschaft, daß der Kryptoanalytiker den Schlüssel bestimmen kann, wenn er den Klartext kennt.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]