RSA - matematikk, IT

En offentlig RSA-nøkkel består av to positive heltall e og n, hvor n er produktet av to store primtall p og q. Den private nøkkelen er et positivt heltall d som oppfyller kongruensen ed≡ 1 (mod (p–1)(q–1)) (Uttrykket (p–1)(q–1) er L. Eulers φ-funksjon av n).

Tallene e og n offentliggjøres til bruk for de som skal kryptere meldinger. Fra en klartekst M beregner man den krypterte teksten C ved å eksponensiere M modulo n:

C ≡ M^e (mod n)

For å dekryptere meldingen trenger man den private nøkkelen d. Ifølge Eulers generalisering av Fermats lille sats (se P. de Fermat), kan man rekonstruere klarteksten fra kryptoteksten C som følger: C^d ≡ (M^e)^d = M^(ed) ≡ M (mod n).

To primtall velges p=32749 og q=40277 som multiplisert gir n = p*q = 1319031473 og φ=(p-1)(q-1)=1318958448. Velg så e=17 og finn d=1241372657 slik at ed ≡ 1 (mod φ). Den offentlige nøkkelen er paret (n,e) = (1319031473, 17) mens den private nøkkelen er d=1241372657.

Om meldingen m=12345 skal krypteres beregner avsenderen c=m^e mod n = 12345¹⁷ mod 1319031473 = 410553092.

For å dekryptere beregnes c^d mod n = 410553092^1241372657 mod 1319031473= 12345.

Primtallene p og q i dette eksempelet har en lengde på kun 16 bit. I en virkelig anvendelse bør de gjerne være flere tusen bit. Beregningene krever manipulasjon av svært store tall.

RSA ble publisert i 1978 og har over tid blitt en av de mest utbredte asymmetriske kryptosystemene. Metoden er ikke så effektiv som symmetrisk kryptografi, der krypteringsnøkkel og dekrypteringsnøkkel er like, og den blir derfor spesielt brukt til behandling av mindre informasjonsmengder, slik som nøkkelhåndtering og digital signering. Sikkerheten i RSA er basert på at faktorisering av store tall er svært ressurskrevende.

Hvis primtallene p og q er kjent, er det lett å beregne den private nøkkelen d og dermed dekryptere kryptoteksten. Sikkerheten i RSA avhenger dermed av at en uvedkommende ikke klarer å faktorisere modulus n. Forskning innen faktorisering har de siste 30 årene brakt fram en rekke sofistikerte metoder basert på tallteoretiske resultater. De mest effektive metodene man kjenner til er basert på massiv parallellisering, der samme program kjøres på opptil flere tusen datamaskiner samtidig.

Ved systematiske faktoriseringsprosjekter benyttes typisk Mersenne-tall som er tall på formen 2ⁿ − 1, der n er et primtall. Alle Mersenne-tall med n mellom 1000 and 1200 ble faktorisert i et multiple-tall-filter prosjekt der mange av filtreringstrinnene ble muliggjort samtidig for multiple tall av en gruppe som inkluderte en rekke kjente matematikere. Prosjektet ble påbegynt i 2010, og forskjellige deler av prosjektet ble ferdig til forskjellig tid. Hele prosjektet ble erklært ferdig i 2014. Prosjektet krevde i størrelsesorden 7500 CPU-år med 2.2 GHz Opterons, herav ca. 5700 brukt på filtrering og 1800 på lineær algebra. Den største tallet som er som er faktorisert (per mars 2017) er 2ⁿ − 1, der n = 1199. Typiske kommersielle anvendelser benytter RSA-nøkler som er 1024 eller 2048 bit. For informasjon som behøver langsiktig beskyttelse anbefales nøkler på minst 2048 bit.