Temat wykladu:
Kryptografia: Asymetryczne algorytmy szyfrowania (by jaboja, 2007-07-30) @ wyklady.net
Komentarze: http://forum.wyklady.net/index.php?topic=115.0
20:38JaBoJaWitam
20:39JaBoJaDzisiejszy wyklad poswiecony bedzie niesymetrycznym algorytmom szyfrowania
20:40JaBoJaZacznijmy od tego czym wogole sa algorytmy niesymetryczne
20:40JaBoJaZ pewnoscia znacie szyfrowanie symetryczne, to znaczy z tym samym kluczem uzywanym zarowno do szyfrowania jak i do deszyfrowania
20:41JaBoJaChociazby prosty XOR, czy jego tekstowa wersja czyli kod Vigeneree'a
20:41JaBoJaTen sam klucz sluzy tam do zaszyfrowania wiadomosci i do jej pozniejszego odkodowania
20:42JaBoJaNatomiast w algorytmach niesymetrycznych klucze te sa rozne
20:42JaBoJaW wiekszosci wypadkow dodatkowo nie da sie uzyskac pierwszego znajac drugi et vice versa
20:42JaBoJa(acz sa wyjatki)
20:43JaBoJaCo w ten sposob uzyskujemy?
20:43JaBoJaMozemy opublikowac jeden klucz np. w internecie (tzw. klucz publiczny)
20:43JaBoJai jesli ktos chce nam rpzyslac wiadomosc przeznaczona tylko dla naszych oczu to uzyje go do szyfrowania
20:44JaBoJaOdszyfrowac mozna ja bedzie tylko tym drugim kluczem (tzw. klucz prywatny), wiec tylko my ja przeczytamy
20:44JaBoJaCo jednak wazne mozna ten proces odwrocic uzyskujac tym samym podpis elektroniczny
20:44JaBoJaPodpis dziala nastepujaco:
20:45JaBoJaSzyfrujemy wiadomosc swoim kluczem prywatnym, a odbiorca dekoduje ja naszym kluczem publicznym
20:46JaBoJaW ten sposob ma on pewnosc ze to my jestesmy autorem, bo tylko my znamy nasz klucz prywatny
20:46JaBoJaTu jednak pojawia sie pewien problem. Spojrzmy na nastepujaca sytuacje:
20:47JaBoJaSzyfrujemy wiadomosc swoim kluczem prywatnym i dolaczamy do tekstu zaszyfrowanego kluczem publicznym odbiorcy jako podpis.
20:48JaBoJaStwarza to mozliwosc zlamania kodu
20:48JaBoJaWyglada to nastepujaco:
20:50JaBoJanapastnik moze tak spreparowac wiadomosc zeby zmusic nas do jej nieswiadomego odszyfrowania gdy bedziemy tworzyc podpis
20:50JaBoJadzieje sie tak jesli uzyjemy dodatkowo potwierdzenia odbioru poprzez odeslanie wiadomosci nadawcy
20:52JaBoJadlatego tez o wiele lepszym rozwiazeniem jest podpisywanie nie z uzyciem calej wiadomosci, ale jej skrotu
20:52JaBoJa(na przyklad wygenerowanego algorytmem MD5)
20:53JaBoJaTak wiec schemat kozystania z algorytmu niesymetrycznego powinien byc nastepujacy:
20:53JaBoJa1. Obliczamy skrot (np. MD5) wiadomosci
20:54JaBoJa2. Szyfrujemy go swoim kluczem prywatnym
20:54JaBoJa3. Dolaczamy go do wiadomosci i szyfrujemy calosc kluczem publicznym odbiorcy
20:54JaBoJa4. Odbiorca deszyfruje wiadomosc swoim kluczem prywatnym
20:55JaBoJa5. Odbiorca deszyfruje podpis naszym kluczem publicznym i porownuje go z podpisem wygenerowanym samodzielnie ta sama funkcja skrotu
20:56JaBoJaZ algorytmami niesymetrycznymi wiaze sie jednak jeszcze problem innego rodzaju, dodatkowo komplikujacy rzeczywiste implementacje
20:56JaBoJaSa one o wiele wolniejsze od symetrycznych
20:57JaBoJaNa przyklad niesymetryczny algorytm RSA jest 1000 razy wolniejszy od symetrycznego DES
20:57JaBoJaZ tego tez powodu dobrym rozwiazaniem jest stosowanie systemow hybrydowych stosujacych oba typy algorytmow
20:58JaBoJaKlucz algorytmu symetrycznego (np. DES) jest generowany losowo, a nastepnie szyfrowany algorytmem niesymetrycznym.
20:58JaBoJaOdbiorca odkodowuje swoim kluczem prywatnym nie wiadomosc, ale zaszyfrowany klucz, ktory dopiero sluzy do odczytania wiadomosci.
20:59JaBoJaPojawia sie tu jednak kolejny problem: klucz musi byc na tyle dlugi, aby nie mozna bylo go odgadnac metoda brute-force
21:02JaBoJajesli jest za krotki to znajac klucz publiczny mozemy sobie bez problemu zakodowac dowolny klucz do algorytmu symetrycznego
21:02JaBoJai gdyby udalo nam sie zaszyfrowac tak wszystkie mozliwe klucze
21:02JaBoJato mogli bysmy znalesc ten wlasciwy
21:02JaBoJanawet jesli znalezienie klucza prywatnego algorytmu niesymetrycznego jest niewykonalne
21:04JaBoJaOczywiscie to samo moze nas spotkac jesli zaszyfrujemy bezposrednio wiadomosc algorytmem niesymetrycznym (np. RSA): jesli bedzie za krotka to mozna probowac szyfrowac wszystkie mozliwe wiadomosci sprawdzajac ktora bedzie pasowac do tej ktora przechwycilismy
21:04JaBoJawtedy wystarczy dolozyc na koncu wiadomosci jakas duza liczbe losowa
21:05JaBoJaI moze jeszcze jedna uwaga nim przejde do opisu algorytmu RSA:
21:05JaBoJaLiczby losowe
21:05JaBoJanie wolno ich napewno generowac systemowym generatorem pseudolosowym
21:07JaBoJaGeneratory losowe nie sa sprawa az tak prosta, wiec i tak musimy znalesc jakis skuteczny generator pseudolosowy, ale nalezy pamietac ze jesli bedzie zbyt przewidywalny to przewidywanie jego dzialania moze posluzyc zlamaniu kodu.
21:07JaBoJaGeneratorm pseudolosowym nie bede dzis poswiecal zbyt duzo czasu, natomiast pochwale sie ze mam generator losowy zbudowany w oparciu o wzmacniacz szumow tranzystora.
21:08JaBoJaDla zainteresowanych moge podac schemat budowy.
21:08JaBoJahttp://www.edw.com.pl/pdf/k04/43_10.pdf
21:09JaBoJaProblematyczne moze byc natomiast podlaczenie go do komputera, ale to juz nie temat tego wykladu.
21:10JaBoJaPrzejdzmy teraz do algorytmu RSA
21:11JaBoJanotabene: jest on opatentowany w USA, nie wiem jak tu wyglada kwestia prawna, ale wydaje mi sie ze nas w Polsce ten patent nie dotyczy (jak ktos chce sprawdzic to niech we wlasnym zakresie poszuka w Google).
21:12JaBoJabezpieczenstwo algorytmu RSA wynika z trudnosci w rozkladzie na czynniki pierwsze duzych liczb
21:12JaBoJaZacznijmy jednak od sposobu generowania kluczy (rzecz opisywana w niemal wszystkich ksiazkach):
21:14JaBoJa[ baiji mi dal wlasnie znac na priv, ze patent na RSA wygasl w 2000 roku ]
21:15JaBoJagenerujemy losowo dwie duze liczby pierwsze p i q
21:16JaBoJaduze to np. 200cyfr (albo i wiecej)
21:16JaBoJaobliczmy: n=p*q
21:17JaBoJawazna uwaga: mimo ze teoretycznie znajac n znamy p i q to obliczenie tego jest niewykonalne w rozsadnym czasie
21:17JaBoJanastepnie musimy wygenerowac liczbe losowa e, taka aby byla wzglednie pierwsza z liczba (p-1)(q-1)
21:18JaBoJadla przyspieszenia calego algorytmu warto wziasc e=3 albo e=65537
21:19JaBoJamaja one malo jedynek w zapisie binarnym i latwo jest wykonywac z ich uzyciem pozniejsze obliczenia
21:20JaBoJanastepnie musimy znalesc liczbe d, taka ze e*d w dzieleniu przez (p-1)(q-1) daja reszte 1
21:21JaBoJakluczem publicznym algorytmu RSA jest para (n, e), a prywatnym para (n, d)
21:21JaBoJamozna je zamienic miejscami, to ktora liczba jest ktorym kluczem nie ma znaczenia
21:22JaBoJaaby zaszyfrowac wiadomosc algorytmem RSA musimy podzielic ja na bloki mniejsze od n
21:22JaBoJaczyli jesli n mialaby 200 bitow znaczacych to wiadomosc dzielimy na bloki 199 bitowe (dzieki temu mamy gwarancje, ze kazdy blok bedzie liczba mniejsza od n)
21:24JaBoJaszyfrogram takiego bloku danych obliczamy podnoszac (mod n) liczbe reprezentujaca ten blok do potegi rownej kluczowi
21:24JaBoJaszyfrogram = (tekst^e) mod n
21:25JaBoJadeszyfrowanie przebiega analogicznie, acz z drugim kluczem:
21:25JaBoJatekst = (szyfrogram^d) mod n
21:26JaBoJato ze wybierzemy dla kazdego generowanego klucza to samo e (np. 65537) nie ma wplywu na bezpieczenstwo jesli tylko liczby p i q sa rzeczywiscie losowe
21:26JaBoJainna sprawa ze algorytmy generowania losowych liczb pierwszych sa probabilistyczne
21:27JaBoJamozemy uzyskac liczby p i q nie bedace pierwszymi i pojawi sie problem
21:27JaBoJazwykle przy probie szyfrowania nie uda sie odkodowac wiadomosci
21:27JaBoJagorzej jesli zdaza sie nam takie liczby ze szyfrowanie sie powiedzie, ale klucze beda latwe do zlamania
21:28JaBoJajednak generalnie algorytm RSA jest bezpiecznym algorytmem
21:29JaBoJaInnym algorytmem niesymetrycznym, ktory notabene tak jak RSA dziala w obie strony (tj. zarowno jako mechanizm podpisu elektronicznego jak i jako mechanizm szyfrowania) jest algorytm ElGamela
21:30JaBoJagenerujac klucz w tym algorytmie:
21:30JaBoJaNajpierw wybieramy losowa liczbe pierwsza p
21:31JaBoJaNastepnie dwie losowe liczby g, x < p
21:31JaBoJai obliczamy:
21:31JaBoJay = g^x (mod p)
21:32JaBoJa(reszta z dzielenia (g do potegi x ) przez p)
21:32JaBoJakluczem publicznym jest trojka liczb (y, g, p), zas prywatnym liczba x
21:33JaBoJadodatkowo dla uproszczenia algorytmu mozemy uzywac tych sam liczb (g, p) do generacji kluczy dla kilku roznych uzytkownikow
21:34JaBoJaSzyfrowanie algorytmem ElGamela:
21:35JaBoJaGenerujemy liczbe losowa k, taka ze k jest wzglednie pierwsze z (p-1)
21:35JaBoJaSZyfrogram stanowi para liczb (a,b) obliczonych wzorami:
21:36JaBoJaa = (g^k) mod p
21:36JaBoJab = ((y^k)*wiadomosc) mod 5
21:37JaBoJaO ile w przypadku RSA szyfrogram byl podobnej (mniejwiecej z przewaga wicej :P) dlugosci jak tekst jawny to tutaj jest on okolo dwa razy dluzszy
21:37JaBoJa(bo stanowia go dwie liczby)
21:38JaBoJaaby odszyfrowac wiadomosc wystarczy obliczyc:
21:38JaBoJawiadomosc = b/a^x mod p
21:40JaBoJaDla diabla dodatkowo zacytuje z ksiazki "Kryptografia dla praktykow" B. Schneiera fragment tabeli z czasami szyfrowania dla roznych dlugosci liczby p:
21:41JaBoJa[wykladnik potegi ma 160 bitow, a algorytm byl obliczany na komputerze Sparc II]
21:41JaBoJa512 bitow - Szyfrowanie 0,33s / Deszyfrowanie 0,24s
21:42JaBoJa768 bitow - Szyfrowanie 0,80 s / Deszyfrowanie 0,58 s
21:42JaBoJa1024 bity - Szyfrowanie 1,09s / Deszyfrowanie 0,77 s
21:43JaBoJaNotabene w przypadku sprawdzania podpisu elektronicznego algorytmem ElGamela (o tym za chwile) w przypadku 1024 bitow czas wynosi 9,30 s, czyli jest dosyc dlugi
21:44JaBoJapozatym nalezy pamietac ze przy wzroscie dlugosci wiadomosci czas odpowiednio rosnie
21:45JaBoJaczyli jesli p ma 1024 bity, to mozna nim zaszyfrowac nie wiecej niz 1024b/8 = 128B
21:46JaBoJajesli chcemy zaszyfrowac np. 5kB plik Worda to uzyskamy czas (5000B / 128B) * 1,09s ~= 43s
21:47JaBoJadlatego lepiej jest uzywac do samej wiadomosci algorytmow symetrycznych a niesymetrcyzne tylko do losowego klucza
21:47JaBoJaWracajac do samego algorytmu
21:47JaBoJaPodpis cyfrowy algorytmem ElGamela:
21:48JaBoJaMusimy jak poprzednio wygenerowac liczbe losowa k wzglednie pierwsza z (p-1)
21:48JaBoJaobliczmy: a = g^k mod p
21:49JaBoJanastepnie musimy obliczyc b z rownania:
21:49JaBoJawiadomosc = (x*a + k*b) mod (p-1)
21:49JaBoJauzywamy tu notabene tego samego algorytmu co przy generowaniu kluczy RSA
21:50JaBoJajest to tzw. rozszerzony algorytm Euklidesa
21:50JaBoJapodpisem jest tu, podobnie jak szyfrogramem przy szyfrowaniu, para liczb -> (a, b)
21:51JaBoJaSprawdzenie podpisu (czyli de facto deszyfrowanie):
21:52JaBoJa(y^a)(a^b) mod p = g^wiadomosc mod p
21:52JaBoJajesli rownanie to jest prawdziwe podpis jest audentyczny
21:53JaBoJaalgorytm nie jest tu odwracalny w tym sensie ze mozna bezproblemowo zamienic klucz publiczny z prywatnym, bo obliczenie wiadomosci z powyzszego wzoru moze byc niejednoznaczne
21:54JaBoJaUwaga: k musi byc za kazdym razem generowane od nowa, bo inaczej znajac dwa podpisy z ta sama wartoscia k mozna odtworzyc klucz prywatny.
22:01JaBoJaTeraz przejde do algorytmu DSA
22:01JaBoJanie jest to algorytm sluzacy do szyfrowania wiadomosci, ale do podpisow elektronicznych
22:02JaBoJaalgorytm ten uzywa ponadto jednokierunkowej funkcji skrotu realizowanej algorytmem SHA-1
22:03JaBoJagenerujemy liczbe pierwsza p o dlugosci L bitow, gdzie L ma wartosc od 512 do 1024 i jest wielokrotnoscia 64
22:04JaBoJaobliczamy q - czynnik pierwszy liczby (p-1) majacy dlugosc 160 bitow
22:04JaBoJanastepnie obliczamy liczbe g taka ze:
22:05JaBoJag = ( h ^ ((p-1)/q) ) mod p; h jest dowolna liczba mniejsza od (p-1) oraz g>1
22:06JaBoJate trzy liczby sa jawne i ponadto moga byc wspolne dla wielu uzytkownikow
22:06JaBoJanastepnie generujemy klucz prywatny x:
22:07JaBoJax < q
22:07JaBoJaklucz publiczny y obliczamy ze wzoru:
22:07JaBoJay = (g^x) mod p
22:08JaBoJaPodpisywanie wiadomosci wyglada tu nastepujaco:
22:08JaBoJatak jak w poprzednim algorytmie generujemy liczbe losowa k. k powinno byc mniejsze od q.
22:09JaBoJaPodpisem jest para (r,s) obliczona wzorami:
22:09JaBoJar = (g^k mod p) mod q
22:10JaBoJas = ( k^(-1) * (sha1(wiadomosc) + x*r) ) mod q
22:11JaBoJauwaga! k do minus pierwszej oznacza ze uzywamy algorytmu Euklidesa
22:11JaBoJamozemy to inaczej zapisac:
22:11JaBoJas*k = (sha1(wiadomosc) + x*r) mod q
22:12JaBoJaWeryfikacja podpisu przez odbiorce:
22:12JaBoJa1. Obliczamy w ze wzoru: w*s = 1 (mod q)
22:13JaBoJa(notabene to co ja tu pisze w jakims jezyku programowania pewnie mialoby forme: w*s mod q == 1)
22:14JaBoJa2. u1 = (sha1(wiadomosc) * w) mod q
22:14JaBoJa3. u2 = (r*w) mod q
22:14JaBoJa4. v = ((g^u1 * y^u2) mod p) mod q
22:15JaBoJav powinno być równe r
22:15JaBoJajeœli jest inaczej podpis nie jest audentyczny
22:17JaBoJaNa dzisiaj to juz koniec wykladu, material jest jednak dosc obszerny, wiec postaram sie dokonczyc jego omawianie w przyszlym tygodniu (dokladny dzien i godzine podam na forum).
22:18JaBoJaNa koniec standardowe pytanie: sa jakies pytania?
22:18garbus_Dzięki, ze spóŸnieniem ale doczytałem.
22:18garbus_;]
22:19JaBoJaDo zobaczenia na nastepnym wykladzie ;)