Shors algoritme: ressursbehovet for å knekke RSA-2048 falt en størrelsesorden på under ett år

Krypteringen som beskytter moderne digital infrastruktur, kollapser ikke i det øyeblikket en kvantecomputer bygges. Den kollapser i det øyeblikket motstandere skaffer seg nok kvantekapasitet til å dekryptere data de allerede har samlet inn. Denne tidsmessige inversjonen — trusselen kommer før maskinen — definerer Q-Day-problemets reelle struktur og forklarer hvorfor beredskapsunderskuddet som måles i dag, direkte omsettes til et sikkerhetsbrudd målt i år.

Mekanismen som er i faresonen, er ikke obskur. RSA-kryptering, den dominerende standarden for asymmetrisk kryptografi, hviler på en enkelt matematisk asymmetri: å multiplisere to store primtall er beregningsteknisk trivielt, men å gjenvinne dem fra produktet skalerer i vanskelighetsgrad så bratt at ingen klassisk datamaskin kan reversere operasjonen for nøkkellengder på 2048 bit eller mer innenfor en praktisk tidsramme. TLS-håndtrykk som sikrer nettverkstrafikk, sertifikatmyndigheter som autentiserer identiteter, digitale signaturer som validerer finansielle transaksjoner: hele arkitekturen for betrodd digital kommunikasjon hviler på denne asymmetrien.

Shors algoritme, formalisert i 1994, beviste at kvanteberegning fullstendig løser opp denne asymmetrien. Ved å utnytte kvanteoverlapping og kvantefouriertransformasjoner for å finne perioden til en modulær aritmetisk funksjon som koder faktoriseringsproblemet, ville en tilstrekkelig stor kvantecomputer kunne gjenvinne RSA-privatnøkler på timer, ikke de milliardene av år en klassisk maskin ville kreve. Algoritmen har vært kjent i tre tiår. Det som endret seg det siste året, er ressursestimatet for å kjøre den.

Du vil kanskje også likePixel Maniacs og PM Studios annonserer det fargebaserte hjernetrimspillet ChromaGun 2: Dye Hard

Hardwarekravene for en kryptografisk relevant kvantecomputer var inntil nylig så enormes at de fungerte som en praktisk barriere. Tidlige estimater plasserte antallet fysiske qubiter som trengs for å faktorisere RSA-2048, på rundt en milliard. I 2021 hadde Gidney og Ekerå redusert dette estimatet til omtrent tjue millioner qubiter i åtte timers drift. Deretter, på under tolv måneder mellom 2024 og 2025, kollapset tre algoritmiske fremskritt estimatet med ytterligere en størrelsesorden.

Det første var en omstrukturering av hvordan modulær eksponentiering — den sentrale beregningsoperasjonen i Shors algoritme — utføres. Den klassiske tilnærmingen krevde kvanteregistre som var store nok til å holde 2048-bit heltall simultant. Approksimativ modulær aritmetikk, utviklet av Chevignard, Fouque og Schrottenloher, erstattet dette med en segmentert tilnærming som beregner eksponentiering i deler ved hjelp av langt mindre registre og tolererer kontrollerte feil som kan korrigeres etterpå. Det andre fremskrittet adresserte den dominerende kostnadsbegrensningen i feiltolerante kvanteberegninger: å generere de spesielle kvantressursstilstandene som trengs for ikke-feilrettbare gateoperasjoner. Magic state cultivation, utviklet hos Google Quantum AI, dyrker tilstander med høy troskap fra tilstander av lavere kvalitet med drastisk redusert overhead sammenlignet med tradisjonell destillasjon. Det tredje fremskrittet, syntetisert i Craig Gidneys artikkel fra 2025, kombinerte begge teknikkene og reduserte det totale antallet påkrevde Toffoli-gateoperasjoner fra omtrent to billioner til omtrent 6,5 milliarder, en mer enn hundredoblet forbedring i beregningseffektivitet.

Det kombinerte resultatet: å faktorisere RSA-2048 virker nå teknisk gjennomførbart med omtrent en million fysiske qubiter i omtrent en ukes drift. Hardware-kløften mellom dette kravet og eksisterende systemer er fortsatt reell, men kompresjonsbanens karakter har endret seg kvalitativt. Å redusere fra en milliard til tjue millioner qubiter tok tolv år; å redusere fra tjue millioner til under en million tok under ett år. Denne akselerasjonen er det analytisk viktige signalet.

Parallelle hardwarefremskritt styrker denne banen. Googles Willow-brikke, demonstrert mot slutten av 2024, leverte den første eksperimentelle bekreftelsen på at kvantefeilkorrigering kan undertrykke støy under terskelen for overflate-koden. IBMs publiserte veikart projiserer den første storskala feiltolerante kvantecomputeren med omtrent 200 logiske qubiter til 2029. Flere uavhengige plattformer har demonstrert to-qubit-gatetroskap på 99,9% eller høyere. Kløften mellom teoretiske ressurskrav og demonstrert hardwarekapasitet har komprimert seg fra flere størrelsesordener til noe nær én.

Denne kompresjonen gir materiell hast til en trussel som hittil er blitt behandlet som bekvemt fjern: samle nå, dekryptere senere. Statslige og sofistikerte ikke-statlige aktører som har samlet kryptert nettverkstrafikk i årevis, besitter kryptotekst som blir lesbar i det øyeblikket en kryptografisk relevant kvantecomputer eksisterer. Den rette tidsrammen for å vurdere Q-Day-risikoen er ikke når kvantecomputere vil bli bygget, men hvor lenge data kryptert i dag må forbli konfidensielle.

