Räsifunktsioon

Räsifunktsioon (inglise keeles hash function) on matemaatiline funktsioon, mis kujutab väärtusi suuremast (või lõpmatust) hulgast fikseeritud väiksema võimsusega lõplikku hulka.

Räsifunktsiooni kasutatakse assotsiatiivsete massiivide ülesehituseks, andmekogumite seeriates duplikaatide otsimiseks, unikaalsete identifikaatorite (andmekogumite jaoks) ülesehituseks, kontroll-liitmiseks kogemata või meelega pandud (säilimisel või ülekandmisel) vigade leidmise eesmärgil, ka kaitsesüsteemide paroolide säilitamiseks (sel juhul ligipääs sellele mälukohale, kus asuvad paroolid, ei lase taastada parooli ennast).

Üldjuhul ühemõttelist vastavust lähteandmete ning räsikoodi vahel pole seetõttu, et räsifunktsiooni tähenduste arv on väiksem kui sisendmassiivi variantide arv; on olemas palju massiive erineva sisuga, mis annavad samu räsikoode – siis on tegemist nn kollisioonidega. Kollisioonide tekkimise tõenäosus mängib suurt rolli räsifunktsioonide kvaliteedi hindamisel.

On olemas palju erinevate omadustega (arvutuse raskus, krüpteerimiskindlus jne) räsimisalgoritme. Ühe või teise räsifunktsiooni valik oleneb lahendatava ülesande eripärast.

 Ajalugu 

Donald Knuth peab esimese räsimissüsteemi idee autoriks IBM-i palgal olnud Hans Peter Luhni, kes pakkus välja kodeerimise räsimise abil jaanuaris 1953. Arnold Dumey esitas oma 1956. aasta töös "Arvutid ja automatiseerimine" esimesena räsimise kontseptsiooni sellisena, nagu enamik programmeerijaid seda tänapäeval tunneb. Dumey nägi räsimises "sõnaraamatu probleemi" lahendust ning pakkus välja idee kasutada räsiaadressiks algarvuga jagamise jääki.

Esimeseks tõsiseks tööks, mis tegeles otsimisega suurtest failidest, oli W. Wesley Petersoni 1957. aasta artikkel, milles ta käsitles avalikku adresseerimist ning osutas tootlikkuse halvenemisele kustutamisel. Kuus aastat hiljem avaldati Werner Buchholzi töö, milles on läbi viidud räsifunktsioonide põhjalik uurimine. Mitme järgmise aasta jooksul kasutati räsimist küll laialdaselt, kuid ei avaldatud ühtegi olulist uurimust.

1967. aastal mainis räsimist kaasaegses tähenduses Herbert Hellerman oma raamatus "Numbriliste arvutisüsteemide põhimõtted". 1968. aastal avaldas Robert Morris räsimisest põhjaliku ülevaate ning seda tööd peetakse võtmepublikatsiooniks, mis viis räsimise mõiste teaduskeelde ning kinnistas seni vaid spetsialistide argoos kasutatud terminit "räsi".

1990. aastate alguseni kasutati venekeelses kirjanduses tänu Andrei Jeršovi töödele termini "räsimine" ekvivalendina sõna "järjestus", ning kollisioonide jaoks kasutati terminit "konflikt". Tänapäeval on kasutusse jäänud vaid sõna "räsimine".

 Räsifunktsioonide liigid 
Hea räsifunktsioon peab vastama kahele tingimusele: 
 olema kiiresti arvutatav;
 minimeerima kollisioonide arvu.

Määratletuseks oletame, et võtmete arv on , ja räsifunktsioonil  on mitte rohkem kui  erinevaid tähendusi:

Halva räsifunktsiooni näitena võib tuua funktsiooni , mis kümnekohalisele naturaalarvule  vastastab kolm numbri  kahekümnenda ruudu keskelt valitud arvu. Tundub, et räsikoodide tähendused peaksid ühtlaselt jaotuma «000» ja «999» vahel, kuid reaalsete andmete jaoks sobib selline meetod vaid juhul, kui võtmetel pole suurt nullide arvu vasakul ja paremal.

