Räsifunktsiooni arvutamise tulemus on. Elektrooniline digitaalallkiri. Nõuded räsifunktsioonidele

Ühesuunalistel räsifunktsioonidel põhinevad teisendatud andmete tihendamise meetodid

Räsifunktsioon (räsi, räsifunktsioon) on teisendus, mis saab suvalise pikkusega andmetest teatud kindla pikkusega väärtuse (konvolutsiooni). Lihtsamad näited on kontrollsummad (nt crc32). Seal on:

· krüptograafilised räsid;

· programmeerija räsid.

Krüptograafiline räsi erineb programmeerija räsist kahe järgmise omaduse poolest: pöördumatus ja kokkupõrkevabadus. Tähistame:

m - algandmed,

h(m) on nende räsifunktsioon.

Pöördumatus tähendab seda, et kui arv h0 on teada, siis m on raske valida nii, et h(m) = h0.

Kokkupõrkevaba tähendab, et m1 ja m2 on raske leida nii, et m1 ei oleks võrdne m2-ga, vaid h(m1) = h(m2).

Krüptograafilised räsifunktsioonid jagunevad kahte klassi:

Räsifunktsioonid ilma võtmeta (MDC (modifikatsiooni (manipulatsiooni) tuvastamise koodi) koodid),

Räsifunktsioonid võtmega (MAC (Message Authentication Code) koodid).

Võtmeta räsifunktsioonid jagunevad kahte alamklassi: nõrgad räsifunktsioonid ja tugevad räsifunktsioonid.

Nõrk räsifunktsioon on ühesuunaline funktsioon H(x), mis vastab järgmistele tingimustele:

1. argument x võib olla suvalise pikkusega bitistring;

2. h(x) väärtus peab olema fikseeritud pikkusega bitijada;

3. h(x) väärtust on lihtne arvutada;

4. iga fikseeritud x jaoks on arvutuslikult võimatu leida teist x" ≠ x nii, et h(x")=h(x).

Paari x" ≠ x, kui h(x")=h(x) nimetatakse räsifunktsiooni kokkupõrkeks.

Tugev räsifunktsioon on ühesuunaline funktsioon h(x), mis vastab nõrga räsifunktsiooni tingimustele 1–4 ja omadusele 5:

5. Arvutuslikult on võimatu leida ühtegi paari x" ≠ x, mille puhul h(x")=h(x).
Kuna omadustest 1-2 tuleneb, et räsifunktsiooni definitsioonihulk on väärtuste hulgast palju laiem, peavad kokkupõrked olema. Omadus 4 eeldab, et nende leidmine antud väärtuse x jaoks on peaaegu võimatu. Nõue 5 ütleb, et tugeval räsifunktsioonil on arvutuslikult võimatu leida kokkupõrget.

Räsifunktsioonide arvutamiseks on mitu algoritmi

MD2 (Message Digest) on krüptograafiline redutseerimisalgoritm. Loob suvalise pikkusega sõnumist 128-bitise ploki. MD2 töö üldine skeem:

a. sõnumi teksti täitmine pikkusega, mis on 128 biti kordne;

b. 16-bitise kontrollsumma arvutamine, enamik olulisi bitte jäetakse kõrvale;

c. tekstile kontrollsumma lisamine;

d. kontrollsumma ümberarvutamine.

MD2 algoritm on väga aeglane, seetõttu kasutatakse sagedamini MD4, MD5, SHA (Secure Hash Algorithm). Saadud räsi on 160 bitti pikk.

GOST R34.11-94. Vene algoritm. Konvolutsiooni pikkus on 256 bitti (väga mugav GOST 28147-89 jaoks võtme genereerimiseks parooli abil).

USA riiklik standardite ja tehnoloogia instituut (NIST) avaldas oma veebisaidil http://www.nist.gov/sha/ spetsifikatsioonid uutele räsimisalgoritmidele SHA-256, SHA-384 ja SHA-512, mille eesmärk on et tagada räsi krüptograafilise tugevuse tase, mis vastab uue DES-i krüpteerimisstandardi võtmepikkustele.

Tuletame meelde, et n-bitine räsi on suvalise pikkusega sõnumi vastendamine n-bitiseks pseudojuhuslikuks jadaks (räsiväärtus). Krüptograafiline räsi kui sellise funktsiooni eritüüp on n-bitine räsi, millel on "ühesuunalisuse" ja "kokkupõrkekindluse" omadused.

Seni on populaarseimad räsifunktsioonid olnud Raivisti loodud MD4 ja MD5, mis genereerivad n=128 pikkuseid räsikoode ning USA NSA poolt välja töötatud algoritm SHA-1, mis genereerib n=160 pikkuseid räsikoode. .

GOST R34.10-94 "Asümmeetrilisel krüptoalgoritmil põhineva elektroonilise digitaalallkirja väljatöötamise ja kontrollimise protseduurid".

räsimine ülesannete lahendamisel C++ keeles.

Suurte teabemahtude hulgast andmete otsimise protsess on aeganõudev, kuna otsinguklahviga on vaja vaadata ja võrrelda märkimisväärset hulka elemente. Otsingut saab vähendada vaateala lokaliseerimisega. Näiteks sortige andmed otsinguvõtme järgi, jagage need mittekattuvateks plokkideks vastavalt mõne rühma tunnusele või viige tegelikud andmed kokku kindla koodiga, mis lihtsustab otsinguprotseduuri.

Praegu on laialdaselt kasutatav meetod välismällu salvestatud teabele kiire juurdepääsu tagamiseks räsimine.

Räsimine(või räsimine, Inglise räsimine) on teatud tüüpi ja suvalise pikkusega sisendandmete massiivi teisendus fikseeritud pikkusega väljundbittide stringiks. Selliseid teisendusi nimetatakse ka räsifunktsioonid või konvolutsioonifunktsioonid ja nende tulemusi nimetatakse räsi, räsikood, räsitabel või seedida sõnumid (inglise keeles) sõnumi kokkuvõte).

Räsi tabel- See andmestruktuur, mis rakendab assotsiatiivse massiivi liidest, st võimaldab salvestada võtme-väärtuse paare ja teha kolm toimingut: uue paari lisamise toiming, otsinguoperatsioon ja paari võtme järgi kustutamise toiming. Räsitabel on räsifunktsiooniga kindlas järjekorras moodustatud massiiv.

funktsioon peab olema arvutuslikust seisukohast lihtne;
funktsioon peaks jaotama võtmed räsitabelis võimalikult ühtlaselt;
funktsioon ei tohi vastendada võtmeväärtuste vahelisi seoseid aadressiväärtuste vaheliseks suhteks;
funktsioon peab minimeerima kokkupõrgete arvu - see tähendab olukordi, kus erinevad võtmed vastavad samale räsiväärtusele (sel juhul nimetatakse võtmeid sünonüümid).

Sel juhul sõltub hea räsifunktsiooni esimene omadus arvuti omadustest ja teine - andmete väärtustest.

Kui kõik andmed oleksid juhuslikud, oleksid räsifunktsioonid väga lihtsad (näiteks mõned võtmebitid). Kuid praktikas on juhuslikud andmed piisavalt haruldased, et peate looma funktsiooni, mis sõltub kogu võtmest. Kui räsifunktsioon jaotab populatsiooni võimalikud võtmedühtlaselt mitme indeksi vahel jagab räsimine tõhusalt mitu võtit. Halvim on see, kui kõik võtmed on räsistatud ühte indeksisse.

Kokkupõrgete ilmnemisel on vaja leida uus asukoht, kuhu salvestada võtmed, mis nõuavad sama räsitabeli lahtrit. Veelgi enam, kui kokkupõrked on lubatud, tuleb nende arv minimeerida. Mõnel erijuhul on võimalik kokkupõrkeid üldse vältida. Näiteks kui kõik elemendivõtmed on ette teada (või muutuvad väga harva), siis võib nende jaoks leida mingi süstiva räsifunktsiooni, mis jaotab need räsitabeli lahtrite vahel ilma kokkupõrgeteta. Sarnaseid räsifunktsioone kasutavad räsitabelid ei vaja kokkupõrke lahendamise mehhanismi ja neid nimetatakse räsitabeliteks koos otsene adresseerimine.

