Strona używa cookies (ciasteczek). Dowiedz się więcej o celu ich używania i zmianach ustawień. Korzystając ze strony wyrażasz zgodę na używanie cookies, zgodnie z aktualnymi ustawieniami przeglądarki.    X

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. 

bezpieczeństwo hobby inne

Komentarze

0 nowych
Vanshei   14 #1 05.01.2014 16:48

stawiam że prędzej czy później nas wszystkich zaczipują, dobrowolnie czy nie i nie będą musieli łamać żadnych szyfrów ;)

eimi REDAKCJA  16 #2 05.01.2014 16:52

Tak, Władimira Putina pierwszego zaczipują :). Już to widzę.
Swoją drogą, bardzo fajny serial się zaczął, "The Assets", o szpiegostwie w czasach zimnej wojny.

Vanshei   14 #3 05.01.2014 17:14

No z nim mógłby być problem ale z resztą szarej masy by sobie dali radę.
Co do tych komputerów kwantowych to tak naprawdę możemy się tylko domyślać co tam NSA w swoich piwnicach chowa.
A serial na pewno sprawdzę. Dzięki ;)

Vanshei   14 #4 05.01.2014 17:25

@Zbigniew nie przewidziałeś jednego, tego gołębia z emailem mogą Ci z wiatrówki zestrzelić ;)

Hitm3n   7 #5 05.01.2014 17:28

Hmm... Gdyby NSA miało coś w tych swoich piwnicach, to ktoś puściłby parę z ust, nie ma bata - jak eimi wspomniał, nie jest to odkrycie za czapkę gruszek.

z3gaa   1 #6 05.01.2014 18:12

dobry wpis!

Shaki81 MODERATOR BLOGA  37 #7 05.01.2014 18:30

Od wielu lat mówi się o takich komputerach. Może w końcu ktoś się na poważnie zajął tą technologią.

Ryychuu   5 #8 05.01.2014 18:38

news sponsorowany przez NSA, oni chcą uśpić naszą czujność, pannie Golański, myślałem, ze ma pan chodź trochę godności... :)

Cóż dobry wpis, Onet i TVN to taki chłam, że aż się dziwię, że ludzie tam w ogóle wchodzą... A potem się dziwić, że mamy rząd jaki mamy...

Kowal155   4 #9 05.01.2014 18:48

@Vanshei

Co możemy zrobić? Zaprotestować :)

command-dos   17 #10 05.01.2014 19:13

kurde - tekst zbyt trudny dla mnie... Przyczepię się jednak do tytułu: "Kwantowy upiór NSA tańszy niż nowy myśliwiec 5 generacji". Nie wiem, na co miało owe porównanie wskazywać, ale zazwyczaj takie porównania mają zaszokować, zaciekawić, czyli porównujemy złe rzeczy do czegoś dobrego, np: kałach 10 generacji tańszy od czapki gruszek. Według tego tytułu obojętne mi na co idzie ta kasa ;) i już potem z takim nastawieniem czytam dalej...

rm7   4 #11 05.01.2014 19:39

"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"
Transakcje opierają się na krzywych eliptycznych i je da się sfałszować, ale co ma komputer kwantowy do ataków na łańcuch bloków, który opiera się na SHA?

  #12 05.01.2014 22:45

NSA to nie problem... zacipują nas jaszczury z piekła!
http://www.mmszczecin.pl/blog/entry/217213/Sekta+z+Czech+ostrzega+przed+atakiem+...

rsajdok   2 #13 05.01.2014 23:49

Polecam książkę Wojciecha Orlińskiego Internet strach się bać. W zasadzie już od jakiegoś czasu straciliśmy takie rzeczy jak wolność słowa, prywatność, kulturę, transparentność i w przyszłości pracę. Autor wykazuje to na bardzo wielu przykładach.

adam01   5 #14 06.01.2014 00:11

mamciu ile trudnych słóf...

djDziadek   16 #15 06.01.2014 01:07

Eeeeeeeeeee, tego, ten... o co kaman ?

  #16 06.01.2014 01:30

Odnosnie bitcoina to zakladajac ze kontroluja wiele kluczowych routerow chyba mogliby juz teraz przejac siec? W koncu potrzeba 50% ogolnej mocy sieci, a wlasciwie to nie musza przejmowac tych komputerow tylko odpowiednio modyfikowac pakiety z protokolu bitcoina?

4lpha   9 #17 06.01.2014 02:26

@eimi
Wiadomo coś więcej o konstrukcji komputera D-Wave?
Btw. super się czytało.

treuer25   6 #18 06.01.2014 08:44

Jeśli chodzi o fizykę kwantową to tak naprawdę jesteśmy dopiero na samym początku drogi jeśli chodzi o więdzę na ten temat. Kiedyś pewien fizyk powiedział że fizyka kwantowa (wiedza na jej temat) przypomina mu twór który w naturze wyglądał by tak nogi małby głowa rekina tułów żaby czyli właściwie nic do siebie nie pasuje ( a jakoś to żyje!) tak obrazowo można by opisać wiedzę na temat fizyki kwantowej.

rm7   4 #19 06.01.2014 13:31

@zacos2
Modyfikacja pakietów zmieni sumy kontrolne.
Transakcje są zabezpieczone ECDSA, a blockchain SHA.
Żeby przejąć sieć, trzeba kontrolować 50% mocy sieci.

