Zenbaki lehenak, sekretuak eta etorkizun ziurgabea

Komunikazio digitalaren garaian, etengabe gabiltza mezuak eta datuak alde batetik bestera bidaltzen. Hauek sarean modu seguruan bidaltzeko erabiltzen diren algoritmoentzat zenbaki lehenak eta haien propietateak ezinbestekoak dira. Ordenagailu kuantikoen etorrerak, halaber, kolokan jarri lezake orain arte matematikek bermatu diguten segurtasuna.

Medikuarekin hitzordua eskatu, bankuko kontu korrontetik transferentzia bat egin, lagunei Whatsapp bat bidali... Zaila da gaur egungo gizartea komunikazio digitalik gabe ulertzea. Erosotasun gorena ipar, teknologia berriek mundu birtualera migratu dituzte gure egunerokotasuneko behar gehienak.  Abantaila ugari eskaintzen badizkigute ere, errealitate ukiezin honen erabiltzaile izateak badu bere alde iluna ere: segurtasun neurririk hartu ezean, gure datu pertsonalak okerreko eskuetan eror daitezke.

Informazio konfidentziala partekatzeak dakarren arriskua, ordea, ez da gauza berria. Antzinaroan, gutun bat bidaltzen zenean etsaiak mezularia bidean atzemanez gero eskutitzaren nondik norakoak agerian geratu eta publiko bihurtzen ziren. Halakoak saihesteko teknika ugari garatu behar izan ziren: tinta ikusezinez idatzitako gutunak edota aurretiaz elkarbanatutako kode sekretuan idatzitakoak, besteak beste. Horra hor kriptografiaren jaiotza: begi bistan dagoena ezkutatzearen artea.

Baten batek pentsa lezake ezin dela konplikatuegia izan sistema kriptografiko seguru bat ezartzea, azken finean, aurretiaz elkarbanatutako kode sekretu bat erabiliz gero, esku okerretan eroritako edozein mezu ulergaitz izango zaio irakurle arrotz orori. Baina arrazoiketa honek arazo potolo bat du: nola elkarbanatuko zenuke kode sekretu hori beste pertsonarekin hasiera batean? Saretik bidaliz gero, hau atzematzen duen edonor izango da gai atzetik datorren mezu edo informazio “sekretu” oro deszifratzeko…

Dilema honi aurre egiteko sistema kriptografiko asimetrikoak garatu behar izan ziren, non giltza publiko eta giltza pribatu kontzeptuak erabiltzen diren. Sistema hauen berezitasuna honakoa da: nahiz eta hirugarren batek bi entitateren artean bidalitako mezu guztiak atzeman, elkarren arteko komunikazioa deszifratzea konputazionalki ezinezkoa da.¹  Komunikabide digital modernoak sortu zirenetik erabili diren punta-puntako algoritmo kriptografikoak mota horretakoak izan dira.

Algoritmo Kriptografikoak

Ordenagailuek oraindik tinta ikusezina erabiltzen ikasi ez dutenez, beste metodo eta algoritmo batzuk erabili behar dira komunikazio digitala modu seguruan gauzatzeko. Makinen erraiek zero eta bat zenbakiak soilik digeri ditzazketenez, zifratu-sistema orok matematikarien gidaliburuetatik edan behar du. Gaur egun gehien erabiltzen diren algoritmoak bi dira: RSA eta AES izenez ezagutzen direnak. Bi horien atzean ezkutatzen diren ideia matematikoak zeharo desberdinak dira: lehenak aritmetika modularraren eta zenbaki lehenen inguruko trikimailuak darabiltza, eta bigarrenak, aldiz, gorputz finituak zein polinomio laburtezinak. Hala ere, ezaugarri bat dute amankomunean: baliatzen dituzten ideia matematikoak inolako aplikazio praktikorik bilatu gabe garatu ziren duela ehun urte baina gehiago, helburutzat zenbakien propietate aberatsak ezagutzea besterik ez zuten pentsalarien eskutik. Hemendik aurrera, artikuluaren izenburutik antzemango zenuenez, RSA (Rivest-Shamir-Adleman, sortzaileen omenez) algoritmoari buruz hitz egingo dugu. Horregatik, aurrera egin baino lehen, ekar dezagun gogora zenbaki lehen bat zer den, gaurko protagonista nabarmenak baitira.