Räsitabelid peavad vastama järgmistele omadused.

Räsitabelis toimingu sooritamine algab võtme räsifunktsiooni arvutamisega. Saadud räsiväärtus on algse massiivi indeks.
Kutsutakse salvestatud massiivi elementide arv jagatud võimalike räsiväärtuste arvuga räsitabeli täitmistegur (koormustegur) ja see on oluline parameeter, millest sõltub toimingute keskmine täitmise aeg.
Otsingu-, sisestamis- ja kustutamistoimingud tuleks sooritada keskmiselt O(1) ajaga. See hinnang ei võta aga arvesse massiivi suuruse väärtuse suurendamisega ja räsitabelisse uue paari lisamisega seotud räsitabeli indeksi taastamise võimalikke riistvarakulusid.
Kokkupõrke lahendamise mehhanism on iga räsitabeli oluline komponent.

Räsimine on kasulik, kui väikesesse mälumahtu tuleb salvestada suur hulk võimalikke väärtusi ja vaja on kiiret, peaaegu juhuslikku juurdepääsu. Rästabeleid kasutatakse sageli andmebaasides ja eriti nendes keeleprotsessorid nagu kompilaatorid ja komplekteerijad, kus need suurendavad identifikaatoritabeli töötlemise kiirust. Räsi kasutamise näideteks igapäevaelus on raamatukogus raamatute jaotamine temaatilistesse kataloogidesse, sõnaraamatutes sõnade esitähtede järgi järjestamine, erialade krüpteerimine ülikoolides jne.

Kokkupõrke lahendamise meetodid

Kokkupõrked raskendavad räsitabelite kasutamist, kuna need katkestavad unikaalse vastavuse räsikoodide ja andmete vahel. Kuid tekkivate raskuste ületamiseks on viise:

aheldamismeetod (väline või avatud räsimine);
avatud adresseerimismeetod (suletud räsimine).

Ahel meetod. Elementide nakkumise tehnoloogia on see komplekti elemendid, mis vastavad samale räsiväärtusele, on lingitud ahelloendisse. Positsiooninumber i salvestab kursori nende elementide loendi päisesse, mille võtme räsiväärtus on võrdne i-ga; kui hulgal selliseid elemente pole, kirjutatakse positsioonile i NULL. Joonisel fig. Joonisel 38.1 on näidatud aheldamise meetodi rakendamine kokkupõrgete lahendamiseks. Võtmele 002 kuuluvad kaks väärtust, mis on organiseeritud lineaarsesse loendisse.

Riis.

38.1.

Iga massiivilahter on osuti võtme-väärtuste paaride lingitud loendile (ahelale), mis vastab võtme samale räsiväärtusele. Kokkupõrgete tulemuseks on lihtsalt ühest elemendist pikemad ahelad.

Otsingu- või kustutamistoimingud nõuavad vastava ahela kõigi elementide vaatamist, et leida selles antud võtmega element. Andmete lisamiseks tuleb lisada element vastava loendi lõppu või algusesse ning kui täitmistegur muutub liiga suureks, siis massiivi suurust suurendada ja tabel uuesti üles ehitada.

Räsimine (mõnikord "räsimine", inglise keeles räsimine) on suvalise pikkusega sisendandmete massiivi teisendamine kindla pikkusega väljundbiti stringiks, kasutades deterministlikku algoritmi. Selliseid teisendusi nimetatakse ka räsifunktsioonideks või konvolutsioonifunktsioonideks ning nende tulemusi räsi-, räsikoodiks või sõnumi kokkuvõtteks. sõnumi kokkuvõte).

wikipedia