eimi REDAKCJA  16 #20 06.01.2014 13:46

@rm7: na bitcointalk kiedyś była długa dyskusja o tym https://bitcointalk.org/index.php?topic=133425.0. Przejęcie mocy sieci teoretycznie nie jest niemożliwe, o wykorzystaniu maszyn kwantowych do haszowania jest tu ciekawy tekst: http://cs.stackexchange.com/questions/586/could-quantum-computing-eventually-be-.... Oczywiście w takiej sytuacji można zawsze zmienić haszowanie (choć płacz właścicieli asicowych koparek będzie głośny).


@4lpha: coś tam na łamach DP było: http://www.dobreprogramy.pl/Cala-prawda-o-maszynach-DWave-tak-to-komputery-kwant...

Znajdziesz tam linki do naukowego artykułu, w którym technologia D-Wave jest dość dokładnie przeanalizowana.

Jim1961   7 #21 06.01.2014 14:23

@eimi
"The pilot episode earned only 0.7 rating in the 18–49 year old demographic, making The Assets the lowest rated drama premiere in big four networks ever" :D

Trailer (ciut) wskazuje na klasę B :)

Stalker11517   2 #22 06.01.2014 15:37

Hmmm... ciekawe co będzie po komputerze kwantowym... :D

so69   4 #23 06.01.2014 16:20

@eimi popisałeś się, teraz tylko przełóż to na język dla przeciętnego zjadacza chleba...

januszek   18 #24 06.01.2014 20:10

42 :)

skrzypek   12 #25 06.01.2014 23:16

Kto bogatemu zabroni... ludzie sami sobie to sponsorują.

  #26 06.01.2014 23:39

Trochę nie na temat, ale też straszne ;)
Przepowiednia lepsza niż ta związana z Majami i informatyką kwantową.

1-go stycznia 2017 może dojść do tzw. NWO a ściślej mówiąc do NWC (New World Calendar) ;)
I kto za tym stoi? Bill Edward Gates!!! Niestety (a może stety) to nie ten sam niesławny Bill, ale i tak robi wrażenie ;). Róbcie zapasy i budujcie bunkry ;p

  #27 06.01.2014 23:42

Jeszcze linka jako dowód przepowiedni ;): https://pl.wikipedia.org/wiki/World_Calendar

  #28 07.01.2014 00:54

@weneraichora

A słyszałeś o przepowiedni końca świata w 2038r? Wg. starożytnych afrykańskich programistów skończy się wtedy czas i zniknie świat jaki znamy.

budda86   9 #29 07.01.2014 10:20

"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)"

Jeśli to prawda, konsekwencje etyczne są również bardzo poważne. Kto nas upoważnił do okradania z mocy obliczeniowej mieszkańców wszechświatów równoległych? I co zrobimy, jeśli w końcu się połapią i wezmą odwet?

  #30 07.01.2014 14:50

@sdj

"Wg. starożytnych afrykańskich programistów" chyba pijesz do Marka S. ;)

Do 2038 jest trochę czasu. Do tego casu sprzęt i soft pewnie będzie głównie 64bitowy, ale warto tydzień przed 19-tym stycznia 2038 wypłacic troche kasy z banku i schować do skarpety bo giełda, banki, ZUSy i inne OFE mogą się zawiesić.

Ja tam czekam na 2017 r. Może temu Gatesowi się uda przekonać do tych zmian cały świat. Więc warto juz dziś planować długi weekend biorąc pod uwagę: Worldsday i Leapyear Day ;)

  #31 07.01.2014 14:52

@budda86

"Jeśli to prawda, konsekwencje etyczne są również bardzo poważne. Kto nas upoważnił do okradania z mocy obliczeniowej mieszkańców wszechświatów równoległych? I co zrobimy, jeśli w końcu się połapią i wezmą odwet?"

Odpowiedź znajdziesz w serialu "Fringe" ;)

  #32 08.01.2014 21:16

@budda86
Deutsch skłania się ku interpretacji wielu światów (Many worlds interpretation), istnieją inne interpretacje mechaniki kwantowej, nieco bardziej przyziemne.

  #33 10.01.2014 23:05

W pierwszym akapicie fraza "o lata świetlne wyprzedzającej" dotyczy czasu, podczas gdy rok świetlny jest miarą odległości. Tu moja prośba: może dałoby się z tekstu usunąć słowo "świetlne", czyniące tę frazę nieco nonsensowną?
Ja rozumiem, że taki nieco egzaltowany styl jest modny w pewnych kręgach, ale warto zadbać o poprawność językową i treściową przekazu.
Z góry dziękuję.

tomimaki   6 #34 12.01.2014 22:23

@olleand
Nie liczyłbym na to, bardziej na wykład, że to poprawne, modne w tych czasach i takie tam pleple. ;)

  #35 26.12.2014 23:54

Wystarczy po prostu mocno przyśpieszyć obliczenia. Taki mion w realu istnieje bardzo krotko, ale dla nas jesli przyleci z kosmosu bardzo dlugo. Wystarczy obliczenia prowadzic w akceleratorach i juz. Ba wystarczy tez robic to na orbicie (o dziwo wszyscy robia eksperymenty z laserami w kosmosie od niedawna). I wtedy komputer kwantowy moze liczyc nie na kilku ale na kilkuset q-bitach i co najwazniejsze moze to robic wiele razy. Do tego brak obserwatora w postaci interakcji z otoczeniem.