Entropie (Kryptologie)

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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.

Definition[Bearbeiten | Quelltext bearbeiten]

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.

Beispiele[Bearbeiten | Quelltext bearbeiten]

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.

Redundanz[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

Literatur[Bearbeiten | Quelltext bearbeiten]

  • 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[Bearbeiten | Quelltext bearbeiten]

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

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  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.