Wikiproiektu:EHU-Wikipedia 2016/Probalekua/Proba orria3

RSA, 1977 urtean Ronald Rivest, Adi Shamir eta Leonard Adlemanek sortu zuten kriptografia-sistema da. Oso kriptografia-sistema segurua da eta zenbaki-teorian oinarritzen da. Berezia da publikoa den gako bat erabiltzen duelako. Mezuak 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.

Adi Shamir, RSA algoritmoaren hiru egileetako bat.

RSA algoritmoa 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 asimetrikoan (hau da bi gako ezbedin, non bat izateak ez du bestearen informaziorik ematen) oinarritutako 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 MITko 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.

Gaur egun RSA kriptosistemako gakoak kalkulatzen dituen algoritmoari, RSA algoritmo deritzo.

Funtzionamendua

Gakoen hautaketa

RSA kriptosistema gako publiko eta pribatu asimetrikoetan oinarrituta dago. Gako publikoa inolako zifratzerik gabe bidaltzen da. Interneten 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.

RSA algoritmoak 5 urrats jarraitzen ditu:

1. p eta q zenbaki lehenak aukeratu.
2. $n=p\cdot q$ kalkulatu.
3. $m=(p-1)\cdot (q-1)\,$ kalkulatu.
4. r kalkulatzeko, $zkh(m,r)=1\,$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.
5. s r-ren alderantzizkoa modulu m kalkulatu behar da. Hau da, $s={r}^{-1}{\pmod {m}}\,$. 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.

$R={X}^{r}{\pmod {n}}\,$

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.

$X={R}^{s}{\pmod {n}}\,$

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 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 txikian oinarritzen da. Teorema honen arabera, p lehena bada eta a osoa zatitzen ez badu, orduan:

$a^{p-1}\equiv 1{\pmod {p}}$

Frogatu behar duguna hurrengoa da: Edozein p eta q lehen desberdinak izanik eta e eta d positiboak izanik, m^ed ≡ m (mod pq) betetzen dela. Hortaz:

$ed\equiv 1{\pmod {\phi (pq)}}.$

$\phi (pq)=(p-1)(q-1)$ izanik, beste modu batera idatziz,

$ed-1=h(p-1)(q-1)$

m^ed eta m kongruenteak direla egiaztatzeko mod pq nahikoa da frogatzea kongruenteak direla mod p eta mod q bakoitza bere aldetik.

m^ed ≡ m (mod p) frogatzeko, bi kasu hartu behar ditugu kontuan: m ≡ 0 (mod p) eta m $\not \equiv$ 0 (mod p).

Lehenengo kasuan, m p-ren multiploa da; beraz, m^ed ere.

Bigarren kasuan,

$m^{ed}=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}}$

non Fermaten teorema txikia erabiliz, m^p−1 mod p ordeztu dugu 1-egatik.

m^ed ≡ m (mod q) berdin frogatzen da, m ≡ 0 (mod q) eta m $\not \equiv$ 0 (mod q) bakoitza bere aldetik frogatuz.

Lehenengo kasuan, m^ed q-ren multiploa da; beraz, m^ed ≡ 0 ≡ m (mod q).

Bigarren kasuan,

$m^{ed}=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}}$

Honela egiaztatzen da edozein m, e eta d zenbaki oso hartuta eta $ed\equiv 1{\pmod {\phi (pq)}}$ betetzen bada,

$\left(m^{e}\right)^{d}\equiv m{\pmod {pq}}$

"Padding"

RSA aurkako erasoak

• Esponente txikiak erabiltzen direnean zifratzean (e.g., e = 3) eta $m$ zenbakia; hau da, zifratu beharreko edukiaren zenbakizko balioa, txikia denean, $m$^$e$ zenbakiak hartuko duen balioa $n$ gako publikoarena baino txikiagoa izatea gerta liteke. Kasu honetan, testu zifratua erraz itzul daiteke honen zenbakizko balioa erro $e$ eginez eta ondoren zenbaki osoengatik zatituz.
• Zifratutako testu berdina $e$ jasotzaileri edo gehiagori bidaliz gero, eta jasotzaile denek $e$ esponente berdina badute, $p$ eta $q$ 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, 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, $r$ 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, $e$ berretzaile bat izanik modulo $n$, eta $c$ zenbaki bat emanik, $m$ zenbaki bat lortzean datza, non, c ≡ m^e (mod n). Arazo honi aurre egiteko modurik eraginkorrena $n$ zenbakia faktorizatzea da, behin faktore lehenak izanik, erasotzaile batek kalkula dezake $d$ exponente bat gako publikoaz baliatuta, $d$ 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 $n$ faktorizatzea, ez da hain eraginkorra $n$ handietarako, beraz bi hauek konbinatuz apurtzeko oso zaila den kriptosistema bat eraiki daiteke.

Gako akasdunak

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

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

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

Ausazko zenbaki ekoizte algoritmo on baten garrantzia

Kriptografikoki ona den ausazko zenbaki ekoizle (RNG, Random number generator) bat erabili behar da $p$ eta $q$ 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 $d$ exponente pribatua zehaztasun askorekin bornatzea. Mota honetako arazoak ekiditeko era bat, konputadoreari beti denbora berdina ($d$ edozein izanik beharko zuen denbora maximoa) erabiltzeko programatzea da.