4. [Vigenere]Buchstaben-Kombos in Texten erkennen/zählen

[Vigenere]Buchstaben-Kombos in Texten erkennen/zählen

  • L

    Hi,
    ich wollte mir ein kleines Programm in Ansi C unter Linux schreiben, welches mir mit Vigenere verschlüsselte Texte analysiert, d.h. daß es eine Auflistung aller Buchstaben-Kombinationen ausgibt, von denen man auf die Schlüssellänge schließen kann. Beispiel: die Kombi "awejdk" kommt 5 mal vor usw ...
    Ich habe Schwierigkeiten einen Algo dafür zu finden, bzw. ihn zu implementieren.

    Kann mir da jemand Ratschläge/Links/Quellcodes geben?
    Vielen Dank!

    0
  • C

    wie würdest du es denn mit stift und papier machen?
    nimm den ersten buchstaben, such danach, merke dir/zähle die vorkommen.
    nimm die ersten zwei buchstaben, such/zähle.
    ...
    nimm den zweiten und suche
    nimm den zweiten und dritten ...

    bei vigenere kommts doch auch auf die position an, also dass es z.b. index 0, 15, 20, 55 sein müsste für schlüssellänge 5. kannst ja den text von 1..n umbrechen und was probieren.

    hab ein vigenere leider noch nicht vorgesetzt bekommen. kannst ja nen beispieltext posten zum rumprobieren.

    0
  • L
     

    JrlhAobd psg wpn Cjvgestm, zaa drkzea Zplsw Zir cyyclvgesmifuoe Iwyfnzyea suwrfkea mud 
nfhllkpeewu köafln. Fg rönawu Svw uehw Koxmteall eekaeydln hfk brkaeuwudr Vvkhelngw 
ömfawu uav devllr owhrowptrf. 
Lia Vvkhelng chna eptgwss iwyspzpeqwuee Nlrfuolüfkllhfnsiwyfnzyea nlr- hfk ealzcudüzsrda 
wrjkea. Wz sgwoea kvwbzs kyszsvkjhr (rbm Owpscall qsz Cnwzae-Nlrfuolüfkllhfnsiwyfnzyea) 
sss nmjh zgkeefl Vrjzcudüzsrdbntkceexhhewu (brazpvwssjwpsr vhs EKH- uav kaf VLS-Iwyfnzyea 
kvwvw hus wslvhaifuoea Cbriwu bnkpeewudr Nlrssorrf) gue Nlrsüybnt. Wpnr Ütlrfajhg ütlr ndse 
Iwyspzsüsfwsuayzvrjmaujln vf JrlhAobd miavlt zsu ahx kee Zplswzevll zhe Teaü 
Nlr-/Rfaspzsüsfwsn.

Nmßlrqwt knfu CeqwTbgs vbf liawt Dbcbmrfa Hnkowrjae owyepzuea (kpeuw Teaü Zhsuolrgw). 
Mür qal kyszsvkjhrf Ceekjhyükzeymugfnlrssorrf ztrzln nmaozsaifuoe Nfhllkln mmy Vrjmüghfn, 
dvw Zir au dvw Satw ceekltmwu, mvl Reafanvk kef nlrfuolüfkllgwu Dbcbmrfas hfk eiwuthwsl 
jwptrjlr Vfmoeehtvguea (muvrjzcudüzsrdaef Vvkhelng gkee Kwrnuoe qwz Dbcbmrfas) qwu

    Schlüssel: hans

    0
  • C

    bei der analyse wärs besser, alles rauszunehmen, was nicht verschlüsselt ist. so muss man nicht mitzählen, an welcher schlüsselposition man grad sein müsste.

    ich bastel mal ein script nach dem wiki eintrag:
    http://en.wikipedia.org/wiki/Kasiski_examination

    0
  • L

    Genau, es geht um

    A cryptanalyst looks for repeated groups of letters and counts the number of letters between the beginning of each repeated group. For instance if the ciphertext was FGXTHJAQWNFGXQ, the distance between FGX's is 10. The analyst repeats this for as many repeated groups as appear in the text.

    Das umzusetzen in C schaffe ich nicht ausreichend ... 🙄

    0
  • C

    mach dir da mal keine vorwürfe. ich bastel es grad in python...

    der algorithmus schafft es ohne menschliches zutun eh nicht.
    also die indices von substrings gehen einfach rauszufinden.
    sieht dann irgendwie so aus:
    "foobarbaz" ist der string
    das könnte rauskommen:
    {"foo": [0], "oo": [1], "ba": [3, 6], ...}
    jetz nimmt man sich die indices der längsten substrings (hier wären es die von "ba").
    wenn ich nicht [3,6] hätte sondern [4,7] dann wäre es immernoch OK. aber man kann da keinen ggT von machen. man muss das kleinste element finden und von allen abziehen. so bekommt man die relativen abstände. also ggt([0,3]) = 3
    der könnte aber immernoch ein vielfaches der eigentlichen schlüssellänge sein... guck einfach in mein script, dann siehst du es.

    so, hier das python script für die kasiskianalyse und auch gleich noch ne "coincidence analysis" (guck bei wikipedia)
    http://cracki.incast-security.de/downloads/vigenere.py

    du musst dann nur noch den cipher zerhacken und über jeden teil ne häufigkeitsanalyse laufen lassen. und weil die selten perfekt sitzt, bastel dir am besten eine oberfläche (in der konsole natürlich 😋 ), mit der du für jeden teilcipher die häufigkeiten anders mappen kannst.

    0
  • K

    ich hab ka wovon ihr sprecht, es hört sich aber extrem gut an 🙂

    lasst euch nicht stören von mir 🙂

    0
  • C

    erstmal brauchst du dynamische listen.
    mit nem struct type und ein paar funktionen, die damit arbeiten, geht das gut in ansi c.
    unter den funktionen sollte auch eine suchfunktion sein.
    hashlisten wären natürlich noch besser, aber das wäre dann schon wieder sehr heftig.

    jedenfalls müsstest du einen großen loop machen, der von i=a bis b zeichen länge durchläuft. (macht erst bei a >= 3 sinn)
    in dem loop dann müsstest du von 0 bis strlen(quellstring)-i durchläuft und einen substring der länge i rausnimmt.
    dann muss der im quellstring gesucht und alle vorkommen samt index in einer liste registriert werden.
    den suchalgorithmus würde ich auf alle fälle separat entwickeln und testen.
    jetz erklärt sich auch, wieso hashlisten gut wären. du kannst bei hashlisten die elemente mit einem string oder sonstigen hashbaren daten ansprechen.

    wenn du alle vorkommen hast, nimm dir von den längsten die mit den meisten vorkommen.
    jetz hast du eine liste von offsets. finde das kleinste und ziehe dieses von allen ab.
    jetz hast du relative offsets zum ersten fund. da jagst du jetzt nen ggt drüber (größter gemeinsamer teiler/faktor).

    wenn du glück hast, ist es die schlüssellänge, wenn du pech hast, kommt 1 raus und du musst mit dem nächsten vorkommen weitermachen.

    0
  • L

    c.rackwitz:

    Erstmal vielen vielen Dank für deine Mühe! 🙂
    Ich werde mich jetzt erst einmal durch die Links und deine Arbeit durchwühlen, ich melde mich dann nochmal.

    Gruß

    0
Anmelden zum Antworten