Räsifunktsioon

Ajalugu

Donald Knuth peab esimese räsimissüsteemi idee autoriks IBMi kaastöötajat 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 programmeerijatest 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 jäänud vaid sõna "räsimine".

Ideaalne räsimine

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

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

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.

Kontrollsummad

Lihtsad, äärmiselt kiired 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 ning 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 (). 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 tähestikulist sõnade järjestust sõnaraamatus. Sõna esimene täht on selle räsikood, ning otsimisel me vaatame üle mitte terve sõnaraamatu, vaid vajaliku tähe.