RSA forklaret
Hver gang en browser viser en hængelås, en besked signeres, eller et program kontrollerer en opdatering, er offentlig nøgle-kryptografi i gang, og RSA er dens bedst kendte form. Idéen er, at nøglen, der låser en besked, kan offentliggøres, mens nøglen, der åbner den, forbliver privat. Bemærkelsesværdigt nok hviler hele systemet på regning, man lærer i skolen: primtal, multiplikation og rester.
Problemet, som RSA løser
Ældre krypteringer, fra Cæsars forskydning til moderne AES, bruger den samme nøgle til at låse og låse op, så de to parter først skal dele en hemmelig nøgle i fortrolighed. Offentlig nøgle-kryptografi fjerner det trin. Hver person har to nøgler: en offentlig nøgle, som alle må bruge til at kryptere en besked til vedkommende, og en privat nøgle, som kun vedkommende selv har, og som alene kan dekryptere den. Whitfield Diffie og Martin Hellman beskrev idéen i 1976, og et år senere fandt Ron Rivest, Adi Shamir og Leonard Adleman ved MIT en måde at gøre det på, som blev kaldt RSA efter deres forbogstaver.
At lave nøglerne
Vælg to store primtal, p og q, og gang dem sammen: n = p × q. Beregn φ(n) = (p − 1)(q − 1), Eulers phi-funktion, der tæller de tal under n, som ikke har nogen fælles faktor med det. Vælg en offentlig eksponent e, der ikke har nogen fælles faktor med φ(n); 65537 er det sædvanlige valg. Find derefter den private eksponent d, så e × d giver resten 1 ved division med φ(n). Den udvidede euklidiske algoritme gør det hurtigt. Den offentlige nøgle er parret (e, n); den private nøgle er d. Med p = 61 og q = 53 giver det n = 3233, φ(n) = 3120, e = 17 og d = 2753.
Kryptering og dekryptering
En besked omdannes først til et tal m, der er mindre end n. For at kryptere den beregner man c = mᵉ mod n, resten af mᵉ ved division med n. For at dekryptere beregner man cᵈ mod n. Eulers sætning garanterer, at det giver m tilbage, fordi e × d er 1 mere end et multiplum af φ(n). Med nøglerne ovenfor bliver bogstavet A, kode 65, til 65¹⁷ mod 3233 = 2790, og 2790²⁷⁵³ mod 3233 = 65 igen. Så store potenser skrives aldrig ud: gentagen kvadrering beregner dem med én kvadrering pr. bit i eksponenten og tager resten ved hvert trin.
Digitale signaturer
RSA virker også omvendt. Opløfter man en besked til den private eksponent, s = mᵈ mod n, får man en signatur, som kun nøglens ejer kan lave. Alle kan kontrollere den med den offentlige nøgle: hvis sᵉ mod n giver m tilbage, kom beskeden fra indehaveren af d og blev ikke ændret undervejs. I praksis er det en kort hashværdi af beskeden, der signeres, snarere end selve beskeden. Signaturer som denne beskytter softwareopdateringer, sikre websteder og elektroniske dokumenter.
Hvorfor den er sikker
Alle kan se n og e. For at finde d har en angriber brug for φ(n), og for at finde φ(n) skal angriberen kende p og q, så at bryde RSA koger ned til at faktorisere n. At gange to primtal sammen tager en computer en brøkdel af et mikrosekund; at splitte produktet op i dem igen menes at være ekstremt svært. Det største RSA-udfordringstal, der hidtil er faktoriseret, RSA-250 i 2020, har 829 bit og krævede omkring 2700 års computertid. Nøgler, der bruges i dag, har mindst 2048 bit, omkring 617 cifre.
En hemmelighed opdaget to gange
I 1973, fire år før RSA, fandt den britiske matematiker Clifford Cocks det samme system, mens han arbejdede for efterretningstjenesten GCHQ, og byggede videre på en idé fra sin kollega James Ellis. Arbejdet var hemmeligstemplet og blev først offentliggjort i 1997. RSA selv blev patenteret i USA i 1983; patentet udløb i september 2000, to uger efter at algoritmen var blevet frigivet til fri brug for alle.
RSA i praksis
Rigtig RSA krypterer aldrig tekst direkte. Beskeden udfyldes med tilfældige bytes efter et skema som OAEP, så den samme besked krypteres forskelligt hver gang, og mønstre ikke kan slippe ud. Fordi RSA er langsom, bruges den mest til at udveksle eller beskytte en kort nøgle til en hurtig symmetrisk kryptering som AES eller til at signere. Store nok kvantecomputere ville kunne faktorisere n hurtigt med Shors algoritme fra 1994, og derfor indføres nye post-kvante-metoder ved siden af RSA.
Udforsk den
Åbn RSA-krypteringsdemoen for at bygge nøgler af dine egne primtal eller af tilfældige primtal med 2 til 8 cifre, se den udvidede euklidiske algoritme finde d række for række, kryptere eller signere en besked tegn for tegn og følge den gentagne kvadrering for et hvilket som helst tegn. Lad så Eve faktorisere n, og se, hvordan den tid, hun skal bruge, vokser med primtallenes størrelse.
Ofte stillede spørgsmål
Hvorfor har RSA brug for primtal?
Fordi φ(n) kun er let at beregne, når man ved, hvordan n deler sig i primtal. For n = p × q med p og q primtal er φ(n) = (p − 1)(q − 1). Primtal gør også n så svært som muligt at faktorisere i forhold til dets størrelse, da det slet ikke har nogen små faktorer.
Hvorfor er e ofte 65537?
65537 = 2¹⁶ + 1 er et primtal og har kun to 1-taller binært, så kryptering med det kræver kun 16 kvadreringer og én multiplikation. Det er også stort nok til at undgå svagheder ved meget små eksponenter som 3.
Hvad er forskellen på RSA og Diffie–Hellman?
Diffie–Hellman lader to personer blive enige om en fælles hemmelig nøgle over en åben kanal; den krypterer eller signerer ikke noget i sig selv. RSA krypterer og signerer direkte med et nøglepar. Begge hviler på problemer, der er lette den ene vej og svære den anden: faktorisering for RSA, den diskrete logaritme for Diffie–Hellman.
Kan demoens nøgler bruges til rigtig kryptering?
Nej. Dens primtal har højst et dusin cifre, så enhver nøgle, den laver, kan faktoriseres på sekunder eller mindre, og den krypterer hvert tegn for sig uden udfyldning. Den er beregnet til at vise, hvordan RSA virker, ikke til at beskytte noget.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Åbn RSA-krypteringsdemoen