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.

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, , 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.

RSA gakoak kalkulatzeko urratsak honakoak dira:

 Bi zenbaki lehen  eta  desberdin aukeratu. Segurtasun arrazoiengatik, zenbaki handiak aukeratzea gomendatzen da (100 digitutik gorakoak).
  kalkulatu.
  kalkulatu.
 -rekin lehen erlatiboa den, hau da, betetzen duen  kalkulatu.
  kalkulatu, hau da, -ren alderantzizkoa modulu .

Gako publikoa: , gako pribatua: .

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  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.

Deszifratzea 

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 
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:
 eta 

Lehenengo kasuan,  balioa -ren multiploa denez,  ere.

Bigarren kasuan,
 

Fermaten teorema txikia erabiliz,  denez,  balioa  balioaz ordezka dezakegu.

 

 kongruentziaren froga modu berean egiten da.
 eta 
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.

RSA aurkako erasoak 
 Zifratzeko erabilitako gako publikoa txikia denean (e=3 berretzailea, esaterako) eta zifratu beharreko  zenbakizko balioa ere txikia denean,  balioa  gako publikoa baino txikiagoa izatea gerta liteke. Kasu horretan, testu zifratua erraz deszifra daiteke erro  eginez eta ondoren zenbaki osoengatik zatituz.
 Zifratutako mezu bera  hartzaileri edo gehiagori bidaliz gero, eta hartzaile guztiek  berretzaile bera badute,  eta  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, ,  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.

Gako akasdunak 
 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.

Ausazko zenbakiak ekoizteko algoritmo on baten garrantzia 

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.

Denbora-erasoak 
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.

Erreferentziak

Kanpo estekak 

Algoritmoak
Kriptografia
Segurtasun informatikoa
Informatikako akronimoak