Wikiproiektu:EHU-Wikipedia 2016/Probalekua/Proba orria3-en iturria ikusi

'''RSA''', [[1977]] urtean [[Ronald Rivest]], [[Adi Shamir]] eta [[Leonard Adleman]]ek sortu zuten [[Kriptografia|kriptografia-sistema]] da<ref>Smart, Nigel (February 19, 2008). "Dr Clifford Cocks CB". Bristol University. Retrieved August 14, 2011.</ref>. Oso kriptografia-sistema segurua da eta [[Zenbakien teoria|zenbaki-teorian]] oinarritzen da. Berezia da [[gako publiko|publikoa den gako]] bat erabiltzen duelako. Mezuak [[Enkriptatze|enkriptatuta]] jaso nahi dituen pertsonak bere gako publikoa beste edonori pasatzen dio, baina mezu enkriptatu horiek irakurtzeko behar den [[gako pribatua]] berak bakarrik daki. Sistema honetan abantaila handia da igorle eta hartzailearen artean ez dela gako sekretua adostu behar.

[[Fitxategi:Adi Shamir 2009 crop.jpg|thumb|175px|[[Adi Shamir]], RSA algoritmoaren hiru egileetako bat.]]

RSA [[algoritmo]]a erabiliz bidalitako mezuak, zenbakien bidez agertzen dira eta enkriptatzearen funtzionamendua ausaz aukeratutako bi [[zenbaki lehen]] handi lortzean datza (gutxienez 100 [[digitu]] dituzten zenbaki lehenak). 

==Historia==
1976. urtean [[Whitfield Diffie]] eta [[Martin Hellman]] ikerlariek, gako publiko eta gako pribatu [[gako asimetriko|asimetrikoan]] (hau da bi gako ezbedin, non bat izateak ez du bestearen informaziorik ematen) oinarritutako [[Kriptosistema|kriptosistemaren]] kontzeptua asmatu zuten. Zenbaki teoria aplikatuz kriptosistema eraginkor bat ekoizten saiatu ziren, zenbaki bat beste batez berretuz eta ondoren beste zenbaki lehen batez [[modulu]] eginez gako publiko bat lortzen zuten. Funtzionatzen zuen kriptosistema bat lortzetik hurbil geratu baziren ere ez zuten lortu noranzko bakar batean zuzendua dagoen [[funtzio]] bat formulatzea, beraz gako publikoaz gako pribatua lortzea posiblea zen.

Ron Rivest, Adi Shamir eta Leonard Adleman [[MIT]]ko ikerlariak, urte baten zehar, noranzko bakar batean zuzendua dagoen eta kontrako noranzkoan erabiltzea zaila den funtzio baten bila aritu ziren. Gogor saiatu ondoren, ezinezkoa zela pentsatzen hasiak zirela, Rivest noranzko bateko funtzioari buruz pentsatzen aritu zen gau oso bat eta lan mordoa egin ondoren hurrengo egunerako lortua zuen funtzioa<ref>Calderbank, Michael (2007-08-20). "The RSA Cryptosystem: History, Algorithm, Primes"</ref>.

Gaur egun RSA kriptosistemako gakoak kalkulatzen dituen algoritmoari, RSA algoritmo deritzo<ref>Robinson, Sara (June 2003). "Still Guarding Secrets after Years of Attacks, RSA Earns Accolades for its Founders" (PDF). SIAM News. 36 (5).</ref>.

==Funtzionamendua==

===Gakoen hautaketa===
RSA kriptosistema gako publiko eta pribatu asimetrikoetan oinarrituta dago. Gako publikoa inolako zifratzerik gabe bidaltzen da. Interneten [[datu pakete|datu paketea]] lortu ezkero edonork jakin dezake zein den gako publikoa, mezua bidaltzeko eskaera egin ez dutenek barne. Gako horrekin bidali nahi den informazioa zifratzen da, informazio hau gako pribatua izan ezean ezin daiteke praktikoa litzatekeen denbora batean deszifratu, beti ere gakoak lortzeko orduan erabilitako zenbakiak nahikoa handiak badira. Hau zenbaki handiak faktorizatzeak duen zailtasunari esker da posible, eta honetan hain zuzen ere oinarritzen da RSA algoritmoa<ref>Rivest, R.; Shamir, A.; Adleman, L. (February 1978). "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems" (PDF). Communications of the ACM. 21 (2): 120–126. doi:10.1145/359340.359342.</ref>.

RSA algoritmoak 5 urrats jarraitzen ditu:

#''p'' eta ''q'' zenbaki lehenak aukeratu.
#<math>n = p\cdot q </math> kalkulatu.
#<math>m = (p-1)\cdot(q-1) \,</math> kalkulatu.
#''r'' kalkulatzeko, <math>zkh(m,r)=1 \,</math>bete behar da; hau da, lehen erlatiboak izan behar dira. Ez dago balio posible bakarra, baina orokorrean balio txikiena aukeratzen da. Hau izango da gure gako publikoa.
#''s'' ''r''-ren [[alderantzizko modularra|alderantzizkoa modulu]] ''m'' kalkulatu behar da. Hau da, <math>s = {r}^{-1}\pmod m\,</math>. Hau izango da gure gako pribatua.

===Zifratzea===

Mezua zifratu aurretik, derrigorrezkoa da karaktereak zenbakitan bihurtzea. Horretarako, bide ezberdinak existitzen dira. Gehien erabiltzen den kodeketa metodoa [[ASCII]] taula da, non alfabeto latinoko letra larriak 65etik 90era doaz (A-Z) eta xeheak 97tik 122ra (a-z). Hauez gain, beste karaktereak (zenbakiak, ikurrak...) ere taula honetan bilduta daude eta bakoitzari zenbaki bat dagokio.

Behin kodetuta, zifratze-prozesua hasten da. Prozesu honetan letrei dagozkien zenbakiak zeharo aldatzen dira, dena eragiketa bakarretik pasatuz.

<center><math> R = {X}^{r} \pmod n \,</math></center>

non X hizkiari dagokion zenbakia den eta R zifratutako X den.

===Deszifratzea===

Behin mezua hartzaileak harrapatzean, zifratutako jatorrizko zenbakiak  berreskuratzeko beste berreketa modular bat eragin behar zaie, baina oraingo kasuan r-rekin berretu beharrean, s gako pribatuarekin egin behar da.

<center><math> X = {R}^{s} \pmod n \,</math></center>

non R lehen zifratutako zenbakia den eta X zifratu aurretik lortutako zenbakia den.

Sistemak oso sinplea eta edonork deszifratzeko erraza dirudien arren, gogoratu algoritmo honetan erabilitako zenbakiak 200 zifratik gorako zenbakiak direla eta horiek faktorizatzea ia ezinezkoa dela. Horregatik bakarrik hartzaileak, s daukanak, bakarrik deszifratu ahal du mezua.

Azkenik zenbaki horiek letretara [[deskodeketa|deskodetu]] behar dira. Hasierako prozesuaren bezala, deszifratutako zenbaki bakoitzari letra bat dagokio eta deskodetze horrekin lortzen da RSA zifratzearen azken pausua ematea.





==Egiaztapena==
RSA-ren egiaztapena [[Fermaten teorema txikia|Fermaten teorema txikian]] oinarritzen da. Teorema honen arabera, ''p'' lehena bada eta ''a'' osoa zatitzen ez badu, orduan:
: <math> a^{p - 1} \equiv 1 \pmod{p}</math>

Frogatu behar duguna hurrengoa da: Edozein ''p'' eta ''q'' lehen desberdinak izanik eta ''e'' eta ''d'' positiboak izanik, {{nowrap|''m<sup>ed</sup>'' ≡ ''m'' (mod ''pq'')}} betetzen dela. Hortaz:
: <math>e d \equiv 1 \pmod{\phi(pq)}.</math>

<math>\phi(pq) = (p - 1)(q - 1)</math> izanik, beste modu batera idatziz,
: <math>ed - 1 = h(p - 1)(q - 1)</math>

: ''m<sup>ed</sup>'' eta ''m'' [[Kongruentzia (zenbakien teoria)|kongruenteak]] direla egiaztatzeko mod ''pq'' nahikoa da frogatzea kongruenteak direla mod ''p'' eta mod ''q'' bakoitza bere aldetik.

{{nowrap|''m<sup>ed</sup>'' ≡ ''m'' (mod ''p'')}} frogatzeko, bi kasu hartu behar ditugu kontuan: {{nowrap|''m'' ≡ 0 (mod ''p'')}} eta {{nowrap|''m'' <math>\not\equiv</math> 0 (mod ''p'')}}.

Lehenengo kasuan, ''m'' ''p''-ren multiploa da; beraz, ''m<sup>ed</sup>'' ere. 

Bigarren kasuan,
: <math>m^{e d} = m^{(ed - 1)}m = m^{h(p - 1)(q - 1)}m = \left(m^{p - 1}\right)^{h(q - 1)}m \equiv 1^{h(q - 1)}m \equiv m \pmod{p}</math>

non [[Fermaten teorema txikia]] erabiliz, ''m''<sup>''p''−1</sup> mod ''p'' ordeztu dugu ''1''-egatik.

{{nowrap|''m<sup>ed</sup>'' ≡ ''m'' (mod ''q'')}} berdin frogatzen da, {{nowrap|''m'' ≡ 0 (mod ''q'')}} eta {{nowrap|''m'' <math>\not\equiv</math> 0 (mod ''q'')}} bakoitza bere aldetik frogatuz.

Lehenengo kasuan, ''m<sup>ed</sup>'' ''q''-ren [[Multiplo (matematika)|multiploa]] da; beraz, {{nowrap|''m<sup>ed</sup>'' ≡ 0 ≡ ''m'' (mod ''q'')}}.

Bigarren kasuan,
: <math>m^{e d} = m^{(ed - 1)}m = m^{h(p - 1)(q - 1)}m = \left(m^{q - 1}\right)^{h(p - 1)}m \equiv 1^{h(p - 1)}m \equiv m \pmod{q}</math>

Honela egiaztatzen da edozein ''m'', ''e'' eta ''d'' [[zenbaki oso]] hartuta eta <math>e d \equiv 1 \pmod{\phi(pq)}</math> betetzen bada,
: <math>\left(m^e\right)^d \equiv m \pmod{pq}</math>
=="Padding"==
===RSA aurkako erasoak===
* [[Esponente]] txikiak erabiltzen direnean zifratzean (e.g., e = 3) eta <math>m</math> zenbakia; hau da, zifratu beharreko edukiaren zenbakizko balioa, txikia denean, <math>m</math><sup><math>e</math></sup> zenbakiak hartuko duen balioa <math>n</math> gako publikoarena baino txikiagoa izatea gerta liteke. Kasu honetan, testu zifratua erraz itzul daiteke honen zenbakizko balioa erro <math>e</math> eginez eta ondoren zenbaki osoengatik zatituz.
*Zifratutako testu berdina <math>e</math> jasotzaileri edo gehiagori bidaliz gero, eta jasotzaile denek <math>e</math> esponente berdina badute, <math>p</math> eta <math>q</math> zenbaki lehen ezberdinak izanik, [[Hondarraren Teorema Txinatarra]] erabiliz, erraz deszifra daiteke. Testua berdina ez balitz, eraso hau erabiltzerik badago, beti ere erasotzaileak testuen arteko erlazio lineala baleki.
*RSA zifratzea, guztiz determinista denez (hau da ez du zorizko osagairik, behin zorizko lehenak hautatuz), erasotzaile batek bidalitako testuak duen eduki berdina duen testu bat gako berdinez zifratzen badu, zifratutako testua berdina izango da. Beraz, konparaketa bat eginez baiezta daiteke igorleak bidalitako testua erasotzaileak punturen batean zifratu duen testuaren berdina dela. Kriptosistema bat semantikoki segurua da testu berdinaren edozein bi zifratze ezberdinak direnean. RSA ez da berez semantikoki segurua<ref> S. Goldwasser and S. Micali, Probabilistic encryption & how to play mental poker keeping secret all partial information, Annual ACM Symposium on Theory of Computing, 1982.</ref>, baina "Padding" delako teknikak erabiliz ezaugarri hau bereganatu dezake kriptosistemak.
*RSA kriptosistemaren funtsezko ezaugarri bat, bi testu zifratuen zenbakizko balioen biderkadura eta jatorrizko testuen zenbakizko balioen biderkaduraren zifraketa (gako berdinak erabiliz) berdinak direla da. Erasotzaileak jasotzailearen (gako pribatua duenaren) mezu bat deszifratzea lortzen badu eta mezu hau deszifraturik itzultzea lortzen badu, <math>r</math> gako ezberdin batekin zifratutako testu bat bidal diezaioke erasotzaileak jasotzaileari deszifra dezan eta testua deszifratua bueltan jasotzerakoan, erasotzaileak edozein mezu deszifratzeko adina informazio lortuko du RSAren ezaugarri honegatik.
==="Padding" Teknika===
Azken bi arazo hauek saihesteko asmoz, ohikoa da RSA inplementazio praktikoak jatorrizko testuaren zenbakizko balioari zoriz aukeratzen den zenbaki batez eragitea modu batera edo bestera zifratu aurretik. Ondoren, jatorrizko testua bueltatzeko aurkako eragiketa egiterik baino ez dago. Hau eginez, testuaren zenbakizko balioa seguruak ez diren balioen artean suertatuko ez dela bermatzen da.

