Ćwiczenie nr 8

Podstawy kryptologii

CEL ĆWICZENIA

Celem ćwiczenia jest zapoznanie z zagadnieniami związanymi z ochroną danych na bazie kryptologii. Zakres kryptologii obejmuje zagadnienia takie jak utajnienie (informacji nie można odczytać bez klucza), uwierzytelnienie (strona wysyłająca może udowodnić swoją tożsamość) niezaprzeczalność (strona odbierająca może udowodnić tożsamość autora informacji) oraz spójność (pewność, że informacja nie została zmieniona).

W trakcie ćwiczenia student zapozna się z podstawami działania algorytmu RSA oraz dokona próby „złamania” bardzo prostego i słabo zabezpieczonego komunikatu z wykorzystaniem prostych narzędzi.

WSTĘP TEORETYCZNY

W najogólniejszym ujęciu kryptologia jest dziedziną wiedzy obejmującą zagadnienia związane z ukrywaniem wiadomości (danych) przed nieupoważnionymi podmiotami przy pomocy ich przekształcania (szyfrowania) do postaci wiadomości "niezrozumiałych" i ich odtwarzaniem (deszyfrowaniem) przez podmioty upoważnione (kryptografia) lub nieupoważnione (kryptoanaliza). Wiadomość poddawana szyfrowaniu nosi nazwę wiadomości jawnej, zaś po zaszyfrowaniu przyjmuje postać tzw. wiadomości zaszyfrowanej (szyfrogramu). Procesy szyfrowania i deszyfrowania określone są przez odpowiednie przekształcenia matematyczne - algorytmy kryptograficzne, którym poddawane są liczby lub ciągi liczb, odpowiadające wiadomości jawnej lub zaszyfrowanej. Zazwyczaj sama formuła przekształcenia szyfrującego (i deszyfrującego) jest powszechnie znana, zaś o skuteczności "utajniania" wiadomości lub jej odtwarzania decyduje dodatkowy parametr przekształcenia, zwany kluczem, znany jedynie podmiotom upoważnionym. System, w którym dokonuje się szyfrowania i deszyfrowania wiadomości, nosi nazwę systemu kryptograficznego.

Algorytm szyfrujący RSA (Rivesta-Shamira-Adlemana)

Dawniej stosowane powszechnie algorytmy należały do rodziny symetrycznych - zarówno do szyfrowania, jak i odczytywania wiadomości korzystają z tego samego klucza. Wadą algorytmów symetrycznych jest to, że każda para komunikujących się osób wymaga innego klucza, stąd grupa N osób musi posługiwać się N*(N-1)/2 liczbą kluczy, co stwarza problem z ich bezpiecznym przechowywaniem.

Szyfrowanie asymetryczne wykorzystuje dwa różne klucze - prywatny i publiczny. Klucz publiczny używany jest do szyfrowania, a prywatny - do odczytania informacji. Ponieważ za pomocą klucza publicznego nie można odszyfrować żadnej wiadomości, nie jest konieczne utrzymywanie go w tajemnicy. Zabezpieczenia algorytmów asymetrycznych umożliwiają ujawnienie klucza publicznego, którego znajomość nie wystarcza do odtworzenia klucza prywatnego.

Podstawy matematyczne

Weźmy dwie możliwie duże liczby pierwsze p i q. Niech n=p*q, a k=(p-1)*(q-1). Wybieramy dowolną liczbę e, względnie pierwszą z k (czyli taką, że największym wspólnym dzielnikiem (NWD) liczb e i k jest jeden).

Para liczb e i n stanowi klucz publiczny. Na ich podstawie należy obliczyć klucz prywatny. Jest on parą liczb d i n, gdzie liczba d spełnia równanie:

(d * e) mod k = 1

Jak widać, do znalezienia d konieczna jest znajomość k - samo n zawarte w kluczu publicznym nie wystarczy. Z kolei, aby poznać k, trzeba znać p i q - zaś ich uzyskanie przez rozłożenie liczby n na czynniki pierwsze jest niezwykle czasochłonne.

Matematyczne rozwiązanie równania na obliczenie d jest problemem o trudności wzrastającej wykładniczo, gdyż wymaga rozłożenia k na czynniki pierwsze.

Jak więc można obliczyć klucz prywatny?

Należy zastosować Rozszerzony Algorytm Euklidesa, który służy w podstawowej wersji do znajdowania największego wspólnego dzielnika dwóch liczb.

Rozważmy przykład: Niech k=480, e=11. Interesuje nas ich NWD. Dzielimy liczbę k przez e i otrzymujemy:

480 = 43 * 11 + 7. (1)

Teraz dzielimy 11 przez 7 i kontynuujemy, podobnie dzieląc przez siebie dwie kolejne reszty z dzielenia:

11 = 1 * 7 + 4 (2)

7 = 1 * 4 + 3 (3)

4 = 1 * 3 + 1 (4)

3 = 3 * 1 + 0 (5)

aż do natrafienia na zerową resztę (ostatnie równanie 5 ignorujemy). Poprzednia reszta jest poszukiwanym NWD - w tym przypadku jest to 1, czyli 480 i 11 są względnie pierwsze (k i e powinny być względnie pierwsze). Teraz jednak pójdziemy w przeciwną stronę algorytmu, zapisując jedynkę jako:

1 = 4 - 1 * 3 (z równania 4)

Wstawiamy zamiast trójki zapis z równania (3):

1 = 4 - 1 * (7 - 1 * 4), po uporządkowaniu otrzymamy:

1 = 2 * 4 - 1 * 7

Teraz zastępujemy czwórkę wyrażeniem z równania (2) i otrzymujemy:

1 = 2 * (11 - 1 * 7) - 1 * 7, po uporządkowaniu:

1 = 2 * 11 - 3 * 7

