Szyfr Vigenere’a

W tym semestrze na uczelni mamy przedmiot Wstęp do kryptografii mający nam przedstawić podstawy szyfrowania danych i muszę przyznać ,że jest nawet ciekawie. Mamy w ciągu semestru zrobić klika małych „projektów”. Na pierwszy ogień poszły historyczne szyfry. I pierwszym zadaniem było złamanie szyfru Vigenere’a metodą kryptoanalizy. Samo szyfrowanie jest bardzo proste, każdej literze alfabetu przypisujemy liczbę odpowiednio a -> 0, b -> 1, …. , z -> 25 . Zapisujemy tekst który chcemy zaszyfrować w postaci cyfr. Potem to samo robimy z kluczem, który wykorzystamy do szyfrowania. Samo szyfrowanie polega na dodaniu do siebie wartości danej pozycji w tekście i danej pozycji w kluczu (modulo 25 26). Jako, że klucz jest krótszy od tekstu to gdy się „skończy” zapisujemy go od początku i tak do momentu pokrycia całej długości tekstu. Gdy już pododajemy do siebie odpowiednie pozycje to zamieniamy liczby na litery.

Jak łamiemy szyfr?

Na początek musimy odgadnąć długość klucza użytego do zaszyfrowania tekstu. Na zajęciach przedstawiono nam 2 metody: Metodę Kasiskiego oraz metodę Friedmana.

Metoda Kasiskiego polega na wyszukiwaniu powtarzających się ciągów w tekście (więcej niż 3 znakowych). Analizujemy odległości miedzy występowaniami tych samych ciągów. Kasiski zauważył, że jeśli zbitki tych samych znaków powtarzały się np co 35, 70, 95, 15 ,23 to najprawdopodobniejszą długością klucza będzie 5 większość liczb dzieli się przez 5 (23 przyjmujemy jako skrajną wartość , ja w swojej implementacji brałem pod uwagę 60% „najlepszych” wyników tylko). Ogólniej mówiąc zbitki liter powtarzają się w pewnych odstępach będących wielokrotnością długości klucza, analizując wystąpienia zbitek możemy wywnioskować długość klucza.

Metoda Friedmana polega natomiast na analizowaniu ilości koincydencji. Jak to wygląda w praktyce? Zapisujemy „pod sobą” 2 razy szyfrogram jeden normalnie a drugi przesuwamy o ileś znaków. Następnie sprawdzamy ile razy wystąpi koincydencja tj. ile razy na miejscu i pojawia się w obu tekstach taka sama litera. Liczba koincydencji będzie największa przy przesunięciach o wielokrotność długości klucza. Jeśli analizujemy szyfrogram ręcznie to długość klucza zobaczymy od razu rysując sobie wykres koincydencji. W programie trzeba jakoś rozkminić, które przesunięcie jest tym „pierwszym odpowiednim”. Ja zdecydowałem się wziąć pierwszy element który będzie większy niż średnia + odchylenie standardowe wszystkich koincydencji. Poniżej kod realizujący te metodę.

private static int znajdzDlugoscKluczaFriedman(String szyfrogram) {
   int[] koincydencje = new int[szyfrogram.length()];
   for(int i=1;i<szyfrogram.length();i++)
      for (int j=0; j < szyfrogram.length(); j++)
         if(szyfrogram.charAt(j) == szyfrogram.charAt((i+j)%szyfrogram.length()))
            koincydencje[i]++;
   int sred=0;
   int odchyl=0;
   for (int j=0; j < szyfrogram.length(); j++)
      sred+=koincydencje[j];
   sred/=szyfrogram.length();
   for (int j=0; j < szyfrogram.length(); j++)
      odchyl+=Math.abs(koincydencje[j]-sred);
   odchyl/=szyfrogram.length();
   for (int j=0; j < szyfrogram.length(); j++)
      if(koincydencje[j] > sred + odchyl) return j;
         return 0;
}

Gdy znamy już długość klucza możemy przystąpić do jego łamania. Jak to zrobić?
Analizujemy częstość występowania konkretnych liter w tekście i porównujemy je z częstością występowania znaków w j. polskim. Np litera ‚a’ występuje w j. polskim z częstotliwością około 10%, więc jeśli w szyfrogramie znajdzie się litera występująca z podobną częstością to z dużym prawdopodobieństwem jest to zaszyfrowane ‚a’.
Wówczas od wartości liczbowej tej litery odejmujemy wartość liczbową naszego ‚a’ i w ten sposób otrzymujemy wart. liczbową danej litery klucza.
Oczywiście to bardzo mocne uproszczenie. W praktyce zdarza się że literka ‚a’ występuje nieco rzadziej niż np. literka ‚e’ a wg tabeli częstości powinna występować najczęściej.
Ja do odgadnięcia danej litery klucza zastosowałem znów odchylenie standardowe. Sprawdzając po kolei każdą literę jako daną pozycje klucza wybierałem tę, dla której suma wartości bezwzględnych odchyleń standardowych, między częstością w tekście a częstością w j. polskim była najmniejsza.

public static String odgadnijKlucz(String szyfrogram, int[][] czestosci, int dlKlucza){
   String tmp = "";
   for(int i=0;i<dlKlucza;i++){
      int indexZminOdchyleniami=0;
      int minOdch = Integer.MAX_VALUE;
      for(int j=0;j<26;j++){
         int sumaOdchylen = 0;
         for(int c='a';c<='z';c++){
            sumaOdchylen += Math.abs(czestosci[i][(c-'a'+j)%26] - czestosciPL[c-'a']);
         }
         if(sumaOdchylen < minOdch){
            indexZminOdchyleniami = j;
            minOdch = sumaOdchylen;
         }
      }
      tmp += (char)('a'+indexZminOdchyleniami);
   }
   return tmp;
}

No i to byłoby na tyle. Mnie zadanko zaciekawiło może i kogoś jeszcze zaciekawi :)

5 komentarzy to “Szyfr Vigenere’a”

You can leave a reply or Trackback this post.
  1. kalo - 02-11-2013

    Bardzo dobry artykuł – bardzo mi się przydał w zrozumieniu tego zagadnienia :)

  2. Qbisek - 18-12-2013

    Fajny, pomocny artykuł :) Drobny błąd we wstępie – powinno być modulo 26.

  3. Krzysztof Kędziorski - 18-01-2016

    Cieszę się, że wpis się przydał i dziękuje za wyłapanie błędu :) … poprawione

  4. Bartas - 09-10-2016

    Witam, piszę pracę magisterską na ten temat. Czy mógłby Pan podesłać literaturę, z której Pan korzystał publikując ów artykuł? :)

  5. Krzysztof Kędziorski - 09-10-2016

    Niestety nie. Wpis opierał się na wiedzy wyciągniętej z zajęć, a po 6 latach już nie mam szans nawet na odnalezienie notatek :)

Leave a Reply

Your email address will not be published.