Ogled vira RSA

'''RSA''' je [[algoritem]], ki spada v družino algoritmov za [[Šifriranje sporočil|šifriranje]] z [[javni ključ|javnim ključem]]. Je prvi algoritem praktično primeren za podpisovanje in šifriranje z javnim ključem. RSA se na široko uporablja v [[protokol]]ih, namenjenim komercialnim [[komunikacija]]m in velja kot varen, če je le dolžina ključev dovolj velika.

==Zgodovina ==
Algoritem so leta [[1977]] opisali [[Ronald Rivest|Ron Rivest]], [[Adi Shamir]] in [[Leonard Adleman|Len Adleman]] na [[Tehnološki inštitut Massachusettsa|MIT]] (Massachusetts Institute of Technology). Črke RSA so začetnice njihovih imen.

[[Clifford Cocks]], britanski [[matematik]] zaposlen pri [[GCHQ]] (Government Communications Headquarters), je predstavil ekvivalenten sistem v notranjem dokumentu leta [[1973]]. Predstavljen sistem bi potreboval relativno drage računalniške komponente, kar je povzročalo pomisleke in, kot je znano, se sistem ni razširil. Ponovno je bil sistem obravnavan leta [[1997]] in je bil razvrščen v razred stroge tajnosti.

MIT  je algoritem patentiral leta [[1983]] v [[Združene države Amerike|ZDA]] kot »U.S. Patent 4,4050,829«.  Prenehal je veljati [[21. september|21.9.]][[2000]]. Do tega časa je bilo treba v ZDA plačevati licenčnino, zato algoritem ni bil vključen v nekatere produkte.

==Postopek ==

* '''Predstavitev'''
RSA vsebuje dva ključa: javnega in zasebnega (ključ je konstantno število, ki ga kasneje uporabljamo v formuli za šifriranje). Javni ključ poznajo vsi in se uporablja  za šifriranje sporočil. Sporočila lahko dešifriramo samo z zasebnim  ključem. Z drugimi besedami: vsi lahko sporočilo zašifrirajo, prebere pa ga lahko samo lastnik zasebnega ključa. 

Praktičen primer: oseba A pošlje osebi B škatlo z odprto ključavnico, za katero ima ključ samo oseba A. Oseba B prejme škatlo in vanjo položi sporočilo, napisano v preprostem jeziku. Škatlo zaklene s ključavnico osebe A in ji jo pošlje. Oseba B pošlje škatlo osebi A, kjer jo ta odpre s svojim ključem. V tem primeru je škatla s ključavnico javni ključ osebe A in ključ za to ključavnico je njen zasebni ključ.

*'''Kreiranje ključev'''
Predvidevamo, da [[oseba|osebi]] A in B [[komunikacija|komunicirata]] preko nezaščitenega [[prenosni medij|prenosnega medija]] in oseba A želi osebi B poslati zasebno ali tajno sporočilo. Z uporabo RSA bo oseba A izvedla naslednje korake za kreiranje javnega in [[zasebni ključ|zasebnega ključa]]:

# Izbere dve [[praštevilo|praštevili]], p in q tako da velja <math>p \ne q</math>. Izbere ju tako, da sta [[naključen|naključni]] in [[neodvisen|neodvisni]] druga od druge.
# Izračuna  <math>n = p q \,</math>.
# Izračuna [[koeficient]] <math>\phi(n) = (p-1)(q-1) \,</math>.
# Izbere [[celo število]] ''e'', tako da velja <math>1 < e < \phi(n) \,</math>, ki je relativno praštevilo številu <math>\phi(n) \,</math>
#Izračuna <math>d</math>, tako da je <math>d e \equiv 1 \pmod{\phi(n)}</math> To je <math>de = 1 + k\varphi(n)</math> za celoštevilčno vrednot <math>k</math>.

* [[praštevilo|praštevila]] lahko s preizkušanjem predhodno testiramo
* korake 4 in 5 lahko izvedemo z razširjenim [[Evklidov algoritem|Evklidovim algoritmom]]
* korak 5 lahko izvedemo tudi z iskanjem celega števila x, s pomočjo katerega dobimo celo število, ki ga potem uporabimo za <math>\phi = (p-1)(q-1) \,</math>

Javni ključ je sestavljen iz:
* ''n'', [[generator]]
* ''e'', javni [[potenciranje|eksponent]] (šifrirni eksponent)

Zasebni ključ je sestavljen iz:
* ''n'', generatorja, ki je javen in se pojavlja v javnem ključu
* ''d'', zasebni eksponent (dešifrirni eksponent), ki mora ostati skriven.

Po navadi shranimo različno obliko zasebnega ključa (z upoštevanjem [[Kitajski izrek o ostankih|CRT]] parametrov)
* ''p'' in ''q'' sta praštevili iz kreiranega ključa
* ''d mod(p-1)'' in ''d mod (q-1)'' pogosto poznana  kot ''dmp1'' in ''dmq1''
(1/q) mod p največkrat poznan kot iqmp

Ta oblika dovoljuje hitrejše [[Šifriranje sporočil|dešifriranje]] in podpisovanje z uporabo [[Kitajski izrek o ostankih|kitajskega izreka o ostankih]] (CRT). V tej obliki morajo biti skriti vsi deli privatnega ključa. 

Oseba A pošlje javni ključ osebi B , pri tem pa skrbi za tajnost zasebnega ključa. Vrednosti ''p'' in ''q'' sta občutljivi, ker sta faktorja n in omogočata izračun ''d'' s podanim ''e''. Če ''p'' in ''q'' nista spravljena v CRT obliki zasebnega ključa, ju je potrebno varno izbrisati, prav tako, kot je potrebno izbrisati tudi ostale vrednosti, ki so bile ustvarjene pri računanju para javnega in skrivnega ključa.

[[Kategorija:Šifrirni algoritmi]]
[[Kategorija:1977 v znanosti]]