Komputery kwantowe: koniec kryptografii?

Reklama

Obliczenia kwantowe to jedna z tych technologii, która jest tak tajemnicza, że ​​nazwy postaci telewizyjnych upuszczają je, gdy chcą brzmieć mądrze.

Informatyka kwantowa jako pomysł istnieje już od jakiegoś czasu - teoretyczną możliwość pierwotnie wprowadzili Yuri Manin i Richard Feynman w 1982 r. Jednak w ciągu ostatnich kilku lat pole było niepokojąco bliższe praktyczności.

Firmy takie jak Google i Microsoft, a także agencje rządowe, takie jak NSA, od lat gorączkowo poszukują komputerów kwantowych. Firma o nazwie D-Wave wyprodukowała i sprzedaje urządzenia, które (choć nie są odpowiednimi komputerami i potrafią) wykonują tylko kilka algorytmów) wykorzystują właściwości kwantowe i są kolejnym krokiem na drodze do całkowicie Turing-complete Co to jest test Turinga i czy kiedykolwiek zostanie on pokonany?Test Turinga ma na celu ustalenie, czy maszyny myślą. Czy program Eugene'a Goostmana naprawdę zdał test Turinga, czy też twórcy po prostu oszukiwali? Czytaj więcej maszyna kwantowa.

Nie wydaje się nierozsądne stwierdzenie, że mogą wystąpić przełomy, które pozwolą na zbudowanie pierwszego dużego komputera kwantowego w ciągu dekady.

Skąd więc takie zainteresowanie? Dlaczego powinno Cię to obchodzić? Komputery stają się coraz szybsze Jakie jest prawo Moore'a i co ma z tobą wspólnego? [MakeUseOf wyjaśnia]Pech nie ma nic wspólnego z prawem Moore'a. Jeśli masz takie skojarzenie, mylisz je z Prawem Murphy'ego. Nie byliście jednak daleko, ponieważ prawo Moore'a i prawo Murphy'ego ... Czytaj więcej - co jest takiego specjalnego w komputerach kwantowych?

Aby wyjaśnić, dlaczego te maszyny są tak ważne, musimy cofnąć się o krok i dokładnie zbadać, czym są komputery kwantowe i dlaczego działają. Na początek porozmawiajmy o koncepcji zwanej „złożonością środowiska wykonawczego”.

Co to jest złożoność środowiska wykonawczego?

Jedną z wielkich niespodzianek na początku informatyki było odkrycie, że jeśli masz komputer, który rozwiązuje problem pewien rozmiar w określonym czasie, podwojenie prędkości komputera niekoniecznie pozwala rozwiązać problemy dwukrotnie duży.

Niektóre algorytmy zwiększają całkowity czas wykonania bardzo, bardzo szybko wraz ze wzrostem rozmiaru problemu - niektóre algorytmy można szybko ukończyć biorąc pod uwagę 100 punktów danych, ale wypełnienie algorytmu podanego 1000 punktów danych wymagałoby komputera wielkości Ziemi działającego przez miliard lat Złożoność środowiska wykonawczego jest formalizacją tego pomysłu: patrzy na krzywą, jak szybko rośnie złożoność problemu, i wykorzystuje kształt tej krzywej do klasyfikowania algorytmu.

Ogólnie rzecz biorąc, te klasy trudności są wyrażone jako funkcje. Algorytm, który staje się proporcjonalnie trudniejszy, gdy zbiór danych, na którym pracuje, rośnie (podobnie jak prosta funkcja zliczania), mówi się, że jest funkcją o złożoności w czasie wykonywania „n ” (jak w, trzeba n jednostki czasu do przetworzenia n punkty danych).

Alternatywnie można go nazwać „liniowym”, ponieważ po wykreśleniu go uzyskuje się linię prostą. Inne funkcje mogą być n ^ 2 lub 2 ^ n lub n! (n silnia). Są to wielomian i wykładniczy. W dwóch ostatnich przypadkach wykładnicze rosną tak szybko, że prawie we wszystkich przypadkach nie da się rozwiązać niczego poza bardzo trywialnymi przykładami.

Złożoność środowiska wykonawczego i kryptografia

Jeśli słyszysz te rzeczy po raz pierwszy i brzmi to bezsensownie i tajemniczo, spróbujmy ugruntować tę dyskusję. Złożoność środowiska wykonawczego ma kluczowe znaczenie dla kryptografii, która polega na ułatwieniu odszyfrowywania osobom, które znają tajny klucz, niż tym, którzy go nie znają. W idealnym schemacie kryptograficznym deszyfrowanie powinno być liniowe, jeśli masz klucz, i 2 ^ k (gdzie k to liczba bitów w kluczu), jeśli nie.

