RSA

RSA 1977 urtean Ronald Rivest, Adi Shamir eta Leonard Adlemanek sortu zuten kriptografia-sistema edo zifratze-sistema da. Oso zifratze-sistema segurua da eta zenbaki-teorian oinarritzen da. Berezia da publikoa den gako bat erabiltzen duelako. Erabiltzaile bakoitzak bi zifratze-gako ditu: bata publikoa eta bestea pribatua. Mezuak zifratuta jaso nahi dituen pertsonak bere gako publikoa beste edonori pasatzen dio, baina mezu zifratu 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 mezuetan zenbakiak agertzen dira letren ordez. Zifratzearen funtzionamendua ausaz aukeratutako bi zenbaki lehen handi (gutxienez 100 digitu) lortzean datza, mezua zifratuta bidali dadin. Uste da RSA segurua izango dela zenbaki handi bat lehenen produktuan deskonposatzeko modu azkarrak ezagutzen ez diren bitartean.

Historia

1976. urtean Whitfield Diffie eta Martin Hellman ikerlariek, gako publiko eta gako pribatu asimetrikoan (hau da, bi gako ezberdin, non bat izateak ez duen bestearen informaziorik ematen) oinarritutako kriptosistemaren kontzeptua asmatu zuten. Zenbaki teoria aplikatuz zifratze-sistema eraginkor bat sortzen saiatu ziren aritmetika modularra erabiliz. Funtzionatzen zuen zifratze-sistema bat lortzetik hurbil geratu baziren ere, ez zuten lortu noranzko bakar batean zuzendua dagoen funtzio bat formulatzea; gako publikoaz gako pribatua lortzea posiblea zen.

Ron Rivest, Adi Shamir eta Leonard Adleman MIT-ko ikerlariak urtebetez aritu ziren noranzko bakar batean zuzendua dagoen eta kontrako noranzkoan erabiltzea zaila den funtzio baten bila. Gogor saiatu ondoren, ezinezkoa zela pentsatzen hasiak zirela, Rivest 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 algoritmoa deritzo.

Funtzionamendua

Funtzionamenduaren adibidea

RSAren funtzionamenduaren ideia hurrengoa da: igorleak giltzarrapo bat irekita duen kutxa bat bidaltzen dio hartzaileari, eta igorleak bakarrik du giltza. Hartzaileak kutxa jaso, mezua idatzi, kutxan jarri eta giltzarrapoarekin ixten du (orain hartzaileak ezin du mezua irakurri). Hartzaileak kutxa igorleari bidaltzen dio eta giltzaz irekitzen du. Adibide honetan, giltzarrapodun kutxa igorlearen “gako publikoa” da, eta giltzarrapoaren giltza haren “gako pribatua” da.

RSA Gakoen kalkulua

RSA zifratze-sistema gako publiko eta pribatu asimetrikoetan oinarrituta dago. Gako publikoa, $(n,e)$, zifratu gabe bidaltzen da, edonork ikusteko moduan. Bidaltzaileak bidali beharreko mezua gako publiko hori erabiliz zifratzen du eta gako pribatua $(d)$ duen hartzaileak deszifratuko du, berak eta ez beste inork lortuko duelarik bidaltzaileak igorritako informazioa deszifratzea. Mezu zifratua eta gako publikoa ikusi dituzten gainerakoek ezin izango dute mezua deszifratu praktikoa litzatekeen denbora epe batean, beti ere RSA gakoak nahiko handiak badira. Zenbaki handiak faktorizatzeak duen zailtasunagatik gertatzen da hori, eta horretan datza, hain zuzen ere, RSA algoritmoaren segurtasuna.

RSA gakoak kalkulatzeko urratsak honakoak dira:

1. Bi zenbaki lehen $p$ eta $q$ desberdin aukeratu. Segurtasun arrazoiengatik, zenbaki handiak aukeratzea gomendatzen da (100 digitutik gorakoak).
2. $n=p\cdot q$ kalkulatu.
3. $\phi (pq)=\phi (n)=(p-1)\cdot (q-1)\,$ kalkulatu.
4. $\phi (n)$-rekin lehen erlatiboa den, hau da, $zkh(\phi (n),e)=1\,$betetzen duen $e$ kalkulatu.
5. $d={e}^{-1}{\pmod {\phi (n)}}\,$ kalkulatu, hau da, $e$-ren alderantzizkoa modulu $\phi (n)$.

Gako publikoa: $(n,e)$, gako pribatua: $(d)$.

Zifratzea

Bidaltzaileak bidali beharreko mezua zifratu aurretik, derrigorrez karaktereak zenbaki bihurtu behar ditu. Horretarako, aukera ezberdinak existitzen badira ere, ASCII kodeketa erabili ohi da. Kodeketa horren arabera, alfabeto latinoko Atik Zrako hizki larriak 65etik 90erako kodeen bidez adierazten dira eta hizki xeheak 97tik 122ra bitarteko kodeen bidez. Testuetan agertu ohi diren gainerako karaktereek ere (zenbakiek, ikurrek, ...) badute beren ASCII kodea esleituta. Kodeketa prozesuaren ondorioz lortzen diren kodeak $X$ notazioaz adierazten dira aurrerantzean.

Behin mezua kodetu denean, zifratze-prozesua hasten da. RSA algoritmoaren arabera, $X$ kodea zifratzea $(n,e)$ gako publikoa erabiliz honako eragiketa egitea da:

$E={X}^{e}{\pmod {n}}.$

Berreketa berreketa modular horren emaitza den $E$ da zifratutako X. Kode guztiak modu berean zifratuz lortuko du bidaltzaileak mezu zifratua osatzea.

Deszifratzea

Mezua deszifratzea kontrako prozesua aplikatzea da. Hartzaileak mezu zifratua jasotzen duenean, $E$ deszifratu beharko du dagokion $X$ kodea berreskuratzeko. RSA algoritmoaren arabera, $E$ deszifratzea $(d)$ gako pribatua erabiliz honako berreketa modularra egitea da:

$X={E}^{d}{\pmod {n}}.$

RSA zifratze-sistema oso sinplea izateaz gain, oso segurua da gakoak nahiko handiak badira. $n$ gako publikoa 200 digitutik gorako bada, bera faktorizatzea ia ezinezkoa gertatzen da gaur egun; ezkutuan geratzen dira $p$ eta $q$ balioak, eta babestuta $(d)$ gako pribatua. Ondorioz, hartzailea eta ez beste inor izango da mezua deszifratu ahal izango duen bakarra.

Prozesua amaitzeko, $X$ kodeak deskodetu besterik ez da egin beharko; kode bakoitzari dagokion karakterea lortuz bidaltzaileak bidalitako jatorrizko mezua berreskuratuko da.

RSA-ren froga

RSA-ren froga Fermaten teorema txikian oinarritzen da. Teorema horren arabera, $p$ lehena bada eta $a$ osoa zatitzen ez badu, orduan:

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

Frogatu behar duguna zera da: $p$ eta $q$ bi zenbaki lehen desberdin izanik eta $e$ eta $d$ positiboetarako

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

betetzen bada, orduan

$m^{ed}\equiv m{\pmod {pq}}$

betetzen dela ($m^{ed}$ eta $m$ kongruenteak direla ${\pmod {pq}}$). Horrela, frogatuta geratuko da $m$ kodea $e$ gako publikoarekin zifratu ondoren $d$ gako pribatuarekin deszifratzean jatorrizko $m$ kodea berreskuratzen dela. $\phi (pq)=(p-1)(q-1)$ denez,

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

idatz daiteke, $h$ zenbaki oso ez negatiboa izanik.

$m^{ed}\equiv m{\pmod {pq}}$ frogatzeko, nahikoa da $m^{ed}\equiv m{\pmod {p}}$ eta $m^{ed}\equiv m{\pmod {q}}$ modu independentean frogatzea.

