Schlüssellänge/Blocklänge für Trannspositionschiffre (Single Column) erraten

[simlei]

Hallo,
ich bin neu hier, und bin auf dieses Board durch sehr gute Beschreibungen klassischer Algorithmen durch einige Member hier gekommen. Selbst entwickle ich gerade in meiner Freizeit für das JCrypTool-Projekt Plugins.

Gerade versuche ich, eine halbautomatische Analyse der Single Column Transposition zu programmieren.
kennt jemand von euch gute Methoden, um die Schlüssel-/Blocklänge einer Chiffre, die durch einfache einzeilige Transposition mit einem recht kurzen Schlüssel verschlüsselt wurde, systematisch zu erraten?

Selbst fällt mir nur ein, dass Teiler der Gesamtlänge des Textes in Frage kommen. Doch oft stehen ja nur Fragmente zur Verfügung, und außerdem gibt es Implementierungen, die bei Texten hinten nicht auffüllen.
Bin für jede Anregung dankbar.

MfG,
Simon Leischnig

[Smartie]

Hallo,
darüber habe ich mir auch schon öfters Gedanken gemacht. Ich bin allerdings nur auf Ideen, die stark von der Sprache abhängen...zb. indem man (für eine Sprache) die Column Transposition umsortiert und dann Trigramme oder höhere Kombinationen testet.
Problem hierbei: Man braucht gute Daten für jede Sprache bzgl. von Bigrammen oder Trigrammen oder sonstigem. Ausserdem führt das bei längeren Transpositionsspalten ganz schnell an die Fakultätsgrenze.
Alternativ könnte man in jeder Sprache auch auf die Verteilung von Satzzeichen schauen und den Text danach neu ausrichten. (Für sowas solltest du mal dann Computerlinguisten fragen, bzgl. Textverteilung oder sonstigen strukturellen Eigenschaften generell)
Das ist eigentlich eine Aufgabe für Branch'n'Bound, das muss man an Bäumen entlang ausprobieren und die Wahrscheinlichkeiten aufgewichten. Das kann aber aufwendig werden. Man probiert halt quasi dabei einen Teil klug aus und fährt dann im Kindesknoten mit den nächsten Teildaten ab. Dabei könnte man ja Fixpunkte in der Transposition ausnutzen, von denen man ausgeht. Aber das ist dann relativ schnell durch den Speicher beschränkt.. Oder der Rechner wird langsam..

Du könntest das auch insofern verbinden, in dem du (zb in deutschen Texten) nach tranpositionen suchst, die Wörter wie "die" ergeben, und dann weiterprobieren im Baum.

Als ich mir CrypTool angeschaut hab, kam's mir auch so ein bisschen vor, als würden die intern auch so arbeiten bei den halbautomatischen Algorithmen.

Man kann auch bei einfacheren Texttranspositionen davon (ascii o.ae.) ausgehen, dass der grösste Teils des Textes vorhanden ist, also dass man die nächsten ganzen Zahlen mit einigen Teilern nimmt und mit den Teilern rumtut und testet und den Benutzer das anschauen lässt

Es gibt meines Wissens keine generische Möglichkeit, Transpositionen rauszufiltern, da sie ja die Struktur zerstören eben. Vor allem weil sie gut gewählt sind. Man kann natürlich den Tradeoff machen und sagen, ich unterstütze das standardmässig nur bis Blocklänge x (kleiner 5 zb) sonst wirds langsam. Bei vielen Hobbychiffrieren hab ich sowieso gesehen, dass es oft nicht grösser gewählt wird, weil diese eben angst vor dem padding haben..

Was u.u. auch noch geht: Wenn du von einem bestimmten Padding weisst (also format), könntest du versuchen daran die originale Position wiederherzustellen.

Ich finde das Thema sehr interessant und hoffe du hälst uns auf dem Laufendem. Ich würde mich da auch gerne mit dir unterhalten, da mich die Cryptool-Entwicklung schon immer sehr interessiert hat.. aber ich dachte das jcryptool sei total eingeschlafen?

sorry wenn's etwas verpeilt ist... es ist schon spät =)

[simlei]

Hm.. Ich bin inzwischen nicht ganz sicher, ob die Sache einfach wird..
Ich rede also immernoch von ganz einfacher Transposition von Klartextzeichen in unbekannten Blockweiten - weiter will ich erst mal noch nicht gehen (auch im Programm).

Ich würde auch auf sprachspezifische Bi-/Trigramme setzen.. Das allein wird schon bei langen Texten ein großer Rechenaufwand. Der Tradeoff, den du erwähnst, wäre auf jeden Fall da mit einzubeziehen, und man kann den User ja immernoch entscheiden lassen, wie weit er geht.
Die 5-10 wahrscheinlichsten Treffersätze kann man ja dann sortiert dem User zeigen zur Entscheidung/Weiterverarbeitung..

Auf jeden Fall bringen kombinierte Methoden weiter. Wird ein festes Padding - im besten Fall xxxxx.. verwendet, hat man ja mit Glück oft schon gewonnen. Man sollte das Ende des Textes erst auf festes Padding untersuchen, und dann nochmal dem User vorlegen.
Außerdem Teileingaben von Schlüsseln akzeptieren, es soll ja keine vollautomatische Analyse werden

Mehr Ideen herzlich willkommen, und wenn ich was fortgeschrittenes habe melde ich mich auch nochmal.


Was das JCrypTool angeht: Ja, sehr viele Entwickler sind nicht mehr an dem Projekt dran (aber waren es jemals viele? Jedenfalls sind die 3-4 Leute die das Projekt dauerhaft betreuen, aktiv) - und ich bastle halt mehr oder weniger regelmäßig im Pluginbereich an klassischen Algorithmen und an was eben so anfällt herum.
Trotzdem, ausgestorben ist falsch, da immer (mal) wieder ein paar neue Beiträge kommen von Studentenarbeiten o.ä., und das Kernteam auch recht aktiv an einem stabilen Release in Richtung April arbeitet (so Werbeblock Ende).

[Smartie]

Ja, einfach wird es garantiert nicht. Je grösser die Blocklänge, desto interaktiver muss es halt werden... du könntest auch Permutationssubgruppen versuchen zu finden, dann würden die testzyklen kleiner... wenn du allerdings weisst, das ein wort vorkommt, könntest du das wort ja permutieren und dann schauen, ob ein teilwort (mittels longest prefix matching) auf irgendeinen Teiltext passt.
Das kann dir aber auch schnell explodieren, wenn du nicht aufpasst und tut nur bei längeren Worten.. Bei branch and bound kann dir ja im übrigen nicht nur helfen, dass manche sehr wahrscheinlich sind, sondern einfach auf gut glück sehr unwahrscheinlich dann einfach abschneiden. "eee" oder "ee ee" kommt nicht vor

Ich würde vorschlagen, du versuchst das Problem in mehr Teilprobleme zu verwandeln und dann für die Teilprobleme bestimmte Algorithmen zu verwenden. zb. permuationslängen 2-4, 5-6, 7-8 und rest... Denn z.b. kannst du den lpm-ansatz zwar bei 5-8 anwenden abe rnicht bei 2-4. den automatischen test kannst du nur bei 2-4 anwenden und subgruppen gibt es bei 5-6 einheiten auch nicht viele..

Im übrigen darfst du für cryptool, solange es sich um probleme der entwicklung dabei handelt ruhig schleichwerbung machen, wenn wir dafür über algorithmik diskutieren

[simlei]

Hey,

Ich würde vorschlagen, du versuchst das Problem in mehr Teilprobleme zu verwandeln und dann für die Teilprobleme bestimmte Algorithmen zu verwenden. zb. permuationslängen 2-4, 5-6, 7-8 und rest... Denn z.b. kannst du den lpm-ansatz zwar bei 5-8 anwenden abe rnicht bei 2-4. den automatischen test kannst du nur bei 2-4 anwenden und subgruppen gibt es bei 5-6 einheiten auch nicht viele..

Mh, wäre schön, wenn du einen Tick genauer andeutest, was du meinst - ich dachte erst ich habe dich mit dem LPM richtig verstanden, aber dann hat mich stutzig gemacht, warum das bei Blocklänge 2-4 nicht funktioniert. Kannst du nochmal erklären, was du mit deinem LPM-Ansatz meinst? Und nochmal deine Zerlegung in die Permutationssubgruppen genauer darlegen?

Danke

[Smartie]

Mit Permutationssubgruppen meine ich folgendes:

( 1 2 3 4 5 6 7 8 )
( 2 3 4 1 7 6 8 5 )
[----------][----------]