Innymi słowy, najlepszym algorytmem do odszyfrowywania wiadomości bez klucza powinno być po prostu odgadnięcie możliwych kluczy, co jest trudne do uzyskania dla kluczy o długości zaledwie kilkuset bitów.

W przypadku kryptografii z kluczem symetrycznym (w której obie strony mają możliwość bezpiecznej wymiany tajemnicy przed rozpoczęciem komunikacji) jest to dość łatwe. W przypadku kryptografii asymetrycznej jest trudniej.

Kryptografia asymetryczna, w której klucze szyfrowania i deszyfrowania są różne i nie mogą być łatwo obliczone między sobą, jest znacznie trudniejsza matematycznie struktura do zaimplementowania niż kryptografia symetryczna, ale jest ona również o wiele bardziej wydajna: kryptografia asymetryczna umożliwia prowadzenie prywatnych rozmów, nawet po podsłuchu linie! Umożliwia także tworzenie „podpisów cyfrowych”, które pozwalają zweryfikować, skąd pochodzi wiadomość i czy nie została zmieniona.

Są to potężne narzędzia, które stanowią fundament współczesnej prywatności: bez asymetrycznej kryptografii użytkownicy urządzeń elektronicznych nie mieliby niezawodnej ochrony przed wścibskimi oczami.

Ponieważ szyfrowanie asymetryczne jest trudniejsze do zbudowania niż symetryczne, standardowe schematy szyfrowania, które są obecnie używane, nie są tak silne jak mogą być: najpopularniejszy standard szyfrowania, RSA, może zostać złamany, jeśli można skutecznie znaleźć czynniki pierwsze bardzo dużego numer. Dobra wiadomość jest taka, że ​​to bardzo trudny problem.

Najbardziej znany algorytm faktorowania dużych liczb do liczb pierwszych składowych nazywa się sitem pola liczb ogólnych i ma złożoność czasu działania, która rośnie nieco wolniej niż 2 ^ n. W związku z tym klucze muszą być około dziesięć razy dłuższe, aby zapewnić podobne bezpieczeństwo, co ludzie zwykle tolerują jako koszt prowadzenia działalności. Zła wiadomość jest taka, że ​​całe pole gry zmienia się, gdy komputery kwantowe zostają wrzucone do miksu.

Komputery kwantowe: zmiana gry kryptograficznej

Komputery kwantowe działają, ponieważ mogą mieć wiele stanów wewnętrznych jednocześnie, poprzez zjawisko kwantowe zwane „superpozycją”. Oznacza to, że mogą jednocześnie atakować różne części problemu, podzielone na możliwe wersje wszechświata. Można je również skonfigurować tak, aby gałęzie, które rozwiązują problem, kończyły się z największą amplitudą, tak aby po otwarciu skrzynki na Kot Schrodingera, wersja stanu wewnętrznego, w której najprawdopodobniej zostaniesz przedstawiony, to zadowolony z siebie kot trzymający odszyfrowane wiadomość.

Aby uzyskać więcej informacji o komputerach kwantowych, sprawdź nasz ostatni artykuł na ten temat Jak działają komputery optyczne i kwantowe?Nadchodzi era egzaskalii. Czy wiesz, jak działają komputery optyczne i kwantowe i czy te nowe technologie staną się naszą przyszłością? Czytaj więcej !

Skutkiem tego jest to, że komputery kwantowe nie są po prostu liniowo szybsze, tak jak normalne komputery: zdobywanie dwóch, dziesięciu lub stu razy szybciej nie pomaga w przypadku konwencjonalnej kryptografii, której przetwarzanie jest setki miliardów razy zbyt wolne. Komputery kwantowe obsługują algorytmy, których złożoność w czasie wykonywania jest coraz mniejsza niż w innych przypadkach. Właśnie to sprawia, że ​​komputery kwantowe zasadniczo różnią się od innych przyszłych technologii obliczeniowych obliczenia grafenu i memristera Najnowsza technologia komputerowa, którą musisz wierzyćSprawdź niektóre z najnowszych technologii komputerowych, które zmienią świat elektroniki i komputerów w ciągu najbliższych kilku lat. Czytaj więcej .

