728 x 90

, i

Co wspólnego ma Juliusz Cezar z Twoim smartfonem?

Co wspólnego ma Juliusz Cezar z Twoim smartfonem?

Zapewne wiele razy słyszeliście, że twórcom najbardziej popularnych systemów mobilnych na świecie bardzo zależy na Waszej prywatności. W tym celu korzystają z coraz bardziej wymyślnych technik szyfrowania danych zarówno przesyłanych przez sieć, jak i przechowywanych wewnątrz urządzeń. Tymczasem szyfrowania używano z powodzeniem już w czasach Juliusza Cezara. Ten artykuł jest pierwszym z serii dotyczącej kryptologii:

Szyfry podstawieniowe, część 1: szyfry monoalfabetyczne.

Wstęp

Kryptologia to dziedzina wiedzy dotycząca bezpiecznego przekazywania informacji. Jej początki sięgają pierwszych tajemnic człowieka. Używano jej, gdy dwie strony chciały chronić wiadomości przed osobami postronnymi. Wraz z rozwojem militarnych zapędów ludzkości, zaczęto przywiązywać znaczną wagę do poufności korespondencji, a informacja stała się jednym z najważniejszych posiadanych zasobów.

Jednym z pierwszych znanych szyfrów był szyfr Cezara, używany około 58 r. p. n. e. Cezar przesuwał każdą literę w swoich wojskowych rozkazach aby były niezrozumiałe dla wroga, gdyby tamten je przechwycił. Wyobraźmy sobie, że Alicja i Bob decydują się porozumiewać używając szyfru Cezara. Po pierwsze, muszą wcześniej uzgodnić jakiego będą używać klucza, np. 3. Aby zaszyfrować tekst Alicja musi zamienić każdą literę tekstu jawnego na taką, która znajduje trzy miejsca dalej w alfabecie. Zatem A przechodzi na D, B przechodzi na E, a C przechodzi na F i tak dalej. Ta zaszyfrowana wiadomość zostaje  wysłana do Boba. Teraz Bob po prostu przesuwa każdą literę w drugą stronę, aby odczytać pierwotną wiadomość.  Niezrozumiałe? Zaraz to dogłębnie wytłumaczymy.

Na opisanej powyżej zasadzie działają właśnie szyfry podstawieniowe –  każdy znak tekstu jawnego zastępowany jest przez inny znak lub znaki szyfrogramu  Dziś zajmiemy się szczególnym przypadkiem szyfru podstawieniowego – szyfrem monoalfabetycznym, w którym każdy symbol jednoznacznie zastępowany jest innym. W następnych częściach wgłębimy się  w inne zagadnienia kryptologiczne.

Szyfrowanie

Szyfrowanie symetryczne opiera się na jednym tajnym kluczu znanym tylko stronom konwersacji.  W szyfrze monoalfabetycznym każda litera posiada zawsze jednoznacznie określony odpowiednik, co jest szczególnie istotne podczas kryptoanalizy. Oznacza to, że jeśli mamy alfabet Q, złożony z n liter, to jego przestrzeń klucza, czyli ilość kluczy o określonej długości, wynosi n!.  Osoby znające podstawowe zagadnienia matematyczne, już widzą pewien problem. Jednak dla osób mniej wtajemniczonych, postaramy się to wyjaśnić. Silnia z liczby naturalnej n, to iloczyn  wszystkich liczb naturalnych dodatnich nie większych niż n np. 6!=6•5•4•3•2•1. Jak widzimy wartość tej funkcji ma bardzo szybki przyrost. Posłużmy się alfabetem języka łacińskiego zawierającego 26 znaków. Przestrzeń klucza wynosi 26!=26•25•…•3•2•1 co w przybliżeniu wynosi 288 . Dla zobrazowania – jest to liczba mająca 27 cyfr. Jednak kryptoanalizą zajmiemy się później.

Szczególnym przypadkiem takiego szyfru jest popularny szyfr Cezara, w którym każdą literę tekstu jawnego a przesuwamy o jednakową liczbę, mamy tu stałą k. Funkcja szyfrująca wygląda następująco:

F (a) = (a+k) mod n

gdzie:

  • a– wartość liczbowa przypisana danej literze
  • k– wartość przesunięcia, która jest tajnym kluczem
  • n– długość alfabetu

Przykład: Przyjmijmy klucz o wartości 3. Oznacza to, że każdą literę przesuwamy o 3 pozycję.

Nr litery

0

1

2

3

23

24

25

Oryginalny alfabet

A

B

C

D

X

Y

Z

Alfabet do szyfrowania

X

Y

Z

A

U

V

W

Chcemy teraz zaszyfrować słowo KRYPTOLOGIA, możemy skorzystać z naszej tablicy przedstawionej wyżej lub funkcji szyfrującej.

  • K jest 19 literą alfabetu, stąd F(10) = (10+3) mod 26 = 13 mod 26 = 13, a 13. Literą alfabetu jest N.
  • R: F(17)=(17+3) mod 26 = 20 czyli U.
  • Y: F(24)=(24+3) mod 26 = 1 a jej odpowiednikiem jest B

I tym sposobem szyfrujemy każdą literę naszego słowa.

Po wykonaniu tych operacji dla wszystkich liter otrzymujemy szyfrogram: NUBSWRORJLD.

Załóżmy teraz, że jesteśmy druga stroną konwersacji to znaczy otrzymujemy dany szyfrogram: NUBSWRORJLD kanałem niezabezpieczonym (nieodpornym na podsłuchy) oraz znamy klucz (stałą permutację e) równy 3. Aby odszyfrować wiadomość zaszyfrowaną szyfrem symetrycznym, należy obliczyć  permutację  odwrotną d=e-1 . Warto tutaj wspomnieć, że  Z26 jest grupą, a wynika to z następujących aksjomatów:

  • Działanie dodawania modularnego Z26 jest działaniem wewnętrznym
  • Istnieje element neutralny taki, że : a+e=e+a=a i jest nim 0
  • Każdy element t zbioru Z26  posiada element odwrotny  t-1   taki, że t-1 +t=e, w tym przypadku t-1 =26-t
  • Działanie jest łączne tzn. a+(b+c)=(a+b)+c

Przyjmijmy np. liczbę 4.  Jej elementem odwrotnym jest liczba 22, ponieważ 22+4 mod 26 = 0, a zero jest elementem neutralnym grupy addytywnej Z26, to wtedy do deszyfrowania używamy następującej funkcji:

D(a)=a+k-1 mod n

Przykład

Elementem odwrotnym do liczby 3, w grupie Z26 to 23 stąd:

  • N ma przyporządkowany numer 13.  D(13)=13+23 mod 26 = 10 -> K
  • Teraz litera U. D(20)=20+23 mod 26 = 17 -> R

Postępujemy analogicznie, dla pozostałych znaków. Po wykonaniu czynności dla wszystkich liter otrzymamy tekst jawny: KRYPTOLOGIA. Dla ułatwienia zamiast korzystać z elementu odwrotnego w Z26, możemy użyć zwykłego odejmowania, bo jak wiemy 23 przystaje do –3 modulo 25.

Kryptoanaliza

Jeżeli nie znamy tekstu jawnego, możemy policzyć rozkład statystyczny znaków w danym szyfrogramie i przyrównać go do rozkładu liter występującego w danym języku. Wyniki będą dokładniejsze, jeśli użyjemy tekstu tego samego autora, który jest twórcą szukanej przez nas wiadomości. Dzięki porównaniu częstości wystąpień znaków w tekstach można z łatwością dopasować znaki z szyfrogramu do odpowiadających im liter w tekście jawnym.

W przypadku szyfru Cezara złamanie szyfru może być jeszcze prostsze, ze względu na skończoną liczbę możliwych przesunięć. W alfabecie łacińskim wystarczy sprawdzać kolejno wartości klucza = 1, 2, 3… 25, aż do otrzymania sensownej wiadomości (metoda brute force). Średnio należy wykonać 26/2 = 13 prób.

Przykład

Tekst zaszyfrowany:

D RVJPVSRHJO IPNVZ NYGHUV; D ZSVDHJO DFKHJ AYBKUV
IPNVZB ZTHR WYGLKGPDUF, RVSVY P DVU JBKUH;
ZSVD AFSRV IYGLR BZSFZGF P YFTVD WVYGHKLR,
HSL AYLZJP PJO TPLQZRP UPL WVQTPL GVSHKLR.
HIF JLUPJ SPALDZRPL WPLZUP P WVAYHDF,
AYGLIH TPLJ GKYVDPL, UH DZP GFJ, DYHJHJ G VISHDF.
WYGLJPLG P ILG AFJO WYGFWYHD WVAYHDH UPL SHKH
QLZA IPNVZ, IV ZPL G QHYGFU KVIYFJO ZGABJGUPL ZRSHKH.
IPLYGL ZPL KVU ZPLRHUH, RDHZGVUH RHWBZAH,
RAVYH, DLKSL WYGFZSVDPH, ZHTH PKGPL D BZAH;
GHTRUPLAH D RVASL, SVULT DPSNVAULT VRYFDH
DFZGBRHULNV JGHZARP UHQSLWZGL TPLZPDH;
P WYHGF ZPL, HG VNPLU DZGFZARPL G UPLQ DFJPZUPL
ZVRP GFDUL, HG G IYGLNVD UHJGFUPH DHY WYFZUPL
P WVDPLAYGL KVRVSH GPVUPL HYVTHALT.
IPNVZ QBG NVAVD. ZAYGLSJF G AYGFRYVAUFT DPDHALT,
GIYVQUP SFGRHTP, IPLNH P IVKH UHJGFUPL,
TPLKG NYGTP, KFT IBJOH, IPNVZ QHR RHTMVYH NPUPL,
GUPRUHS, BSLJPHS; AFSRV D JGLSBZJPHJO ZHNHUVD
DYL WHYH QHR D RYHALYGL GHNHZSFJO DBSRHUVD.

W celu złamania szyfru wystarczy przyjrzeć się rozkładowi częstości znaków. Poniżej pokazana jest ich częstość w języku polskim, wyliczona na podstawie innego tekstu autora wiadomości.

Jak widać, jest ona dość charakterystyczna. Skoro szyfr Cezara jedynie przesuwa znaki o konkretną wartość, to wykres częstości znaków w tekście zaszyfrowanym będzie niemal identyczny. Niemal – będzie on przesunięty o konkretną wartość. Porównując oba wykresy wystarczy zauważyć różnicę między nimi – to znaczy o ile znaków dany wykres został przesunięty.

Analizując wykresy łatwo zauważyć, że literze A w tekście jawnym odpowiadać będzie litera H, F ->M i tak dalej. Wynika z tego, że szukany klucz jest równy 7. Skoro tak, to ,,cofając” każdy znak o siedem otrzymamy tekst:

W KOCIOLKACH BIGOS GRZANO; W SLOWACH WYDAC TRUDNO
BIGOSU SMAK PRZEDZIWNY, KOLOR I WON CUDNA;
SLOW TYLKO BRZEK USLYSZY I RYMOW PORZADEK,
ALE TRESCI ICH MIEJSKI NIE POJMIE ZOLADEK.
ABY CENIC LITEWSKIE PIESNI I POTRAWY,
TRZEBA MIEC ZDROWIE, NA WSI ZYC, WRACAC Z OBLAWY.
PRZECIEZ I BEZ TYCH PRZYPRAW POTRAWA NIE LADA
JEST BIGOS, BO SIE Z JARZYN DOBRYCH SZTUCZNIE SKLADA.
BIERZE SIE DON SIEKANA, KWASZONA KAPUSTA,
KTORA, WEDLE PRZYSLOWIA, SAMA IDZIE W USTA;
ZAMKNIETA W KOTLE, LONEM WILGOTNEM OKRYWA
WYSZUKANEGO CZASTKI NAJLEPSZE MIESIWA;
I PRAZY SIE, AZ OGIEN WSZYSTKIE Z NIEJ WYCISNIE
SOKI ZYWNE, AZ Z BRZEGOW NACZYNIA WAR PRYSNIE
I POWIETRZE DOKOLA ZIONIE AROMATEM.
BIGOS JUZ GOTOW. STRZELCY Z TRZYKROTNYM WIWATEM,
ZBROJNI LYZKAMI, BIEGA I BODA NACZYNIE,
MIEDZ GRZMI, DYM BUCHA, BIGOS JAK KAMFORA GINIE,
ZNIKNAL, ULECIAL; TYLKO W CZELUSCIACH SAGANOW
WRE PARA JAK W KRATERZE ZAGASLYCH WULKANOW.

Poniżej znajduje się kod w języku C++, którego zadaniem jest ustalenie częstości występowania znaków w podanym pliku tekstowym. Funkcja ta zwraca tablicę struktur, w której to każda litera ma przyporządkowaną ilość wystąpień. Najważniejszą rolę odgrywa pętla while, która zlicza  ilość wystąpień poszczególnych znaków alfabetu. Odczytywane są kolejne znaki, jeśli napotkana zostanie spacja, wtedy jest ona ignorowana i liczniki nie zwiększają się.

struct pakiet {
  float licznik = 0;
  char first;
};

struct pakiet* count() {
  std::fstream file;
  file.open("szyfrowany.txt", std::ios::in);
  struct pakiet* wsk = new pakiet[26];
  char tmp;  int licznik = 0;
  for (int= 0;< 26;++) {
    wsk[i].first = (char)(+ 97);
  }  
while (!file.eof()) {
   file >> tmp;
   if ((int)tmp != 32) {
    wsk[(int)tmp - 97].licznik++;
     licznik++;
   }  
  } 
 return wsk;
}

Leave a Comment

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

Cancel 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