Räsifunktsioon: erinevus redaktsioonide vahel

Eemaldatud sisu Lisatud sisu

Reasisene

Redaktsioon: 2. märts 2014, kell 16:58

Räsifunktsioon (inglise hash function) on krüptograafias kasutatav ühesuunaline funktsioon tekstistringide kodeerimiseks^[1].

Räsifunktsiooni kasutatakse assotsiatiivsete massiivide ülesehituseks, andmekogumite seeriates dublikaatide 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ähem, 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 räsimisalgoritme erinevate omadustega (arvutuse raskus, krüpteerimiskindlus jne.). Ühe või teise räsifunktsiooni valiku tehakse kindlaks lahendava ülesanne eripäraga.

Ajalugu

Donald Knuth arvab esimese räsimise süsteemi idee autoriks IBM kaastöötajat, kelleks on Hans Peter Lun, kes pakkus välja kodeerimist räsimise abil jaanuaris 1953. Arnold Dumey esitas oma 1956. aasta töös "Computers and automation" esimesena räsimise kontseptsiooni sellisena, millena seda teab enamik programmeerijatest tänapäeval. Dumey vaatas räsimist nagu "Sõnaraamatu probleemi" lahendust ning pakkus välja kasutada räsiaadressiks algarvuga jagamise jääki.

Esimeseks tõsiseks tööks, mis oli seotud otsimisega suurtest failidest, oli W. Wesley Petersoni artikkel 1957. aastal, milles ta avas avaliku adresseerimist ning osutas tootlikkuse halvenemisele kustutamisel. Kuus aastat hiljem avalikustati Werner Buchholz töö, milles on tehtud räsifunktsioonide lai uurimine. Mitmete järgmiste aastate jooksul oli räsimine küll laialt kasutatud, aga ei avalikustatud mitte ainsatki tähtsat tööd.

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

1990-te aastate alguseni venekeelses kirjanduses oli tänu Andrei Jeršovi töödele kasutatud 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".

Räsifunktsioonide liigid

Hea räsifunktsioon peab vastama kahele tingimusele:

Olema kiiresti arvutatav;
Minimiseerima kollisioonide arvu.

Määratletuseks oletame, et võtide arv on $K$ , ja räsifunktsioonil $h(K)$ on mitte rohkem, kui $M$ erinevaid tähendusi:

$0<h(k)<M$ "Halva" räsifunktsiooni näitena võib tuua funktsiooni $M=1000$ , mis kümnekohalisele naturaalarvule $K$ vastastab kolm numbri $K$ kahekümnenda ruudu keskest valitud arvu. Tundub, et räsikoodide tähendused peaksid ühtlaselt jaotuma «000» ja «999» vahel, kuid reaalsete andmete jaoks selline meetod sobib vaid juhul, kui võtmetel pole suurt nullide arvu vasakul ja paremal.^[2]

Kuid on olemas mitu lihtsamaid ja kindlamaid meetodeid, millele tuginevad paljud räsifunktsioonid.

Jagamisele rajatud räsifunktsioonid

Esimene meetod seisneb selles, et me kasutame räsina jagamise $M$ -ga jääki, kus $M$ on kõikide võimalike räside arv:

h(K)=K\mod M

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

Veel tasuks mainida räsimise meetodit, mis on rajatud mooduliga kaks jagamisele polünoomile. Antud meetodi puhul $M$ peab samuti olema kahe aste, ning binaarvõtid ( $K=k_{n-1}k_{n-2}...k_{0}$ ) on kujutatud polünoomidena. Sel juhul räsikoodina võetakse tegurite tähendusi polünoomist, mis on saadud nagu jääk $K$ jagamisest eelnevalt valitud polünoomiga $P$ astmes $m$ :

K(x)\mod P(x)=h_{m-1}x^{m-1}+h_{1}x+h_{0}

h(x)=h_{m-1}...h_{1}h_{0}

Õigesti valitud $P(x)$ puhul selline viis tagab kollisioonide peaaegu sarnaste võtmete vahel puudumise.Mall:Snf

Räsimise multiplikaatne skeem

Teine meetod seisneb mingi terve konstandi $A$ , mis on vastastikult harilik $w$ -ga, valimises, kus $w$ on masinsõna abil esindatavate tähenduste arv (IBM PC arvutites see on $2^{32}$ ). Siis võib võtta järgmist räsifunktsiooni:

h(k)=\left[M\left\lfloor {\frac {A}{w}}*K\right\rfloor \right]

Sel juhul, kahendsüsteemiga arvutil $M$ on kahe aste ning $h(K)$ koosneb korrutise $A*K$ parempoolsetest vanematest bittidest.

Nende kahe meetodite 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õige omadustel. $A$ arvuna võetakse lähedasemat $\varphi ^{-1}*w$ arvule algarvu, mis on vastastikult harilik $w$ -ga.

Muutliku suurusega ridade räsimine

Üleval mainitud meetodid on kasutatavad ka sel juhul, kui me peame tegelema võtmetega, mis koosnevad mitmetest sõnadest, või muutliku suurusega võtmetega. Näiteks võib kombineerida sõnad ühte $w$ mooduliga liitmise või "välistav või" operatsiooni abil. Üks algoritmitest, mis töötab sel põhimõttel, on Pearsoni räsifunktsioon.