Na konkretny przykład algorytm Shora, który można wykonać tylko na komputerze kwantowym, może uwzględniać duże liczby log (n) ^ 3 czas, który jest zdecydowanie lepszy niż najlepszy klasyczny atak. Zastosowanie sita ogólnego pola liczbowego do obliczenia liczby z 2048 bitami zajmuje około 10 ^ 41 jednostek czasu, co daje ponad trylion bilionów bilionów. Korzystając z algorytmu Shora, ten sam problem zajmuje tylko około 1000 jednostek czasu.

Efekt staje się bardziej wyraźny, im dłuższe są klawisze. To jest siła komputerów kwantowych.

Nie zrozumcie mnie źle - komputery kwantowe mają wiele potencjalnych nie-złych zastosowań. Komputery kwantowe mogą skutecznie rozwiązać problem podróżnego sprzedawcy, umożliwiając naukowcom budowanie bardziej wydajnych sieci wysyłkowych i projektowanie lepszych obwodów. Komputery kwantowe mają już potężne zastosowania w sztucznej inteligencji.

To powiedziawszy, ich rola w kryptografii będzie katastrofalna. Technologie szyfrowania, które pozwalają naszemu światu dalej funkcjonować, zależą od trudnego do rozwiązania problemu faktoryzacji liczb całkowitych. RSA i powiązane schematy szyfrowania pozwalają ci mieć pewność, że jesteś na właściwej stronie, że twoje pliki pobieranie nie jest pełne złośliwego oprogramowania, a ludzie nie szpiegują przeglądania Internetu (jeśli używasz Słup).

Kryptografia chroni Twoje konto bankowe i zabezpiecza światową infrastrukturę nuklearną. Kiedy komputery kwantowe stają się praktyczne, cała ta technologia przestaje działać. Pierwsza organizacja, która opracuje komputer kwantowy, jeśli świat nadal pracuje nad technologiami, których obecnie używamy, znajdzie się w przerażająco silnej pozycji.

Czy więc kwantowa apokalipsa jest nieunikniona? Czy możemy coś z tym zrobić? Jak się okazuje… tak.

Kryptografia post kwantowa

Istnieje kilka klas algorytmów szyfrowania, które, o ile wiemy, nie są znacznie szybsze do rozwiązania na komputerze kwantowym. Są one znane łącznie jako kryptografia post kwantowa i dają nadzieję, że świat może przejść do kryptosystemów, które pozostaną bezpieczne w świecie szyfrowania kwantowego.

Obiecujący kandydaci to szyfrowanie oparte na sieci, takie jak Ring-Learning With Error, który czerpie swoje bezpieczeństwo z wyraźnie złożonego problem uczenia maszynowego i kryptografia wielowymiarowa, która czerpie swoje bezpieczeństwo z trudności w rozwiązywaniu bardzo dużych systemów prostych równania. Możesz przeczytać więcej na ten temat w Internecie Artykuł w Wikipedii. Uwaga: wiele z tych rzeczy jest skomplikowanych i może się okazać, że twoje tło matematyki musi zostać znacznie wzmocnione, zanim naprawdę zagłębisz się w szczegóły.

Wiele z tego wynika, że ​​post-kwantowe kryptografie są bardzo fajne, ale także bardzo młode. Potrzebują więcej pracy, aby być skutecznym i praktycznym, a także wykazać, że są bezpieczni. Powodem, dla którego możemy ufać kryptosystemom, jest to, że rzuciliśmy w nich wystarczająco paranoicznymi geniuszami klinicznymi wystarczająco długo że wszelkie oczywiste niedociągnięcia zostałyby do tej pory odkryte, a badacze udowodnili, że je cechują silny.

Współczesna kryptografia zależy od światła jako środka dezynfekującego, a większość postkwantowych schematów kryptograficznych jest po prostu zbyt nowa, aby zaufać światowemu bezpieczeństwu. Dotarli na miejsce, a przy odrobinie szczęścia i przygotowaniach eksperci ds. Bezpieczeństwa mogą dokończyć zmianę, zanim pierwszy komputer kwantowy wejdzie na linię.

Jeśli jednak zawiodą, konsekwencje mogą być tragiczne. Myśl o tym, że ktoś ma taką moc, jest niepokojąca, nawet jeśli optymistycznie podchodzisz do jej zamiarów. Pytanie, kto pierwszy opracuje działający komputer kwantowy, jest tym, na które wszyscy powinni uważnie obserwować, gdy przechodzimy do następnej dekady.

Czy martwi Cię niepewność szyfrowania komputerów kwantowych? Jakie masz zdanie? Podziel się swoimi przemyśleniami w komentarzach poniżej!

Kredyty obrazkowe: Kula binarna Via Shutterstock