Algorytm Grovera

Algorytm Grovera (ang. Grover’s algorithm) to algorytm kwantowy do przeszukiwania nieuporządkowanego zbioru, który znajduje szukany element w około √N krokach zamiast około N kroków potrzebnych klasycznie. Opisał go w 1996 roku Lov Grover z Bell Labs. Udowodniono też, że w tego typu zadaniach komputer kwantowy nie może zrobić tego istotnie szybciej, więc przyspieszenie kwadratowe to sufit, a nie wstęp do czegoś więcej.

Algorytm Grovera to drugi, obok algorytmu Shora, kwantowy algorytm, który pojawia się w dyskusjach o bezpieczeństwie kryptowalut. Dotyczy jednak innych elementów: szyfrów symetrycznych, funkcji skrótu i kopania bitcoina. Z mojej perspektywy warto go rozumieć głównie po to, żeby nie dać się nabrać na tezę, że komputer kwantowy „złamie SHA-256” albo przejmie wydobycie bitcoina. Poniżej pokazuję, dlaczego jest to zagrożenie realne na papierze, ale znacznie słabsze w praktyce.

Co to jest algorytm Grovera w prostych słowach

Wyobraź sobie zamek szyfrowy z milionem kombinacji. Klasycznie, w najgorszym przypadku, sprawdzasz milion kombinacji, a średnio pół miliona. Algorytm Grovera pozwala znaleźć właściwą w około tysiącu kroków, czyli w pierwiastku z miliona. Brzmi imponująco, ale przy kryptografii kluczową rolę gra skala: jeśli kombinacji jest 2^128, to pierwiastek wynosi 2^64, a jeśli 2^256, to wciąż 2^128. Przyspieszenie kwadratowe działa więc tak, jakby klucz był o połowę krótszy, a nie jakby przestał istnieć.

Mechanizm opiera się na tzw. wzmacnianiu amplitudy. Komputer kwantowy zaczyna od równej superpozycji wszystkich możliwych odpowiedzi. Specjalny podukład, nazywany wyrocznią, „oznacza” poprawną odpowiedź zmianą znaku. Następnie operacja dyfuzji odbija wszystkie amplitudy względem średniej. Każde powtórzenie tej pary kroków trochę zwiększa prawdopodobieństwo trafienia w dobrą odpowiedź i zmniejsza resztę. Po około √N powtórzeniach pomiar z dużym prawdopodobieństwem daje szukany wynik. Ważne: tych powtórzeń nie da się wykonać naraz, muszą iść jedno po drugim.

Grover a szyfry symetryczne i funkcje skrótu

W kryptografii algorytm Grovera to po prostu szybszy atak siłowy. Dla popularnych zastosowań wygląda to tak:

• AES-128. Klasycznie 2^128 prób, z Groverem teoretycznie około 2^64 iteracji. Stąd często powtarzane uproszczenie, że AES-128 „ma 64 bity bezpieczeństwa” wobec komputera kwantowego.
• AES-256. Około 2^128 iteracji Grovera, czyli poziom uznawany za bezpieczny na dziesięciolecia.
• Odwracanie skrótu (preimage) SHA-256. Klasycznie około 2^256 prób, z Groverem około 2^128. To nadal poza zasięgiem jakiejkolwiek przewidywalnej technologii.
• Kolizje skrótów. Istnieje kwantowy algorytm Brassarda, Høyera i Tappa (BHT, oparty na Groverze), który teoretycznie obniża koszt szukania kolizji SHA-256 z około 2^128 do około 2^85 zapytań. Wymaga jednak ogromnej pamięci, a analizy kosztów, m.in. Daniela J. Bernsteina z 2009 roku, wskazują, że po uwzględnieniu sprzętu nie wypada lepiej niż klasyczne równoległe szukanie kolizji. Traktuj to jako ciekawostkę teoretyczną.

Dlaczego Grover jest dużo słabszy od Shora

Uproszczenie „AES-128 ma tylko 64 bity” jest mylące, bo pomija koszt praktyczny. Kilka powodów:

• Przyspieszenie tylko kwadratowe. Algorytm Shora zamienia problem wykładniczy w wielomianowy. Grover tylko skraca wykładnik o połowę, więc wystarczy dłuższy klucz, żeby odzyskać margines.
• Słabe zrównoleglanie. Klasyczny atak siłowy dzielisz na tysiąc maszyn i kończysz tysiąc razy szybciej. Przy Groverze podział przestrzeni na M części skraca czas tylko √M razy, a łączna praca rośnie. Im krótszy termin ataku, tym mniej zostaje z przewagi kwantowej.
• Ogromna głębokość obwodu. Każda iteracja Grovera to pełne obliczenie AES albo SHA-256 w wersji kwantowej, z korekcją błędów, na kubitach logicznych działających tysiące razy wolniej niż tranzystory. 2^64 takich kroków wykonanych po kolei to czas liczony w latach nawet przy bardzo optymistycznych założeniach.

Dlatego NIST przyjął odporność na przeszukanie klucza AES-128 jako najniższą kategorię bezpieczeństwa (Category 1) w standaryzacji kryptografii postkwantowej i ocenia, że algorytm Grovera da tu niewielką albo żadną realną przewagę. Analiza Filippo Valsordy z kwietnia 2026 roku szacuje, że złamanie AES-128 w ciągu dekady wymagałoby około 2^47 równoległych maszyn kwantowych. Dla porównania atak Shora na krzywą 256-bitową potrzebuje według Google z marca 2026 roku rzędu dziesiątek milionów bramek na jednym urządzeniu. To pokazuje, gdzie leży prawdziwe ryzyko.

Kopanie bitcoina z algorytmem Grovera

