Algorytm Shora (ang. Shor’s algorithm) to algorytm kwantowy, który w czasie wielomianowym rozkłada duże liczby na czynniki pierwsze i rozwiązuje problem logarytmu dyskretnego, także na krzywych eliptycznych. Opublikował go w 1994 roku Peter Shor, matematyk pracujący wtedy w Bell Labs.
To hasło opisuję, bo właśnie algorytm Shora stoi za każdym nagłówkiem typu „komputery kwantowe złamią bitcoina”. Podpisy, którymi autoryzujesz transakcje w Bitcoinie i Ethereum, opierają się na trudności logarytmu dyskretnego na krzywej eliptycznej. W 2025 i 2026 roku kilka prac naukowych mocno obniżyło szacunki sprzętu potrzebnego do ataku, więc temat przestał być czysto akademicki. Poniżej wyjaśniam, co algorytm Shora potrafi, czego nie potrafi i jak wygląda realny stan sprzętu na październik 2026 roku.
Co to jest algorytm Shora w prostych słowach
Kryptografia klucza publicznego działa jak kłódka, którą każdy może zatrzasnąć, ale otworzyć może tylko właściciel klucza. W RSA kłódka opiera się na tym, że łatwo pomnożyć dwie ogromne liczby pierwsze, a bardzo trudno odtworzyć je z wyniku. W bitcoinie opiera się na tym, że z klucza prywatnego łatwo policzyć klucz publiczny, a odwrotnie praktycznie się nie da. Algorytm Shora to wytrych, który obie te „jednokierunkowe” operacje odwraca, pod warunkiem że ma do dyspozycji duży i stabilny komputer kwantowy.
Pod spodem kryje się sprytny trik. Shor zauważył, że łamanie tych problemów można sprowadzić do znalezienia okresu pewnej funkcji, czyli odstępu, co jaki jej wartości zaczynają się powtarzać. Klasyczny komputer musiałby sprawdzać wartości jedna po drugiej. Komputer kwantowy wprowadza rejestr w superpozycję wielu wartości naraz, oblicza funkcję dla wszystkich jednocześnie, a potem stosuje kwantową transformatę Fouriera. Ta operacja działa jak stroik: wzmacnia wyniki zgodne z rytmem funkcji i wygasza resztę. Po pomiarze dostajesz informację o okresie, a z niej klasyczny komputer szybko wylicza czynniki albo klucz prywatny.
Co algorytm Shora łamie, a czego nie
Zagrożone są wszystkie popularne schematy oparte na faktoryzacji i logarytmie dyskretnym:
- RSA. Szyfrowanie i podpisy w certyfikatach, bankowości, poczcie, VPN-ach.
- Krzywe eliptyczne. Podpisy ECDSA i Schnorr używane w Bitcoinie (krzywa secp256k1), podpisy w Ethereum i większości blockchainów, a także krzywe NIST w przeglądarkach.
- Wymiana kluczy Diffie-Hellman. Zarówno klasyczna, jak i jej wersja na krzywych eliptycznych (ECDH), na której opiera się nawiązywanie bezpiecznych połączeń w internecie.
Algorytm Shora nie łamie natomiast funkcji skrótu (np. SHA-2, RIPEMD-160) ani szyfrów symetrycznych typu AES. W ich przypadku komputer kwantowy może użyć innego narzędzia, algorytmu Grovera, który daje tylko przyspieszenie kwadratowe i jest zagrożeniem nieporównywalnie mniejszym. Dlatego bitcoinowe kopanie i same adresy w postaci skrótu nie są głównym problemem. Problemem są podpisy.
Kubity fizyczne i logiczne, czyli dlaczego to wciąż trudne
Kubity w dzisiejszych maszynach są bardzo wrażliwe na zakłócenia. Typowy błąd bramki dwukubitowej w najlepszych systemach to rząd jednej pomyłki na tysiąc operacji, a algorytm Shora dla klucza 256-bitowego wymaga dziesiątek milionów operacji wykonanych bez błędu. Rozwiązaniem jest kwantowa korekcja błędów: wiele kubitów fizycznych wspólnie koduje jeden kubit logiczny, który jest znacznie stabilniejszy. W zależności od jakości sprzętu i użytego kodu na jeden kubit logiczny potrzeba od kilkudziesięciu do kilkuset kubitów fizycznych, plus dodatkowe zasoby na tzw. stany magiczne. Dlatego liczba kubitów z komunikatów prasowych niewiele mówi, liczą się kubity logiczne i długość obwodu, jaki da się na nich wykonać.
Demonstracje i „podrasowane” rekordy
W grudniu 2001 roku zespół IBM i Uniwersytetu Stanforda opisał w Nature rozłożenie liczby 15 na 3 × 5 algorytmem Shora na siedmiokubitowym komputerze NMR. W kolejnych latach pojawiały się „rekordy” z coraz większymi liczbami, ale wiele z nich miało haczyk. Już w 2013 roku John Smolin, Graeme Smith i Alexander Vargo pokazali, że jeśli przy projektowaniu obwodu wykorzysta się wcześniejszą znajomość wyniku, można „sfaktoryzować” dowolnie dużą liczbę na kilku kubitach, co nie ma nic wspólnego z prawdziwym atakiem.
W 2025 roku Peter Gutmann i Stephan Neuhaus opublikowali złośliwą pracę, w której powtórzyli rekordy kwantowej faktoryzacji przy pomocy 8-bitowego komputera VIC-20 z 1981 roku, liczydła i psa. Ich wniosek: część rekordów dotyczyła liczb dobranych tak, by ich czynniki różniły się kilkoma bitami, albo problem był wcześniej przekształcony na klasycznym komputerze. Uczciwe wykonanie algorytmu Shora nadal kończy się na liczbach dwucyfrowych.
Aktualne szacunki zasobów
Rekordy na sprzęcie są skromne, ale szacunki potrzebnych zasobów spadają szybko, głównie dzięki lepszym algorytmom i kodom korekcji:
- 2019, Gidney i Ekerå. RSA-2048 w około 8 godzin na około 20 mln zaszumionych kubitów fizycznych.
- Maj 2025, Craig Gidney (Google). RSA-2048 w mniej niż tydzień na mniej niż milionie zaszumionych kubitów fizycznych, przy założeniu błędu rzędu 0,1% na operację.
- Luty 2026, Iceberg Quantum. Architektura z kodami qLDPC, według autorów RSA-2048 poniżej 100 tys. kubitów fizycznych.
- 31 marca 2026, Google Quantum AI. Dla 256-bitowej krzywej eliptycznej, takiej jak w bitcoinie, około 1200–1450 kubitów logicznych, poniżej 500 tys. kubitów fizycznych i kilkadziesiąt milionów bramek Toffoliego. Po wstępnych obliczeniach odzyskanie jednego klucza miałoby trwać około 9 minut. Google nie opublikował samych obwodów, tylko dowód z wiedzą zerową, że je ma.
Stan sprzętu na październik 2026
Najlepsze publicznie znane maszyny są wciąż daleko od tych liczb. Quantinuum Helios (listopad 2025) ma 98 kubitów fizycznych i pokazał 48 kubitów logicznych z pełną korekcją błędów oraz 94 kubity z samą detekcją błędów. Google Willow ma 105 kubitów. IBM planuje na 2029 rok maszynę Starling z około 200 kubitami logicznymi, a Quantinuum na ten sam rok system Apollo. Do ataku na krzywą 256-bitową brakuje więc mniej więcej jednego rzędu wielkości w kubitach logicznych i kilku rzędów w długości bezbłędnych obliczeń. Mimo to Google wyznaczył 2029 rok jako własny termin migracji na kryptografię postkwantową i wezwał społeczności kryptowalut, by nie zwlekały.
Co to oznacza dla bitcoina
Algorytm Shora potrzebuje klucza publicznego. Dlatego narażenie Twoich monet zależy od tego, czy ten klucz jest już widoczny w łańcuchu:
- Wyjścia P2PK. Najstarsze transakcje, w tym monety z czasów Satoshiego, zawierają klucz publiczny wprost.
- Ponownie użyte adresy. Po pierwszym wydaniu z adresu P2PKH lub P2WPKH klucz publiczny jest w łańcuchu na zawsze. Jeśli na adresie zostały środki, są odsłonięte.
- Taproot. Wyjścia bc1p z założenia zawierają klucz publiczny, więc mają podobny profil ryzyka jak P2PK.
- Atak w oknie mempoolu. Nawet adres użyty raz ujawnia klucz w momencie wysłania transakcji. Jeśli atakujący odzyska klucz prywatny, zanim transakcja trafi do bloku, może wysłać konkurencyjną transakcję z wyższą opłatą. Przy szacunku Google około 9 minut na klucz i średnio 10 minutach na blok szansa powodzenia wychodzi na około 41% w idealnych warunkach.
Do tego dochodzi strategia harvest now, decrypt later (zbieraj teraz, odszyfruj później). W internecie to nagrywanie dziś zaszyfrowanego ruchu, by odczytać go za lata. W blockchainie nie trzeba nawet niczego nagrywać, bo każdy ujawniony klucz publiczny leży w łańcuchu na zawsze. Stąd propozycje BIP-360 (nowy typ wyjścia P2MR bez ujawniania klucza) i kontrowersyjny BIP-361 (etapowe wygaszanie starych podpisów i zamrożenie niezmigrowanych monet). Na październik 2026 roku obie mają status projektu.
Co to oznacza dla Ciebie
Nie musisz dziś niczego panicznie przenosić, ale kilka nawyków warto mieć już teraz. Uważaj też na tokeny i usługi „chroniące przed kwantami”, to dziś głównie marketing.
- Nie używaj ponownie adresów. Nowy adres przy każdym odbiorze ogranicza liczbę odsłoniętych kluczy publicznych.
- Sprawdź stare portfele. Monety na adresie, z którego już coś wysyłałeś, rozważ przenieść na świeży adres.
- Śledź kubity logiczne, nie nagłówki. Realny sygnał to liczba stabilnych kubitów logicznych i długość obwodów, a nie „rekordowa faktoryzacja”.
Ryzyka związane z algorytmem Shora
- Kradzież z odsłoniętych adresów. Pierwszym celem byłyby monety z jawnym kluczem publicznym, w tym stare wyjścia P2PK.
- Szok podażowy. Nagłe uruchomienie dużej liczby uśpionych monet mogłoby wywołać gwałtowną przecenę na całym rynku krypto.
- Spóźniona migracja. Zmiana podpisów w Bitcoinie wymaga konsensusu i ruchu od milionów użytkowników, co może trwać latami.
- Niepewność szacunków. Ostatnie lata pokazały, że postęp algorytmiczny potrafi obniżyć wymagania kilkukrotnie w ciągu jednej publikacji.
Najczęstsze pytania o algorytm Shora
Czy algorytm Shora już złamał jakiś klucz bitcoina?
Nie. Żaden istniejący komputer kwantowy nie jest bliski takiej możliwości. Uczciwe demonstracje dotyczą liczb dwucyfrowych.
Ile kubitów potrzeba do złamania bitcoina?
Według pracy Google z 31 marca 2026 roku około 1200–1450 kubitów logicznych, czyli poniżej 500 tys. kubitów fizycznych o odpowiedniej jakości. Dzisiejsze maszyny mają rząd stu kubitów fizycznych i kilkudziesięciu logicznych.
Czy adres, z którego nic nie wysłałem, jest bezpieczny?
Wobec algorytmu Shora jest znacznie bezpieczniejszy, bo klucz publiczny ukrywa się za skrótem. Odsłania się dopiero w momencie wydania środków.
Podsumowanie
Algorytm Shora, opublikowany przez Petera Shora w 1994 roku, pozwala komputerowi kwantowemu łamać RSA, Diffie-Hellmana i podpisy na krzywych eliptycznych, w tym te, które chronią bitcoina. Nie łamie funkcji skrótu ani AES. Dzisiejszy sprzęt jest od ataku daleko, a uczciwe demonstracje kończą się na liczbach dwucyfrowych, ale szacunki zasobów spadły w ostatnich latach wielokrotnie: według Google z marca 2026 roku na krzywą 256-bitową wystarczy około 1200–1450 kubitów logicznych. Dla Ciebie najważniejsze jest unikanie ponownego używania adresów i obserwowanie, jak Bitcoin przygotowuje migrację podpisów.
