3.3 Entropie

Während sich Netzspezialisten unter anderem um das Problem der Kanalkapazität kümmern müssen, interessiert den Kryptologen viel eher, welche Eigenschaften die übermittelten Informationen haben.

Denn um eine Nachricht wirksam zu verschlüsseln muß man wissen, welche Eigenschaften überhaupt die Information ausmachen, die in der Nachricht übermittelt wird.

Deswegen fängt man ganz unten an. Man fragt sich, welchen Informationsgehalt die einzelnen Zeichen theoretisch besitzen - und dazu machen wir einen kleinen Abstecher in die Wahrscheinlichkeitsrechnung.

Stellen wir uns vor, wir haben einen Vorrat an Zeichen, die durch Folgen von "ja-nein"-Entscheidungen unterscheidbar sind. Dies ist nicht ungewöhnlich, jeder handelsübliche Computer funktioniert auf diese Weise - übrigens auch einige TV-Quizsendungen. Um ein Zeichen zu erhalten, muß man dann eine gewisse Anzahl von Auswahlentscheidungen treffen. Diese Anzahl ist der Informationsgehalt des Zeichens.

Nehmen wir an, daß wir ein Repertoire R = A,B,C,D haben, dann erhält man jedes Zeichen in zwei Schritten. Zunächst teilt man die Menge in zwei gleichgroße Teile und schaut nach, wo sich das gesuchte Zeichen befindet. Dann wiederholt man den Schritt für die Teilmenge, die das Zeichen enthält. Schließlich erhält man das gesuchte Zeichen. Der Informationsgehalt für jedes der vier Zeichen ist also 2 bit.

Allgemein gilt der Zusammenhang

N=2^I

wobei

N die Anzahl der Zeichen des Alphabets ist und
I der Informationsgehalt eines Zeichens

Um I zu erhalten wendet man den Logarithmus an, in diesem Falle den Logarithmus zur Basis 2 (logarithmus dualis, ld).

Man erhält also

I = ld N

mit der Einheit [bit/Zeichen].

Diese Annahme gilt jedoch nur für Zeichenvorräte, bei denen jedes Zeichen gleichhäufig vorkommt.

Die Wahrscheinlichkeit in diesem Fall ist dann

p1 = p2 = ... = pN = 1/N

(denn die Summe aller Einzelwahrscheinlichkeiten ergibt stets 1).

Etwas anders sieht es aus, wenn die Einzelwahrscheinlichkeiten unterschiedlich sind. Dann ändert sich der Zusammenhang in

I(zi) = ld (1/pi) bit

Dies kann man umformen in

I(zi) = ld 1 - ld pi = -ld pi

Dies ist der realistische Rahmen, denn eine Gleichverteilung tritt in der Regel nicht auf. Spätestens seit dem Auftreten der internationalen "Glücksradshow" weiß man zumindest, daß das "e" im Deutschen der häufigste Buchstabe ist. Man kann so die charakteristische Verteilung eines Textes bestimmen. Vorsicht ist jedoch bei vorgefertigten Tabellenwerken gegeben. Diese können die Verteilung nur sehr unscharf wiedergeben, denn jeder Text trägt in sich die charakteristischen Merkmale des Autors.

Betrachtet man nun über einen längeren Zeitraum eine Nachricht, die ja aus Zeichenketten zusammengesetzt ist, so möchte man natürlich ein Maß für den mittleren Informationsgehalt haben. Genau dieses bekommt man in folgendem Zusammenhang:

H ist die negative Summe über (p_i * ld(p_i)) für i=1...n

wobei

p_i die Einzelwahrscheinlichkeit des Zeichens x_i und
n die Anzahl der verwendeten Zeichen

darstellen.

Somit hängt die Entropie direkt von den Wahrscheinlichkeiten (oder tatsächlichen Häufigkeiten) eines Zeichens ab. Im Deutschen findet man im allgemeinen die Buchstaben ETAONI am häufigsten, die Buchstaben JKXQZ bilden das Schlußlicht.

