kryptogr.pdf

Zarys algorytmów kryptogracznych

Laboratorium: Algorytmy i struktury danych

Spis tre±ci

1 Wst¦p

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

4 wiczenia do wykonania

1 Wst¦p

wiczenie ma na celu zapoznanie studentów z poj¦ciem kryptograi oraz

kilkoma podstawowymi metodami szyfrowania. Szczególn¡ uwag¦ zwraca

si¦ na implementacj¦ algorytmu RSA.

Aby wykona¢ ¢wiczenie nale»y rozpocz¡¢ od nast¦puj¡cych denicji:

Kryptogra¡ 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, cza-

sami 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

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

D(C) = P

(2)

Celem szyfrowania i pó¹niejszego deszyfrowania jest otrzymanie tekstu jaw-

nego, dlatego te» musi by¢ speªniona nast¦puj¡ca zale»no±¢:

D(E(P)) = P

(3)

2 Szyfry

2.1 Algorytmy i szyfry

Algorytm kryptograczny, zwany równie» szyfrem (ang. cipher ), jest

funkcj¡ matematyczn¡ u»yt¡ do szyfrowania i deszyfrowania. Do zaszyfro-

wania 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¢:

E k (P) = C

(4)

D k (C) = P

(5)

Je»eli klucze szyfruj¡cy i deszyfruj¡cy s¡ takie same, to

D k (E k (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 k E jest inny ni» odpowiada-

j¡cy mu klucz deszyfruj¡cy k D . W takim przypadku:

E k E (P) = C

(7)

D k D (C) = P

(8)

D k D (E k E (P)) = P

(9)

W±ród wielu algorytmów kryptogracznych najcz¦±ciej stosowane s¡ trzy:

DES (ang. Data Encryption Standard ) {obecnie najpopularniejszy

komputerowy algorytm szyfruj¡cy. Jest to standardowy algorytm szy-

fruj¡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 zaszy-

frowane z wykorzystaniem tego algorytmu ªatwo odczyta¢, nawet bez kom-

putera. 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 szy-

frogramu 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 szyfro-

wania zwykªego tekstu ASCII; inne teksty jawne charakteryzuj¡ si¦

innymi parametrami). Najmniejsze z przesuni¦¢ wskazuj¡ce na jedna-

kow¡ dªugo±¢ klucza jest dªugo±ci¡ klucza.

2. Cyklicznie przesuni¦cie szyfrogramu o dªugo±ci klucza i sumowanie mo-

dulo 2 z szyfrogramem nie przesuni¦tym powoduje usuni¦cie klucza i

daje tekst jawny zsumowany modulo 2 z przesuni¦tym tekstem jaw-

nym. 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 zdyskwalikowaª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 m i powinien

mie¢ dªugo±¢ s mniejsz¡ od 200. Zaszyfrowana wiadomo±¢ c b¦dzie

utworzona z bloków c i , o podobnych dªugo±ciach.

6. Poszczególne bloki szyfrujemy zgodnie ze wzorem:

c i = m i mod n

(15)

7. W celu odszyfrowania wiadomo±ci, bierzemy ka»dy zaszyfrowany blok

c i i obliczamy :

m i = c i 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 Eu-

klidesa. 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 m i , równych:

i Warto±¢

688

232

687

966

668

Pierwszy blok jest zaszyfrowany jako

688 79

mod 3337 = 1570 = c 1

Po wykonaniu tych samych operacji na kolejnych blokach otrzymujemy za-

szyfrowan¡ 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

1570 1019

mod 3337 = 688 = m 1

Pozostaªa cz¦±¢ wiadomo±ci mo»e by¢ odzyskana w ten sam sposób.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: