|
Kryptologie
Mathematisches Modell der Chiffrierung |
a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h:
Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø |
|
Kryptographie beschäftigt sich mit der Transformation von Zeichenketten.
Daher wird hier gleich zu Beginn mathematisch formuliert, was damit gemeint
ist. Natürlich sind einige (aber nicht viele!) der folgenden Abschnitte auch
ohne mathematischen
Formalismus verständlich, so dass der Leser ohne mathematische Vorbildung
sich hier nicht gleich abschrecken lassen sollte, sondern diesen Abschnitt
- und weitere mathematische Abschnitte -
einfach überspringen. Es sei aber darauf hingewiesen, dass Kryptologie
eine mathematische Wissenschaft ist und man ohne mathematische Formulierungen
nicht weit kommt.
Ohne mathematischen Formalismus kann man den Inhalt dieses Abschnitts
so zusammenfassen: |
Eine Verschlüsselungsfunktion transformiert beliebige Zeichenketten
in andere Zeichenketten. (Der Zeichensatz ist dabei vorgegeben.) |
Eine Chiffre ist eine parametrisierte Familie von
Verschlüsselungsfunktionen. Der Parameter ist der Schlüssel; er bestimmt
die Auswahl der konkreten Funktion. Ohne Kenntnis des Schlüssels kann
niemand die Verschlüsselung umkehren. |
Alphabete und Texte
Sei S eine endliche Menge; sie wird in diesem
Zusammenhang Alphabet genannt und ihre Elemente
Zeichen.
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;
der Fernschreibcode verwendet 5-Bit-Blöcke, also das Alphabet
F25 mit 32 verschiedenen Zeichen].
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 auch als Ring der ganzen Zahlen
mod n mit
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.
Sei S ein Alphabet,
S*
die Menge aller endlichen Folgen aus S;
solche Folgen werden hier Texte genannt.
Definition
Gegeben sei ein Alphabet S und eine
Menge K, die auch unendlich sein kann
(ihre Elemente werden hier Schlüssel genannt).
(i) Eine Verschlüsselungsfunktion über
S ist eine injektive Abbildung
f: S*
® S*.
(ii) 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.
[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. Solche Verallgemeinerungen 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~ £ #K.
- Allerdings kann, wenn K
unendlich ist, auch d(F) unendlich sein.
- Man kann auch 2log(#K) als Schlüssellänge der Chiffre
bezeichnen. Diese Zahl ist meist leichter zu bestimmen, aber
praktisch weniger wert.
- Oft sind die zu verschlüsselnden Texte nicht allgemeine Zeichenketten, 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).
- Durch die Schlüsselwahl wird die Chiffre »randomisiert«. Auch wenn der Gegner
die Verschlüsselungsmethode kennt oder errät, kann er doch ohne den Schlüssel
nicht unbefugt entziffern.
Historisch wurde bei der Zuordnung des gewöhnlichen Alphabets zu Buchstaben
meist mit A « 1 begonnen; solche Zuordnungen gab es
schon im Altertum, wo sie zu allerlei Zahlenmystik missbraucht wurden. Zu
kryptographischen Zwecken, also um Chiffren arithmetisch zu beschreiben, wurde
sie systematisch - soweit bekannt - erstmals von COMIERS verwendet:
- Claude COMIERS:
L'Art d'Écrire et de Parler Occultement et sans Soupçon.
Paris 1690.
Natürlich ist die Zuordnung A « 1 statt A
« 0 ungeschickt und führt zu weniger eleganten Formeln.
Ein späteres Werk, wo Buchstaben durch Zahlen codiert werden, wurde unlängst von
Joachim von zur GATHEN ausgegraben (Friedrich Johann Buck: Arithmetic puzzles in
Cryptography. Cryptologia XXVIII (2004), 309 - 324) und
online gestellt:
- Friedrich Johann BUCK:
Mathematischer Beweiß: daß die Algebra zur Entdeckung einiger verborgener
Schriften bequem angewendet werden könne.
Königsberg 1772.
Aus ihm stammt der Abschnitt
Autor: Klaus Pommerening, 25. Oktober 1999;
letzte Änderung: 10. Januar 2005.
E-Mail an
Pommerening@imsd.uni-mainz.de.