Algebraa Shaora

Dlaczego RSA zaufuje złożoności rozkładu na liczbę pierwszą

Szyfrowanie RSA opiera się na jednej asymetrii: mnożenie dwóch dużych liczb pierwszych jest szybkie, ale odzyskiwanie tych liczb pierwszych z iloczynu jest, co do teraz dowiedziono klasycznie, bardzo wolne. Generuj dwie duże liczby pierwsze p i q, opublikuj ich iloczyn N = p·q jako moduł, a p i q utrzymaj w tajemnicy. Klucz prywatny wywodzi się z φ(N) = (p−1)(q−1), który nikt poza właścicielim klucza nie może obliczyć bez rozkładu N. Algorytm Petera Shora z 1994 roku był pierwszym algorytmem wielomianowym — klasycznym lub kwantowym — dla tego samego problemu, a to jest powodem, dla którego RSA-2048 i kryptografia krzywych eliptycznych są uważane za zagrożone dużym wystarczająco potęgowym komputerem kwantowym.

najlepszy klasyczny rozkład (GNFS): czas ≈ exp(N^(1/3)) dla RSA-2048: ~10²³ operacji algorytm Shora: czas ≈ O(n³) brakujące kwantowe drzwi dla RSA-2048: ~10¹⁰ operacji To dziesięcio-miejsce różnicy między skalowaniem wykładniczym a wielomianowym — nie szybszy wyszukiwania brutalnego, ale inny strukturalnie algorytm — jest to, co sprawia, że Algorytm Shora tak istotny, i dlaczego symulowanie nawet małej instancji tego algorytmu, jak to zrobiono w interaktywnym demo na tej stronie, jest warto wykonanie ręczne.

best classical factoring (GNFS):  time ≈ exp(N^(1/3))         for RSA-2048: ~10²³ operations
Shor's algorithm:                 time ≈ O(n³) quantum gates    for RSA-2048: ~10¹⁰ operations

Zredukowanie: czynnik rozkładu jest szukaniem okresu w ukrytej formie

Przede wszystkim, Shor nie zauważył szybszego sposobu wyszukiwania czynników bezpośrednio — zauważył, że rozkład N redukuje się do znalezienia okresu elementu losowo wybranego w grupie mnożenia modulo N. Wybierz losowy a tak, aby 1 < a < N i gcd(a,N) = 1 (jeśli gcd nie jest równe 1, to już odnalazłeś klasyczny czynnik, bez potrzeby komputera kwantowego). Ciąg a¹, a², a³, ... modulo N jest okresowy; nazwij jego okres r — najmniejszą dodatnią liczbę całkowitą taką, że aʳ ≡ 1 (modulo N). Jeśli r jest parzyste i a^(r/2) nie jest kongruentne z −1 modulo N, elementarna algebra dostarcza Ci czynnik bezpłatnie.

a^(r/2) ≡ 1 (modulo N) ⟹ (a^(r/2) − 1)(a^(r/2) + 1) ≡ 0 (modulo N) przykład: N = 15, a = 7 7¹=7, 7²=4, 7³=13, 7⁴=1 (modulo 15) → okres r = 4 a^(r/2) = 7² = 49 ≡ 4 (modulo 15) gcd(4−1, 15) = gcd(3, 15) = 3 ✓ znaleziony czynnik gcd(4+1, 15) = gcd(5, 15) = 5 ✓ inny czynnik znaleziony Znalezienie okresu klasycznie jest trudne — wyszukiwanie metoda „krok mały-krok duży” kosztuje O(√r), nadal eksponencjalnie w liczbie bitów — więc ta redukcja sama po sobie niczego nie kupuje bez szybkiego sposobu znalezienia r. To dokładnie to, co dostarcza komputer kwantowy.

a^(r/2) ≡ 1 (mod N)  ⟹  (a^(r/2) − 1)(a^(r/2) + 1) ≡ 0 (mod N)

worked example:  N = 15, a = 7
  7¹=7, 7²=4, 7³=13, 7⁴=1 (mod 15)  →  order r = 4
  a^(r/2) = 7² = 49 ≡ 4 (mod 15)
  gcd(4−1, 15) = gcd(3, 15) = 3      ✓ factor found
  gcd(4+1, 15) = gcd(5, 15) = 5      ✓ other factor found

Transformacja kwantowa Fouriera czyta okres

Transformacja kwantowa Fouriera (QFT) jest kwantowym odpowiednikiem transformacji Fouriera dyskretnej: zamiast przekształcać listę klasycznych liczb, przekształca amplitudy superpozycji stanów podstawowych kwantowych. Na n qubitach potrzebuje tylko n brakujących gate’ów i n(n−1)/2 obrótów fazowych kontrolowanych — O(n²) gate’ów w sumie, w przeciwieństwie do O(n·2ⁿ) dla klasycznej transformacji Fouriera dyskretnej nad tym samym przestrzenią z 2ⁿ elementami. Właściwość, która sprawia, że jest przydatna tutaj: poda QFT superpozycję, której amplitudy są okresowe o okresie r, a amplitudy wyjściowe skupiają się gęsto wokół wielokrotności N/r, które można następnie odczytać z pomiaru.

