Entropie (Kryptologie)

Die Entropie (Kunstwort altgriechisch ἐντροπία entropía, von

ἐν

en ‚an‘, ‚in‘ und

τροπή

tropḗ ‚Wendung‘, ‚Umkehr‘) ist ein auch in der Kryptologie verwendeter Begriff. Er stellt ein Maß für die „Unordnung“ in Texten dar. Abgekürzt wird die Entropie zumeist mit dem griechischen Großbuchstaben Η (‚Eta‘).

Bei der Kryptanalyse von Geheimtexten ist die Bestimmung der Entropie nützlich, um Erkenntnisse über die Struktur des Textes und, ergänzt durch den Koinzidenzindex, möglichst auch über die zugrundeliegende Sprache zu erhalten, mit dem Ziel, den Bruch (Entzifferung) des Geheimtextes zu ermöglichen.

Definition

Die Entropie $\mathrm {H}$ eines Textes, bei dem die einzelnen Zeichen mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} durchnummeriert sind und in dem jedes dieser Zeichen jeweils mit der Wahrscheinlichkeit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_i} auftritt, ist:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Eta = -\sum_i p_i \textrm{ld} (p_i)}

In dieser Formel ist:

• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} ein Index über den Text
• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_i} die Auftrittswahrscheinlichkeit des Zeichens an der Stelle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i}
• ${\textrm {ld}}$ der Logarithmus dualis, also zur Basis 2

Der Text kann aus beliebigen Zeichen, Symbolen oder Zahlen bestehen, vorausgesetzt, sie sind unterscheidbar.

Da die einzelnen Wahrscheinlichkeiten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_i} zwischen 0 und 1 liegen, ist der Ausdruck Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \textrm{ld}(p_i)} stets negativ oder null. Das Minus vor dem Summenzeichen sorgt dafür, dass jeder einzelne Summand eine positive Zahl oder null ist. Dadurch ist auch die gesamte Entropie stets positiv oder null.

Anschaulich entspricht die Entropie eines Textes genau der Anzahl Ja/Nein-Fragen, die man stellen muss, um den kompletten Text zu erraten. Die Entropie ist jedoch nicht auf ganze Zahlen beschränkt, sondern ist eine reelle Zahl.

Beispiele

Klartexte weisen je nach benutzter Sprache leicht unterschiedliche Buchstabenhäufigkeiten und damit auch verschiedene Entropiewerte auf. Ausgehend von den gewohnten 26 Großbuchstaben des lateinischen Alphabets lässt sich die Entropie über die Buchstabenhäufigkeit berechnen. Eine Auszählung der typischen Buchstabenhäufigkeiten für einige europäische Sprachen ergibt die folgenden Werte (jeweils in Prozent). Neben den einzelnen Häufigkeiten für diverse Sprachen wie Deutsch, Englisch, Niederländisch, Spanisch, Französisch und Italienisch ist links (in der zweiten Spalte) zum Vergleich der Wert 3,85 % ergänzt. Dieser ergibt sich als Quotient 1/26 für einen idealen Zufallstext, bei dem alle Buchstaben mit gleicher Wahrscheinlichkeit auftreten.

Zuf Deu Eng Nie Spa Fra Ita A 3,85 5,45 7,19 7,17 6,69 6,82 10,73 B 3,85 1,75 1,58 1,41 0,71 0,70 0,89 C 3,85 3,37 4,05 1,78 3,52 3,30 5,05 D 3,85 5,11 3,11 6,85 4,03 3,71 3,57 E 3,85 16,89 13,05 18,84 15,92 15,61 13,19 F 3,85 1,28 2,42 0,78 1,10 1,13 1,31 G 3,85 3,76 2,34 2,94 1,57 0,84 1,05 H 3,85 5,26 4,71 2,75 1,22 0,59 1,50 I 3,85 8,51 7,71 6,87 7,32 7,11 9,80 J 3,85 0,18 0,09 1,50 0,16 0,19 0,01 K 3,85 1,51 0,58 1,92 0,05 0,01 0,01 L 3,85 3,77 3,72 4,15 5,31 4,85 5,76 M 3,85 2,22 2,54 1,88 2,56 3,22 2,98 N 3,85 10,42 7,81 9,91 7,14 9,42 7,57 O 3,85 3,11 7,52 5,85 6,01 6,08 9,66 P 3,85 0,63 2,30 1,36 3,53 3,21 2,63 Q 3,85 0,01 0,10 0,02 1,36 1,74 0,69 R 3,85 7,14 6,41 6,50 7,03 5,81 6,09 S 3,85 6,24 6,49 4,45 9,44 9,53 5,94 T 3,85 6,08 9,22 6,02 7,31 7,32 5,90 U 3,85 3,40 2,83 1,77 5,72 6,92 2,95 V 3,85 0,89 0,86 2,66 1,12 1,06 1,64 W 3,85 1,64 1,07 1,40 0,05 0,01 0,01 X 3,85 0,02 0,45 0,02 0,71 0,42 0,02 Y 3,85 0,07 1,73 0,09 0,36 0,36 0,01 Z 3,85 1,27 0,10 1,12 0,06 0,03 1,04