Räsimine infotehnoloogias laialdaselt kasutatav - andmekogumitele üsna unikaalsete identifikaatorite konstrueerimiseks, kontrollsummadeks, et tuvastada juhuslikke või tahtlikke vigu salvestamise või edastamise ajal, paroolide salvestamiseks turvasüsteemides (antud juhul juurdepääs mälualale, kus paroolid asuvad ei võimalda parooli enda taastamist) jne.

Räsifunktsioon mõeldud kokkusurumiseks sisendandmete massiiv suvaline pikkus sisse bit string etteantud suurus (mitu kümneid või sadu bitte).

Räsifunktsioon h võtab argumendina sisendandmete massiiv(dokument) X suvalise pikkusega ja tagastab fikseeritud pikkusega räsiväärtuse h(X)=H. Tavaliselt on räsitud teave suvalise pikkusega alussõnumi tihendatud binaarne esitus sõnumi kokkuvõte (sõnumi kokkuvõte). Tuleb märkida, et räsifunktsiooni väärtus h(X) sõltub keeruliselt dokumendist X ega võimalda dokumenti ennast räsiväärtusest H rekonstrueerida (ühesuunaline räsifunktsioon).

Üldiselt ei pea me ühesuunalisuse all silmas sõnumi taastamise võimatust, vaid keerukust. räsi, kuna hetkel ei ole kasutatud räsifunktsioonid tõestatud ühesuunalisusega.

Teoreetiliselt on olemas andmemassiivi Y, mille puhul h(X) = h(Y). Neid X,Y paare nimetatakse kokkupõrgeteks. Peamine nõue, mille krüptograafilised rakendused räsifunktsioonidele esitavad, on tõhusate kokkupõrketuvastusalgoritmide puudumine.

Elektroonilise allkirja skeemid on üks räsifunktsioonide rakendusvaldkondi.

Moodustades elektrooniline allkiri praktikas ei kirjutata sageli alla mitte sõnumile endale, vaid sellele räsipilt.

Digitaalallkirjastamise protsessi käigus töötleb digitaalallkirjasüsteem algset sõnumit (eelpilti) krüptograafiliselt tugeva ühesuunalise räsialgoritmiga. See toiming genereerib sõnumi kokkuvõte.

Seejärel krüpteerib süsteem saadud kokkuvõtte saatja privaatvõtmega, luues "elektroonilise allkirja" ja lisab selle prototüübile. Sõnumi vastuvõtmisel arvutab saaja digiallkirjasüsteemi kasutades uuesti allkirjastatud andmete kokkuvõtte, dekrüpteerib saatja avaliku võtmega digitaalallkirja, kontrollides sellega vastavalt andmete ja nende allika terviklikkust; kui adressaadi arvutatud ja sõnumiga saabunud kokkuvõtted langevad kokku, siis pärast allkirjastamist infot muudetud ei ole.

EDS-süsteemid võivad kasutada erinevaid räsifunktsioonid, kuid need peavad vastama mitmele tingimusele:

räsifunktsioon peab olema tundlik igasuguste teksti muudatuste suhtes, nagu lisamised, kustutamised, ümberpaigutused jne;
räsifunktsioonil peab olema pöördumatuse omadus, see tähendab, et ülesanne valida dokument, millel oleks vajalik räsifunktsiooni väärtus, peab olema arvutuslikult lahustumatu;
kokkupõrgete tõenäosus, see tähendab, et kahe erineva dokumendi (olenemata nende pikkusest) räsifunktsiooni väärtused langevad kokku, peaks olema tühine.

Valitud räsifunktsioon peaks olema lihtsalt arvutatav ja tekitama võimalikult vähe kokkupõrkeid, s.t. peaks võtmed jaotama ühtlaselt tabelis olemasolevate indeksite vahel. Muidugi on võimatu kindlaks teha, kas konkreetne räsifunktsioon jagab võtmeid õigesti, kui need võtmed pole ette teada. Kuigi võtmeid endid teatakse harva enne räsifunktsiooni valimist, on tavaliselt teada mõned nende võtmete omadused, mis mõjutavad nende levikut. Vaatame räsifunktsiooni määramise levinumaid meetodeid.