On ka mitu lihtsamat ja kindlamat meetodit, mida kasutavad paljud räsifunktsioonid.

 Jagamisele rajatud räsifunktsioonid 
Esimene meetodi kohaselt kasutatakse räsina jagamise -ga jääki, kus  on kõikide võimalike räside arv:



Seejuures on selge, et paaris- puhul funktsiooni tähendus on ka paarisarvuline, paaris- puhul, ning paaritu – paaritu puhul, mis võib viia failiandmete olulise nihutuseni. Samuti ei tasu kasutada -na arvuti arvutamise aluse astet, kuna räsikood sõltub ainult  arvu mitmetest paremal asuvatest numbritest, mis viib suure kollisioonide arvuni. Praktikas tavaliselt valitakse hariliku (alg-)  – enamasti on selline valik täiesti rahuldav.

Veel tasuks mainida räsimise meetodit, mis on rajatud mooduliga kaks jagamisele polünoomile. Antud meetodi puhul  peab samuti olema kahe aste, ning binaarvõtmed () on kujutatud polünoomidena. Sel juhul räsikoodina võetakse tegurite tähendusi polünoomist, mis on saadud nagu jääk  jagamisest eelnevalt valitud polünoomiga  astmes :




Õigesti valitud  puhul tagab selline viis kollisioonide peaaegu sarnaste võtmete vahel puudumise. 

 Räsimise multiplikaatne skeem 
Teine meetod seisneb mingi terve konstandi , mis on vastastikult harilik -ga, valimises, kus  on masinsõna abil esindatavate tähenduste arv (IBM PC arvutites see on ). Siis võib võtta järgmist räsifunktsiooni:



Sel juhul on kahendsüsteemiga arvutil  kahe aste ning  koosneb korrutise  parempoolsetest vanematest bittidest.

Nende kahe meetodi eeliste hulgas tasub mainida, et nad kasulikul viisil kasutavad seda, et reaalsed võtmed pole juhuslikud, näiteks juhul, kui võtmed kujutavad endast aritmeetilist progressiooni (näiteks nimede «NIMI1», «NIMI2», «NIMI3» järjestust). Multiplikaatne meetod näitab aritmeetilist progressiooni kui erinevate räsitähenduste lähtestatud aritmeetilist progressiooni, mis vähendab kollisioonide arvu võrreldes juhusliku olukorraga.

Selle meetodi üks variatsioonidest on Fibonacci arvu räsimine, mis põhineb kuldlõike omadustel.  arvuna võetakse lähedasemat  arvule algarvu, mis on vastastikult harilik -ga.

 Muutliku suurusega ridade räsimine 
Eelpool mainitud meetodid on kasutatavad ka juhul, kui tegeletakse mitmest sõnast koosnevate või muutliku suurusega võtmetega. Näiteks võib kombineerida sõnad ühte  mooduliga liitmise või "välistav või" operatsiooni abil. Üks sel põhimõttel töötavaid algoritme on Pearsoni räsifunktsioon.

Pearsoni räsimine (inglise: Pearson hashing) on Peter Pearsoni pakutud algoritm 8-bitiste registritega protsessoritele, mille ülesandeks on suvalise suurusega rea jaoks räsikoodi kiire arvutus. Sisendile funktsioon saab sõna , mis koosneb  sümbolitest, igaüks 1 baiti suurusega, ning tagastab tähenduse diapasoonis nullist kuni 255-ni. Seejuures räsikoodi tähendus sõltub sisendsõna iga sümbolist.

Algoritmi saab kirjeldada järgmise pseudokoodiga, mis saab sisendile rida  ning kasutab vaheste tabeli 
 h := 0
 for each c in W loop
   index := h xor c
   h := T[index]
 end loop
 return h

Algoritmi eeliste hulgas tasub märkida:
 Arvutuse lihtsust; 
 Pole olemas selliseid sisendandmeid, mille jaoks kollisiooni tõenäosus on suurim; 
 Võimalikkus modifitseerida ideaalseks räsifunktsiooniks.

Võtmete , mis koosnevad  sümbolitest (), räsimise alternatiivse viisina võib välja pakkuda arvutust 
 .

 Ideaalne räsimine 
