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 $i$ durchnummeriert sind und in dem jedes dieser Zeichen jeweils mit der Wahrscheinlichkeit $p_{i}$ auftritt, ist:[1]

\mathrm {H} =-\sum _{i}p_{i}{\textrm {ld}}(p_{i})

In dieser Formel ist:

$i$ ein Index über den Text
$p_{i}$ die Auftrittswahrscheinlichkeit des Zeichens an der Stelle $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 $p_{i}$ zwischen 0 und 1 liegen, ist der Ausdruck ${\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).[2] 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 $p_{i}$ den Wert $1/26$ einsetzt. Dadurch sind alle Summanden gleich, und die Entropie berechnet sich zu $-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 $1\cdot {\rm {{ld}(1)=1\cdot 0=0}}$ , also 0 Bit/Zeichen. Die Teilentropie der übrigen Zeichen ist $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

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.

Einzelnachweise

Claude Shannon: Communication Theory of Secrecy Systems. Bell System Technical Journal, 28(Oct), S. 681 unten. PDF;0,6 MB. Abgerufen: 15. September 2016.
Ronald Wick: Europäische Alphabete, S. 80. PDF; 1,9 MB (Memento vom 15. September 2016 im Internet Archive).

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.

[1] Claude Shannon: Communication Theory of Secrecy Systems. Bell System Technical Journal, 28(Oct), S. 681 unten. PDF;0,6 MB. Abgerufen: 15. September 2016.

[2] Ronald Wick: Europäische Alphabete, S. 80. PDF; 1,9 MB (Memento vom 15. September 2016 im Internet Archive).