Jagamise meetod. Algandmed on mingi täisarvuline võti võti ja laua suurus m. Selle funktsiooni tulemus on jääk, kui see võti jagatakse tabeli suurusega. Funktsiooni üldvaade:

int h(klahv int, int m) (

tagastusvõti % m; // Väärtused

Sest m= 10 räsifunktsioon tagastab võtme vähima tähendusega numbri.

Sest m= 100 räsifunktsioon tagastab võtme kõige vähem olulised kaks numbrit.

Lisandmeetod, milles võti on märgistring. Räsifunktsioonis teisendatakse string täisarvuks, liites kõik märgid ja tagastades jäägi pärast jagamist m(tavaliselt laua suurus m= 256).

int h(char *klahv, int m) (

Kokkupõrked tekivad stringides, mis koosnevad samast märgikomplektist, näiteks abc Ja Takso.

Seda meetodit saab veidi muuta, saades tulemuse ainult võtmestringi esimese ja viimase märgi summeerimisel.

int h(char *klahv, int m) (

int len = strlen(võti), s = 0;

if (len< 2) // Если длина ключа равна 0 или 1,

s = võti; // tagastusklahv

s = klahv + klahv;

Sel juhul tekivad kokkupõrked ainult liinidel, näiteks abc Ja amc.

Keskmise ruudu meetod, milles võti on ruudus (korrutatud iseendaga) ja indeksina kasutatakse saadud väärtuse mitut keskmist numbrit.

Näiteks võti on 32-bitine täisarv ja räsifunktsioon tagastab oma ruudu keskmised 10 bitti:

int h(klahv int) (

võti >>= 11; // Loobu 11 kõige väiksema tähtsusega bitti

tagastusvõti % 1024; // Tagastab 10 vähima tähtsusega bitti

Eksklusiivne VÕI-meetod reaklahvide jaoks (tavaliselt tabeli suurus m=256). See meetod sarnaneb aditiivse meetodiga, kuid eristab sarnaseid sõnu. Meetod seisneb selles, et "eksklusiivne VÕI" toiming rakendatakse järjestikku stringi elementidele.

IN kordamismeetod lisaks kasutatakse juhuslikku reaalarvu r intervallist . Kui see toode korrutada tabeli suurusega m, siis annab tulemuseks oleva korrutise täisarvuline osa väärtuse vahemikus 0 kuni m–1.

int h(klahv int, int m) (

double r = klahv * rnd();

r = r – (int)r; // Vali murdosa

Üldiselt suurte väärtuste puhul m räsifunktsiooni genereeritud indeksid on laialt levinud. Veelgi enam, matemaatiline teooria väidab, et jaotus on ühtlasem, kui m on algarv.

Vaadeldavates näidetes räsifunktsioon i = h(võti) määrab ainult asukoha, kust kirjet võtmega otsida (või algselt tabelisse paigutada). võti. Seetõttu peab räsiskeem sisaldama konfliktide lahendamise algoritm , mis määrab toimingute järjekorra, kui asend i = h(võti) on juba hõivatud erineva võtmega kirjega.

Räsiskeemid

Enamiku probleemide puhul on kahel või enamal võtmel sama räsi, kuid nad ei saa räsitabelis sama lahtrit hõivata. Võimalikud on kaks võimalust: kas leida uuele võtmele erinev asukoht või luua iga räsitabeli indeksi jaoks eraldi loend, mis sisaldab kõiki selle registriga seotud võtmeid.

Need valikud esindavad kahte klassikalist skeemi:

– räsimine ahelmeetodil (loenditega) ehk nn mitmemõõtmeline räsimine – aheldamine eraldi loenditega;

– räsimine avatud adresseerimismeetodil lineaarse diskreetiga – lineaarne sondi avatud adresseerimine.

Avatud adresseerimismeetod lineaarse valimiga. Algselt märgitakse kõik räsitabeli lahtrid, mis on tavaline ühemõõtmeline massiiv, hõivamata. Seetõttu kontrollitakse uue võtme lisamisel, kas antud lahter on hõivatud. Kui lahter on hõivatud, siis otsib algoritm ringis, kuni leitakse vaba ruum (“avatud aadress”), s.t. kas homogeensete võtmetega elemendid paigutatakse saadud indeksi lähedusse või tehakse topelträsi, kasutades erinevaid, kuid omavahel seotud räsifunktsioone.

Edaspidi otsides leidke esmalt asukoht võtme järgi i tabelis ja kui võti ei ühti, viiakse järgnev otsing vastavalt konflikti lahendamise algoritmile, alustades asukohast i nimekirja järgi.

Ahel meetod kasutatakse sagedamini kui eelmist Sel juhul räsifunktsiooni abil saadud indeks i käsitletakse indeksina loendite räsitabelis, st. võti võti järgmine kirje kaardistatakse positsioonile i = h(võti) tabelid. Kui asend on vaba, siis asetatakse võtmega element sellesse võti, kui see on hõivatud, siis töötatakse välja konfliktide lahendamise algoritm, mille tulemusena lisatakse sellised võtmed loendisse alates kella i räsitabeli lahter. Näiteks tähistades N –NULL:

Selle tulemusena on meil tabel lingitud loendite või puude massiiviga.

Räsitabeli täitmise (lugemise) protsess on lihtne, kuid elementidele juurdepääs nõuab järgmisi toiminguid:

– indeksi arvutamine i;

– otsi vastavast ahelast.

Otsingu parandamiseks uue elemendi lisamisel saab kasutada sisestamisalgoritmi mitte nimekirja lõpus, vaid koos järjestamisega, s.t. lisage element soovitud asukohta.

Praktikas ülesannete lahendamisel on vaja valida räsifunktsioon i= h(võti), mis kuvab võtmeväärtused võimalikult ühtlaselt võti intervalli kohta, m– räsitabeli suurus. Ja enamasti, kui puudub teave võtmete jaotuse tõenäosuse kohta kirjete vahel, kasutavad nad jagamismeetodit räsifunktsiooni. i = h(võti) = võti%m.

Pöördülesande lahendamisel on ligipääs (otsing) võimalik konkreetsele alamhulgale räsitabelist (räsi struktuur), mis tagab kiire ligipääsu soovitud elemendile räsiaadressi (indeksi) järgi.

Räsimine(mõnikord hashing, inglise räsi) - suvalise pikkusega sisendandmete massiivi teisendamine fikseeritud pikkusega väljundstringiks. Selliseid teisendusi nimetatakse ka räsifunktsioonid või konvolutsioonifunktsioonid, sisendmassiiv – prototüüp, ja teisenduse tulemused on räsi, räsikood, räsipilt, digitaalne sõrmejälg või sõnumi kokkuvõte(Inglise sõnumi kokkuvõte).

Räsifunktsioon– kergesti arvutatav funktsioon, mis teisendab suvalise pikkusega algteate (eelkujutis) fikseeritud pikkusega sõnumiks (räsikujutis), mille jaoks puudub efektiivne kokkupõrkeotsingu algoritm.

Kokkupõrge funktsiooni jaoks h nimetatakse väärtuste paariks x, y, x ≠ y, selline, et h(x) = h(y). See. Räsifunktsioonil peavad olema järgmised omadused:

Antud väärtuse eest h(x) ei leia argumendi väärtust x. Selliseid räsifunktsioone nimetatakse ravi seisukohalt püsiv või tugevas mõttes püsiv;

Antud argumendi jaoks x ei leia teist argumenti y selline, et h(x) = h(y). Selliseid räsifunktsioone nimetatakse kokkupõrkearvutuste osas vastupidav või nõrgas mõttes püsiv.

Juhul, kui räsifunktsiooni väärtus ei sõltu ainult eelpildist, vaid ka privaatvõtmest, nimetatakse seda väärtust sõnumi autentimiskoodiks (MAC), andmete autentimiskoodiks (DAC) või imitatsiooni sisestamine.

Praktikas kasutatakse räsifunktsioone järgmistel eesmärkidel:

Andmete otsimise kiirendamiseks andmebaasis;

Andmete otsimise kiirendamine. Näiteks kui tekstiväljad kirjutatakse andmebaasi, saab nende räsikoodi välja arvutada ja andmed paigutada sellele räsikoodile vastavasse sektsiooni. Siis tuleb andmete otsimisel esmalt välja arvutada teksti räsikood ja saad kohe teada, millisest rubriigist seda otsida, s.t. Peate otsima mitte kogu andmebaasi, vaid ainult selle ühe osa kaudu (see kiirendab otsingut oluliselt).

Räsimise tavaliseks analoogiks võib sel juhul olla sõnade paigutamine sõnaraamatus tähestikulises järjekorras. Sõna esimene täht on selle räsikood ja otsides ei vaata me läbi tervet sõnastikku, vaid ainult soovitud tähega osa.

Räsifunktsiooni arvutusprotseduur (standardalgoritmdiagramm) on toodud järgmisel joonisel.

Joonis 10.1. Räsiväärtuse arvutamise protseduur

1) Algsesse sõnumisse T lisatakse abiinfot (näiteks eelpildi pikkus, abisümbolid jne), et eelpildi pikkus oleks X sai mitmekordseks Lbl, mis on määratletud räsifunktsiooni spetsifikatsiooniga (standard).

2) Räsiprotseduuri lähtestamiseks kasutatakse sünkroonimisteadet y 0.

3) Prototüüp X laguneb n plokid x i(i = 1 .. n) fikseeritud pikkus Lbl, mille üle tehakse sama tüüpi räsiprotseduur f(y i-1 , x i), olenevalt eelmise ploki räsimise tulemusest y i-1.

4) Räsiviis h(T) Originaalne Sõnum T on räsimisprotseduuri tulemus y n, mis saadi pärast viimase ploki töötlemist x n.

10.2. MD5

MD5 Message Digest 5 on 128-bitine räsimisalgoritm, mille töötas välja 1991. aastal Massachusettsi Tehnoloogiainstituudi (MIT) professor Ronald L. Rivest. See on MD4 täiustatud versioon.

Allpool on toodud räsi arvutamise algoritm.

1. Voolu võrdsustamine.

Algsõnumi lõpus pikkus L, lisage üks bitt, seejärel vajalik arv nullbitte, nii et uus suurus L" oli võrreldav 448 modulo 512-ga (L' mod 512 = 448). Nullbittide lisamine toimub isegi siis, kui uus pikkus, sealhulgas üks bitt, on juba võrreldav 448-ga.

2. Sõnumi pikkuse lisamine.

Muudetud sõnumile lisatakse andmete pikkuse 64-bitine esitus (bittide arv sõnumis). Need. sõnumi pikkus T muutub 512 kordseks (T mod 512 = 0). Kui algsõnumi pikkus ületab 2 64 - 1, siis lisatakse ainult alumised 64 bitti. Lisaks kirjutatakse kindlaksmääratud 64-bitise pikkusega esituse jaoks kõigepealt madala järgu 32 bitti, millele järgneb kõrge järgu 32 bitti.

3. Puhvri lähtestamine.

Arvutuste jaoks lähtestatakse 4 muutujat, millest igaüks on 32 bitti ja määratakse algväärtused (kuueteistkümnendsüsteem):

A = 67 45 23 01;
B= EF CD AB 89;
C= 98 BA DC FE;
D = 10 32 54 76.

Need muutujad salvestavad vahepealsete arvutuste tulemused. Esialgne olek ABCD nimetatakse initsialiseerimisvektoriks.

4. Räsiarvutus tsüklis.

Algne sõnum on jagatud plokkideks T, 512 bitti pikk. Iga tsükli ploki jaoks viiakse läbi joonisel 10.2 näidatud protseduur. Algse sõnumi kõigi plokkide töötlemise tulemus 32-bitiste muutujate väärtuste ühendusena ABCD ja sellest saab räsi.

Joonis 10.2. Räsiarvutuse põhiahela samm

Igas voorus muutujate üle ABCD ja lähteteksti plokk T tsüklis (16 iteratsiooni) tehakse sarnased teisendused järgmise skeemi järgi.

Joonis 10.3. Üks ümmargune tsükli iteratsioon

konventsioonid.

1) RF- ümmargune funktsioon, mis määratakse järgmise tabeli järgi.

