nicht angemeldet
Kasiski-Test - Javascript Tool
Hallo allerseits,
ich bin seit einigen Tagen damit beschäftigt den Kasiski-Test mit Javascript zu realisieren.
Als erstes ist es nötig alle Wiederholungen von Buchstabenfolgen (3 oder länger) im Kryptogramm zu finden. Ich habe nun eine Funktion geschrieben, die mir absolut jede Wiederholung in ein Array schreibt. Hier kommt die 1. Frage: gegeben sei der Text 'hausgartenkatzegartenhund'. Meine Funktion würde nun finden: garten , garte , arten , gart , arte , rten , gar , art , rte , ten. Ist es nun wirklich das, was man beim Kasiski-Test wirklich macht? Oder "zählt" nur das längste eines Wortes - hier also nur garten? Wenn ja, wie filtere ich zuverlässig alle anderen Treffer raus?
2: Nun müssen die Abstände zwischen den gleichen Wiederholungen bestimmt werden - geschafft.
3: Zum Schluss müssen aus den ermittelten Abständen die ganzzahligen Teiler berechnet werden - geschafft.
Jetzt zähle ich, wie oft ich welchen Teiler gefunden habe. Nun ist die Schlüssellänge am wahrscheinlichsten, bei welchem größten Teiler noch hinreichend Treffer vorhanden sind.
Ich habe mal im Internet nach Kasiski-Tests geschaut und bin auf diese Seite gekommen. Gebt dort folgendes englisches Kryptogramm bei 'Vigenere ciphered text' ein und klickt auf 'Find Key Length'. Auf der linken Seite bei 'Results' erscheint dann eine Liste mit den Wahrscheinlichkeiten der möglichen Schlüssellänge. Bei folgendem Kryptogramm kommt heraus:
- 6 lett. 71.4%
- 2 lett. 56.9%
- 12 lett. 54.8%
- 3 lett. 54.4%
- 18 lett. 47.3%
- 4 lett. 37.9%
- 8 lett. 31.2%
- 16 lett. 27.8%
- 9 lett. 27.7%
- 10 lett. 23.3%
- 14 lett. 22.7%
- 15 lett. 22.6%
- 5 lett. 13.4%
- 7 lett. 12.2%
- 13 lett. 8.8%
- 11 lett. 7.1%
- 17 lett. 6.4%
- 19 lett. 5.7%
Das Kryptogramm:
CVJTNAFENMCDMKBXFSTKLHGSOJWHOFUISFYFBEXEINFIMAYSSDYYIJNPWTOKFRHWVWTZFXH LUYUMSGVDURBWBIVXFAFMYFYXPIGBHWIFHHOJBEXAUNFIYLJWDKNHGAOVBHHGVINAULZFOF UQCVFBYNFTYGMMSVGXCFZFOKQATUIFUFERQTEWZFOKMWOJYLNZBKSHOEBPNAYTFKNXLBVUA XCXUYYKYTFRHRCFUYCLUKTVGUFQBESWYSSWLBYFEFZVUWTRLLNGIZGBMSZKBTNTSLNNMDPM YMIUBVMTLOBJHHFWTJNAUFIZMBZLIVHMBSUWLBYFEUYFUFENBRVJVKOLLGTVUZUAOJNVUWT RLMBATZMFSSOJQXLFPKNAULJCIOYVDRYLUJMVMLVMUKBTNAMFPXXJPDYFIJFYUWSGVIUMBW STUXMSSNYKYDJMCGASOUXBYSMCMEUNFJNAUFUYUMWSFJUKQWSVXXUVUFFBPWBCFYLWFDYGU KDRYLUJMFPXXEFZQXYHGFLACEBJBXQSTWIKNMORNXCJFAIBWWBKCMUKIVQTMNBCCTHLJYIG IMSYCFVMURMAYOBJUFVAUZINMATCYPBANKBXLWJJNXUJTWIKBATCIOYBPPZHLZJJZHLLVEY AIFPLLYIJIZMOUDPLLTHVEVUMBXPIBBMSNSCMCGONBHCKIVLXMGCRMXNZBKQHODESYTVGOU GTHAGRHRMHFREYIJIZGAUNFZIYZWOUYWQZPZMAYJFJIKOVFKBTNOPLFWHGUSYTLGNRHBZSO PMIYSLWIKBANYUOYAPWZXHVFUQAIATYYKYKPMCEYLIRNPCDMEIMFGWVBBMUPLHMLQJWUGSK QVUDZGSYCFBSWVCHZXFEXXXAQROLYXPIUKYHMPNAYFOFHXBSWVCHZXFEXXXAIRPXXGOVHHG GSVNHWSFJUKNZBESHOKIRFEXGUFVKOLVJNAYIVVMMCGOFZACKEVUMBATVHKIDMVXBHLIVWT JAUFFACKHCIKSFPKYQNWOLUMYVXYYKYAOYYPUKXFLMBQOFLACKPWZXHUFJYGZGSTYWZGSNB BWZIVMNZXFIYWXWBKBAYJFTIFYKIZMUIVZDINLFFUVRGSSBUGNGOPQAILIFOZBZFYUWHGIR HWCFIZMWYSUYMAUDMIYVYAWVNAYTFEYYCLPWBBMVZZHZUHMRWXCFUYYVIENFHPYSMKBTMOI ZWAIXZFOLBSMCHHNOJKBMBATZXXJSSKNAULBJCLFWXDSUYKUCIOYJGFLMBWHFIWIXSFGXCZ BMYMBWTRGXXSHXYKZGSDSLYDGNBXHAUJBTFDQCYTMWNPWHOFUISMIFFVXFSVFRNA
Nun wollte ich auch eine solche Prozent-Bewertung anbieten. Allerding kann ich nicht nachvollziehen, nach welchem Prinzip ich die Anzahl der gefundenen Teiler in eine Prozentangabe überführen könnte. Besitzt das Schlüsselwort nun eine Länge von 6 habe ich bei den gefundenen Teilern bei 2 und 3 eine mindestens ebenso große Zahl wie für 6... Ich hoffe auf ein paar Tipps in diese Richtung.
Ein Dankeschön an alle, die es bis hierhin geschafft haben.
Reinhard
-
Tach,
Als erstes ist es nötig alle Wiederholungen von Buchstabenfolgen (3 oder länger) im Kryptogramm zu finden. Ich habe nun eine Funktion geschrieben, die mir absolut jede Wiederholung in ein Array schreibt. Hier kommt die 1. Frage: gegeben sei der Text 'hausgartenkatzegartenhund'. Meine Funktion würde nun finden: garten , garte , arten , gart , arte , rten , gar , art , rte , ten. Ist es nun wirklich das, was man beim Kasiski-Test wirklich macht? Oder "zählt" nur das längste eines Wortes - hier also nur garten? Wenn ja, wie filtere ich zuverlässig alle anderen Treffer raus?
du interessierst dich ja nicht für den Inhalt der Wiederholungen sondern für die Abstände; kürzere Doppelungen würde ich also nur registrieren, wenn die Abstände unterschiedlich sind.
Nun wollte ich auch eine solche Prozent-Bewertung anbieten. Allerding kann ich nicht nachvollziehen, nach welchem Prinzip ich die Anzahl der gefundenen Teiler in eine Prozentangabe überführen könnte.
Ich sehe auch nicht, was Prozente hier aussagen sollen; ich würde eher ein gewichtetes Scoringverfahren verwenden, um die Teiler nach Güte zu sortieren.
mfg
Woodfighter-
Hallo,
gegeben sei der Text 'hausgartenkatzegartenhund'. Meine Funktion würde nun finden: garten , garte , arten , gart , arte , rten , gar , art , rte , ten. Ist es nun wirklich das, was man beim Kasiski-Test wirklich macht? Oder "zählt" nur das längste eines Wortes - hier also nur garten? Wenn ja, wie filtere ich zuverlässig alle anderen Treffer raus? du interessierst dich ja nicht für den Inhalt der Wiederholungen sondern für die Abstände; kürzere Doppelungen würde ich also nur registrieren, wenn die Abstände unterschiedlich sind.
Leichter gesagt als getan...
Wenn ich dich nun richtig verstehe, sagst du, dass nur das längste 'zählt'.
Heißt also: WENN längeresWort.indexOf(kürzeresWort) != -1 //Das kürzere Wort ist vollständig im längeren enthalten
UND abstandZwischenLängeresWortUndWiederholung == abstandZwischenKürzeresWortUndWiederholung //Wenn beide Abstände identisch sind
DANN kürzeresWort fliegt aus dem Arrayrichtig?
(Kryptogramm: hasehase
Script findet: hase , Indexe: 0 & 4 , Abstand hase - hase: 4
Script findet: has , Indexe: 0 & 4 , Abstand has - has: 4
Script findet: ase , Indexe: 1 & 5 , Abstand ase - ase: 4)Nun wollte ich auch eine solche Prozent-Bewertung anbieten. Allerding kann ich nicht nachvollziehen, nach welchem Prinzip ich die Anzahl der gefundenen Teiler in eine Prozentangabe überführen könnte. Ich sehe auch nicht, was Prozente hier aussagen sollen; ich würde eher ein gewichtetes Scoringverfahren verwenden, um die Teiler nach Güte zu sortieren.
Schon wieder muss ich sagen, dass du mit Worten sparst. Momentan erreiche ich mit meinem Script folgende Verteilung der ganzzahligen Teiler für den zuvor erwähnten Text (links: meine Treffer , rechts: die zuvor gezeigt Prozent-Wertung):
|2 lett. 824 | 2 lett. 56.9% |3 lett. 798 | 3 lett. 54.4% |4 lett. 517 | 4 lett. 37.9% |5 lett. 106 | 5 lett. 13.4% |6 lett. 786 | 6 lett. 71.4% |7 lett. 129 | 7 lett. 12.2% |8 lett. 249 | 8 lett. 31.2% |9 lett. 371 | 9 lett. 27.7% |10 lett. 104 |10 lett. 23.3% |11 lett. 56 |11 lett. 7.1% |12 lett. 500 |12 lett. 54.8% |13 lett. 70 |13 lett. 8.8% |14 lett. 123 |14 lett. 22.7% |15 lett. 104 |15 lett. 22.6% |16 lett. 138 |16 lett. 27.8% |17 lett. 32 |17 lett. 6.4% |18 lett. 365 |18 lett. 47.3% |19 lett. 58 |19 lett. 5.7%
Gut, ich als Mensch könnte ahnen, dass da was bei 6 im Busch ist, aber wie bringe ich einem Script sowas bei? Wie kann sagen: _dies_ kommt auf Rang 1, _das_ kommt auf Rang 2 etc. oder ach schau doch mal dahin, das sieht auffällig aus?
Reinhard
-
Tach,
Wenn ich dich nun richtig verstehe, sagst du, dass nur das längste 'zählt'.
Heißt also: WENN längeresWort.indexOf(kürzeresWort) != -1 //Das kürzere Wort ist vollständig im längeren enthalten
UND abstandZwischenLängeresWortUndWiederholung == abstandZwischenKürzeresWortUndWiederholung //Wenn beide Abstände identisch sind
DANN kürzeresWort fliegt aus dem Arrayrichtig?
sofern es an der selben Stelle ist. Wenn ich als Beispieltext haaseaasenhaase habe, möchte ich die Paare haase zu haase betrachten, aber nicht unbedingt das darin enthaltene aase, aber der Abstand vom mittleren aase zu den äußeren ist relevant.
Schon wieder muss ich sagen, dass du mit Worten sparst.
Ich bin halt nicht Morn.
Gut, ich als Mensch könnte ahnen, dass da was bei 6 im Busch ist, aber wie bringe ich einem Script sowas bei? Wie kann sagen: _dies_ kommt auf Rang 1, _das_ kommt auf Rang 2 etc. oder ach schau doch mal dahin, das sieht auffällig aus?
Mit gewichtetem Scoring meinte ich ein Verfahren, bei dem du z.B. betrachtest wie lang ist der gefundene String, eine vier Zeichen lange übereinstimmung ist wahrscheinlich relevanter als eine dreibuchstabige; dann kannst du dir ansehen, welche der gefundenen Abstände sich aus vorher gefundenen Faktoren zusammensetzen, zwei gleiche Treffer im Abstand 3 hintereinander sind auch ein Treffer im Abstand 6. Alternativ kannst du deinen Algorithmus so arbeiten lassen, wie du es vermutlich getan hast: die 6 und die zwölf stechen heraus, weil die Differenz der Treffer von 5 und 6 sowie 6 und 7 bzw. 11 und 12 sowie 12 und 13 so groß sind; alle diese Zahlen haben außerdem jeweils keine gemeinsamen Primfaktoren, so dass es eher nicht Treffer wegen dieser Primfaktoren sind.
mfg
Woodfighter-
Zum Kuckuck nochmal...
Egal was ich versuche, da funktioniert einfach nix... absolut gar nix. Ganzzahl-Teiler der Abstände addieren, Primzahlfaktoren addieren, vereinfachte Primzahlfaktoren addieren, eine andere Methode um sich wiederholende Buchstabenfolgen zu finden . . .
Wenn jemand eine "Schritt für Schritt" Anleitung parat hat.. so langsam könnte ich sie gebrauchen. Auch bin ich für eine Seite dankbar, deren Javascript Kasiski-Test nicht durch AJAX oder ein Flash Plugin verschleiert wird! - was bisher überall der Fall war, wo ich mich umgesehen habe.
Ich kann ja bei Bedarf später mal meinen derzeitigen Versuch mit zusätzlichen Kommentaren hierrein stellen - jetzt brauche ich erstmal eine Mütze Schlaf.Reinhard
-
Tach,
Auch bin ich für eine Seite dankbar, deren Javascript Kasiski-Test nicht durch AJAX oder ein Flash Plugin verschleiert wird! - was bisher überall der Fall war, wo ich mich umgesehen habe.
http://cs.colgate.edu/~chris/FSemWeb/tools/kasiski.html ist in Javascript, implementiert aber nur den Test und keine Auswertung.
Ich kann ja bei Bedarf später mal meinen derzeitigen Versuch mit zusätzlichen Kommentaren hierrein stellen - jetzt brauche ich erstmal eine Mütze Schlaf.
ah, not enough caffein error
mfg
Woodfighter-
Guten Abend,
Auch bin ich für eine Seite dankbar, deren Javascript Kasiski-Test nicht durch AJAX oder ein Flash Plugin verschleiert wird! - was bisher überall der Fall war, wo ich mich umgesehen habe.
http://cs.colgate.edu/~chris/FSemWeb/tools/kasiski.html ist in Javascript, implementiert aber nur den Test und keine Auswertung.Dort war ich natürlich schon. Den Algorithmus da mit der for-Schleife womit nach Wiederholungen gesucht wird verstehe ich zwar nicht wirklich, somit kann ich nicht beurteilen, ob er "besser" ist wie meiner...
Ich habe hier einen sehr interessanten Artikel gefunden. Bin gerade bei der Hälfte.. Versuchhe das dann später mal zu scripten. Ich schreibe dann morgen mal wie's ausgegangen ist.
Reinhard
-
Tach,
Ich habe hier einen sehr interessanten Artikel gefunden. Bin gerade bei der Hälfte.. Versuchhe das dann später mal zu scripten. Ich schreibe dann morgen mal wie's ausgegangen ist.
ah über den IC kommt man natürlich an Dinge wie eine Prozentabschätzung ran, aber das geht über Kasiski natürlich schon ziemlich hinaus.
mfg
Woodfighter-
Guten Abend,
Ich habe hier einen sehr interessanten Artikel gefunden. ah über den IC kommt man natürlich an Dinge wie eine Prozentabschätzung ran, aber das geht über Kasiski natürlich schon ziemlich hinaus.
Ja, ich habe nun die Teiler aller gefundenen Abstände zusammen gezählt und anschließend mit dem Friedmann-Test einen hinterher gesetzt. Jetzt ist die Schlüssellänge i.d.R. eindeutig.
Reinhard
-
-
-
-
-
-
-