Perfekte Sicherheit

Wir benötigen die Komponenten eines Verschlüsselungsverfahrens: Sei ${\displaystyle {\mathcal {P}}}$ die Menge aller möglichen Klartexte, ${\displaystyle {\mathcal {K}}}$ die Menge der Schlüssel und ${\displaystyle {\mathcal {C}}}$ die Menge aller möglichen Chiffrate. Diese Mengen haben jeweils endlich viele Elemente. Außerdem sei ${\displaystyle E\colon {\mathcal {P}}\times {\mathcal {K}}\to {\mathcal {C}}}$ eine Verschlüsselungsfunktion und ${\displaystyle D\colon {\mathcal {C}}\times {\mathcal {K}}\to {\mathcal {P}}}$ die korrespondierende Entschlüsselungsfunktion.

Klartexte treten in der Regel nicht mit gleicher Wahrscheinlichkeit auf. Dies ist beispielsweise abhängig von der verwendeten Sprache oder einem Protokoll, dem die Konversation folgt. ${\displaystyle Pr(p)}$ bezeichne die Wahrscheinlichkeit, mit der ein Klartext ${\displaystyle p\in {\mathcal {P}}}$ auftritt.

Ein Verschlüsselungsverfahren heißt perfekt sicher, wenn das Auftreten eines bestimmten Klartextes stochastisch unabhängig davon ist, dass ein bestimmtes Chiffrat vorliegt. Es gilt also für alle Klartexte ${\displaystyle p\in {\mathcal {P}}}$ und jedes Chiffrat ${\displaystyle c\in {\mathcal {C}}}$ die Gleichung ${\displaystyle Pr(p|c)=Pr(p)}$.

Fängt ein Angreifer einen Schlüsseltext ${\displaystyle c}$ ab, ist es ihm nicht möglich, statistische Auffälligkeiten des Klartextraums auszuwerten. Versucht er den zu ${\displaystyle c}$ gehörigen Klartext zu erraten, liegt er lediglich mit der Wahrscheinlichkeit richtig, die er auch erreichen würde, wenn er den abgefangenen Schlüsseltext nicht kennt und blind einen Klartext rät.

Im Jahre 1949 bewies Shannon das folgende Theorem, welches erklärt, unter welchen Voraussetzungen ein Verschlüsselungsverfahren perfekt sicher ist.

Sei ${\displaystyle |{\mathcal {P}}|=|{\mathcal {K}}|=|{\mathcal {C}}|<\infty }$ und für alle ${\displaystyle p\in {\mathcal {P}}}$ sei ${\displaystyle Pr(p)>0}$. Das Verschlüsselungsverfahren ist perfekt sicher, genau dann, wenn die Wahrscheinlichkeitsverteilung auf dem Schlüsselraum die Gleichverteilung ist und wenn für jeden Klartext ${\displaystyle p\in {\mathcal {P}}}$ und jedes Chiffrat ${\displaystyle c\in {\mathcal {C}}}$ genau ein Schlüssel ${\displaystyle k\in {\mathcal {K}}}$ existiert, so dass ${\displaystyle E(p,k)=c}$.

Aus dem Satz von Shannon geht hervor, dass bei perfekt sicheren Verfahren die Wahrscheinlichkeitsverteilung auf dem Schlüsselraum die Gleichverteilung sein muss. Statistische Abweichungen können dabei dazu führen, dass das System unsicher wird. Daher sollten zur Schlüsselerzeugung kryptographisch sichere Zufallszahlengeneratoren verwendet werden.

Shannon konnte zeigen, dass perfekt sichere Verschlüsselungsverfahren tatsächlich existieren. Ein Beispiel dafür ist das One-Time-Pad. Solche perfekt sicheren Verfahren einzusetzen ist in der Praxis meist umständlich. Bei Echtzeitanwendungen wie im Internet werden sie daher kaum verwendet.

• Johannes Buchmann: Einführung in die Kryptographie. Springer, Berlin, 2010, ISBN 978-3-642-11185-3
• Claude E. Shannon: Communication Theory of Secrecy Systems. In: Bell System Technical Journal. 28. Jahrgang, Nr. 4. AT&T Corporation, USA Oktober 1949, S. 656–715 (wisc.edu [PDF; abgerufen am 11. Oktober 2020]).