Hieraus lassen sich die Entropiewerte (in Bit/Zeichen) für die diversen Sprachen mithilfe der oben angegebenen Definitionsgleichung leicht berechnen. In der folgenden Tabelle werden sie (in der zweiten Spalte) wiederum ergänzt durch den Wert für ideale Zufallstexte.

Zuf Deu Eng Nie Spa Fra Ita Η 4,7 4,07 4,16 4,06 4,03 3,98 3,99

Der Wert für die Zufallstexte ergibt sich, indem man in der Definitionsgleichung für jedes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_i} den Wert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1/26} einsetzt. Dadurch sind alle Summanden gleich, und die Entropie berechnet sich zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle -26 \cdot (1/26) \cdot \rm{ld}(1/26)} oder 4,7 Bit/Zeichen. Dies ist zugleich die maximale Entropie, die ein Text aus 26 Zeichen aufweisen kann.

Die minimale Entropie wird erreicht, wenn ein Text (beliebiger Länge) immer nur einen einzigen Buchstaben benutzt, also beispielsweise aus der (sinnlosen) Hintereinanderreihung von A besteht, wie „AAAAA…“. In dem Fall berechnet sich die Entropie aus der Teilentropie des „A“ und der der übrigen Buchstaben. Die Teilentropie des „A“ ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 \cdot \rm{ld}(1) = 1 \cdot 0 = 0} , also 0 Bit/Zeichen. Die Teilentropie der übrigen Zeichen ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0 \cdot \rm{ld}(0) = 0 \cdot -\infty = 0} , also ebenfalls 0 Bit/Zeichen. Die Gesamtentropie ist damit ebenfalls 0 Bit/Zeichen.

Redundanz

Eng verknüpft mit der Entropie ist der Begriff Redundanz (ebenfalls in Bit/Zeichen). Darunter versteht man die Differenz zwischen der maximalen Entropie und der Entropie des betrachteten Textes oder der Sprache. Ein Zufallstext weist keinerlei Redundanz auf (R = 0), während natürliche Sprachen sämtlich mehr oder weniger redundant sind.

Zuf Deu Eng Nie Spa Fra Ita R 0 0,63 0,54 0,64 0,67 0,72 0,71

Siehe auch

• Entropie (Informationstheorie)
• Redundanz (Informationstheorie)

Literatur

• Friedrich L. Bauer: Entzifferte Geheimnisse – Methoden und Maximen der Kryptologie. Springer, Berlin 2000 (3. Aufl.), ISBN 3-540-67931-6.
• C. A. Deavours: Unicity Points in Cryptanalysis, Cryptologia, 1(1), 1977, S. 46–68.
• Michael Miller: Symmetrische Verschlüsselungsverfahren, Teubner, 2003, S. 88–105. ISBN 3-519-02399-7.
• Claude Shannon: Communication Theory of Secrecy Systems. Bell System Technical Journal, 28(Oct), 1949, S. 656–715. PDF;0,6 MB. Abgerufen: 15. September 2016.
• Ronald Wick: Europäische Alphabete PDF; 1,9 MB. Abgerufen: 15. September 2016.

Weblinks

• Video Prof. Craig Bauer stellt die Entropie für verschiedene Sprachen vor (nach 7 Minuten; englisch). Abgerufen: 15. September 2016.