Friedman-Test

Neue Frage »

jokin Auf diesen Beitrag antworten »
Friedman-Test
Hallo jungs,
ich arbeite gerade ein Bisschen mit dem Thema Kryptographie.
Zum Knacken von polyalphabetischen Substitutionsverschlüsselungen soll sich ja angeblich der Friedman-Test bewähren. Mit ihm kann man scheinbar die Länge des verwendeten Schlüssels bestimmen. Soweit so gut.

Ich habe mir die Formel dafür angesehen und etwas geknobelt und soweit ich das einschätze, bin ich da richtig mitgekommen bzw ich halte das ganze für nachvollziehbar, warum das so ist.

Der Praxistest allerdings macht mich etwas stutzig.
Mein Prüftext war gut 300.000 Zeichen lang, meine Schlüssellänge bewegte sich in allen möglichen Dimensionen... Also von 5 bis 50.000 smile
Die jeweils Testhalber berechnete vermutete Schlüssellänge jedoch ließ zu wünschen übrig. Zwar kam sie immer "in etwa" in die Region, wo die tatsächliche Schlüssellänge lag, aber welchen praktischen Wert hat eine Abweichung von teilweise über 20% für einen Angreifer?

Langer Rede kurzer Sinn: Wie genau ist die mit dem Friedman-Test berechnete vermutete Schlüssellänge in der Regel denn so?
sqrt(2) Auf diesen Beitrag antworten »

Ich habe das gerade einmal selbst implementiert und erhalte ähnliche Resultate wie du. Ich habe mal einen Plot angehängt, der den Zusammenhang zwischen Abweichung von der wahren Schlüssellänge (die sich logischerweise nur durch eine additive Konstante -- die Schlüssellänge -- von der berechneten Schlüssellänge unterscheidet) und Koinzidenzindex aufzeigt. Mein zu Grunde liegender Text ist der Anfang von Goethes Werther, den ich von Leer- und Sonderzeichen bereinigt habe, die Umlaute umgewandelt und den gesamten Text schließlich auf Kleinbuchstaben gebracht, was in 20089 Zeichen resultiert. Die verwendete Schlüssellänge war 5, die verwendeten Schlüssel zufällige Zeichenketten.

Sowohl aus dem Plot als auch aus der Gleichung für die Schlüssellänge im Friedman-Verfahren sieht man, dass es sich dabei um einen antiproportionalen Zusammenhang handelt, also der Graph eine Hyperbel ist, und damit erklären sich wohl auch die zum Teil sehr großen Abweichungen; wenn sich der Koinzidenzindex in bestimmten Bereichen nur um einige Prozent ändert, hat das starke Auswirkungen auf die berechnete Schlüssellänge, 20% und mehr.

Nur, wenn ich mit Friedman die Schlüssellänge auch nur auf 20% eingrenzen kann, dann erspare ich mir damit schon einiges an Rechenzeit; angenommen die berechnete Schlüssellänge ist 10, dann kann ich die Schlüssellänge 12 ansetzen und, indem ich zunächst die ersten Ziffern des Schlüssels variiere, kürzere Schlüssel schon früher finden, vorausgesetzt, die ersten paar Stellen des Textes haben irgend einen Sinn. Ginge ich von noch kürzeren Schlüsseln als 8 aus, müsste ich auf deutlich mehr Text das Entschlüsselungsverfahren anwenden, um zu überprüfen, ob der Schlüssel möglicherweise korrekt ist.

Falls ich eine Wörterbuchattacke starte, ist eine Eingrenzung auf 20% sogar extrem nützlich und dürfte in sehr kurzer Zeit zum Ziel führen, weil die Anzahl der Schlüssel wohl nur noch in der Größenordnung 10^3 liegt; dazu ist jeder Heimrechner imstande.
jokin Auf diesen Beitrag antworten »

Hallo!

Gleich zuerst möchte ich mich entschuldigen, aber die letzten Tage waren recht voll und da blieb mir keine Zeit, mich weiter mit dem Problemchen zu beschäftigen.

Dann kommt gleich ein freundliches "Dankeschön" an sqrt(2), für den hilfreichen Beitrag und für seine "weiterführenden Recherchen" auf meiner Homepage smile

