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

Kryptering

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

Dekryptering

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

Eksempel

Generering av nøkkeltall

Vi velger to primtall som ${\displaystyle p}$ og ${\displaystyle q}$.

${\displaystyle p=5}$ og ${\displaystyle q=7}$

Vi finner n og b.

${\displaystyle n=p\cdot q=5\cdot 7=35}$

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

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

Vi faktoriserer ${\displaystyle b}$.

${\displaystyle 24=2\cdot 2\cdot 2\cdot 3}$ 

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

Vi ser at ${\displaystyle sfd(11,24)=1}$

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

${\displaystyle n=35}$ og ${\displaystyle e=11}$

Nå må vi lage det hemmelige tallet ${\displaystyle d}$.

${\displaystyle ed\equiv 1{\pmod {b}}}$

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

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

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

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

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

Det hemmelige tallet er dermed ${\displaystyle d=11}$ (d=decryption key)

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

Kryptering

Vi mottar de offentlige nøklene ${\displaystyle e}$ og ${\displaystyle n}$

${\displaystyle e=11}$ og ${\displaystyle n=35}$

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

${\displaystyle N\equiv M^{e}{\pmod {n}}}$

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

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

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

${\displaystyle N\equiv 22{\pmod {35}}}$

Den hemmelige meldingen er ${\displaystyle N=22}$

Dekryptering

Vi mottar den krypterte meldingen ${\displaystyle N}$.

${\displaystyle N=22}$

Fra tidligere kjenner vi den hemmelige nøkkelen ${\displaystyle d}$ og den offentlige nøkkelen ${\displaystyle n}$

${\displaystyle d=11}$ og ${\displaystyle n=35}$

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

${\displaystyle M\equiv N^{d}{\pmod {n}}}$
${\displaystyle 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.

${\displaystyle 22^{1}=22\equiv 22{\pmod {35}}}$

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

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

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

Vi ser at ${\displaystyle 11=1+2+8}$

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

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

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

${\displaystyle 22^{11}\equiv 8{\pmod {35}}}$

Vi har nå funnet den krypterte meldingen

${\displaystyle 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.^[1]

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