Naukowcy z Francji złamali najbardziej skomplikowany algorytm kryptograficzny, który do tej pory próbowano rozszyfrować. Wykorzystali w tym celu kilka komputerów pracujących jednocześnie na całym świecie, aby zamienić 35 milionów godzin obliczeniowych na bardziej realistyczne ramy czasowe.
Metoda szyfrowania, którą badacze zastosowali do wygenerowania problemu do rozwiązania, nazywa się algorytmem RSA. W jego przypadku dwie strony szyfrują informacje, używając niesamowicie dużej liczby utworzonej przez pomnożenie dwóch liczb pierwszych.
Szczególną cechą szyfrowania liczb pierwszych jest to, że iloczyn dwóch liczb pierwszych jest unikalny. Tworzą one specjalną klasę liczb zwanych półpierwszymi. Ponieważ 2 jest technicznie liczbą pierwszą i jedyną parzystą tego typu, każdy liczba półpierwsza 2 razy większa od liczby pierwszej byłaby parzysta, co czyni ją bardzo prostą do rozwiązania.
Liczby, których badacze używali do wykonania wielowątkowych obliczeń, zawierały 240 cyfr i istnieje nieskończona ilość liczb pierwszych, których w przyszłości mogą użyć kryptografowie.
Uruchamiając zaprogramowane algorytmy, komputery mogą próbować nowych kombinacji aż do uzyskania prawidłowej odpowiedzi. Uruchomienie tylko kandydatów w postaci liczb pierwszych zawęża pole znacznie, ale 4 z 9 miliardów potencjalnych 10-cyfrowych liczb jest pierwszymi, co oznacza 360 000 000 liczb pierwszych do sprawdzenia. Każda dodatkowa cyfra mnoży pulę przez 10.
Tym samym fakt, który sprawia, że szyfrowanie RSA jest matematycznie zniechęcające, czyni je zniechęcającym również dla hakerów. A sama jego złożoność jest powodem, dla którego produkty szyfrowania RSA mogą być udostępniane otwarcie, ponieważ dzielenie gigantycznych liczb jest kolejnym wyzwaniem.
Francuscy naukowcy pobili poprzedni rekord zarówno pod względem złożoności, jak i czasu, rozwiązując 240-cyfrowy kod w czasie krótszym niż ten, który był potrzebny do odkodowania 232-cyfrowego. Co ciekawe, nawet ta gigantyczna liczba, z kluczem kryptograficznym o długości 795 bitów, stanowi nieco ponad jedną trzecią 2048-bitowego szyfrowania używanego przez większość komputerów.