Jetzt aber zurück zum Wesentlichen:
Meine Testwerte sind immer noch unbefriedigend. Während dein Diagramm ja erkennen lässt, dass es einen Bereich gibt, in dem der K-Index relativ gute Arbeit leistet, ja teilweise sogar die präzise Schlüssellänge ausgeben kann, haperts bei mir noch.

Meine Berechnungsfunktion für n ist korrekt. Das habe ich mittlerweile überprüft. Für k = \phi = 1/a (a = Anzahl der Buchstaben im Alphabet) erhalte ich eine Schlüssellänge von n = m, das entspricht ja dem One-Time-Pad: Jedes statistische Merkmal des Klartextes ist verwischt.
Und für k = \mu = Summe über 1/p_i^2 (p_i = Wahrscheinlichkeit des i-ten Buchstabens) erhalte ich n = 1, dh der Text wurde quasi nicht verschlüsselt, höchstens "verschoben" und alle statistischen Merkmale des Klartextes sind noch da.

Der Koinzidenzindex gibt quasi an, inwiefern die "Spuren" des Klartextes noch sichtbar sind und da mit zunehmender Schlüssellänge auch diese "Spuren" schwächer werden, kann man damit Rückschlüsse auf die Schlüssellänge anstellen.

Ja jetzt jedenfalls das Problem:
Wenn ich aus der tatsächlichen Schlüssellänge den "zu erwartenden" K-Index errechne und den mit dem "angeblich gerade vorliegenden" K-Index vergleiche, weisen die beiden Werte doch eine nicht akzeptable Differenz auf....

Könntest du mir einen Ratschlag erteilen, wie ich die Berechnung des K-Indexes am besten im Programm realisieren kann?

