Za kilka lat czeka nas kryptokalipsa? Matematycy i hakerzy wierzą w możliwość złamania algorytmu RSA

Gdy w latach 70 zeszłego stulecia Ron Rivest, Adi Shamir iLeonard Adleman (wszyscy z MIT) przedstawili algorytm RSA – pierwszą praktyczną implementację systemu szyfrowania na bazieklucza publicznego, a mniej więcej w tym samym czasie WhitfieldDiffie i Martin Hellman pokazali, jak bezpiecznie wymieniać kluczekryptograficzne, wydawało się, że ludzkość dokonała wielkiegopostępu. Oto zyskaliśmy system szyfrowania, który mimo całkowitejotwartości miał być całkowicie bezpieczny, jego bezpieczeństwogwarantowała sama matematyka, trudność faktoryzacji dużych liczbzłożonych. Z perspektywy typowego internetowego hakera czy kryptoanalitykapracującego w jednej z agencji wywiadowczych, algorytmy RSA czy Diffiego-Hellmana wyglądają naprawdę solidnie, a możliwym siłowym atakom (do tejpory największym kluczem, jaki został rozłożony na czynnikipierwsze, jest klucz 768-bitowy – nastąpiło to na przełomie 2009i 2010 roku) łatwo zaradzić, zwiększając długość klucza (to,jak długość klucza wpływa na odporność na atak, można zobaczyćna stronie www.keylength.com).Rozważania na temat możliwych słabości kryptograficznychalgorytmów prowadzone były przede wszystkim w kręgachakademickich, a wiedza z hermetycznego świata matematyków nieprzenika wcale łatwo do świata praktyków (zapewne głównie zewzględu na poziom trudności matematycznego dyskursu– przepaśćmiędzy matematyką, a dziedzinami w których elementy Królowej Naukznajdują zastosowanie pogłębia się z roku na rok).[img=crypto-opener]Niektórzy spośród ludzi zajmujących się bezpieczeństwem ITpodejmują wysiłek, by przyjrzeć się osiągnięciom akademickiegoświata. Wśród nich jest Alex Stamos, dyrektor techniczny firmyArtemis, który podczas ostatniej konferencji Black Hat przedstawiłzebranym stan badań nad technikami szyfrowania stosowanymi wInternecie. Ostrzegł, że istnieje realna szansa na to, że w ciągunajbliższych czterech czy pięciu lat, algorytmy RSA iDiffiego-Hellmana przestaną się nadawać do szyfrowania, a todoprowadzi do całkowitego załamania się mechanizmów zaufania wInternecie.Stamos nie przesadza – towłaśnie kryptografia klucza publicznego i bezpieczne systemywymiany kluczy zabezpieczają elektroniczną bankowość, umożliwiająwysyłanie poufnych e-maili, czy zdalne aktualizowanie systemówoperacyjnych. Jednak z prac francuskiego matematyka Anoine'a Jouxawynika, że cały ten kryptosystem okaże się trywialnie łatwy dozłamania. Poświęcone tejkwestii prace opublikowane zostały na początku 2013 roku.Dotyczą znajdywania logarytmudyskretnego, dziś uważanego za problem trudny, przez coprzekonani do tej pory jesteśmy, że szybkie odszyfrowanie danychnie jest możliwe bez klucza użytego do zaszyfrowania – albowykorzystania pracujących przez dziesiątki lat superkomputerów,realizujących algorytm ogólnegosita ciała liczbowego. A jednak z prac Jouxa wynika, że powinny istnieć algorytmyznacznie efektywniejsze niż dziś stosowany do znajdywania logarytmudyskretnego algorytm Pohliga-Hellmana, radzący sobie szybko jedyniez kryptosystemami, które wykorzystują niewielkie liczby pierwsze.Przez 25 lat prac praktycznie nie poczyniono w tej sprawie żadnegopostępu, ale teraz może się to zmienić, tym bardziej że metodywykorzystane przez francuskiego matematyka nie są zupełnie nieznane– po prostu nie stosowano ich wcześniej wobec tych szyfrów.Jarved Samuel, kryptograf pracujący dla firmy ISEC Partner ocenił,że osiągnięcia Jouxa pozwolą innym badaczom przyjrzeć sięzagadnieniu bliżej, przynosząc dalszy postęp.Wydaje się, że poważni gracze przeczuwają już schyłekkryptografii bazującej na liczbach pierwszych. Dowodem na to możebyć zachowanie amerykańskiej Agencji Bezpieczeństwa Narodowego(NSA), która wydała już w 2005 roku SuiteB, oficjalnie rekomendowany zestaw algorytmów do zabezpieczaniainformacji w biznesie. Usunięto z niego wcześniej rekomendowanealgorytmy RSA i Diffiego-Hellmana, zastępując je algorytmamikryptografii na bazie krzywych eliptycznych. Podejrzewa się, że tosamo dotyczy zestawu SuiteA, wykorzystywanego do zabezpieczania informacji o najwyższympoziomie tajności, dotyczących nomen omen, bezpieczeństwanarodowego, i o którym oficjalnie prawie nic nie wiadomo.Ta grupa technik kryptografii rozwijana jest od 1985 roku i swojebezpieczeństwo opiera na złożoności obliczeniowej dyskretnychlogarytmów na krzywycheliptycznych (ECC). Algorytmy wykorzystujące krzywe eliptycznesą bardzo szybkie, pozwalają na stosowanie relatywnie niedługichkluczy (256-bitowy klucz ECC jest równoważny mniej więcej3072-bitowemu kluczowi RSA), a najlepsze algorytmy do ich łamania(np. algorytm rhoPollarda) są znacząco mniej wydajne od algorytmówwykorzystywanych przeciwko RSA.Nie tylko NSA sięga po krzywe eliptyczne, nawet w naszym krajukilka lat temu zrobiło się o nich głośno w mass-mediach, z okazjinagrodzenia budowanego przez zespół prof. Gawineckiego „narodowegoszyfratora”. Można by się więc spodziewać, że przejściena nowe techniki kryptograficzne nastąpi wręcz automatycznie –ale wcale to nie jest takie pewne. Problem tkwi w patentachdotyczącychECC, należących do firmy Certicom, która zaimplementowała jejako pierwsze. Należący obecnie do BlackBerry Certicom nie mazamiaru rozdawać je za darmo. Nawet federalna administracja USAmusiała wykupić licencje na stosowanie algorytmów zalecanych wSuite B. Gdy Sony wykorzystało ECC w swoich odtwarzaczach Blu-ray,jednocześnie próbując unieważnić część patentów Certicom,sprawa skończyła się sądową ugodą, a Japończycy musieli zalicencje zapłacić.Niektórzy eksperci są przekonani, że jedyną szansą nauniknięcie katastrofy kryptograficznej jest więc unieważnieniepatentów Certicomu, przeprowadzone przez samą administracjęamerykańską. To wymagałoby jednak zmian w prawie, któreuderzałyby w interesy posiadaczy wartych miliardy patentowychportfolio – nie można przecież wydać ustawy, która unieważniapo prostu patenty jednej firmy. Jeśli jednak nawet do zmian w prawiepatentowym dojdzie, to trzeba pamiętać o tym, że tzw. biznesowe ITjest wyjątkowo mało zwinne, a wdrażanie nowych technologii zajmujetam całe lata. O ile opensource'owe społeczności, agencjewywiadowcze czy najlepsze firmy programistyczne z przejściem na ECCsobie poradzą szybko, to inni będą mieli znacznie gorzej.AktualizacjaNiestety oryginalny link zpracami francuskiego matematyka nie działa, ale udało się nam znaleźć inne ich źródła:Anew index calculus algorithm with complexity L(1=4 + o(1)) in smallcharacteristicAquasi-polynomial algorithm for discrete logarithm in finitefields of small characteristic