Dienstag, 4. Mai 2010


Topthema

Donnerstag, 31. August 2006 | Topthema

About Security #70: Kryptographie — Feistel-Netzwerke

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

Ab dieser Folge lernen Sie aktuell eingesetzte kryptographische Verfahren kennen. W�hrend bisher mit Ausnahme der bitweisen Vigen�re-Verschl�sselung zeichenorientierte Verfahren behandelt wurden, wird in den nun folgenden Verfahren in der Regel bitweise gearbeitet. Zuerst m�ssen wieder einige Grundbegriffe erkl�rt werden:

Konfusion und Diffusion

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

Claude Shannon hat 1949 in seinem Artikel "Communication Theory of Secrecy Systems" (als gescannte Bilder) zwei Grundprinzipien der Chiffrierung beschrieben: Bei der Konfusion wird der Zusammenhang zwischen Klartext- und Geheimtextzeichen verwischt, wie z.B. bei der einfachen Substitution (siehe About Security #66). Bei der Diffusion werden die Informationen des Klartexts im Geheimtext verteilt.

Stromchiffren

Bei einer Stromchiffre wird ausgehend von einem Schl�ssel eine "zuf�llige" Bitfolge generiert, die meistens als Schl�ssel eines One-Time-Pads (siehe About Security #69) verwendet, d.h. �ber XOR mit dem Klartext verkn�pft wird. Die Sicherheit des Verfahrens h�ngt vollst�ndig von der Generierung der Bitfolge ab. Stromchiffren sind besonders gut zur Onlineverschl�sselung von Nachrichtenkan�len geeignet.

About Security: Die komplette Serie
Blockchiffren

Bei einer Blockchiffre werden Gruppen von Bits zu Bl�cken zusammengefasst und gemeinsam verschl�sselt. Eine Substitution (siehe About Security #66) kann als Blockchiffre mit 8-Bit-Bl�cken betrachtet werden, bei polyalphabetischen Substitutionen (siehe About Security #68) entspricht die Blockl�nge der Periode (siehe About Security #69).

Produktalgorithmen

Bei einem Produktalgorithmus werden mehrere einfache, kryptographisch unsichere Schritte (genannt Runden) nacheinander ausgef�hrt. Diese Kombination der einfachen Funktionen kann die Sicherheit stark erh�hen. Zum Vergleich nennt Reinhard Wobst in seinem Buch "Abenteuer Kryptologie" das L�sen von Gleichungen: Lineare Gleichungen der Form "ax + b = c" sind leicht zu l�sen, f�r quadratische Gleichungen lernt man die Formel in der Schule, und f�r kubische Gleichungen werden bereits mehrere Formeln ben�tigt. Die Formeln f�r Gleichungen 4. Grades sind schon sehr komplex, und f�r Gleichungen ab dem 5. Grad gibt es keine allgemeinen L�sungen mehr.

Feistel-Netzwerke

Feistel-Netzwerke wurden erstmals 1973 von Horst Feistel in seinem Artikel "Cryptography and Computer Privacy" (als gescannte Bilder) beschrieben. Sie dienen der Beschreibung einer Runde in einem Produktalgorithmus.

Jeder Block wird in zwei gleich gro�e H�lften geteilt. In der i-ten Runde wird die linke H�lfte des (Klartext-)Blocks als L_i-1, die rechte als R_i-1 bezeichnet. Die Verschl�sselungsfunktion f verwendet einen geheimen Schl�ssel S_i, um aus einem gegebenen (Klartext-)block K_i einen (Geheimtext-)block f(S_i, K_i)zu erzeugen. Die eigentliche Verschl�sselung erfolgt dann, indem die beiden Halbbl�cke vertauscht und L_i-1mit f(S_i, R_i-1) XOR-verkn�pft werden:

<pre> L_i := R_i-1 R_i := L_i-1 (+) f(S_i, R_i-1) </pre>

Grafisch l�sst sich das Ganze folgenderma�en darstellen:

Eine Verschl�sselungsrunde eines Feistel-Netzwerks

F�r die Entschl�sselung muss dieser Prozess umgekehrt werden. Das Ergebnis von Runde i ist

<pre> L_i := R_i-1 R_i := L_i-1 (+) f(S_i, R_i-1) </pre>

Zum Entschl�sseln werden L_i und R_igetauscht, au�erdem wird der Rundenindex i r�ckw�rts statt vorw�rts gez�hlt. F�hrt man die Runde erneut durch, so ergibt sich

<pre> L_i =: R_i-1 L_i-1 (+) f(S_i, R_i-1) (+) f(S_i, L_i) = L_i-1 (+) f(S_i, L_i) (+) f(S_i, L_i) =: L_i-1 </pre>

Grafisch l�sst sich das Ganze folgenderma�en darstellen:

Eine Entschl�sselungsrunde eines Feistel-Netzwerks

Wie man sieht, ist das Entschl�sselungsprinzip unabh�ngig von Blockl�nge und Rundenzahl. Auch die Verschl�sselungsfunktion f(S_i, K_i)muss nicht mehr wie bei den klassischen Verfahren umkehrbar sein. Bisher war eine Grundbedingung der kryptographischen Verfahren, dass die Umkehrung der Verschl�sselungsfunktion f(S, K) nur bei Kenntnis des Schl�ssels S m�glich ist. Bei Feistel-Netzwerken reicht die Forderung, dass ohne Kenntnis des Schl�ssels S keine der Funktionen f(S_i, K_i)berechnet werden kann. Dies ist eine deutlich einfachere Aufgabe, da auf die Umkehrbarkeit nicht mehr geachtet werden muss.

Feistel-Netzwerke werden in vielen kryptographischen Verfahren eingesetzt, so z.B. in DES oder Blowfish.

Die Entwicklung von DES

Der Data Encryption Standard DES entstand in Folge einer 1973 vom US-amerikanischen National Bureau of Standards (NBS, heute NIST) gestarteten Ausschreibung f�r einen einheitlichen, sicheren Verschl�sselungsalgorithmus. Die ersten Ergebnisse waren mehr als mager: Kein einziger der eingereichten Entw�rfe erf�llte auch nur ann�hernd die Anforderungen. Erst nach einer zweiten Ausschreibung 1974 wurde von einem IBM-Team, dem u.a. der bereits oben erw�hnte Horst Feistel angeh�rte, ein auf dem IBM-Projekt Lucifer basierender Algorithmus eingereicht. Ende 1976 wurde dieser nach eingehender Pr�fung durch das NBS und die hinzugezogene National Security Agency (NSA) zum offiziellen Standard erkl�rt.

�ber die Beteiligung der NSA ranken Ger�chte, so soll der Algorithmus absichtlich unsicherer gemacht oder eine Hintert�r eingebaut worden sein. 1978 untersuchte ein Komitee mit Zugriff auf geheime Unterlagen diese Bef�rchtungen und erkl�rte sie f�r unbegr�ndet, hielt die Begr�ndung daf�r jedoch geheim.

Der Algorithmus des DES-Verfahrens wird in der n�chsten Folge vorgestellt.

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