Erinevus lehekülje "Räsifunktsioon" redaktsioonide vahel

Artikli lõppvariant on valmis
(Artikli lõppvariant on valmis)
===Krüptograafiline sool===
On olemas mitu viisi kaitseks paroolide võltsimise eest, 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 laialt kasutatakse krüptograafias ning samuti paljudes andmestruktuurides - räsitabelites, Blumi filtrites ning 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 <math>H</math> võiks pidada krüptograafiliselt kindlaks, ta peab vastama kolmele põhinõudmistele, milledel on rajatud enamik räsifunktsioone kasutusi krüptograafias:
* ''Pööramatus'': räsifunktsiooni ''m'' antud tähenduse jaoks peab olema arvutamise poolest võimatu leida andmeplokk <math>X</math>, mille jaoks <math>H(X)=m</math>.
* Kindlus ''esimese liigi kollisioonide'' suhtes: antud teate ''M'' jaoks peab olema arvutamise poolest võimatu leida teist teadet ''N'', mille jaoks <math>H(N)=H(M)</math>.
* Kindlus ''teise liigi kollisioonide'' suhtes: peab olema arvutamise poolest võimatu leida paari teateid <math>~ (M, M')</math>, millel on sama räsi.
 
Antud 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 antud 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 <math>2^{n/2}</math> räsifunktsiooni arvutustega. Seepärast ''n''-bitine räsifunktsioon on peetud krüptokindlaks, kui tema jaoks kollisioonide leidmise arvutuslik keerulisus on lähedane <math>2^{n/2}</math>-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, ää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 [[Ethernet]]i 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). Sellisel juhul räsimist teostatakse 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 ({{lang-en|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 sellisel juhul võib pidada alfabeetilise 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 vajalikku tähte.
 
 
101

muudatust