Zarys algorytmów kryptograficznych

Laboratorium: Algorytmy i struktury danych

Spis treści

1

Wstęp

1

2

Szyfry

2

2.1

Algorytmy i szyfry . . . . . . . . . . . . . . . . . . . . . . . .

2

2.2

Prosty algorytm XOR . . . . . . . . . . . . . . . . . . . . . .

3

2.3

Algorytm RSA . . . . . . . . . . . . . . . . . . . . . . . . . .

4

2.4

Przykład zastosowania algorytmu RSA . . . . . . . . . . . . .

5

3

Algorytm Euklidesa

6

4

Ćwiczenia do wykonania

6

1

Wstęp

Ćwiczenie ma na celu zapoznanie studentów z pojęciem kryptografii oraz kilkoma podstawowymi metodami szyfrowania. Szczególną uwagę zwraca się na implementację algorytmu RSA.

Aby wykonać ćwiczenie należy rozpocząć od następujących definicji: Kryptografią nazywamy sztukę zabezpieczania wiadomości, której przeci-wieństwem jest kryptoanaliza zajmująca się łamaniem szyfrów, tzn. od-czytywania wiadomości pomimo maskowania.

Tekst jawny oznaczamy literą P . może nim być ciąg bitów, plik tekstowy, ciąg próbek głosu lub cyfrowy obraz wideo. Dla komputerów P to po prostu dane binarne. tekst jawny może być przeznaczony do przesyłania lub do zapamiętania. W każdym przypadku P jest wiadomością do zaszyfrowania.

Szyfrogram oznaczamy literą C. Szyfrogram to również dane binarne, czasami o tej samej wielkości co P , czasami większe. (W przypadku połączenia szyfrowania z kompresją, wielkość C może być mniejsza od P . Jednakże za-stosowanie wyłącznie szyfrowania nie da takiego efektu). Funkcja szyfrująca 1

Edziała na P i w wyniku daje C:

E(P ) = C

(1)

W procesie odwrotnym, funkcja deszyfrująca D działa na C i daje w wyniku P :

D(C) = P

(2)

Celem szyfrowania i późniejszego deszyfrowania jest otrzymanie tekstu jawnego, dlatego też musi być spełniona następująca zależność:

D(E(P )) = P

(3)

2

Szyfry

2.1

Algorytmy i szyfry

Algorytm kryptograficzny, zwany również szyfrem (ang. cipher ), jest funkcją matematyczną użytą do szyfrowania i deszyfrowania. Do zaszyfrowania tekstu jawnego jest stosowany algorytm szyfrujący (ang. encryp-tion algorithm), a do deszyfrowania szyfrogramu –algorytm deszyfrujący (ang. decryption algorithm).

Jeżeli zabezpieczenie zastosowane w algorytmie jest oparte na utrzymaniu w tajemnicy istoty tego algorytmu, to mówimy o algorytmie ograniczonym (ang. restricted algorithm).

We wszystkich nowoczesnych algorytmach, dzięki zastosowaniu klucza (ozna-czanego literą k), jest zapewnione prawdziwe bezpieczeństwo. klucz może przyjąć jedną z wielu wartości (najkorzystniejsze są wartości bardzo duże).

żakres wartości, które może przyjąć klucz, nazywamy przestrzenią klucza (ang. keyspace).

Wartość klucza wpływa na funkcję szyfrującą i deszyfrującą. Funkcje te przyjmują wtedy postać:

Ek(P ) = C

(4)

Dk(C) = P

(5)

Jeżeli klucze szyfrujący i deszyfrujący są takie same, to

Dk(Ek(P )) = P

(6)

Opracowano również algorytmy, w których stosuje się pary kluczy: szyfrujący i deszyfrujący. Oznacza to, że klucz szyfrujący kE jest inny niż odpowiada-jący mu klucz deszyfrujący kD. W takim przypadku:

Ek (P ) = C

(7)

E

2

Dk (C) = P

(8)

D

Dk (E

(P )) = P

(9)

D

kE

Wśród wielu algorytmów kryptograficznych najczęściej stosowane są trzy:

• DES (ang. Data Encryption Standard) –obecnie najpopularniejszy komputerowy algorytm szyfrujący. Jest to standardowy algorytm szyfrujący rządu USA, został przyjęty przez armię USA do szyfrowania informacji „nie utajnionej, ale ważnej”. Jest to algorytm symetryczny, z tym samym kluczem używanym do szyfrowania i deszyfrowania.

• RSA (nazwa jest złożeniem pierwszych liter nazwisk autorów –Rivest, Shamir i Adleman) –najpopularniejszy algorytm z kluczem jawnym.

Może być zastosowany zarówno do szyfrowania, jak i do podpisów cyfrowych.

• DSA (ang. Digital Signature Algorithm), zastosowany w DSS –ang.

Digital Signature Standard inny niż RSA algorytm z kluczem jawnym, ale może być stosowany tylko do podpisów cyfrowych.

2.2

Prosty algorytm XOR

Jest to algorytm symetryczny. Szyfrogram jest wynikiem binarnego sumowa-nia modulo 2 tekstu jawnego z kluczem. Ten sam klucz może być stosowany do szyfrowania i deszyfrowania, ponieważ dwukrotne sumowanie modulo 2

tej samej wartości daje w wyniku tę wartość.

P ⊕ k = C

(10)

C ⊕ k = P

(11)

(P ⊕ k) ⊕ k = P

(12)

Stosowanie tego algorytmu nie daje żadnego bezpieczeństwa. teksty zaszyfrowane z wykorzystaniem tego algorytmu łatwo odczytać, nawet bez komputera. Użycie komputera umożliwia łamanie szyfru w ciągu kilku minut.

Szyfr XOR można złamać w następujący sposób:

1. Rozpoznanie długości klucza dokonuje się stosując procedurę zwaną zliczaniem koincydencji. polega ona na sumowaniu modulo 2 szyfrogramu z samym sobą dla kolejnych wzajemnych przesunięć i zli-czaniu jednakowych bajtów. Jeśli dwa fragmenty szyfrogramu były zaszyfrowane tym samym kluczem, to nieco ponad 6% bajtów będzie jednakowych. jeżeli były szyfrowane różnymi kluczami, to mniej niż 0, 4% będzie jednakowych (zakładając przypadkowy klucz do szyfrowania zwykłego tekstu ASCII; inne teksty jawne charakteryzują się innymi parametrami). Najmniejsze z przesunięć wskazujące na jednakową długość klucza jest długością klucza.

3

2. Cyklicznie przesunięcie szyfrogramu o długości klucza i sumowanie modulo 2 z szyfrogramem nie przesuniętym powoduje usunięcie klucza i daje tekst jawny zsumowany modulo 2 z przesuniętym tekstem jawnym. tekst angielski zawiera ok. jednego bita informacji na bajt, jest to nadmiarowość pozwalająca dokonać jednoznacznego deszyfrowania.

Pomimo łatwości złamania tego szyfru lista dostawców oprogramowania, których wmawia się klientom, iż ten typ algorytmu jest „prawie tak bez-pieczny jak DES”, jest oszałamiająca. W ten sposób można uchronić swój plik przed młodszą siostrą, ale na pewno nie uchroni się go przed krypto-grafem na dłużej niż kilka minut.

2.3

Algorytm RSA

Nazwany od nazwisk trzech jego odkrywców, Rona Rivesta, Adi Shamira i Leonarda Adelmana, którzy pierwsi wprowadzili algorytm w 1978 r., wytrzy-mał od tego czasu lata intensywnej kryptoanalizy. Chociaż kryptoanaliza ani nie udowodniła, ani nie zdyskwalifikowała bezpieczeństwa algorytmu RSA, jednak sugeruje poziom zaufania w teoretycznych ocenach algorytmu.

Zabezpieczenie dawane przez RSA wynika z trudności faktoryzacji dużych liczb. Klucze jawne i prywatne są funkcjami pary dużych (100 do 200 cyfr lub nawet dłuższych) liczb pierwszych. Przypuszcza się, że uzyskanie tekstu jawnego przy znajomości jednego z tych kluczy i szyfrogramu jest równo-ważne faktoryzacji iloczynu tych dwóch liczb pierwszych.

