Dienstag, 4. Mai 2010


Topthema

Donnerstag, 24. August 2006 | Topthema

About Security #69: Kryptographie — Vernam-Chiffre

(Link zum Artikel: http://www.entwickler.de/php/kolumnen/030868)

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.

N E U ! Security aktuell
T�glich aktuelle Security-Infos!

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.

About Security: Die komplette Serie

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.

Wenn Sie Fragen oder Themenvorschl�ge haben, k�nnen Sie diese gerne an die angegebene E-Mail-Adresse senden oder im Security-Forum einbringen!

Carsten Eilers

About Security � �bersicht zum aktuellen Thema "Kryptographie � Grundlagen"

Kommentare

Folgende Links könnten Sie auch interessieren