Algorytm RSA (Rivesta-Shamira-Adlemana) umożliwia utworzenie klucza publicznego oraz prywatnego, a następnie wykorzystywanie ich w celu szyfrowania i deszyfrowania informacji. Klucz publiczny jest powszechnie znany i każdy może za jego pomocą zaszyfrować dowolną wiadomość. Natomiast jedynie posiadacz klucza prywatnego może odszyfrować otrzymaną wiadomość. Posiadacz klucza prywatnego może używać go też do szyfrowania danych, a posiadacz klucza publicznego może odszyfrować te dane. Bezpieczeństwo algorytmu szyfrowania RSA opiera się na faktoryzacji dużych liczb przypierwszych o których mowa poniżej.
Klucz publiczny składa się z modułu n (p*q) i publicznego wykładnika e, natomiast klucz prywatny składa się z tego samego modułu n i prywatnego wykładnika d.
Wszystkie liczby powiązane z kluczem prywatnym powinny być trzymane w tajemnicy: liczba d oraz trzy kolejne: p, q i φ(n), które mogą być użyte do wyliczenia d.
Luka bezpieczeństwa w algorytmie RSA
Zacznijmy więc od następujących wzorów:
6y+1 gdzie y > 0, y mod 10 ≠ 4, y mod 10 ≠ 9
oraz
6x-1 gdzie x > 0 , x mod 10 ≠ 1, x mod 10 ≠ 6
{(6y+1), (6x-1) | y > 0, y mod 10 ≠ 4, y mod 10 ≠ 9, x > 0 , x mod 10 ≠ 1, x mod 10 ≠ 6}
Oto kilka początkowych liczb z omawianych wzorów:
7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 77, 79, 83, 89, 91, 97…
Wzory te tworzą wszystkie liczby pierwsze (oprócz 2, 3 i celowo 5) oraz liczby przypierwsze czyli iloczyny i kwadraty liczb pierwszych (oprócz 2, 3 i 5). (Więcej na temat liczb przypierwszych znajduję się w dziale LICZBY PRZYPIERWSZE). Wzory użyte powyżej eliminują wszystkie liczby naturalne które nie mogą być wartościami p, q i n występującymi w algorytmie RSA. Jak wiemy iloczyn p i q to zawsze liczba przypierwsza i tworzy wartość n klucza publicznego.
Zaletą tych wzorów jaką doceni branża IT jest możliwość generowania zbioru liczb w którym jest pomijane aż ~73,33% wszystkich liczb naturalnych które nie mogą być liczbami pierwszymi. Minusem istnienia takich wzorów jest powód że szyfrowanie RSA może być poddane poważnym zagrożeniom, które mogą narazić prywatność i bezpieczeństwo wielu systemów informatycznych.
Jako ciekawostkę należy dodać że 2/3 wartości n kluczy publicznych należy do wzoru 6y+1, a tylko 1/3 wartości n należy do zbioru 6x-1, ponieważ:
{(6x-1)*(6x-1)} ⊆ {6y+1}
{(6y+1)*(6y+1)} ⊆ {6y+1}
natomiast
{(6x-1)*(6y+1)} ⊆ {6x-1}
Czynnik pierwszy
Jak wiemy wartość n klucza publicznego zawsze należy do jednego ze zbiorów 6x-1 lub 6y+1. Używając podane powyżej wzory generujemy zbiór liczb do pierwiastka wartości n. Wygenerujemy zatem tylko ~26,66% liczb naturalnych mniejszych od √n. Jedna z wygenerowanych liczb będzie zawsze odpowiadać wartości p lub q.
Przykład
Mamy wartość n=1037. Obliczamy √1037 = ~32.
Użyjemy teraz liczb z omawianych wzorów które są mniejsze od 32. Oto liczby wygenerowane z tych wzorów: 7, 11, 13, 17, 19, 23, 29, 31.
Wiemy że jedna z tych liczb na pewno jest wartością n. Obliczymy szybko że to właśnie liczba 17 jest dzielnikiem liczby 1037. Zatem drugi czynnik wynosi 61, gdyż:
1037 / 17 = 61
Jak widzimy przy zastosowaniu tej metody użyliśmy tylko 7, 11, 13 i 17, czyli cztery pierwsze liczby ze wzorów 6x-1 oraz 6y+1. W teorii byliśmy przygotowani na maksymalne użycie 8 wygenerowanych liczb z możliwych 32 liczb naturalnych, by znaleźć jeden czynnik pierwszy. W praktyce użyliśmy pierwsze 4 wygenerowane liczby, z 17 możliwych liczb naturalnych, by w końcu trafić na jeden z czynników p lub q.
Moglibyśmy też zaryzykować i użyć tylko jednego zbioru liczb. Przy odrobinie szczęścia użylibyśmy tylko ~13,33% wszystkich liczb naturalnych mniejszych od √n i przyśpieszyli proces faktoryzacji o połowę.
Baza danych
Kolejne zagrożenie leży w tym iż istnieje możliwość wygenerowania bazy danych z gotową faktoryzacją n. Używając formuł 6x-1 oraz 6y+1 można wyeliminować ~73,33% wszystkich liczb naturalnych, które nie mogą być wartościami p i q, co znacznie ułatwia pracę potencjalnemu atakującemu.
Jeśli atakujący napisze skrypt który pomnoży każdą liczbę otrzymaną ze wzorów 6y+1 i 6x-1 przez każdą inną liczbę z tych wzorów, w tym również przez siebie samą, następnie w bazie danych zapisze te wartości z informacją jakie liczby pierwsze stworzyły konkretną wartość n klucza publicznego, będzie on posiadał gotową bazę danych z faktoryzacją wartości n z algorytmu RSA.
Atakujący w celu optymalizacji czasu i zasobów zapewne wygeneruje taką bazę danych od zakresu liczb w którym znajduje się jedna z wartości p lub q tylko do zakresu wartości n. Obliczenie wartość φ(n) oraz zastosowanie prostego algorytmu odwracania modularnego pozwoli atakującemu w efektywny sposób obliczyć wartość d klucza prywatnego.
Kwestią jest tylko moc obliczeniowa i czas potrzebny do wygenerowania takiej bazy danych, ale warto wziąć pod uwagę fakt iż jeśli taka baza danych zostanie wygenerowana chociażby jeden raz, to wtedy nastąpi koniec ery szyfrowania RSA. Jednym z rozwiązań tego problemu jest zmiana sposobu szyfrowania na inny który nie jest tak podatny na ataki z wykorzystaniem takich metod. Oczywiście na dzień dzisiejszy bez powszechnej dostępności technologii i komputerów kwantowych stanowi to poważne zagrożenie jeśli atakujący będzie w posiadaniu odpowiedniej mocy obliczeniowej i zasobów finansowych.
Ten artykuł jest dostępny także w języku angielskim, kliknij tutaj.