Informatyka dla klas II

Szyfr Cezara

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

 

Algorytm szyfrowania tekstu kodem Cezara

Wejście
Łańcuch tekstowy s
Wyjście:

Łańcuch tekstowy s  zaszyfrowany kodem Cezara

Elementy pomocnicze:
i  –  indeks, i obrazek N
kod(x)  – zwraca kod litery x
znak(x)  – zamienia kod x  na odpowiadający mu znak ASCII
Lista kroków:
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  

 

Szyfrowanie Szyfrem Cezara
(C)2014 mgr Jerzy Wałaszek

 

.

Algorytm deszyfrowania tekstu zaszyfrowanego kodem Cezara

Wejście

Łańcuch tekstowy s  zaszyfrowany kodem Cezara

Wyjście:

Tekst jawny

Elementy pomocnicze:
i  –  indeks, i obrazek N
kod(x)  – zwraca kod litery x
znak(x)  – zamienia kod x  na odpowiadający mu znak ASCII
Lista kroków:
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  

 

Szyfrowanie Szyfrem Cezara
(C)2014 mgr Jerzy Wałaszek


 

.

 

Szyfrowanie z pseudolosowym odstępem

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.

 

Projekt generatora LCG

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.

 

Szyfrowanie

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.

 

Algorytm szyfrowania z pseudolosowym odstępem

Wejście
X  –  klucz, X obrazek N
m,a, c  – parametry generatora LCG, m,a,c obrazek N
s  – łańcuch tekstowy
Wyjście:

Zaszyfrowany łańcuch s

Elementy pomocnicze:
i  –  indeks, i obrazek N
kod(x)  – zwraca kod litery x
znak(x)  – zamienia kod x  na odpowiadający mu znak ASCII
Lista kroków:
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

 

Szyfrowanie kodem o pseudolosowym odstępie
(C)2014 mgr Jerzy Wałaszek

Klucz 0 ... 3956279999 :


.

 

Deszyfrowanie

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

 

Algorytm deszyfrowania z pseudolosowym odstępem

Wejście
X  –  klucz, X obrazek N
m, a, c  – parametry generatora LCG, m,a,c obrazek N
s  – zaszyfrowany łańcuch tekstowy
Wyjście:

Rozszyfrowany łańcuch s

Elementy pomocnicze:
i  –  indeks, i obrazek N
kod(x)  – zwraca kod litery x
znak(x)  – zamienia kod x na odpowiadający mu znak ASCII
Lista kroków:
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

 

Deszyfrowanie kodu o pseudolosowym odstępie
(C)2014 mgr Jerzy Wałaszek

Klucz 0 ... 3956279999 :


.


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2024 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

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