Автор неизвестен - Algorytm kryptograficzny rsa schemat i opis algorytmu procedura szyfrowania i odszyfrowania aspekty bezpieczenstwa stosowanie - страница 1

Страницы:
1 

Wyklad 2

Temat: Algorytm kryptograficzny RSA: schemat i opis algorytmu, procedura szyfrowania i odszyfrowania, aspekty bezpieczenstwa, stosowanie

RSA jest algorytmem z kluczem publicznym i zostat opracowany przez Ronalda Rivesta, Adi Shamira i Leonarda Adlemana, od inicjatow ktorych pochodzi jego nazwa tworcow. Algorytm ten jest chroniony patentem USA numer 4405892 („System i metoda komunikacji kryptograficznej"). Wniosek zostat zgtoszony 14 grudnia 1977 roku, zas patent wygast 20 wrzesnia 2000 roku. Metody tej mozna by to jednak uzywac bezptatnie poza obszarem USA, gdyz algorytm zostat opublikowany wczesniej, niz ztozono wniosek.

Algorytm RSA moze byc uzywany do szyfrowania danych, jak i podpisow cyfrowych. Moc algorytmu wynika z trudnosci roztozenia duzej liczby na czynniki pierwsze, czyli faktoryzacji duzych liczb oraz obliczania logarytmow dyskretnych.

Schemat blokowy algorytmu RSA przedstawiony jest na rys. 2.1.

Klucze publiczny (jest to para liczb (e, n) jawna dla kazdego, nadawcy wiadomosci, wedtug ktorego szyfrowana jest wiadomosc) i tajny (liczba d znana tylko wtascicielowi i umozliwia rozszyfrowanie otrzymanej wiadomosci wedtug klucza publicznego), wiadomosc m i kryptogram c sa_ wyrazony w postaci liczb nalezaxcych do zbioru liczb catkowitych

Zn = {0,1, 2,..., n-1}, (2.1)

gdzie

n = p q, (2.2)

przy czymp i q - losowe duze liczby pierwsze.

Generator klucza Losowanie p, q i e

n = p q

f(n) = (p - 1)(q -1)

e d = 1 mod (<p(n))

Klucz publiczny Klucz tajny d;

(e, n) n

Wiadomosc Szyfrowanie Odszyfrowanie

m Є {0, n-1} c = m mod n m = cd mod n

Rys. 2.1. Schemat blokowy algorytmu RSA

W celu zabezpieczenia maksymalnego bezpieczenstwa liczby p i q sa wybrane tej samej dtugosci oraz utrzymywany w tajemnicy. Zbior Zn z dwoma dziataniami: dodawaniem i mnozeniem wedtug modutu n (modulo n) tworzy arytmetyku modulo n.

Klucz jawny e jest wybrany losowo, aby spetnic zaleznosci:

1< e < (p(n), NWD (e, (p(n)) = 1,

<p(n) = (p - 1)(q -1), (2.3) gdzie ((n) - funkcja Eulera, zdefiniowana jako liczba liczb naturalnych mniejszych od n i wzglednie pierwszych z e; NWD - najwie_kszy wspolny dzielnik.

Liczby e i ((n) sa wzglednie pierwszymi, jesli nie maja wspolnych podzielnikow innych niz 1. Funkcja Eulera ((n) zawsze przyjmuje wartosc mniejsza niz n.

Nastepnie obliczamy klucz tajny d, stuzacy do odszyfrowania kryptogramu c. W tym celu wykorzystujemy rozszerzony algorytm Euklidesa (zatacznik 1). Liczba d spetnia zaleznosc

e d mod ((n) = 1, (2.4)

czyli kongruencje

e d mod ((n) = 1 (mod ((n)), (2.5)

albo

d = e-1(mod (p - 1)(q -1)). (2.6)

Zauwazmy, ze liczba d musi byc wzglednie pierwsza z liczba n.

Klucz jawny e jest wykorzystywany do szyfrowania danych, a klucz tajny d - do odszyfrowania. Po obliczeniu kluczy liczby p i q nalezy wymazac z systemu, zeby nie zostaty ujawnione.

Procedura szyfrowania E wyznacza kryptogram c przez pare (klucz jawny e, wiadomosc m), zgodnie z nastepujacym wzorem:

c = Ee(m) = mt (mod n).

(2.7)

W celu szybkiego obliczania wartosci c jest wykorzystywany ciag kolejnych podnoszen do kwadratu liczby catkowitej m oraz mnozen na m ze sprowadzeniem wedtug modutu n.

Operacja odwrotna polegajaca w obliczaniu m wedtug c, e i n jest praktycznie niewykonywalna dla n ~ 2512.

Majac pare (kryptogram c oraz klucz tajny d), mozemy obliczyc wiadomosc m za pomoca procedury deszyfrowania D z rownania

Wiadomosc mozna rowniez zaszyfrowac za pomoca liczby d, a odszyfrowac za pomoca liczby e.

> Owszem, jesli kryptogram c

jest potegowany wedtug potegi d, to otrzymujemy odnowiony tekst wejsciowy m, poniewaz

m = Dd(c) = cd (mod n).

(2.8)

c = mt (mod n)

(2.9)

(me)d = nfd = m" ((n)

+1

m(mod n).

(2.10)

Uogolnienie.

Uzytkownik B tworzacy kryptosystem ochrania dwa parametry: 1) klucz tajny d i 2) pare liczb (p, q), iloczyn ktorych jest rowny n.

Z innej strony, uzytkownik B ujawnia liczbe n i klucz jawny e. Niepowotanym osobom sa znane tylko liczby e i n.   Jesli oni

mogtyby roztozyc mnozniki p i q (zadanie faktoryzacji), to kazda z tych osob mogta by dowiedziec sie o „tajnym chodzie" - trojce liczb (p, q i n), nastepnie obliczyc funkcje Eulera ((n) = (p - 1)(q - 1) i znalezc klucz tajny d.

W 1994 r. szyfr RSA zostat ztamany, za pomoca sieci Internet. Pracowato nad tym 600 osob na pieciu kontynentach, przez osiem miesiecy od sierpnia 1993 r. do kwietnia 1994 r. Odczytano wtedy tekst „The magic words are squeamish ossifrage" zaszyfrowany przez tworcow RSA siedemnascie lat wczesniej, przy czym:

n - liczba o dlugosci 129 znakow dziesiejtnych,

p - liczba pierwsza o dlugosci 64 znakow dziesiejtnych,

q - liczba pierwsza o dlugosci 65 znakow dziesiejtnych,

e = 9007.

Mimo to algorytm RSA w sposob praktycznie bezkonkurencyjny jest powszechnie uwazany za algorytm bezpieczny.

Algorytm RSA zostat zrealizowany sprzejtowo przez wiele firm. Szybkosc transmisji, jaka osiagniejo w realizacji sprzejtowej, wynosi 64 Kbit/s w blokach 512-bitowych. Jedna z powaznych wad jaka mozna zarzucic algorytmowi RSA jest szybkosc dziatania, ktora w porownaniu do algorytmu DES jest okoto 1000 razy mniejsza w realizacji sprzejowej, a okoto 100 razy mniejsza w realizacji programowej.

Procedura szyfrowania i odszyfrowania.

Niech uzytkownik A (nadawca) chce wystac wiadomosc skierowana do uzytkownika B (odbiorca, posiadacz klucza tajnego). Wtedy kolejnosc dziatan uzytkownikow A i B jest taka.

Uzytkownik B:

1. Wybiera dwie dowolne liczby pierwsze p i q nie ujawniajac ich.

2. Oblicza modut n = p q.

3. Oblicza funkcje Eulera ((n) = (p - 1)(q -1).

4. Wybiera losowo klucz jawny e taki, ze e jest liczba pierwsza wzgledem ((n): 1< e < ((n), NWD (    e, ((n)) = 1.

5. Ustala klucz tajny d taki, ze d e = 1 (mod ((n)) i ze d < ((n).

6. Przekazuje uzytkowniku A pare liczb (e, n) bezpiecznym kanatem transmisyjnym.

Uzytkownik A:

7. Dzieli tekst jawny m na bloki m,-, kazdy z ktorych jest liczba m{ = {0, n -1}.

8. Szyfruje tekst zgodnie ze wzorem c = mf (mod n).

9. Wysyta kryptogram d, c^, c3,..., c,    uzytkowniku B.

Uzytkownik B:

10. Odszyfrowuje   przekazany   kryptogram   d, c^, c3,..., c, stosujac klucz tajny d, zgodnie ze wzorem    = cd (modn).

Opracowanie przykladu RSA. Aby pokazac jak RSA generuje klucze, przeprowadzimy przyktadowe obliczenie. Wybieramy liczby, ktore mozna wzglednie tatwo zweryfikowac, lecz do prawdziwego zastosowania RSA korzysta z duzo wiekszych liczb.

Dzialania uzytkownika B:

1. Najpierw wybiera dwie liczby pierwsze. W tym przypadku p = 3, a q = 11.

2. Teraz oblicza n = p q. To znaczy, ze n = 3*11 = 33.

3. Teraz musi obliczyc ((n) = (p - 1)(q -1) = (3 --1) = 20..

4. Wybiera liczbe e taka, ze e jest wzglednie pierwsze do ((n) = 20. Jako te liczbe wybiera e = 7.

5. Musi ustalic d takie, ze d e = 1 (mod ((n)). Tak wiec d = 7-1 mod 20, a d musi byc rownoczesnie mniejsze od 20. Ustalamy, ze d = 3 (3 razy 7 rowna sie 21. 21 podzielone przez 20 rowna sie 1 z reszta 1).

6. Wysyta uzytkowniku A pare liczb (e = 7, n = 33).

Aby wykonac wtasciwe szyfrowanie i odszyfrowanie korzystamy z pierwotnych wzorow:

Tekst zaszyfrowany = (tekst jawny)e mod n, Tekst jawny = (tekst zaszyfrowany)d mod n. Przyjmijmy,   ze  uzytkownik  A  chce  wystac   uzytkowniku B wiadomosc m o tresci „312".

Dzialania uzytkownika A:

7. Dzieli wiadomosc m = 312 na bloki    = 3, m2 = 1, m3 = 2.

8. Stosuje wzor szyfrowania i otrzymuje: d = 37 (mod 33) = 2187 (mod 33) = 9, c2 = 17 (mod 33) = 1 (mod 33) = 1,

c3 = 27 (mod 33) = 128 (mod 33) =2 9.

9. Wysyta uzytkowniku B kryptogram c1, c2, c3 = 9, 1, 29.

Dzialania uzytkownika B:

10. Kiedy zaszyfrowana wiadomosc jest otrzymana, przechodzi przez algorytm deszyfrujacy:

1П1 = 93 (mod 33) = 729 (mod 33) = 3, ah = 13 (mod 33) = 1 (mod 33) = 1, 1113 = 293 (mod 33) = 24389 (mod 33) = 2. Odnowiony tekst jawny m = 312.

Miedzynarodowa organizacja standaryzacyjna ISO zarejestrowata 9796 standardow, ktore opieraja sie na algorytmie RSA. Ten algorytm jest stosowany miedzy innymi w:

• ogolnoswiatowych sieci bankowych, zwtaszcza do wykonywania operacji za pomoca kart kredytowych;

banku miedzynarodowym SWIFT (Society for Worldwide Interbank Financial Telecommunications);

francuskim systemie finansowym - standard ETEBAC 5;

• systemie bankowym USA;

• australijskim standardzie zarzadzania kluczami szyfrowymi;

programie szyfrujacym komunikaty poczty elektronicznej PGP (Pretty Good Privacy), w potaczeniu z symetrycznym algorytmem kryptograficznym IDEA (International Data Encryption Algorithm);

• standardzie zabezpieczania poczty elektronicznej SMIME (Secure Multipurpose Internet Mail Extention), bedacym norma szyfrowania wiadomosci i sktadania podpisu cyfrowego;

• protokole zabezpieczania przekazow przesytanych w warstwie 4 (transportowej) TLS (Transport Layer Security) modelu ISO/OSI.

Страницы:
1 


Похожие статьи

Автор неизвестен - 13 самых важных уроков библии

Автор неизвестен - Беседы на книгу бытие

Автор неизвестен - Беседы на шестоднев

Автор неизвестен - Богословие

Автор неизвестен - Божественность христа