Hvad er RSA-kryptering og hvordan fungerer det?

Definition af RSA-kryptering

RSA er et public-key-kryptografisystem, der bruges til at etablere sikre forbindelser og skabe digitale underskrifter.

RSA-kryptering fik sit navn fra efternavnene på dens skabere, Rivest, Shamir og Adleman, som beskrev algoritmen, mens de arbejdede på Massachusetts Institute of Technology tilbage i 1977.

RSA bruger en offentlig nøgle til at kryptere beskeden og en privat nøgle til at dekryptere den. Matematikken bag RSA-krypteringsalgoritmen omfatter en envejsfunktion — den er nem at beregne, men udfordrende at vende. Det gør RSA til en sikker krypteringsalgoritme, der er praktisk talt umulig at bryde.

Hvordan fungerer RSA-kryptering?

RSA er en type af asymmetrisk kryptografi (public key kryptering), der kræver brug af både offentlige og private nøgler.

• Du skal bruge en offentlig nøgle til at kryptere beskeden — til at omdanne den almindelige klartekst til chiffertekst. De offentlige nøgle kan deles og tilgås offentligt.
• Du skal bruge en privat nøgle til at dekryptere den krypterede besked — til at omdanne chiffertekst til almindelig klartekst igen. Din private nøgle skal altid forblive hemmelig.

Symmetrisk kryptering bruger på den anden side den samme private nøgle til at kryptere og dekryptere beskeden. Det fungerer godt, når der på en sikker måde på forhånd er mulighed for at dele den private nøgle med modtageren af beskeden. Public-key-kryptografi, herunder RSA, er fremragende, når en sådan mulighed ikke er tilgængelig.

Asymmetriske krypteringsalgoritmer involverer fire dele: generering af offentlige og private nøgler, (offentlig) nøgleudveksling (via nøgleudvekslingsalgoritme), kryptering og dekryptering.

Nøglegenerering

Nøglegenerering er proceduren for beregning af RSA-nøgler — et privat og offentligt nøglepar. Processen består af følgende trin:

1. Valg af to primtal (p and q)

For at en kryptering er sikker, skal de valgte primtal være både forskellige og store. Eksempelvis benytter 2048-bit kryptering sig af primtal på 308 cifre. Da det ikke er nemt at finde frem til så store tal selv, så gør man brug af en primalitetstest til at generere dem.

2. Beregning af modulus (n)

Første halvdel af din private og offentlige nøgle udgør modulus (n) – produktet af p og q:

Selvom det er nemt at beregne, skal det være praktisk talt umuligt at estimere, hvilke tal der blev ganget for at få produktet.

Hvis dit p for eksempel er 6.637, og q er 8.971, vil lommeregner-appen på din telefon fortælle dig, at produktet er 59.540.527. Men hvis du ser 59.540.527 foran dig, kan du så se eller bruge den samme lommeregner til at afgøre, hvilke præcise tal der blev ganget sammen for at få produktet?

Sandsynligvis ikke. Og det er idéen bag RSA-kryptering — algoritmen skal være enkel at beregne, men stort set umulig at omgøre.

Tallene fra eksemplet ovenfor ville være nemme at dekomponere for en faktoriseringsberegner. Men som nævnt bruger RSA-kryptering primtal på 308 cifre, som er meget større og sværere at udregne.

3. Generering af den offentlige nøgle (e)

Den offentlige RSA-nøgle består af modulus (n) og den offentlige eksponent (e). Før du kan få e — den anden halvdel af din offentlige nøgle, skal du udregne φ — totienten for n:

Derefter kan du vælge e — et vilkårligt heltal, der er højere end 1, men lavere end og relativt primtal til φ. Normalt bruges 65.537 som e i RSA-kryptering.

4. Generering af den private nøgle (d)

Den private RSA-nøgle består af modulus (n), og den private eksponent (d). d beregnes ud fra p og q og indebærer at finde disse tals største fælles divisor (GCD). Denne procedure kaldes en euklidisk algoritme, og det er lettere at overlade den til online-regnemaskiner.

Nøgledistribution

Hvis nogen ønsker at bruge RSA til at kryptere en besked til dig, så er de nødt til at kende din offentlige nøgle. Du kan dele din offentlige nøgle på en hvilken som helst pålidelig måde — det behøver ikke nødvendigvis at være hemmeligt.

Kryptering

Lad os antage, at personen i den anden ende har din offentlige nøgle (e og n) og gerne vil sende dig en besked (M). Hvad sker der så?

For at kunne omdanne den almindelige klartekst til chiffertekst (C), skal de bruge følgende funktion:

Mod står for modulo operation og henviser til den rest, der er tilbage, når den ene side er divideret med den anden, f.eks. 11 mod 3 = 2 (3 passer ind i 11 tre gange, og der er 2 tilbage).

Hvis den besked, du vil sende, er et tal, erstatter du M’et med dit tal, og funktionen har alle de manglende brikker. Hvis det er en tekstbesked, er du nødt til at konvertere teksten til tal først. Hvis du f.eks. bruger ASCII-alfabetet, vil beskeden "NORDVPN" være "78798268868078" i tal.

Dekryptering

For at kunne dekryptere chifferteksten, som du modtager, skal du have fat i din private nøgle (d og n) fra din hemmelige lokation. Herefter skal du tage den modtagne chiffertekst (C) og benytte følgende funktion:

Dette vil omdanne chifferteksten til den almindelige beskedtekst igen.

Hvor benyttes RSA-kryptering?

Som public key-kryptografi er RSA praktisk, når du sender information sikkert til personer eller servere, du ikke har haft kontakt med før, og som derfor ikke har de private nøgler til symmetrisk kryptering. Du finder det derfor ofte i browsere, e-mailudbydere, chatprogrammer, cloud-tjenester, VPN’er, P2P-systemer og andre kommunikationskanaler.

Men når det gælder digital kryptering, er RSA efterhånden en gammel kending, den bruges derfor normalt sammen med andre krypteringssystemer. Et grundlæggende eksempel ville være at bruge RSA til at kryptere den private nøgle til symmetrisk kryptering — for at dele nøglen sikkert og samtidig beskytte de faktiske følsomme data med symmetrisk kryptering.

De vigtigste anvendelser af RSA omfatter etablering af en sikker forbindelse og oprettelse af digitale underskrifter. RSA bruges ikke til at kryptere beskeder eller filer, da andre krypteringssystemer er mere sikre, hurtigere og kræver færre ressourcer.

Etablering af sikre forbindelser

Webbrowsere bruger RSA til at etablere sikre internetforbindelser, som hjælper med at forhindre sniffing eller man-in-the-middle-angreb. De fleste internetforbindelser bruger SSL til at sikre trafikken, og RSA er en del af SSL/TLS handshakes. Du kan finde det i kryptografiske biblioteker, såsom OpenSSL.

OpenVPN bruger RSA til nøgleudveksling og sikker kommunikation mellem VPN-klienten og VPN-serveren, når VPN-forbindelsen er etableret. Men VPN’er beskytter normalt de faktiske data med forskellige krypteringschifre. For eksempel bruger NordVPN’s næstegenerationskryptering AES-256-GCM.

RSA var også den første algoritme, der blev brugt i PGP-kryptering til at kryptere sessionsnøgler.

Oprettelse af digitale underskrifter

Du kan bruge den private nøgle til at underskrive din besked eller dit dokument, mens den anden part kan bruge den offentlige nøgle til at verificere ægtheden af beskeden eller dokumentet.

Det er en alsidig funktion, så når det kommer til digitale underskrifter, kan RSA bruges overalt, lige fra e-mail til bankanliggender til online shopping.

For eksempel bliver e-mails ofte signeret digitalt ved hjælp af PGP-kryptering, som bruger RSA-algoritmen til oprettelse af digitale signaturer.