Dieses H nennt man Entropie der Nachrichtenquelle oder mittleren Entscheidungsgehalt. Wir wollen nicht weiter darauf eingehen, tiefere theoretische Zusammenhänge können z.B. in [6] oder [8] nachgesehen werden.

Die Entropie ist der zentrale Punkt bei Texten, seien sie nun verschlüsselt oder nicht. Wenn man Erkenntnisse über die Entropie einer Nachricht erhält, kann man auf die enthaltene Information zugreifen. Wer also eine unbefugt eine verschlüsselte Nachricht abfängt, möchte demnach zuerst die Entropie der Nachricht bestimmen. Sie ist der Schlüssel zur Information.

Wir wollen einmal ein Beispiel durchrechnen:

"The Babel fish," said The Hitch Hiker's Guide to the Galaxy quietly, "is small, yellow and leech-like, and probably the oddest thing in the Universe. It feeds on brainwave energy not from its carrier but from those around it. It absorbs all unconscious mental frequencies from this brainwave energy to nourish itself with. It then excretes into the mind of ist carrier a telepathic matrix formed by combining the conscious thought frequencies with nerve signals picked up from the speech centres of the brain which has supplied them. The practical upshot of all this is that if you stick a Babel fish in your ear you can instantly understand anything said to you in any form of language. The speech patterns you actually hear decode the brainwave matrix which has been fed into your mind by your Babelfish. [...]
Meanwhile, the poor Babel fish, by effectively removing all barriers to communication between different races and cultures, has caused more and bloddier wars than anything else in the history of creation." (Aus [9])

Eine Analyse dieses Zitats ergibt für die insgesamt 1610 Zeichen (Leerzeichen und Interpunktion nicht mitgerechnet) folgende Werte:

 Zeichen     Wahrscheinlichkeit   Entropie
   E               0.1068          0.34
   T               0.0882          0.31
   I               0.0801          0.29
   A               0.0783          0.29
   O               0.0752          0.28
   N               0.0702          0.27
   S               0.0646          0.26
   H               0.0615          0.25
   R               0.0497          0.22
   L               0.0416          0.19
   D               0.0360          0.17
   C               0.0329          0.16
   U               0.0323          0.16
   F               0.0292          0.15
   B               0.0255          0.13
   Y               0.0255          0.13
   G               0.0242          0.13
   M               0.0224          0.12
   P               0.0161          0.10
   W               0.0124          0.08
   V               0.0118          0.08
   K               0.0068          0.05
   X               0.0050          0.04
   Q               0.0025          0.02
   Z               0.0012          0.01
   J               0.0000          0.00

Die mittlere Entropie der Zeichen im vorliegenden Text beträgt

H = 4.2285 bit.

Dies alleine wäre noch sehr unsicher, aber man kann das nun für n-Gramme fortführen. n-Gramme sind Kombinationen von Zeichen, die vorkommen dürfen. Für n=2 sind das Bigramme, also Kombinationen von 2 Zeichen, für n=3 werden sie Trigramme genannt. So kommen im Deutschen als Bigramme häufig "ee" vor, im Englischen die Kombinationen "ea" und "th". Im Deutschen steht "s" oft vor einem Mitlaut, "r" steht eher neben Selbstlauten.

Weitere n-Gramm-Tabellen finden Sie beispielsweise in [6]. Die Analyse solcher n-Gramme ist ein Grundwerkzeug der Kryptologie.

Daß man umgekehrt mit solchen Tabellen auch wieder (unsinnige) Texte erzeugen kann, die einem echten Text täuschend ähnlich sehen, sei hier nur nebenbei bemerkt. So ein Programm ist recht einfach zu schreiben: Zunächst analysiert man einen Originaltext, z.B. Shakespeare oder den Quelltext eines C-Programms. Danach kann man mit Hilfe der Zufallsfunktion, die durch solche n-Gramm-Tabellen gewichtet wurde, einen künstlichen Text erzeugen, der keinerlei Sinn enthält, der aber durchaus den Stil des Originals nachahmt. Es kann so ein weiteres "Shakespeare-Drama" herauskommen oder ein (formal) fehlerfreies C-Programm, je nach dem, wie groß n ist. Solche Programme werden auch manchmal Eddington-Affen genannt.