Preorder drugiego tomu książki sekuraka: Wprowadzenie do bezpieczeństwa IT. -15% z kodem: sekurak-book
Komputery kwantowe kontra współczesne algorytmy szyfrowania
Prędzej czy później komputery kwantowe o możliwościach znacznie przewyższających tradycyjne maszyny obliczeniowe wejdą do powszechnego użytku. Będzie to moment, w którym cała gama stosowanych obecnie algorytmów szyfrowania straci swoje znaczenie.
Komputery kwantowe
Pomimo tego, że firma D-Wave oferuje pierwsze urządzenia wykorzystujące zjawiska mechaniki kwantowej, a agencje rządowe i wielkie korporacje pracują usilnie nad jego zbudowaniem, to komputer kwantowy w pełnym tego słowa rozumieniu najprawdopodobniej jeszcze jednak nie powstał.
Na czym więc będzie polegała przewaga komputerów kwantowych w starciu z dzisiejszymi metodami szyfrowania danych?
Klasyczne komputery oparte są na tranzystorach. Obliczenia prowadzone są w kodzie binarnym wykorzystując zjawisko przewodzenia prądu elektrycznego. Prąd przepływa albo nie przepływa — to dwa stany: 1 albo 0. Dwa możliwe stany to jeden bit, czyli podstawowa jednostka informacji.
W komputerze kwantowym podstawowym elementem jest nie tranzystor, lecz najczęściej atom, a podstawową jednostką informacji nie bit, lecz kubit (kwantowy bit). Kubit nie będzie miał ustalonej wartości 1 lub 0, tak jak klasyczny bit. W trakcie obliczeń będzie się znajdował w jakimś stanie pośrednim. Kubit stanowi więc kwantową superpozycję zera i jedynki.
Dlatego też kubit niesie w sobie naraz więcej informacji niż zero-jedynkowy bit. W komputerach klasycznych jeden bajt może reprezentować w danym momencie tylko jedną z 256 wartości, natomiast jeden kubajt to reprezentacja 256 różnych stanów jednocześnie. Co to znaczy w praktyce? Komputery kwantowe byłyby nieporównywalnie szybsze, jednak wbrew obiegowej opinii tylko w niektórych zastosowaniach.
Komputery kwantowe kontra współczesne algorytmy symetryczne
Wizja rychłego nadejścia komputerów kwantowych jest bardzo często przedstawiana w kontekście całkowitej zagłady stosowanych obecnie mechanizmów szyfrowania danych. Mówi się, że komputer kwantowy będzie w stanie w ułamku sekundy złamać wszystkie zabezpieczenia, z którymi klasyczny komputer nie poradziłby sobie nawet w ciągu milionów lat. W dużej mierze nie jest to jednak prawdą.
Przede wszystkim należy wiedzieć, że większość stosowanych obecnie standardów szyfrowania symetrycznego (wykorzystujących pojedynczy klucz tajny — np. popularny AES) nawet w obliczu upowszechnienia się nowego rodzaju komputerów jest względnie bezpieczna.
Wynika to z prostego faktu. Otóż specyficzne własności komputera kwantowego nie pozwolą na stworzenie algorytmów, które byłyby w stanie dramatycznie przyspieszyć łamanie szyfrów symetrycznych.
Co prawda istnieją opracowania mówiące o możliwości przyspieszenia łamania kluczy symetrycznych za pomocą algorytmów kwantowych, jednak wystarczającą obroną będzie tutaj po prostu dwukrotne zwiększenie długości klucza.
Algorytmy asymetryczne (kryptografia klucza publicznego)
Zupełnie inaczej wygląda kwestia „odporności” na komputery kwantowe w przypadku obecnie wykorzystywanych algorytmów szyfrowania asymetrycznego (wykorzystujących parę kluczy — publiczny oraz prywatny).
Bezpieczeństwo najczęściej wykorzystywanych obecnie algorytmów asymetrycznych takich jak RSA, ElGamal, czy ECC (algorytmy z wykorzystaniem krzywych eliptycznych), bazuje na trzech zagadnieniach matematycznych, które dla współczesnych komputerów stanowią bardzo duże wyzwanie obliczeniowe.
Problemy faktoryzacji dużych liczb złożonych, odnalezienia logarytmu dyskretnego lub dyskretnych logarytmów na krzywych eliptycznych są dla znanych nam komputerów (przy odpowiednim doborze parametrów) nie do rozwiązania w jakimkolwiek rozsądnym czasie.
Tutaj jednak sytuacja zupełnie zmieni się wraz z nadejściem komputerów kwantowych. Wszystkie trzy wymienione zagadnienia nie będą stanowiły wyzwania dla odpowiednio dużego (wyposażonego w odpowiednią liczbę kubitów) komputera kwantowego.
Dzięki pracom Petera Shora wiemy, że korzystając z opracowanego przez niego kwantowego algorytmu faktoryzacji łamanie dzisiejszych algorytmów asymetrycznych w dobie komputerów kwantowych będzie można dramatycznie przyspieszyć. Na tyle, że wspomniane algorytmu zupełnie utracą swe znaczenie.
Upraszczając, obrazowo można by powiedzieć, że tam gdzie klasyczne algorytmy faktoryzacji (czyli rozkładu zadanej liczby na czynniki) muszą mozolnie dokonywać próby dzielenia przez kolejne liczby, to algorytm kwantowy pozwala na sprawdzenie wszystkich potencjalnych czynników… jednocześnie i po prostu odczytanie prawidłowego rozwiązania.
Algorytmy asymetryczne w erze informatyki kwantowej
Wiemy już, że algorytmy symetryczne są w obliczu upowszechnienia się informatyki kwantowej w miarę bezpieczne. Kryptografia asymetryczna jest nam jednak równie potrzebna.
Główną bolączką szyfrowania symetrycznego jest problem bezpiecznej wymiany wspólnego sekretu (klucza szyfrującego). Dobrze widać to na przykładzie połączeń internetowych zabezpieczonych za pomocą standardów SSL/TLS.
Właściwa wymiana informacji w tak zabezpieczonych połączeniach odbywa się za pomocą szyfrowania symetrycznego. Przed rozpoczęciem transmisji obie strony muszą jednak najpierw w bezpieczny sposób wymienić klucz symetryczny. Z oczywistych względów odpada przesłanie sekretnego klucza nieszyfrowanym kanałem…
Tutaj właśnie do akcji wkracza szyfrowanie asymetryczne, które pozwala nam na przesłanie (zaszyfrowanie) sekretu — w tym wypadku symetrycznego klucza sesji SSL/TLS — z wykorzystaniem klucza publicznego odbiorcy, jednocześnie dając nam pewność, że tylko odbiorca ten sekret zdoła rozszyfrować (korzystając z posiadanego klucza prywatnego).
Wygląda więc na to, że wraz z nadejściem komputerów kwantowych, w celu skorzystania z naszej bankowości internetowej, będziemy musieli za każdym razem udać się uprzednio do siedziby banku w celu pobrania symetrycznego klucza sesji…
Algorytmy asymetryczne odporne na komputery kwantowe
Na szczęście taki scenariusz również nam raczej nie grozi. Po pierwsze, jak już wspomniałem, stworzenie komputerów kwantowych z prawdziwego zdarzenia zajmie jeszcze najprawdopodobniej długie lata, a obecne osiągnięcia w praktycznym stosowaniu kwantowej faktoryzacji są nadal bardzo skromne.
Po drugie, już obecnie trwają prace nad nowymi algorytmami szyfrowania asymetrycznego, które będą odporne na specyficzne własności komputerów kwantowych. Takie badania prowadzi już m.in. Microsoft, który w walce o przyszłe bezpieczeństwo standardu TLS proponuje wykorzystanie algorytmów opartych na matematycznych strukturach zwanych „kratami” (Lattice-based cryptography).
Wygląda więc na to, że prorocy kwantowej apokalipsy kryptografii nie mają racji. Będziemy mogli spać spokojnie nawet wtedy, gdy potężne komputery nowego rodzaju będą powszechnie sprzedawane na aukcjach internetowych. Spokojne mogą być również agencje rządowe, gdyż te z pewnością poradzą sobie w taki, czy inny sposób, nawet z metodami szyfrowania odpornymi na komputery kwantowe.
— Wojciech Smol
Hmmm… nie do końca. Oczywiście problem stworzenia procesora kwantowego to inna bajka, ale wszystkie te obliczenia i wnioski wysuwa się na podstawie obecnych „podstaw” technologicznych jak chociażby komputer Della. Naukowcy z całego świata sugerują, że technologia kwantowa rozwinie się do stopnia ok. 64 kubitów na procesor. Jednak co się stanie wtedy, kiedy komuś uda się stworzyć stabilne kubity wielkości obecnych tranzystorów i zmieścić ich na płytce krzemowej (grafenowej? innej?) 6 miliardów, a do tego będzie to GPU z jednostkami strumieniowymi? ;) Kiedyś Bill Gates też stwierdził, że ludzie będą wykorzystywać maksymalnie 64kb pamięci, dzisiaj 16gb to niekiedy za mało. Obliczeń dotyczących procesorów posiadających ogromne ilości kubitów nie ma, dlatego „względnie” bezpieczne to słowo klucz :) Według „specjalistów” również zastosowanie procesorów kubitowych będzie różne od obecnego – procesory X86 będą wydajniejsze w np. dodawaniu liczb niż procesory kwantowe, jednak znowu – wnioski są wysuwane na podstawie zbyt małej skali, i skali ilości tranzystorów/kubitów i wielkości liczb, jeżeli X86 będzie szybszy w dodawaniu 1+1, ale kubitowy szybszy w dodawaniu 2^9999999999999+2^999999999999999 to który tak na prawdę będzie szybszy? ;) Zwykłe pojęcia względności. Nikt jak dotąd nie stworzył pełnoprawnego procesora kwantowego (WSZYSTKIE obecne zastosowane prace naukowe to tylko obiekty działające na pewnych kwantowych zależnościach), więc jak na razie żyjemy sobie w czystej teorii.
Problem polega na tym, że komputery kwantowe owszem, będą znacznie szybsze od tych normalnych, ale nie dadzą ci jednoznacznego wyniku przy obliczeniu. Wynik działania 1+1= przedstawiony przez komputer kwantowy może wynosić zarówno 2, sqrt(2) albo 6^66. Oczywiście, im większa liczba obliczeń, tym pewność będzie większa, bo coraz więcej wyników będzie oscylowało wokół liczby 2, ale żeby mieć stuprocentową pewność wyniku trzeba by przeprowadzić nieskończoną liczbę operacji. Oczywiście, takie NSA nie będzie chciało stuprocentowej pewności, ale i tak. Dlatego kwantowe metody liczenia najlepsze zastosowanie znajdą tam, gdzie wynik nie musi być dokładny, ale musi być obliczany bardzo szybko (np. programowanie AI w grach).
Tak, zgadzam się. Kwestia precyzyjności wyniku, ilości cykli, przebiegów, funkcjonowanie zegara itp. itd. etc. to tylko kwestia doprecyzowania i zastosowania w praktyce. Jeżeli wystarczy nam np. 60% pewność wyniku przy jak najmniejszej ilości cykli, to również może się okazać, że kwantowy procesor może okazać się szybszy :) Tak jak mówię, najpierw musi powstać działający procesor, a wtedy muszą powstać algorytmy oraz oprogramowanie i dopiero wtedy na prawdę dowiemy się, jak szybko może działać procesor kwantowy w konkretnych zastosowaniach. Nie ujmuję obecnym teoriom i obliczeniom kwantowych fizyków, ale jednak chciałbym zobaczyć jak to działa w praktyce, teoria teorią, praktyka praktyką :)
„Kiedyś Bill Gates też stwierdził, że ludzie będą wykorzystywać maksymalnie 64kb pamięci”
On tego nigdy nie powiedział, a przynajmniej nie ma na to niepodważalnych dowodów.
@józek masz chyba na myśli „wszystkie znane” prace naukowe na ten temat. Naiwnością jest myśleć, że nie ma takich które jeszcze światła dziennego nie ujrzały. Mogły już nawet zostać zaimplementowane. Tak, brzmi to jak teoria spiskowa, ale określenie „teoria spiskowa” zostało stworzone na potrzeby tych, którzy takie właśnie rzeczy ukrywają.
Problem tworzenia kubitów to problem tworzenia stanów superpozycji. Oczywiście można twierdzić, że gdzieś już na to wpadł ktoś, ale szczerze w to wątpię. Nad procesorem kwantowym głowią się największe umysły świata, a żaden z nich nie jest nawet blisko stwierdzenia, w stronę jakiego materiału powinniśmy się udać (gaz? ciecz?). Z tego co wiem, udało się wprowadzić pojedyncze cząsteczki w stan superpozycji, na kilka sekund i przy użyciu ciekłego azotu. Moja wypowiedź jest w 100% zgodna – nikt nie stworzył procesora kwantowego (nawet specsłużby :P), ale możliwe, że opracowano już jakieś sposoby stabilnego utrzymywania superpozycji (nie zagłębiałem się w temat od kilku lat). W każdym bądź razie, nikt również nie jest wstanie przewidzieć, jak szybko liczyłby procesor, który mógłby w jednym czasie przyjąć 6 000 000 000 stanów, bo obecnie stoimy na poziomie, na którym 1 kubajt jest bardzo odległym marzeniem. Aha i proszę się tu nie sugerować systemem Della, komputer Della korzysta z techniki nazywanej „wyżarzaniem kwantowym” i mimo że posiada cechy komputera kwantowego, jest od niego znacznie (ZNACZNIE!) wolniejszy – naukowcy się w ciąż kłócą nawet, czy jest to komputer kwantowy, jedni udowadniają, że tak, inni udowadniają, że nie, wymyślając przy tym niebanalne algorytmy i testując swoje programiki, jednak żaden wynik nie jest jednoznacznie przekonujący ;)
józku, krótko, stan superpozycji jest stanem powszechnym w naturze. Zapraszam do lektury podstaw fizyki ciała stałego. Co do zjawisk obecnie aktywnie eksploatowanych pod kątem komputerów kwantowych (a konkretnie bramek logicznych stanowiących podstawe takiego komputera) obiecujące wyniki uzyskuje się dla nadprzewodników wysokotemperaturowych. Problemy głownie związane są ze zjawiskiem dekoherencji stanu kwantowego w fizycznych realizacjach, ostatnie osiągnięcia na tym polu pozwalają rednak realnie i praktycznie zastanawiać się nad przyszłością tej technologii.
Dekoherencja stanu kwantowego powoduje, że zostaje utracona superpozycja w układzie, co skutkuje utratą informacji (splątania), zgadza się?
Zgadza się. Utworzenie jednak „superpozycji” a jego utrzymanie to dramatycznie (technologicznie) problemy innej skali.
Więc gdzie popełniłem błąd logiczny, że musiałeś mnie tak ochoczo poprawiać polecając dokształcanie się? Zacytuję sam siebie: „nikt nie stworzył procesora kwantowego (nawet specsłużby :P), ale możliwe, że opracowano już jakieś sposoby stabilnego utrzymywania superpozycji”. W związku z tym, problem superpozycji można rozbić na dwa osobne problemy – tworzenia superpozycji i dekoherencji, a stosować w zależności od stopnia „zagłębiania” się w temat. Nie trawię gdy ludzie próbują się wymądrzać tam, gdzie nie muszą, zwłaszcza że nie używam słownictwa technicznego, bo kieruję swoje słowa do osób w ogóle nie zagłębionych w temat (czyli dosłownie odbiorców artykułu sekuraka). Przy mechanice kwantowej godzinami można było by rozmawiać o samej teorii pola, tylko po co? Oczywiście mechanika kwantowa to fascynujący temat, ale większości teorii (a już tym bardziej twierdzeń), nikt niezaznajomiony z fizyką, w pełni nie pojmie. Wymądrz się w tym temacie: wytłumacz laikowi co to dokładnie oznacza, że układ kubitowy przyjmuje konkretne stany (możesz zastosować prostszą wersję: co dokładnie oznacza „stan” pojedynczego kubita)? Obecnie wszystkie portale próbują to określać w błędny sposób „kubit posiada jednocześnie 0 i 1”, a jak wiemy to nie prawda – wchodzimy w teorię pola, którą również trzeba wyjaśnić. Proszę, wytłumacz to laikom :)
Kiepski argument. Fuzja termojądrowa też występuje w naturze, co nie powoduje, że potrafimy ją wywołać i zaprząc do swoich celów :)
Potrafimy, tylko aktualne rozwiazania technologiczne fuzji termojądrowej nie są opłacalne ekonomicznie i energetycznie (nie osiągamy punktu Break-even – https://www.iter.org/sci/beyonditer i informacje z MIT: http://kopalniawiedzy.pl/MIT-tokamak-fuzja-jadrowa-ARC,22940).
Jeśli gościu szukałeś jakiegoś argumentu do zbicia argumentu, to trzeba było pisać o aktualnym stanie adaptacji technicznej wiedzy o grawitacji. W końcu jest powszechnym zjawiskiem w naturze i w zasadzie nie wiele więcej o niej wiadomo. Reszta to teorie.
A jak komputery kwantowe mogłyby sobie radzić ze znajdowaniem kolizji hashy?
Podobnie, jak w przypadku szyfrowania symetrycznego, funkcje skrótu są „względnie” bezpieczne: http://www.pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/9783540887010-c1.pdf
Niech ktoś kto się trochę orientuje napisze jak to się odnosi do Bitcoin
@A: Google Twoim przyjacielem:
http://bitcoinet.pl/2013/08/11/komputery-kwantowe-a-bitcoin/
Bardzo sensowny artykuł. Polecam wszystkim dziennikarzom panikującym na sam dzwięk terminu „komputer kwantowy”. Materiał przystępny, systematyczny i ciekawy. Brakowało mi niestety krótkiego akapitu na temat kwantowej dystrybucji klucza (zalet i zmagań w implementacjach) oraz aktualnych zastosowań (tak kryptografia kwantowa aktualnie jest z powodzeniem stosowana na odległościach <50 km) do transmisji klucza poufnego.
Raz jeszcze polecam i gratuluje udanego artykułu.
Tak, ale to już w sumie zagadnienia bardziej z zakresu kryptografii kwantowej, a artykuł skupiał się w sumie na klasycznym krypto.
Jeszcze jedno, jeśli ktoś jest zainteresowany „liźnięciem” tematu to polecam w języku polskim dwie pozycje:
a) „Wprowadzenie do Krypografii Kwantowej” Opracowanie zebrane wydane przez Oficynę Wydawniczą Politechniki Wrocławskiej ISBN 978-83-7493-746-7
b) kurs EITCA-IS -bezpieczeństwo systemów informatycznych (ten kurs jest w zasadzie głównie kursem mechaniki i informatyki kwantowej jak również kwantowej kryptografii, pozostałe przedmioty są niejako „przy okazji”)…
Do działania komputera kwantowego potrzebne są specyficzne warunki: nadprzewodniki – niskie temperatury (działają w temp. ciekłego azotu ([- 195C] 77K)), choć są już znane nadprzewodniki wysoko temperaturowe ([-120C] 150K )
Zanim pierwszy komputer pojawi się na biurku musi upłynąć jeszcze wiele kilka dekad, a nawet stuleci. To jedna kwestia. Druga to zmienić pogląd na temat wyników jakie otrzymamy przy użyciu kompa kwantowego. 1 Kubit przechowuje informacje o prawdopodobieństwie 0 lub 1.
I nie jarajmy się tak tym co piszą – komputery kwantowe nie będą „prawidłowo” liczyły 1+1 bo wynik dla niego to zbiór prawdopodobieństw wyników. Do takich zastosowań tylko widzę, gdzie wynik nie jest istotny ale istotne jest prawdopodobieństwo wyników.
Dla tych co jeszcze nie wiedzą jakie rewolucje wprowadziła mechanika kwantowa – polecam teoretyczne rozważania na temat Kota Schrödingera
https://pl.wikipedia.org/wiki/Kot_Schr%C3%B6dingera