Tabel 10.1. Ümmargused RF-funktsioonid

2) t j- algse sõnumiploki j-s 32-bitine osa T suur endian;

3) k i- valemiga määratud konstandi täisarv

k i = 2 32 * | sin(i + 16 * (r - 1)) |, (10,1)

kus i on tsükli iteratsiooniarv (i = 1..16);
r – ümmargune arv (r = 1..4).

Patufunktsiooni argumenti mõõdetakse radiaanides.

4) ⊞ – mooduli 2 lisamine 32.

5) <<< s i– tsükliline nihe vasakule s i numbri võrra.

Kasutati algse sõnumiploki 32-bitist osa t j ja tsüklilise vasakpoolse nihke suurus s i sõltuvad iteratsiooninumbrist ja on näidatud järgmises tabelis.

Tabel 10.2. Ümmarguse tsükli etapis kasutatud kogused

Iteratsiooni number		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
1. voor	t j	t 1	t 2	t 3	t 4	t 5	t 6	t 7	t 8	t 9	t 10	t 11	t 12	t 13	t 14	t 15	t 16
1. voor	s i	7	12	17	22	7	12	17	22	7	12	17	22	7	12	17	22
2. voor	t j	t 2	t 7	t 12	t 1	t 6	t 11	t 16	t 5	t 10	t 15	t 4	t 9	t 14	t 3	t 8	t 13
2. voor	s i	5	9	14	20	5	9	14	20	5	9	14	20	5	9	14	20
3. voor	t j	t 6	t 9	t 12	t 15	t 2	t 5	t 8	t 11	t 14	t 1	t 4	t 7	t 10	t 13	t 16	t 3
3. voor	s i	4	11	16	23	4	11	16	23	4	11	16	23	4	11	16	23
4. voor	t j	t 1	t 8	t 15	t 6	t 13	t 4	t 11	t 2	t 9	t 16	t 7	t 14	t 5	t 12	t 3	t 10
4. voor	s i	6	10	15	21	6	10	15	21	6	10	15	21	6	10	15	21

