RSA

Wikipedia, Entziklopedia askea
Hona jauzi: nabigazioa, Bilatu

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

Historia[aldatu | aldatu iturburu kodea]

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 | aldatu iturburu kodea]

RSA Gakoen kalkulua[aldatu | aldatu iturburu kodea]

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 | aldatu iturburu kodea]

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 | aldatu iturburu kodea]

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 | aldatu iturburu kodea]

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 | aldatu iturburu kodea]

  • 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 | aldatu iturburu kodea]

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 | aldatu iturburu kodea]

Zenbaki konposatuen faktorizazioa eta RSA problema[aldatu | aldatu iturburu kodea]

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

Gako akasdunak[aldatu | aldatu iturburu kodea]

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 | aldatu iturburu kodea]

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 | aldatu iturburu kodea]

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 | aldatu iturburu kodea]

  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.