Kwantowy upiór NSA tańszy niż nowy myśliwiec 5 generacji

Kilka dni temu, akurat gdy próbowałem zorientować się, który to rok mamy, media zachłysnęły się kolejną wieścią z archiwum Snowdena. Niewielki miałem wówczas dostęp do Sieci, by bliżej sprawdzić, o co chodzi – ale nagłówki z głównych stron brzmiały pysznie: TVN24 informowało, że NSA chce mieć komputer, który (sic!) złamie wszystko, a Onet nieco powściągliwiej pisał, że NSA pracuje nad komputerem łamiącym większość zabezpieczeń. Samo źródło tych rewelacji, amerykański Washington Post, wspominało o wyścigu mającym na celu stworzenie maszyny o lata świetlne wyprzedzającej te, które używają zer i jedynek. Wszystko jasne – NSA wzięło się za magię (by zacytować trzecie prawo Clarke'a: Każda wystarczająco zaawansowana technologia jest nieodróżnialna od magii). Z magią jednak ten problem, że pełno w niej szarlatanów, którzy nie tylko nie mają żadnych mistycznych, cudownych mocy, ale też nawet wcale nie dążą do jakichś magicznych celów – często chodzi im o zamaskowanie rzeczy bardzo przyziemnych. Jak więc czaruje NSA?

Trochę ponudzę o fizyce i obliczeniach

Z komputerami kwantowymi mamy problem nie mniejszy niż doktorant fizyki z mechaniką kwantową (student problemu nie ma, bo musi tylko policzyć zadania na kolokwium, podczas gdy doktorant powinien pokazać, że coś już tych bra i ketów rozumie poza matematycznym formalizmem). Mimo że w zasadzie wszystko jest już jasne od strony teoretycznej, fizyczna realizacja układów utrzymujących sekwencję kwantowych superpozycji (złożeń) stanów kodujących informacje jest piekielnie trudna.

Jak pewnie wiecie, sam pojedynczy kubit niewiele informacji przechowa, lecz już maszyna mająca n kubitów może być jednocześnie w superpozycji do 2^n stanów. Ustawiając te kubity w określonym stanie wyjściowym i następnie przekształcają je sekwencją kwantowych bramek logicznych znanych jako algorytm kwantowy, przeprowadzane jest obliczenie, które kończy się pomiarem wszystkich stanów, prowadzącym do kolapsu każdego kubitu do jednego z dwóch klasycznych stanów. Co prawda większość algorytmów kwantowych zwraca poprawne odpowiedzi jedynie z pewnym prawdopodobieństwem, jednak poprzez zwielokrotnienie liczby cykli inicjalizacji, uruchomienia i pomiaru komputera kwantowego, prawdopodobieństwo to można zwiększać.

Prawie nikt by się komputerami kwantowymi pewnie nie interesował, gdyby nie to, że algorytmy kwantowe pozwalać mają na efektywne radzenie sobie z problemami, dla których nie istnieją efektywne algorytmy klasyczne – koronny przykład to np. rozkład dużych liczb na czynniki, będący jedynym znanym formalnym sposobem zaatakowania kryptografii z użyciem klucza publicznego RSA. Najlepszy algorytm klasyczny stosowany do tego celu, ogólne sito ciała liczbowego, ma oczywiście swoje sukcesy, ale jego realizacja jest bardzo kosztowna obliczeniowo – ludzie, którzy rozłożyli liczbę RSA200 (dwieście cyfr dziesiętnych, 663 bity) na dwie liczby pierwsze ocenili, że w przybliżeniu wymaga to 75 lat pracy procesora Opteron 2,2 GHz. Im dalej w las, tym gorzej – największa rozłożona liczba RSA‑768 (768 bitów, 232 cyfry dziesiętne) zająć by miała już 2000 lat pracy modelowego Opterona, jak zaś oceniają autorzy tego osiągnięcia, poradzenie sobie z RSA‑1024 (309 cyfr dziesiętnych) będzie przynajmniej tysiąckrotnie trudniejsze.

Mając komputer kwantowy można by tymczasem skorzystać z klasyczno-kwantowego algorytmu Shora, który działa w czasie wielomianowym, znacząco szybciej niż ogólne ciało sita liczbowego (działające w czasie podwykładniczym). Choć metafizyczne konsekwencje działania tego algorytmu są upiorne (fizyk David Deutsch twierdzi np., że maszyna kwantowa implementująca algorytm Shora, podczas rozkładu dużych liczb musi wykorzystywać znacznie więcej zasobów obliczeniowych, niż dostępne jest w naszym wszechświecie – czerpie je więc z wszechświatów równoległych), to jednak działa on przecież w praktyce. Pokazali to ludzie z IBM, rozkładając po raz pierwszy w 2001 roku, rozkładając na czynniki pierwsze liczbę 15, z użyciem 7‑kubitowej maszyny. 10 lat później, korzystając ze sprytnej sztuczki polegającej na zastąpieniu n‑kubitowego rejestru kontrolnego pojedynczym kubitem poddanym n‑krotnemu recyklingowi, udało się rozłożyć liczbę 21.

Niech nikt nie ma wątpliwości – od strony teoretycznej to niesamowite osiągnięcia, jest co podziwiać. Do porządnego łamania RSA, nie mówiąc już o innych algorytmach kryptograficznych, droga jeszcze jednak daleka, o ile w ogóle możliwa. Utrzymanie układów kwantowych w stanach koherentnych jest bardzo trudne z perspektywy fizyki doświadczalnej, wszelkie oddziaływania układu z otoczeniem zakłócają jego ewolucję i niszczą zakodowaną informację, więc czas w jakim można wykonać algorytm jest krótki. Różne fajne pomysły na przedłużenie czasu życia kubitów, takie jak wnęki rezonansowe, czy pułapki jonowe mają zaś inny problem – nie bardzo jest jak łączyć takie reprezentacje kubitów w większe układy.

Tak więc dziś w praktyce stoimy w sytuacji, w której o ile wiadomo jak przygotować układ kwantowy, to zrealizowanie na nim określonej logiki (czyli kontrolowanego poddawania układu zewnętrznym zaburzeniom) jest ogromnie trudne. Jeśli jednak w jakiś cudowny sposób ten etap ewoluowania układu kwantowego zostanie zrealizowany, to pojawia się jeszcze większy problem – trzeba będzie odczytać informację z wyjściowego stanu kwantowego. Przewidzieć wyniku pomiaru układu znajdującego się w superpozycji się nie da, każdy pomiar niekontrolowanie zmienia stan układu, a pomiarów takich trzeba do wydobycia pełnej informacji wykonać całkiem sporo. Jeśli by ktoś chciał przed pomiarem zrobić backup układu kwantowego, to obrzydzi mu życie twierdzenie o nieklonowaniu, według którego stanu układu kwantowego skopiować nie można – zostaje on zniszczony w czasie kopiowania.

80 mln dolarów, czyli jeden myśliwiec nowej generacji

Są oczywiście teoretyczne pomysły na rozwiązanie tych technicznych bądź co bądź kwestii, ale moim zdaniem laika, wątpię byśmy zobaczyli je w tym stuleciu (choć jacyś specjaliści mają twierdzić, że stanie się to już w tej dekadzie). IMHO w najlepszym razie komputerami kwantowymi będą maszyny podobne do tych robionych dziś przez D‑Wave, wykorzystujące efekty wyżarzania kwantowego do rozwiązywania pewnej klasy problemów optymalizacyjnych – i to wszystko, co uda się zrobić na skalę przemysłową, kosztem miliardów, dziesiątków miliardów dolarów.

Tymczasem straszne nagłówki z TVN24 czy Onetu przesłaniają znacznie skromniejsze realia prac badawczych. Na badania w dziedzinie komputerów kwantowych NSA poświęcić miało raptem część niespełna 80‑milionowego budżetu projektu o nazwie „Penetrating Hard Targets”, zaś w roku fiskalnym 2013 zademonstrowane miało zostać wykorzystanie raptem 2‑kubitowego systemu. Spora część tych pieniędzy poszła też na inne zagadnienia, takie jak badania nad komunikacją kwantową i jej bezpieczeństwem. Poziom subtelności i wyrafinowania technicznego NSA w tej dziedzinie najlepiej demonstruje zaś chyba wykorzystanie ogromnych klatek Faradaya do ochrony budowanych maszyn kwantowych przed zewnętrznymi zakłóceniami – XIX‑wieczne rozwiązania rodem z pracowni fizycznej II. Wygląda na to, że i przemysł i świat akademicki wcale jakoś specjalnie przez NSA nie zostały zdystansowane, a może i jest odwrotnie (pamiętajmy, że mówimy o rządowej organizacji, której agenci spędzali całe miesiące na poszukiwaniu terrorystów w World of Warcraft).

A jeśli jednak NSA się uda, to co?

Golański jednak tyle wie o mechanice kwantowej co zje, więc być może mylę się kompletnie, a do końca dekady NSA nie tylko przeczyta wszystkie nasze zaszyfrowane e‑maile, ale też zabierze nam wszystkie bitcoiny. W sumie czemu by nie? Mamy w praktyce tylko trzy typy kryptografii na kluczu publicznym: Diffie-Helllmana, na krzywych eliptycznych i oczywiście RSA. Szybka maszyna kwantowa realizująca algorytm Shora nie tylko dałaby dostęp do wiadomości, ale też pozwoliłaby na skuteczne ataki fałszowania łańcucha bloków Bitcoina, Trochę lepiej z wiadomościami zabezpieczonymi szyframi symetrycznymi, choć i tu coś tam podobno można osiągnąć kwantowym algorytmem Grovera.

Zanim jednak taka maszyna by powstała (a sygnały o realnych postępach w dziedzinie prac nad czymś takim trudno ukryć), to w świecie kryptografii sporo się może zmienić. Od wielu lat matematycy pracują nad kryptosystemami na czasy kwantowych komputerów – i rezultaty są bardzo obiecujące. Kryptografia bazująca na kratach (np. systemy NTRUEncrypt/NTRUSign ), kryptografia na bazie wielomianów wielu zmiennych (np. szyfr strumieniowy QUAD ), czy system cyfrowych podpisów Lamporta, pozwalający np. na zabezpieczenie bitcoinowych transakcji przed kwantowym atakiem – to wszystko działa dobrze już dziś, i to z tymi właśnie kryptosystemami musiałaby się zmierzyć hipotetyczna kwantowa maszyna NSA. A jeśli nawet nie będzie to takie proste, to przecież są jeszcze systemy szyfrów z kluczem jednorazowym (http://pl.wikipedia.org/wiki/Szyfr_z_kluczem_jednorazowym), których złamać się nie da, i których upowszechnieniu przeszkadza dziś jedynie relatywnie wysoki koszt (co za kilka lat nie musi być już prawdą).

Nic więc takiego przełomowego pod względem deszyfrowania NSA w przyszłości nie zrobi, wciąż jej agenci będą musieli ciężko pracować, szukając luk w oprogramowaniu, wykradając klucze, śledząc nas w wirtualnych światach. A że przy okazji wyda się trochę pieniędzy podatników na różne ciekawe, niekoniecznie mające praktyczny sens akcje, to przecież nie szkodzi. W porównaniu do łącznych wydatków na podtrzymanie strategicznej supremacji Stanów Zjednoczonych na tej planecie to przecież grosze.