Kryptologie: FEISTEL-Chiffren

Kryptologie

FEISTEL-Chiffren

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

Die Kernabbildung

Die Blockgröße n = 2s wird als gerade vorausgesetzt.

Blöcke a Î F₂ⁿ werden in ihre linke und rechte Hälfte zerlegt:

a = (l,r) Î F₂^s × F₂^s.

Eine FEISTEL-Chiffre beruht auf einer Kernabbildung

f : F₂^s × F₂^q ® F₂^s,

an die formal keine weiteren Anforderungen gestellt werden; insbesondere brauchen die f(·,k) nicht bijektiv zu sein.

Um ein brauchbares Verschlüsselungsverfahren zu erhalten, fordert man jedoch, dass f gute Konfusion und Diffusion bietet, etwa bereits aus Substitutionen und Transpositionen zusammengesetzt und hochgradig nichtlinear ist.

Beschreibung der Runden

Eine FEISTEL-Chiffre besteht aus r Runden, wobei jeweils aus dem Schlüssel k Î F₂^l ein q-Bit-Rundenschlüssel gebildet wird mit Hilfe der i-ten Schlüsselauswahl

a_i F₂^l ® F₂^q für i = 1, ..., r.

Die i-te Runde soll dann so aussehen:

Algorithmische Beschreibung

Aus der graphischen Beschreibung leitet man leicht eine algorithmische ab:

Input ® a = (a₀,a₁) Î F₂^s × F₂^s

a₂ := a₀ + f(a₁,a₁(k)) - 1. Runde, Ergebnis (a₁,a₂)

| |

a_i+1 := a_i-1 + f(a_i,a_i(k)) - i-te Runde, Ergebnis (a_i,a_i+1)
[a_i = r_i-1 = l_i, a_i+1 = r_i]

| |

Output ¬ c = (a_r,a_r+1) =: F(a,k)

Input	®	a	=	(a₀,a₁) Î F₂^s × F₂^s
		a₂	:=	a₀ + f(a₁,a₁(k))	- 1. Runde, Ergebnis (a₁,a₂)
		\|		\|
		a_i+1	:=	a_i-1 + f(a_i,a_i(k))	- i-te Runde, Ergebnis (a_i,a_i+1) [a_i = r_i-1 = l_i, a_i+1 = r_i]
		\|		\|
Output	¬	c	=	(a_r,a_r+1) =: F(a,k)

Die Entschlüsselung

Entschlüsselt wird nach der Formel

a_i-1 = a_i+1 + f(a_i,a_i(k)) für i = 1, ..., r.

Das entspricht dem gleichen Algorithmus, nur werden die Runden in umgekehrter Reihenfolge durchlaufen - mit anderen Worten: Die Schlüsselauswahl wird in umgekehrter Reihenfolge ausgeführt.

Insbesondere ist damit bewiesen:

Satz (FEISTEL). Sei F : F₂^2s × F₂^l ® F₂^2s die Blockabbildung zur Kernabbildung f : F₂^s × F₂^q ® F₂^s und zur Schlüsselauswahl a = (a₁, ..., a_r), a_i : F₂^l ® F₂^q.

Dann ist die Verschlüsselungsfunktion F(·,k) : F₂^2s ® F₂^2s für jeden Schlüssel k Î F₂^l bijektiv.

Zusatz. Die Entschlüsselung ist die Blockabbildung zur gleichen Kernabbildung f und zur umgekehrten Schlüsselauswahl (a_r, ..., a₁).

Achtung: Beginnt man die Entschlüsselung mit c = (a_r,a_r+1), so sind zuerst die Seiten zu vertauschen, denn der Algorithmus beginnt mit (a_r+1,a_r). Daher wird bei der letzten Runde meist die Seitenvertauschung weggelassen.

Anmerkungen

Sind f und die a_i linear, so auch F.
Für die a_i nimmt man meist nur eine Bitauswahl, also eine Projektion F₂^l ® F₂^q.
Alternative graphische Beschreibung: [s. Tafel].

Verallgemeinerungen

Beliebige Gruppe [s. Tafel].
Unbalancierte FEISTEL-Chiffren (SCHNEIER/KELSEY) [s. Tafel].

Beispiele

Lucifer II (FEISTEL 1971 entwickelt, 1975 veröffentlicht),
DES (COPPERSMITH u. a./IBM 1974 entwickelt, 1977 als US-Norm veröffentlicht),
u. v. a. neuere Bitblock-Chiffren

Die Bedeutung der FEISTEL-Netze liegt in den empirischen Beobachtungen:

Die »(s,q)-Bit-Sicherheit« der Kernfunktion f wird zu einer »(n,l)-Bit-Sicherheit« der FEISTEL-Chiffre F erweitert.
Die gesamte Chiffre ist lässt sich aus handhabbaren, auf Sicherheit optimierbaren Stücken zusammensetzen.

Die erste dieser Beobachtungen lässt sich auch theoretisch untermauern: Nach einem Ergebnis von LUBY/RACKOFF ist eine FEISTEL-Chiffre mit mindestens vier Runden nicht mehr effizient von einer zufälligen Permutation zu unterscheiden, wenn die Kernfunktion nicht effizient von einer zufälligen Funktion zu unterscheiden ist.

Autor: Klaus Pommerening, 7. April 2000; letzte Änderung: 23. April 2000.

E-Mail an Pommerening@imsd.uni-mainz.de.