Mall:Pearsoni räsimine on Peter Pearsoni pakutud algoritm 8-bitiste registritega protsessorite jaoks, mille ülesandeks on suvalise suurusega rea jaoks räsikoodi kiire arvutus. Sisendile funktsioon saab sõna $W$ , mis koosneb $n$ 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 $W$ ning kasutab vaheste tabeli $T$

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 $K$ , mis koosnevad $l$ sümbolitest ( $K=x_{1}x_{2}...x_{l}$ ), räsimise alternatiivse viisina võib välja pakkuda arvutust

h(K)=(h_{1}(x_{1})+h_{2}(x_{2})+...+h_{l}(x_{l}))\mod M

.

Ideaalne räsimine

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

Kirjeldus

Funktsiooni $h(k)\colon U\to [m]$ nimetatakse ideaalseks räsifunktsiooniks $S\subseteq U$ jaoks, kui ta on injektiivne $S$ jaoks;
Funktsiooni $h(k)\colon U\to [m]$ nimetatakse minimaalseks ideaalseks räsifunktsiooniks $S\subseteq U$ jaoks, kui ta on ideaalne räsifunktsioon ning $m=n=|S|$ ;
$k\geq 1$ , mis on täisarv, jaoks funktsiooni $h(k)\colon U\to [m]$ nimetatakse $k$ -ideaalseks räsifunktsiooniks (k-PHF) $S\subseteq U$ jaoks, kui iga $j\in [m]$ jaoks meil on $|\{x\in S|h(x)=j\}|\leq k$ .

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 ning krüptograafias.

Kirjeldus

Oletame, et me tahame kujutada võtmed ruumist $U$ arvudesse $[m]$ . Sisendile algoritm saab teatud andmete hulka $S\in U$ suurusega $n$ , 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 $H=\{h:U\to [m]\}$ .

Vaata ka

Räsimine (inglise hashing)

Viited

↑ e-Teatmik (vaadatud 04.09.2012)
↑ Дональд Кнут. Искусство программирования.

[e-Teatmik-1] -Teatmik (vaadatud 04.09.2012)

[FOOTNOTEДональд_Кнут._Искусство_программирования-2] Дональд Кнут. Искусство программирования.

[1]

[2]

@@ 55. rida: / 55. rida: @@
 Selle meetodi üks variatsioonidest on Fibonacci arvu räsimine, mis põhineb kuldlõige omadustel. <math>A</math> arvuna võetakse lähedasemat <math>\varphi^{-1}*w</math> arvule algarvu, mis on vastastikult harilik <math>w</math>-ga.
+=== Muutliku suurusega ridade räsimine ===
+Üleval mainitud meetodid on kasutatavad ka sel juhul, kui me peame tegelema võtmetega, mis koosnevad mitmetest sõnadest, või muutliku suurusega võtmetega. Näiteks võib kombineerida sõnad ühte <math>w</math> mooduliga liitmise või "välistav või" operatsiooni abil. Üks algoritmitest, mis töötab sel põhimõttel, on Pearsoni räsifunktsioon.
+{{Pearsoni räsimine||en|Pearson hashing}} on Peter Pearsoni pakutud algoritm 8-bitiste registritega protsessorite jaoks, mille ülesandeks on suvalise suurusega rea jaoks räsikoodi kiire arvutus. Sisendile funktsioon saab sõna <math>W</math>, mis koosneb <math>n</math> 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 <math>W</math> ning kasutab vaheste tabeli <math>T</math>
+<code lang="pseudo">
+ h := 0
+ '''for each''' c '''in''' W '''loop'''
+   index := h '''xor''' c
+   h := T[index]
+ '''end loop'''
+ '''return''' h
+</code>
+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 <math>K</math>, mis koosnevad <math>l</math> sümbolitest (<math>K=x_{1}x_{2}...x_{l}</math>), räsimise alternatiivse viisina võib välja pakkuda arvutust
+: <math>h(K)=(h_{1}(x_{1})+h_{2}(x_{2})+...+h_{l}(x_{l})) \mod M</math>.
+=== Ideaalne räsimine ===
+Ideaalseks räsifunktsiooniks ({{lang-en|Perfect hash function}}) nimetatakse sellist funktsiooni, mis kujutab iga võtme <math>S</math> komplektist täisarvude hulka ilma kollisioonideta. Matemaatilistes terminites see on injektiivne kujutis.
+==== Kirjeldus ====
+# Funktsiooni <math>h(k)\colon U\to [m]</math> nimetatakse ideaalseks räsifunktsiooniks <math>S\subseteq U</math> jaoks, kui ta on injektiivne <math>S</math> jaoks;
+# Funktsiooni <math>h(k)\colon U\to [m]</math> nimetatakse minimaalseks ideaalseks räsifunktsiooniks <math>S\subseteq U</math> jaoks, kui ta on ideaalne räsifunktsioon ning <math>m = n = |S|</math>;
+# <math>k\ge 1</math>, mis on täisarv, jaoks funktsiooni <math>h(k)\colon U\to [m]</math> nimetatakse <math>k</math>-ideaalseks räsifunktsiooniks (k-PHF) <math>S\subseteq U</math> jaoks, kui iga <math>j\in [m]</math> jaoks meil on <math>|\{x\in S | h(x) = j\}|\le k</math>.
+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 ning krüptograafias.
+==== Kirjeldus ====
+Oletame, et me tahame kujutada võtmed ruumist <math>U</math> arvudesse <math>[m]</math>. Sisendile algoritm saab teatud andmete hulka <math>S\in U</math> suurusega <math>n</math>, 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 <math>H = \{ h : U \to [m] \}</math>.