Ostatnio omówiliśmy podstawowe pojęcia, a mianowicie definicję kryptografii, kryptologiii. Powiedzieliśmy też o komunikacji między dwiema stronami, gdzie istnieje strona A, strona B, oraz bierny przeciwnik, który monitoruje i podsłuchuje przesyłanie informacji. Omówiliśmy też definicję kryptosystemu. I powiedzieliśmy o kryptosystemach symetrycznych, czyli kryptosystemach tajnego klucza, gdzie ta rodzina przekształceń (algorytm) jest znany, natomiast jego bezpieczeństwo opiera się na tajności klucza używanego do szyfrowania i deszyfrowania. To, że ta rodzina jest jawna, to przyjmujemy tak zwaną zasadę Kerckhoffsa. Warunkiem koniecznym bezpieczeństwa takiego kryptosystemu jest, żeby atakujący nie mógł dokonać ataku brutalnego. Mówiliśmy też o szyfrze Cezara - najprostszym. Szyfr Cezara jest przykładem szyfrowania przesuwającego i my o tym mówiliśmy, natomiast dziś powiemy o tej metodzie nieco więcej. W szyfrze przesuwającym szyfrowanie polega na przesunięciu cyklicznym alfabetu o k pozycji w prawo, gdzie k to klucz wyznaczający o ile ma być przesunięty tekst. Jak nie trudno się domyśleć deszyfrowanie będize tu polegało na przesunięcu cyklicznym o k pozycji w lewo. Szyfr przesuwający opiera się więc o arytmetykę modularną i wygląda to tak, że litery alfabetu numerujemy (kodujemy) liczbami mod 26 w nastepujący sposób:

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

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Szyfrowanie kluczem
zapiszemy wówczas wzorem
, zaś deszyfrowanie wzorem
. I jednym z przykładów takiego szyfru jest własnie szyfr Cezara. Szyfr przesuwający jest rodzajem szyfru podstawieniowego. Ogólny schemat takiego szyfrowania podstawieniowego wygląda z kolei nastepująco. Przyjmijmy za A dowolny alfabet n - znakowy, oraz przyjmijmy, że A = P = C. Niech przestrzenia klucza K będzie zbiór wszystkich permutacji alfabetu A, gdzie liczba wszystkich kluczy wynosić będzie n! Przykładowo dla alfabetu 26 znakowego:
. Dla wybranego klucza (permutacji) k:
. Tekst jawny x = 1, …, l zastepujemy szyfrogramem
, gdzie l jest długością tekstu jawnego. Szyfr podstawieniowy może być stosowany do dowolnego alfabetu (przykładowo A może być zbiorem wszystkich ciągów ośmiobitowych). Szyfr podstawieniowy jest szyfrem monoalfabetycznym, co znaczy, że przy ustalonym kluczu dany znak alfabetu jest jednakowo przekształcany niezależnie od jego położenia w tekście jawnym. Szyfry przestawieniowe z kolei reprezentują również klasyczne metody szyfrowania i charakteryzują się tym, że w zaszyfrowanym tekście występują wszystkie znaki z tekstu jawnego, ale w innej kolejności. Szyfry należące do tej grupy (jak na przykład szyfr płotkowy) zmieniają kolejność liter w szyfrowanym tekście według określonego schematu. Najczęściej przestawienia liter dokonuje się za pomocą figury geometrycznej. Najprostszym przykładem szyfru przestawieniowego jest pisanie wspak. S P O D E K -> K E D O P S. Szyfry przestawieniowe są łatwe do złamania i nie zapewniają żadnego bezpieczeństwa. Łamie się je metodą słów prawdopodobnych. Dopasowanie fragmentu znanego (lub odszyfrowanego) tekstu do szyfru pozwala na znalezienie zasady przestawiania. Innym sposobem jest wykorzystanie znajomości zasad tworzenia wiadomości - jednakowe szablony dokumentów szyfrowanych, często spotykane zwroty, nagłówki, podpisy czy stopki wiadomości. Wykorzystuje się też błędy i przyzwyczajenia osób posługujących się tą metodą szfyrowania. Metoda statystyczna jest raczej nieprzydatna ponieważ rozkład statystyczny liter wiadomości nie zmienia się po przestawieniu liter w innej kolejności. Taki prosty szyfr przestawieniowy wykorzystywał przyrząd scytale wyglądający mniejwięcej tak:

Na wałek tak własnie zwany nakładało się pasek z ukrytym tekstem, którego zupełnie nie można było odczytać. Był to niby przypadkowy ciąg znaków, ale tak opracowany, że po nawinięciu takiego paska na wałek można było odczytać poziomo ukrytą informację. Istnieją inne metody szyfrowania prócz tych, które wymieniliśmy. W niektórych metodach wykorzystywana jest analiza częstościowa. Bardzo często zadawano bowiem pytanie, czy prosty szyfr podstawieniowy jest bezpieczny mimo dużej przestrzeni klucza. Otóż nie i dlatego zastosowano tą właśnie metodę. Jak wiadomo każdy język natoralny ma nadmiarowość - w naturalnych tekstach poszczególne znaki alfabetu występuja z określonymi częstościami. Analizując typowe teksty możemy sporządzić tabelę względnych częstości (prawdopodobieństw) wystepowania poszczególnych znaków. I tak sporządza się tabelę występowania znaków w szyfrogramie (dla niezależnego, ale ustalonego podstawienia). Na tej podstawie stawia się hipotezę, jak wygląda nieznane nam podstawienie i deszyfrujemy. Przy posiadaniu odpowiednio długiego szyfrogramu i wykonaniu prób przy różnych podstawieniach, metoda ta pozwala złamać prosty szyfr podstawieniowy. Przykładem takiego szyfru opartego na czestościach jest szyfr Vigenere'a. Algorytm Vigenère'a jest jednym z klasycznych algorytmów szyfrujących. Należy on do grupy wieloalfabetowych szyfrów podstawieniowych. Szyfr ten błędnie został przypisany twórcy bardziej skomplikowanego szyfru Blaise'owi de Vigenère. Działanie szyfru Vigenere'a oparte jest na następującej tablicy:

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

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 A

C 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

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

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 D

F G H I J K L M N O P Q R S T U V W X Y Z A B C D E

G H I J K L M N O P Q R S T U V W X Y Z A B C D E F

H I J K L M N O P Q R S T U V W X Y Z A B C D E F G

I J K L M N O P Q R S T U V W X Y Z A B C D E F G H

J K L M N O P Q R S T U V W X Y Z A B C D E F G H I

K L M N O P Q R S T U V W X Y Z A B C D E F G H I J

L M N O P Q R S T U V W X Y Z A B C D E F G H I J K

M N O P Q R S T U V W X Y Z A B C D E F G H I J K L

N O P Q R S T U V W X Y Z A B C D E F G H I J K L M

O P Q R S T U V W X Y Z A B C D E F G H I J K L M N

P Q R S T U V W X Y Z A B C D E F G H I J K L M N O

Q R S T U V W X Y Z A B C D E F G H I J K L M N O P

R S T U V W X Y Z A B C D E F G H I J K L M N O P Q

S T U V W X Y Z A B C D E F G H I J K L M N O P Q R

T U V W X Y Z A B C D E F G H I J K L M N O P Q R S

U V W X Y Z A B C D E F G H I J K L M N O P Q R S T

V W X Y Z A B C D E F G H I J K L M N O P Q R S T U

W 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

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

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 X

Z 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

Jak można zauważyć, każdy z wierszy tablicy odpowiada szyfrowi Cezara, przy czym w pierwszym wierszu przesunięcie wynosi 0, w drugim 1 i tak dalej. Aby zaszyfrować pewien tekst, potrzebne jest słowo kluczowe. Słowo kluczowe jest tajne i mówi, z którego wiersza (lub kolumny) należy w danym momencie skorzystać. Przypuśćmy, że chcemy zaszyfrować prosty tekst: TO JEST BARDZO TAJNY TEKST. Do tego celu użyjemy znanego tylko nam słowa kluczowego - przykładowo: TAJNE Na początku zauważamy, że użyte słowo kluczowe jest zbyt krótkie, by wystarczyło do zaszyfrowania całego tekstu, więc należy użyć jego wielokrotności. Będzie to miało następującą postać:

TO JEST BARDZO TAJNY TEKST

TA JNET AJNETA JNETA JNETA

Następnie wykonujemy szyfrowanie w następujący sposób: Litera szyfrogramu odpowiada literze z tabeli znajdującej się na przecięciu wiersza, wyznaczanego przez literę tekstu jawnego i kolumny wyznaczanej przez literę słowa kluczowego, np. po kolei T i T daje M, O i A daje O itd. W efekcie otrzymujemy zaszyfrowany tekst:

