Faktoryzacja

[Piterniel]

Pomóż w rozkodowaniu seca 2!

Więcej tutaj >>TU<<

Faktoryzacja za pomocą masowej równoległości?

Około rok temu Daniel Bernstein z Uniwersytetu Illinois w Chicago opublikował fragment swojego wniosku o grant National Science Foundation, odpowiednika naszego KBN, w postaci artykułu zatytułowanego Circuits for Integer Factorization: A Proposal. Artykuł wywołał serię alarmistycznych apeli na e-maliowych listach dyskusyjnych wzywających do zaniechania używania kluczy 1024-bitowych, a nawet 1536-bitowych, w kryptosystemie RSA, oraz sensacyjne artykuły w prasie na temat "odkrycia Bernsteina". W artykule przedstawiony jest pomysł na sprzętową konstrukcję urządzenia (maszyny, komputera), które mogłoby dokonywać faktoryzacji, czyli rozkładać na czynniki pierwsze liczby całkowite trzykrotnie dłuższe niż dziś, ale w porównywalnym czasie. Po dokładnym zapoznaniu się z tą publikacją okazuje się jednak, że pomysł ten jest bardzo daleki od realizacji. Takiej maszyny nie ma i nie widać realnej perspektywy skonstruowania jej wcześniej niż za 25-30 lat, czyli w dającej się przewidzieć przyszłości.

Najważniejsze tezy pracy sam autor sformułował jako pytania badawcze - czy to możliwe?, ile to by kosztowało?, itp. Pomysł sprowadza się do zbudowania komputera, o tak wielkiej liczbie równolegle (jednocześnie) wykonywanych operacji, że jest to nierealne na dziś. I nie wiadomo, kiedy może stać się realne.

Propozycja Bernsteina nie wnosi zasadniczych zmian do ogólnej idei metod rozkładu liczb na czynniki pierwsze. Trzeba najpierw zbudować "bazę" przykładów, z natury rzeczy można to robić współbieżnie, a następnie wykonać obliczenia na dużych macierzach. Te ostatnie obliczenia słabo poddają się uwspółbieżnieniu. Wielkość bazy jest sprawą kompromisu tak, by żaden z dwu kroków algorytmu nie okazał się wąskim gardłem. Propozycja Bernsteina sprowadza się do rozważenia możliwości zastosowania masowej równoległości w algorytmie sortowania, co ma zasadnicze znaczenie dla obliczeń na macierzach. Zmienia się w ten sposób proporcja kompromisowej wielkości bazy.

I tak, w pierwszym kroku algorytmu proponowanego przez Bernsteina trzeba "zbadać" 223 krzywych eliptycznych w przypadku RSA-768, albo 232 krzywych dla RSA-1024, albo 242 krzywych dla RSA-1536. (RSA-X oznacza problem łamania algorytmu RSA z zastosowanym kluczem długości X bitów.) Bernstein proponuje wykonywanie tego przy pomocy około 25 mln procesorów działających równolegle.

W drugim kroku stosuje masowo równoległy algorytm sortowania. Bardzo szybki. Sortujący m2 liczb całkowitych w czasie liniowym O(m) z niewielką stałą. Ale za to wymagający sprzętowej tzw. "aktywnej pamięci" złożonej z komórek samodzielnie wykonujących porównywanie i zamianę zawartości komórek. W pamięci tej komórki liczbowe leżą na siatce kwadratowej i mogą porównywać się, a w razie potrzeby zamieniać zawartością, z komórkami sąsiednimi. To bardzo proste operacje. Ale już w przypadku RSA-1024, potrzeba tych komórek 50 miliardów.

Architektura komputera z masową równoległością, nawet dla bardzo prostych operacji, ale dla tak ogromnej liczby procesorów, jest zagadnieniem o stopniu trudności daleko wykraczającym poza granice obecnego stanu wiedzy i możliwości technologicznych. Połączenie odpowiednimi przeplotami przewodów tak wielkiej ilości procesorów, zapewnienie ich wzajemnego komunikowania się, reagowania na komendy, przyjmowania danych wejściowych i zwracania wyników na zewnątrz do odpowiednich innych procesorów, wreszcie zasilanie i chłodzenie takiego układu, NIE jest możliwe do realizacji obecnie. Idea budowy takiego urządzenia wyprzedza obecne komputery o kilka generacji.

