Nøkkellengde: Det er størrelsen som gjelder

Kryptografiske nøkler er tall som har helt spesielle egenskaper avhengig av hvilken kryptografisk algoritme eller metode som benyttes. Den mest vanlige algoritmen som benyttes for PKI kalles RSA og er oppkalt etter de 3 amerikanske forskerne som først publiserte algoritmen (Ron Rivest, Adi Shamir og Leonard Adleman).

RSA er en såkalt asymmetrisk algoritme og for slike algoritmer benyttes et nøkkelpar bestående av en offentlig nøkkel og en privat nøkkel .

Den offentlige nøkkelen er, som navnet antyder, offentlig tilgjengelig og da gjerne i form av et digitalt sertifikat som knytter nøkkelen til innehaveren av den korresponderende private nøkkelen. Den private nøkkelen derimot skal bare være tilgjengelig for innehaveren. Nøkkelen er gjerne beskyttet i et smartkort og bruk av nøkkelen må autoriseres av innehaver ved bruk av en PIN-kode.

For å generere et RSA-nøkkelpar benyttes følgende fremgangsmåte:

1. Velg to store ulike primtall, p og q
2. Beregn RSA modulus, N = p∙q 
3. Velg en offentlig eksponent e med spesielle egenskaper i forhold til p og q. e velges gjerne lik 65537
4. Den offentlige nøkkelen består da av N og e
5. Beregn en privat eksponent d med spesielle egenskaper i forhold til e, p og q
6. Den private nøkkelen består da av N og d (eller egentlig p,q og d)

RSA-algoritmen er basert på såkalt modulus-aritmetikk . Klokken og tiden på døgnet er et godt eksempel på praktisk bruk av modulus-aritmetikk. Da benytter vi en modulus på 24 timer og uansett hvor langt frem i tid eller tilbake i tid vi regner, så ender vi alltid opp med en tid på døgnet mellom 00:00 og 23:59.

De fleste beregninger basert på kryptografi bygger på 2 fundamentale operasjoner; kryptering og dekryptering . Figuren nedenfor viser hvordan en melding (m) i klartekst kan omdannes til en uleselig melding (c) ved å kryptere meldingen med den offentlige nøkkelen. Vi kan bringe den uleselige meldingen tilbake til sin opprinnelige form (m) ved å dekryptere med den korresponderende private nøkkelen.

Legg merke til at kryptering og dekryptering er operasjoner modulus N og at resultat dermed alltid vil være et tall mellom 0 og N.

Nå nærmer vi oss også det som er tema for tittelen på artikkelen, nemlig nøkkelens lengde. Lengden på en RSA-nøkkel er lik lengden på RSA-modulusen, dvs N. Nøkkellengden måles gjerne i antall bits og en vanlig brukt nøkkellengde frem til nå er 1024 bits. Dette er et stort heltall som består av mer enn 300 siffer!

For å knekke en RSA-nøkkel så må man løse det underliggende matematiske problemet som RSA bygger på; nemlig faktorisering av store heltall. N er som beskrevet over en del av den offentlige nøkkelen og dermed kjent. Dersom man klarer å faktorisere N i dens enkeltkomponenter p og q, så har man knekt nøkkelen.

Kan dette være så vanskelig? Ja, dersom N for eksempel består av 200 siffer (663 bits), så finnes det ca 4∙10⁹⁷ primtall som kan være komponenter i N. Dette er et veldig stort tall – mer enn antall partikler i universet! Dersom man kan sjekke 10⁹ (altså 1 milliard) primtall i sekundet, så tar det 10⁸¹ år å teste alle disse primtallene.

En slik prøve-og-feile metode har såkalt eksponentiell kompleksitet, dvs kompleksiteten øker eksponentielt med nøkkellengden (eller mer presist; med antall primtall som har lengde mindre enn kvadratroten av nøkkellengden).

Det finnes imidlertid smartere måter å faktorisere store heltall på enn å bruke en slik ”test alle primtall” strategi, men dette gir en god indikasjon på kompleksiteten i problemet.  

Faktorisering av store heltall er et fagområde innenfor matematikken hvor det skjer en kontinuerlig utvikling. Selv om problemet fortsatt er veldig komplisert for store heltall, så skjer det stadig vekk fremskritt innenfor dette området. I tillegg til en slik metodeutvikling har man også tilgang til stadig raskere datamaskiner og dette gjør at nøkkellengden må utvides for å ivareta samme sikkerhet over tid.   

Den mest effektive, kjente metode for å faktorisere store heltall kalles Number Field Sieve og har såkalt semi-eksponentiell kompleksitet. Kompleksiteten øker tilnærmet eksponentielt med kubikkroten av nøkkellengden og en slik metode er mye mer effektiv enn metoder med eksponentiell kompleksitet.

Det kan også nevnes at det finnes en svært effektiv metode, Shor’s algoritme, der kompleksiteten øker polynomisk med nøkkellengden. Dersom en slik metode realiseres, er faktorisering av store heltall et trivielt problem å løse og RSA vil være knekt for alle nøkkellengder. Utfordringen her er at denne metoden må implementeres på en kvantedatamaskin og en slik datamaskin er sannsynligvis ikke tilgjengelig med det første.

I januar 2010 publiserte en gruppe forskere fra ulike internasjonale akademiske miljøer en artikkel der de beskriver hvordan de har faktorisert en RSA-modulus på 768-bits ved bruk av Number Field Sieve metoden. Dette er et arbeid som har pågått over flere år og mange hundre datamaskiner i flere forskningsmiljøer har vært brukt i beregningene.

Det kreves mer enn 10³⁰ operasjoner å utføre disse beregningene. På en single core 2.2 GHZ AMD Opteron CPU vil det ta mer enn 2000 år å utføre disse beregningene.

Modulusen som ble faktorisert er et desimaltall med 232 siffer:

N=23018668453011775513049495838496272077285356959533479219732245 21517264005072636575187452021997864693899564749427740638459251925 57326303453731548268507917026122142913461670429214311602221240479 274737794080665351419597459856902143413

Og resultatet er 2 primtall, p og q, hvert på 116 siffer:

p=334780716989568987860441698482126908177047949837137685689124313 88982883793878002287614711652531743087737814467999489

q=367460436667995904282446337996279526322791581643430876426760322 83815739666511279233373417143396810270092798736308917

Publiseringen er imidlertid en milepæl i det kryptografiske miljøet og man anser med dette at RSA-nøkler med 768-bits lengde ikke lenger gir tilstrekkelig sikkerhet. Man regner også med at man ved bruk av tilsvarende fremgangsmåte kan knekke 1024-bits RSA-nøkler i løpet av neste 5-10 års periode.

Gjeldende anbefalinger for nøkkellengder går ut på at man må fase ut 1024 bits RSA-nøkler i løpet av de 3-4 neste årene. Nøkkellengder som erstatter disse er typisk 1536 eller 2048 bits.

Buypass planlegger også å legge om til lengre nøkler i sine produkter i løpet av 2010. Vi krever allerede 2048 bits for SSL Evident og aksepterer lengre nøkler for våre SSL-produkter der kunden selv genererer nøklene.

Når det gjelder kryptografiske nøkler og deres evne til å gi tilstrekkelig sikkerhet, så er det definitivt størrelsen som gjelder.