Kryptografia

Ludzie od wieków stosowali rozmaite metody, by chronić ważne, poufne informacje. Spartanom przypisuje się autorstwo pierwszego narzędzia szyfrującego o nazwie skytale – był to skórzany lub pergaminowy pasek, na którym znajdowały się litery, odczytanie wiadomości było możliwe po nawinięciu go na laskę takiej samej grubości, jaką miał autor wiadomości. W trakcie $\text{II}$ wojny światowej Niemcy wykorzystywali urządzenie szyfrujące Enigma, a Polacy wsławili się dzięki rozszyfrowaniu wiadomości wojskowych, które ta maszyna szyfrowała. Do szyfrowaniaszyfrowanieszyfrowania nie zawsze konieczne są specjalne urządzenia, czasami wystarczy kartka i ołówek.

Rozmawiając ze znajomymi, korzystasz z różnych komunikatorów. Czasami zdarza się, że chcesz przekazać jakąś poufną informację. Zależy ci, by nikt poza odbiorcą jej nie przeczytał. Z pomocą może przyjść kryptografiakryptografiakryptografia.

Istnieje wiele algorytmów szyfrujących, które można wykorzystać. Najczęściej stosowane algorytmy polegają na specyficznym przekształceniu wiadomości za pomocą kluczakluczklucza.

Szyfry możemy podzielić na kilka rodzajów:

• szyfr podstawieniowy – każdy znak szyfrowanej wiadomości zostaje zastąpiony innym; deszyfrowanie polega na odwróceniu podstawienia; przykładem takiego szyfru jest szyfr CezaraPvJJ5fOYkszyfr Cezara;

• szyfr przestawieniowy – w zaszyfrowanej wiadomości obecne są wszystkie znaki użyte w tekście jawnym, zmieniona zostaje jedynie ich pozycja w szyfrogramieszyfrogramszyfrogramie; przykładem takiego szyfru jest szyfr płotkowy;

• szyfr symetryczny – wiadomość jest szyfrowana za pomocą tajnego klucza, który następnie służy do odczytania wiadomości;

• szyfr asymetryczny – wiadomość zostaje zaszyfrowana oraz deszyfrowana różnymi kluczami; klucz używany w procesie szyfrowania jest publicznyklucz publicznypubliczny, natomiast drugi klucz, wykorzystywany podczas deszyfrowania, jest prywatnyklucz prywatnyprywatny; przykładem takiego szyfru jest szyfr RSAPl0GrlFTpszyfr RSA.

W dalszej części materiału poznasz przykład szyfru przedstawieniowego – szyfr płotkowy.

Szyfr płotkowy – opis algorytmu szyfrowania

Chcesz przekazać przyjacielowi tajne miejsce waszego spotkania – punktem zbiórki jest fontanna w parku.

Aby zaszyfrować wiadomość za pomocą szyfru płotkowego, na początku należy wybrać klucz symetryczny, za pomocą którego zaszyfrujemy wiadomość. W przypadku tego algorytmu kluczem będzie wysokość płotku, czyli w podanym przykładzie: pięć kwadratów.

RmBQGOi8B89cM

Ilustracja przedstawia tabelę w kształcie płotu, gdzie każda deska podzielona jest na pięć części a na samej górze każdej deski znajduje się pole trójkąt.

Pierwszym krokiem będzie właściwe przygotowanie wiadomości. Należy zmienić wielkość wszystkich liter na duże (np. a na A) oraz usunąć spacje. Zmiana wielkości liter utrudni odczytanie szyfrogramu przez niepowołaną osobę. W efekcie otrzymamy następujący tekst:

FONTANNAWPARKU

Następnie należy wypełnić pola w płotku literami tekstu jawnego, począwszy od lewej górnej kratki schematu. W każdym kolejnym kroku następny znak szyfrowanego tekstu wpisujemy do pola diagramu ulokowanego o jedną pozycję na prawo oraz w dół w stosunku do poprzedniej kratki. W momencie, w którym osiągniemy pole znajdujące się w najniższym rzędzie płotku, zmieniamy kierunek wyboru kolejnych kratek – każde następne pole będzie zlokalizowane o jedną pozycję na prawo oraz do góry w stosunku do poprzedniej kratki. Gdy dotrzemy do pozycji w rzędzie najwyższym, ponownie zmieniamy kierunek. Proces ten powtarzamy, aż do wpisania w pola płotku wszystkich liter tekstu jawnego. Utworzony przez znaki kształt powinien przypominać zygzak.

R1VQovVYDGpim

