Konkursy RSA

RSA – firma, która na co dzień zajmuje się pisaniem oprogramowania szyfrującego przeprowadza liczne konkursy, w których nagrody sięgają nawet 200.000 $. Nie trzeba wiele, by zdobyć te pieniądze. Wystarczy trochę sprytu i umiejętność szybkiego liczenia. Naprawdę szybkiego liczenia.

Jedno z zadań jest, wydawałoby się, bajecznie proste. Trzeba rozłożyć zadaną liczbę na czynniki pierwsze, czyli dokonać jej faktoryzacji. Co to znaczy? Liczba pierwsza to taka liczba, która dzieli się tylko przez 1 i przez samą siebie. Na przykład 7, 11, 23 itp. Udowodniono (już dawno temu), że każda liczba naturalna ma tylko jeden rozkład na czynniki pierwsze, czyli właśnie liczby pierwsze, z dokładnością do kolejności. I tak na przykład 2618=2*7*11*17. Inaczej tej liczby nie da się rozłożyć na czynniki pierwsze, najwyżej możemy je poprzestawiać (bo mnożenie jest przemienne).

Tego właśnie oczekuje RSA. Za rozłożenie liczby o długości 617 cyfr oferuje 200 tys. dol. Dla mniej ambitnych przewidziano mniejsze nagrody – liczba o zaledwie 174 cyfrach wyceniana jest na 10 tys. dol. Gdy tylko RSA zweryfikuje poprawność rozkładu, natychmiast wypłaca nagrodę w gotówce.

Gdzie jest kruczek? Otóż faktoryzacja jest bardzo czasochłonna. Istnieją różne efektywne algorytmy, ale mimo to nie ma na świecie komputera, który poradziłby sobie z tym w rozsądnym czasie. A na pewno nie ma komputera wartego mniej niż owe 200 tys. dol. To czyni zadanie wysoce niepraktycznym. Te zadania mają uzmysłowić opinii publicznej, jak trudno jest złamać szyfry stosowane współcześnie, choćby w czasie wymiany informacji z naszym bankiem internetowym. Część algorytmów szyfrujących wykorzystuje właśnie fakt, że łatwo jest pomnożyć przez siebie dwie duże liczby pierwsze, natomiast niezwykle trudno jest sfaktoryzować wynik, jeśli nie znamy czynników wyjściowych.

Nie znaczy to, że zadanie jest w ogóle niewykonalne. W zeszłym miesiącu RSA wypłaciło 10 tys. dol. nagrody za zwycięstwo w innym konkursie – szukaniu 64 bitowego klucza, którym zaszyfrowano wiadomość, używając algorytmu DES (stosowanego m.in. w telekomunikacji). Nagrodę zdobyła firma distributed.net, która gromadzi rzesze ochotników skłonnych poświęcić wolny czas swoich komputerów dla dobra nauki.

Więcej na gazeta.pl

Zobacz również: rsasecurity.com [RSA]