Dr inż. Robert Wójcik



Pobieranie 2,08 Mb.
Strona13/13
Data14.02.2018
Rozmiar2,08 Mb.
1   ...   5   6   7   8   9   10   11   12   13
Funkcje szyfrująca i deszyfrująca są wzajemnie odwrotne, co zapewnia poprawność operacji deszyfrowania.
Na bezpieczeństwo szyfru wpływa dobór liczb pierwszych p i q.
Powinny to być liczby o długości powyżej stu cyfr. W celu lepszego zabezpieczenia n przed rozkładem na czynniki pierwsze zaleca się, aby:

– liczby p i q różniły się o kilka cyfr,

– zarówno p − 1, jak i q − 1 miały duże czynniki pierwsze,

– wartość NWD( p − 1, q − 1) była niewielka.


W realizacji praktycznej algorytmu występuje problem wyboru algorytmu generowania liczb pierwszych i realizacji funkcji szyfrującej.
Do generowania dużych liczb pierwszych nie nadaje się klasyczna metoda sita Eratostenesa. Również nie powinno się używać powszechnie znanych liczb pierwszych, takich jak np. liczby pierwsze Mersenna lub Fermata.

W kryptografii poszukuje się liczb pierwszych w ten sposób, że za pomocą generatora losowego losuje się liczby nieparzyste, a następnie poddaje się je testom pierwszości.


Jeśli wylosowana liczba przechodzi pomyślnie te testy, to jest bardzo prawdopodobne, że jest ona liczbą pierwszą.
Znanych jest kilka testów pierwszości. Jeden z tych testów opiera się na małym twierdzeniu Fermata, które mówi, że liczba pierwsza p spełnia zależność

dla a całkowitych niepodzielnych przez p.
Na przykład dla p = 5 i a = 4, otrzymamy 44 mod 5 = 256 mod 5 = 1.
Jeśli ustalonego p i pewnej liczby (np. 100) wylosowanych wartości liczby a twierdzenie Fermata jest spełnione, to mamy prawo przypuszczać z dużym prawdopodobieństwem, że liczba p jest liczbą pierwszą.
P r z y k ł a d obliczeń RSA.
Stosując algorytm RSA, wykonać szyfrowanie i deszyfrowanie informacji mi = 3.
Przyjąć, że wygenerowane elementy klucza tajnego wynoszą:
p = 5, q = 7 i e = 11.
Dla przyjętych wyżej wartości p, q i e ze wzorów otrzymamy:
n = p q = 35 i ϕ(n) = (p −1)(q −1) = 24.
Obliczamy d, wykorzystując algorytm Euklidesa.

Najpierw wyznaczamy NWD(11, 24).



Aby znaleźć d, należy rozwiązać równanie:

W celu przedstawienia liczby 1 jako kombinacji liniowej liczb 11 i 24 wykorzystujemy ciąg równości od ostatniej do pierwszej w algorytmie Euklidesa.
W każdym kroku zapisujemy liczbą 1 za pomocą wcześniejszych reszt, aż dojdziemy do samych liczb 11 i 24:


Szukana liczba d wynosi 11.
Szyfrowanie informacji przeprowadzamy według wzoru:

Deszyfrowanie kryptogramu odbywa się według wzoru:

W 1994 r. szyfr RSA został złamany. Odczytano wtedy zdanie zaszyfrowane przez twórców RSA siedemnaście lat wcześniej.
Pracowało nad tym 600 osób na pięciu kontynentach, przez osiem miesięcy, za pomocą sieci Internet. Mimo to algorytm RSA jest obecnie uważany za algorytm bezpieczny.

Algorytm RSA jest około 1000 razy wolniejszy od algorytmu DES w realizacji sprzętowej, a około 100 razy wolniejszy w realizacji programowej.


Algorytm RSA jest standardem do podpisów cyfrowych Międzynarodowej Organizacji Normalizacyjnej ISO (International Standards Organisation), ISO/IEC 9796.
Opracowano też inne algorytmy asymetryczne, które są bardziej odporne na złamanie przez komputery kwantowe niż RSA. Jest to algorytm NTRU, wykorzystujący algebrę kraty.
NTRU – asymetryczny kryptosystem z kluczem publicznym i prywatnym. Ma dwie cechy dające mu przewagę nad algorytmem RSA i ECC – krzywe eliptyczne (dla których może stanowić rozwiązanie alternatywne): szybkość i odporność na obliczenia kwantowe. Istnieją dwa algorytmy NTRU: NTRUEncrypt i NTRUSign. Dostępna jest otwarta implementacja NTRU.

1   ...   5   6   7   8   9   10   11   12   13


©operacji.org 2017
wyślij wiadomość

    Strona główna