Algorytmy Shora i Grovera — wyjaśnienie

Komputery kwantowe nie tylko uruchamiają klasyczne algorytmy szybciej — wykorzystują superpozycję kwantową i interferencję, aby rozwiązywać niektóre problemy wykładniczo szybciej. Dwa algorytmy zagrażają większości wdrożonych systemów kryptograficznych: algorytm Shora (łamie RSA/ECC) i algorytm Grovera (osłabia kryptografię symetryczną oraz funkcje skrótu).

Algorytm Shora (1994) rozwiązuje problem faktoryzacji liczb całkowitych i problem logarytmu dyskretnego w czasie wielomianowym na komputerze kwantowym. Bezpośrednio łamie to RSA (oparty na faktoryzacji), Diffie-Hellman (logarytm dyskretny modulo p) oraz ECDH/ECDSA (logarytm dyskretny na krzywych eliptycznych).

Kluczowym elementem algorytmu Shora jest kwantowa transformata Fouriera (QFT) — wykładniczo szybsza kwantowa wersja DFT. Podczas wyszukiwania okresu QFT identyfikuje okres funkcji f(x) = a^x mod N, na podstawie którego czynniki N są wyznaczane za pomocą GCD.

Aby rozłożyć N na czynniki: (1) należy wybrać losowe a < N i sprawdzić gcd(a,N)=1. (2) Należy znaleźć okres r funkcji f(x)=a^x mod N za pomocą QFT. (3) Z dużym prawdopodobieństwem gcd(a^{r/2}±1, N) daje nietrywialny czynnik. Krok klasyczny ma złożoność O(log N); kwantowe wyszukiwanie okresu ma złożoność O((log N)^3) — jest to czas wielomianowy.

Najlepsza klasyczna metoda faktoryzacji: GNFS — podwykładnicza złożoność O(exp((64/9 log N)^{1/3} log log N)^{2/3})). Algorytm Shora na odpornym na błędy komputerze kwantowym: wielomianowa złożoność O((log N)^3). RSA-2048 wymaga około 4000 kubitów logicznych i około 10^9 operacji bramek. Dzisiejsze komputery NISQ mają około 1000 zaszumionych kubitów — nie stanowią jeszcze zagrożenia.

Algorytm Grovera (1996) zapewnia kwadratowe przyspieszenie dla wyszukiwania nieustrukturyzowanego. Dla przestrzeni wyszukiwania zawierającej N elementów algorytmy klasyczne potrzebują O(N) zapytań, a algorytm Grovera — O(√N). Zastosowany do kryptografii łamie n-bitowe klucze symetryczne w O(2^{n/2}) zamiast O(2^n).

AES-128: bezpieczeństwo klasyczne 2^128, algorytm Grovera zmniejsza je do 2^64 — taki poziom jest niebezpieczny w obliczu dużego komputera kwantowego. AES-256: 2^256 → 2^128 — nadal bezpieczny. Rozwiązanie: podwoić rozmiary kluczy symetrycznych. Odporność SHA-256 na kolizje: 2^128 → 2^85 (paradoks urodzinowy + algorytm Grovera). Odporność SHA-256 na znalezienie preobrazu: 2^256 → 2^128 — wystarczająca.

Obecne komputery kwantowe NISQ (IBM Heron: 133 kubity, Google Sycamore: 70 kubitów) są zbyt małe i zbyt zaszumione, aby wykonywać obliczenia istotne kryptograficznie. Szacunki dotyczące złamania RSA-2048 wskazują na lata 2035–2050 w przypadku odpornych na błędy komputerów kwantowych. Ataki typu harvest-now-decrypt-later stanowią zagrożenie już dziś.

Przeciwnicy gromadzą dziś zaszyfrowany ruch i przechowują go. Gdy dostępny będzie komputer kwantowy, odszyfrują te dane wstecz. Oznacza to, że dane wymagające zachowania poufności przez długi czas (niejawne dane rządowe, dokumentacja medyczna) są już dziś narażone. W przypadku takich danych migrację do PQC należy rozpocząć teraz.

Problemy kratowe (LWE, SIS), problemy oparte na kodach (McEliece), podpisy oparte na funkcjach skrótu (SPHINCS+), problemy wielomianowe — nie jest znany żaden kwantowy algorytm działający w czasie wielomianowym. Stanowią one podstawę postkwantowych standardów NIST.

Standardy NIST PQC (ML-KEM, ML-DSA, SLH-DSA) zostały sfinalizowane w 2024 roku. Organizacje powinny: zinwentaryzować obecnie używaną kryptografię, zidentyfikować dane wymagające długoterminowej ochrony oraz nadać priorytet wdrożeniu PQC dla wymiany kluczy (najpilniejszej ze względu na ataki harvest-now-decrypt-later). W przypadku podpisów jest więcej czasu.

Algorytm Shora (czas wielomianowy) łamie RSA, DH i ECC. Algorytm Grovera (kwadratowe przyspieszenie) zmniejsza o połowę siłę kluczy symetrycznych. Rozwiązanie: migracja do standardów NIST PQC (opartych na kratach). Dalej: CRYSTALS-Kyber KEM.