Ideaalseks räsifunktsiooniks (inglise: Perfect hash function) nimetatakse sellist funktsiooni, mis kujutab iga võtme  komplektist täisarvude hulka ilma kollisioonideta. Matemaatilistes terminites see on injektiivne kujutis.

 Kirjeldus 
 Funktsiooni  nimetatakse ideaalseks räsifunktsiooniks  jaoks, kui ta on injektiivne  jaoks; 
 Funktsiooni  nimetatakse minimaalseks ideaalseks räsifunktsiooniks  jaoks, kui ta on ideaalne räsifunktsioon ning ; 
 , mis on täisarv, jaoks funktsiooni  nimetatakse -ideaalseks räsifunktsiooniks (k-PHF)  jaoks, kui iga  jaoks meil on .

Ideaalset räsimist kasutatakse nendel juhustel, kui me tahame omistada unikaalset identifikaatori võtmele, säilitamata mingitki infot võtme kohta. Üheks kõige ilmselgemaks ideaalse (võib pigem k-ideaalse) räsimise kasutamise näiteks on olukord, kui meil on käsutusel väike kiire mälu, kuhu me paneme selliste räsi võtmete tähendusi, mis on seotud suures, aga aeglases mälus säilitatavate andmetega. Seejuures ploki suurust võib valida selliseks, et vajatavad andmed, mis säilivad aeglases mälus, võivad olla saadud ühe päringuga. Sellist lähenemist kasutatakse, näiteks, aparaatruuterites. Samuti ideaalset räsimist kasutatakse algoritmide töö graafidel kiirendamiseks, neil juhustel, kui graafi kujundus ei mahu põhimälus.

 Universaalne räsimine 
{{|Universaalne räsimine|Universaalseks räsimiseks|en|Universal hashing}} nimetatakse räsimist, mille puhul kasutatakse mitte üht konkreetset räsifunktsiooni, vaid toimub valik antud parvest juhusliku algoritmi järgi. Universaalse räsimise kasutamine tavaliselt tagab väikest kollisioonide arvu. Universaalset räsimist kasutatakse mitmel viisil, näiteks räsitabelite realiseerimises ja krüptograafias.

 Kirjeldus 
Oletame, et me tahame kujutada võtmed ruumist  arvudesse . Sisendile algoritm saab teatud andmete hulka  suurusega , kusjuures ta on teadmata ebaselge. Reeglina räsimise eesmärgiks on kollisioonide minimaalse arvu saamine, mida on raske saavutada, kasutades mingit teatud räsifunktsiooni.

Sellise probleemi lahendusena võib valida funktsiooni juhuslikul viisil teatud hulgast (kogusest), mida nimetatakse universaalseks parveks .

 Kollisioonitõrje meetodid 

Nagu eespool mainitud, nimetatakse räsifunktsiooni kollisiooniks kaht sellist andmete sisendplokki, mis annavad samasuguseid räsikoode.

Räsitabelites
Enamik esimesi töid, kus oli kirjeldatud räsimist, käsitles kollisioonitõrje meetodeid räsitabelites, kuna räsifunktsioone oli kasutatud otsimiseks suurtes failides. Räsitabelites kasutatakse kaht meetodit: 
Kettide meetod 
Avatud aadressi meetod

Esimene meetod seisneb  seotud nimestike toetuses, igaüks iga räsifunktsiooni tähendusele. Nimestikus säilivad võtmed, mis annavad sama räsikoode tähenduse. Üldjuhul, kui meil on  võtmeid ning  nimestikke, räsifunktsiooni keskmine suurus on  ning räsimine viib töö keskmise koguse vähenemiseni võrreldes järjestiku otsimisega ligikaudu  korda.

Teine meetod seisneb selles, et tabeli massiivis säilivad paarid võti-tähendus. Sel viisil me loobume täiesti linkidest ning lihtsalt vaatleme tabelikirjeid, kuni leiame otsitud võtme  või tühja koha. Järjestust, milles vaadeldakse tabeli lahtreid, nimetatakse proovide järjestuseks.

Krüptograafiline sool
Paroolide kaitsmiseks võltsimise eest on mitu viisi, mis töötavad isegi siis, kui krüptoanalüütikule on teada antud räsifunktsiooni jaoks antud kollisioonide ehituse viisid. Üheks sellistest meetoditest on krüptograafilise soola (ehk juhuslike andmete rea) lisamine sisendandmetele (vahel "soola" lisatakse räsikoodile), mis oluliselt raskendab lõplike räsitabelite analüüsi. Antud meetodit, näiteks, kasutatakse paroolide säilitamiseks UNIX-taolistes operatsioonisüsteemides.

 Räsifunktsioonide kasutus 

Räsifunktsioone kasutatakse laialt krüptograafias ja paljudes andmestruktuurides – räsitabelites, Blumi filtrites ja Dekarti puudes.

 Krüptograafilised räsifunktsioonid 
Mitmesuguste olevate räsifunktsioonide hulgas on kombekohane eristada krüptograafiliselt kindlaid, mida kasutatakse krüptograafias, kuna neile seatakse lisatingimusi. Selleks, et räsifunktsiooni  võiks pidada krüptograafiliselt kindlaks, ta peab vastama kolmele põhinõudmistele, millel on rajatud enamik räsifunktsioone kasutusi krüptograafias:  
 Pööramatus: räsifunktsiooni m selle tähenduse jaoks peab olema arvutamise poolest võimatu leida andmeplokk , mille jaoks . 
 Kindlus esimese liigi kollisioonide suhtes: antud teate M jaoks peab olema arvutamise poolest võimatu leida teist teadet N, mille jaoks . 
 Kindlus teise liigi kollisioonide suhtes: peab olema arvutamise poolest võimatu leida paari teateid , millel on sama räsi.

Need nõuded pole sõltumatud: 
 Pöörduv funktsioon pole kindel esimese ja teise liigi kollisioonide suhtes. 
 Funktsioon, mis pole kindel esimese liigi kollisiooni suhtes, pole kindel ka teise liigi kollisiooni suhtes; vastupidine pole õige.

Tasub märkida, et pole tõestatud pöördumatute räsifunktsioonide olemasolu, mille jaoks räsifunktsiooni selle tähenduse mingisuguse prototüübi arvutamine on teoreetiliselt võimatu. Tavaliselt vastupidise tähenduse leidmine on vaid arvutamise poolest keeruline ülesanne.

"Sünnipäevade" atakk lubab leida kollisioone räsifunktsiooni jaoks keskmiselt tähenduste pikkusega n bitti ligikaudu  räsifunktsiooni arvutustega. Seepärast n-bitine räsifunktsioon on peetud krüptokindlaks, kui tema jaoks kollisioonide leidmise arvutuslik keerulisus on lähedane -ni.

Kriptograafiliste räsifunktsioonide jaoks on tähtis ka, et argumendi väikseimagi muutumisega funktsiooni tähendus muutuks oluliselt (laviini efekt). Sealhulgas räsi tähendus ei pea andma info kadumist isegi argumendi omaette bittidest. See nõudmine on krüptokindluse tagatiseks sellistele räsimise algoritmidele, mis räsivad kasutaja parooli võtme saamiseks.

Räsimist tihti kasutatakse digitaalallkirja algoritmides, kus šifreeritakse mitte teadet, vaid selle räsikoodi, mis vähendab arvutamise aega ning suurendab krüptokindlust. Samuti enamikul juhtudest paroolide asemel hoitakse nende räsikoodide tähendusi.

 Kontrollsummad 

Lihtsad, ülikiired ning kergesti täidetavad aparaadialgoritmid, mida kasutatakse kaitseks ettekavatsemata moonutustest, sealhulgas aparatuuri vigade eest. Matemaatika seisukohast on räsifunktsiooniks selline, mis arvutab sellist kontrollkoodi, mida kasutatakse vigade avastamiseks info edastamisel ning säilitamisel.

Arvutuse kiiruse poolest on kümnete ning sadade kordade kiiremad, kui krüptograafilised räsifunktsioonid, ning oluliselt lihtsamad aparaadi abil teostamise seisukohast.

Sellise kõrge kiiruse tasuks on krüptokindluse puudus – kerge võimalus sobitada teadet eelnevalt teadaolevaks summaks. Samuti on kontrollsummade järgulisus (tüüpiline arv:32 bitti) vähem, kui krüptograafiliste räside omad (tüüpilised arvud: 128, 160 ja 256 bitti), mis tähendab tahtmatute kollisioonide tekkimise võimalust.

