Zrozumieć algorytm szyfrowania RSA

Zrozumieć algorytm szyfrowania RSA

10 marca 2022 0 przez It-hits

W 1976 roku, tuż po tym, jak Diffie-Hellman wywrócił do góry nogami całą branżę kryptograficzną, pojawiło się trzech kolejnych nowicjuszy, którzy jeszcze bardziej zrewolucjonizowali tę dziedzinę: Ron Rivest, Adi Shamir i Leonard Adleman. Trio to opracowało sposób negocjowania bezpiecznej komunikacji między nieznanymi stronami na odległość, co okazało się niezwykle ważne dla funkcjonowania Internetu. Algorytm, który wymyślili, stał się znany dzięki ich inicjałom: RSA.

Rivest, Shamir i Adleman, zainspirowani dokumentem Diffiego-Hellmana, wymyślili nowy, ale pokrewny sposób szyfrowania z kluczem publicznym, czyli szyfrowanie asymetryczne. W tym artykule opisano działanie RSA na poziomie praktycznym.

Innowacyjność RSA

Algorytm RSA, wraz z Diffie-Hellmanem, jest bohaterem jednego z najbardziej fascynujących rozdziałów dotyczących wpływu technologii na społeczeństwo. Wcześniej bezpieczna komunikacja była wyłączną domeną suwerennych państw lub globalnych korporacji. Wynikało to z wysokich kosztów utrzymania infrastruktury kluczy związanych z algorytmami symetrycznymi. Wraz z pojawieniem się algorytmów Diffie-Hellmana i RSA bezpieczna komunikacja między osobami fizycznymi stała się możliwa. (A wraz z pojawieniem się PGP w latach 90. stało się to proste).

Można było przewidzieć, że agencje bezpieczeństwa rządu Stanów Zjednoczonych, na czele z NSA, wpadły we wściekłość z powodu tej nagłej eksplozji nieczytelnej komunikacji. Walka między inwigilacją a prywatnością trwa nadal, ale matematyczne podstawy algorytmów takich jak RSA oznaczają, że małe organizacje i osoby prywatne mają możliwość zabezpieczenia swojej komunikacji przed wścibskimi oczami, nawet przed podmiotami państwowymi.

RSA kontra Diffie-Hellman

Na najwyższym poziomie algorytm RSA działa podobnie jak Diffie-Hellman, wymieniając informacje publiczne, które są następnie używane do ustanowienia tajnego klucza znanego tylko uczestnikom. Tajny klucz jest odporny na podsłuch dzięki funkcji jednokierunkowej.

Pomiędzy tymi dwoma algorytmami występują istotne różnice w szczegółach. Na początek w algorytmie Diffiego-Hellmana obie strony wymieniają informacje o kluczu publicznym, a następnie uzyskują wspólny klucz tajny. W algorytmie RSA jedna strona generuje parę kluczy, zarówno klucz publiczny, jak i klucz tajny, a następnie druga strona używa klucza publicznego do zaszyfrowania komunikacji. Klucz prywatny jest używany do odszyfrowania.

RSA w akcji

Prześledźmy algorytm RSA krok po kroku na przykładzie. Załóżmy, że Bob chce wysłać prywatną wiadomość do Alicji. Pierwszym krokiem jest wygenerowanie przez Alicję kluczy, zarówno publicznego, jak i prywatnego. W kroku drugim Alicja przekazuje Bobowi klucz publiczny. W kroku trzecim Bob używa klucza publicznego do zaszyfrowania swojej wiadomości dla Alicji. W czwartym i ostatnim kroku Alicja odszyfrowuje wiadomość za pomocą klucza prywatnego.

Ponieważ Alicja jest jedyną osobą, która posiada klucz prywatny, jest jedyną osobą, która może odczytać wiadomość Boba.

Generowanie kluczy RSA

Pierwszym krokiem do wygenerowania pary kluczy RSA jest wybranie dwóch dużych liczb pierwszych, p i q. Następnie mnożymy te duże liczby pierwsze, aby otrzymać n.

