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.

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

aldatu

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

Funtzionamendua

aldatu

Funtzionamenduaren adibidea

aldatu

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

aldatu

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:

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

Gako publikoa:  , gako pribatua:  .

Zifratzea

aldatu

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

aldatu

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

aldatu

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

aldatu
  • 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[5], 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

aldatu

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

aldatu

Zenbaki konposatuen faktorizazioa eta RSA problema

aldatu

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

aldatu

  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

aldatu

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

aldatu

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

aldatu
  1. Smart, Nigel (February 19, 2008). "Dr Clifford Cocks CB". Bristol University. Retrieved August 14, 2011.
  2. Calderbank, Michael (2007-08-20). "The RSA Cryptosystem: History, Algorithm, Primes"
  3. Robinson, Sara (June 2003). "Still Guarding Secrets after Years of Attacks, RSA Earns Accolades for its Founders" (PDF). SIAM News. 36 (5).
  4. 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.
  5. 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.

Kanpo estekak

aldatu