RSA

Fra Wikipedia, den frie encyklopedi
Gå til: navigasjon, søk

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

Drift[rediger | rediger kilde]

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

Generering av nøkkeltall[rediger | rediger kilde]

  • 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[rediger | rediger kilde]

  • 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[rediger | rediger kilde]

  • 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[rediger | rediger kilde]

Generering av nøkkeltall[rediger | rediger kilde]

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[rediger | rediger kilde]

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[rediger | rediger kilde]

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[rediger | rediger kilde]

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 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[rediger | rediger kilde]

  1. ^ SIAM News, Volume 36, Number 5, June 2003,"Still Guarding Secrets after Years of Attacks, RSA Earns Accolades for its Founders", by Sara Robinson
datastubbDenne datarelaterte artikkelen er dessverre kort eller mangelfull, og du kan hjelpe Wikipedia ved å utvide den.