Matematyczna Luka w Algorytmach Szyfrujących

---

Zła wiadomość, proszę Państwa, bezpieczeństwo internetowych transakcji handlowych i międzynarodowej komunikacji cyfrowej zagrożone.

Matematycy z ośrodków badawczych w Stanach Zjednoczonych i Szwajcarii odkryli istotny błąd w powszechnie stosowanych algorytmach do cyfrowych zabezpieczeń (zwanych “RSA”).

Większość takich algorytmów wykorzystuje wielkie i losowo generowane liczby pierwsze do tworzenia kluczy autoryzujących np. internetowe transakcje.

W swojej opublikowanej 14 lutego naukowej publikacji matematycy wykazali, że znacząca liczba tych właśnie liczb pierwszych nie jest wcale losowa, co stwarza olbrzymie zagrożenie dla opartych na nich kluczy.

Nie wnikali też w swojej pracy w przyczyny takiego stanu rzeczy (oczywiście z generowaniem “zupełnie”  losowych liczb jest zawsze problem).

Algorytm Euklidesa

Prof James P. Hughes wraz z kolegami użyli zwykłego, znanego nam z podstawówki (!) algorytmu Euklidesa do rozkładu liczb na czynniki. Wykazali, że 12720 na 6 400 000 przebadanych kluczy o długości 1024 bitów miało tą samą wielką liczbę pierwszą jako czynnik. Daje nam to 0.2%, a to o wiele ZA DUŻO na to, żeby mógł to być czysty przypadek.

Badania podważają wynalezioną w 1978 roku, a stosowaną publicznie od 2000 metodę szyfrowania zwaną RSA.

Można więc w uproszczeniu powiedzieć, że 99,8% światowych transakcji internetowych jest bezpiecznych i wydaje się, że to całkiem dużo, ale pomyślmy, że dokonuje się ich około pół miliona dziennie i widać skalę problemu.

Naukowcy byli zszokowani prostotą metod (przypominam, że chodzi o algorytm z podstawówki), które użyli do swoich odkryć. Ciężko im uwierzyć, że problem jest nowością dla “agencji i znanych z zainteresowania tego typu kwestiami stron”, jak żartobliwie piszą w swojej publikacji.

W kluczach RSA 2048-bitowych również pojawia się problem braku losowości, choć na mniejszą skalę.

Jednak występuje on tylko w algorytmach RSA, wynalezionych m.in. przez Rona Rivesta, a nie w innych algorytmach (dlatego matematycy zatytuowali swoją publikację “Ron był w błędzie, Whit ma rację”).

Więcej o sprawie znajdziecie w artykule, na którym głównie bazowałem:

Hidden flaw jeopardizes millions of online transactions (ang.)

A więcej technicznych szczegółów tutaj (ta instytucja razem z New York Timesem pierwsza zabiła na alarm):

Researchers Use EFF’s SSL Observatory To Discover Widespread Cryptographic Vulnerabilities (ang.)

No i oczywiście u źródła, czyli w samej publikacji matematyków:

Ron był w błędzie, Whit ma rację (ang.)

A więcej o szyfrowaniu algorytmem RSA w tej pracy w języku polskim:

Przełamywanie szyfru RSA