Jag börjar nu skriva en serie lättlästa dagliga inlägg om post-kvantsäkerhet. Men jag har ingen aning om hur många dagar det kommer att pågå :). Så, låt oss se. DAG 1: Shors algoritm och kvantapokalyps(?) Största delen av vår säkerhetsstack—RSA, ECC, Diffie-Hellman—bygger på ett enda antagande: Heltalsfaktorisering och diskreta loggar är "svåra." På klassisk kisel är de det. För att knäcka RSA-2048 skulle du helt enkelt behöva mer tid än universums ålder. Men detta är ingen fysisk lag. Det är en begränsning i klassisk beräkning. År 1994 visade Peter Shor att de kan lösas effektivt på en kvantdator. Shors algoritm använder inte bara brute force-tangenter; den använder kvant-Fouriertransformen (QFT [Inte kvantfältteori lol]) för att hitta perioden för en funktion f(x) = a^x mod N. När du väl har mensen, har du faktorerna. Och när du har faktorerna är den privata nyckeln död. Eftersom den privata nyckeln kan rekonstrueras från den publika nyckeln. Komplexitetsskiftet är den verkliga "apokalypsen." Vi går från subexponentiell tid till polynomtid O((log N)^3). Vi pratar inte om en 10x hastighetsökning; vi pratar om att gå från biljoner år till några timmar på en CRQC. Likt RSA är ECC (elliptisk kurvkryptografi) också INTE säkert. På grund av sin effektiva algebraiska gruppstruktur kräver det faktiskt färre logiska qubits än RSA-2048 att bryta en 256-bitars ECC-nyckel. --- Tack för att du läste! Imorgon ska vi diskutera varför hotet om HNDL (harvest-now-decrypt-later) innebär att post-kvant-övergången måste ske nu. (Visuell: Peter Shor)