Hur en kvantdator kunde bryta 2048-bitars RSA-kryptering på 8 timmar

En närbild av D-Wave Vesuvius-chippet Steve Jurvetson | Flickr

Många människor oroar sig för att kvantdatorer ska kunna knäcka vissa koder som används för att skicka säkra meddelanden. Koderna i fråga krypterar data med matematiska funktioner för falldörr som fungerar enkelt åt ena hållet men inte åt andra hållet. Det gör det enkelt att kryptera data men att avkoda det enormt svårt utan hjälp av en speciell nyckel.

Dessa krypteringssystem har aldrig varit okrossbara. Istället är deras säkerhet baserad på den enorma tid det skulle ta för en klassisk dator att göra jobbet. Moderna krypteringsmetoder är speciellt utformade så att avkodning av dem skulle ta så lång tid att de är praktiskt taget okrossbara.

Men kvantdatorer förändrar detta tänkande. Dessa maskiner är mycket kraftfullare än klassiska datorer och bör kunna bryta dessa koder med lätthet.

Det väcker en viktig fråga - när kommer kvantdatorer att vara tillräckligt kraftfulla för att göra detta? Efter det datumet blir all information som skyddas av denna form av kryptering osäker.

Så datavetare har försökt beräkna vilka resurser en sådan kvantdator kan behöva och sedan räkna ut hur lång tid det kommer att ta innan en sådan maskin kan byggas. Och svaret har alltid varit årtionden.

Idag behöver det tänkandet revideras tack vare Craig Gidneys arbete på Google i Santa Barbara och Martin Ekerå vid Kungliga Tekniska Högskolan i Stockholm. Dessa killar har hittat ett mer effektivt sätt för kvantdatorer att utföra de kodbrytande beräkningarna, vilket minskar de resurser de kräver i storleksordningar.

Följaktligen är dessa maskiner betydligt närmare verkligheten än någon misstänkt. Resultatet blir obekväm läsning för regeringar, militär- och säkerhetsorganisationer, banker och alla andra som behöver säkra data i 25 år eller längre.

Först lite bakgrund. Redan 1994 upptäckte den amerikanske matematikern Peter Shor en kvantalgoritm som överträffade sin klassiska motsvarighet. Shors algoritm påverkar stora siffror och är det avgörande elementet i processen för att knäcka falldörrsbaserade koder.

Falldörrsfunktioner är baserade på multiplikationsprocessen, som är lätt att utföra i en riktning men mycket svårare att göra i omvänd riktning. Till exempel är det trivialt att multiplicera två tal tillsammans: 593 gånger 829 är 491 597. Men det är svårt att börja med talet 491 597 och räkna ut vilka två primtal som måste multipliceras för att producera det.

Och det blir allt svårare när siffrorna blir större. Faktum är att datavetare anser att det är praktiskt taget omöjligt för en klassisk dator att faktorisera tal som är längre än 2048 bitar, vilket är grunden för den vanligaste formen av RSA-kryptering.

Shor visade att en tillräckligt kraftfull kvantdator kunde göra detta med lätthet, ett resultat som skickade chockvågor genom säkerhetsindustrin.

Och sedan dess har kvantdatorer ökat i kraft. 2012 använde fysiker en kvantdator med fyra qubit till faktor 143. Sedan 2014 använde de en liknande enhet till faktor 56 153.

Det är lätt att föreställa sig att kvantdatorer med denna framstegshastighet snart skulle kunna överträffa de bästa klassiska.

Inte så. Det visar sig att quantum factoring är mycket svårare i praktiken än man annars kan förvänta sig. Anledningen är att brus blir ett betydande problem för stora kvantdatorer. Och det bästa sättet för närvarande att hantera brus är att använda felkorrigerande koder som själva kräver betydande extra qubits.

Att ta hänsyn till detta ökar dramatiskt resurserna som krävs för att faktorisera 2048-bitars nummer. År 2015 uppskattade forskare att en kvantdator skulle behöva en miljard qubits för att göra jobbet på ett tillförlitligt sätt. Det är betydligt mer än de 70 qubitarna i dagens toppmoderna kvantdatorer.

På den grunden skulle säkerhetsexperter mycket väl ha kunnat motivera tanken att det skulle dröja årtionden innan meddelanden med 2048-bitars RSA-kryptering kunde brytas av en kvantdator.

Nu har Gidney och Ekerå visat hur en kvantdator kunde göra beräkningen med bara 20 miljoner qubits. De visar faktiskt att en sådan enhet skulle ta bara åtta timmar att slutföra beräkningen. [Som ett resultat] har den värsta uppskattningen av hur många qubits som kommer att behövas för att faktorisera 2048 bitars RSA-heltal sjunkit nästan två storleksordningar, säger de.

Deras metod fokuserar på ett mer effektivt sätt att utföra en matematisk process som kallas modulär exponentiering. Detta är processen att hitta resten när ett tal höjs till en viss styrka och sedan divideras med ett annat tal.

Denna process är den beräkningsmässigt dyraste operationen i Shors algoritm. Men Gidney och Ekerå har hittat olika sätt att optimera den, vilket avsevärt minskat de resurser som behövs för att köra algoritmen.

Det är intressant arbete som borde ha viktiga konsekvenser för alla som lagrar information för framtiden. En kvantdator på 20 miljoner qubit verkar verkligen vara en avlägsen dröm idag. Men frågan som dessa experter borde ställa sig är om en sådan enhet skulle kunna vara möjlig inom de 25 år de vill säkra informationen. Om de tror att det är så behöver de en ny form av kryptering.

Säkerhetsexperter har faktiskt utvecklat postkvantkoder som inte ens en kvantdator kommer att kunna knäcka. Så det är redan idag möjligt att skydda data mot framtida attacker från kvantdatorer. Men dessa koder används ännu inte som standard.

För vanliga människor är risken liten. De flesta använder 2048-bitars kryptering, eller något liknande, för uppgifter som att skicka kreditkortsuppgifter över internet. Om dessa transaktioner registreras idag och bryts om 25 år kommer lite att gå förlorat.

Men för regeringar står det mer på spel. De meddelanden de skickar idag – mellan ambassader eller militären, till exempel – kan mycket väl vara betydelsefulla om 20 år och därför värda att hålla hemliga. Om sådana meddelanden fortfarande skickas via 2048-bitars RSA-kryptering, eller något liknande, bör dessa organisationer börja oroa sig – snabbt.

Ref: arxiv.org/abs/1905.09749 : Hur man faktorisera 2048-bitars RSA-heltal på 8 timmar med 20 miljoner bullriga Qubits

Dölj