Największym obecnie osiągnięciem w tej dziedzinie jest blisko 10 tys. procesorów (dokładnie 9632) działających równolegle w systemie ASCI Red firmy INTEL zainstalowanym w laboratorium Sandia National Laboratories. Drugi w kolejności system, ASCI White firmy IBM, ma 8192 procesory i zainstalowany jest w Lawrence Livermore National Laboratory w USA. (Patrz http://www.top500.org/list/2002/06/). Trzeci z kolei, bo zawierający "tylko" 5120 procesorów system Earth Simulator wyprodukowany został w kwietniu 2002 przez japońska firmę NEC dla Earth Simulator Centre w Jokohamie w Japonii. Oparty jest na zupełnie nowej technologii tzw. procesorów wektorowych. Zajmuje dwa piętra budynku, każde o wymiarach 50 na 60 m. Według specjalistów z tej dziedziny, w najbliższych latach mogą pojawić się systemy mające 15, a może 20 tys. procesorów działających równolegle.

Obecnie granicą możliwości w dziedzinie faktoryzacji jest - będące w zasięgu możliwości dużych firm i potężnych agend rządowych - łamanie algorytmu RSA z kluczem 512-bitowym. W sierpniu 1999 r. świat nauki, i nie tylko, zelektryzowała wiadomość ogłoszona w dość lakonicznym komunikacie http://www.rsasecurity.com/rsalabs/c...ng/rsa155.html, iż zespół naukowców rozłożył na czynniki pierwsze liczbę 512-bitową wygenerowaną zgodnie ze wszystkimi regułami kryptosystemu RSA. Liczba ta została podana w konkursie ogłoszonym właśnie w celu zbadania możliwości jej faktoryzacji. Ma ona 155 cyfr dziesiętnych:

10941738641570527421809707322040357612003732945449 2059909138421314763499842889
34784717997257891267332497625752899781833797076537 244027146743531593354333897

Jest iloczynem dwu liczb pierwszych 78-cyfrowych:

10263959282974110577205419657399167590071656780803 8066803341933521790711307779
*
10660348838016845482092722036001287867920795857598 9291522270608237193062808643

Znalezienie tych czynników zajęło 4 miesiące pracy. W marcu 2002, podczas Financial Cryptography Conference, firma nCipher Inc. ogłosiła, że opracowała oprogramowanie, które pozwala na złamanie 512-bitowego klucza RSA w czasie 6 tygodni przy użyciu komputerów dostępnych w pojedynczej firmie. Nieco później poprawiono czas do 1 doby.

Dalszy postęp wykorzystujący zwykły wzrost mocy obliczeniowej i szybkości coraz nowszych komputerów nie prowadzi do radykalnego przełomu. Konieczne w problemie faktoryzacji przeszukiwanie gigantycznie większych przestrzeni wymaga jakościowo nowych algorytmów.

Artykuł Bernsteina jest właśnie w tym nurcie badań. Choć nie wnosi nic nowego do praktycznej kryptografii, jest interesujący z punktu widzenia teorii algorytmów z masową równoległością. Od strony matematycznej, algorytm został zaakceptowany przez najlepszych w tej dziedzinie. Używa techniki sita ciał liczbowych oraz krzywych eliptycznych. Na implementację jednak poczekamy jeszcze wiele lat. [Cytat z B. Schneiera, http://www.counterpane.com, 15 marca, 2002: " (...) it will be years before anyone knows exactly whether, and how, this work will affect the actual factoring of practical numbers"].

Masowa równoległość jest też nadzieją kilku innych prób podejścia do problemu rozkładu liczb całkowitych na czynniki pierwsze, do epokowego przyspieszenia obliczeń w ogóle. Najgłośniejsze to obliczenia molekularne, model obliczeń Pauna (P-maszyny) i komputery kwantowe. Bernstein jest lepszy, naszym zdaniem, ponieważ wymaga "tylko" kwadratowo wiele procesorów pracujących równolegle, podczas gdy w tamtych próbach jest to de facto wykładniczo wiele w stosunku do danych wejściowych.

Według prognoz z najlepszych ośrodków badawczych, w instytutach, uniwersytetach i w wielkich firmach komputerowych, systemy RSA i DSA można uważać za wiarygodne (bezpieczne) przez co najmniej 25-30 następnych lat. Inną sprawą jest długość kluczy. Na dziś klucze 1024-bitowe w algorytmie RSA dają zadowalający poziom wiarygodności zabezpieczeń. W perspektywie będziemy stosować klucze dłuższe, 1536- czy 2048-bitowe. Niezbędne jest stałe monitorowanie postępów badań w tej dziedzinie. I elastyczne, dostatecznie szybkie wprowadzanie odpowiednich zmian w praktyce. Jednym z narzędzi monitoringu jest wspomniany już konkurs, a dokładniej wyzwanie, firmy RSA polegający na próbie rozkładu kolejnej dużej liczby, takiej jak te stosowane na co dzień w algorytmie RSA. Obecne wyzwanie firmy jest liczbą o 174 cyfrach dziesiętnych. Czytelnik może zechce spróbować swoich sił rozkładając na czynniki pierwsze liczbę:

18819881292060796383869723946165043980716356337941 7382700763356422988859715234665485319
06060650474304531738801130339671619969232120573403 1879550656996221305168759307650257059

* Pragniemy podziękować serdecznie doc. dr hab. Markowi Tudrujowi z IPIPAN za cenne konsultacje.