Ilustracja przedstawia tabelę w kształcie płotu, gdzie każda deska podzielona jest na pięć części a na samej górze każdej deski znajduje się trójkąt .
W komórkach tabeli umieszczono napis: FONTANNA W PARKU.
Litery te umieszczone są w komórkach tworząc zygzaka.

Kolejne litery odczytujemy w wierszach, zaczynając zawsze od lewej strony. W ten sposób otrzymamy następujący zaszyfrowany tekst:

FWOAPNNATNRUAK

Aby twój przyjaciel mógł odczytać informację, należy przekazać mu zaszyfrowaną wiadomość wraz z kluczem symetrycznym.

Pseudokod algorytmu szyfrowania płotkowego

Specyfikacja problemu:

Dane:

• n – liczba naturalna; liczba znaków w tekście jawnym

• tekst[0..n - 1] – przekazany do zaszyfrowania szyfrem płotkowym tekst jawny; tablica znaków zawierająca wielkie i małe litery alfabetu angielskiego oraz spacje

• klucz – liczba rzędów, z których składa się wykorzystywany w szyfrowaniu schemat płotku; liczba naturalna dodatnia.

Wynik:

• szyfrogram[0..m - 1] – zaszyfrowany szyfrem płotkowym tekst jawny; tablica znaków zawierająca wielkie litery alfabetu angielskiego; gdzie m jest równe n minus liczba spacji w tekście jawnym

Do funkcji szyfrującej przekazywany jest podany przez użytkownika tekst jawny, liczba znaków w nim zawarta oraz klucz. Postępujemy według przedstawionego schematu.

Krok 1. Usuń spacje i zmień małe litery na wielkie, jeżeli jest to konieczne.

W funkcji początkowo definiujemy tablicę jawny[] o długości n, która docelowo przechowywać będzie tekst jawny składający się jedynie z wielkich liter alfabetu angielskiego (po usunięciu spacji oraz zmianie małych liter na wielkie). Dodatkowo przydatne będzie utworzenie zmiennej a wskazującej na indeks elementu tablicy jawny[], do którego zapisywać będziemy znak tekstu jawnego. Inicjalizujemy ją wartością 1.

funkcja szyfrPlotkowy(tekst[0..n - 1], klucz)
	jawny[0..n - 1] ← wprowadzamy wiadomość do zaszyfrowania
	a ← 1

Każdy element tablicy tekst[] porównujemy ze znakiem „ „ (spacja). Jeżeli dany element nie jest spacją, to weryfikujemy, czy stanowi małą literę alfabetu poprzez sprawdzenie, czy jego kod ASCII jest większy lub równy kodowi litery „a”. Zasadność takiego porównania wynika z faktu, że małe litery w kodzie ASCII mają wartości od 97 do 122, a wielkie od 65 do 90. Jeżeli sprawdzany znak okaże się małą literą, pomniejszamy jego kod ASCII o 32 i zapisujemy do tablicy tekst[]. Jest to stała różnica pomiędzy kodami tej samej litery w wariancie wielkim i małym, np. „a” (97) oraz „A” (65), czyli 97 - 65 = 32. W ten sposób małe litery zostają zamienione na wielkie. Niezależnie, czy przeprowadzona została operacja zmiany wielkości litery, sprawdzany znak (o ile nie jest spacją) zapisujemy do elementu tablicy jawny[] o indeksie a. Na koniec inkrementujemy wartość zmiennej a.

funkcja szyfrPlotkowy(tekst[0..n - 1], klucz)
	jawny[0..n - 1] ← wprowadzamy wiadomość do zaszyfrowania
	a ← 1
    
	dla i = 0, 1, ..., n - 1 wykonuj:
		jeżeli tekst[i] ≠ ' ':
			jeżeli znakDoKodu(tekst[i]) >= znakDoKodu('a') wykonaj:
				tekst[i] ← kodDoZnaku(znakDoKodu(tekst[i]) - 32)
			jawny[a] ← tekst[i]
			a ← a + 1

Krok 2. Określ liczbę znaków w tekście jawnym po przeprowadzonych operacjach usuwania spacji oraz zmiany wielkości liter.

Długość tablicy jawny[] początkowo określiliśmy jako n, ponieważ jest to maksymalna liczba znaków, które może zawierać tekst jawny po usunięciu spacji (w przypadku gdy pierwotnie nie znajdowały się w nim żadne spacje). Może jednak dojść do sytuacji, że długość tekstu – po wykonaniu opisanych operacji – ulegnie zmianie. Aby określić liczbę liter w tablicy jawny[], sprawdzimy, ile z jej elementów posiada kod ASCII pomiędzy 65 (kod litery „A”) a 90 (kod litery „Z”). Poszukiwaną długość tekstu jawnego, po modyfikacjach, przechowywać będziemy w zmiennej m.

