Hashberechnung der Topologie eines Wortes - wie?

[himitsu]

Wie Hagen schon erwähnte: Bist du dir wenigstens sicher, daß jedes Zeichen genau einem bestimmten Buchstaben entspricht? (ich hoffe ja mal, deine Freunde haben es dir nicht zu schwer gemacht)

PS: Im Notfall gibt es ja noch sowas, das nennt sich Bruteforce. :mrgreen:
Alle möglichen Kombinationen durchprobieren und jedesmal die entstandenen Wörter mit deinem Wörterbuch vergleichen ... je mehr Wörter im Wörterbuch gefunden werden, desto wahrscheinlicher ist es, daß es sich um die Lösung handelt.

@Hagen: Es ist ja nicht direkt ein Algo ... es soll nur eine Möglichkeit darstellen, um einen "kleinen" Wert zu erhalten, welcher die Positionsabfrage aus Post #1 ermöglichst.

[negaH]

Achso eines noch: falls deine "Freunde" ein komplett zufälliges Passwort benutzt haben das auch noch exakt so lang wie deine Nachricht ist dann hast du die klassische OTP Verschlüsselung, One Time Pad. Das wirst du dann nie knacken können, bzw. alle deine für dich richtigen Lösungen sind gleichwertig korrekte mögliche Lösungen des Problemes. Du wirst also alle möglichen deutschen Sätze die so lange wie deine Nachricht sind erzeugen können und hast keinerlei Chance zu erkennen welche die richtige Nachricht nun ist.

Gruß Hagen

[negaH]

Zitat:

PS: Im Notfall gibt es ja noch sowas, das nennt sich Bruteforce.

Tja der Erfolg hängt dann aber auch von der Länge der Nachricht ab. Schon bei wenigen Worten steigt die Komplexität dieser Bruteforcesuche ins Unermeßliche an.

Gruß Hagen

[helgew]

Hagen, meine bisherige Überlegung war es, zu den möglichen Kombinationen eine Liste aller Möglichkeiten zu erzeugen ( später kommen noch vordefinierte Zeichen hinzu, die das ganze weiter einschränken) und zu diesen im Wörterbuch zu suchen. Ein entscheidender Schritt ist dabei in dem Falle, dass wenn man eine Symbolvariante herausgegriffen hat, zu dieser der Struktur nach passende Wörter finden kann und diese im Kontext der restlichen Wörter auf Übereinstimmung des Alphabets testen kann.

Vielleicht ist diese Vorgehensweise auch ineffizient, da man mit der Festlegung des ersten Wortes das Unteralphabet schon in die Suchmasken für weitere Worte einbeziehen könnte, aber irgendwo muss man ja mal anfangen ^^

[helgew]

Zitat:

Zitat von negaH

Zitat:

PS: Im Notfall gibt es ja noch sowas, das nennt sich Bruteforce.

Tja der Erfolg hängt dann aber auch von der Länge der Nachricht ab. Schon bei wenigen Worten steigt die Komplexität dieser Bruteforcesuche ins Unermeßliche an.

Gruß Hagen

bisher schätze ich den Aufwand als in der Größenordnung 10^9..10^11 Vergleiche liegend. Das ist immerhin schon berechenbar, wobei ich auch keine Lust habe, einen Tag vor schlechtem Code zu sitzen, bis er mal fertiggerechnet hat.


übrigens liegen die Buchstaben in ihrer Häufigkeit nur um 1-2% auseinander, wenn nicht noch weniger, dazu variieren die Verteilungen von Schriftsprache, Wörterbüchern, Onlineartikeln und Forenbeiträgen, sodass bei etwa 50 Symbolen, die ich habe, keine hinreichende Signifikanz erreicht wird. Eine Häufigkeitsanalys scheidet demnach aus. Ich habe als Hinweis bisher jedoch, dass Buchstaben eindeutig zugeordnet sind und umgekehrt. Gehen wir also davon aus, die Symbole seien bis auf Permutationen und Variationen hin bekannt, also etwa

ab(cde,edc,df)ghi

für cde, edc : verschiedene Interpretationen gestapelter Symbole
df : ein Teil der Symbole wird als anderes, neues Symbol interpretiert.

daraus würde ich

abcdeghi
abedcghi
abdfghi

