2 Grundlagen

Ein kryptographisches System besteht aus fünf Komponenten:

1.	Klartextraum M
2.	Chiffretextraum C
3.	Schlüsselraum K
4.	Familie von Chiffriertransformationen Ek: M -> C mit k aus K
5.	Familie von Dechiffriertransformationen Dk: C -> M mit k aus K

Dabei sind M, C und K höchstens abzählbar. Jede Chiffriertransformation E_k wird durch einen Schlüssel k und einen Chiffrieralgorithmus E definiert, der für jede Transformation der Familie gleich ist. Entsprechendes gilt für jede Dechiffriertransformation D_k.
Für ein gegebenes k und für alle m aus M gilt D_k(E_k(m)) = m.

Kryptosysteme müssen auf jeden Fall drei Eigenschaften erfüllen:

(1)	Chiffrier- und Dechiffriertransformationen müssen für alle Schlüssel effizient berechnet werden können.
(2)	Die Systeme müsen leicht zu benutzen sein. Es muß also leicht sein, einen Schlüssel sowie die Abbildungen Ek und Dk zu finden.
(3)	Die Sicherheit des Systems sollte auf der Geheimhaltung der Schlüssel und nicht der Algorithmen beruhen; allein aus der Kenntnis der Methode des (De-)Chiffrierens soll der Klartext nicht gewonnen werden können.

Für Geheimhaltung und Authentizität gibt es spezielle Forderungen. Geheimhaltung verlangt, daß ein Kryptoanalytiker nicht in der Lage ist, Klartext aus einem abgefangenen Chiffretext zu bestimmen. Authentizität erfordert, da&zlig; der Kryptoanalytiker ohne Entdeckung keinen falschen Chiffretext c' für einen Chiffretext c einsetzen kann. Daraus ergeben sich die

Geheimhaltungsforderungen:
Es sollte einem Kryptoanalytiker berechnungsmäßig praktisch unmöglich sein,

(1)	systematisch Dk aus einem abgefangenen Chiffretext c zu bestimmen, selbst dann, wenn der Klartext m bekannt ist, und
(2)	den Klartext m aus c zu bestimmen.

Für die Geheimhaltung muß nur D_k geschützt werden, sofern E_k nicht D_k verrät. E_k kann also publik gemacht werden. Weiter erhalten wir die

Authentizitätsforderungen:
Es sollte einem Kryptoanalytiker berechnungsmäßig praktisch unmöglich sein,

(1)	systematisch Ek aus c zu bestimmen, selbst dann, wenn der Klartext m mit Ek(m) = c bekannt ist, oder
(2)	einen Chiffretext c' zu finden, so daß Dk(c') ein gültiger Klartext aus M ist. Dies ist bei numerischen Daten denkbar.

Durch (1) wird gesichert, daß der Kryptoanalytiker keinen falschen Klartext m' durch E_k(m') = c einschieben kann. Für die Authentizität muß nur E_k geschützt werden, wenn D_k nicht E_k verrät. D_k kann also publik gemacht werden.

Für zahlreiche Verfahren (insbesondere RSA) werden große Primzahlen und schnelle modulo-Operationen benötigt. Entsprechende Algorithmen werden in den nächsten Kapiteln vorgestellt.

2.1 Euklidischer Algorithmus