Channel Security

Wie die Vigenère-Chiffre (siehe About Security #68) gebrochen werden kann, erfahren Sie in dieser Folge. Danach lernen Sie mit dem One-Time-Pad das einzig beweisbar absolut sichere Verfahren kennen.

Vigenère-Chiffre brechen

Für das Brechen einer Vigenère-Chiffre wird der Geheimtext in mehrere Teiltexte aufgespalten. Wenn die Länge n des Schlüsselwortes bekannt ist, werden nur die Geheimtextzeichen an den Positionen 1, (n+1), (2n+1),... betrachtet. Diese Teilmenge ist normal Cäsar-chiffriert, da immer der gleiche Buchstabe zum Klartextzeichen addiert wurde, und kann mit statistischen Verfahren angegriffen werden. Ebenso wird mit der Teilmenge aus den Geheimtextzeichen an den Positionen 2, (n+2), (2n+2),... verfahren, usw. usf.. Die Länge des Schlüsselworts wird ermittelt, indem verschiedene Längen ausprobiert und die Häufigkeitsverteilungen der Teilmengen betrachtet werden.

Im Beispiel aus About Security #68 ergibt sich diese Aufteilung (vorausgesetzt, die Länge des Schlüsselworts (5) ist bereits bekannt).

Allgemeine Polyalphabetische Substitution

Eine Verbesserung der Vigenère-Chiffre ist die Allgemeine Polyalphabetische Substitution. Dabei werden statt der Cäsar-Chiffrierung allgemeine Substitutionen der Reihe nach auf die einzelnen Klartextzeichen angewendet, nach der letzten wird mit der ersten fortgefahren. Die Anzahl der verwendeten Substitutionen wird als Periode des Verfahrens bezeichnet. Bei der Analyse des Verfahrens wird genau wie bei der Vigenère-Chiffre vorgegangen, nur muss für jede Teilmenge die darauf angewandte Substitution ermittelt werden. Um das Entschlüsseln zu erschweren, werden möglichst viele mögliche Substitutionen vorgesehen, entsprechend einer möglichst langen Periode. Der Hintergedanke dabei ist, dass der dem Angreifer zur Verfügung stehende Geheimtext für eine statistische Analyse hoffentlich zu kurz ist.

Das Verfahren wurde in den so genannten Rotormaschinen umgesetzt, z.B. in der von Deutschland während des Zweiten Weltkriegs verwendeten Enigma.

Der Vorteil polyalphabetischer Substitutionen ist, dass sie sich leicht synchronisieren lassen. Da die Substitutionen nur von der Position im Text abhängig sind, sind bei einem Übertragungsfehler nur die beschädigten Zeichen nicht zu entschlüsseln. Auch wenn die Länge des beschädigten Geheimtextabschnitts unbekannt ist, lässt sich die Entschlüsselung danach relativ problemlos wieder synchronisieren: Wenn der entschlüsselte Text lesbar ist, hat man den Anschluss gefunden.

Vernam-Chiffre

Eine besonders einfache Variante der polyalphabetischen Substitutionen ist die bitweise Vigenère-Verschlüsselung, oft auch Vernam-Chiffre genannt. Während bisher die 26 Buchstaben des lateinischen Alphabets betrachtet und modulo 26 gerechnet wurde, wird nun mit Bits gerechnet. Ein Bit ist ein Buchstabe des Alphabets aus 0 und 1, die Addition modulo 2 in diesem Alphabet entspricht dem XOR (exklusives ODER, ):

0 0 = 0
0 1 = 1 = 1 0
1 1 = 0

Der Schlüssel ist wieder eine endliche Zeichenfolge, die wie der Klartext als Bitfolge aufgefasst und nicht zeichen-, sondern bitweise addiert wird. Die Dechiffrierung erfolgt durch eine erneute Chiffrierung, da

(a b) b = a

gilt.

Wie bei der Verschlüsselung ändert sich auch bei der Kryptanalyse nichts Grundlegendes.

One-Time-Pad

Alle bisher vorgestellten Verfahren haben einen Nachteil: Sie sind mit mehr oder weniger Aufwand zu brechen. Alle – bis auf eines: Wird für die Vernam-Chiffre ein Schlüssel verwendet, der mindestens genauso lang wie der Klartext ist und aus zufälligen Zeichen besteht, so ist das Ergebnis nicht zu brechen. Da jeder Teil des Schlüssels nur ein einziges Mal verwendet wird, wird das Verfahren als One-Time-Pad bezeichnet.

Ein Beispiel:

diesistderklartext
AFRWJIVTQYMODWEBKSCLKRGBZUWBDXZ

Wie schon bei der Cäsar-Chiffre werden übereinander stehende Zeichen addiert und ergeben folgenden Geheimtext:

DNVORAOWUPWZDNXFHL

Statt buchstabenweise wird im Computer bitweise verschlüsselt. Dies hat zwei Vorteile: XOR ist eine Grundoperation von Mikroprozessoren, die Rechenoperation für den Computer also sehr einfach durchzuführen, und es lassen sich beliebige Datenströme chiffrieren statt nur Texte ohne Sonderzeichen.

Warum ist dieses Verfahren absolut sicher, während die Vernam-Chiffre doch unsicher ist? Der entscheidende Faktor ist der Schlüssel: Da er nur einmal verwendet wird und nichts über ihn bekannt ist, könnte jeder Klartext mit gleicher Wahrscheinlichkeit den zu analysierenden Geheimtext ergeben haben. Während die anderen vorgestellten Verfahren Schlüssel fester Länge verwenden und dadurch zwangsläufig Gesetzmäßigkeiten entstehen, gibt es beim One-Time-Pad keine.

Zwei Probleme erschweren den Einsatz des One-Time-Pads:

1. Es muss ein 'echt zufälliger' Schlüssel verwendet werden, der keinerlei Gesetzmäßigkeit enthält. Die von einem Computer erzeugten Pseudozufallszahlen werden durch Algorithmen erzeugt, enthalten also zwangsläufig Gesetzmäßigkeiten.
2. Der Schlüssel muss sicher zwischen Sender und Empfänger ausgetauscht werden, und der Schlüssel ist genau so lang wie der Klartext. Um also z.B. 5.000 Zeichen Klartext zu verschlüsseln, müssen vorher 5.000 Schlüsselzeichen ausgetauscht worden sein. Dann kann man aber auch den Klartext direkt austauschen.

Hiermit endet die Vorstellung klassischer Verfahren. Ab der nächsten Folge geht es um aktuell eingesetzte Systeme.

Carsten Eilers

About Security – Übersicht zum aktuellen Thema "Kryptographie – Grundlagen"

• About Security #66: Kryptographie – Substitution
• About Security #67: Kryptographie – Transposition
• About Security #68: Kryptographie – Polyalphabetische Substitution
• About Security #69: Kryptographie – Vernam-Chiffre
• About Security #70: Kryptographie – Feistel-Netzwerke