Zenbaki oso bat lehena dela diogu, baldin eta haren zatitzaile bakarrak bat zenbakia eta huraxe bera badira.² Adibidez, 7 eta 19 zenbakiak lehenak dira, baina 15, 22 eta 91 zenbakiak, ordea, ez, zeren eta 15=3 x 5, 22=2x11 eta 91=7x13. Askotan esan ohi da zenbaki lehenak gainontzeko zenbakiak sortzeko erabiltzen diren adreiluak direla.

1. Irudia: Arrosa kolorez, 1 eta 100 zenbakien tartean dauden zenbaki lehen guztiak.

Ikuspuntu matematikotik ezaugarri interesgarri ugari dituzte zenbaki lehenek, eta alor zein azpidisziplina askotan erabiltzen dira. Bereziki garrantzitsuak dira aritmetika modularra deritzogun disziplinan, non talde-teoria eta zenbaki-teoriaren arteko zubi gisa jokatzen duten. RSA algoritmoaren bigarren zutabe kontzeptuala, hain zuzen ere, aritmetika modularrari dago lotuta.

Askotan esan ohi da aritmetika modularra erlojuarekin zenbatzea besterik ez dela. Goizeko 9ak badira eta 20 ordu beranduago zer ordu den jakin nahi badugu, burutu beharreko eragiketa ez da 9+20=29, baizik eta (9+20)-24=5 (hau da, goizeko bostak). Adibide korapilatsuago bat: eguerdiko hamabiak badira, zer ordu izango da 145 ordu pasatzen direnean? Ba nahikoa da 145 hori 24rekin zatitzea eta hondarra zein den begiratzea: 145 = 24x6+1. Horrela, badakigu denbora guzti hori pasatakoan eguerdiko ordu bata izango dela.

Orduen kasuan zatiketak 24 zenbakiarekin egiten ditugu, egunak beste horrenbeste ordu baititu, baina beste edozein zenbaki erabil daiteke oinarri gisa. Esaterako, asteko egunen kasuan oinarria 7 zenbakia izango da. Hemen adibidea: gaur astelehena bada, zer egun izango da 100 egun barru? Ba 100=14 x 7+2 denez, bi egun gehitu behar dizkiogu astelehenari, eta asteazkena izango da bilatzen dugun eguna. Idazkera matematikoan honela adieraziko genituzke aipatutako adibideak:

Oinarria zenbaki lehena bada, aritmetika modularrak ezaugarri berezi asko dauzka. Ezaugarri horietatik adierazgarriena ziurrenik Fermaten Teorema Txikia da, eta RSA algoritmoarentzat ezinbestekoa da. Xehetasun gehiago emateak ur sakonagoetan sartzera behartuko gintuzkenez, aurrera egingo dugu RSA algoritmoaren nondik norakoekin.

RSA: Biderketak eta Deskonposaketak Ordenagailuen Munduan

Demagun entitate handiren batek (banku batek, esaterako) bere bezeroekin modu seguruan elkarbanatu nahi duela informazioa. Horretarako bankuak, sekretuan, bi zenbaki lehen aukeratzen ditu: p eta q. Bankuarentzat ezinbestekoa da p eta q publikoak ez izatea, eta ahal dela, zenbaki oso handiak izatea (geroz eta handiagoak, orduan eta seguruagoa izango da sistema kriptografikoa. Pentsa bizitza errealean zenbaki hauek ia ehundaka zifra luze direla!). Ondoren, bankuak bi zenbaki horiek biderkatzen ditu, zenbaki are handiago bat eskuratuz, n = p x q. Eragiketa hori burutzea nahiko lan erraza da, izan ere, ordenagailuak ikaragarri onak dira zenbakiak biderkatzen. Berdin du zeinen handiak diren biderkatu nahi diren zenbakiak, ordenagailuek duten efizientzia ezin hobea da.

Ostera, bankuak zenbaki berezi bat kalkulatu behar du: n-ren Carmichael zenbakia, C(n).³ Izen xelebre xamarra edukitzeaz gain, ezaugarri garrantzitsu pare bat ditu C(n) zenbaki honek:

1. n=p x q bada, non p eta q bere faktore lehenak diren, orduan C(n)=MKT(p-1,q-1), non MKT siglak “multiplo komun txikiena” esanahia duen. Eragiketa hori burutzea lan erraza da ordenagailuentzat. Bankuak p eta q ezagutzen dituenez, erraz kalkula dezake C(n) zenbakia.

