Entropiemessung eines Textes

[Hans Meibach]

Hallo!

Hat jemand einen kleinen Beispielsource,
wie man die Entropie/Zufall eines Strings prüft?
Nun konnte ich zwar nachlesen, wie häufig
z.B. der Buchstabe "e" usw. im deutschen Alphabet vorkommt, aber irgendwie reicht mir diese Information nicht aus.
Außerdem soll die Funktion am besten auch
mit englischen Texten klarkommen.
Interessant wäre auch, wie man die Entropie
bei Binärdaten bewertet und ob man verschlüsselte Binärdaten mit denen "normaler" (diverse Fileformate) Daten vergleichen kann.

Alles, was weiterhilft, wird gerne genommen.

Vielen Dank vorab, Hans

[Robert Marquardt]

Da hat sich Zippen als guter Massstab herausgestellt. Filegroesse zu gezippter Filegroesse ist ein Mass fuer die Entropie. Es ist uebrigens auch sprachspezifisch und kann daher zur Erkennung der Sprache benutzt werden

[Günther Samane]

// Zuerst mußt du die Häufigkeit der enthaltenen Zeichen ermitteln. Dies lässt sich mit einem array[0..255] byte realisieren.
&lt
for i := 1 to Length(Text) do begin
for j := 0 to 255 do begin
if(hArray[j] = Ord(Text[i]) then inc(hArray[j])
end;
end;
&gt

// Nun muß der Informationsgehalt(M[i])der enthaltenen Zeichen gemessen werden.
&lt
for i := 0 to 255 do begin
if(hArray[i] > 0) then mArray[i] := -log(hArray[i])
end;
&gt

// Nach dieser Berechnung kann die Entropiemessung auf Basis des mArray[] erfolgen.
// Dazu durchläuft du das mArray[] und alle Elemente > 0 werden für die Entropie benötigt.
&lt
for i := 0 to 255 do begin
if(mArray[i] <> 0) then Entropie := Entropie + -(mArray[i] * log(mArray[i])
end;
&gt

So stehts jedenfalls in einem Buch geschrieben.
Hoffe, konnte helfen.
- Günthe

[Hagen Reddmann]

Zippen als Sicherheitskriterium für Passwörter oder verschlüsselte Messages reicht nicht aus. Eine Verschlüsselung muß nicht zwangsläufig sicherer sein je zufälliger sie wirkt. Das ist sogar grund verkehrt. Z.b. es gibt Stromverschlüsselungen wie RC4 und Blockverschlüsselungen wie Blowfish. Interessant ist nun das die Stromverschlüsselungen meistens eine wesentlich besserer Entropie erzeugen als Blockverschlüselungen. D.h. Stromverschl. wirken viel zufälliger und lassen sich ca. 3-5% komprimieren, Blockverschl. lassen sich bis zu 20% komprimieren. ABER! jetzt der Witz an der Sache: Strimverschl. wurde schon kurz nach dem 2. WK durch die differentielle Kryptoanalyse geknackt und aus diesem Wissen heraus entstanden erst die Blockverschlüsselungen. Es wird allgemein angenommen das Blockverschl. viel sicherer sind als Stromverschlüsselungen.

Zur Messung von Daten auf deren Entropie gibt es verschiedene annerkannte Verfahren, "Run Length Test", "Bit Length Test", "Mono Bit Test", "Poker Test", suche mal nach <i>FIPS PUBS 140-1, Federal Information Processing Standards Publications</i>.<br>

Deine Frage scheint mir darauf abzuzielen das du eine eigene Verschlüsselung testen möchtest. In diesem Falle wären solche Tests nur eine leichte Untermauerung des nötigen mathematischen Beweises das der Algo. sicher ist. Einfach mal so eben einen Algo. zu entwicklen und zu prüfen ob er statistischen Überprüfungen standhält reicht da bei weitem nicht aus.

Willst du aber anhand der Entropiebestimmung erkennen ob eine Datei verschlüsselt wurde oder nicht, so kann ich dir sagen das auch das nicht möglich ist. Zumindestens sind es die vielen Ausnahmen die nicht in den Griff zu bekommen sind. Also z.b. eine komprimierte Datei sieht aus wie verschlüsselt und eine verschlüsselte Datei sieht aus wie komprimiert.<br>
Zudem gibt es durch die Steganographie ein Mittel mit dem man seine verschl. Daten in Bilder oder Waves einbetten kann. In diesem Moment würde man annehmen müssen das diese Daten nicht verschlüsselt wurden und denoch enthalten sie verschlüsselte Daten. Dies funktioniert auch umgekehrt. D.h. Daten erscheinen so als wurden verschl. Daten eingebette wo aber keine sind. Das ist ja auch der Sinn von Steganographie.<br>

Willst du die Qualität eines Passworts überprüfen so reicht eine Entropiemessung ebenfalls nicht aus. Es gibt nämlich Wissensbasierte Passwortangriffe die eine solche Entropiemessung ins Gegenteilige verkehren. Z.b. wäre ein Passwort wie "11a7z5" eine relativ gute Wahl nach der Entropie, aber eine enorm schlechte Wahl wenn man weis das ICH Primzahlen liebe und diese immer mit Buchstaben kombiniere. Dies ist eben Wissensbasiert. Die meisten Verfahren nutzen dazu Dictionaries.

Gruß Hage