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.

Alphabete und Texte

Sei S eine endliche Menge; wir nennen sie Alphabet.

Beispiele:

• {A, B, ..., Z} = das Standard-Alphabet der klassischen Kryptologie,
• {0, 1} = F₂ = der Körper mit zwei Elementen = Alphabet der Bits,
• F₂⁸ = das Alphabet der Bytes (eigentlich: Oktette),
• oder allgemeiner F₂^l = 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.

• Z_n = zyklische Gruppe der Ordnung n = #S -
  [Rechnen in dieser Gruppe ist Arithmetik mod n, also elementare Zahlentheorie] -
  Z_n wird als Ring der ganzen Zahlen mod n auch als Z/nZ bezeichnet.
• F₂ mit der Körperaddition +, auch als BOOLEsche Operation XOR oder Å geschrieben;
• F₂^l als l-dimensionaler Vektorraum über dem Körper F₂ 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 = (f_k)_kÎK von Verschlüsselungsfunktionen über S.

(iii) Sei F eine solche, F^~ = {f_k | k Î K} Í Abb(S^*,S^*) die zugehörige Menge von (verschiedenen) Verschlüsselungsfunktionen. Dann heißt

d(F)  : =  ²log(#F^~)

[Beispiele folgen.]

Bemerkungen

1. 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.
2. Nicht alle f_k, k Î K, müssen verschieden sein; daher ist im allgemeinen #F^~ £ #K
. Allerdings kann, wenn K unendlich ist, auch d(F) unendlich sein.
3. 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 C_k = f_k(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 C_k

   bilden.
4. 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.

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