2. n-ren faktore lehenak ezagutzen ez baditugu, C(n) kalkulatzeko existitzen diren algoritmoak ez dira batere eraginkorrak, oso mantsoak dira oro har. Gainera, n zenbakia geroz eta handiagoa bihurtu, C(n) kalkulatzeko behar den denbora esponentzialki hazten da.

Behin C(n) zenbakia kalkulatuta, bankuak harekiko lehena ⁴ den zenbaki bat aukeratzen du, dei dezagun e. Azkenik, oinarri gisa C(n) erabiliz e zenbakiaren alderantzizko modularra kalkulatzen du bankuak, hau da:

Azken bi paragrafoak irakurri ondoren zorabioak jota bukatu baduzu, lasai, guztiz normala da. Ez da nire asmoa pauso guzti hauen atzean dagoen logika xehetasun osoz azaltzea, baizik eta gure bizitzetan hain oinarrizko bihurtu den zeozertan zenbaki lehenen eta aritmetika modularraren garrantzia azpimarratzea. 

Jarrai dezagun algoritmoaren funtzionamenduarekin. Bankuak n eta e zenbakiak lau haizetara zabaltzen ditu: hauek dira bankuaren giltza publikoak. Bestalde, bankuak h zenbakia isilpean gordeko du: ezinbestekoa zaio hau inorrekin ez elkarbanatzea . Horixe izango da bankuaren giltza pribatua.

Demagun orain bezero batek mezu bat bidali nahi diola bankuari, transferentzia agindu bat emateko edo. Horretarako, lehenik eta behin mezua zenbaki bihurtzen da, protokolo estandar publiko baten bidez. Abstrakzio hauek zehatzagoak bihurtzearren, demagun “Bidali 200€ Pepitori ” mezuari protokolo hauetako batek M=1782750245738892 zenbakia esleitzen diola. Protokolo hauek alderantzikagarriak dira: testu bat emanda zenbaki bat sortzen dute, eta zenbaki bera emanez gero hasierako testua berreskuratzen dute. Beraz, M oraindik ez dago zifratuta/enkriptatuta, izan ere edonork berreskura dezake hasierako testua. Hortaz, bezeroak mezu hori enkriptatu beharko du, bankuaren (n,e) giltza publikoa erabiliz. Horretarako hurrengo eragiketa burutuko du:

Irakurleren batek pentsa lezake M^e zenbaki erraldoia kalkulatu beharko litzatekela lehenik eta gero modulu n kalkulatu. Zorionez, “berreketa modular azkarra”-ren bitartez ordengailuek segituan eskura dezakete eragiketa honen emaitza. Zenbaki berri hau da bezeroak bankuari bidaliko dion mezua. Testuak zenbaki eta zenbakiak testu bihurtzen dituen protokoloari zenbaki berri hau emanez gero lortuko dugun testua letra anabasa ulergaitza izango da ziurrenik. Bankuak mezua desenkriptatzeko burutu beharreko eragiketa honakoa da, zeinetarako h zenbakia ezagutu behar den:

Horrela, giltza pribatua daukanak soilik berreskura dezake bezeroak bidali nahi duen mezua. Gaizkile edo kuxkuxeroren bat saia daiteke h giltza sekretua zein den asmatzen. Horretarako, ordea, C(n) zenbakia ezagutzea beharrezkoa da, eta horretarako, aldi berean, n deskonposatu beste aukerarik ez da geratzen. Baina lehenago aipatu bezala, n zenbakia ehundaka zifra luze denean, gaur egungo ordenagailuentzako ezinezkoa da egiteko hori burutzea.

2. Irudia: RSA sistema kriptografikoa laburbiltzen duen diagrama.

Baina zer da “ezinezkoa” hitz horren atzean dagoena? Ez da deskonposaketa egitea matematikoki ezinezkoa denik, baizik eta denboran ezinezkoa bihurtzen dela. Izan ere, gaur egun erabiltzen diren konputagailu klasiko batek milioika urte beharko lituzke zenbaki handi baten faktore lehenak aurkitzeko.

Hortxe dago gaur egungo kriptografia digitalaren mami guztia: zenbakiak biderkatzea oso erraza da konputagailuentzat, baina zenbaki konposatu bat faktore lehenetan deskonposatzea ikaragarri zail bihurtzen da hauen tamaina hazten hasi ahala. Eta faktore lehenak ezagutu gabe, Carmichaelen funtzioa kalkulatzeko milioika urte beharko lituzke gaur egun existitzen den ordenagailu aurreratuenak ere!