Proof of Work w Bitcoinie to w istocie przeszukiwanie: koparka zmienia nonce i inne pola nagłówka bloku, aż podwójny SHA-256 da wynik poniżej celu trudności. Teoretycznie Grover daje tu przyspieszenie kwadratowe, czyli kwantowa koparka potrzebowałaby pierwiastka z liczby prób potrzebnych klasycznie.

W praktyce sprawa wygląda inaczej. Praca Divesha Aggarwala i współautorów z 2017 roku („Quantum attacks on Bitcoin, and how to protect against them”) doszła do wniosku, że Proof of Work w Bitcoinie jest względnie odporny na istotne przyspieszenie kwantowe przez co najmniej 10 lat, głównie dlatego, że wyspecjalizowane koparki ASIC są ekstremalnie szybkie w porównaniu z przewidywaną częstotliwością pracy komputerów kwantowych. Dochodzą do tego ograniczenia samego Bitcoina:

• Limit czasu. Iteracje Grovera muszą zmieścić się w czasie bloku, średnio około 10 minut. Nie da się ich rozłożyć na tygodnie.
• Słabe zrównoleglanie. Farmę ASIC skalujesz liniowo. Farmę kwantowych koparek skalujesz gorzej, z tego samego powodu co przy łamaniu AES.
• Dostosowanie trudności. Nawet gdyby kwantowa koparka kiedyś dorównała ASIC-om, sieć po prostu dostosuje trudność. To byłaby nowa, wydajniejsza koparka, a nie złamanie protokołu.

Teoretycznie można sobie wyobrazić przyszłość, w której kwantowe koparki dają przewagę na tyle dużą, że sprzyjają centralizacji wydobycia. To jednak scenariusz odległy i dużo mniej pilny niż zagrożenie dla podpisów.

Grover a adresy bitcoina

Klasyczne adresy P2PKH i P2WPKH to skrót klucza publicznego: najpierw SHA-256, potem RIPEMD-160, w sumie 160 bitów. Żeby ukraść środki z takiego adresu samym Groverem, trzeba by znaleźć klucz prywatny, którego klucz publiczny daje ten sam skrót. Nawet z przyspieszeniem kwadratowym to około 2^80 iteracji wykonywanych po kolei, a każda zawiera mnożenie punktu na krzywej i dwa skróty. To praktycznie niewykonalne. Dlatego realne ryzyko dla adresów nie wynika z Grovera, tylko z momentu, gdy klucz publiczny zostaje ujawniony i wchodzi do gry algorytm Shora.

Co to oznacza dla Ciebie

• SHA-256 i kopanie bitcoina nie są w realnym niebezpieczeństwie. Jeśli ktoś przekonuje Cię inaczej, zwykle sprzedaje „kwantowo odporny” token.
• Szyfrowanie symetryczne wystarczy wydłużyć. Wiele systemów i tak przechodzi na AES-256, co z nawiązką pokrywa efekt Grovera.
• Silne hasło do zaszyfrowanego backupu ma znaczenie. Słabe hasło złamie klasyczny komputer szybciej niż jakikolwiek algorytm kwantowy. Grover tego nie zmienia.
• Uwagę kieruj na podpisy. W portfelach liczy się przede wszystkim to, czy Twój klucz publiczny jest ujawniony.

Ryzyka związane z algorytmem Grovera

• Mylenie z Shorem. Wrzucanie obu algorytmów do jednego worka prowadzi do przesadzonych wniosków, np. że „kwanty złamią SHA-256”.
• Krótkie klucze symetryczne. Systemy z kluczami poniżej 128 bitów mogą w przyszłości stracić margines bezpieczeństwa.
• Centralizacja wydobycia w dalekiej przyszłości. Gdyby kwantowe koparki kiedyś przegoniły ASIC-i, przewagę dostałby ten, kto ma do nich dostęp.
• Marketing strachu. Projekty reklamujące „ochronę przed Groverem” często rozwiązują problem, który praktycznie nie istnieje.

Najczęstsze pytania o algorytm Grovera

Czy algorytm Grovera złamie SHA-256?

Nie. Obniża koszt odwrócenia skrótu z około 2^256 do około 2^128 kroków, co pozostaje poza zasięgiem jakiejkolwiek przewidywalnej technologii.

Czy AES-128 jest bezpieczny wobec komputerów kwantowych?

NIST traktuje go jako punkt odniesienia dla najniższej kategorii bezpieczeństwa postkwantowego i uznaje, że Grover da tu niewielką przewagę. Kto chce dodatkowego marginesu, wybiera AES-256.

Czy komputer kwantowy przejmie kopanie bitcoina?

W dającej się przewidzieć przyszłości nie. Analizy wskazują, że koparki ASIC pozostaną dużo szybsze, a ewentualną przewagę zniwelowałoby dostosowanie trudności.

Czym algorytm Grovera różni się od algorytmu Shora?

Grover daje przyspieszenie kwadratowe w przeszukiwaniu i dotyczy szyfrów symetrycznych oraz skrótów. Shor daje przyspieszenie wykładnicze i łamie kryptografię klucza publicznego, w tym podpisy w bitcoinie.

Podsumowanie

Algorytm Grovera, opisany przez Lova Grovera w 1996 roku, przyspiesza przeszukiwanie kwadratowo, czyli w praktyce „skraca” klucze symetryczne i skróty o połowę bitów. AES-256 i SHA-256 nadal zachowują ok. 128 bitów bezpieczeństwa, a przez słabe zrównoleglanie i ogromną głębokość obwodu nawet AES-128 jest uznawany za akceptowalny. Kopanie bitcoina i adresy w postaci skrótu nie są realnie zagrożone przez Grovera. Prawdziwy kwantowy problem kryptowalut to podpisy i algorytm Shora, nie przeszukiwanie.