Laden...

String nach sich wiederholenden Zeichenfolgen dursuchen [ Vigenére-Chiffre knacken ]

Letzter Beitrag vor 16 Jahren 12 Posts 2.295 Views
String nach sich wiederholenden Zeichenfolgen dursuchen [ Vigenére-Chiffre knacken ]

Hallo!

Momentan arbeite ich an einem Programm um die Vigenére Verschlüsselung zu knacken.
Um die Schlüssellänge herauszubekommen, muss man einen Text nach sich wiederholenden Zeichenfolgen durchsuchen ( 3 oder mehr zeichen ) und dann den Abstand zwischen den 1. Buchstaben zusammenrechnen. Der gemeinsame Teiler aller Abstände ist dann die Schlüssellänge.
Nur wie mache ich das mit den sich wiederholenden Zeichenfolgen?
Hab überhaupt keine Idee 🙁
Mit papier hab ich den Schlüssel schon geknackt, jetzt will ich das aber auch mit meinem programm schaffen xD

Wie würdet ihr vorgehen?

mfg
Timmey

Vllt genau so wie du es auf dem Papier gelöst hast 😉

Meinst du, es ist möglich das ganze mal hier als Beispiel zu posten?

Dr. J. Z.

Ja ich meine wie man das programmtechnisch lösen könnte ^^

also der Text ist :

Boeizi jfibxp moeig kkf Wxxvz mswcerusb Kffnse Aysis psismejhoh kvo vrdsh gomi ft
ditvxsccqc zbxsmodmfb Rmj dbiuwmxzcx tfdeprfvc bbyae oc Qfcbij Zka jhkxvg dlrh
dvrbcmjhyv usxwzhi se wxxvubeksn gzfmyzhc hfilpvg kffid imsbc kky cvobw Kcnep
Wxxvz msehsrlsc xf zoeu hri zbnyjhbc ufszzbq Qfcbij Zka kc srtfoejs pyeqdmfbkpzhi eer
ziityvdoxgv oxh usmvvoci tccxj pbmeusrx ubsnhr xf wxhlgdvzsc affvhnwni

Wiederholungen :
Qfcbij Zka , 2x, Abstand : 132 , Teiler : 2,3,4,6,11,12,22,33,44,66,132
xf , 2x, Abstand : 100 , Teiler : 2,4,5,10,20,25,50,100
ox , 2x, Abstand : 4 , Teiler : 2,4

D.h. mögliche Schlüssellängen sind 2 oder 4!

hoffe du hast das prinzip verstanden 🙂

außerdem gibt es da noch

  1. Wxxvz
  2. _kk (wenn das leerzeichen ja mitgerechnet werden darf..)
  3. _zb
  4. und noch ein paar andere.. die frage ist auch noch ob case sensitive?

nee ist nicht case sensitive.
leerzeichen werden bei der verschlüsselung auch nicht beachtet!

also wie würde ich nach solchen sich wiederholenden zeichenfolgen suchen?#
mit dem auge ist es ja leicht zu erkennen, aber wie ich das mit C# realisieren würde, keinen schimmer 🙁
Ideen?

Ich wuerde es so machen einmal durch den Text zu laufen und keinen Katalog anzulegen welches Zeichen an welchen Positionen vorkommt. Dann einmal durch diesen Katalog und dabei einen neuen Katalog anlegen welche Abstaende zwischen zwei Zeichen ueberhaupt auftreten und wo und zwischen welchen Zeichen. Dann letztendlich noch durch diesen Katalog und schauen, ob die Abstaende nicht nur bei einzelnen Zeichen, sondern ganzen Zeichenketten auftreten und voila


//Katalog anfertigen, wo fuer jedes Zeichen alle Positionen aufgefuehrt ist

Dictionary<Char, List<Integer>> zeichenkatalog = new Dictionary<Char, List<Integer>>();

Char c;

for (Integer i=0;i<text.Length;i++)
{
//nicht case sensitive
   c=text[i].ToLower();
   if (!zeichenkatalog.Contains(c)) zeichenkatalog.Add(c, new List<Integer>());
   zeichenkatalog[c].Add(i)
}

//Katalog anfertigen, wo alle moeglichen Abstaende mit deren jeweiligen Positionen aufgefuehrt sind

Dictionary<Integer, List<Integer>> positionskatalog = new Dictionary<Integer, List<Integer>>;

