Czym są liczby pierwsze i dlaczego kryptografia tak chętnie z nich korzysta?
Liczby pierwsze są szeroko stosowane w kryptografii, ponieważ zapewniają większą szansę na utworzenie unikalnych wartości funkcji hashujących. Funkcje haszujące używają modulo, a użycie liczb złożonych (tj. innych niż pierwsze) zwiększa prawdopodobieństwo kolizji haszujących (tj. różnych danych wejściowych dających ten sam hash). Liczby pierwsze zwiększą szansę na utworzenie unikalnych wartości podczas haszowania w drodze pomnożenie wartości przez liczbę pierwszą. Na przykład, jeśli masz ciąg „Unblockchain”, pomnożenie każdej litery przez liczbę pierwszą, a następnie dodanie ich wszystkich da bardzo unikalną wartość skrótu.
W ten sam sposób liczby pierwsze są również używane do tworzenia kluczy prywatnych, które są szeroko stosowane w podpisywaniu transakcji i kryptograficznych algorytmach hashujących. W infrastrukturze klucza publicznego podpisy cyfrowe użytkowników są wykorzystywane do walidacji autentyczności podpisu transakcji, zapewniając bezpieczny sposób sprawdzenia, czy transakcja użytkownika została podpisana posiadanym przez niego kluczem prywatnym. Każdy może wysłać wiadomość przy użyciu klucza publicznego odbiorcy, ale tylko odbiorca będzie mógł otworzyć wiadomość za pomocą swojego klucza prywatnego.
Za każdym razem, gdy wysyłamy lub odbieramy transakcję w sieci Bitcoin (i prawie każdym innym blockchainie), używamy liczb losowych, które pomagają nam tworzyć duże liczby pierwsze, które są używane do tworzenia silnych i bezpiecznych kluczy prywatnych.
Co to jest liczba pierwsza?
Liczba pierwsza to taka, która dzieli się tylko przez 1 i siebie samą. Niektóre przykłady liczb pierwszych to: 1, 3, 5, 7, 11, 13, 17… i 89, 97, 8191. Największa znana liczba pierwsza to 2⁸² 589 933, która jest astronomicznie dużą liczbą – liczy sobie 24 862 048 cyfr.
Im wyższa liczba pierwsza, tym mniejsze prawdopodobieństwo jej znalezienia. Na przykład jest 25 liczb pierwszych z zakresu od 1 do 100, ale tylko 21 liczb pierwszych z zakresu od 100 do 200, 15 liczb pierwszych z zakresu od 200 do 300 oraz tylko 6 liczb pierwszych z zakresu od 10 000 do 10 100.
Już ponad 2000 lat temu Euklides udowodnił, że liczb pierwszych jest nieskończenie wiele. Chociaż sprawdzenie, czy mała liczba jest liczbą pierwszą, czy nie, jest łatwe, im większa jest liczba, tym trudniej jest sprawdzić, czy jest to liczba pierwsza. To, rzecz jasna, stanowi duże wyzwanie w matematyce i informatyce. Ponadto, im wyższy zakres liczb, tym mniejsze prawdopodobieństwo znalezienia liczby pierwszej i trudniejsze przeprowadzenie dowodu, czy rzeczywiście jest ona liczbą pierwszą. Przygotowanie wydajnego algorytmu weryfikacji liczb pierwszych jest niezwykle trudnym zadaniem.
Liczby pierwsze można w przybliżeniu obliczyć ze wzoru x/In(x), a gęstość liczb pierwszych: 1/In(x). Im większe X, tym dokładniejsza formuła.
Liczby pierwsze w kryptografii
Aby stworzyć silny klucz prywatny potrzebujemy 2 dużych liczb pierwszych oraz pewności, że te liczby pierwsze są bardzo trudne do odgadnięcia. Należy stworzyć dużą liczbę losową i sprawdzić, czy jest ona liczbą pierwszą.
Jak możemy sprawdzić, czy liczba jest liczbą pierwszą, czy też nie? Najbardziej bezpośrednim podejściem jest podzielenie liczby przez każdą liczbę, która jest od niej mniejsza. Jeśli nie jest podzielna przez żadną z nich, jest wówczas z pewnością liczbą pierwszą. Wypada przyznać, że jest to jednak procedura dość czaso- i pracochłonna.
Aby sprawdzić, czy liczba pierwsza jest liczbą pierwszą, czy nie, musimy zastosować jakiś sprawdzony test lub algorytm,. Podkreślmy raz jeszcze, że jeśli szukamy małej 6-cyfrowej liczby pierwszej, dość łatwo i szybko sprawdzić, czy 100699 jest liczbą pierwszą. Jeśli jednak szukamy dużych liczb pierwszych, powiedzmy, które mają więcej niż 1000 cyfr, praca zaczyna być „nieco” trudniejsza do wykonania.
Testy pierwszości w kryptografii — deterministyczne i probabilistyczne
Zasadniczo istnieją dwa sposoby obliczania liczby pierwszej. Jednym z nich jest użycie algorytmu deterministycznego, takiego jak dzielenie próbne (dzielenie liczby pierwszej przez wszystkie liczby przed nią, aby sprawdzić, czy przeprowadzenie dzielenia jest możliwe) lub twierdzenie Wilsona. Deterministyczny sposób oznacza, że będziemy w stanie stwierdzić, czy liczba jest liczbą pierwszą ze 100% dokładnością. Algorytmy deterministyczne są jednak wyjątkowo nieefektywne obliczeniowo.
Inną alternatywą na szybsze uzyskanie odpowiedzi jest sposób probabilistyczny, aczkolwiek nie potrafi określić ze 100% pewnością, że dana liczba jest liczbą pierwszą (choć umiarkowanie dokładna, nie daje 100% pewności).
Deterministyczne sposoby testowania liczby pierwszej są bardzo pracochłonne, ponieważ wymagają wielu obliczeń. Próbne dzielenie wymaga, aby n (liczba całkowita do sprawdzenia) zostało podzielone przez dowolną mniejszą liczbę. Procesowanie sprawdzenia twierdzeniem Wilsona wymaga również dużo energii. Działa to w następujący sposób: biorąc pod uwagę liczbę naturalną n> 1, jest ona liczbą pierwszą wtedy i tylko wtedy, gdy iloczyn wszystkich dodatnich liczb całkowitych mniejszych od n jest o jeden mniejszy od wielokrotności n.
Metoda Millera-Rabina jest metodą probabilistyczną, tzn. nie jest w 100% dokładna, ale jest wystarczająco dokładna dla większości algorytmów kryptograficznych. Większość systemów kryptograficznych używa testu pierwszości Millera-Rabina, aby określić, czy liczba jest (!)prawdopodobnie liczbą pierwszą, czy nie.
Metoda Millera-Rabina jest również szeroko stosowana w blockchainach do znajdowania liczb pierwszych. Jest częścią bibliotek Pythona i bogato udokumentowana na GitHub.