Podprogram kwantowy Shora wykorzystuje to dwiema rejestrów. Rejestr kontrolny jest umieszczony w uniformnej superpozycji nad każdym wartością x od 0 do N−1 za pomocą n brakujących gate’ów. Rejestr docelowy, z kolei, oblicza aˣ mod N — dla każdego x w superpozycji jednocześnie, dzięki kwantowej paralelizacji — przy użyciu O(n³) gate’ów budowanych na podstawie powtarzanej kwadracji. Pomiar rejestru docelowego zredukowuje go do jednej wartości, która w turze zredukowuje rejestr kontrolny do superpozycji dokładnie tych x-wartości, które produkują tę wartość: stan okresowy względem x o okresie r. Zastosowanie QFT do tej okresowej superpozycji i ponowny pomiar prowadzi do wyniku c, który jest prawdopodobnie bliski wielokrotności N/r.

Z noisowego pomiaru powrót do dokładnego okresu

QFT zwraca przybliżenie, c ≈ k·N/r dla nieznanej całkowitej liczby k — a nie r samej. Odtworzenie dokładnego okresu z c/N jest klasycznym problemem rozwiązywanym przez rozwinięcie ułamkowe: napisanie c/N w postaci rozwinięcia ułamka nieskrótnego i odczytanie jego konvergentów p/q daje najlepsze ułamki właściwe przybliżające c/N z małymi mianownikami, a każda kiedykolwiek |c/N − k/r| < 1/(2N), jedna z tych konvergentów równa się dokładnie k/r, odsłaniając r (lub mały wielokrotność jego, która jest rozstrzygnięta w kolejnej sprawdzeniu).

Jedno uruchomienie powoduje sukces z prawdopodobieństwem około 1/(2 ln r) ≈ 1/n, więc cała koncepcja — Hadamardy, modułowa potęgowanie, QFT, pomiar, rozwinięcie ułamkowe, gcd — jest oczekiwana na to, że będzie musiała być uruchomiona około O(n) razy przed tym, jak wygeneruje użyteczną czynnik. Każda kroku poza QFT i modułowym potęgowaniem wykonuje się na zwykłej klasycznej maszynie; sprzęt kwantowy jest tylko odpowiedzialny za ciężką pracę znalezienia okresu.

Ile kubitów potrzebuje na rzeczywistość RSA-2048

Rozkład liczby n-bitowej wymaga około 2n + 3 logicznych kubitów — około 4,000 dla modułu RSA-2048 o 2048 bitach — działając na około 10¹⁰ drzwi kwantowych. Przestrzeń między logicznymi a fizycznymi kubitami ukrywa rzeczywistą trudność: skorygowanie kodu powierzchinnego, liderowy schemat tolerujący błędy, wymaga około 1,000 nozyrzanych fizycznych kubitów na czysty logiczny kubit, co przekładając się na RSA-2048 daje około 4 miliony fizycznych kubitów. Największe procesory zbudowane do 2026 roku operują w dolnej tysiącowce fizycznych kubitów — między innymi Google Willow i IBM klasy Condor — więc rozkład kryptograficznie znaczący pozostaje problemem sprzętowym, pomiarowym na lata i dekady, a nie problemem programistycznym czekającym na lepszy algorytm.

Dlaczego migracja do kryptografii po-kwantowej się zaczyna teraz

Odległość od funkcjonującej wieloskalowej komputera kwantowego jest dokładnie tą przyczyną, dlaczym organizacje nie czekają na jego budowę. Przeprowadzone obecnie ruchy zaszyfrowane mogą być prosto przechowywane i odszyfrowywane po tym, jak pojawi się odpowiednie sprzęt — atak „sodbierz teraz, odszyfruj później”, który zagrożeniem stanowi tylko dane, które nadal muszą pozostać tajne kilka lat stąd. W 2024 roku NIST zakończyła publiczny przegląd i wprowadziła swoje pierwsze standardy kryptografii po-kwantowej: ML-KEM (dawniej CRYSTALS-Kyber) dla wymiany kluczy, ML-DSA (dawniej Dilithium) dla podpisów, a także SLH-DSA i FN-DSA jako alternatywy oparte na innych trudnych problemach. Oba te standardy zależą od problemów opartych na siatce lub zasada haszująca, które są przeciwdziałane atakom kwantowym, w przeciwieństwie do problemu rozkładu liczb dla RSA. Dla kluczowych przeglądów i dostawców CDN już zastosowano schematy hybrydowe, które wykonują obok siebie algorytm klasyczny i po-kwantowy, co oznacza, że obecne połączenia pozostają chronione nawet wtedy, gdy jedna z dwóch metod okazuje się być w końcu słaba.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Shor's Algorithm i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.