RSA

Mal:Andrebetydninger RSA er en krypteringsalgoritme basert på offentlig nøkkel (en.: public key).

Drift

For å bruke RSA-algoritmen må den gjennom tre steg; generering av nøkkeltall, kryptering og dekryptering.

Generering av nøkkeltall

• Mottaker finner fram to primtall som $p$ og $q$ og regner ut $n=p\cdot q$ og $b=(p-1)\cdot (q-1)$. For at dette skal bli tilstrekkelig sikkert må man velge to store primtall (over noen 100 siffer i hver).
• Nå velger mottaker et tall $e$ slik at $sfd(e,b)=1$
• Tallene $n$ og $e$ kan nå offentliggjøres for at sender kan begynne kryptering. Dette er den offentlige nøkkelen (en.: public key).
• Kongruensen $ed\equiv 1(\mathrm{mod}b)$ regnes nå ut, og det minste positive tallet velges til det hemmelige tallet $d$. ($d$= hemmelig dekrypteringsnøkkel).

Kryptering

• Meldingen som skal sendes gjøres om til tall. La $M$ være ett av tallene.
• Vi finner nå det minste positive tallet for $N$, slik at $N\equiv M^e(\mathrm{mod}n)$. Resten ved divisjonen $M^e:n$ er altså den hemmelige meldingen.
• Nå kan avsender sende $N$ til mottaker.

Dekryptering

• I dekrypteringsprosessen er $M$ det minste positive tallet i $M\equiv N^d(\mathrm{mod}n)$. Ved å finne resten av $N^d:n$ kan man finne meldingen, $M$.

Eksempel

Generering av nøkkeltall

Vi velger to primtall som $p$ og $q$.

$p=5$ og $q=7$

Vi finner n og b.

$n=p\cdot q=5\cdot 7=35$

$b=(p-1)(q-1)=(5-1)(7-1)=4\cdot 6=24$

Nå må vi finne en verdi for $e$ slik at $sfd(e,b)=1$.

Vi faktoriserer $b$.

$24=2\cdot 2\cdot 2\cdot 3$ 

Nå velger vi et tall for $e$. Vi kan velge $e=11$ siden $11$ ikke finnes i $24$

Vi ser at $sfd(11,24)=1$

Vi offentliggjør nøklene n og e, (e = encryption key)

$n=35$ og $e=11$

Nå må vi lage det hemmelige tallet $d$.

$ed\equiv 1(\mathrm{mod}b)$

$11d\equiv 1(\mathrm{mod}24)$

$11d\equiv 1+5\cdot 24(\mathrm{mod}24)$

$11d\equiv 121(\mathrm{mod}24)$

$11d\equiv 11\cdot 11(\mathrm{mod}24)$

$d\equiv 11(\mathrm{mod}24)$

Det hemmelige tallet er dermed $d=11$ (d=decryption key)

OBS: $e$ og $d$ er ikke alltid like. Det er bare en tilfeldighet at de er like i dette eksemplet.

Kryptering

Vi mottar de offentlige nøklene $e$ og $n$

$e=11$ og $n=35$

Meldingen $M=8$ ønskes å bli sendt, men den må krypteres først.
For å finne $N$, den krypterte meldingen, gjør vi slik:

$N\equiv M^e(\mathrm{mod}n)$

$N\equiv 8^{11}(\mathrm{mod}35)$

$N\equiv 8589934592(\mathrm{mod}35)$

$N\equiv 8589934592-245426702\cdot 35(\mathrm{mod}35)$

$N\equiv 22(\mathrm{mod}35)$

Den hemmelige meldingen er $N=22$

Dekryptering

Vi mottar den krypterte meldingen $N$.

$N=22$

Fra tidligere kjenner vi den hemmelige nøkkelen $d$ og den offentlige nøkkelen $n$

$d=11$ og $n=35$

Vi ser at det er en sammenheng mellom $N$, $d$ og $n$ slik at vi kan finne $M$.

$M\equiv N^d(\mathrm{mod}n)$
$M\equiv 22^{11}(\mathrm{mod}35)$

For å få lettere tall å regne med så bruker vi litt kreativ regning. Vi ser på eksponenter av 22 som er lavere enn 11.

$22^1=22\equiv 22(\mathrm{mod}35)$

$22^2=484\equiv 29(\mathrm{mod}35)$

$22^4=(22^2{)}^2\equiv 29^2\equiv 841\equiv 1(\mathrm{mod}35)$

$22^8=(22^4{)}^2\equiv 1^2\equiv 1(\mathrm{mod}35)$

Vi ser at $11=1+2+8$

$22^1\cdot 22^2\cdot 22^8\equiv 22\cdot 29\cdot 1(\mathrm{mod}35)$

$22^{1+2+8}\equiv 638(\mathrm{mod}35)$

$22^{11}\equiv 638-18\cdot 35(\mathrm{mod}35)$

$22^{11}\equiv 8(\mathrm{mod}35)$

Vi har nå funnet den krypterte meldingen

$M=8$

Historie

Algoritmen ble først beskrevet i 1977 av Ron Rivest, Adi Shamir og Leonard Adleman ved MIT; de tre bokstavene RSA er initialene i etternavnene deres i samme rekkefølge som de fremkommer på artikkelen deres.

Den Britiske matematikeren Clifford Cocks beskrev et lignende system i et internt dokument for den britiske etterretningstjenesten GCHQ. Hans oppdagelse ble ikke offentliggjort før i 1997, grunnet top-secret klassifisering av arbeidet.

MIT fikk et patent på "Cryptographic communications system and method" som benyttet algoritmen i 1983. Patentet ville vært gyldig til 2003, men ble offentliggjort av RSA 21. september 2000.