$m^{ed}\equiv m{\pmod {p}}$ kongruentziaren froga. Bi kasu hartu behar dira kontuan:

$m\equiv 0{\pmod {p}}\quad$ eta $\quad m\not \equiv 0{\pmod {p}}$

Lehenengo kasuan, $m$ balioa $p$-ren multiploa denez, $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$

Fermaten teorema txikia erabiliz, $m^{p-1}{\pmod {p}}\equiv 1{\pmod {p}}$ denez, $m^{p-1}$ balioa $1$ balioaz ordezka dezakegu.

$=\left(m^{p-1}\right)^{h(q-1)}m\equiv 1^{h(q-1)}m\equiv m{\pmod {p}}$

$m^{ed}\equiv m{\pmod {q}}$ kongruentziaren froga modu berean egiten da.

$m\equiv 0{\pmod {q}}\quad$ eta $\quad m\not \equiv 0{\pmod {q}}$

kasuak hartu behar dira kontuan.

Lehenengo kasuan, $m$ balioa $q$-ren multiploa denez, $m^{ed}$ ere: $m^{ed}\equiv 0\equiv m{\pmod {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}}$

Frogatuta geratzen da $m$, $e$ eta $d$ zenbaki osoak izanik, $ed\equiv 1{\pmod {\phi (pq)}}$ betetzen bada,

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

betetzen dela, hau da, zifratutakoa deszifratuz jatorrizko $m$ berreskuratzen dela.

RSA aurkako erasoak

• Zifratzeko erabilitako gako publikoa txikia denean (e=3 berretzailea, esaterako) eta zifratu beharreko $m$ zenbakizko balioa ere txikia denean, $m$^$e$ balioa $n$ gako publikoa baino txikiagoa izatea gerta liteke. Kasu horretan, testu zifratua erraz deszifra daiteke erro $e$ eginez eta ondoren zenbaki osoengatik zatituz.
• Zifratutako mezu bera $e$ hartzaileri edo gehiagori bidaliz gero, eta hartzaile guztiek $e$ berretzaile bera badute, $p$ eta $q$ zenbaki lehen ezberdinak izanik, Hondarraren Teorema Txinatarra erabiliz mezu zifratua erraz deszifra daiteke. Testu zifratu berbera ez balitz ere, erasoa arriskutsua litzateke, beti ere testuen arteko erlazio lineala balego.
• RSA zifratzea guztiz determinista denez, hau da, behin zorizko bi zenbaki lehenak hautatu direnean algoritmoak zorizko osagairik ez duenez, erasotzaileak bidalitako testuak duen eduki bera duen testu bat gako berberaz zifratzen badu, zifratutako testua berdina izango da. Beraz, konparaketa bat eginez baiezta daiteke igorleak bidalitako testua erasotzaileak punturen batean zifratu duen testuaren berdina dela. Baina, zifratze-sistema bat semantikoki segurua dela esateko, testu beraren edozein bi zifratzek desberdinak izan behar dute. RSA ez da berez semantikoki segurua, baina "Padding" teknikak erabiliz posible da kriptosistemak ezaugarri hori bereganatzea.
• RSA kriptosistemaren funtsezko ezaugarri bat honakoa da: gako berak erabiliz gero, bi testu zifraturen zenbakizko balioen biderkadura eta jatorrizko testuen zenbakizko balioen biderkaduraren zifratzea berdinak dira. Erasotzaileak gako pribatua duen hartzailearen mezu bat deszifratzea lortzen badu eta mezu hori deszifraturik itzultzea lortzen badu, gako ezberdin batekin zifratutako testu bat bidal diezaioke erasotzaileak hartzaileari deszifra dezan eta testua deszifratua bueltan jasotzerakoan, erasotzaileak edozein mezu deszifratzeko adina informazio lortuko du RSAren ezaugarri honegatik.

"Padding" Teknika

