RSA

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 $d$ slik at $sfd(d,b)=1$
• Tallene $n$ og $d$ kan nå offentligjøres for at sender kan begynne kryptering. Dette er den offentlige nøkkelen(en.: public key).
• Kongruensen $dx\equiv 1 \pmod{b}$ regnes nå ut og det minste positive tallet velges til det hemmelige tallet $e$. Nå er altså $d\cdot e \equiv 1 \pmod{b}$. $e$ er den private nøkkelen(en.: private key).

Kryptering

• Meldingen som skal sendes gjøres om til tall. La $M$ vere ett av tallene.
• Vi finner nå det minste positive tallet for $N$, slik at $N \equiv M^d \pmod{n}$. Resten ved divisjonen $M^d: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^e \pmod{n}$. Ved å finne resten av $N^e: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 $d$ slik at $sfd(d,b)=1$.

Vi faktoriserer $b$.
$24=2\cdot 2\cdot 2\cdot 3$ 
Nå velger vi et tall for $d$. Vi kan velge $d=11$ siden $11$ ikke finnes i $24$
Vi ser at $sfd(11,24)=1$

Vi offentligjør nøklene n og d

$n=35$ og $d=11$

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

$dx\equiv 1 \pmod{b}$
$11x\equiv 1 \pmod{24}$
$11x\equiv 1+5\cdot 24 \pmod{24}$
$11x\equiv 121 \pmod{24}$
$11x\equiv 11\cdot 11 \pmod{24}$
$x\equiv 11 \pmod{24}$

Det hemmelige tallet er dermed $e=x=11$

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 $d$ og $n$

$d=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^d \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 $e$ og den offentlige nøkkelen $n$

$e=11$ og $n=35$

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

$M\equiv N^e \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 å 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 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 datarelaterte artikkelen er dessverre kort eller mangelfull, og du kan hjelpe Wikipedia ved å utvide den.
Det finnes mer utfyllende artikkel/artikler på  .