Zaczynam serię łatwych do przeczytania codziennych postów na temat bezpieczeństwa post-kwantowego. Ale nie mam pojęcia, jak długo to potrwa :). Zobaczymy. DZIEŃ 1: Algorytm Shora i Apokalipsa Kwantowa(?) Większość naszego stosu zabezpieczeń—RSA, ECC, Diffie-Hellman—opiera się na jednym założeniu: Rozkład liczb całkowitych i logarytmy dyskretne są "trudne." Na klasycznym krzemie, są. Aby złamać RSA-2048, potrzebowałbyś po prostu więcej czasu niż wiek wszechświata. Ale to nie jest prawo fizyczne. To ograniczenie klasycznego obliczenia. W 1994 roku Peter Shor pokazał, że można je rozwiązać efektywnie na komputerze kwantowym. Algorytm Shora nie tylko brutalnie łamie klucze; wykorzystuje Kwantową Transformację Fouriera (QFT [Nie teoria pól kwantowych lol]), aby znaleźć okres funkcji f(x) = a^x mod N. Gdy masz okres, masz czynniki. A gdy masz czynniki, klucz prywatny jest martwy. Ponieważ klucz prywatny można odtworzyć z klucza publicznego. Zmiana złożoności to prawdziwa "apokalipsa." Przechodzimy z czasu sub-eksponencjalnego do czasu wielomianowego O((log N)^3). Nie mówimy o przyspieszeniu 10x; mówimy o przejściu z bilionów lat do kilku godzin na CRQC. Podobnie jak w przypadku RSA, ECC (kryptografia krzywych eliptycznych) również NIE jest bezpieczne. Z powodu swojej efektywnej struktury grupy algebraicznej, złamanie 256-bitowego klucza ECC wymaga w rzeczywistości mniej logicznych kubitów niż RSA-2048. --- Dzięki za przeczytanie! Jutro omówimy, dlaczego zagrożenie HNDL (zbieraj-teraz-odszyfruj-później) oznacza, że przejście na post-kwantowe musi nastąpić teraz. (Wizualizacja: Peter Shor)