MO SRWM BJEHSO CNNGY CROLT

Warto zauważyć, że tak naprawdę nie ma znaczenia, czy litera tekstu jawnego będzie wyznaczała wiersz, a słowa kluczowego kolumnę, czy na odwrót, efekt szyfrowania będzie zawsze taki sam. Odszyfrowywanie przebiega bardzo podobnie. Bierzemy kolejne litery szyfrogramu oraz odpowiadające im litery słowa kluczowego (podobnie, jak przy szyfrowaniu). Wybieramy kolumnę odpowiadającą literze słowa kluczowego. Następnie w tej kolumnie szukamy litery szyfrogramu. Numer wiersza odpowiadający znalezionej literze jest numerem litery tekstu jawnego. Np. w kolumnie T litera M znajduje się w wierszu T, w kolumnie A litera O znajduje się w wierszu O i tak dalej. Istnieje jednakże prostszy, szczególnie dla celów implementacyjnych, sposób deszyfrowania. Wymaga on wykonania prostej operacji odwrócenia hasła, jak poniżej:

K2(i) = [26 - K(i)] mod 26

gdzie K(i) to kolejne litery słowa kluczowego, numerowane A = 0, B = 1 itak dalej, a K2(i) to kolejne litery hasła odwróconego. 26 oznacza liczbę liter alfabetu łacińskiego.Efektem działania takiego przekształcenia dla hasła TAJNE będzie słowo HARNW. Następnie należy na szyfrogramie wykonać operację szyfrowania z otrzymanym hasłem. Wynikiem, jak można się przekonać, będzie postać jawna tekstu. Oryginalny szyfr Vigenère'a używał autoklucza, pierwsza litera klucza była ustalana, a kolejnymi literami były kolejne litery tekstu jawnego.

Niech naszą literą szyfrującą, będzie N

tekst jawny: TO JEST BARDZO TAJNY TEKST

klucz: NT OJES TBARDZ OTAJN YTEKS

tekst zaszyfrowany: GH XNWL UBRUCN HTJWL RXOCL

Odszyfrowanie przebiega w następujący sposób, pierwszą literę szyfrogramu, odszyfrowywujemy ustaloną literą (N), kolejne litery, dopiero co odszyfrowanymi literami:

G N -> T
H T -> O
X O -> J
...

szyfrogram: G H X N W L ...

klucz: N T O J E S ...

tekst odszyfrowany: T O J E S T ...

Szyfr ten ze względu na to, że długość klucza była równa długości tekstu jawnego opierał się analizie statystycznej (częstościowej). Kolejny ciekawy szyfr to takzwany szyfr Vernama. Jest to szyfr z kluczem jednokrotnym. Tutaj klucz ma długość tekstu jawnego, jest losowym ciągiem znaków, oraz jest stosowany tylko raz (warunki te ograniczają stosowalność szyfru Vernama). Szyfr ten uzywany jest głównie w wojsku, dyplomacji i tajnych służbach. Oto jak wygląda realizacja binarna:

Tekst jawny:

Klucz:

Szyfrogram:
, gdzie

Deszyfrowanie:

Szyfr ten jest bardzo dobrym szyfrem i jest bezpieczny, co wynika z twierdzenia Shannona. Mówi ono, że szyfr z kluczem jednokrotnym jest absolutnie bezpieczny i jest to tak zwany szyfr idealny. Pod pojęciem szyfru idealnego rozumie się nastepującą równość: Prawdopodobieństwo z (m|c), gdzie m to wiadomość, a c - szyfrogram równe jest prawdopodobieństwu z m. Dzięki temu znajomość szyfrogramu nie daje żadnych informacji o tekście jawnym. Na zakończenie zajęć powiemy sobie o rodzajach bezpieczeństwa. Wyróżniamy dwa rodzaje bezpieczeństwa: bezwarunkowe i warunkowe. Bezpieczeństwo bezwarunkowe polega na tym, że nie można złamać szyfru niezależnie od posiadanych mocy obliczeniowych. Warunkowe polega na tym, że atakujący dysponuje ograniczoną mocą obliczeniową, a bezpieczeństwo szyfru oparte jest na aktualnej wiedzy i stanie technologii. Szyfr Vernama jest bezwarukowo bezpieczny.

---