Fordele og ulemper ved RSA-kryptering

Fordele:

• RSA-algoritmen er nem at implementere og forstå. Algoritmen er ret grundlæggende, og funktionerne er ikke for komplicerede sammenlignet med andre algoritmer, såsom RSAs hovedalternativ Elliptic Curve Cryptography, som mange tjenester skifter til, da det er mere effektivt med hensyn til ressourcestyring.

• RSA-kryptering er ret alsidig, så den kan (og bliver) brugt i vid udstrækning.

• Når RSA-kryptering er implementeret korrekt, er den umulig at bryde, i hvert fald med den nuværende computerkapacitet.

Ulemper:

• Når RSA implementeres forkert, er det sårbart over for mange forskellige angreb.

• RSA-nøglens længde er afgørende for krypteringssikkerheden, men længere nøgler kræver meget computerkraft at generere, så de er ikke altid bæredygtige.

• Dekrypteringen tager også lang tid og kræver mange ressourcer.

• Det stigende antal tilgængelige offentlige RSA-nøgler gør det lettere for cyberkriminelle at udtænke måder at bryde eller overvinde krypteringen på.

Sårbarheder i RSA-algoritmer

RSA-sikkerhed afhænger i høj grad af implementeringen. Hver del af processen kan involvere sårbarheder, der påvirker resultatet af krypteringen.

Svag RNG (Random Number Generator)

RSA-algoritmen starter med at vælge primtal, og dette første trin kan være den sårbare del. Hvis primtalene ikke er tilfældige nok, er det lettere at faktorisere modulus og knække krypteringen.

Svage tilfældige talgeneratorer (RNG’ere) er normalt skyld i dette, så du kan undgå sårbarheden ved at bruge pseudo-tilfældige talgeneratorer i stedet.

Fejlbehæftet nøglegenerering

Primtal kan være tilpas tilfældige, men vil til tider være for små eller for tæt på hinanden. Og det er endnu et problem.

Da RSA-algoritmen bruger en offentlig nøgle til kryptering, er nøglestørrelsen afgørende for at forhindre faktorisering. Det er lettere at afdække primtal (p og q), når tallene er mindre. Og hvis tallene er for tæt på hinanden, ender den private nøgle (d) med at være relativt lille.

Det er derfor, at sikkerhedseksperter anbefaler en minimumsnøgle på 2048-bit, mens nyere RSA-nøgler normalt er på 4096-bit.

Angreb på RSA-kryptering

Mangel på viden om de nævnte sårbarheder ved RSA kan føre til lette angreb på RSA.

Angreb med faktorisering

Hvis du ikke adresserer sårbarhederne, kan cyberkriminelle udnytte dem til at begå faktoriseringsangreb.

RSA-kryptering er kun sikker, hvis ingen kan opdage primtallene p og q ud fra deres produkt n. Men hvis primtallene ligger for tæt på hinanden eller ikke er tilfældige og store nok, kan cyberkriminelle faktorisere dem, og så skal der ikke meget til for at afsløre den private nøgle.

Side-channel angreb

Ved side-channel angreb analyserer hackerne de ekstra oplysninger, der indsamles om dekrypteringsprocessen, i stedet for at knække krypteringsnøglen. For eksempel undersøger de, hvor meget strøm algoritmen bruger, eller endda de lyde, computerne laver under processen.

Et timing-angreb er også et eksempel på side-channel-angreb. I RSA-timingangreb analyserer de cyberkriminelle, hvor lang tid dekrypteringen tager for forskellige kendte chiffertekster for at udlede den private nøgle (d).

Klartekst-angreb

Hvis den pågældende hacker formår at matche en hvilken som helst del af en klartekstbesked med chifferteksten, så vil hackeren kunne udføre klartekstangreb:

• Angreb mod korte beskeder. En cyberkriminel har adgang til dele af klartekstbeskeden og krypterer den for at få chiffertekst. Den cyberkriminelle kan derefter bruge den til at udlede andre dele af klartekstbeskeden. Du kan undgå dette klartekstangreb ved at bruge paddling — at inkludere ekstra data i klartekstbeskeden, før du krypterer den.
• Cycling angreb. En hacker tester permutationsoperationer, der kunne have været udført for at skabe chifferteksten. Hvis det virker, kan den cyberkriminelle derefter vende processen om for at få klartekstmeddelelsen fra chifferteksten.
• Angreb med skjult besked. I teorien kan dele af en krypteret chiffertekst være identisk med den oprindelige klartekstbesked, omend det sjældent sker. Skulle det dog finde sted, kan cyberkriminelle udlede andre dele af den krypterede besked og udføre angreb med skjult besked.

Chosen cipher-angreb

Som tidligere nævnt bruger man den euklidiske algoritme til at generere den private nøgle. Da algoritmen ikke er hemmelig, kan den cyberkriminelle bruge den udvidede euklidiske algoritme til at få den almindelige tekstbesked fra chifferteksten. Det er sådan, man får chosen cipher-angreb.

Er RSA-kryptering sikker?

Når snakken falder på sårbarheder ved og angreb på RSA, så er det nærliggende at spørge, om RSA-kryptering overhovedet er sikkert. Svaret er ikke så lige til, for det kommer reelt an på en række forskellige ting.

Det afhænger mere præcist af implementeringen.

Hvis du implementerer algoritmen uden at overveje sårbarhederne, så vil RSA-kryptering ikke være stærk nok til at modstå angrebene. Desværre ignorerer mange RSA-brugere ofte sårbarhederne, som forskning viser.

I 2012 indsamlede forskere 5,5 millioner offentlige nøgler og opdagede, at RSA 1024-bit krypteringsnøgler i bedste fald gav 99,8% sikkerhed. Med andre ord ville det være let at knække næsten 13.000 nøgler.

For nylig opdagede forskere fra Keyfactor, at 1 ud af 172 RSA-certifikater er sårbare over for faktoriseringsangreb.

Men hvis du forebygger sårbarheder i RSA-algoritmen, bruger tilstrækkelig nøglelængde og tager ekstra forholdsregler for at øge sikkerheden (f.eks. paddling), er RSA-kryptering sikker og ubrydelig for de fleste moderne computere.

I hvert fald indtil videre.

Fremtiden indenfor RSA-kryptering

RSA-kryptering er ikke den bedste krypteringsalgoritme, hvad angår sikkerhed eller effektivitet, så dens fremtid er ret tvivlsom i den henseende.

Traditionelle computere ville bruge 300 billioner år på at bryde RSA-kryptering, men kvantecomputere kunne gøre det på 10 sekunder. Da sådanne computere ikke findes endnu, ledes man til at tro, at RSA-kryptering er godt for nu. Men det er ikke det eneste, der peger på en dyster fremtid for RSA-algoritmen.

Ifølge anbefalingerne fra National Institute of Standards and Technology er RSA-kryptering med 2048-bit krypteringsnøgler sikker at bruge indtil slutningen af 2030. Selvom man altid kan vælge en nøglelængde på 4096 bit, som vil være relevant lidt længere, er længere nøgler ikke bæredygtige.

Når alt kommer til alt, er det ikke kun sikkerhed, der gør en krypteringsalgoritme til et godt valg. Det er også effektiviteten af krypteringen. Og det er her, RSA kommer til kort.

RSA-algoritmen kræver mange ressourcer at køre. Den er langsom, især hvis du bruger længere nøgler, men hvis du bruger kortere nøgler, bliver kryptosystemet usikkert. Så selvom 4096-bit nøgler er okay indtil videre, vil alt derudover koste for meget computerkraft.

Brugen af RSA har været gradvist faldende i årevis nu. Det er for besværligt, når man har bedre alternativer — systemer, der er mere sikre og effektive, såsom Elliptic Curve Cryptography. Så det er kun et spørgsmål om tid, før RSA bliver forældet.