erzeugen und entsprechend länger suchen, da ich dreimal mehr Kombinationen erhalte, unsere Methoden unterscheiden sich nun daran, ob ich unter einer generalisierten Suchmaske mehr Wörter finde oder ob ich drei Untergruppen finde und diese dann zusammenfüge.
Ein ungelöstes Problem ist jedoch noch das Wiederkehren von Variationen, denn das Interpretieren der Symbole ist ja nicht nur lokal, sondern entsprechend im nächsten Wort dann ebenfalls "df" oder "edc". Es kann aber auch wieder sein, dass eine Grammatik festlegt, wann die Symbolfolge (...) als df oder als edc intepretiert wird. Das muss man dann austesten...

[negaH]

Zitat:

@Hagen: Es ist ja nicht direkt ein Algo ... es soll nur eine Möglichkeit darstellen, um einen "kleinen" Wert zu erhalten, welcher die Positionsabfrage aus Post #1 ermöglichst.

Schon klar das ist ;) Aber wir wollen doch wissen was im Geburtstagsgruß drinnensteht und dafür sollte man analytisch korrekt vorgehen da ansonsten der TE unnötig Zeit mit dem falschen Algo. verschwendet. Oder: bei seinem konkreten Problem können wir ihm nicht helfen da wir nicht die Nachricht vorliegen haben, ergo können wir ihm nur Tipps geben wir man sowas in der Kryptoanalsyse richtig anpackt. Und da zählt als erstes die Häufigkeitsanalyse. Und erst wenn man diese vorliegen hat kann man entscheiden wie man weitermachen muß.

Gruß Hagen

[himitsu]

Zitat:

Zitat von negaH

Schon bei wenigen Worten steigt die Komplexität dieser Bruteforcesuche ins Unermeßliche an.

Ich hab nicht behaubtet, daß es schnell geht. :angel2:

Haben deine Freunde dir also nur den Zettel hingehalten "so mach mal" und sonst keinerlei Tipp gegeben?
(ohne zu wissen/ahnen, wie das Ganze eventuell verrechnet wurde, kann es ja nicht grad leicht lösbar sein, falls es das dann überhaupt jemals ist)

[negaH]

Zitat:

Zitat von helgew

Hagen, meine bisherige Überlegung war es, zu den möglichen Kombinationen eine Liste aller Möglichkeiten zu erzeugen ( später kommen noch vordefinierte Zeichen hinzu, die das ganze weiter einschränken) und zu diesen im Wörterbuch zu suchen. Ein entscheidender Schritt ist dabei in dem Falle, dass wenn man eine Symbolvariante herausgegriffen hat, zu dieser der Struktur nach passende Wörter finden kann und diese im Kontext der restlichen Wörter auf Übereinstimmung des Alphabets testen kann.

Vielleicht ist diese Vorgehensweise auch ineffizient, da man mit der Festlegung des ersten Wortes das Unteralphabet schon in die Suchmasken für weitere Worte einbeziehen könnte, aber irgendwo muss man ja mal anfangen ^^

Nein nein, nicht ineffizient weswegen ich ja mein DAWG oben ansprach das dieses Problem effizient lösen könnte. Das problem was ich sehe ist das die Entscheidung es so zu versuchen einfach verfrüht ist.

Mach mal eine, wie oben angesprochene, Häufigkeitsanalsyse der Symbole in deiner Nachricht und poste sie hier, also die häufigsten Symbole sind ausreichend. Dann können wir weiter sehen.

[edit]
Nochwas: wenn du denkst das du mit einem Algo. das Problem sofort lösen kannst dann ist das falsch. Normalerweise wendet man auf eine solche Nachricht sukzessive verschiedene Algo. an und entscheidet an Hand deren Resultate welcher Algo. also nächstes ausprobiert wird.
[/edit]

Gruß Hagen

[helgew]

Zitat:

Zitat von himitsu

Haben deine Freunde dir also nur den Zettel hingehalten "so mach mal" und sonst keinerlei Tipp gegeben?

So ein Rätsel gab es schonmal und bei mir hat man es wohl etwas zu gut gemeint, nach dem Motto: der schafft das eh... (wohlgemerkt ohne dass derjenige, der sich das ausgedacht hat die Machbarkeit geprüft hat..)

[negaH]

Zitat:

(wohlgemerkt ohne dass derjenige, der sich das ausgedacht hat die Machbarkeit geprüft hat..)

Na cool, dh. es könnte auch durchaus sein das der Text so verschlüsselt wurde das es garkeine Entschlüssung dafür gibt ?

Gruß Hagen