From Wikipedia, the free encyclopedia
RSA 1977 urtean Ronald Rivest, Adi Shamir eta Leonard Adlemanek sortu zuten kriptografia-sistema edo zifratze-sistema da[1]. 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.
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.
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[2].
Gaur egun RSA kriptosistemako gakoak kalkulatzen dituen algoritmoari, RSA algoritmoa deritzo[3].
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 zifratze-sistema gako publiko eta pribatu asimetrikoetan oinarrituta dago. Gako publikoa, , zifratu gabe bidaltzen da, edonork ikusteko moduan. Bidaltzaileak bidali beharreko mezua gako publiko hori erabiliz zifratzen du eta gako pribatua 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[4].
RSA gakoak kalkulatzeko urratsak honakoak dira:
Gako publikoa: , gako pribatua: .
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 notazioaz adierazten dira aurrerantzean.
Behin mezua kodetu denean, zifratze-prozesua hasten da. RSA algoritmoaren arabera, kodea zifratzea gako publikoa erabiliz honako eragiketa egitea da:
Berreketa berreketa modular horren emaitza den da zifratutako X. Kode guztiak modu berean zifratuz lortuko du bidaltzaileak mezu zifratua osatzea.
Mezua deszifratzea kontrako prozesua aplikatzea da. Hartzaileak mezu zifratua jasotzen duenean, deszifratu beharko du dagokion kodea berreskuratzeko. RSA algoritmoaren arabera, deszifratzea gako pribatua erabiliz honako berreketa modularra egitea da:
RSA zifratze-sistema oso sinplea izateaz gain, oso segurua da gakoak nahiko handiak badira. gako publikoa 200 digitutik gorako bada, bera faktorizatzea ia ezinezkoa gertatzen da gaur egun; ezkutuan geratzen dira eta balioak, eta babestuta gako pribatua. Ondorioz, hartzailea eta ez beste inor izango da mezua deszifratu ahal izango duen bakarra.
Prozesua amaitzeko, kodeak deskodetu besterik ez da egin beharko; kode bakoitzari dagokion karakterea lortuz bidaltzaileak bidalitako jatorrizko mezua berreskuratuko da.
RSA-ren froga Fermaten teorema txikian oinarritzen da. Teorema horren arabera, lehena bada eta osoa zatitzen ez badu, orduan:
Frogatu behar duguna zera da: eta bi zenbaki lehen desberdin izanik eta eta positiboetarako
betetzen bada, orduan
betetzen dela ( eta kongruenteak direla ). Horrela, frogatuta geratuko da kodea gako publikoarekin zifratu ondoren gako pribatuarekin deszifratzean jatorrizko kodea berreskuratzen dela. denez,
idatz daiteke, zenbaki oso ez negatiboa izanik.
frogatzeko, nahikoa da eta modu independentean frogatzea.
kongruentziaren froga. Bi kasu hartu behar dira kontuan:
Lehenengo kasuan, balioa -ren multiploa denez, ere.
Bigarren kasuan,
Fermaten teorema txikia erabiliz, denez, balioa balioaz ordezka dezakegu.
kongruentziaren froga modu berean egiten da.
kasuak hartu behar dira kontuan.
Lehenengo kasuan, balioa -ren multiploa denez, ere:
Bigarren kasuan,
Frogatuta geratzen da , eta zenbaki osoak izanik, betetzen bada,
betetzen dela, hau da, zifratutakoa deszifratuz jatorrizko berreskuratzen dela.
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.
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, , eta zenbakiak ezagunak izanik, zenbaki bat lortzean datza, non, beteko den. Problema hori ebazteko modurik eraginkorrena zenbakia faktorizatzea da. Behin eta faktore lehenak izanik, erasotzaileak berretzaile bat (gako pribatua) kalkula dezake gako publikoa erabiliz, eta harekin erasotzaileak testu zifratua erraz deszifra dezake ohiko prozedura erabiliz.
nahiko handia bada, RSA algoritmoa segurua da (gaur egun 2048 bitekoa izatea gomendatzen da). zenbakia faktorizatzea ezinezkoa izateko zein tamainakoa izan behar duen neurtzeko asmoz sortu zen, hain zuzen ere, RSA faktorizazio-lehia.
lortzeko erabilitako eta balioak ezin dira "hurbil" egon ( bete behar da). Bestela, Fermaten faktorizazioa erabiliz ez litzateke zaila izango eta aurkitzea jakin batentzako. Beraz, baldintza hori betetzen ez duten eta bikoteak baztertu behar dira.
zenbakiak edo zenbakiak faktore oso txikiak baino ez badituzte, bizkor kalkula daitezke eta , Pollarden algoritmoa erabiliz; halako eta zenbaki lehenen bikoteak ere baztertu behar dira.
Oso garrantzitsua da berretzailea (gako pribatua) nahikoa handia izatea (). Horrela izan ezean eta betetzen bada, gako pribatua era eraginkorrean kalkula daiteke eta gako publikoetatik.
Kriptografikoki ona den ausazko zenbaki ekoizle (RNG, Random Number Generator) bat erabili behar da eta 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.
Erasotzaileak hartzailearen konputagailuaren ezaugarriak ezagutuko balitu eta mezu bat deszifratzeko beharko duen denbora kalkulatzeko gai izango balitz, gako pribatua kalkulatu ahal izango luke. Horrelako arazoak ekiditeko era bat konputagailuari beti denbora bera erabil dezan programatzea da.