2a. Kryptographische Basistechniken
Mathematisches Modell der Chiffrierung
Kryptographie beschäftigt sich mit der Transformation von Zeichenketten.
Hier wird mathematisch formuliert, was damit gemeint ist. Die folgenden
Abschnitte sind (mit wenigen Ausnahmen) auch ohne diesen mathematischen
Formalismus verständlich. Es sei aber darauf hingewiesen, dass Kryptologie
eine mathematische Wissenschaft ist und man ohne mathematische Formulierungen
nicht weit kommt.
Alphabete und Texte
Sei S eine endliche Menge; wir nennen sie
Alphabet.
Beispiele:
- {A, B, ..., Z} = das Standard-Alphabet der klassischen Kryptologie,
- {0, 1} = F2 = der Körper mit zwei Elementen = Alphabet der Bits,
- F28 = das Alphabet der Bytes (eigentlich: Oktette),
- oder allgemeiner F2l = das Alphabet der
l-Bit-Blöcke -
[oft l = 64, z. B. bei DES oder IDEA
oder l = 128, z. B. bei AES].
Das Alphabet S wird oft mit einer Gruppenstruktur versehen,
z. B.
- Zn = zyklische Gruppe der Ordnung n
= #S -
[Rechnen in dieser Gruppe ist Arithmetik mod n,
also elementare Zahlentheorie] -
Zn wird als Ring der ganzen Zahlen
mod n auch als
Z/nZ bezeichnet.
- F2 mit der Körperaddition +, auch als BOOLEsche Operation XOR
oder Å geschrieben;
- F2l als l-dimensionaler Vektorraum
über dem Körper F2 mit der Vektoraddition,
+ oder Å geschrieben.
Definition
Sei S ein Alphabet, S*
die Menge aller endlichen Folgen aus S
(wir nennen solche Folgen »Texte«).
(i) Eine Verschlüsselungsfunktion über S
ist eine injektive Abbildung f: S*
® S*.
(ii) Sei K eine Menge (wir nennen ihre Elemente »Schlüssel«). Eine
Chiffre (oder Verschlüsselungssystem) über
S mit Schlüsselraum K ist eine Familie
F =
(fk)kÎK
von Verschlüsselungsfunktionen über S.
(iii) Sei F eine solche, F~ =
{fk | k Î K}
Í
Abb(S*,S*)
die zugehörige Menge von (verschiedenen) Verschlüsselungsfunktionen. Dann heißt
d(F) : = 2log(F~)
die effektive Schlüssellänge der Chiffre F.
Sie ist eine (oft grobe) obere Schranke für die Stärke der Chiffre.
[Beispiele folgen.]
Bemerkungen
- Die Definition einer Verschlüsselungsfunktion ist nicht die allgemeinste sinnvolle.
Man kann auch nicht-injektive Funktionen betrachten, ebenso Relationen, die keine
(eindeutigen) Funktionen oder nicht auf ganz S*
definiert sind. Die erste und dritte Verallgemeinerung spielen in dieser Vorlesung
keine Rolle; die zweite (Nichteindeutigkeit) wird am besten als probabilistische
Chiffrierung modelliert.
- Nicht alle fk, k Î K,
müssen verschieden sein; daher ist im allgemeinen
#F~ £ #F
.
Allerdings kann, wenn K
unendlich ist, auch d(F) unendlich sein.
- Oft sind die zu verschlüsselnden Texte nicht allgemeine Zeichenkette, sondern
entstammen einer Teilmenge M Í
S*, also einer Sprache über dem
Alphabet S. Man nennt M dann den
»Klartextraum« und die Elemente von M »sinnvolle Texte« oder »Klartexte«
(englisch: plain texts).
Üblicherweise werden allerdings, auch wenn nur Texte aus M verschlüsselt
werden sollen, Verschlüsselungsfunktionen auf ganz
S* definiert.
Die Bildmenge Ck = fk(M)
hängt im allgemeinen vom Schlüssel k ab. Ihre Elemente werden
»Geheimtexte« genannt (englisch: cipher texts). Man kann auch den »Geheimtextraum«
C : =
ÈkÎK
Ck
bilden. Die Chiffre besteht dann aus einer Familie von Abbildungen
fk: M ® C.
Vorlesung Datenschutz und Datensicherheit,
Johannes-Gutenberg-Universität Mainz
Autor: Klaus Pommerening, 25. Oktober 1999;
letzte Änderung: 23. November 2001.
E-Mail an
Pommerening@imsd.uni-mainz.de.