Shannon Entropie

Kategorisierung:Kryptoanalyse
Herkunft / Verwendung: Der Entropie-Wert nach Shannon liefert einen Wert für die Informationsdichte einer binären Nachricht und lässt so darauf schließen, ob eine Datei verschlüsselt oder komprimiert ist. Für textuelle Nachrichten ist der Koinzidenzindex besser geeignet.

Der Begriff Entropie in der Informationstheorie wurde 1948 von Claude E. Shannon geprägt. Er ist ein Maß für den mittleren Informationsgehalt einer Nachricht. Der Minimalwert Null steht für keine Zufälligkeit, während der Maximalwert für totale Zufälligkeit steht. Ein Standardtext in deutsch oder englisch sollte sich bei 3,5 bis 5 bewegen. Komprimierte oder stark verschlüsselte Daten sollten bei über 6,5 liegen. Die Entropie wird üblicherweise mit einem großen Eta (Η) abgekürzt.

1948 veröffentlichte Shannon seine fundamentale Arbeit A Mathematical Theory of Communication und prägte damit die moderne Informationstheorie. In diesem Werk geht es um die Übertragung von Daten, dessen Störung von außen und die Rekonstruktion von Datenfragmenten, die durch Störungen verloren gegangen sind.

Er ersann einen Algorithmus, um den mittleren Informationsgehalt einer Nachricht zu messen und prägte damit den Begriff der Entropie in der Informationstheorie, den er aus der Physik (eine thermodynamische Zustandgröße in Joule per Kelvin) übernahm.

Den mittleren Informationsgehalt bzw. die Informationsdichte zu kennen war für die elektronische Übertragung wichtig, den je höher die Dichte ist, desto schwieriger lassen sich verlorene Zeichen wiederherstellen und desto schwieriger ist es, die Daten zu komprimieren.

In einem gewöhnlichen Text ist die Informationsdichte nicht so hoch (Entropiewert von etwa 3,5 bis 5) und einzelne fehlende Zeichen lassen sich aufgrund ihrer Nachbarn und Wortbedeutung wiederherstellen. Der geschriebenen Sprache ist insofern eine "Checksumme" durch Grammatik eingebaut.

Aber bei einem zufälligen binären Schlüssel (z. B. zur Verwendung bei einem One-Time-Pad) ist die Informationsdichte sehr hoch (Entropiewert von etwa 6 bis 8) und die Rekonstruktion von verloren gegangenen einzelnen Bits nicht möglich. Darum fügt man moderner Kommunikation Paritätsbits hinzu, mit Hilfe dessen sich die Unversehrheit einer Nachricht feststellen lässt und aus denen sich auf mathematischen Wege einzelne, verloren gegangene Teile wiederherstellen lassen, solange noch genügend unbeschädigte Bits in der Nachricht vorhanden sind. Diese Fehlerkorrektur-Bits finden sich in Modem-Datenübertragungsstandards (z. B. MNP5), QR-Codes, RAM-Bausteinen und anderen binären Daten, ohne dass wir sie auf dem ersten Blick erkennen.

Eine Zeichenkette aus Eintausend gleichen Buchstaben hat einen Entropiewert von Null. Die Nachricht ist das Gegenteil von zufällig und besonders gut packbar, denn man könnte statt 1000 As hintereinander (Speicherverbrauch: 1000 Bytes) auch schreiben : "merke dir: 1000 As" (Speicherverbrauch ~ 10 Bytes).

Den Entropiewert kann man nicht nur dazu verwenden, zu bestimmen, ob und in welchem Umfang man eine Fehlerkorrektur benötigt. Man kann ihn auch dazu verwenden, ein Chiffrat einzuordnen. Dabei ist allerdings zu beachten, dass die Shannon-Entropie für binäre Daten (256 Zuständige pro Zeichen 0...255) geschaffen wurde, nicht fürden begrenzten Raum eines Alphabets (26 Zustände, A...Z). Die Werte werden für textuelle Chiffrate also eher keine so signifikanten Unterscheid aufweisen wie für binäre Daten. Für textuelle Daten ist der Koinzidenzindex besser geeignet.
  • Ist die Entropie eher niedrig (um 4) handelt es sich wohl um einen Text, bei dem nur eine Transposition oder monoalphabetische Substitution zum Einsatz kam

  • Ist die Entropie dagegen eher hoch (um 4.5) handelt es sich wohl um einen Text, bei dem eine polyalphabetische Substitution zum Einsatz kam

  • Ist die Entropie für eine binäre Datei hoch (über 6,5), kann man davon ausgehen, dass die Datei verschlüsselt oder gepackt ist.
Auch hat die Länge der Nachricht einen Einfluss auf den Algorithmus. Längere Nachrichten liefern aussagekräftigere Werte.

Beschreibung des Verfahrens

Claude Elwood Shannon definierte die Entropie H einer diskreten, gedächtnislosen Quelle (diskreten Zufallsvariable) X über einem endlichen, aus Zeichen bestehenden Alphabet Z={z1, z2, z3, ...} wie folgt: Zunächst ordnet man jeder Wahrscheinlichkeit p eines Ereignisses seinen Informationsgehalt I(z)= - log 2} pz zu. Dann ist die Entropie eines Zeichens definiert als der Erwartungswert des Informationsgehalts.