Horrexegatik da sistema kriptografikoa asimetrikoa: bankuarentzat oso erraza da p eta q zenbakiak biderkatzea, baina alderantzizko prozesua burutzea, hau da, biderketaren emaitza deskonposatzea,  konputazionalki ezinezkoa da. Faktu hau ez da oso intuitiboa hasiera batean: egunerokotasunean erabiltzen ditugun zenbaki txikiekin ez dirudi zailtasun desberdintasun handiegirik dagoenik 3 x 5=15 edo 21=7 x 3 eragiketak burutzean. Hala ere zenbakiak geroz eta handiago bilakatu, orduan eta ageriagoa da zein zail bihurtzen den bigarren kasua lehenengoarekin alderatuta.

Horrela, egunerokoan, gure bizitza digitalaren segurtasuna zenbaki lehen erraldoien atzean dago: ehundaka digitu dituzten zenbaki horiek bihurtzen dira gure pasahitz, transakzio eta sekretuen atezain.

Ordenagailu Kuantikoen Etorrera

Azken urteotan gero eta gehiago hitz egiten da ordenagailu kuantikoei buruz. Bai telebistan, bai sare sozialetan maiztasun handiagoarekin entzuten da hango enpresa horrek edo beste honek ordenagailu kuantiko prototipo berria kaleratu duela. Agian behar lukeen baino hauspo gehiago jaso du teknologia berritzaile honek, baina, nahiz eta oraindik esperimentazio fasean badago ere, aitortu beharra dago paradigma aldaketa bat ekar lezakeela, bai konputazio munduan, bai kriptografian.

Ordenagailu kuantiko bat zer den azaltzea eta gaur egun dauzkagunekiko dituen desberdintasunak plazaratzea ez da lan makala. Zorionez, hemengo artikulu honetan jada azaldu genituen gai honen oinarrizko kontzeptuak.

Arazoa (ala abantaila?) zera da: Qubitak erabiliz zenbait eragiketa matematiko ohiko ordenagailuek baino askoz azkarrago burutu ditzakete ordenagailu kuantikoek. Eragiketa horien artean, hain zuzen ere, zenbakien deskonposaketa lehena dago. 1994. urtean Peter Shor ikerlari amerikarrak zenbakien faktorizaziorako algoritmo kuantiko bat diseinatu zuen , Shor-en algoritmo deritzona (etorkizun batean hitz egingo dugu sakonago honi buruz). Oraingoz, existitzen diren ordengailu kuantikoek ez dute “potentzia” nahikorik hain zenbaki handiak deskonposatzeko, baina denbora kontua izan liteke prototipo aurreratuagoren batek aurrepausoa eman eta RSA kriptosistema agerian uztea.

3. Irudia: Ordenagailu kuantiko bat

Horregatik, azken urteotan ikerketa eta diru ugari bideratu da kriptografia post-kuantikoa deritzon arlora. Helburua argia da: algoritmo berriak garatzea, konputazio kuantikoaren abantailak baliatuta ere haustea ezinezko izango direnak. Oraindik ez dago “irabazle” argirik, baina nazioarteko estandarizazio-prozesuak martxan daude, eta etorkizunean gure segurtasuna bermatuko duten tresnak ziurrenik gaur egun ikertzen ari diren horietatik sortuko dira.

Laburbilduz, historia errepikatu egiten da nolabait: antzina tinta ikusezina edo kode sekretuak asmatu ziren mezulariak engainatzeko, gaur egun zenbaki lehenak baliatzen dira gure datuak babesteko, eta bihar, agian, bestelako egitura matematikoak izango dira segurtasun digitalaren zutabe. Ziurgabetasuna handia bada ere, argi dago matematika beti izango dela joko honetan giltzarri nagusia.

Orri Oinak

1.Aurrerago azalduko da “ezinezkoa” hitzak zer esan nahi duen esaldi honetan

2.Bat zenbakia ez da lehena kontsideratzen, nahiz eta emandako definizioa betetzen duen.

3.Definizio zehatza nahi duenak ikus bedi link hau

4.Bi zenbaki elkarrekiko lehenak direla diogu heuren arteko zatitzaile komun handiena (zkh) 1 zenbakia bada.