Azken bi arazo horiek saihesteko asmoz, ohikoa da RSA jatorrizko testuaren zenbakizko kodeketarekin zoriz aukeratutako zenbaki batekin eragiketaren bat egitea zifratu aurretik. Ondoren, jatorrizko testua berreskuratzeko aurkako eragiketa egitea nahikoa izango da. Hori eginez gero, testuaren zenbakizko balioak seguruak direla bermatuko da.

Segurtasuna

Zenbaki konposatuen faktorizazioa eta RSA problema

RSA kriptosistemaren segurtasuna bi problema matematikotan oinarrituta dago: zenbaki konposatu handien faktorizazioaren problema eta RSA problema. RSA algoritmoaz zifratutako testua gako pribatua ezagutu gabe deszifratzea ezinezkotzat jotzen da, aipatutako bi problemen ebazpena oso zaila baita. Gainera, ez dago nahiko eraginkorra den algoritmo bat gako handiez zifratuta dagoen testu bat denbora tarte praktikoan deszifratzeko.

RSA problema, $e$, $n$ eta $c$ zenbakiak ezagunak izanik, $m$ zenbaki bat lortzean datza, non, $c\equiv m^{e}{\pmod {n}}$ beteko den. Problema hori ebazteko modurik eraginkorrena $n$ zenbakia faktorizatzea da. Behin $p$ eta $q$ faktore lehenak izanik, erasotzaileak $d$ berretzaile bat (gako pribatua) kalkula dezake gako publikoa erabiliz, eta harekin erasotzaileak testu zifratua erraz deszifra dezake ohiko prozedura erabiliz.

$n$ nahiko handia bada, RSA algoritmoa segurua da (gaur egun 2048 bitekoa izatea gomendatzen da). $n$ zenbakia faktorizatzea ezinezkoa izateko zein tamainakoa izan behar duen neurtzeko asmoz sortu zen, hain zuzen ere, RSA faktorizazio-lehia.

Gako akasdunak

$n$ lortzeko erabilitako $p$ eta $q$ balioak ezin dira "hurbil" egon ( $p-q>2n^{1/4}$ bete behar da). Bestela, Fermaten faktorizazioa erabiliz ez litzateke zaila izango $p$ eta $q$ aurkitzea $n$ jakin batentzako. Beraz, baldintza hori betetzen ez duten $p$ eta $q$ bikoteak baztertu behar dira.

$(p-1)$ zenbakiak edo $(q-1)$ zenbakiak faktore oso txikiak baino ez badituzte, bizkor kalkula daitezke $p$ eta $q$, Pollarden $p-1$ algoritmoa erabiliz; halako $p$ eta $q$ zenbaki lehenen bikoteak ere baztertu behar dira.

Oso garrantzitsua da $d$ berretzailea (gako pribatua) nahikoa handia izatea ($d>n^{1/4}/3$). Horrela izan ezean eta $q<p<2q$ betetzen bada, $d$ gako pribatua era eraginkorrean kalkula daiteke $e$ eta $n$ gako publikoetatik.

Ausazko zenbakiak ekoizteko algoritmo on baten garrantzia

Kriptografikoki ona den ausazko zenbaki ekoizle (RNG, Random Number Generator) bat erabili behar da $p$ eta $q$ zenbaki lehenak hautatzeko. Horrez gain, hazia (RNG algoritmo batean sasiausazko zenbakiak kalkulatzeko erabiltzen den zenbakia) ere ahalik eta modu zorizkoenean lortu behar da.

Pausu hori zuzen ez egiteak RSA kriptosistemarekin zerikusirik ez duten erasoak agertzea ahalbidetzen du, RNG algoritmoaren iragargaitasuna erasotuz, alegia.

Denbora-erasoak

Erasotzaileak hartzailearen konputagailuaren ezaugarriak ezagutuko balitu eta mezu bat deszifratzeko beharko duen denbora kalkulatzeko gai izango balitz, $d$ gako pribatua kalkulatu ahal izango luke. Horrelako arazoak ekiditeko era bat konputagailuari beti denbora bera erabil dezan programatzea da.

Kanpo estekak

• Datuak: Q181551