Det kryptografiske svaret på denne trusselen har et navn, et sett med standarder og en etterlevelsestidsplan. Postkvantkryptografi erstatter heltallsfaktoriserings- og diskrete logaritmeproblemene som ligger til grunn for RSA og elliptisk kurve-kryptografi med matematiske strukturer som anses resistente mot både klassiske og kvanteangrep. Den primære familien adoptert av globale standardiseringsorganer er gitterbasert kryptografi, som begrunner sikkerheten sin i vanskelighetsgraden av det korteste vektorproblemet og relaterte geometriske utfordringer i høydimensjonale rom. I august 2024 ferdigstilte NIST tre postkvantkryptografistandarder. I mars 2025 ble en femte algoritme, HQC, valgt som et kodebasert alternativ til ML-KEM.

Anbefalt lesningDen algoritmiske seansen: Sorg, dataisme og endelighetens død

Eksistensen av standarder løser ikke migreringsproblemet. Den innleder det. Kryptografiske overganger i denne skalaen har historisk krevd femten til tjue år for full infrastrukturpenetrasjon, og denne migreringen er strukturelt mer kompleks enn noe tidligere eksempel. Infrastrukturen for offentlige nøkler må redesignes på hvert lag. Hardwaresikkerhetsmoduler som lagrer og administrerer nøkler, må erstattes eller oppgraderes; sertifikatmyndigheter må utstede nye legitimasjonshierarkier; TLS-implementasjoner på milliarder av endepunkter må oppdateres; protokoller innebygd i innebygde systemer, industriell styringsinfrastruktur og langlivede finansielle systemer må revideres og erstattes.

Norges posisjon som en avansert digital økonomi med sterk offentlig sektors digitalisering og engasjement i EUs koordinerte cybersikkerhetspolitikk gir et spesifikt insentiv til å behandle denne migreringen med den langsiktige, systemtenkte tilnærmingen som preger norsk offentlig forvaltning. Det regulatoriske rammeverket har svart med en komprimert tidsplan som gjenspeiler hardwarebanens hast. NSAs CNSA 2.0 krever at alle nye nasjonale sikkerhetssystemer er quantum-safe innen januar 2027. EUs NIS-samarbeidsgruppe publiserte i 2025 en koordinert implementeringsveiledning. IBM Institute for Business Values kvantsikkerhetsberedskapsvurdering fra 2025 fant en global gjennomsnittscore på bare 25 av 100.

Det praktiske rådet som fremgår av dette tekniske landskapet, er ikke panikk, men graduert, prioritert handling. Kryptografisk inventering er forutsetningen. Systemer som håndterer data med lange konfidensialitetshorisonter, må prioriteres for tidlig migrering. Hybride kryptografiske utrullinger, som kombinerer ML-KEM med klassiske nøkkelutvekslingsalgoritmer parallelt, tilbyr en praktisk bro: data beskyttet av et hybridskjema krever at en motstander simultant bryter de klassiske og postkvantkryptografiske komponentene, noe som i vesentlig grad hever kostnadene ved ethvert innsamlings- og dekrypteringsangrep.

Det algoritmiske fremskrittet i 2024 og 2025 har fundamentalt endret usikkerhetsfordelingen rundt Q-Day. Den tidligere konsensus plasserte bekvemt kryptografisk relevant kvanteberegning i 2030-årene, med betydelige feilmarginer som strakte seg mot 2040-årene. Kompresjonen av ressursestimater til under en million qubiter, kombinert med IBMs veikart for 2029 og Googles eksperimentelle bekreftelse av feilkorrigering under terskelen, har forskjøvet troverdige estimater meningsfullt fremover og innsnevret usikkerhetsintervallet.

Overgangen til postkvantkryptografi slutter ikke med utrullingen av gitterbaserte algoritmer. Den skaper en ny kryptografisk overflate hvis langsiktige sikkerhet avhenger av antakelser om vanskelighetsgraden av geometriske problemer i høydimensjonale rom — antakelser som har motstått tiår med klassisk kryptoanalyse, men som ennå ikke er blitt satt på prøve av kvantecomputere som til slutt vil eksistere i stor skala. Det som kreves av det nåværende øyeblikket, er ikke visshet om når kvanteberegning vil modnes, men en klar vurdering av hva det betyr å bygge en institusjon hvis sikkerhetsposisjon fortsatt er grunnlagt på antakelsen om at faktorisering av store primtall er vanskelig. Den antakelsen har en utløpsdato.

Mer som dette

Kina godkjenner verdens første kommersielle hjerneimplantat og etterlater Neuralink

Suncatcher-gambiten: Innsikt i Googles plan for å erobre KI-fremtiden

Farvel til silisium: Kina avslører ‘LightGen’ – lysprosessoren som utfordrer Nvidia og bryter varmemuren

Den Starlink-tilkoblede autonome dronen som gjør nødsamtalsdispatchering til en algoritmisk beslutning

Roland-Garros eSeries og fremveksten av mobil-esport i den digitale idrettskulturen

Dragonkin: The Banished og fremveksten av fellesskapsformet RPG-utvikling