Beispiele

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa Entropie (Shannon) = 0 Dies ist ein gewöhnlicher deutscher Text, mit Groß- und Kleinschreibung, Satzzeichen und Umlauten. Entropie (Shannon) = 3,963 And this is a simple english text without much sense but with a lot of letters and some words. Entropie (Shannon) = 3,969 KDZfgfiOTYJSRcfhbITODacGadDAYiPPiENgKfMZGZgcFdJiFJHPaBGHOeaLMjDQWPAhigAZejLddEhjdKeQOCeIBfEMAjbbKPYI (100 zufällige Buchstabe A-Z|a-z) Entropie (Shannon) = 4,269 3B26EE5323F63A6D1817D8941A88C60DB107C2D6551B0EF04B3CAC1891AE9BD4E42C969DCCFCE374C11D80DFC38F2B575A52 6A21FE22B7F7F342546239B4FFDA8C333FA430478BBE256829E56BD9D35E02581327A6285F419C8DFD69E2BBA8E1357DE7AA (100 zufällige Binärzeichen, hex-kodiert) Entropie (Shannon) = 6,624 2B6462A4396898A110A8FAB65BDAF2D5A84DBFDEFD6B39FFBBD5E17385A3F716A1EF61AA6FBF2D25BB7741A7EFB8AAEFC6BB 6F4CFB7DBC381EBC7FB96AB5F7BFD713838F2A0360C0F272EACDFBCE0D584038C1AF17B819B003F68A0A41CED2D54EAFDDB6 EBBE9B133936CEFBD1FBE2F05AFCCB3844824DFDB7CE8670452D74C03FA4EF81F86DEF1BBEAF308D2D6F87A6759FC305894F 8D52FA9A16A9249FCD36BF29D2785E7080447838E14BFF8D5EB72318E0E327E0DF8DFF593AD85E4B9D170280CCC936DADA34 3E25F348EABA96FFCEC2C542FF36FA7BFFC7D7A6FFB79DFFAA0812DF476438C19DC26BCDEEDB1CC0F1A6E7D9679B67C7287A 315F809B3B8B6F505B67C37AAD914EE05FE0AEF7F7BB202060F01CE7B1F59F47D91AB5B676DB8020B2480D8DB4B6567B3C7C (300 Bytes aus einer Zip-komprimierten Datei) Entropie (Shannon) = 7,185 513ADFFA4B012BBAD9ACE2BB56AE85D6B790E20B42E27440E7BB61C1AC46B3974227D8A158F847D147448F8619ACE546BBC1 6856C0C8A1B10E346D443CEB0AD8BD44092B83825DAC7C2657C2BB69F338611624D7BDDDA912E0C7007953C2541D9F161D75 70221C20F0AB35D059D8ECEC1A77F49916287F2A34842495914293F3FAE5D46B6EC37BC757477E507D8147D950BCD241BB6F 522C0AF2A5676D44ED8B6285448C5E7FABDEB822C4F43F3738280194B38AC9CADB150315EEB8D4E43CF75C6BC0ED5BD5FD9F F86DE86558BC02EDB6751053341B4778E2EEBE22C08AC79DA3FAF60F0B8C4BCB0FA9CE441460EC66D090B44A60C74A636202 353DED4AECB618B0A1B4D2AB2A0A5145A1F4C60406010A4945CB8F034051453383E2DF84F95820B9E9583741CB08891BFFFC 386B4B8B (304 Bytes aus einer AES-128bit-CBC-Verschlüsselung) Entropie (Shannon) = 7,234 4CFFFAA8FBD45FE8092FBD2068B55CBF63744F5093316D1BD1576C2A41AEC4B95E018FACBEFA95AF962F1C69A3C0473B057E E14BEE93A397ABADB80747FB8F053CEE7769B2F209EAA06108C43F489AC81B0D910D9A1CEDB78FADE4A844BE7582A0388793 270820320CBF33A6AD22126B75D1A16D7C093B90848DA50724E121A3E844F0438F2431416070F1238FC1233A34B484E66E09 3F8CA96F7E133DF513A22180678A55F6F8B4E88BA3B1E885F772201F8D07F8BD289059F8681B153F639C9A666347D7C3C7A1 50EB8FA4C713A5BAFFF04C32907ADFF8C6379A3FFEE33F2ED7D55547499B6E81A3BA8AE4C936A4E8A095F77C2881CCD39FFF 05D4F522C550A869F29E80BEE873FA8693E4204F78F986D3366F7DD2B3081833BCF7BE56FD227464E47FBF3D526C77F90461 (300 Bytes aus .png-Grafikdatei (komprimiert)) Entropie (Shannon) = 7,199 FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF1F1F1F2020202020202020202020202020202020202020202020201F1F1FFFFF FFFFFFFFFFFFFFFFFFFF1F1F1F20202020202020202020202020202020202020201F1F1FFFFFFFFFFFFFFFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFFFFFF1F1F1F2020202020202020202020202020202020202020202020201F1F1FFFFFFFFFFFFFFFFFFFFF FFFF1F1F1F20202020202020202020202020202020202020201F1F1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF FFFF1F1F1F2020202020202020202020202020202020202020202020201F1F1FFFFFFFFFFFFFFFFFFFFFFFFF1F1F1F202020 20202020202020202020202020202020201F1F1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF1F1F1F202020 (300 Bytes aus .bmp-Grafikdatei (unkomprimiert)) Entropie (Shannon) = 1,427

Code / Chiffre online dekodieren / entschlüsseln bzw. kodieren / verschlüsseln (Decoder / Encoder / Solver-Tool)

Quellen, Literaturverweise und weiterführende Links

Wikipedia-Artikel zur Entropie
Wikipedia-Artikel zur Entropie
Claude E. Shannon: A Mathematical Theory of Communication, 1948