m ← 0
dla i = 0, 1, ..., n - 1 wykonuj:
	jeżeli znakDoKodu(jawny[i]) >= znakDoKodu('A') i znakDoKodu(jawny[i]) <= znakDoKodu('Z'):
		m ← m + 1

Krok 3. Umieść tekst jawny w tablicy dwuwymiarowej.

Tworzymy tablicę plotek[][] zawierającą liczbę wierszy równą kluczowi oraz składającą się z liczby kolumn równej wartości zmiennej m. Wypełniamy ją znakami spacji. Następnie uzupełniamy ją kolejnymi znakami tekstu jawnego w formie opisanego w szyfrze płotkowym zygzaka. Pomoże nam w tym flaga dol, która będzie zmieniać swoją wartość na 1 (gdy tekst będzie iść w dół) lub 0 (gdy tekst będzie iść do góry) – w zależności od tego, czy osiągnięta zostanie minimalna lub maksymalna wysokość tablicy plotek[][].

plotek[0..klucz - 1][0..m - 1]
wiersz ← 1
dol ← 1
    
dla i = 0, 1, ..., klucz - 1 wykonuj:
	dla j = 0, 1, ..., m - 1 wykonuj:
    	plotek[i][j] ← ' '
i ← 1
    
dopóki i <= m wykonuj:
	plotek[wiersz][i] ← jawny[i]
    i ← i + 1
        
    jeżeli wiersz = klucz:
        dol ← 0
    jeżeli wiersz = 1:
        dol ← 1    
    jeżeli dol = 1:
        wiersz ← wiersz + 1
    w przeciwnym razie:
        wiersz ← wiersz - 1

Krok 4. Odczytaj zaszyfrowaną wiadomość.

Na koniec definiujemy tablicę szyfrogram o długości m, a następnie zapisujemy do niej litery, którymi wypełniliśmy pola utworzonego płotku (według zasad szyfru płotkowego). Rezultat przedstawionych operacji zwracamy.

szyfrogram[0..m - 1]
b ← 1
    
dla i = 0, 1, ..., klucz - 1 wykonuj:
	dla j = 0, 1, ..., m - 1 wykonuj:
        jeżeli plotek[i][j] ≠ ' ':
            szyfrogram[b] ← plotek[i][j]
            b ← b + 1
                
zwróć szyfrogram[]

Krok 5. Gotowa funkcja zapisana w pseudokodzie.

funkcja szyfrPlotkowy(tekst[0..n - 1], klucz)
	jawny[0..n - 1] ← wprowadzamy wiadomość do zaszyfrowania
	a ← 1
    
	dla i = 0, 1, ..., n - 1 wykonuj:
		jeżeli tekst[i] ≠ ' ':
			jeżeli znakDoKodu(tekst[i]) >= znakDoKodu('a') wykonaj:
				tekst[i] ← kodDoZnaku(znakDoKodu(tekst[i]) - 32)
			jawny[a] ← tekst[i]
			a ← a + 1
    
m ← 0
dla i = 0, 1, ..., n - 1 wykonuj:
	jeżeli znakDoKodu(jawny[i]) >= znakDoKodu('A') i znakDoKodu(jawny[i]) <= znakDoKodu('Z'):
		m ← m + 1
    
plotek[0..klucz - 1][0..m - 1]
wiersz ← 1
dol ← 1
    
dla i = 0, 1, ..., klucz - 1 wykonuj:
	dla j = 0, 1, ..., m - 1 wykonuj:
    	plotek[i][j] ← ' '
i ← 1
    
dopóki i <= m wykonuj:
	plotek[wiersz][i] ← jawny[i]
    i ← i + 1
        
    jeżeli wiersz = klucz:
        dol ← 0
    jeżeli wiersz = 1:
        dol ← 1    
    jeżeli dol = 1:
        wiersz ← wiersz + 1
    w przeciwnym razie:
        wiersz ← wiersz - 1
            
szyfrogram[0..m - 1]
b ← 1
    
dla i = 0, 1, ..., klucz - 1 wykonuj:
	dla j = 0, 1, ..., m - 1 wykonuj:
        jeżeli plotek[i][j] ≠ ' ':
            szyfrogram[b] ← plotek[i][j]
            b ← b + 1
                
zwróć szyfrogram[]

Słownik