Jak algorytm Shora łamie RSA i ECC?

Zamienia trudne problemy, na których się opierają, w łatwe. RSA jest bezpieczne, bo nikt nie potrafi w rozsądnym czasie rozłożyć bardzo dużej liczby na dwa czynniki pierwsze; kryptografia krzywych eliptycznych jest bezpieczna, bo nikt nie potrafi odtworzyć tajnej liczby stojącej za publicznym punktem na krzywej. Peter Shor pokazał w 1994 r., że komputer kwantowy potrafi znaleźć w obu problemach ukryty powtarzający się wzór, okres, a z tego okresu szybko wynika sekret. Na dostatecznie dużej maszynie atak zajmuje praktyczny czas zamiast niewykonalnego. Dłuższe klucze nie ratują RSA ani ECC: jedynie nieco spowalniają atak kwantowy. Dlatego odpowiedzią jest nowa matematyka, na przykład problemy kratowe, na których opierają się ML-KEM i ML-DSA, a dla których nie jest znany wydajny algorytm kwantowy. Opublikowane szacunki potrzebnej maszyny wciąż znacznie wykraczają poza wszystko, co dotąd zbudowano.

← Wszystkie pytania (33): Kryptografia postkwantowaWszystkie tematy