Forskere har funnet ut at noen av dagens krypteringsnøkler kan la seg enkelt og raskt knekke – med en metode som ble utviklet for 379 år siden.
RSA-nøklene det dreier seg om består av to store primtall som multipliseres. Resultatet danner en krypteringsnøkkel. Den er offentlig og kan brukes til å kryptere informasjon med, men informasjonen kan kun dekrypteres ved hjelp av de to primtallene som sammen dannet krypteringsnøkkelen, og disse er ikke offentlig kjent.
De kan imidlertid i noen tilfeller lett bli det.
Ingen kjent måte å knekke den på, hvis brukt riktig
Krypteringssystemet kalles RSA, etter etternavnene til de som oppfant det, og baserer seg på at det er svært krevende å finne ut hvilke to store primtall som multiplisert har dannet et annet tall. Metoden har vært kjent siden 70-tallet, men det finnes i prinsippet ikke en enkel metode å knekke krypteringen på hvis man har brukt den riktig.
Det er det imidlertid ikke alle som gjør. For at metoden skal fungere må primtallene som multipliseres være store nok – typisk mellom 2048 og 4096 bits hver – og de må ikke være for like.
Og akkurat det siste er det enkelte som har syndet mot, noe som gjør at Pierre de Fermats metode fra 1643 kan brukes til å knekke koden.
Det er uvisst hvordan man har kommet frem til den svake utvelgelsen av primtall, men en mulighet forskerne trekker frem, er at utviklerne var late og plukket et tilfeldig tall, og så valgte ut de to påfølgende primtallene som ble funnet etter dem. Altså primtall som selv om de kan være store, er «naboer».
Slik funker det
Fermat baserte sin metode på at et hvilket som helst oddetall kan omskrives som forskjellen mellom to kvadrattall. Metoden er enkel, men ikke spesielt effektiv - med mindre forskjellen mellom primtallene er liten. Hvis begge primtallene er for nær hverandre i verdi, vil det være en enkel sak å knekke koden, og det er gjort på sekunder med en datamaskin.
Siden krypteringsnøkkelen består av to primtall som er multiplisert, kan man benytte kvadratroten av det multipliserte tallet til å finne et tall som er et godt utgangspunkt for å finne de to primtallene. Hvis primtallene i utgangspunktet ikke er langt fra hverandre, vil de heller ikke være langt fra denne verdien.
Man kan da endre verdien man gjetter på med 1 for hver gang, og beregne seg frem til riktig verdi med relativt få trinn.
Dette gjør det svært enkelt og raskt å prøve seg frem med Fermats metode til man har begge primtallene.
I teorien kunne man gjort det samme på minutter med fjærpenn og pergament.
Ikke mye brukt
Heldigvis er kodene med denne svakheten lite brukt. De kommer ifølge Ars Technica fra en versjon av SafeZone Crypto Libraries, som har sitt opphav i et firma som Rambus kjøpte opp i 2019. Programvareversjonen med svakheten er fra før overtagelsen, og brukes heldigvis i liten grad i dag.
Noen steder er imidlertid krypteringsnøkler fra denne programvaren funnet «i det fri» den dag i dag. I hovedsak dreier det seg om skrivere fra Canon og Fujifilm (markedsført som Fuji Xerox), og et lite antall PGP-koder for kryptering av epost.
Pierre de Fermat
Pierre de Fermat var en fransk matematiker som ble født i 1601 og var en av de absolutt dominerende matematikere på første halvdel av 1600-tallet. Isaac Newton utviklet sine matematiske metoder basert på Fermats grunnleggende arbeid, og var hele tiden tydelig på at han fant sin inspirasjon der.
Fermat er kanskje mest kjent for det som siden har blitt kalt Fermats siste teorem, selv om den beskrivelsen er forholdsvis upresis.
Fermats siste teorem
I 1637 eller deromkring skrev Fermat i margen på en matematisk bok at «Cuius rei demonstrationem mirabilem sane detexi hanc marginis exiguitas non caperet». Oversatt til norsk blir det noe slikt som «Jeg har oppdaget en virkelig bemerkelsesverdig demonstrasjon av dette, men det er ikke plass til å skrive det ned i denne margen».
Demonstrasjonen han mente var avledet fra Pythagoras klassiske a2 + b2 = c2. Skrevet på en annen måte, an + bn = cn. Det var lenge kjent at ligningen hadde uendelig antall løsninger for n=1 og n=2. Euclid hadde et bevis for at det ikke fantes løsninger for n=3 og Fermat selv hadde et bevis for det samme for n=4, men et generelt bevis for alle heltallsverdier av n var det ingen som hadde. Og det var nettopp dette beviset Fermat påstod at han hadde funnet, men ikke hadde plass til å skrive ned i margen.
Problemet forble uløst i 358 år.
I 1995 fant den britiske matematiskeren Andrew Wiles endelig et bevis, men det var på over 200 sider og han brukte topp moderne og nylig utviklede matematiske metoder for å få det til. Som wikipedia skriver det er beviset «... utenfor rekkevidde for de fleste nålevende matematikere».
Hadde Fermat faktisk en løsning? Bløffet han? Tok han feil? Ingen vet.