(Erst die p_i's ermitteln, oder einfach Buchstabe für Buchstabe des Textes durch... Irgend n Tip halt...)
sqrt(2) Auf diesen Beitrag antworten »

Zitat:
Original von jokin
Könntest du mir einen Ratschlag erteilen, wie ich die Berechnung des K-Indexes am besten im Programm realisieren kann?


Also der Koinzidenzindex ist ja die Wahrscheinlichkeit, dass zwei zufällig aus dem Text ausgewählte Buchstaben gleich sind. Es gibt Möglichkeiten, zwei Buchstaben aus einem Text der Länge auszuwählen. Ist die absolute Häufigkeit des i-ten Buchstabens im Text, so gibt es für jeden Buchstaben günstige Möglichkeiten, nach Laplace macht das also insgesamt

,

und dementsprechend sieht das bei mir auch aus:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
final static char ALPH_LOW = 'a';   // erster Buchstabe des Alphabets
final static char ALPH_HIGH = 'z';  // letzter Buchstabe des Alphabets

public static double coincidenceIndex(Vector text) {
    int[] alphabet = new int[ALPH_HIGH - ALPH_LOW + 1];
    // bestimme Frequenzverteilung
    for (int i = 0; i < text.size(); i++) {
        char c = ((Character)text.get(i)).charValue();
        alphabet[c - ALPH_LOW]++;
    }
    // bestimme Konizidenzindex
    long sum = 0;
    for (int i = 0; i < alphabet.length; i++)
        sum += alphabet[i] * (alphabet[i] - 1);
    return (float)sum / text.size() / (text.size() - 1);
}


Das Laufzeitverhalten ist O(n), und zumal man mindestens einmal über den Text gehen muss, um alle Buchstaben zu lesen, geht's wohl auch nicht schneller.
jokin Auf diesen Beitrag antworten »

Okok, es handelte sich um einen ganz profanen Programmierfehler...
Nachdem ich das nun endlich bemerkt habe, funktioniert der Test durchaus zufriedenstellend.

Dankeschön!
jokin Auf diesen Beitrag antworten »

Eine Frage taucht bei mir nun aber doch noch auf:
Mit was für einem Programm hast du dieses schicke Diagramm geplottet?

Ich habe auch en masse Datenreihen, die ich plotten muss und ehrlich gesagt hängt mir die Diagramm Funktion von OpenOffice langsam zum Hals raus... Das ist so ewig lahm und zickig...

Und bevor ich mir auch dazu noch ein Programm schreiben muss....
 
 
sqrt(2) Auf diesen Beitrag antworten »

Das Diagramm hab ich mit gnuplot gemacht: http://www.gnuplot.info/
jokin Auf diesen Beitrag antworten »

ok, also auf ein neues:
oder auch: die suche geht weiter


so oft ich auch schiebe und wende und probiere...
so gut wie bei dir werden meine testergebnisse nicht...

nicht nur das, ich habe auch einen ganz anderen zusammenhang...

dann muss ich noch einschieben, dass ich meine fehler "absolut" gemessen habe, also ohne angabe, ob der berechnete schlüssel zu kurz oder zu lang war... wenn ich 500 tests mache und den fehler im durchschnitt errechnen möchte, scheint mir das auch sinnvoll, da fehler "mit vorzeichen" sich ja dann rausheben...

also jedenfalls funktioniert der friedmantest bei mir nur dann einigermaßen vernünftig, wenn k noch nahe am maximalwert ist. dort ist die ableitung dk/dn am steilsten, eine minimale änderung von n ändert k ganz immens, eine kleine änderung an k hat für die umkehrfunktion kaum eine bedeutung. sprich statistische fehler fallen nicht so sehr ins gewicht. der raum der einer bestimmten schlüssellänge zugeordnet wird ist sehr groß. dagegen wird bei kleinen ks die ableitung sehr flach. hier kann man n leicht ändern, ohne k groß zu beeinflussen, im umkehrschluss jedoch hat schon ein minimal anderes k einen völlig verschieden langen schlüssel zur folge.

ein diagramm "fehler in abhängigkeit vom k index" ergibt bei mir keine hyperbel wie bei dir, sondern eine die der kurve 1/x gleicht (nur halt die y-achse bis zum theoretischen mindestwert von k verschoben)

soweit so gut. dummerweise fällt mein k schon bei einem schlüssel der länge 4 quasi auf den minimalwert ab, danach tut sich kaum noch was. praktische beobachtung und theoretische erwartung stimmen hier erstaunlich gut überein.

das heißt ab schlüsseln länger als 3-5 ist der friedmantest quasi wertlos.

was für mich im endeffekt den ganzen test hinfällig macht, da ich meine tests mit texten der länge von mehreren zig tausend zeichen und schlüsseln die entsprechend mehrere 100 zeichen haben, durchführe.

die letzte mögliche hoffnung die ich noch habe, ist dass dieser entscheidende unterschied daher rührt, dass mein alphabet aus praktischen zwecken statt 26 stolze 38 zeichen enthält. aber da bin ich nicht optimistisch. erstens könnte ich mir das nicht wirklich erklären, zweitens hab ich mein alphabet testhalber auf 26 reduziert und keine verbesserung festgestellt..

wenn du nun tatsächlich schreibst, dass dein friedmantest tatsächlich dort funktioniert wo ich nur noch fehler im raum von 20-40% einfahre, dann muss ich nochma tierisch penibel nach eventuellen fehlerquellen suchen... :/
sqrt(2) Auf diesen Beitrag antworten »

Die schon auf deine PN hin vorbereitete Antwort... Augenzwinkern

Zitat:
Original von jokin
so oft ich auch schiebe und wende und probiere...
so gut wie bei dir werden meine testergebnisse nicht...

So gut sind meine Ergebnisse nicht; wie ich schon schrieb, sie haben ungefähr die Qualität deiner Ergebnisse. In 50% der Fälle liegt der Fehler unter 20%, in 90% der Fälle unter 40%.

Zitat:
Original von jokin
ein diagramm "fehler in abhängigkeit vom k index" ergibt bei mir keine hyperbel wie bei dir, sondern eine die der kurve 1/x gleicht (nur halt die y-achse bis zum theoretischen mindestwert von k verschoben)

f(x)=1/x ist eine Hyperbel.

Zitat:
Original von jokin
was für mich im endeffekt den ganzen test hinfällig macht, da ich meine tests mit texten der länge von mehreren zig tausend zeichen und schlüsseln die entsprechend mehrere 100 zeichen haben, durchführe.

Schlüssel mit mehreren hundert Zeichen? Du brauchst einen Supercomputer...

Zitat:
Original von jokin
die letzte mögliche hoffnung die ich noch habe, ist dass dieser entscheidende unterschied daher rührt, dass mein alphabet aus praktischen zwecken statt 26 stolze 38 zeichen enthält. aber da bin ich nicht optimistisch. erstens könnte ich mir das nicht wirklich erklären, zweitens hab ich mein alphabet testhalber auf 26 reduziert und keine verbesserung festgestellt..

Andere Alphabete haben natürlich andere und . Während noch mit leicht zu bestimmen ist, musst du für wohl für sehr viel unverschlüsselten deutschen Text deines Alphabets den Koinzidenzindex ermitteln.

Es gibt übrigens noch eine andere Möglichkeit, die Schlüssellänge eines polyalphabetisch chiffrierten Textes zu bestimmen: Du verschiebst den chiffrierten Text jeweils um eine Stelle und vergleichst diesen Text Stelle für Stelle mit dem ursprünglichen Geheimtext. Du wirst relative Häufigkeiten für Koinzidenz um herum erhalten, alle Verschiebungen allerdings Werte um herum (du vergleichst dann ja schließlich immer Buchstaben, die mit demselben Buchstaben des Schlüssels verschlüsselt wurden). Ich habe das noch nicht implementiert, aber davon würde ich mir deutlich bessere Ergebnisse als mit dem Friedmantest über den globalen Koinzidenzindex erwarten; es dauert nur eben deutlich länger.
jokin Auf diesen Beitrag antworten »

ja ich weiß, dass 1/x auch ne hyperbel ist. nur war deine hyperbel eben mehr à la -(1/x)... meine eben umgedreht...
/edit:
ah ich honk... das liegt natürlich an dem umstand, dass ich nur absolute fehler ermittelt habe.
naja trotzdem: meine asymptode ist die 0%-fehler gerade und die wird wie der name schon sagt, nicht die bei dir geschnitten... also je höher der index, desto fehlerfreier...


an die sich ändernden werte von phi und mu habe ich auch gedacht. das ging am ende soweit, dass ich mu für jeden testtext vorher neu errechnen hab lassen....


zum thema supercomputer: also eine einzelne verschlüsselung macht mein stinknormaler desktop pc quasi mit einem wimpernschlag...
für eine etwas aufwändigere statistik (habe den friedmantest mit immer neu generierten zufälligen schlüsseln von der länge 1 bis zur länge 1000 pro schritt 500 mal durchführen lassen und dann eben die messergebnisse von den 500 mal gemittelt und als datenlog danach mit gnuplot inspiziert... für diese operation musste ich den rechner allerdings gute 5 stunden lang nudeln lassen smile )

dann komme ich hiermit zu dem befund, dass der friedman test einfach am limit ist.

die idee mit dem konkreten koinzidenz index hatte ich übrigens auch schon, nur in anderer form. ich habe daraus auch schon ein extrem gut funktionierenes system zur bestimmung der schlüssellänge gezimmert. das allerdings, du sagst es, wesentlich länger dauert als der friedman test.

nunja, damit ist die sache dann endgültig bei den akten.

vielen dank nochmal für dein engagement. auch der tip mit gnuplot war gold wert. ich werd dir die facharbeit zukommen lassen smile
sqrt(2) Auf diesen Beitrag antworten »

Zitat:
Original von jokin
ja ich weiß, dass 1/x auch ne hyperbel ist. nur war deine hyperbel eben mehr à la -(1/x)... meine eben umgedreht...
/edit:
ah ich honk... das liegt natürlich an dem umstand, dass ich nur absolute fehler ermittelt habe.
naja trotzdem: meine asymptode ist die 0%-fehler gerade und die wird wie der name schon sagt, nicht die bei dir geschnitten... also je höher der index, desto fehlerfreier...

Es kommt halt darauf an, was da wogegen aufgetragen wird... So kann ich mir wenig darunter vorstellen.

Zitat:
Original von jokin
zum thema supercomputer: also eine einzelne verschlüsselung macht mein stinknormaler desktop pc quasi mit einem wimpernschlag...

Ich bezog mich eher auf den Entschlüsselungsvesuch, selbst wenn man eine ungefähre Schlüssellänge hat.

Zitat:
Original von jokin
dann komme ich hiermit zu dem befund, dass der friedman test einfach am limit ist.

Das nehme ich auch an.

Zitat:
Original von jokin
ich werd dir die facharbeit zukommen lassen smile

Eine Facharbeit? Ja, da wäre ich interessiert... smile
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »