Autor artykułu: mgr Jerzy Wałaszek, wersja1.0
©2011 mgr
Jerzy Wałaszek
I LO w Tarnowie
|
|
Autor artykułu: mgr Jerzy Wałaszek, wersja1.0 |
©2011 mgr
Jerzy Wałaszek
|
Szyfrowanie tekstów (ang. text encryption) ma na celu ukrycie ważnych informacji przed dostępem do nich osób niepowołanych. Historia kodów szyfrujących sięga czasów starożytnych. Już tysiące lat temu egipscy kapłani stosowali specjalny system hieroglifów do szyfrowania różnych tajnych wiadomości. Szyfr Cezara (ang. Ceasar's Code lub Ceasar's Cipher) jest bardzo prostym szyfrem podstawieniowym (ang. substitution cipher). Szyfry podstawieniowe polegają na zastępowaniu znaków tekstu jawnego (ang. plaintext) innymi znakami przez co zawarta w tekście informacja staje się nieczytelna dla osób niewtajemniczonych. Współcześnie szyfrowanie stanowi jedną z najważniejszych dziedzin informatyki – to dzięki niej stał się możliwy handel w Internecie, funkcjonują banki ze zdalnym dostępem do kont, powstał podpis elektroniczny oraz bezpieczne łącza transmisji danych. Przykładów zastosowania jest bez liku i dokładne omówienie tej dziedziny wiedzy leży daleko poza możliwościami tego artykułu.
Szyfr Cezara został nazwany na cześć rzymskiego imperatora Juliusza Cezara, który stosował ten sposób szyfrowania do przekazywania informacji o znaczeniu wojskowym. Szyfr polega na zastępowaniu liter alfabetu A...Z literami leżącymi o trzy pozycje dalej w alfabecie:
| Tekst jawny | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
| Szyfr Cezara | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C |
Ostatnie trzy znaki X, Y i Z nie posiadają następników w alfabecie przesuniętych o trzy pozycje. Dlatego umawiamy się, iż alfabet "zawija się" i za literką Z następuje znów litera A. Teraz bez problemu znajdziemy następniki X → A, Y → B i Z → C.
Przykład:
Zaszyfrować zdanie: NIEPRZYJACIEL JEST BARDZO BLISKO.
Poszczególne literki tekstu jawnego zastępujemy literkami szyfru Cezara zgodnie z powyższą tabelką kodu. Spacje oraz inne znaki nie będące literami pozostawiamy bez zmian:
NIEPRZYJACIEL JEST BARDZO
BLISKO
QLHSUCBMDFLHO MHVW EDUGCR EOLVNR
Deszyfrowanie tekstu zaszyfrowanego kodem Cezara polega na wykonywaniu operacji odwrotnych. Każdą literę kodu zamieniamy na literę leżącą o trzy pozycje wcześniej w alfabecie.
| Szyfr Cezara | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
| Tekst jawny | X | Y | Z | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W |
Podobnie jak poprzednio trzy pierwsze znaki szyfru Cezara nie posiadają bezpośrednich odpowiedników liter leżących o trzy pozycje wcześniej, ponieważ alfabet rozpoczyna się dopiera od pozycji literki D. Rozwiązaniem jest ponowne "zawinięcie" alfabetu, tak aby przed literą A znalazły się trzy ostatnie literki X, Y i Z.
Do wyznaczania kodu literek przy szyfrowaniu i deszyfrowaniu posłużymy się operacjami modulo. Operacja modulo jest resztą z dzielenia danej liczby przez moduł. Wynik jest zawsze mniejszy od modułu. U nas moduł będzie równy 26, ponieważ tyle mamy liter alfabetu.
Jeśli c jest kodem ASCII dużej litery alfabetu (rozważamy tylko teksty zbudowane z dużych liter), to szyfrowanie kodem Cezara polega na wykonaniu następującej operacji arytmetycznej:
c = 65 + (c - 62) mod 26
Deszyfrowanie polega na zamianie kodu wg wzoru:
c = 65 + (c - 42) mod 26
Łańcuch tekstowy s
Łańcuch tekstowy s zaszyfrowany kodem Cezara
| i | – | indeks, i
N |
| kod(x) | – | zwraca kod litery x |
| znak(x) | – | zamienia kod x na odpowiadający mu znak ASCII |
| K01: | Dla i = 0,1,...,|s| - 1 wykonuj K02...K03 | ; przeglądamy kolejne znaki tekstu |
| K02: | Jeśli s[i] < "A" ∨ s[i] > "Z", to następny obieg pętli K01 | ; pomijamy znaki nie będące literami A...Z |
| K03: | s[i] ← znak(65 + (kod(s[i]) - 62) mod 26) | ; szyfrujemy szyfrem Cezara |
| K04: | Pisz s | |
| K05: | Zakończ |
Łańcuch tekstowy s zaszyfrowany kodem Cezara
Tekst jawny
| i | – | indeks, i
N |
| kod(x) | – | zwraca kod litery x |
| znak(x) | – | zamienia kod x na odpowiadający mu znak ASCII |
| K01: | Dla i = 0,1,...,|s| - 1 wykonuj K02...K03 | ; przetwarzamy kolejne znaki tekstu |
| K02: | Jeśli s[i] < "A" ∨ s[i] > "Z", to następny obieg pętli K01 | ; pomijamy znaki nie będące literami A...Z |
| K03: | s[i] ← znak(65 + (kod(s[i] - 42) mod 26) | ; deszyfrujemy |
| K04: | Pisz s | |
| K05: | Zakończ |
Szyfr Cezara posiada kilka wad, które uniemożliwiają praktyczne zastosowanie. Po pierwsze wystarczy odkryć wartość przesunięcia kodów (oryginalnie wynosi ono 3, lecz można je zmieniać w zakresie od 1 do 25), aby rozszyfrować całą wiadomość. W tym celu należy przeprowadzić 25 prób, co dla współczesnych komputerów nie stanowi żadnego problemu.
| Przesunięcie kodów | Szyfr |
| 0 | ALA MA KOTA |
| + 1 | BMB NB LPUB |
| + 2 | CNC OC MQVC |
| + 3 | DOD PD NRWD |
| + 4 | EPE QE OSXE |
| + 5 | FQF RF PTYF |
Po drugie, z uwagi na stałe przesunięcie kodów, te same znaki są zawsze szyfrowane tak samo. Jeśli na przykład zaszyfrujemy AAAAAAAAAA, to otrzymamy ciąg DDDDDDDDDD.
Aby znacząco utrudnić rozszyfrowanie wiadomości zaprojektujemy szyfr, w którym przesunięcie kodów będzie się zmieniało w zakresie od 0 do 25 w trakcie szyfrowania znaków. Do tego celu potrzebna nam jest możliwość generacji tych samych ciągów liczbowych przy szyfrowaniu oraz rozszyfrowywaniu. Wykorzystamy generator pseudolosowy LCG, który startując od określonego ziarna tworzy zawsze te same ciągi liczb pseudolosowych. Kluczem szyfrującym będą parametry generatora oraz wartość ziarna pseudolosowego. Parametry generatora: moduł m, mnożnik a oraz przyrost c zostaną na stałe zdefiniowane w programie (możesz je zmienić, wtedy zmianie ulegnie sposób szyfrowania). Użytkownik będzie jedynie podawał wartość ziarna pseudolosowego Xo. Sposób projektowania generatora LCG opisaliśmy w rozdziale o liczbach pseudolosowych.
Im większy zakres generowanych liczb pseudolosowych, tym dłuższy okres powtarzania tworzonego ciągu. W efekcie trudniejsze jest złamanie szyfru. Kryptologia potrafi bez większych problemów łamać szyfry oparte na prostych generatorach pseudolosowych z uwagi na ich właściwości, dlatego nie są one stosowane w praktycznych systemach szyfrowania – użyty generator musi być kryptologicznie bezpieczny. My się tym nie będziemy przejmowali, ponieważ nasz projekt jest czysto dydaktyczny.
Wybieramy zakres od 0 do Xmax = 3956279999.
Moduł m jest równy Xmax + 1 = 3956280000
Czynniki pierwsze modułu m = 3956280000 = 2 × 2 × 2 × 2 × 2 × 2 × 3 × 5 × 5 × 5 × 5 × 32969
Przyrost c = 7 × 11 × 17 = 1309
Mnożnik a - 1 = 2 × 2 × 3 × 5 × 32969 = 1978140, stąd a = 1978141.
Podsumowując otrzymujemy następujący generator LCG:
LCG(3956280000,1978141,1309,Xo)
Ziarno Xo jest w zakresie od 0 do Xmax, czyli od 0 do 3956279999. Liczba ta będzie naszym kluczem szyfrującym.
Zasada szyfrowania jest następująca:
Odczytujemy klucz i wprowadzamy go do ziarna pseudolosowego naszego generatora LCG. Na podstawie tego klucza generator LCG będzie tworzył ściśle określony ciąg liczb pseudolosowych. Odczytujemy następnie łańcuch s, który ma zostać zaszyfrowany. Zamieniamy wszystkie litery z małych na duże (nasz algorytm szyfruje tylko duże znaki). Przetwarzamy kolejne znaki tego łańcucha. Dla każdego znaku generujemy liczbę pseudolosową X. Teraz sprawdzamy, czy przetwarzany znak łańcucha s jest dużą literą od A do Z. Jeśli tak, to obliczamy jego kod ch i przekształcamy go zgodnie ze wzorem:
ch = 65 + (ch - 65 + X mod 26) mod 26
Wynik jest kodem zaszyfrowanego znaku – umieszczamy go w łańcuchu s na miejscu przetwarzanego znaku i kontynuujemy te same operacje aż do przetworzenia wszystkich znaków w s. Na końcu łańcuch s zwracamy jako wynik szyfrowania.
| X | – | klucz, X
N |
| m,a, c | – | parametry generatora LCG, m,a,c
N |
| s | – | łańcuch tekstowy |
Zaszyfrowany łańcuch s
| i | – | indeks, i
N |
| kod(x) | – | zwraca kod litery x |
| znak(x) | – | zamienia kod x na odpowiadający mu znak ASCII |
| K01: | Dla i = 0,1,...,|s| - 1, wykonuj K02...K04 | ; przetwarzamy kolejne znaki łańcucha s |
| K02: | X ← (a × X + c) mod m | ; obliczamy nową liczbę pseudolosową |
| K03: | Jeśli s[i] < 'A' ∨ s[i] > 'Z', to następny obieg pętli K01 | ; pomijamy znaki nie będące literami od A do Z |
| K04: | s[i] = znak(65 + (kod(s[i]) - 65 + X mod 26) mod 26) | ; szyfrujemy |
| K05: | Pisz s | ; wyprowadzamy szyfr |
| K06: | Zakończ | ; gotowe |
Zwróć uwagę, iż dla różnych kluczy otrzymujemy zupełnie inne szyfry. Co więcej powtarzające się literki (tutaj A przed i za tekstem) zostają zaszyfrowane w różne znaki – to zaleta szyfru z pseudolosowym odstępem. Aby ukryć odstępy między wyrazami, które pozwalają zidentyfikować słowa, można wpisywać w ich miejsce wybraną literkę (np.X – tak postępowali operatorzy niemieckich maszyn Enigma w czasie II Wojny Światowej). Wtedy szyfr stanie się jednolitym blokiem liter.
Zasada rozszyfrowywania jest prawie identyczna jak przy szyfrowaniu. Jedyna różnica leży we wzorze obliczania kodu znaku z kodu szyfru:
ch = 65 + (ch - 39 - X mod 26) mod 26
| X | – | klucz, X
N |
| m, a, c | – | parametry generatora LCG, m,a,c
N |
| s | – | zaszyfrowany łańcuch tekstowy |
Rozszyfrowany łańcuch s
| i | – | indeks, i
N |
| kod(x) | – | zwraca kod litery x |
| znak(x) | – | zamienia kod x na odpowiadający mu znak ASCII |
| K01: | Dla i = 0,1,...,|s| - 1, wykonuj K02...K04 | ; przetwarzamy kolejne znaki łańcucha s |
| K02: | X ← (a × X + c) mod m | ; obliczamy nową liczbę pseudolosową |
| K03: | Jeśli s[i] < 'A' ∨ s[i] > 'Z', to następny obieg pętli K01 | ; pomijamy znaki nie będące literami od A do Z |
| K04: | s[i] = znak(65 + (kod(s[i]) - 39 - X mod 26) mod 26) | ; rozszyfrowujemy |
| K05: | Pisz s | ; wyprowadzamy tekst |
| K06: | Zakończ | ; gotowe |
 | I Liceum Ogólnokształcące |
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe