To tylko jedna z 7 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
Algorytm RSA Pionierska praca Diffiego i Hellmana wprowadziła nowe podejście do kryptografii i rzuciła kryptologom wyzwanie: stworzyć algorytm kryptograficzny spełniający wymagania systemów szyfrowania z kluczem jawnym. Jedna z pierwszych odpowiedzi na to wyzwanie była dziełem Rona Rivesta, Adi Shamira i Lena Adlemana z MIT, powstała w 1977 r. i została po raz pierwszy opublikowana w 1978 r. System Rivesta-Shamira-Adlemana (RSA) od tej pory znajduje się na szczycie jako jedyna powszechnie akceptowana i stosowana metoda szyfrowania z kluczem jawnym.
System RSA to szyfr blokowy, w którym tekst jawny i tekst zaszyfrowany są liczbami całkowitymi od 0 do n-l dla pewnego n . Ponieważ jest to jedyna powszechnie akceptowana metoda szyfrowania z kluczem jawnym, w niniejszym podrozdziale omówimy ją dość szczegółowo, zaczynając od wyjaśnienia algorytmu.
Następnie zajmiemy się niektórymi aspektami kryptoanalitycznymi i obliczeniowymi RSA.
Opis algorytmu System stworzony przez Rivesta, Shamira i Adlemana korzysta z wyrażenia potęgowego. Tekst jawny jest szyfrowany blokami, z których każdy ma wartość binarną mniejszą od pewnej liczby n. Szyfrowanie i deszyfrowanie dla bloku tekstu jawnego M i bloku tekstu zaszyfrowanego Z mają następującą formę:
C=M e mod n M=C d mod n =(M e ) d mod n =M ed mod n Zarówno nadawca, jak i odbiorca muszą znać wartość n . Nadawca zna wartość e i jedynie odbiorca zna wartość d . Jest to więc algorytm szyfrowania z kluczem jawnym KU={ e, n } i kluczem prywatnym KR={ d, n }. Aby algorytm ten był odpowiedni do szyfrowania z kluczem jawnym, muszą być spełnione następujące wymagania:
1. Czy możliwe jest znalezienie takich wartości e, d, n , że M ed =M mod n dla każdego M
(…)
… d. Zakładając, że mamy do czynienia z pierwszą sytuacją, musimy wybrać takie d, że nwd Φ(n), d)=1, a następnie obliczyć e=d-1 mod Φ(n). Na szczęście istnieje jeden algorytm, który jednocześnie oblicza największy wspólny dzielnik dwu liczb całkowitych i jeśli nwd=l, oblicza odwrotność jednej z liczb całkowitych modulo druga. Algorytm ten, zwany jest rozszerzonym algorytmem Euklidesa. Procedura…
… całkowita a. Jeżeli n „nie zda” testu, nie jest liczbą pierwszą. Jeśli „zda", może być liczbą pierwszą lub nie. Jeśli n przejdzie wiele testów z udziałem wielu losowo wybranych wartości a, możemy mieć sporą pewność, że n jest rzeczywiście liczbą pierwszą.
W skrócie procedura losowania liczby pierwszej jest następująca:
1. Wylosować nieparzystą liczbę całkowitą n (np. za pomocą generatora liczb…
…: tylko wtedy, kiedy zaistnieje potrzeba stworzenia nowej pary kluczy (KU, KR).
Warto wspomnieć o tym, jak wiele liczb prawdopodobnie zostanie odrzuconych, zanim zostanie znaleziona liczba pierwsza. Wniosek z teorii liczb, zwany twierdzeniem o liczbach pierwszych, mówi, że liczby pierwsze w otoczeniu N są rozmieszczone średnio jedna na (ln N) liczb całkowitych. A więc należałoby sprawdzić średnio ln (N) liczb całkowitych, zanim…
…, co problem rozkładu na czynniki. Możemy posłużyć się wydajnością rozkładania na czynniki jako miarą oceny bezpieczeństwa algorytmu RSA.
Oprócz stwierdzenia, że n powinno być liczbą rzędu od l0150 do l0200, badacze zaproponowali wiele innych ograniczeń. Aby uniknąć takich wartości n, które mogłyby zostać łatwiej rozłożone na czynniki, wynalazcy algorytmu zaproponowali następujące ograniczenia dotyczące…
... zobacz całą notatkę
Komentarze użytkowników (0)