Odzyskanie klucza prywatnego do RSA-512. Klucz publiczny + 4 dni + ten poradnik = klucz prywatny.

Niby dużo osób wie że RSA-512 (chodzi o 512 bitów) już dawno temu został złamany, a chyba najlepszym publicznym wynikiem jest złamanie RSA-829.

Gadu, gadu, ale jak konkretnie na podstawie tylko klucza publicznego odzyskać klucz prywatny? Jakich narzędzi użyć?

Poradnik krok po kroku dostępny jest tutaj.

Autor zaczyna po prostu od wygenerowania testowej pary kluczy i bierze na warsztat klucz publiczny:

$ openssl genrsa -out keypair.pem 512
$ openssl rsa -in keypair.pem -pubout -out pubkey.pub

Sam klucz zapisany szesnastkowo wygląda tak (trzeba go skonwertować na liczbę w formacie dziesiętnym):

Później używa narzędzia CADO-NFS:

CADO-NFS is a complete implementation in C/C++ of the Number Field Sieve (NFS) algorithm for factoring integers and computing discrete logarithms in finite fields. It consists in various programs corresponding to all the phases of the algorithm, and a general script that runs them, possibly in parallel over a network of computers.

Czyli:

$ python3 ./cado-nfs.py 13256042284593353982685386592904581600931188946182985378120493025350646620349861342499533434006337407427902755435001220152736225750695462704353038966535639

Po czterech dniach (maszyna z jednym 6-corowym procesorem AMD Ryzen 5 3600 + 64GB RAM):

Mając faktoryzację wystarczy wygenerować klucz prostym skrypcikiem (który autor namierzył na IRC-u – #crypto). Efekt?

Wnioski? Używajcie minimum RSA-2048. Ta rekomendacja jest już ze sporym zapasem, bowiem wspominane wcześniej złamanie RSA-829 wymagało dość dużej mocy obliczeniowej:

The total computation time was roughly 2700 core-years, using Intel Xeon Gold 6130 CPUs as a reference (2.1GHz):

~Michał Sajdak