«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
og
og regner ut
og
. For at dette skal bli tilstrekkelig sikkert må man velge to store primtall (over noen 100 siffer i hver). - Nå velger mottaker et tall
slik at ![{\displaystyle sfd(e,b)=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/392e813fb7efcb60eaac9a0f0b33b160083da103)
- Tallene
og
kan nå offentliggjøres for at sender kan begynne kryptering. Dette er den offentlige nøkkelen (en.: public key). - Kongruensen
regnes nå ut, og det minste positive tallet velges til det hemmelige tallet
. (
= hemmelig dekrypteringsnøkkel).
Kryptering
- Meldingen som skal sendes gjøres om til tall. La
være ett av tallene. - Vi finner nå det minste positive tallet for
, slik at
. Resten ved divisjonen
er altså den hemmelige meldingen. - Nå kan avsender sende
til mottaker.
Dekryptering
- I dekrypteringsprosessen er
det minste positive tallet i
. Ved å finne resten av
kan man finne meldingen,
.
Eksempel
Generering av nøkkeltall
Vi velger to primtall som
og
.
og
Vi finner n og b.
![{\displaystyle n=p\cdot q=5\cdot 7=35}](https://wikimedia.org/api/rest_v1/media/math/render/svg/132ab89ab03f63a25063193bf59e227cc20fff4f)
Nå må vi finne en verdi for
slik at
.
Vi faktoriserer
.
Nå velger vi et tall for
. Vi kan velge
siden
ikke finnes i ![{\displaystyle 24}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0be92101c8b0277e66fdefeef1ccdd7788e88ef5)
Vi ser at
Vi offentliggjør nøklene n og e, (e = encryption key)
og
Nå må vi lage det hemmelige tallet
.
![{\displaystyle ed\equiv 1{\pmod {b}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9de902d140be0bd3bf18e3d144558546db9172c9)
![{\displaystyle 11d\equiv 1{\pmod {24}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1065eb5ae318ee91ea652d5d7730c050c8c71a6f)
![{\displaystyle 11d\equiv 1+5\cdot 24{\pmod {24}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7c6352437fc94075a95c2bbe90db6a6eda98c3f5)
![{\displaystyle 11d\equiv 121{\pmod {24}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/49c5a703d7ccfa90a01cc27a0914ac1bc325ac42)
![{\displaystyle 11d\equiv 11\cdot 11{\pmod {24}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cfafe42deb030b6f192afd3759a342d7983d44c1)
Det hemmelige tallet er dermed
(d=decryption key)
OBS:
og
er ikke alltid like. Det er bare en tilfeldighet at de er like i dette eksemplet.
Kryptering
Vi mottar de offentlige nøklene
og
og
Meldingen
ønskes å bli sendt, men den må krypteres først.
For å finne
, den krypterte meldingen, gjør vi slik:
![{\displaystyle N\equiv M^{e}{\pmod {n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6aa46ebd37fed35785c8fdc5be92b3e4b7b8cda5)
![{\displaystyle N\equiv 8^{11}{\pmod {35}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/af55d326434f13114d2f316f992d67c8d7d83e02)
![{\displaystyle N\equiv 8589934592{\pmod {35}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/626c3b4b554983ed6affde266e51a4a16c711e3d)
![{\displaystyle N\equiv 8589934592-245426702\cdot 35{\pmod {35}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7d8c8871902107cfefd9edb76a48b438280d8e3a)
Den hemmelige meldingen er
Dekryptering
Vi mottar den krypterte meldingen
.
Fra tidligere kjenner vi den hemmelige nøkkelen
og den offentlige nøkkelen ![{\displaystyle n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
og
Vi ser at det er en sammenheng mellom
,
og
slik at vi kan finne
.
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a6181d53047e482d074407c305d53620f7aa1d2b)
![{\displaystyle 22^{2}=484\equiv 29{\pmod {35}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e606ccd4c724f99abcc9bafa8291da69cd061e1f)
![{\displaystyle 22^{4}=(22^{2})^{2}\equiv 29^{2}\equiv 841\equiv 1{\pmod {35}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/60f58be5ee8f1e4ac5d3a03208def58b244ff014)
Vi ser at ![{\displaystyle 11=1+2+8}](https://wikimedia.org/api/rest_v1/media/math/render/svg/35375afd6fb58b8544f62940d548c470c5bc7ed2)
![{\displaystyle 22^{1}\cdot 22^{2}\cdot 22^{8}\equiv 22\cdot 29\cdot 1{\pmod {35}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/40abc4f5f4365ad02b966048fd2b2fc495dfc653)
![{\displaystyle 22^{1+2+8}\equiv 638{\pmod {35}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/366a613bd9f9f044b7f6f1b5c671c6b8599de624)
![{\displaystyle 22^{11}\equiv 638-18\cdot 35{\pmod {35}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/02b44770c89627ff9af167dc07514f58c0c170a1)
Vi har nå funnet den krypterte meldingen
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
- ^ SIAM News, Volume 36, Number 5, June 2003 Arkivert 16. januar 2017 hos Wayback Machine.,"Still Guarding Secrets after Years of Attacks, RSA Earns Accolades for its Founders", by Sara Robinson
Denne artikkelen er en spire. Du kan hjelpe Wikipedia ved å utvide den.
Oppslagsverk/autoritetsdata | Encyclopædia Britannica · MathWorld |
---|