==Segurtasuna==
===Hondarraren Teorema Txinatarraren erabilera===
Eraginkortasuna dela eta, kriptografiako pakete askok Hondarraren Teorema Txinatarrarean oinarritzen den optimizazioa erabiltzen dute. Optimizazio hauek berreketa karratu bat egin beharrean, bi berreketa modular egitea ahalbidetzen dute askoz eraginkorragoa dena berreketa modularraren ezaugarriengatik. Berreketa modularra egiteko ez da beharrezkoa berreketa aritmetikoa egitea eta ondoren modulua. Aldiz berreketa bitarraren metodoa erabiliz, algoritmo errekurtsibo bat formulatu daiteke zenbaki handien berreketa aritmetikoarekin konparatuz askoz eraginkorragoa dena.

===Zenbaki konposatuen faktorizazioa eta RSA problema===
RSA kriptosistemaren segurtasuna bi problema matematikotan oinarrituta dago: zenbaki konposatu handien faktorizazioaren problema eta RSA problema, hain zuzen ere. RSA algoritmoaz zifratutako testuaren gako pribatu gabeko deszifratzea ezinezkotzat hartzen da, bi arazo hauek oso zailak baitira, gainera ez dago nahikoa eraginkorra den algoritmo bat, gako  handiez zifratuta dagoen testu bat denbora tarte praktiko batean deszifratzeko.

RSA problema, <math>e</math> berretzaile  bat izanik modulo <math>n</math>, eta <math>c</math> zenbaki bat emanik, <math>m</math> zenbaki bat lortzean datza, non,
{{nowrap|''c'' ≡ ''m''<sup>''e''</sup> (mod ''n'')}}. Arazo honi aurre egiteko modurik eraginkorrena <math>n</math> zenbakia faktorizatzea da, behin faktore lehenak izanik, erasotzaile batek kalkula dezake <math>d</math> exponente bat gako publikoaz baliatuta, <math>d</math> exponente hau gako pribatua izango da eta hau lortu ezkero erasotzaileak testu zifratua erraz deszifra dezake ohiko prozedura erabiliz.

RSA problema ez litzateke nahikoa izango kriptosistema seguru bat eraikitzeko ordea, zenbaki handien faktorizazioa dela eta, RSA arazoari aurre egiteko modu eraginkorrena, hau da <math>n</math> faktorizatzea, ez da hain eraginkorra <math>n</math> handietarako, beraz bi hauek konbinatuz apurtzeko oso zaila den kriptosistema bat eraiki daiteke.

===Gako akasdunak===
<math>n</math> lortzeko erabilitako <math>p</math> eta <math>q</math> balioak ezin dira "hurbil" egon (<math>p-q > 2n^{1/4}</math> izan behar da), bestela Fermaten faktorizazioaz ez litzateke zaila izango <math>p</math> eta <math>q</math> aukitzea <math>n</math> jakin batentzako, beraz hau betetzen ez duten  <math>  p</math> eta <math>q</math> bikoteak baztertuak gelditzen dira.

<math>(p - 1)</math> edo <math>(q - 1)</math> zenbakiak faktore oso txikiak baino ez badituzte bizkor kalkula daitezke <math>  p</math> eta <math>q</math>, Pollarden <math>p-1</math> algoritmoa erabiliz, beraz <math>  p</math> eta <math>q</math> bikote hau ere baztertu beharra dago.

Oso garrantzitsua da <math>d</math> exponente pribatua nahikoa handia izatea (<math>d > n^{1/4}/3</math>), horrela izan ezean  eta<math>q<p<2q</math> betetzen bada era eraginkor batean kalkula daiteke <math>d</math>
<math>e</math> eta <math>n</math> gako publikoa izanik.

===Ausazko zenbaki ekoizte algoritmo on baten garrantzia===

Kriptografikoki ona den ausazko zenbaki ekoizle (RNG, Random number generator) bat erabili behar da <math>p</math> eta <math>q</math> zenbakien ekoizpenerako eta honez gain hazia (zenbaki bat, non RNG algoritmo batean erabiltzean sasiausazkoak diren zenbakiak lortzen dituena) ere ahalik eta modu zorizkoenean lortu behar da. 

Pauso hau zuzen ez egiteak RSA kriptosistemarekin zer ikusirik ez duten erasoak ahalbidetzen ditu, RNG algoritmoaren iragargaitasuna erasotuz alegia.

===Denbora erasoak===
Erasotzaileak jasotzaileak mezua deszifratzeko erabiliko duen konputadorearen ezaugarriak jakingo balitu, mezu bat deszifratzeko jasotzaileak behar duen denbora neurtuz posiblea da  <math>d</math> exponente pribatua zehaztasun askorekin bornatzea. Mota honetako arazoak ekiditeko era bat, konputadoreari beti denbora berdina (<math>d</math> edozein izanik beharko zuen denbora maximoa) erabiltzeko programatzea da.

==Erreferentziak==