Der Begriff der perfekten Sicherheit wurde von Shannon eingeführt. Shannons Idee bei perfekt sicheren Kryptosystemen war, dass ein Angreifer Oskar aus einem empfangenen Chiffrat $\text{[math]}$ keinerlei Rückschlüsse auf den zugehörigen Klartext ziehen kann.

Wir nehmen an, dass die Klartexte $\text{[math]}$ gemäß einer Wahrscheinlichkeitsverteilung $\text{[math]}$ auftreten. Analoges gilt für die verwendeten Schlüssel $\text{[math]}$ gemäß einer Wahrscheinlichkeitsverteilung $\text{[math]}$ . Dann gilt für den Empfang eines bestimmten Chiffrats $\text{[math]}$ :

da Klartext und Schlüssel unabhängig voneinander gewählt werden, wobei $\text{[math]}$ die Chiffrierfunktion ist.

Definition 1 (perfekt sicheres Kryptosystem)
Das eben vorgestellte Kryptosystem heißt perfekt sicher, wenn für alle Paare $\text{[math]}$ mit $\text{[math]}$ gilt $\text{[math]}$ .

In perfekt sicheren Systemen ist also bei Vorliegen des Chiffrats $\text{[math]}$ jeder Klartext genauso wahrscheinlich wie er ohne Vorliegen des Chiffrats ist, das heißt, der Gegner erhält aus $\text{[math]}$ keine Information über den zugehörigen Klartext.

Beispiel 2
Sei $\text{[math]}$ , $\text{[math]}$ und $\text{[math]}$ . Weiter sei $\text{[math]}$ mit $\text{[math]}$ und $\text{[math]}$ , sowie $\text{[math]}$ . Für die Verschlüsselungsfunktion $\text{[math]}$ gelte

\text{[math]}

Dann gilt $\text{[math]}$ sowie $\text{[math]}$ . Weiter ist $\text{[math]}$ und $\text{[math]}$ , sowie $\text{[math]}$ und $\text{[math]}$ . Das System ist also nicht perfekt sicher.

Beweis Sei $\text{[math]}$ ein Chiffrat mit $\text{[math]}$ , und $\text{[math]}$ ein Klartext mit $\text{[math]}$ . Dann gilt wegen der perfekten Sicherheit $\text{[math]}$ , also existiert ein Schlüssel $\text{[math]}$ mit $\text{[math]}$ . Wegen der Injektivität von $\text{[math]}$ sind die gefundenen Schlüssel paarweise verschieden.

Satz 4
Sei $\text{[math]}$ und $\text{[math]}$ für jeden Klartext $\text{[math]}$ . Das Kryptosystem ist perfekt sicher genau dann, wenn die Wahrscheinlichkeitsverteilung $\text{[math]}$ auf der Schlüsselmenge $\text{[math]}$ die Gleichverteilung ist und für jedes Paar $\text{[math]}$ genau ein Schlüssel $\text{[math]}$ mit $\text{[math]}$ existiert.

Beweis Angenommen, das System habe perfekte Sicherheit. Dann gibt es zu jedem Klartext $\text{[math]}$ und für jedes Chiffrat $\text{[math]}$ einen Schlüssel $\text{[math]}$ mit $\text{[math]}$ , da ansonsten $\text{[math]}$ gelten würde. Mit $\text{[math]}$ folgt die Eindeutigkeit des Schlüssels $\text{[math]}$ .

Sei nun ein Chiffrat $\text{[math]}$ gegeben. Für einen beliebigen Klartext $\text{[math]}$ sei $\text{[math]}$ der Schlüssel mit $\text{[math]}$ . Dann gilt nach dem Bayesschen Satz:

\text{[math]}

Mit $\text{[math]}$ folgt sofort

\text{[math]}

also ist $\text{[math]}$ unabhängig von $\text{[math]}$ . Da für jeden Schlüssel $\text{[math]}$ ein Klartext $\text{[math]}$ existiert mit $\text{[math]}$ , folgt Gleichverteilung auf $\text{[math]}$ .

Angenommen nun, auf $\text{[math]}$ liege Gleichverteilung vor und für alle Paare $\text{[math]}$ gibt es genau einen Schlüssel $\text{[math]}$ mit $\text{[math]}$ . Dann gilt

\text{[math]}

also folgt perfekte Sicherheit.

Beispiel

Hill-Chiffre sind nicht perfekt sicher, da Nullvektoren immer zu Nullvektoren verschlüsselt werden. Für $\text{[math]}$ gilt daher $\text{[math]}$ und $\text{[math]}$ bei Gleichverteilung der Nachrichten in $\text{[math]}$ .

Perfekte Sicherheit

Beispiel