W praktyce p i q są bardzo dużymi liczbami, ponieważ obecnie najlepsze praktyki zalecają uzyskanie klucza o rozmiarze co najmniej 2048 bitów, czyli 617 cyfr. Dla celów demonstracyjnych posłużymy się skromniejszymi liczbami.

Alicja wybiera p = 41 i q = 53

Istotne jest, że są to liczby pierwsze, ponieważ użycie liczb pierwszych zapewnia uzyskanie pewnych właściwości przy kolejnych obliczeniach. Następną rzeczą, którą robi Alicja, jest obliczeniee liczba n, która jest iloczynem p * q. (Jako iloczyn dwóch liczb pierwszych, n jest liczbą półpierwszą).

n = p * q = 2173

Należy pamiętać, że p i q muszą być utrzymywane w tajemnicy. Jednak n jest częścią klucza publicznego, więc może być rozpowszechniane.

Funkcja Carmichaela

Następnym krokiem jest znalezienie liczby d, która będzie stanowiła klucz prywatny. Sztuczka polega na znalezieniu d za pomocą matematyki, która jest łatwa dla nas, którzy znamy p i q, ale która będzie bardzo trudna dla każdego, kto nie zna p i q (pomimo znajomości iloczynu p i q, n).

Ta sztuczka zaczyna się od obliczenia funkcji Carmichaela, którą dla liczby n zapisuje się jako λ(n) lub lambda(n). Funkcja Carmichaela jest jakby redukcją funkcji Eulera φ i działa bardzo podobnie. (W rzeczywistości, w oryginalnej wersji RSA użyto funkcji Eulera). Funkcja Carmichaela mówi: Dla każdej liczby z przedziału od 1 do argumentu n, która jest współrzędną n, jaka jest najmniejsza liczba całkowita m, która spełni kryterium 1 (mod n). Innymi słowy:

a^m = 1 (mod n)

Rozpakujmy to trochę. Po pierwsze, dwie liczby są koprime, jeśli żadna liczba całkowita oprócz 1 nie dzieli się równo na obie liczby. W naszym przypadku funkcja Carmichaela wyszukuje każdą liczbę całkowitą z przedziału od 1 do n, która nie ma wspólnych czynników z n oprócz 1.

Funkcja Carmichaela pyta, jaka jest najmniejsza liczba, do której możemy podnieść każdy z tych koprimów i otrzymać wynik, który po podzieleniu przez n pozostawia resztę 1. Pamiętaj, że operator mod zwraca resztę z dzielenia przez n.

Odkrycie funkcji Carmichaela λ(n) dla bardzo dużej liczby byłoby bardzo kosztowną operacją, ale mamy pewien skrót. Ponieważ n jest iloczynem dwóch liczb pierwszych, funkcję Carmichaela można znaleźć poprzez znalezienie najmniejszej wspólnej wielokrotności (lcm) liczb n – 1 i p – 1:

λ(n) = lcm(n-1, p-1)

Jest to wynik nieoczywisty, ale stanowi część wyniku, z którego korzystali twórcy RSA. Naszym następnym krokiem jest znalezienie tej najmniejszej wspólnej wielokrotności:

λ(n) = lcm(n-1, p-1) = lcm(41-1, 53-1) = lcm(40, 52) = 520

Tę liczbę zachowujemy w tajemnicy.

Teraz obliczymy e, ostatni krok na naszej drodze do d. e jest liczbą współrównoległą do λ(n), która jest mniejsza od λ(n) i większa od 1.

Możemy znaleźć koprime dla 520, wybierając znaną liczbę pierwszą i upewniając się, że nie jest ona dzielnikiem 520, albo skorzystać z algorytmu. W tym przykładzie Alicja użyje e = 11.

Na koniec otrzymamy d przez obliczenie następującej zależności:

d ≡ e-1 (mod λ(n))

Gdzie trzy kreski oznaczają kongruencję modularną, to znaczy, że obie strony mają taką samą resztę. W naszym przykładzie Alicja ma następujące równanie dla d:

d ≡ 11^-1 (mod 520)

Które możemy zapisać jako

1 = (11 * d) mod 520

