RSA

«RSA» har flere betydninger.

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{\pmod {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}{\pmod {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}{\pmod {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{\pmod {b}}$

$11d\equiv 1{\pmod {24}}$

$11d\equiv 1+5\cdot 24{\pmod {24}}$

$11d\equiv 121{\pmod {24}}$

$11d\equiv 11\cdot 11{\pmod {24}}$

$d\equiv 11{\pmod {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}{\pmod {n}}$

$N\equiv 8^{11}{\pmod {35}}$

$N\equiv 8589934592{\pmod {35}}$

$N\equiv 8589934592-245426702\cdot 35{\pmod {35}}$

$N\equiv 22{\pmod {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}{\pmod {n}}$
$M\equiv 22^{11}{\pmod {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{\pmod {35}}$

$22^{2}=484\equiv 29{\pmod {35}}$

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

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

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

$22^{1}\cdot 22^{2}\cdot 22^{8}\equiv 22\cdot 29\cdot 1{\pmod {35}}$

$22^{1+2+8}\equiv 638{\pmod {35}}$

$22^{11}\equiv 638-18\cdot 35{\pmod {35}}$

$22^{11}\equiv 8{\pmod {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.

Referanser

Denne artikkelen er en spire. Du kan hjelpe Wikipedia ved å utvide den.