Hier siehst du, dass die Transposition der Zeichen eigentlich in zwei Blöcken statt findet, auch wenn der gesamte Block von Position 1 bis 8 geht. Wenn man solche von einander unabhängige Subgruppen identifizieren kann (also eine Gruppe schon fertig dechiffriert hat) kann man den oder die anderen Teilblöcke noch schneller identifizieren, da die Anzahl der Vermischungen natürlich rapide sinkt.
Bei kurzen Transpositionsblöcken macht das nicht so viel Sinn, siehe (1234) kann in 2 unabhängigen gruppen entweder (2134) sein, oder ein fixpunkt (1342) mit einer 3er permutation. (was natürlich auch der Fall sein kann). Aber je grösser ein Transpositionsblock ist, desto grösser wird natürlich die Wahrscheinlichkeit, dass ein ungeschickter Designer das aus Versehen in Subgruppen unterteilt.

Mit LPM aka Longest Prefix Matching meinte ich, dass wenn du ein Wort hast, von dem du weisst, dass es im Chiffretext vorkommt, du (Test)Permutationen deines Chiffretextes oder des bekannten Wortes vornehmen könntest und versuchen einen Teil davon im Chiffretext wiederzufinden.
Das klappt natürlich nur unter bestimmten Umständen.
Ich glaube nicht, dass LPM bei 2-4-er Längen funktioniert, da einfach zu oft ein Bigramm auftauchen kann, dass auf einen Teil des permutierten bekannten Wortes passt, also bei kuerzeren Folgen die Anzahl der false positives meiner Meinung nach sehr stark ansteigt.

Du brauchst beim LPM-Ansatz halt jeweils je nachdem was du permutierst (ob jetzt das Wort oder (Teile des/) den Text(es) entweder richtige Prefix-suche, oder eine lossy-variante, die in einem Teil auch buchstaben "übersieht" und dann trotzdem das prefix matchen lässt. Das müsste man aber dann in der Praxis noch genauer anschauen, wie man das baut. ^^

[simlei]

Ah, alles klar
Danke für die Erläuterung.. Ich mache mich jetzt auch langsam heran an die Implementierung fürs Grundgerüst.. Im Endeffekt plane ich das so dass der benutzer einen Wizard kriegt, und jede Wizardseite mit Tests und Nutzereingaben führt zur Umgewichtung von Blocklänge und mögl. Schlüssel positionen.

Wenn ich was neues hab melde ich mich, schaue aber auch hier immer wieder vorbei, falls ne neue Idee kommt.

MfG,
Simon

[Smartie]

Noch eine Idee bezüglich des Wizards:
Wäre es möglich, 1-2 zusätzlich Fenster dann zu haben? Darin könnte man dann sehen, welche Aktionen durchgeführt wurden, und evtl. sogar wie es die Texte schritt für schritt verändert? (Und falls möglich, sogar die Kommutation der Aktionen erlaubt? sagen wir wir haben Text x1 auf dem eine Aktion A ausgeführt wurde, was zu Text x2 führt. Dann wird Aktion B ausgeführt und herauskommt Text x3.

Und wenn man das anschaut, dass man z.b. x1 nehmen kann und dann genau die Aktionen B und A vertauscht und dann x3* herausbekommt?

[grip]

Vielleicht ist das ja auch eine interessante Möglichkeit?

--> Breaking Transposition Ciphers with Ants

Das es offenbar gelingt auch schwierige Transpositionen zu knacken, sieht man bei der

--> CRYPTO BOX CHALLENGE

von Dirk Rijmenants.

[simlei]

Danke für die Links. Ich werde mir besonders den mit der ACO mal in der Bahn durchlesen.

Eine weitere Sache dir mir gerade eingefallen ist -
Sollten Worttrenner (Leerzeichen) nicht vor der Verschlüsselung gelöscht worden sein, und man findet zwei in derselben Spalte (zB beim Druchprobieren einiger Spaltenbreiten)
so kann sich sicher sein, dass hier ein Wort komplett enthalten ist. Wahrscheinlich ein kurzes Wort.
Außerdem müssen die Leerzeichen >= 3 Zeichen Abstand haben (entschlüsselt).

Weiß jemand noch etwas, was man aus Wort- und Satztrennern machen könnte?

[grip]

Wenn Worttrenner verwendet werden, ist das folgende Tony Sale Video ja vielleicht auch von Interesse.

--> Video language statistics the Delta and how the delta was used

FG
GRip

[grip]

Hier gibt es dazu ein Thema vom Crypto Board -> Transposition Cipher Cracker (c++)

Speziell das folgende Posting passt zu ganz gut zu unserem Thema -> http://s13.zetaboards.com/Crypto/sin...01847&t=123866