RSA

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}$