Pärast 4 vooru iga muutuja jaoks uus (muudetud) väärtus ABCD lisab (⊞) originaalile (muutuja väärtus enne 1. ringi).

5. ABCD muutujate baitide ümberkorraldamine. Pärast esialgse sõnumi kõigi plokkide töötlemist tehakse iga muutuja jaoks baidi tagasivahetus.

Otsige kokkupõrkeid.

2004. aastal teatasid Hiina teadlased Wang Xiaoyun, Feng Dengguo, Lai Xuejia ja Yu Hongbo, et nad avastasid haavatavuse algoritmis, mis võimaldas IBM p690) leida kokkupõrkeid.

10.3. Räsipildi saamiseks krüptimise kasutamine

Kokkupõrkekindla räsipildi genereerimiseks saab kasutada plokkšifrites pakutavaid erirežiime (näiteks šifriplokkide y konkateneerimine) või räsifunktsioonis endas komponendina ühte plokkšifri režiimidest ( Näiteks komponendi räsifunktsioonid vastavalt standardile GOST 34.11-94 1 on krüptograafilise teisendusalgoritmi lihtsa asendamise režiim vastavalt punktile 2).

Tuletame meelde, et juhul, kui räsifunktsiooni väärtus ei sõltu ainult prototüübist, vaid ka privaatvõtmest, nimetatakse räsipilti sõnumi autentimiskoodiks (MAC), andmete autentimiskoodiks (DAC) või imitatsiooni sisestamine.

Näitena toome režiimi (šifriploki aheldamine).