Jeg starter en serie lettleste daglige innlegg om post-kvantesikkerhet. Men jeg har ingen anelse om hvor mange dager det vil vare :). Så, la oss se. DAG 1: Shors algoritme og kvanteapokalypse(?) Mesteparten av vår sikkerhetsstakk – RSA, ECC, Diffie-Hellman – baserer seg på én antakelse: Heltallsfaktorisering og diskrete logger er "vanskelige." På klassisk silisium er de det. For å knekke RSA-2048 trenger du rett og slett mer tid enn universets alder. Men dette er ikke en fysisk lov. Det er en begrensning ved klassisk beregning. I 1994 viste Peter Shor at de kan løses effektivt på en kvantedatamaskin. Shors algoritme bruker ikke bare nøkler med brute force; den bruker kvante-Fourier-transformasjonen (QFT [Ikke kvantefeltteori lol]) for å finne perioden til en funksjon f(x) = a^x mod N. Når du har mensen, har du faktorene. Og når du har faktorene, er den private nøkkelen død. Fordi den private nøkkelen kan rekonstrueres fra den offentlige nøkkelen. Kompleksitetsskiftet er den virkelige «apokalypsen». Vi går fra sub-eksponentiell tid til polynomisk tid O((log N)^3). Vi snakker ikke om en 10x økning; vi snakker om å gå fra billioner av år til noen timer på en CRQC. På samme måte som RSA er ECC (elliptisk kurvekryptografi) heller IKKE trygt. På grunn av sin effektive algebraiske gruppestruktur krever det faktisk færre logiske qubiter å bryte en 256-bits ECC-nøkkel enn RSA-2048. --- Takk for at du leste! I morgen skal vi diskutere hvorfor trusselen om HNDL (harvest-now-decrypt-later) betyr at post-kvante-overgangen må skje nå. (Visuell: Peter Shor)