728 x 90

, i

Szyfr kraju żabich udek

Szyfr kraju żabich udek

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

 

Zdjęcie tytułowe pochodzi z freeimages.com

Implementacje, wykresy, szyfracja oraz kryptoanaliza powstały we własnym zakresie

Leave a Comment

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

Cancel reply

Inne artykuły