Die Blockgröße n = 2s wird als gerade vorausgesetzt.
Blöcke a Î F2n werden in ihre linke und rechte Hälfte zerlegt:
a = (l,r) Î F2s × F2s.
Eine FEISTEL-Chiffre beruht auf einer Kernabbildung
f : F2s × F2q ® F2s,
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.
Eine FEISTEL-Chiffre besteht aus r Runden, wobei jeweils aus dem Schlüssel k Î F2l ein q-Bit-Rundenschlüssel gebildet wird mit Hilfe der i-ten Schlüsselauswahl
ai F2l ® F2q für i = 1, ..., r.
Die i-te Runde soll dann so aussehen:
Aus der graphischen Beschreibung leitet man leicht eine algorithmische ab:
Input | ® | a | = | (a0,a1) Î F2s × F2s | |
---|---|---|---|---|---|
a2 | := | a0 + f(a1,a1(k)) | - 1. Runde, Ergebnis (a1,a2) | ||
| | | | ||||
ai+1 | := | ai-1 + f(ai,ai(k)) | - i-te Runde, Ergebnis (ai,ai+1)
[ai = ri-1 = li, ai+1 = ri] | ||
| | | | ||||
Output | ¬ | c | = | (ar,ar+1) =: F(a,k) |
Entschlüsselt wird nach der Formel
ai-1 = ai+1 + f(ai,ai(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 :
F22s ×
F2l ®
F22s
die Blockabbildung zur Kernabbildung
f : F2s ×
F2q ®
F2s und zur Schlüsselauswahl
a =
(a1, ...,
ar),
ai :
F2l ®
F2q. Dann ist die Verschlüsselungsfunktion F(·,k) : F22s ® F22s für jeden Schlüssel k Î F2l bijektiv. |
Zusatz. Die Entschlüsselung ist die Blockabbildung zur gleichen Kernabbildung f und zur umgekehrten Schlüsselauswahl (ar, ..., a1). |
Achtung: Beginnt man die Entschlüsselung mit c = (ar,ar+1), so sind zuerst die Seiten zu vertauschen, denn der Algorithmus beginnt mit (ar+1,ar). Daher wird bei der letzten Runde meist die Seitenvertauschung weggelassen.
Die Bedeutung der FEISTEL-Netze liegt in den empirischen Beobachtungen:
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.
E-Mail an Pommerening@imsd.uni-mainz.de.