Znajdujesz się w: oGet.pl » Aktualności » RSA znów pokonane: udana faktoryzacja 768-bitowych kluczy

RSA znów pokonane: udana faktoryzacja 768-bitowych kluczy

8 styczeń 2010, 20:40

Faktoryzacja 768-bitowej, liczącej 232 cyfry liczby, którą wzięto z nieaktualnej już listy konkursu RSA Challenge (listy dużych, pseudopierwszych liczb, przedstawionej w 1991 roku wraz z nagrodami pieniężnymi za ich rozłożenie) została dokonana dzięki algorytmowi rozkładu liczb na czynniki pierwsze, znanemu jako number field sieve – ogólne sito ciała liczbowego.

Za pomocą tego algorytmu wcześniej udało się poradzić z liczbami RSA-576 (174 cyfry dziesiętne) i RSA-640 (193 cyfry dziesiętne). Specjalistom udało się w końcu osiągnąć sukces i złamać RSA-768 12 grudnia 2009 roku. Pobito w ten sposób rekord innego zespołu, który w maju 2005 roku złamał RSA-663.


„To krok milowy dla kryptografii, niepodważalny dowód na to, że klucze 768-bitowe są niewystarczające. Bardzo interesujący sposób na podsumowanie dekady” – stwierdził Benjamin Jun, wiceprezes firmy Cryptography Research.

Faktoryzacja RSA-768 zajęła 2,5 roku pracy setek komputerów PC (dla porównania, złamanie RSA-640 zajęło niecałe pół roku pracy). Pierwsze sześć miesięcy zeszło badaczom na wyborze wielomianów, następne dwa lata zajęło przesiewanie liczb. Jak oceniają autorzy, aby powtórzyć ten wynik na komputerze z jednordzeniowym procesorem Opteron 2,2 GHz i 2 GB RAM, „trzeba byłoby przeznaczyć na to 1500 lat”.

Autorzy twierdzą, że z czysto praktycznego punktu widzenia, złamanie klucza nie powinno być problemem, ponieważ klucze RSA-768 i tak powinny zostać wycofane do końca 2010 roku. Jednak Nate Lawson, kryptograf z firmy Root Labs stwierdził, że klucze takie nie znikną z rynku tak szybko – będą wykorzystywane przez mniejsze urządzenia, którym brak mocy obliczeniowej, aby radzić sobie z większymi liczbami.

Jak oceniają specjaliści, złamanie 768-bitowego klucza było „kilka tysięcy razy trudniejsze”, niż złamanie klucza 512-bitowego. Faktoryzacja RSA-1024 ma być jakieś tysiąc razy trudniejsza niż w wypadku ostatniego sukcesu – ale powinna być możliwa w przeciągu najbliższego dziesięciolecia.

Więcej na: webhosting.pl...