Po zastąpieniu siódemki wyrażeniem z równania (1) i otrzymujemy:

1 = 2 * 11 - 3 * (480 - 43 * 11), i porządkując dostajemy ostatecznie:

1 = 131 * 11 - 3 * 480

W ten sposób zapisaliśmy jeden jako kombinację liniową liczb 11 i 480. To jest właśnie celem Rozszerzonego Algorytmu Euklidesa.

Obliczając resztę z dzielenia prawej strony przez 480, otrzymamy 131*11.
Widać więc, że równanie (d*e) mod k = 1 jest spełnione dla d=131.

Jak należy wykorzystać oba klucze?

Jeżeli informacją do zakodowania jest liczba P, to jej zakodowana wartość E jest równa:

(P^e) mod n = E

Z kolei przy odkodowywaniu wykorzystujemy wartości d i n:

(E^d) mod n = P

Ważną cechą tego algorytmu jest jego odwracalność - możemy zakodować informację przy użyciu liczby d, a następnie odkodować ją, używając liczby e. Tak właśnie tworzy się podpisy cyfrowe.

PRZEBIEG ĆWICZENIA

W powyższym przykładzie ustalono wartości k=480, d=131, e=11.

Jak widać z zamieszczonych powyżej zależności do poprawnego odkodowania lub zakodowania informacji potrzebna jest jeszcze znajomość wartości n, gdzie n=p*q, gdzie p i q to liczby pierwsze. (pamiętać też należy, że jednocześnie k=(p-1)*(q-1))

Należy wyznaczyć wartość n, a następnie (korzystając z kalkulatora systemowego) odkodować szyfrogram w postaci sekwencji liczb E={119,301,128,503,266,392} korzystając z wyznaczonego klucza prywatnego. Odszyfrowane wartości zamienione z pomocą tablicy kodów ASCII na litery dadzą jednowyrazowe rozwiązanie.

UWAGA 1: Przy rozwiązywaniu problemu pomocny może okazać się system Matlab ( w szczególności polecenie primes(największa_liczba_pierwsza)) - choć korzystanie z systemu jest opcjonalne. Ogólnie: dobór narzędzi i metod rozwiązania problemu jest też celem niniejszego ćwiczenia - wykorzystać można dowolne dostępne w laboratorium narzędzie/narzędzia nie wyłączając kartki papieru i długopisu …

UWAGA 2: po odszyfrowaniu obliczone liczby dziesiętne, które zostaną wyświetlone w oknie kalkulatora zamienić należy na litery posługując się tablicą kodów ASCII. Można w tym celu wykorzystać funkcję arkusza kalkulacyjnego =znak(liczba). Tak odczytana sekwencja liter ułoży się w wyraz - tylko w jednym przypadku (dla każdej możliwej wartości n powstanie inne rozwiązanie) uzyskany ciąg będzie sensowny a więc stanowić będzie rozwiązanie, czyli komunikat nadany.

UWAGA 3: przy posługiwaniu się standardowymi programami takimi jak kalkulator systemowy należy pamiętać o ich ograniczeniach co do precyzji wyznaczania liczby. Programy stosujące klasyczną reprezentację maszynową liczb są ograniczone co do precyzji reprezentacji dużych liczb całkowitych. W powyższym zadaniu z zależności (E^d) mod n = P

wynika konieczność obliczenia np. wartości 149¹³¹ co daje w efekcie liczbę na kalkulatorze:

4,868567123005312663063603634689e+284

podczas gdy jej pełne rozwinięcie to:

486856712300531266306360363468884321113831334403394762508437532395733864226994920620441794963368361054685067107168030945327611050970943683673965176828103497996655036036564043671846832587470405493847650627933218046595126769265340874404710734402303465862085117822025856476697876547807149

Z tego m.in. powodu do obliczeń nie da się wykorzystać arkusza kalkulacyjnego Excel (można zrealizować jedynie operacje pomocnicze takie jak poszukiwanie p i q)

Kalkulator systemowy pamięta pełne rozwinięcie i wartość modulo liczy od właściwej wartości - nie jest to jednak zasadą w większości programów obliczeniowych. Oczywiście do celów kryptologii wykorzystuje się programy dedykowane, dla których operacje przedstawione tutaj nie stanowią żadnego problemu. (Swoją drogą przykład tu przedstawiony jest wariantem sztucznym - w zastosowaniach rzeczywistych nikt nie wykorzystuje tak małych liczb pierwszych !)

UWAGA 4: Kalkulatory systemowe różnych wersji systemu Windows różnią się między sobą kilkoma szczegółami np. nie pamiętają wyników obliczeń z pełną precyzją i nie posiadają wbudowanej funkcji MOD (reszta z dzielenia). W wersji systemu XP Professional dostępnej w laboratorium wspomniana funkcjonalność jest dostępna.

SPRAWOZDANIE

Sprawozdanie z realizacji ćwiczenia powinno zawierać kompletny opis przebiegu procesu ustalania wartości n (opis metody) oraz odkodowania szyfrogramu wraz z wnioskami (niejednoznaczność nawet w przypadku tak prostego komunikatu i szyfru) - sprawozdanie musi mieć formę „papierową” (wydruk, sprawozdanie odręczne)

LITERATURA

1. Niels Ferguson, Bruce Schneier, Kryptografia w praktyce, Helion 2004

2. Marcin Karbowski, Podstawy kryptografii, Helion 2005

3. Strony internetowe poświęcone zagadnieniom kryptologii

POLITECHNIKA POZNAŃSKA	KIERUNEK: LogTr		SEMESTR VI
		LABORATORIUM - SYSTEMY INFORMACYJNO-INFORMATYCZNE

3

opracowanie ćwiczenia - dr inż. Waldemar Walerjańczyk

---