Sellise algoritmi lihtsamaks näiteks on teate jagamine 32- või 16-bittisteks sõnadeks ning nende liitmine, mida kasutatakse näiteks TCP/IP-s.

Reeglina sellisele algoritmile esitatakse tüüpiliste aparaadiga sooritatavate vigade jälgimise nõudmiseid. Nõndanimetatud (nn) tsükliliste üleliigsete koodide algoritmide parv vastab sellistele nõudmistele. Nende hulga võib arvata, näiteks, CRC32, mida kasutatakse Etherneti vahendites ning andmete pakkimise formaadis 2IP.

Kontrollsumma võib näiteks olla kantud üle sidekanali kaudu koos põhitekstiga. Vastuvõtuotsas kontrollsumma võib olla arvutatud üle ning seda võib võrrelda ülekantud (saadetud) tähendusega. Kui on avastatud erinevus, siis see tähendab, et edastamisel tekkisid moonutused ning tuleb veel kord proovida.

Räsimise olmeanaloogiks antud juhul võib olla vastuvõtt, kui ülesõidudel mälus hoitakse pagasi kohtade arvu. Siis kontrolliks pole vaja meelde tuletada igat reisikohvrit, vaid piisab nende ülelugemisest. Klappimine tähendab, et mitte ükski kohver pole kaotatud. Teisiti öeldes, pagasi kohtade arv on selle räsikood. 
Antud meetodit on lihtne täiendada kaitseks edastatava info võltsimise eest (MAC meetod). Sel juhul teostatakse räsimist krüptokindla funktsiooni abil teatele, mis on ühendatud salavõtmega, mida teavad ainult teate saatja ning vastuvõtja. Niimoodi krüptoanalüütik ei saa koodi taastada ülevõetud teate ning räsifunktsiooni tähenduse abil, see tähendab, ta ei saa teadet võltsida.

 Geomeetriline räsimine 
Geomeetriline räsimine on laialt arvutigraafikas ning arvutusgeomeetrias kasutatav meetod lahendamiseks ülesandeid tasapinnal või kolmemõõtmelises ruumis, näiteks lähemate paaride leidmiseks punktide hulgas või sarnaste kujutiste otsimiseks. Räsifunktsioon antud meetodi kasutamisel saab sisendile mingisuguse meetrilise ruumi ning jagab seda, moodustades punktidest koosneva võrgu. Tabeliks antud juhul on massiiv kahe või enam indeksiga ning kannab nime võrgufail (inglise: Grid file). Geomeetriline räsimine samuti on kasutatud telekommunikatsioonides töötamisel mitmemõõtmeliste signaalidega.

 Andmete otsimise kiirendamine 
Räsitabeliks nimetatakse andmete struktuuri, mis lubab säilitada paare tüüpe (võti, räsikood) ning toetab elemendi otsimise, sisestamise ning eemaldamise operatsioone. Räsitabelite ülesanneks on otsimise kiirendamine, näiteks, tekstiväljade kirjutamisel andmebaasis võib olla arvutatud nende räsikood ning andmed võivad olla pandud jakku, mis ühtib sellise räsikoodiga. Siis andmete otsimisel tuleb kõigepealt arvutada teksti räsikoodi ning on kohe teada, kus (mis jaos) neid tuleb otsid, see tähendab, neid tuleb otsida mitte kogu baasis, vaid selle ühes jaos (see kiirendab otsingut märgatavalt).

Olmeanaloogiks võib sel juhul pidada sõnade tähestikulist järjekorda sõnaraamatus. Sõna esimene täht on selle räsikood, ning otsimisel me vaatame üle mitte terve sõnaraamatu, vaid vajaliku tähe.

Vaata ka
Räsimine (inglise: hashing)22. oktoober 2015, Anto Veldre, Räsist ja räsimisest, RIA veebipäevik
SHA

 Viited 

Kirjandus
 February 23, 2017 CWI, Google announce first collision for Industry Security Standard SHA-1

Kategooria:Krüptograafia
Kategooria:Informaatika