Amerykańskiej agencji szpiegowskiej NSA utrudnia życie rozwój nowoczesnej kryptografii. Nic więc dziwnego, że ta dziedzina stała się jednym z ważnych obszarów szpiegowskich działań. Kluczowe znaczenie dla kryptografii ma algorytm RSA. Aby zrozumieć ten problem, potrzebne jest wyjaśnienie pewnych elementarnych pojęć z dziedziny kryptografii.
Klasyczne szyfrowanie polegało na użyciu pewnego „klucza”. Najprostszy przykład: szyfrowanie liczb polega na dodaniu do niej 10, a deszyfracja na odjęciu 10. Liczba 10 jest w tym przykładzie kluczem. Bardziej złożonym przykładem jest szyfrowanie asymetryczne. Używa się w nim pary kluczy. Jeden służy do zaszyfrowania, a drugi do odszyfrowania. Na przykład możemy stosować jako algorytm szyfrowania operację dodawania, a parą kluczy jest liczba i jej odwrotność (w powyższym przykładzie 10 i -10). Ta zmiana (z jednego na dwa klucze) wydaje się nie wnosić niczego nowego. Jednak w praktyce tworzymy takie pary kluczy, by posiadając jeden z nich, nie można było łatwo wyliczyć jaki jest drugi klucz z pary.
Warunek ten spełnia szyfr wykładniczy. Polega na szyfrowaniu poprzez potęgowanie modulo n (^ oznacza potęgowanie):
C = M^e mod n
Mając daną wiadomość zaszyfrowaną (C) oraz klucz (e,n) nie potrafimy w łatwy sposób uzyskać wiadomości pierwotnej. Odszyfrowanie można wykonać poprzez potęgowanie używając innego wykładnika (klucza):
M=C^d mod n
Jest to możliwe jeśli powyższe równania są swoją odwrotnością (czyli pomnożenie ich daje w wyniku 1), albo inaczej mówiąc:
(M^e mod n) ^d mod n = M
Mamy więc parę kluczy: (e,n) i (d,n). Okazuje się, że jest ją stosunkowo łatwo znaleźć, gdy n jest iloczynem dwóch liczb pierwszych. Na tym właśnie polega algorytm RSA. Jego złamanie polega na odgadnięciu liczb pierwszych, które po pomnożeniu tworzą n. Problem faktoryzacji (podziału liczby na czynniki) jest łatwy dla małych liczb, ale ma złożoność wykładniczą. W internecie jest dostępna ciekawa praca magisterska poświęcona temu problemowi: „Algorytmy faktoryzacji w zastosowaniach kryptograficznych”.
Algorytm RSA opiera się więc na założeniu odpowiedniej wielkości kluczy (którą wyrażamy w bitach). Przy obecnych mocach komputerów za bezpieczny uznaje się klucz długości 2048 bitów. Taki klucz jest stosowany w podpisach elektronicznych. W systemach Linux standardem jest już klucz długości 4096 bitów.
Kilka lat temu pojawiła się informacja o poważnym zagrożeniu złamaniem algorytmu RSA:
Wydaje się, że poważni gracze przeczuwają już schyłek kryptografii bazującej na liczbach pierwszych. Dowodem na to może być zachowanie amerykańskiej Agencji Bezpieczeństwa Narodowego (NSA), która wydała już w 2005 roku Suite B, oficjalnie rekomendowany zestaw algorytmów do zabezpieczania informacji w biznesie. Usunięto z niego wcześniej rekomendowane algorytmy RSA i Diffiego-Hellmana, zastępując je algorytmami kryptografii na bazie krzywych eliptycznych. Podejrzewa się, że to samo dotyczy zestawu Suite A, wykorzystywanego do zabezpieczania informacji o najwyższym poziomie tajności, dotyczących nomen omen, bezpieczeństwa narodowego, i o którym oficjalnie prawie nic nie wiadomo.
Przyczyną zamieszania była praca pewnego francuskiego matematyka, opisująca efektywny algorytm dotyczący logarytmów dyskretnych. W teorii obliczeń często stosuje się redukcję jednego problemu do drugiego (istnieje dość pokaźna klasa problemów, które są sprowadzane jeden do drugiego – zob. problemy NP-zupełne). Gdyby więc udało się zredukować problem faktoryzacji do problemu logarytmów dyskretnych, a dla niego zaimplementować efektywny (o złożoności mniejszej niż wykładnicza) algorytm, to kryptografia oparta na algorytmie RSA byłaby zagrożona.
Ale redukcja problemu faktoryzacji do logarytmów dyskretnych jest problemem trudnym. Nie udowodniono też, że problem faktoryzacji jest NP-zupełny. Skąd więc ta panika?
Wspomniana wyżej kryptografia oparta na krzywych eliptycznych to po prostu inny sposób budowania kluczy asymetrycznych (alternatywa dla RSA). Problem w tym, że algorytmy te są opatentowane. Można więc było podejrzewać, że chodzi o biznes.
Jednak po ucieczce Snowdena okazało się, że NSA zapłaciło korporacji RSA $10mln za zbudowanie generatora dla kryptografii opartej na krzywych eliptycznych, który ułatwiałby włamania (Dual_EC_DRBG). W uproszczeniu: oprócz pary kluczy prywatnego i publicznego, dostajemy klucz dla NSA.
Uwaga! Należy zwrócić uwagę na zbieżność nazw algorytmu RSA i korporacji RSA. To dwa różne byty i nie wolno ich utożsamiać ze sobą.
Biorąc to wszystko pod uwagę, trudno uwierzyć, że pojawienie się szeregu publikacji podważających bezpieczeństwo RSA było przypadkowe. Przecież z informacji od Snowdena wynika coś dokładnie odwrotnego: NSA dokonywało ataków na systemy transmisji, starając się przechwycić informacje przed zaszyfrowaniem kluczem RSA, albo po odszyfrowaniu. Gdyby mieli sposób na złamanie klucza – nie wysilali by się tak.
Ciekawa jest reakcja korporacji RSA na te doniesienia. Oni stanowczo zaprzeczyli, że porozumienie z NSA było tajne! Współpraca z NSA ma oczywiście na celu podniesienie poziomu bezpieczeństwa!
Rozpoczęła się także osłona informacyjna, zgodnie z zasadą: jeśli złapią cię za rękę to udawaj, że to nie twoja ręka, a jeśli nie możesz – krzycz głośno 'łapać złodzieja'. W efekcie wytworzonej paniki pojawiło się między innymi żądanie, aby zmodyfikować algorytmy szyfrowania w jądrze Linuksa. Bo przecież Snowden ujawnił backdoor w Dual_EC_DRBG. Po pojawieniu się tego wniosku, ostro zareagował opiekujący się jądrem Linuksa jego twórca, Linus Torvalds. Zaczął od pytania, gdzie można wysłać petycję o wzrost IQ i wiedzy ludzi związanych z rozwojem jądra systemu. Kończy krótką odpowiedzią skierowaną do autora wniosku: jesteś ignorantem.
Cała ta historia potwierdza w całej rozciągłości tezę, że teorie spisku dobrze tłumaczą rzeczywistość, ale pod warunkiem, że ich formułowaniem zajmują się ludzie kompetentni. Zaś tropienie spisku przez ignorantów tworzy zasłonę dymną i ułatwia działanie spiskowcom.