Czyli: Jaka liczba, d, razy 11, przy dzieleniu jej przez 520 daje resztę 1? Rozwiązując to zadanie, Alicja otrzymuje

d = 331

d jest kluczem prywatnym, e jest kluczem publicznym, a n jest liczbą niebędącą tajemnicą, używaną do uzyskania obu tych wartości. Algorytm RSA działa, ponieważ gdy n jest dostatecznie duże, wyprowadzenie d ze znanego e i n będzie niepraktycznie długim obliczeniem – chyba że znamy p, wtedy możemy użyć skrótu. Dlatego właśnie p i q muszą pozostać tajne.

Zobaczmy, jak Alice i Bob używają tych funkcji

liczby do zaszyfrowania i odszyfrowania tajnej wiadomości Boba.

Szyfrowanie za pomocą RSAW

rzeczywistych zastosowaniach wiadomości są wypełniane w celu zwiększenia bezpieczeństwa. Należy również powtórzyć, że RSA (i Diffie-Hellman) są zwykle używane do ustanowienia wspólnej tajemnicy, która jest następnie używana jako klucz do szyfrowania symetrycznego, np. Wynika to z ograniczeń szybkości i rozmiaru, jakie wiążą się z szyfrowaniem asymetrycznym.

Powyższe zastrzeżenia wynikają z faktu, że Alicja i Bob będą szyfrować liczbę, a nie wiadomość. Należy pamiętać, że algorytm RSA będzie używany przez Alicję tylko do wymiany kluczy w celu późniejszej wymiany symetrycznej z Bobem.

Załóżmy, że Bob ma liczbę 101, którą bezpiecznie wyśle do Alicji za pomocą klucza publicznego (n = 2173, e = 11). Bob wykonuje więc następujące czynności:

szyfrogram = wiadomość^e mod n = 101^11 mod 2173 = 1305

Bob wysyła 1305 do Alicji.

Odszyfrowanie za pomocą RSAAlice

otrzymuje wiadomość Boba i odszyfrowuje ją za pomocą klucza prywatnego (n = 2173, d = 331). Alice wykonuje więc następującą czynność:

tekst jawny = cyphertext^d mod n = 1305^331 mod 2173

Jeśli wstawisz to równanie do programu Wolfram Alpha, wynikiem będzie oryginalna liczba Boba, czyli 101.

Podpisywanie wiadomości

za

pomocą

RSAJak widać, RSA jest bardziej skomplikowane niż Diffie-Hellman. Ma inne przypadki użycia. Jedną z interesujących funkcji w RSA jest podpisywanie wiadomości. Mówiąc najprościej, podpis cyfrowy pozwala udowodnić, że wiadomość pochodzi od osoby posiadającej klucz prywatny. Jest to możliwe dzięki pewnej właściwości kluczy RSA: Zaszyfrowana wiadomość zaszyfrowana kluczem prywatnym może zostać odszyfrowana tylko przy użyciu odpowiedniego klucza publicznego

.

Krótko mówiąc, możliwość odszyfrowania zaszyfrowanej wiadomości za pomocą klucza publicznego dowodzi definitywnie, że nadawca był w posiadaniu klucza prywatnego.

Zarówno Diffie-Hellman, jak i RSA są dziełami geniuszu, łączącymi matematykę teoretyczną i kodowanie praktyczne w działającą kryptografię asymetryczną. W przypadku RSA to właśnie sztuczka polegająca na wzięciu liczb pierwszych p i q i przekształceniu ich w liczby, które można transmitować, n i e, sprawia, że algorytm jest zarówno praktyczny, jak i bezpieczny.

Jak bezpieczny? Według najnowszych szacunków klasyczny komputer deterministyczny (niekwantowy) potrzebowałby około 300 trylionów lat na złamanie algorytmu RSA-2048 (gdzie n ma 2048 bitów). To całkiem bezpieczny wynik.

Copyright © 2022 IDG Communications, Inc.


Czytaj dalej: https://www.infoworld.com/article/3650488/understand-the-rsa-encryption-algorithm.html#tk.rss_all