728 x 90

, i

Szyfr państwa białej flagi

Szyfr państwa białej flagi

Blaise de Vigenère pochodził z XVI-wiecznej Francji.  Jak możemy się domyślać, stworzył szyfr Vigenère’a, który przez lata był zagadką dla kryptoanalityków tamtych lat. Oczywiście jest to bzdura! Jak w wielu przypadkach prawdziwy twórca został zapomniany, a był nim Giovan Battista Bellaso. Już 33 lata wcześniej opisał w swojej broszurze ten kryptosystem. Zdziwieni? A kto według was wynalazł radio? Marconi? Przez wiele lat taka była oficjalna wersja, jednak dziś wiemy, że wspomniana osoba ukradła ten pomysł. Prawdziwym twórcą był niedoceniany Nicola Tesla. A teraz przykład z naszego podwórka: przez lata za kryptologa, który złamał legendarną Enigmę, uważany był Alan Turing, co jak dziś wiemy nie jest do końca prawdą. Jego prace opierały się na wcześniejszych rozważaniach polskiego Biura Szyfrów Oddziału II Sztabu Głównego Wojska Polskiego, ale o tym przeczytacie w kolejnych artykułach.

Ten artykuł jest drugim z serii dotyczącej kryptologii

Szyfry podstawieniowe, część 2: polialfabetyczny szyfr Vigenère’a

Jeżeli nie czytałeś pierwszej części, serdecznie zapraszamy do zapoznania się z artykułem https://friweb.pl/co-wspolnego-ma-juliusz-cezar-z-twoim-smartfonem/ 

Zachęcamy również do podrzucania propozycji tematów kolejnych artykułów w komentarzach lub za pomocą naszego maila trywialnakrata@gmail.com.

Wstęp

Szyfr polialfabetyczny, w odróżnieniu do klasycznego, monoalfabetycznego  szyfru (np. Cezara), składa się nie z jednego, a wielu przekształceń. Jeżeli za liczbę przekształceń przyjąć n, to kolejne znaki oryginalnej wiadomości szyfrowane są kolejnymi przekształceniami. Po zaszyfrowaniu n znaków przekształcenia są powtarzane od litery n+1. Obecnie takie szyfry nie są już używane, jednak przez pewien czas stanowiły wyzwanie dla kryptologów, więc warto o nich wspomnieć. Jednym z przykładów szyfrów polialfabetycznych jest właśnie  szyfr Vigenère’a.

Szyfrowanie

W poprzednim artykule opisaliśmy szyfr Cezara, w którym każdą literę szyfrogramu zastępowaliśmy inną, jednoznacznie określoną. Tym razem będzie inaczej.  Naszym kluczem będzie jedno słowo, pamiętajmy także aby nie używać polskich znaków alfabetycznych oraz spacji. W szyfrze Vigenère’a możemy używać specjalnych tablic, w których każdy wiersz odpowiada szyfrowi Cezara z różnym przesunięciem tzn.  w pierwszym wierszu przesunięcie równe 0 , w drugim 1 itd do momentu aż powstanie macierz wymiaru NxN, gdzie N to liczba liter w alfabecie. W przypadku alfabetu łacińskiego N=25.

Innym sposobem jest skorzystanie z funkcji szyfrującej dla szyfru monoalfabetycznego.

f( a ) = ( a+k) mod N,

gdzie:

A – odpowiednik numeryczny danej litery tekstu jawnego

K i– odpowiednik numeryczny litery na i-tej pozycji klucza

N – ilość liter w alfabecie (pamiętajmy, że w informatyce rozpoczynamy liczenie od 0)

Litery alfabetu łacińskiego i ich odpowiedniki numeryczne:

Do zaszyfrowania wiadomości niezbędny jest tajny klucz. Jeśli jest on krótszy od oryginalnej wiadomości, musimy użyć go wielokrotnie, aby szyfrowanie przebiegło pomyślnie. Nasz klucz określa  przekształcenia kolejnych liter tekstu jawnego w szyfrogram. Weźmy pierwszy znak wiadomości oraz pierwszy znak klucza i wykonajmy dodawanie modularne odpowiadających im liczb (patrz tabelka wyżej). Wynik tego działania jest pierwszą literą szyfrogramu. Następnie należy postępować analogicznie z resztą tekstu.

Przykład:

Załóżmy teraz, że żyjemy w XVII w. Król Polski  Zygmunt III Waza nakazuje nam wysłać tajną wiadomość do hetmana koronnego Stanisława Żółkiewskiego, który przed kilkoma dniami zdobył Moskwę (1610r.). Bierzemy się zatem do pracy. Na początku musimy wybrać nasz tajny klucz. Niech będzie nim POLSKA. Ponadto władca przekazał nam wiadomość do wysłania, która brzmi następująco:

Necessitas in loco, spes in virtute, salus in victoria

Jest to łacińska sentencja używana przez Żółkiewskiego, która miała za zadanie zachęcić do walki. Oznacza: “Konieczność (obrony) w (tym) położeniu, nadzieja w męstwie, ocalenie w zwycięstwie”.

Algorytm naszej pracy wygląda następująco:

  • Bierzemy pierwszą literę szyfrogramu, jest nią: N. Z tabeli odczytujemy przyporządkowany numer: 13. Następnie czynność tę powtarzamy dla pierwszej litery klucza czyli P -> 15. Podstawiamy dane do wzoru i otrzymujemy 3 czyli Czemu? Ponieważ 13+15 =28 mod 25=3, używamy tu arytmetyki modularnej, co daje nam 3. Czym jest jednak tajemnicze oznaczenie mod? Jest to po prostu reszta z dzielenia przez daną liczbę.
  • Teraz powtarzamy czynność tylko dla drugiej litery klucza czyli e -> 4 : 4+14=18->S
  • Analogicznie dla pozostałych liter tekstu jawnego.

SZYFROGRAM: csnwcsxhlksnacngcptgtffighflospzfksnkwnlyrxo

Aby odszyfrować zakodowaną wiadomość, postępujemy bardzo podobnie. Wystarczy wykonać prostą operację na naszym tajnym kluczu, a potem postępować dokładnie tak samo jak w czasie szyfracji. Zamiana – klucza szyfrującego w klucz deszyfrujący przebiega zgodnie z poniższym wzorem:

K 2,i  = (26 – K 1,i) mod 25

K 2,i  – odpowiednik numeryczny litery na i-tej pozycji klucza po przekształceniu

K 1,i  – odpowiednik numeryczny litery na i-tej pozycji klucza użytego do szyfrowania

Kryptoanaliza

Pierwszym etapem łamania szyfru Vigenère’a jest odnalezienie długości klucza, który został użyty do zaszyfrowania wiadomości. Dwie podstawowe metody, którymi można się w tym celu posłużyć, to metoda Kasiskiego oraz metoda Friedmana.

Metoda Kasiskiego polega na odszukaniu w zaszyfrowanym tekście powtarzającego się ciągu znaków o długości co najmniej trzy. Przykładowo, ciąg xoz mógłby zostać znaleziony czterokrotnie na miejscach: 15, 25, 70 i 105. Można przypuszczać, że klucz jest najmniejszym wspólnym dzielnikiem (gcd) wartości pozycji, na których ciąg został znaleziony. W podanym przykładzie gcd(15, 25, 70, 105) = 5, więc spodziewamy się, że klucz będzie pięcioznakowy.

Metoda Friedmana opiera się na współczynniku koincydencji (inaczej indeks zgodności) oznaczany jako Ic(x). Przyjmijmy ciąg n znaków x = x1, x2, x3, …, xn. Współczynnik koincydencji definiuje się jako prawdopodobieństwo takiego zdarzenia, w którym dwa losowo wybrane znaki ciągu x są identyczne. W alfabecie łacińskim współczynnik koincydencji wygląda następująco:

gdzie fi jest częstością występowania znaku o wartości i.

 

Przyjmijmy, że e jest wiadomością zakodowaną szyfrem Vigenère’a. Teraz dla wartości m = 2, 3, 4… będziemy tworzyć m podciągów w następujący sposób: zi to podciąg w którym w mod m = i – 1, gdzie w oznacza wartość miejsca, na którym znajduje się znak. Wobec tego dla m = 2 w podciągu z1 występować będą znaki o miejscach 0, 2, 4, 6, …, a w z2 1, 3, 5, 7… i tak dalej.

Następnie dla każdego podciągu obliczamy koincydencje. Dla m = 2 należy policzyć koincydencje z1, z2 i policzyć ich średnią. Podobnie dla m = 3 istotna będzie średnia koincydencji z trzech podciągów. Każdą średnią przyrównujemy do koincydencji dla znaków w danym języku. W języku angielskim wartość koincydencji jest równa 0,065, ponieważ:

gdzie pi jest prawdopodobieństwem wystąpienia poszczególnych liter.

Wartość m przy średniej, która jest najbliższa wartości koincydencji w danym języku, prawdopodobnie jest szukaną długością klucza.

Po odnalezieniu długości klucza wystarczy już tylko stworzyć podciągi podobne do tych z metody Friedmana. Jeżeli m jest długością klucza, należy stworzyć m podciągów, przy czym do każdego z nich będą wchodziły znaki na miejscach w mod m = i – 1, gdzie w – znak, i – numer podciągu. Tak więc w skład podciągu pierwszego wchodzić będzie co m litera począwszy od pierwszej, dla drugiego co m zaczynając od drugiej i tak dalej.

Mając gotowe podciągi postępujemy z nimi bardzo podobnie, jak przy łamaniu szyfru Cezara. Dla każdego tworzymy wykres częstości występowania znaku, porównujemy z wykresem częstości liter w języku polskim i obliczamy prawidłowy znak dla dostrzeżonego przesunięcia. Pierwszy podciąg pozwala odzyskać pierwszą literę klucza, drugi drugą, trzeci trzecią i tak dalej. Ostatecznie po porównaniu wykresów każdego podciągu otrzymujemy cały klucz użyty do zaszyfrowania wiadomości, a co za tym idzie – z łatwością możemy ją odszyfrować.

Przykład:

Tekst zaszyfrowany:

eolqh pqqiv tbjym pgxms jracb dwfac jpzia uoxck lgjyt nwfvh pbjyc zglim lzpmb
hhzgb kshiv jabaz ekpdz acasb uojtz oomvx dkpqb kotek laxsq zqahh vhplz nwfjn
afayc kwmus lykuj nwqcr lzfgj ccuen xcxcz nbjya jzpvx awfem tscsr dhbfr tsqic
pxstk tkzqn msden rctgx dzbwy pqjmh pgqly pqjqh lcotz dpzwl znfnd rcocd kfpvh
ocqij tbjyt coacr kupln kybtd xdpjq ksaes zfztz xwbms mmdqk lrdur eomvx dgjyo
lbfgh koncz dhlln wsntm tsouv traim jausq lbfgm tskyr ehpvn hwfgc zdsuv omqly
jajis pamoc kwxsq znocz uodsb sgjyl pguqd xwxmo lbjuk zazmk yctwh lhfhj ecqly
pguly pubtz doemo coxcd ozjqn dqjhh pdpqh ywfha lqtcd ywlif zapqh dwftd ddsuv
tsefh hwocd zpbqh lxbmh pppaz kbbwy jhptd ywfjn efaya fxbmh pupvz ndphh pkbtr
eosui lgjyf znbxn hcmcb toaxn vcowz hmqyk ywbdz ushio cnzez koocz

 

Przykładowy kod dla metody Kasiskiego:

 
def Kasiski (cipher, i, powtorzenia, nwd):
    tab=["a", "b", "c"]
    flaga = 0
    tab[0] = cipher[i]    
    tab[1] = cipher[i+1]    
    tab[2] = cipher[i+2]    
    miejsca = []    
    miejsca.append(i)    
    dlugosc = len(cipher)    
    for l in range (0, dlugosc-2):        
        if l == i:
            l=i+3
        elif tab[0]==cipher[l] and tab[1]==cipher[l+1] and tab[2]==cipher[l+2]:
            miejsca.append(l)
        l=l+3
        if flaga != 1:
        print tab
        flaga = 1
    if i < (dlugosc-6):
        n = miejsca[0]+1
        if flaga==1:
            print miejsca
        for a in range (1, len(miejsca)):
            n = gcd(n, miejsca[a]+1)
        if n != 1:
            nwd.append(n)
        return Kasiski (cipher, i+3, powtorzenia, nwd)
    else:        
        return nwd

 

Wyświetlane powtórzenia i ich miejsca wyglądają następująco:

Lista GCD powyższych miejsc, pomijając wartość 1, zawiera: 2, 10, 11, 11, 5, 2, 5, 5, 4, 2, 2, 2

Z uwagi na otrzymane wartości można uznać, że długość klucza wynosi 5.

Przykładowy kod dla metody Friedmana:

def Friedman(cipher, j):
    koincydencje = []
    A=0
    x=j
    for a in range(0, j):
        tab = ""
        il=0
        for i in range (0, len(cipher)):
        if i%j == a:
            tab = tab + cipher[i]
        X = coincidence_index(tab)
        koincydencje.append(X)
        del tab    
    for a in range(0, j):        
        A=A+koincydencje[a]    
        A=A/j    
    return A 

 

W powyższym przypadku j oznacza liczbę podciągów. Ostateczne wyniki dla naszego szyfrogramu przedstawiają się następująco:

 

Przyrównując powyższe wartości do wartości koincydencji znaków w języku polskim równej 0,0581 okazuje się, że najbliższy jest wynik obliczony dla 5 podciągów, więc to tej długości klucza można się spodziewać.

Teraz można przystąpić do próby odszyfrowania klucza.

Spróbujmy ustalić kolejne litery klucza pięcioznakowego = (k1, k2, k3, k4, k5). W tym celu stwórzmy podciągi znaków z co piątej litery (podobnie jak przy metodzie Friedmana).

Do liczenia częstości występowania znaków oraz ich ilości przydatna jest funkcja Static_Attack:

 

def Static_Attack (cipher):
    tab = []
    for i in range (0,26):
        x = cipher.count(chr(97+i))
        tab.append(x)
    for i in range (0,26):
        tab[i] = tab[i] / float(len(cipher))
        tab[i] = round(tab[i],5)
    return tab

 

Przykładowy kod dla tego etapu może wyglądać następująco:

pierwsza_klucza = []
for j in range (0, 5):
    print j
    pierwsza_klucza = []
    xxx=0
    for i in range (0, len(X)):
        if i%5 == j:
            pierwsza_klucza.append(X[i])
            xxx+=1
    tab_klucza = Static_Attack(pierwsza_klucza)
    print tab_klucza
    for i in range (0, len(tab_klucza)):
        tab_klucza[i] = tab_klucza[i] / float(xxx)
    print tab_klucza

 

Wyniki wywołania powyższego kodu można zapisać na wykresie. W załączonym poniżej przykładzie zamieszczony jest rozkład częstości dla podciągu pierwszego – dla pozostałych czterech można wykonać go analogicznie.

Oczywiście, podciąg pierwszy składa się z co piątej litery (zaczynając od pierwszej litery szyfrogramu), więc ma postać:

e p t p j d j u l n p z l h k j e a u o d k l z v n a k l n l c x n j a t d t p t m r d p p p l d z r k o t c k k x k z x m l e d l k d w t t j l t e h z o j p k z u s p x l z y l e p p d c o d p y l y z d d t h z l p k j y e f p n p e l z h t v h y u c k

Kolejny podciąg zawierałby co piątą literę zaczynając od drugiego znaku szyfrogramu, trzeci od trzeciego i tak dalej.

Jako że otrzymany w ten sposób rozkład częstości odpowiada pewnemu przesunięciu cyklicznemu częstości znaków w języku polskim należy porównać wykresy odpowiadające wynikom. Do wykresu z języka polskiego posłużmy się wykresem wygenerowanym na potrzeby poprzedniego artykułu:

Porównując wykres z każdego podciągu wraz z wykresem można (podobnie jak w szyfrze Cezara) łatwo ustalić przesunięcie, a więc i odpowiadającą przesunięciu literę klucza. Skoro każdy podciąg reprezentuje przekształcenie powstałe z jednej litery klucza, to przesunięcie obliczone dla podciągu drugiego jest pierwszym znakiem szukanego słowa, drugi podciąg – kolejny znak i tak dalej. Wyniki dla naszego przykładu przedstawione są w tabeli poniżej:

Po użyciu otrzymanego klucza zgodnie z zasadami odszyfrowania otrzymujemy wiadomość:

TAK WIEC POWINIENES WSTYDZIC SIE GDYBY OBJAWILA SIE U CIEBIE
NIEDOSKONALOSC W TYM CZEGO WYMAGA TWOJA POZYCJA I ZADALBYS
WOWCZAS KLAM WYROCZNI KTORA CIE POPRZEDZILA TAK JAK CI PISALEM
KROTKO MOWIAC NIE BYLOBY PIEKNIE BYS STAL SIE PODEJRZLIWY WOBEC
KOGOS MYSLAC ZE CI SIE SPRZECIWIA ON ZAS BYC MOZE TEGO NIE ZROBI DOPOKI
NIE URAZISZ GO ROZKAZEM POPRZEZ KTORY ZAMIAST BYC WLADCA STALBYS SIE
PANEM I ZAMIAST KROLEM ZNIENAWIDZONYM TYRANEM NIE JEST TO BOWIEM
DOPRAWDY PRZYMIOTEM LUDZI WYROZNIAJACYCH SIE MESTWEM I
WSPANIALOMYSLNOSCIA TEN KTO PRZESTRZEGA ZASAD SPRAWIEDLIWOSCI
NIEPOWINIEN BAC SIE NIKOGO MOWI SIE ZE SPRAWIEDLIWINIE OBAWIAJA SIE
BOGA ZNA CZY TO ZE NIE POTRZEBUJA SIE GO BAC PONIEWAZ STARAJA SIE GO
ZADOWOLIC I AZ DO KONCA WYPELNIAJA JEGO PRZYKAZANIA
4 comments

Leave a Comment

Your email address will not be published. Required fields are marked with *

Cancel reply

4 Comments

  • Czytelnik
    31 lipca 2017, 20:44

    Francja nie ma białej flagi [… fragment ocenzurowany przez redakcję …].

    I jeśli nawiązujecie to żartu że Francja kapituluje, to polecam podręczniki historii Europy i sprawdzić jak często, które kraje wywieszały białą flagę. Zobaczycie że Francuzi są jednym z najbardziej bitnych ludzi.

    REPLY
    • Mieczysław@Czytelnik
      31 lipca 2017, 21:45

      A ja polecam mieć trochę dystansu do tego co się czyta. Miałem kontakt z kilkoma francuzami i ich też to bawi. No i zobacz, chyba lepiej wywiesić białą flagę niż odwalać kretynizmy wysyłania na front żołnierzy w mundurach galowych, czy atakowania Rosji zimą.

      REPLY
    • Patryk Ostrowski@Czytelnik
      31 lipca 2017, 21:54

      Drogi Czytelniku
      Francja nie ma białej flagi, jednakże na słowa „biała flaga” kraj ten jako pierwszy nasuwa się na myśl chyba każdemu człowiekowi.
      Nie negujemy faktu, że wojska francuskie dzielnie stawiały czoła nieprzyjaciołom w wielu bitwach.
      Wartym uwagi jest tutaj aspekt napoleoński, a także polska rola jaką były pułki Legii Nadwiślańskiej (swoją drogą zapraszam na stronę Oddziału Historycznego WAT, którego jestem aktywnym członkiem : https://www.facebook.com/skh.wat/). Twierdzimy jedynie, że w kulturze (nie tylko Polskiej, ale Europejskiej) utarło się połączenie białego skrawka materiału z tym państwem, co od okresu I WŚ ma szerokie podstawy historyczne.
      Jeśli drogi Czytelnik pamięta kompromitację jaką była kampania francuska, to doskonale wie o co nam chodzi. Trwała ona od 10 maja do 22 czerwca, po czym “najbardziej bitni ludzie”, jak to Czytelnik określił, podpisali kapitulację (zaledwie półtora miesiąca). Dla porównania Polska nie skapitulowała, obrona Wizny trwała 3 dni mimo przewagi 40:1 (a z niektórych źródeł i 91:1) lub Powstanie Warszawskie – 63 dni.
      Jako, że nasze zainteresowania są kryptologiczne chcielibyśmy zwrócić szczególną uwagę na Enigmę, którą złamało polskie Biuro Szyfrów, mimo że francuzi twierdzili, iż jest to nie możliwe. Proszę sobie przypomnieć także jak zachowała się tchórzliwa Francja w stosunku do Polski we wrześniu 1939r, pomino zobowiązań jakie nakładały na nią traktaty.
      Chcielibyśmy również zwrócić uwagę, że używanie zwrotu „nieuk” może być uznane za obraźliwe i nie przystoi dobrze wychowanemu człowiekowi

      Francuske czołgi mają 8 biegów, jeden do przodu, 7 do tyłu. 😀

      Pozdrawiam

      REPLY
    • Druh much@Czytelnik
      1 sierpnia 2017, 19:22

      Podobno bitność opuściła Francuzów po masakrze Wielkiej Wojny, zwanej obecnie IWŚ. (Za R. Ziemkiewiczem). Jestem zwolennikiem demitologizacji historii. Wygrała IIWŚ Ameryka, dzięki czemu angielski jest językiem handlu i nauki. Nie dzięki Anglikom. Przed wojną, a nawet w jej trakcie, językiem nauki i polityki były francuski i niemiecki. Radzieccy matematycy jeszcze w 1944 r. publikowali artykuły po niemiecku. Taki mamy klimat. Gdyby nie don Adolfo, to USA toczyłyby wojnę z Anglią o dominację na oceanach. Tow. Dzugashvili też szykował się. Mieli łodzie podwodne. Tymczasem Francuzi zagazowani przez Niemców w czasie IWŚ mieli już dość. (Za R.Ziemkiewiczem ,,Jakie piękne samobójstwo"). W dżudo klepiemy matę kiedy mamy dość. Francuzi mieli dość, nawet jeśli nie wywiesili kaleson.

      REPLY

Inne artykuły

Zapraszamy na WMiI UMK

Studia na Wydziale Matematyki i Informatyki

Nasze szkolenia

iOS11 Design Patterns: szkolenie w Warszawie, 22-24.09.2017


Python – i Ty możesz programować: szkolenie dla nauczycieli, 13-14 września 2017 w Toruniu


Od zera do Apple kodera – szkolenie dla początkujących, 8-10 września 2017 w Warszawie


Xamarin – programowanie wieloplatformowe, 9-10 września 2017 w Toruniu

Ostatnie artykuły

Zapraszamy na UMK