Kroki potrzebne do zaszyfrowania i odszyfrowania tekstu jawnego można przedstawić następująco:

1. Wybieramy dwie duże liczby pierwsze p i q (czym więcej cyfr w każdej z nich tym lepiej).

2. Wyznaczamy iloczyn n

n = pq

(13)

3. Losowo wybieramy klucz szyfrujący (najlepiej liczbę pierwszą) e.

4. Korzystając z algorytmu Euklidesa wyznaczamy klucz deszyfrujący d d = e−1

mod ((p − 1)(q − 1))

(14)

5. Dzielimy informację na bloki o rozmiarze s gdzie dla danych w postaci binarnej wybieramy największą potęgę 2 mniejszą od n. Oznacza to, że jeżeli p i q są liczbami pierwszymi o 100 cyfrach to ich iloczyn n będzie miał mniej niż 200, a każdy blok wiadomości mi powinien mieć długość s mniejszą od 200. Zaszyfrowana wiadomość c będzie utworzona z bloków ci, o podobnych długościach.

6. Poszczególne bloki szyfrujemy zgodnie ze wzorem:

ci = mei mod n

(15)

4

7. W celu odszyfrowania wiadomości, bierzemy każdy zaszyfrowany blok ci i obliczamy :

mi = cdi mod n

(16)

2.4

Przykład zastosowania algorytmu RSA

Jeżeli p = 47 i q = 71, to

n = pq = 3337

Klucz szyfrujący e nie może mieć wspólnych czynników z:

(p − 1)(q − 1) = 46 · 70 = 3220

Losowo wybierając liczbę e o wartości 79. W tym przypadku

d = 79−1

mod 3220 = 1019

Liczba ta była obliczona przy wykorzystaniu rozszerzonego algorytmu Euklidesa. Liczby e i n publikujemy, natomiast d utajniamy. Liczby p i q wy-mazujemy.

W celu zaszyfrowania wiadomości

m = 6882326879666683

najpierw dzielimy ją na małe bloki. Trzycyfrowe bloki będą tutaj najlepsze.

Wiadomość będzie zaszyfrowana w sześciu blokach mi, równych:

i

Wartość

1

688

2

232

3

687

4

966

5

668

6

3

Pierwszy blok jest zaszyfrowany jako

68879

mod 3337 = 1570 = c1

Po wykonaniu tych samych operacji na kolejnych blokach otrzymujemy zaszyfrowaną wiadomość

c = 15702756209122762423158

Odszyfrowanie wiadomości wymaga wykonania tego samego potęgowania przy użyciu klucza deszyfrującego o wartości 1019. Tak więc

15701019

mod 3337 = 688 = m1

Pozostała część wiadomości może być odzyskana w ten sam sposób.

5

3

Algorytm Euklidesa

Algorytm Euklidesa służy do wyznaczania największego wspólnego dzielnika dwóch liczb a i b.

Wyznaczenie największego wspólnego dzielnika odbywa się według następu-jącego algorytmu:

1. Wyznacz resztę r z dzielenia liczby a przez liczbę b.

2. Podstaw b za a.

3. Podstaw r za b.

4. Jeśli reszta z dzielenia r jest niezerowa wykonaj ponownie od kroku 1.

W przeciwnym przypadku a jest największym wspólnym dzielnikiem.

4

Ćwiczenia do wykonania

1. Utworzyć schemat blokowy i zaimplementować program dokonujący szyfrowania i deszyfrowania prostym algorytmem XOR.

2. Wykonać kryptoanalizę wcześniej wygenerowanych przy pomocy pro-stego algorytmu XOR szyfrogramów.

3. Utworzyć schemat blokowy i zaimplementować program dokonujący szyfrowania i deszyfrowania prostym algorytmem RSA.

4. Sprawozdanie powinno zawierać:

• Schematy blokowe.

• Listingi najważniejszych partii programu.

• Wyniki testów (teksty jawne, szyfrogramy, klucze, itp.).

Bibliografia

[1] Bruce Schneier: Kryptografia dla praktyków – protokoły, algrytmy i pro-gramy źródłowe w języku C, Wydawnictwa Naukowo-Techniczne, War-szawa, 1995.

6