Annons

Våra hemliga koder blir en öppen bok

Kvantdatorn sägs bland annat bli speciellt användbar för att faktorisera tal och knäcka så kallad RSA-kryptering. Men måste man ta till kvantfysik för att faktorisera tal? Skulle det vara möjligt att bygga en ”biodator”, kanske baserad på syntetisk dna-teknik, som på liknande sätt kan testa ett lika stort antal primtalsprodukter mot en given RSA-nyckel?

/Torkel Danielsson, Lidingö

Publicerad:

2015-05-13

Principen för RSA-kryptering är att två mycket stora primtal multipliceras till ett ännu större tal, som används för att kryptera. De två ursprungliga talen används för att skapa hemliga nycklar för dekrypteringen. Det innebär att den som kan faktorisera ett mycket stort tal – det vill säga bryta ner det i primtalsfaktorer – också kan knäcka RSA-kryptering.

Om jag förstår dig rätt så undrar du om man skulle kunna konstruera en organism – en biodator – som gör detta effektivt. Svaret är nej. En biodator skiljer sig i detta avseende inte från en vanlig dator. Båda är vad man kallar klassiska datorer. En klassisk dator kan tackla problemet genom att utföra många beräkningar parallellt på olika hårdvaror. En kvantdator däremot, kan utföra många beräkningar parallellt i samma hårdvara – något som inom kvantvärlden kallas superposition. Medan biodatorn, liksom andra datorer som inte är kvantdatorer, skulle behöva astronomiskt långa tidsrymder för att knäcka en lång RSA-nyckel skulle kvantdatorn kunna klara samma uppgift på någon sekund.

Den bästa kända algoritmen (metoden) för faktorisering av RSA-nycklar kallas GNFS (general number field sieve). För att faktorisera en 1 500 bitar lång RSA-nyckel med GNFS på en klassisk dator med snabb processor (cirka 10 GHz) så skulle beräkningen ta ungefär lika lång tid som vårt universum har existerat. Om det fanns en kvantdator med samma processorhastighet skulle den lösa problemet på mindre än en sekund!

I dag anses 1 024-bitars RSA-nycklar vara något osäkra, medan längre nycklar, till exempel 4 096-bitars, är utom räckhåll för GNFS. Men en kvantdator skulle bara kräva drygt 60 gånger fler beräkningar för att knäcka en nyckel på 4 096 bitar jämfört med en på 1 024 bitar, alltså några sekunder med samma processorhastighet som ovan.

/Adam Nilsson, doktorand i atomfysik, kvantinformationsgruppen, Lunds universitet

Du har just läst en artikel från tidskriften Forskning & Framsteg. Prenumerera här.

Kommentera:

Dela artikeln:

TIDNINGEN FÖR DIG SOM ÄR NYFIKEN PÅ ALLVAR
10 nummer 779 kr
2 nummer 99 kr
Du vet väl att du kan läsa Forskning & Framsteg i din läsplatta? Ladda ned appen från App Store eller Google Play. (Läsplatteutgåvan ingår i alla prenumerationer.)

Lägg till kommentar