foreach KeyValuePair<Char, List<Integer>> in zeichenkatalog
{
   if (kv.Value.Count>1)
   {
      for (Integer i=0;i<kv.Value.Length-1;i++)
      {
         for (Integer j=i+1;j<kv.Value.Length;j++)
         {
            if (!positionskatalog.Contains(kv.Value(j)-kv.Value(i))) positionskatalog.Add(kv.Value(j)-kv.Value(i), new List<Integer>());
            positionskatalog[kv.Value(j)-kv.Value(i)].Add(kv.Value(i));
         }
      }
   }
}

//Jetzt muessen noch die Vorkommen ueberprueft werden, ob es ganze Zeichenfolgen sind

List<Integer> moeglicheAbstaende = new List<Integer>;
foreach KeyValuePair<Integer, List<Integer>> in positionskatalog
{
   if (kv.Value.Count>1
//hier koennen wir noch optional doppelte Buchstaben filtern
   && kv.Key>2)
   {
      kv.Value.Sort();
      Integer letztePosition=-2;
      foreach Integer i in kv.Value
      {
//wir nehmen mal alles ab Zeichenfolgelaenge 2 mit auf, man kann hier aber auch //noch filtern
         if (i==letztePosition+1 && !moeglicheAbstaende.Contains(kv.Key)) moeglicheAbstaende.Add(kv.Key);
         letztePosition=i;
      }
   }
}

NB: alles ungetestet, hoffe dass es funktioniert

//edit: Etwas aufgehuebscht

hmm enthält viele fehler, hab das bissl korrigiert aber in z. 61 und 83 ( die foreach statements ) sind irgendwie falsch ^^

Error 1 Type and identifier are both required in a foreach statement C:\Users\Tim\Documents\Visual Studio 2008\Projects\Vid\Vid\Program.cs 63 43 Vid
Error 2 Type and identifier are both required in a foreach statement C:\Users\Tim\Documents\Visual Studio 2008\Projects\Vid\Vid\Program.cs 81 46 Vid

edit : korrigiert, fehlerfreier code :

             //Katalog anfertigen, wo fuer jedes Zeichen alle Positionen aufgefuehrt ist

Dictionary<Char, List<Integer>> zeichenkatalog = new Dictionary<Char, List<Integer>>();

Char c;

for (Integer i=0;i<text.Length;i++)
{
//nicht case sensitive
   c=text[i].ToLower();
   if (!zeichenkatalog.Contains(c)) zeichenkatalog.Add(c, new List<Integer>());
   zeichenkatalog[c].Add(i);
}

//Katalog anfertigen, wo alle moeglichen Abstaende mit deren jeweiligen Positionen aufgefuehrt sind

Dictionary<Integer, List<Integer>> positionskatalog = new Dictionary<Integer, List<Integer>>();

foreach(KeyValuePair<Char, List<Integer>> kv in zeichenkatalog)
{
   if (kv.Value.Count>1)
   {
      for (Integer i=0;i<kv.Value.Length-1;i++)
      {
         for (Integer j=i+1;j<kv.Value.Length;j++)
         {
            if (!positionskatalog.Contains(kv.Value(j)-kv.Value(i))) positionskatalog.Add(kv.Value(j)-kv.Value(i), new List<Integer>());
            positionskatalog[kv.Value(j)-kv.Value(i)].Add(kv.Value(i));
         }
      }
   }
}

//Jetzt muessen noch die Vorkommen ueberprueft werden, ob es ganze Zeichenfolgen sind

List<Integer> moeglicheAbstaende = new List<Integer>();
foreach(KeyValuePair<Integer, List<Integer>> kv in positionskatalog)
{
   if (kv.Value.Count>1
//hier koennen wir noch optional doppelte Buchstaben filtern
   && kv.Key>2)
   {
      kv.Value.Sort();
      Integer letztePosition=-2;
      foreach (int i in kv.Value)
      {
//wir nehmen mal alles ab Zeichenfolgelaenge 2 mit auf, man kann hier aber auch //noch filtern
         if (i==letztePosition+1 && !moeglicheAbstaende.Contains(kv.Key)) moeglicheAbstaende.Add(kv.Key);
         letztePosition=i;
      }
   }
}

edit 2: jetzt treten noch mehr fehler auf ^^ ( an die 30 )

ja da sieht man das er das vrom stretch geschrieben hat. da sind so einige klammer fehler drinnen aber das sollte dir wohl eher das prinzip verdeutlichen.

joa stimmt nur sagt mir das grad irgendwie garnichts 🙁 hab sowas in der richtung noch nie gemacht ;S

ja da sieht man das er das vrom stretch geschrieben hat.

Heißt das nicht 'from scratch'?! 😉

Gruß
s-sharp

Ja, hab hier auf Arbeit keine IDE. Dazu kommt, dass ich bisher noch fast nix in C# gemacht hab, 99% VB.NET 🙂