NSA: kryptografia na krzywych eliptycznych nie ma przyszłości. Narodowy Szyfrator może trafić do lamusa

Kryptografia wykorzystująca krzywe eliptyczne od dawnaprzedstawiana była jako nasz zbawca, który pozwoli ocalić tajnośćdokumentów, gdy stary kryptosystemRSA będzie już z łatwością łamany przez superkomputeryprzyszłości. Nawet u nas w Polsce głośno było kilka lat opolskiej Enigmie, czyteż jak to oficjalnie nazwano „Narodowymszyfratorze”, budowanym przez matematyków z Wojskowej AkademiiTechnicznej, który miał wykorzystywać nowatorskie rozwiązaniez zakresu krzywych eliptycznych.Tymczasem amerykańska Agencja Bezpieczeństwa Narodowego ostrzega,by nie bawić się we wdrożenia takich kryptosystemów – zdaniemanalityków NSA bliski jest czas, gdy staną się one przestarzałewskutek pojawienia się komputerów kwantowych.

Ostrzeżenie NSA zelektryzowałospołeczność kryptologów. Przez ostatnie 20 lat agencja zajmującasię przecież nie tylko cyberszpiegowstwem, ale też ochronąamerykańskich systemów informatycznych przed szpiegami wrogami,propagowała kryptosystemy na bazie krzywych eliptycznych jakonajbezpieczeniejsze techniki szyfrowania asymetrycznego. Algorytmy jewykorzystujące znalazły się w tzw. Suite B, czyli zestawierekomendowanych technik szyfrowania do zastosowań w biznesie, orazjak wieści niosą, także w supertajnym Suite A, który obejmujetechniki wykorzystywane do zabezpieczania informacji kluczowych dlabezpieczeństwa narodowego.

W publicznym oświadczeniu, NSAoświadczyło tymczasem, że zamierza pomóc instytucjom federalnym istanowym oraz przedsiębiorstwom w przejściu na technikikryptograficzne odporne na ataki za pomocą komputerów kwantowych.We współpracy z uczelniami, organizacjami standaryzacyjnymi ifirmami zajmującymi się bezpieczeństwem rozpoczęte zostały pracenad stworzeniem nowego zestawu algorytmów, rozwijanych w otwarty iprzejrzysty sposób, które staną się podstawą kolejnego zestawuzalecanych kryptosystemów.

Póki co, korzystać należy ztych samych algorytmów co dotąd – AES 256, wymiana kluczyDiffiego-Hellmana z użyciem krzywej P-384, podpisy cyfrowe na baziekrzywych eliptycznych oraz RSA z kluczem 3072-bitowym. Tym jednak,którzy do tej pory nie wdrożyli Suite B, NSA zaleca powstrzymaćsię od tych działań i poczekać, aż gotowy będzie nowy zestawzalecanych algorytmów.

W 1939 roku Winston Churchill, mówiąco Związku Radzieckim, powiedział: to zagadka spowita tajemnicą,a wewnątrz enigma. Tymi właśnie słowami zaczyna się pracaznanych kryptografów Neala Koblitza i Alfreda Menezesa pt. ARiddle Wrapped in an Enigma, w której próbują oni co niecowydedukować z zaskakującego oświadczenia NSA. Miłośnicy twardejnauki mogą kręcić nosem, ale fani spiskowych teorii dziejów będązachwyceni – autorzy przekonani są, że sprawa ma drugie dno.

Zdaniem badaczy to wcale nieprzełomy w dziedzinie komputerów kwantowych są prawdziwym powodemdla odejścia od krzywych eliptycznych. Wszystko co wiemy o NSAsugeruje raczej, że organizacja w dziedzinie tej nie osiągnęłaniczego, co pozwoliłoby realnie zagrozić używanym dziśkryptosystemom. Nie wydaje też na badania nad informatyką kwantowąjakichś znaczących pieniędzy, najwyraźniej nie obawia się więcosiągnieć rosyjskich czy chińskich konkurentów.

Chodzić może o coś innego –otóż matematycy NSA mogliby być świadomi nieznanej powszechniesłabości kryptografii na bazie krzywych eliptycznych, która jednaknie zagraża „zwykłemu” RSA. Dotyczyć by ona miała złożonościobliczeniowej dyskretnych logarytmów na krzywych eliptycznych(ECDLP), uważanej dziś za tak dużą, że fizycznie niemożliwą dozłamania przy poprawnej implementacji algorytmu. Nigdy jednakformalnie nie udało się tego dowieść. Matthew Green, matematyk zJohn Hopkins University, komentującpracę Koblitza i Menezesa na swoim blogu zauważa, że odkrycia NSAnie muszą być przełomowe, wystarczy nawet skromny postęp wdziedzinie łamania ECDLP, by zagrozić całemu zbiorowikryptosystemów. A że takie skromne postępy mogły zostaćdokonane, świadczyć może niemal niezauważone obwieszczenie owycofaniu krzywej P-256, najmniejszej ze standardowych krzywych,zapewniającej odpowiednik 128-bitowego szyfrowania.

Możliwe są oczywiście teżinne teorie tłumaczące oświadczenie NSA, autorzy kontrowersyjnegoartykułu rozważają nawet scenariusze czysto politycznej natury.Długo jeszcze nie dowiemy się, jak było naprawdę. Pocieszajedynie, że nawet w sytuacji, gdy kryptografia na bazie krzywycheliptycznych upadnie, czy to z powodu odkrytych słabości ECDLP, czypojawienia się jednak komputerów kwantowych, to wciąż pod rękąmamy kryptografię na kratachi wykorzystujących gotowy już asymetryczny kryptosystem NTRU.