Han knäckte RSA-kryptering – med 350-årig algoritm 

2022-03-15 15:00  
Foto: Science Photo Library

Krypteringsmetoden RSA är en grundsten för säker dataöverföring. Nu har kryptografiska nycklar skapade med äldre mjukvara forcerats med hjälp av Fermats lilla sats. 

RSA, döpt efter upphovspersonerna Rivest–Shamir–Adleman, är en 45-årig krypteringsalgoritm som använd flitigt bland annat inom finansvärlden och av mjukvarujättar som Microsoft, Apple och IBM.

Det är den första allmänt beskrivna algoritmen som använder så kallad asymmetrisk kryptering – vilket innebär att man använder en publik nyckel för att kryptera meddelanden, och en annan privat nyckel för att dekryptera det. 

RSA drar nytta av faktumet att datorer har ett tvådelat förhållande till så kallad primtalsfaktorisering.

Omständigheten beskrivs så här av Ny Tekniks Peter Ottsjö i ett tidigare reportage om kvantdatorer och dagens krypteringsmetoder: 

"Om datorn å ena sidan känner till vilka primtalsfaktorer som ska ge ett givet tal har den inga bekymmer med att multiplicera faktorerna för att få fram talet. Om den å andra sidan bara känner till det givna talet är den mer eller mindre oförmögen att klura ut vilka primtalsfaktorerna är, hur mycket processorkraft man än använder. Det är detta som ligger till grund för det vi kallar den publika och privata nyckeln."

Känd svaghet hos RSA-kryptering

Men tänk om det inte behövs kraftfulla kvantdatorer för att knäcka RSA-kryptering? 

Det är känt sedan länge att RSA-kryptering blir svagare om primtalen som används är för lika varandra. Nu har den tyska frilansjournalisten och säkerhetsresearchern Hanno Böck beskrivit hur man kan använda Fermats lilla sats för att knäcka äldre RSA-nycklar som härrör från kodbiblioteket SafeZone Crypto Libraries, skapat av företaget Inside Secure som köptes upp av Rambus år 2019.

Fermats lilla sats bygger på faktumet att alla udda tal kan beskrivas som skillnaden mellan två kvadrater. Om primtalsfaktorerna ligger nära roten av talet, kan dessa räknas ut snabbt, skriver Ars Technica.

Hittade fyra sårbara PGP-nycklar

Hanno Böck har hittills identifierat "en handfull" RSA-krypteringsnycklar som är sårbara för den här typen av faktoriseringsattack. Vissa av nycklarna kommer från skrivare som ursprungligen tillverkades under varumärket Fuji Xerox, som numera tillhör Canon. Nycklarna har skapats 2020 eller senare, och har CVE-nummer 2022-26351 

Böck hävdar också att han har identifierat fyra sårbara PGP-nycklar på SKS PGP-nyckelservrar. Dock verkar dessa nycklar inte vara aktiva, och verkar ha skapats enbart för testning. 

Potentiellt mer illavarslande är att Hanno Böck misstänker att inte alla sårbara nycklar han har identifierat är kopplade till kodbiblioteket SafeZone library. Det skulle kunna innebära att även annan mjukvara genererar RSA-nycklar som kan knäckas med hjälp av Fermats lilla sats. 

Kalle Wiklund

Mer om: Kryptering

Kommentarer

Välkommen att säga din mening på Ny Teknik.

Principen för våra regler är enkel: visa respekt för de personer vi skriver om och andra läsare som kommenterar artiklarna. Alla kommentarer modereras efter publiceringen av Ny Teknik eller av oss anlitad personal.

  Kommentarer

Debatt