Entropie (Kryptologie)

in der Kryptologie verwendeter Begriff

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.

Der Begriff „Entropie“ wird auch in der Thermodynamik verwendet, in die er im Jahr 1865 durch den deutschen Physiker Rudolf Clausius (1822–1888) eingeführt wurde.

DefinitionBearbeiten

Die Entropie   eines Textes, bei dem die einzelnen Zeichen mit   durchnummeriert sind und in dem jedes dieser Zeichen jeweils mit der Wahrscheinlichkeit   auftritt, ist:[1]

 

In dieser Formel ist:

  •   ein Index über den Text
  •   die Auftrittswahrscheinlichkeit des Zeichens an der Stelle  
  •   der Logarithmus dualis, also zur Basis 2

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

Da die einzelnen Wahrscheinlichkeiten   zwischen 0 und 1 liegen, ist der Ausdruck   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.

Das Minuszeichen hätte auch direkt vor dem   stehen können, aber dann hätte die Formel zusätzliche Klammern benötigt, und das wäre in der Schreibweise unästhetisch gewesen. Für die Berechnung der Formel ist es unerheblich, ob das Minus ganz vorne oder vor dem   steht (siehe Äquivalenzumformung).

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.

BeispieleBearbeiten

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   den Wert   einsetzt. Dadurch sind alle Summanden gleich, und die Entropie berechnet sich zu   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  , also 0 Bit/Zeichen. Die Teilentropie der übrigen Zeichen ist  , also ebenfalls 0 Bit/Zeichen. Die Gesamtentropie ist damit ebenfalls 0 Bit/Zeichen.

RedundanzBearbeiten

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 auchBearbeiten

LiteraturBearbeiten

  • 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.

WeblinksBearbeiten

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

EinzelnachweiseBearbeiten

  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 des Originals vom 15. September 2016 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/www.wi.hs-wismar.de. Abgerufen: 15. September 2016.