Kas ir hashing funkcija. Kriptogrāfijas hash funkcijas

Meklēšanas algoritmi, ko mēs esam uzskatījuši, parasti balstās uz abstraktu salīdzināšanas darbību. No šīs sērijas sadales metode, kas aprakstīta "simbolu tabulās un binārajos meklēšanas kokos", kas tiek glabāti tabulas I-th pozīcijā, kas ļauj jums tieši atsaukties uz to. Ar izplatīšanas meklēšanu atslēgas tiek izmantotas kā masīva indekss, nevis salīdzinājuma operācijas operandi; Pati metode ir balstīta uz to, ka taustiņi ir dažādi veseli skaitļi no tāda paša diapazona kā tabulas indeksiem. Šajā nodaļā mēs apskatīsim hashing (hashing) - paplašinātu izplatīšanas meklēšanas versiju, ko izmanto vairāk tipiskākiem meklēšanas lietojumprogrammām, kur atslēgām nav tik ērti īpašības. Pieteikuma galīgo rezultātu Šī pieeja Tas ir absolūti ne līdzīgi metodēm, kas balstītas uz salīdzinājumu - tā vietā, lai pārvietotos pa vārdnīcu datu struktūrām, salīdzinot galvenos meklēšanas taustiņus elementos, mēs cenšamies atsaukties uz galda vienumiem tieši, veicot aritmētisko atslēgu konversiju uz galda adresēm.

Meklēšanas algoritmi, izmantojot hashing sastāv no divām atsevišķām daļām. Pirmais solis ir aprēķināt hash funkciju (hash funkciju), kas pārveido tabulas meklēšanas atslēgu. Ideālā gadījumā dažādas atslēgas būtu jāparāda uz dažādām adresēm, bet bieži vien divas vai vairākas dažādas atslēgas var dot tādu pašu adresi tabulā. Tāpēc otrā daļa meklēšanas pēc metodes hashing ir process izšķirtspēju sadursmju (sadursmes izšķirtspēju), kas apstrādā šādus taustiņus. Vienā no konfliktu risināšanas metodēm, kuras mēs izskatīsim šajā nodaļā, tiek izmantoti savienoti saraksti, tāpēc tas atrod tiešu lietošanu dinamiskajās situācijās, kad ir grūti iepriekš paredzēt meklēšanas atslēgu skaitu. Citās divās sadursmes izšķirtspējas metodēs, kas ir ļoti sasniegts veiktspēja Meklēt, jo elementi tiek saglabāti fiksētā masīvā. Mēs izskatīsim šo metožu uzlabošanas metodi, ļaujot tos izmantot un gadījumos, kad nav iespējams iepriekš paredzēt tabulas lielumu.

Hashing ir labs līdzsvars starp laiku un atmiņu. Ja nav nekādu ierobežojumu izmantoto atmiņas apjomu, jebkuru meklēšanu varētu veikt, izmantojot tikai vienu atmiņas piekļuvi, vienkārši izmantojot atslēgu kā atmiņas adresi, kā ar izplatīšanas meklēšanu. Tomēr šis ideālais gadījums parasti ir nesasniedzams, jo garās atslēgas var būt nepieciešama milzīga atmiņa. No otras puses, ja nebūtu ierobežojumu vadības laiks, Tas būtu iespējams ar minimālo atmiņu, izmantojot secīgu meklēšanas metodi. Hashing ir veids, kā izmantot pieņemamu skaitu gan atmiņu, gan laiku, un panākt līdzsvaru starp šīm divām ekstremālajām prasībām. Jo īpaši jūs varat atbalstīt jebkuru līdzsvaru, vienkārši mainot tabulas lielumu un nepārrakstiet kodu un neizvēloties citus algoritmus.

Hashing ir viens no klasiskajiem datorzinātņu uzdevumiem: tās dažādie algoritmi tiek pētīti detalizēti un tiek plaši izmantoti. Mēs redzēsim, ka vispār nav grūti pieņēmumi, jūs varat cerēt uz atbalstu darbībām, lai atrastu un ielīmētu simbolu tabulās ar pastāvīgu izpildes laiku, neatkarīgi no tabulas lieluma.

Šī paredzamā vērtība ir teorētiskā veiktspēja optimum, lai īstenotu simbolu tabulu, bet hash joprojām nav panaceja divu galveno iemeslu dēļ. Pirmkārt, vadības laiks Atkarīgs no atslēgas garuma, kas reālajās lietojumprogrammās, izmantojot garas atslēgas var būt nozīmīgas. Otrkārt, hashing nesniedz efektīvu citu darbību īstenošanu ar simbolu tabulām, piemēram, izvēli vai šķirošanu. Šajā nodaļā mēs sīki izskatīsim šos un citus jautājumus.

Hash funkcija

Pirmkārt, ir nepieciešams, lai atrisinātu uzdevumu aprēķināt hash funkciju, kas pārvērš atslēgas uz galda adresi. Parasti šī aritmētiskā aprēķina īstenošana neatspoguļo sarežģītību, taču joprojām ir nepieciešams ievērot aprūpi, lai neiesaistītos dažādos zemos izaicinājumos. Ja ir tabula, kas var saturēt M elementus, jums ir nepieciešama funkcija, kas pārveido atslēgas veseliem skaitļiem diapazonā. Ideālajai hash funkcijai jābūt viegli aprēķinātai un jābūt līdzīgai nejaušai funkcijai: attiecībā uz visiem argumentiem, rezultāti ir līdzvērtīgi.

Hash funkcija ir atkarīga no atslēgas veida. Stingri runājot, atsevišķa hash funkcija prasa atsevišķu atslēgu veidu. Lai palielinātu efektivitāti, parasti ir vēlams izvairīties no veidiem, sazinoties ar ideju par bināro atslēgu prezentāciju mašīnas vārda kā vesels skaitlis, ko var izmantot aritmētiskos aprēķinos. Hashing parādījās pirms augsta līmeņa valodu - uz agrīnajiem datoriem bija parastais jautājums, lai apsvērtu jebkuru vērtību kā virknes atslēgu, tad kā vesels skaitlis. Dažās augsta līmeņa valodās ir grūti izveidot programmas, kas ir atkarīgas no konkrēta datora atslēgu prezentācijas, jo šādas programmas būtībā ir atkarīgas no mašīnām, un tāpēc tās ir grūti nodot citam datoram. Parasti HSHSH funkcijas ir atkarīgas no galvenajiem konversijas procesa uz veseliem skaitļiem, tāpēc ir grūti vienlaikus nodrošināt mašīnas neatkarību un efektivitāti hashing ieviešanā. Parasti var pārveidot vienkāršus veselus skaitlim vai peldošus punktu tipa taustiņus, izmantojot tikai vienu mašīnu darbību, bet virknes atslēgas un cita veida savienojuma atslēgas prasa augstas izmaksas un lielāku uzmanību efektivitātei.

Iespējams, vienkāršākā situācija ir tad, kad taustiņi ir skaitļi ar peldošo punktu no fiksētā diapazona. Piemēram, ja taustiņi ir numuri, lieli 0 un mazāki 1, to var vienkārši reizināt ar m, noapaļot rezultātu uz mazāku veselu skaitli un iegūt adresi diapazonā no 0 līdz m - 1; Šis piemērs ir parādīts 1. attēlā. 14.1. Ja atslēgas ir lielākas par S un mazāk nekā t, tos var samazināt, atskaitot s un dalot uz TS, kā rezultātā tie nonāk vērtību diapazonā no 0 līdz 1, un pēc tam reizina m un iegūt adrese tabulā.

Fig. 14.1.

Lai pārvērstu numeriku ar peldošo punktu robežās no 0 līdz 1 tabulas indeksiem, kuru lielums ir 97, reizinot šos skaitļus līdz 97. Šajā piemērā, trīs konflikti notika: indeksiem, kas ir vienāds ar 17, 53 un 76. Hash vērtības nosaka vecākās atslēgas izplūdes, jaunākas izplūdes nav nevienas lomas. Viens no hash funkcijas attīstības mērķiem ir novērst šādu nelīdzsvarotību, lai aprēķināšanas laikā tiktu ņemta vērā katra budžeta izpildes apstiprināšana.

Ja taustiņi ir W-bit veseli skaitļi, tos var pārvērst par peldošiem punktu numuriem un dalīts ar 2 W, lai iegūtu peldošās punktu skaitu diapazonā no 0 līdz 1, un pēc tam reiziniet līdz m, kā iepriekšējā punktā. Ja peldošās punktu darbības aizņem daudz laika, un skaitļi nav tik augsti, lai novest pie pārplūdes, to pašu rezultātu var iegūt, izmantojot veselu skaitļu aritmētiskās operācijas: jums ir nepieciešams reizināt atslēgu uz m, un pēc tam veikt pāreju uz Tiesības uz w noplūdēm, lai sadalītu 2 W (vai, ja reizinājums izraisa pārplūdi, maiņu un pēc tam reizināšanu). Šādas metodes ir bezjēdzīgas hashing, ja vien taustiņi ir vienmērīgi sadalīti pēc diapazona, jo hash vērtību nosaka tikai ar galveno ciparu.

Vairāk vienkārši I. efektīva metode W-bit veseliem skaitļiem - viena no varbūt visbiežāk izmantotajām hashing metodēm - izvēle kā lieluma M tabula ar vienkāršu numuru un aprēķinot atlikumu no dalot uz m, t.e. H (k) \u003d k režīms jebkuram veselam skaitlim KEY K. Šo funkciju sauc par moduļu hash funkciju. Tas ir ļoti viegli aprēķināt (K% m c ++), un tas ir efektīvs, lai panāktu vienotu galveno vērtību sadalījumu starp mazākiem M. Neliela piemērs ir parādīts 1. attēlā. 14.2.

Fig. 14.2.

Trīs labajās kolonnās, rezultāts 7 bitu taustiņiem, kas parādīti kreisajā pusē, izmantojot šādas funkcijas:

v% 97 (pa kreisi)

v% 100 (centrs) un

(int) (a * v)% 100 (pa labi), \\ t

kur a \u003d .618033. Tabulas izmēri šīm funkcijām ir attiecīgi 97, 100 un 100. vērtības izskatās nejauši (jo taustiņi ir nejauši). Otrā funkcija (V% 100) izmanto tikai divus galējus labos ciparus taustiņus, un tāpēc par nejaušiem taustiņiem var parādīt zemu veiktspēju.

Modulārā hashing attiecas uz peldošo punktu taustiņiem. Ja atslēgas pieder nelielam diapazonam, tos var samazināt skaitļos no diapazona no 0 līdz 1, 2 W, lai iegūtu W-bitu veselu skaitļu vērtības un pēc tam izmantojiet moduļu hash funkciju. Vēl viena iespēja ir vienkārši izmantot moduļu hash funkciju bināro galveno prezentāciju (ja pieejams).

Modulārā hashing tiek piemērota visos gadījumos, kad piekļuve bitiem, no kuriem atslēgas sastāv, neatkarīgi no tā, vai tie ir veseli skaitļi, ko attēlo mašīnas vārds, simbolu, kas iepakoti mašīnas vārdos vai ko pārstāv jebkurš cits iespējams opcija. Random simbolu secība, kas iesaiņota mašīna Word nav tieši tāds pats kā nejauša vesela atslēgas, jo ne visas izplūdes tiek izmantotas kodēšanai. Bet abi šie veidi (un jebkura cita veida atslēga kodēta tādā veidā, lai ietilptu mašīnas vārdu), var veikt, lai izskatītos kā nejauši indeksi nelielā tabulā.

Galvenais iemesls atlasei kā lieluma M Hash tabula ar vienkāršu skaitu moduļu hashing ir parādīts 1. attēlā. 14.3. Šajā piemērā simboliskie dati ar 7 bitu kodēšanu, atslēga tiek interpretēta kā numurs ar bāzi 128 - ar vienu ciparu katrai rakstzīmei galvenajā rakstzīmi. Tagad vārds atbilst skaitam 1816567, ko var rakstīt arī kā

tā AS ASCII koda simboli N, O un W atbilst skaitļiem 1568 \u003d 110, 1578 \u003d 111 un 1678 \u003d 119. Tabulas M \u003d 64 lielums šāda veida atslēga ir neveiksmīga, jo pievienojot X vērtībām, vairākiem 64 (vai 128), nemaina vērtību X MOD 64 - jebkurai atslēgai, hash funkcijas vērtība ir Šīs atslēgas pēdējo 6 ciparu vērtība. Protams, laba hash funkcija jāņem vērā visas galvenās izplūdes, jo īpaši simboliskiem taustiņiem. Līdzīgas situācijas var rasties, ja m satur reizētāju, kas ir grāds 2. Vienkāršākais veids Izvairieties no tā - izvēlieties tik vienkāršu numuru.

Fig. 14.3.

Katrā šīs tabulas rindā jūs esat: 3 burtu vārds, šī vārda prezentācija ASCII kodā kā 21 bitu skaits oktānā un decimāldaļu formas un standarta moduļu hash funkcijas 64. un 31. tabulas izmēriem (divi) Extreme kolonna pa labi). 64. tabulas lielums noved pie nevēlamiem rezultātiem, jo \u200b\u200btiek izmantotas tikai labās galvenās izplūdes, lai iegūtu hash vērtību, un burti vārdos parastās valodas vārdiem ir nevienmērīgi izplatīti. Piemēram, visi vārdi, kas apveltīti ar burtu Y atbilst hash vērtībai 57. un, gluži pretēji, vienkārša vērtība 31 izraisa mazāk konfliktu tabulā vairāk nekā divas reizes mazāk.

Modulārā hashing ir ļoti viegli īstenot, izņemot to, ka tabulas izmēram jābūt vienkāršam skaitlim. Dažām lietojumprogrammām jūs varat būt apmierināts ar nelielu viena pazīstamu vienkāršu numuru vai meklējot slaveno primāro numuru sarakstā, kas ir tuvu vēlamajam galda lielumam. Piemēram, numuri ir 2 t - 1, ir vienkārši t \u003d 2, 3, 5, 7, 13, 17, 19 un 31 (un bez citām vērtībām t< 31 ): это известные простые числа Мерсенна. Чтобы динамически распределить таблицу нужного размера, нужно вычислить простое число, близкое к этому значению. Такое вычисление нетривиально (хотя для этого и существует остроумный алгоритм, который будет рассмотрен в части 5), поэтому на практике обычно используют таблицу заранее вычисленных значений (см. рис. 14.4). Использование модульного хеширования - не vienīgais iemeslsuz kura tabulas lielums ir vērts izdarīt vienkāršu skaitu; Vēl viens iemesls tiek izskatīts 14.4. Iedaļā.

Fig. 14.4.

Šī tabula ir lielākais vienkāršais skaits, kas ir mazāks par 2 n, par Var izmantot dinamiskai hash galda izplatīšanai, kad ir nepieciešams, lai tabulas izmērs ir vienkāršs numurs. Jebkurai dotajai pozitīvajai vērtībai diapazonā šajā tabulā var izmantot, lai noteiktu vienkāršu numuru, kas atšķiras no tā mazāk nekā 2 reizes.

Vēl viens veselu skaitļa atslēgu iemiesojums ir multiplikatīvu un moduļu metožu kombinācija: jums ir nepieciešams, lai reizinātu atslēgu uz nemainīgu diapazonā no 0 līdz 1, un pēc tam veikt sadalījumu pa moduli M. Citiem vārdiem sakot, jums ir jāizmanto funkcija. Starp galvenajām numuru sistēmas vērtībām, m un efektīvo bāzi, ir attiecības, kas teorētiski var izraisīt anomālu uzvedību, bet, ja jūs izmantojat patvaļīgu vērtību A Īsts pielikums Maz ticams, ka ir kādas problēmas. Bieži vien ir izvēlēta vērtība f \u003d 0.618033 ... (Golden sadaļa).

Ir pētītas daudzas citas izmaiņas šajā tēmā, jo īpaši, hash funkcijas, kuras var īstenot, izmantojot tādus efektīvus mašīnas norādījumus, piemēram, maiņas un maskas izvēli (skatīt saites).

Daudzās lietojumprogrammās, kas izmanto simbolu tabulas, atslēgas nav numuri un ne vienmēr ir īsi; Biežāk ir burtciparu līnijas, kas var būt ļoti garš. Nu, kā aprēķināt hash funkciju vārdam kā Averylongey?

7 bitu ASCII kodā šis vārds atbilst 84 bitu skaitam (saskaņot *) 97 \\ cdot 128 ^ (11) & + 118 \\ cdot 128 ^ (10) + 101 \\ cdot 128 ^ (9) + 114 \\ cdot 128 ^ (8) + 121 \\ cdot 128 ^ (7) \\\\- + 108 \\ cdot 128 ^ (6) + 111 \\ cdot 128 ^ (5) + 110 \\ cdot 128 ^ (4) + 103 128 ^ (3) \\\\ un + 107 \\ cdot 128 ^ (2) + 101 \\ cdot 128 ^ (1) + 121 \\ cdot 128 ^ (0), \\ galdati (saskaņot *),

kas ir pārāk liels, lai parastās aritmētiskās funkcijas var veikt ar to vairumā datoru. Un bieži vien tas ir nepieciešams, lai apstrādātu un daudz ilgāku taustiņu.

Lai aprēķinātu moduļu hash funkciju ilgu taustiņiem, tie tiek pārvērsti fragmentā uz vienu fragmentu. Jūs varat izmantot moduļa funkcijas aritmētiskās īpašības un izmantot Gorner algoritmu (skatīt apakšpunktu 4.9 "Abstract datu tipi"). Šī metode ir balstīta uz citu metodi ierakstīšanas numuriem, kas atbilst atslēgām. Attiecībā uz izskatāmo piemēru mēs uzrakstām šādu izteiksmi: sākt (izlīdzināt *) (((((((((((((((((97 \\ t 128 ^ (9) + 114) \\ cdot 128 ^ (8) + 121) \\ cdot 128 ^ (7) \\\\ & + 108) \\ cdot 128 ^ (6) + 111) \\ cdot 128 ^ (5) + 110) \\ cdot 128 ^ (4) + 103) \\ cdot 128 ^ (3) \\\\ un + 107) \\ cdot 128 ^ (2) + 101) \\ cdot 128 ^ (1) + 121. \\ galdati (saskaņot *)

Tas ir, decimālskaitli, kas atbilst virknes rakstzīmju kodēšanai, var aprēķināt, skatoties to no kreisās uz labo, reizinot uzkrāto vērtību līdz 128, un pēc tam pievienojot nākamā simbola koda vērtību. Garas virknes gadījumā šī aprēķina metode galu galā radīs lielu vienu, ko var iesniegt datorā. Tomēr šis skaitlis nav nepieciešams, jo tikai (mazs) atlikums ir vajadzīgs no tās dalīšanas uz M. Rezultātu var iegūt, pat neuzturot uzkrāto vērtību, jo Jebkurā laikā aprēķinu var izmest vairākos M - katru reizi, kad veicat reizināšanu un papildus, ir nepieciešams uzglabāt tikai atlikumu no nodaļas Moduļa M. Rezultāts būs tāds pats kā, ja mums būtu spēja aprēķināt Ilgstošs un pēc tam veiciet nodaļu (skat. Exercise 14.10). Šis novērojums izraisa tiešu aritmētisko metodi, lai aprēķinātu moduļu hash funkcijas garām līnijām - skatīt programmu 14.1. Šī programma izmanto citu, pēdējo mezglu: Bāzes 128 vietā tā izmanto vienkāršu numuru 127. Šīs pārmaiņas iemesls tiek ņemts vērā nākamajā punktā.

Ir daudzi veidi, kā aprēķināt hash funkcijas aptuveni ar tādām pašām izmaksām kā moduļu hashing, izmantojot Gorner metodi (viens vai divi aritmētiskās operācijas Par katru simbolu atslēgā). Par izlases taustiņiem šīs metodes praktiski nav atšķirīgas viena no otras, bet reālie taustiņi ir reti nejauši. Iespēja pēc izmaksām zemām izmaksām, lai sniegtu reālas atslēgas izlases veida noved pie randomizētu maizes algoritmu apsvērumiem, jo \u200b\u200bmums ir vajadzīgas hash funkcijas, kas rada izlases tabulas indeksus neatkarīgi no galvenā izplatīšanas. Nav grūti organizēt randomizāciju, jo tas nav nepieciešams burtiski ievērot modulārās sajaukšanas definīciju - tas ir nepieciešams tikai, lai aprēķinātu veselu skaitu mazāku m, tika izmantotas visas galvenās izplūdes.

M \u003d 96 un a \u003d 128 (augšpusē)

M \u003d 97 un a \u003d 128 (centrs) un

M \u003d 96 un a \u003d 127 (zemāk)

Nevienmērīgais sadalījums pirmajā gadījumā ir nevienmērīgas izmantošanas rezultāts un nevienmērības saglabāšana sakarā ar to, ka tabulas lielums un reizinātājs reizinātājs 32. Divi citi piemēri izskatās nejauši, jo tabulas lielums un reizinātājs ir savstarpēji vienkārši numuri.

Programma 14.1 parāda vienu no veidiem, kā to izdarīt: izmantojot vienkāršu bāzi, nevis pakāpi 2 un vesels skaitlis atbilst ASCII attēlošanai virknes. Att. 14.5. 14.5 Ir pierādīts, kā šīs izmaiņas uzlabo tipisku virkņu taustiņu izplatīšanu. Teorētiski hash vērtības, ko rada programma 14.1, var sniegt sliktus rezultātus galda izmēriem, kas ir vairāki 127 (kaut arī praksē, visticamāk, būs gandrīz nemanāma); Lai izveidotu nejaušinātu algoritmu, būtu iespējams izvēlēties reizinātāja vērtību nejauši. Vēl efektīvāka pieeja ir izmantot izlases vērtības koeficientu aprēķinā un dažādas izlases vērtības katram galvenajam skaitlim. Šī pieeja sniedz randomizētu algoritmu, ko sauc par universālo hashing (universālo hashing).

Teorētiski ideāla universālā hash funkcija ir funkcija, kurai sadursmes varbūtība starp diviem dažādiem galdiem ar dimensiju m ir precīzi vienāds ar 1 / m. Var pierādīt, ka izmantošana kā koeficients A programmā 14.1 nav fiksēta patvaļīga vērtība, un secīgas atšķirīgās vērtības secības pārvērš moduļu hashing par universālu hash funkciju. Tomēr izmaksas, kas saistītas ar jaunu izlases numura ģenerēšanu katram simbolam, parasti ir nepieņemama. Praksē ir iespējams panākt kompromisu, kas parādīts programmā 14.1, neatrodot dažādus izlases numurus katram atslēgu simbolam, un dažādas koeficientus, izmantojot vienkāršu pseido-izlases secību.

Mēs apkoposim: Lai īstenotu abstraktu rakstzīmju tabulu, lai izmantotu hashing, vispirms ir jāizvērtē abstrakta tipa saskarne, pagriežot to uz hash darbību, kas parāda taustiņus, kas nav negatīvi veseli skaitļi, mazāks tabulas izmērs M.

Kā daļu no šī raksta, es jums pateiks kas ir hashKāpēc tas ir nepieciešams, kur un kā tas tiek izmantots, kā arī visvairāk labi pazīstami piemēri.

Daudzas problēmas informācijas tehnoloģiju jomā ir ļoti svarīgas datu apjomiem. Piemēram, ja jums ir nepieciešams salīdzināt divus failus ar izmēru 1 KB un diviem 10 GB failiem, tad tas ir pilnīgi atšķirīgs laiks. Tāpēc algoritmi, kas ļauj darboties ar īsākiem un ietilpīgiem vērtībām, tiek uzskatīti par ļoti populāriem.

Viena šādas tehnoloģijas ir hashing, kas ir atradusi tās izmantošanu, risinot uzdevumu masu. Bet, es domāju, ka jūs, kā parasts lietotājs, joprojām ir nesaprotams, kāda veida zvērs tas ir vajadzīgs. Tāpēc es centīšos izskaidrot visus vienkāršākos vārdus.

Piezīme: Materiāls ir paredzēts parastiem lietotājiem, tomēr nesatur daudzus tehniskus aspektus, lai to pamatotu iepazīšanu vairāk nekā pietiekami.

Kas ir hash vai hashing?

Es sākšu ar noteikumiem.

Hash funkcija, konvāciju funkcija - Šī ir īpaša iezīme, kas ļauj pārvērst patvaļīgu garuma tekstu uz fiksētu garuma kodu (parasti īss digitālais ieraksts).

Sajaukšana - Tas ir avota tekstu pārveidošanas process.

Hash, hash kods, vērtība hash, hash-summa - Tā ir izejas vērtība hash funkciju, tas ir, iegūtais bloks ir fiksēts garums.

Kā redzat, terminiem ir pāris formas apraksts, no kura ir grūti saprast, kāpēc tas viss ir nepieciešams. Tāpēc es nekavējoties sniegšu nelielu piemēru (par citām lietojumprogrammām pateiks nedaudz vēlāk). Pieņemsim, ka jums ir 2 faili 10 GB. Kā jūs varat ātri uzzināt, kuras vajadzības? Varat izmantot faila nosaukumu, bet to ir viegli pārdēvēt. Jūs varat skatīties datumus, bet pēc failu kopēšanas var būt vienādi vai citās sekvencēs. Izmērs, kā jūs pats saprotat, maz var palīdzēt (it īpaši, ja izmēri sakrīt vai jūs neesat aplūkojuši precīzas baitu vērtības).

Tas ir šeit, ka jums ir nepieciešams šis ļoti hash, kas ir īss bloks, kas tiek ģenerēts no avota teksta faila. Šie divi faili 10 GB būs divi atšķirīgi, bet īss hash kodu (kaut kas līdzīgs "Accac43535" un "BBB3232A42"). Izmantojot tos, jūs varat ātri uzzināt vēlamo failu.Pat pēc kopēšanas un nosaukumu kopēšanas.

Piezīme: Sakarā ar to, ka Hash datorā no pasaules un internetā ir ļoti labi zināms jēdziens, tad bieži vien tas viss, kas ir saistīts ar hash, tiek samazināts līdz šim vārdam. Piemēram, frāze "Es izmantoju Hash MD5" tulkojumā nozīmē, ka vietnē vai kaut kur citur izmanto MD5 standarta hashing algoritms.

Hash īpašības

Tagad es jums pastāstīšu par Hash funkciju īpašībām, lai jūs būtu vieglāk saprast, kur tas tiek izmantots un par to, kas jums nepieciešams. Bet pirmā definīcija.

Sadursme - Tā ir situācija, kad viena un tā pati hash summa tiek iegūta diviem dažādiem tekstiem. Kā jūs zināt, kad ir fiksēta garuma bloks, tam ir ierobežots skaits iespējamo vērtību, un tāpēc ir iespējams atkārtot.

Un tagad uz Hash funkciju īpašībām:

1. Tekstu var piegādāt jebkura izmēra tekstā, un izeja ir fiksēta garuma datu bloks. Tas izriet no definīcijas.

2. Tādu pašu tekstu hash-summai jābūt vienādam. Pretējā gadījumā šādas funkcijas ir vienkārši bezjēdzīgas - tas ir līdzīgs izlases numuram.

3. Labai konvolācijas funkcijai jābūt labam sadalījumam. Piekrītu, ka, ja izejas hash lielums, piemēram, ir 16 baiti, tad, ja funkcija atgriež tikai 3 dažādas vērtības jebkuriem tekstiem, tad neietekmē šādu funkciju, un šie 16 baiti (16 baiti ir 2 ^ 128 Iespējas, kas ir aptuveni 3, 4 * 10 ^ 38 grādi).

4. Cik labi funkcija reaģē uz mazākajām izmaiņām avota tekstā. Vienkāršs piemērs. Mainīts 1 burts 10 GB failā, funkcijas vērtība ir atšķirīga. Ja tā nav tā, tad tas ir ļoti problemātiski piemērot šādu funkciju.

5. Sadursmes rašanās varbūtība. Ļoti sarežģīts parametrs, kas aprēķināts noteiktos apstākļos. Bet viņa būtība ir tā, ka tas, kas ir punkts hash funkciju, ja iegūtā hash summa bieži sakrīt.

6. Hasha aprēķina likme. Kas ir partija no konvicences funkcijas, ja tas ir ilgu laiku, lai aprēķinātu? Nē, jo tad faili ir vieglāk salīdzināt vai izmantot citu pieeju.

7. Avota datu atjaunošanas sarežģītība no hash vērtības. Šī īpašība ir specifiskāka nekā kopumā, jo tas nav nepieciešams visur. Tomēr par slavenākajiem algoritmiem, šī īpašība tiek vērtēta. Piemēram, avota fails jūs varat saņemt no šīs funkcijas. Tomēr, ja notiek sadursmju problēma (piemēram, jums ir jāatrod kāds teksts, kas atbilst šādam hasham), tad šī īpašība var būt svarīga. Piemēram, paroles, bet nedaudz vēlāk.

8. Atveriet vai slēgtu avota kodu šai funkcijai. Ja kods nav atvērts, attiecīgo datu atgūšanas sarežģītību, proti, kriptostility. Daļēji tas ir problēma ar šifrēšanu.

Tagad jūs varat doties uz jautājumu, un kāpēc tas viss ir? ".

Kāpēc jums ir nepieciešams hash?

Galvenie mērķi Hash funkcijas ir tikai trīs (vai drīzāk viņu mērķis).

1. Pārbaudiet datu integritāti. Iebildums Šis gadījums Viss ir vienkāršs, šāda funkcija ir jāaprēķina ātri un ļauj ātri pārbaudīt, vai, piemēram, fails, kas lejupielādēts no interneta, pārsūtīšanas laikā nav bojāts.

2. Pieaugiet datu meklēšanas ātrumu. Fiksētā bloka lielums ļauj jums iegūt daudz priekšrocību meklēšanas uzdevumu risināšanā. Šajā gadījumā mēs runājam par to, kas ir tikai tehniski, hash funkciju izmantošana var pozitīvi ietekmēt veiktspēju. Šādām funkcijām ir ļoti svarīga sadursmju iespējamība un laba izplatīšana.

3. Kriptogrāfiskām vajadzībām. Šī suga Konvolūcijas funkcijas tiek izmantotas drošības jomās, kur ir svarīgi, lai rezultāti ir grūti aizstāt vai ja ir nepieciešams sarežģīt uzdevumu iegūt pēc iespējas vairāk. noderīga informācija no hash.

Kur un kā ir piemērots hash?

Kā jūs droši vien jau uzminējāt, ka hash piemēro, risinot ļoti daudzus uzdevumus. Šeit ir daži no tiem:

1. Paroles parasti tiek glabātas ne atklātā veidā, bet kā hash summas, kas ļauj nodrošināt augstāku drošības pakāpi. Galu galā, pat ja uzbrucējs saņems piekļuvi šādai datu bāzei, viņam vēl būs jātērē daudz laika, lai uzņemt atbilstošos tekstus šiem hash kodiem. Šeit ir raksturīga "sākotnējo datu atjaunošanas sarežģītība no hash vērtībām".

Piezīme: Es ieteiktu jums iepazīties ar rakstu ar pāris padomiem, lai uzlabotu paroļu drošību.

2. Programmēšana, tostarp datu bāzēs. Protams, visbiežāk mēs runājam par datu struktūrām, kas ļauj Ātrā meklēšana. Tīrs tehniskais aspekts.

3. Ja datu pārraides dati (ieskaitot internetu). Daudzi protokoli, piemēram, TCP / IP ietver īpašas pārbaudes laukus, kas satur avota ziņojuma hash summu, lai kaut kur radusies neveiksme, tas neietekmēja datu pārraidi.

4. Dažādiem ar drošību saistītiem algoritmiem. Piemēram, hash tiek izmantots elektroniskajos digitālajos parakstos.

5. Lai pārbaudītu failu integritāti. Ja jūs maksājāt uzmanību, bieži vien ir iespējams izpildīt failus internetā (piemēram, arhīvi) papildu apraksti ar hash kodu. Šis pasākums tiek piemērots ne tikai, lai jūs nejauši palaist failu, kas tika bojāts, lejupielādējot no interneta, bet arī ir hostinga vienkāršība. Šādos gadījumos jūs varat ātri pārbaudīt hash un, ja nepieciešams, tad pārspīlējiet failu.

6. Dažreiz, hash funkcijas tiek izmantotas, lai radītu unikālus identifikatorus (kā daļu). Piemēram, saglabājot attēlus vai vienkārši failus, jūs parasti izmantojat hash nosaukumos kopā ar datumu un laiku. Tas ļauj jums nepārrakstīt failus ar tādu pašu nosaukumu.

Faktiski, tālāk, jo biežāk tiek izmantotas hash funkcijas informācijas tehnoloģijas. Galvenokārt sakarā ar to, ka datu apjoms un vislielākās pilnvaras vienkārši datori Stipri satricināja. Pirmajā gadījumā mēs esam vairāk par meklēšanu, un otrajā mēs esam vairāk par drošības jautājumiem.

Slavenās Hash funkcijas

Slavenākais ir šādas trīs hash funkcijas.

Anotācija: Šajā lekcijā ir formulēta jēdziens hash funkcija, kā arī Īss pārskats Algoritmi hash funkciju veidošanai. Turklāt tiek uzskatīts iespēja izmantot bloku algoritmus šifrēšanai, lai izveidotu hash funkciju.

Lekcijas mērķis: iepazīties ar "hash funkcijas" koncepciju, kā arī ar šādu funkciju principiem.

Hash funkcijas jēdziens

Hash funkcija (hash funkcija) Tiek saukta par matemātisku vai citu funkciju, kas par patvaļīgas garuma līnijām aprēķina kādu veselu skaitli vai kādu citu fiksētā garuma virkni. Matemātiski, tas var būt rakstīts kā šis:

kur m ir sākotnējais ziņojums, ko sauc par dažreiz klātun H - rezultāts, ko sauc par hash funkciju (kā arī hash kodu vai digest ziņu (no angļu valodas. ziņu sagremot.)).

Hash funkcijas nozīme ir noteikt parauga raksturīgo iezīmi - hash funkcijas nozīmi. Šai vērtībai parasti ir noteikta fiksēta izmēra, piemēram, 64 vai 128 biti. Hash kodu var vēl vairāk analizēt, lai atrisinātu jebkuru uzdevumu. Piemēram, hashing var izmantot, lai salīdzinātu datus: ja divi hash kodi ir atšķirīgi, tiek garantēti bloki; Ja tas pats masīvs ir tas pats. Kopumā nepārprotamā sarakste starp avota datiem un hash kodu nav saistīts ar faktu, ka hash funkciju skaits vienmēr ir mazāks par ievades iespējām. Tāpēc ir daudz ievades ziņojumu, kas dod tādus pašus hash kodus (šādas situācijas tiek sauktas kolistija). Sadarbību rašanās varbūtība ir svarīga loma hash funkciju kvalitātes novērtēšanā.

Hash funkcijas tiek plaši izmantotas mūsdienu kriptogrāfijā.

Vienkāršāko hash funkciju var sagatavot, izmantojot "2. moduļa summu" darbību šādi: mēs iegūstam ievades virkni, mēs salokām visus baitus ar 2. moduli un baitu rezultāts atgriežas kā hash fuch. Hash funkcijas ilgums būs šajā gadījumā 8 biti neatkarīgi no izejas ziņojuma.

Piemēram, ļaujiet sākotnējam ziņojumam tulkot digitālo skatu, sekojošo (heksadecimālā formātā):

Mēs pārsūtīsim ziņojumu bināro izskatu, rakstīt baitus viens otram un nodot bitus katrā slejā ar 2. moduli:

0011 1110 0101 0100 1010 0000 0001 1111 1101 0100 ---------- 0110 0101

Rezultāts (0110 0101 (2) vai 65 (16)) un būs hash funkcijas vērtība.

Tomēr šāda hash funkcija nevar izmantot kriptogrāfiskiem mērķiem, piemēram, veidošanai elektroniskais parakstsTā kā ir viegli mainīt parakstītās ziņas saturu, nemainot kontrolsummas vērtības.

Tāpēc uzskatītā hash funkcija nav piemērota kriptogrāfiskiem lietojumiem. Kriptogrāfijā, Hash funkcija tiek uzskatīta par labu, ja ir grūti izveidot divus veidus ar tādu pašu hash funkciju, kā arī, ja funkciju produkcija nav skaidri atkarīga no ieejas.

Mēs formulējam galvenās prasības kriptogrāfiskām hash funkcijām:

hash funkcija ir piemērojama ziņai par jebkura izmēra;
funkcijas vērtības aprēķināšana ir pietiekami ātri;
ar labi zināmu hash funkciju, tas būtu grūti (gandrīz neiespējami), lai atrastu piemērotu prototipu m;
ar labi zināmu ziņu, m jābūt grūti atrast citu ziņojumu m "ar tādu pašu vērtību hash funkciju, piemēram, avota ziņojumu;
būtu jābūt grūti atrast jebkuru pāris izlases dažādus ziņojumus ar tādu pašu hash funkciju.

Izveidojiet hash funkciju, kas atbilst visām uzskaitītajām prasībām, nav viegls uzdevums. Ir arī jāatceras, ka funkcijas funkcija ir saņemta ar patvaļīgas izmēra funkciju, un hash rezultāts nav vienlīdzīgs šiem dažādiem izmēriem.

Pašlaik praksē ievades ziņojuma apstrāde tiek izmantoti kā hash funkcijas, un aprēķinot hash vērtību h i par katru m bloku ievades ziņojuma par atkarību no tipa

h i \u003d h (m i, h i-1)

kur h i-1 ir rezultāts, kas iegūts, aprēķinot hash funkciju iepriekšējais bloks Ievades dati.

Rezultātā hash funkcija dod h n ir funkcija no visiem n ieejas blokiem.

Izmantojiet bloku algoritmu šifrēšanu, lai izveidotu hash funkciju

Jūs varat izmantot bloku kā hash funkciju. Ja bloki, ko izmanto kriptogrāfiski bloka algoritms, tad hash funkcija balstās uz tā būs uzticama.

Vienkāršākais veids, kā izmantot bloka algoritmu, lai iegūtu hash kodu, ir ziņojuma šifrēšana CBC režīmā. Šajā gadījumā ziņojums ir attēlots kā bloku secība, kuru garums ir vienāds ar šifrēšanas algoritma vienības garumu. Vajadzības gadījumā pēdējā vienība tiek papildināta ar pareizajiem nullēm, lai vēlamā garuma vienība ir. Hash būs pēdējais šifrētais teksta bloks. Ievērojot uzticamu bloku šifrēšanas algoritmu, iegūtā hash vērtība būs šādas īpašības:

gandrīz neiespējami, nezinot hash vērtību šifrēšanas atslēgu aprēķinu konkrētai atklātai informācijas klāstam;
tas ir praktiski neiespējami, nezinot šifrēšanas atslēgu atvērto datu izvēli saskaņā ar norādīto hash vērtību.

Šādā veidā veidotā korpusa vērtība parasti tiek saukta imitovka vai autentifikators un izmanto, lai pārbaudītu ziņojuma integritāti. Tādējādi simulators ir kontroles kombinācija, kas ir atkarīga no atvērtiem datiem un slepenas galvenās informācijas. Imitovka lietošanas mērķis ir atklāt visas nejaušās vai apzinātās izmaiņas informācijas klāstā. Vērtība, kas iegūta ar hash funkciju, apstrādājot ievades ziņojumu, ir pievienots ziņai brīdī, kad ir zināms, ka ziņojums ir pareizs. Saņēmējs pārbauda ziņojuma integritāti, aprēķinot saņemtā ziņojuma imitantiju un salīdzinot to ar iegūto hash kodu, kas jānosūta drošā veidā. Viens no tiem droši veidi Varbūt Imitovka šifrēšana slēgta atslēga sūtītājs, ti. Izveidot parakstu. Ir iespējams arī šifrēt iegūto hash koda algoritmu simetriskai šifrēšanai, ja sūtītājam un saņēmējam ir vispārējs simetriskā šifrēšanas atslēga.

Norādītais Imitovka iegūšanas un izmantošanas process ir aprakstīts vietējā standarta GOST 28147-89. Standarts piedāvā izmantot jaunākos 32 bitus bloka, kas iegūta pēc izejas šifrēšanas darbību visu ziņu šifra bloka sajūga režīmā, lai uzraudzītu integritāti nosūtīto ziņu. Tādā pašā veidā jebkuru bloku var izmantot, lai radītu imitavka simetriskā šifrēšanas algoritms.

Vēl viens iespējamais veids, kā izmantot bloku šifrētu, lai radītu hash kodu, ir šāds. Avota ziņojums tiek apstrādāts sērijas blokos. Pēdējais bloks, ja nepieciešams, papildina nulles, dažreiz pēdējā blokā jūs piešķirat ziņojuma garumu formā binārie numuri. Katrā posmā šifrējiet iepriekšējā posmā iegūto hash vērtību, izmantojot pašreizējo ziņojumu bloku kā atslēgu. Pēdējā ievadītā šifrētā vērtība būs galīgā hash.

Faktiski vairākas vairākas shēmas par bloka šifra izmantošanu, lai izveidotu hash funkciju. Ļaujiet m i būt avota bloka vienība, hi - hash funkcijas vērtība I līmeņa posmā, f ir šifrēšanas algoritma bloks, ko izmanto vienkāršā nomaiņas režīmā - 2. moduļa papildināšanas darbība. Tad ir iespējams, Piemēram, šādas hash funkciju veidošanas shēmas:

Visās šajās diagrammās, ģenerētās hash vērtības garums ir vienāds ar bloka garumu šifrēšanas laikā. Visi šie, kā arī dažas citas shēmas, lai izmantotu bloka algoritmu šifrēšanai, lai aprēķinātu hash vērtības, var izmantot praksē.

Galvenais trūkums HASH funkcijas, kas paredzētas, pamatojoties uz bloka algoritmiem, ir salīdzinoši zems ātrums Darbs. Nepieciešamais kriptoskops var nodrošināt arī mazāku skaitu operāciju ievades datiem. Ir ātrākas hashing algoritmi, kas ir neatkarīgi no nulles, pamatojoties uz kriptiskās pretestības prasībām (visbiežāk no tām - MD5, SHA-1, SHA-2 un GOST R 34,11-94).

Kas ir hash?Hash funkcija tiek saukta par matemātisko pārveidošanu par informāciju īsā, noteiktā garuma virknē.

Kāpēc jums tas ir nepieciešams?Analīze, izmantojot Hash funkcijas, bieži tiek izmantota, lai uzraudzītu svarīgu failu integritāti. operētājsistēma, Svarīgas programmas, svarīgi dati. Kontroli var izdarīt gan pēc vajadzības, gan regulāri.

Kā tas ir darīts?Sākumā nosaka, kuras integritāte ir jāuzrauga. Par katru failu, tas tiek aprēķināts, lai aprēķinātu vērtību tās hash pār īpašu algoritmu, vienlaikus saglabājot rezultātu. Pēc nepieciešamā laika tiek veikts līdzīgs aprēķins, un rezultāti tiek salīdzināti. Ja vērtības atšķiras, tas nozīmē, ka informācija ietverta failā ir mainīta.

Kādas īpašības vajadzētu būt hash funkcijai?

jāspēj veikt patvaļīgas garuma datu pārveidojumus, lai noteiktu;
jābūt atvērtam algoritmam, lai varētu izpētīt tās kriptoskopu;
jābūt vienpusējam, tas ir, nav jābūt matemātiskām iespējām, nosakot avota datus;
ir "pretoties" konfliktiem, tas ir, tai nevajadzētu dot tādas pašas vērtības ar dažādiem ievades datiem;
nevajadzētu prasīt lielus skaitļošanas resursus;
ar mazākās izmaiņas ievades datus, rezultāts ir jāmaina būtiski.

Kādas ir populārās hashing algoritmi?Tiek izmantotas šādas hash funkcijas:

CRC - ciklisks liekais kods vai kontrolsumma. Algoritms ir ļoti vienkāršs, ir liels skaits atšķirības atkarībā no nepieciešamā izejas garuma. Nav kriptogrāfijas!
MD 5 ir ļoti populārs algoritms. Kā viņš iepriekšējā versija MD 4 ir kriptogrāfiska funkcija. Hesha izmērs 128 biti.
SHA -1 ir arī ļoti populāra kriptogrāfijas funkcija. Hesha izmērs 160 biti.
GOST R 34.11-94 - Krievijas kriptogrāfiskais standarts hash funkciju aprēķināšanai. Hesha izmērs 256 biti.

Kad šie algoritmi var izmantot sistēmas administratoru?Bieži vien lejupielādējot jebkuru saturu, piemēram, programmas no ražotāja, mūzikas, filmu vai citas informācijas. kontroles summasaprēķina saskaņā ar konkrētu algoritmu. Drošības apsvērumu dēļ pēc lejupielādes ir nepieciešams veikt neatkarīgu hash funkcijas aprēķinu un salīdzināt vērtību ar to, kas ir norādīts tīmekļa vietnē vai lietojumprogrammā failā. Vai jūs kādreiz to izdarījāt?

Kas ir ērtāk skaitīt hash?Tagad ir liels skaits līdzīgu komunālo pakalpojumu gan maksā, gan brīvi izmantot. Man personīgi patika Hashtab. Pirmkārt, lietderība instalēšanas laikā ir iebūvēta cilnes formā uz failu īpašībām, otrkārt, ļauj izvēlēties lielu skaitu maizes algoritmu, un treškārt, ir bezmaksas privātai nekomerciālai lietošanai.

Kas ir krievu?Kā minēts iepriekš Krievijā, ir standarta hashing GOST R 34,11-94, kas tiek izmantots visur daudzos ražotāju informācijas drošības instrumentu. Viens no šiem līdzekļiem ir sākotnējās valsts noteikšanas un kontroles programma. programmatūras pakotne "Fix". Šī programma ir līdzeklis, lai kontrolētu SZI piemērošanas efektivitāti.

Fix (2.0.1 versija) Windows 9x / NT / 2000 / XP

Aprēķiniet norādīto failu pārbaudes ar vienu no 5 ieviestajiem algoritmiem.
Fiksēšana un turpmākā programmatūras paketes stāvokļa kontrole.
Programmatūras pakotnes versiju salīdzinājums.
Katalogu fiksācija un kontrole.
Uzraudzības izmaiņas noteiktos failos (katalogi).
Ziņojumu veidošana TXT, HTML, SV formātos.
Produktam ir sertifikāts FSTEC uz NDV 3 No. 913 līdz 2013. gada 1. jūnijam.

Un kā par EDS?Funkcijas aprēķināšanas rezultāts kopā ar lietotāja slepeno atslēgu iekļūst kriptogrāfiskā algoritma ievadīšanā, kur tiek aprēķināts elektroniski ciparparaksts. Stingri runājot, Hash funkcija nav daļa no EDS algoritma, bet bieži tas tiek darīts tieši, lai izslēgtu uzbrukumu, izmantojot publisko atslēgu.

Pašlaik daudzas e-komercijas lietojumprogrammas ļauj uzglabāt lietotāja slepeno atslēgu slēgtā marķiera apgabalā (Rutoken, Eastoken) bez tehniskās spējas to iegūt no turienes. Tokenam ir ļoti ierobežota atmiņa, ko mēra kilobaitos. Lai parakstītu dokumentu Nav iespējams nodot dokumentu pašu marķieri, bet, lai pārsūtītu dokumenta hash token un pie izejas, lai iegūtu EDS ir ļoti vienkāršs.

Jautājumi:

1. Hash funkcijas jēdziens.

2. Izmantojiet bloku algoritmus šifrēšanai, lai izveidotu hash funkciju.

3. A algoritmu pārskatīšana hash funkciju veidošanai.

1. Hash funkcijas jēdziens

Hash funkcija(Hash funkcija) sauc par matemātisku vai citu funkciju, kas patvaļīgas garuma līnijām aprēķina kādu veselu skaitli vai kādu citu fiksētā garuma virkni. Matemātiski, tas var būt rakstīts kā šis:

h. \u003d H (m) ,

kur M. - dažreiz sauca par avota ziņojumu klāt , bet h. - rezultāts, ko sauc par hash funkcijas vērtību (kā arī hash kodu vai digest ziņu (no angļu valodas. ziņu sagremot.)).

Hash funkcijas nozīme ir noteikt parauga raksturīgo iezīmi - hash funkcijas nozīmi. Šai vērtībai parasti ir noteikta fiksēta izmēra, piemēram, 64 vai 128 biti. Hash kodu var vēl vairāk analizēt, lai atrisinātu jebkuru uzdevumu. Piemēram, hashing var izmantot, lai salīdzinātu datus: ja divi hash kodi ir atšķirīgi, tiek garantēti bloki; Ja tas pats masīvs ir tas pats. Kopumā nepārprotamā sarakste starp avota datiem un hash kodu nav saistīts ar faktu, ka hash funkciju skaits vienmēr ir mazāks par ievades iespējām. Tāpēc ir daudz ievades ziņojumu, kas dod tādus pašus hash kodus (šādas situācijas tiek sauktas kolistija ). Sadarbību rašanās varbūtība ir svarīga loma hash funkciju kvalitātes novērtēšanā.

Hash funkcijas tiek plaši izmantotas mūsdienu kriptogrāfijā.

Vienkāršāko hash funkciju var apkopot, izmantojot "2. moduļa summu" darbību šādi: mēs iegūstam ievades virkni, mēs salokām visus baitus ar 2. moduli un baitu rezultāts atgriežas kā hash fucch vērtība. Hash funkcijas ilgums būs šajā gadījumā 8 biti neatkarīgi no izejas ziņojuma.

Piemēram, ļaujiet sākotnējam ziņojumam tulkot digitālo skatu, sekojošo (heksadecimālā formātā):

2 B.1 4 A.9 5 F.E.4

Mēs pārsūtīsim ziņojumu bināro izskatu, rakstīt baitus viens otram un nodot bitus katrā slejā ar 2. moduli:

0010 1011

0001 0100

1010 1001

0101 1111

1110 0100

——————-

0010 1101

Rezultāts: 0010 1101 vai 2 D. Un tas būs hash funkcijas vērtība.

Tomēr šāda hash funkcija nevar izmantot kriptogrāfiskiem mērķiem, piemēram, lai izveidotu elektronisko parakstu, jo tas ir diezgan viegli mainīt saturu parakstītā ziņojuma, nemainot kontrolsummas vērtības.

Tāpēc testa hash funkcija nav piemērota kriptogrāfiskām lietojumprogrammām. Kriptogrāfijā Hash funkcija tiek uzskatīta par labu, ja ir grūti izveidot divus veidus ar tādu pašu hash funkciju, kā arī, ja funkciju produkcijai nav skaidras atkarības no ieejas.

Mēs formulējam galvenās prasības kriptogrāfiskām hash funkcijām:

· Hash funkcija ir piemērojama ziņai par jebkura izmēra;

· Funkcijas vērtības aprēķināšana ir pietiekami ātri;

· Ar zināmu jēgu hash funkciju, tas būtu grūti (gandrīz neiespējami), lai atrastu piemērotu prototipu M. ;

· Ar labi zināmu ziņojumu M. Būtu grūti atrast citu ziņojumu. M ' ar tādu pašu hash funkcijas vērtību, piemēram, avota ziņojumu;

· Ir jābūt grūti atrast jebkuru pāris izlases dažādus ziņojumus ar tādu pašu hash funkciju.

Pašlaik praksē funkcijas tiek izmantotas kā hash funkcijas, ievades ziņojuma bloka apstrāde aiz ierīces un aprēķinot hash- sVEIKI. Katram blokam M i. Ievades ziņojums par atkarību

h i \u003d h (m i, h i-1)

kur h i-1 - rezultāts, kas iegūts, aprēķinot iepriekšējo ievades datu bloku.

Rezultātā Hash funkcijas ienesīgums h n. ir funkcija no visiem n. Ievades bloki.

2. Izmantojiet bloku algoritmu šifrēšanu, lai izveidotu hash funkciju.

Kā hash funkciju, jūs varat izmantot bloka algoritmu simetrisku šifrēšanu. Ja izmantotais bloka algoritms ir kriptogrāfisks statnis, tad hash-funkcija, pamatojoties uz to, būs uzticama.

Vienkāršākais veids, kā izmantot bloka algoritmu, lai iegūtu hash kodu, ir ziņojuma šifrēšana CBC režīmā ( Šifrēšanas bloku ķēizēšana - CIPHERTEX sajūga režīms). Šajā gadījumā ziņojums ir attēlots kā bloku secība, kuru garums ir vienāds ar šifrēšanas algoritma vienības garumu. Vajadzības gadījumā pēdējā vienība tiek papildināta ar pareizajiem nullēm, lai vēlamā garuma vienība ir. Hash būs pēdējais šifrētais teksta bloks. Ievērojot uzticamu bloku šifrēšanas algoritmu, iegūtā hash būs šādas īpašības:

· Praktiski neiespējami, nezinot, ka šifrēšanas atslēga aprēķina hash vērtību konkrētai atklātā informācijas klāstam;

· Tas ir praktiski neiespējami, nezinot šifrēšanas atslēgu atvērto datu izvēli noteiktu hash vērtību.

Pazemīgs veidojas šādā veidā parasti sauc imitovka vai autentifikators un izmanto, lai pārbaudītu ziņojuma integritāti. Tādējādi simulators ir kontroles kombinācija, kas ir atkarīga no atvērtiem datiem un slepenas galvenās informācijas. Imitovka lietošanas mērķis ir atklāt visas nejaušās vai apzinātās izmaiņas informācijas klāstā. Vērtība, kas iegūta ar hash funkciju, apstrādājot ievades ziņojumu, ir pievienots ziņai brīdī, kad ir zināms, ka ziņojums ir pareizs. Saņēmējs pārbauda ziņojuma integritāti, aprēķinot saņemtā ziņojuma imitantiju un salīdzinot to ar iegūto hash kodu, kas jānosūta drošā veidā. Viens no šiem drošajiem veidiem var šifrēt sūtītāja imitantiju ar slēgtu atslēgu, t.i. Izveidot parakstu. Ir iespējams arī šifrēt iegūto hash koda algoritmu simetriskai šifrēšanai, ja sūtītājam un saņēmējam ir vispārējs simetriskā šifrēšanas atslēga.

Norādītais Imitovka iegūšanas un izmantošanas process ir aprakstīts vietējā standarta GOST 28147-89. Standarts piedāvā izmantot jaunākos 32 bitus bloka, kas iegūta pēc izejas šifrēšanas darbību visu ziņu šifra bloka sajūga režīmā, lai uzraudzītu integritāti nosūtīto ziņu. Tādā pašā veidā, jebkurš bloka algoritms simetrisku šifrēšanu var izmantot, lai veidotu imitavka.

Vēl viens iespējamais veids, kā izmantot bloku šifrētu, lai radītu hash kodu, ir šāds. Avota ziņojums tiek apstrādāts sērijas blokos. Pēdējais bloks ir papildināts ar nullēm, ja nepieciešams, dažreiz ziņojuma garums binārā numura veidā ir attiecināms uz pēdējo bloku. Katrā posmā šifrējiet hash, kas iegūts iepriekšējā posmā, veicot pašreizējo ziņojumu bloku kā atslēgu. Pēdējā ievadītā šifrētā vērtība būs galīgā hash.

Tādējādi, ja parastā ziņojuma šifrēšanas shēma M. izmantojot bloka šifru f. uz atslēgu Uz Mēs reģistrējāmies kā E \u003d f (m, k) tad hash koda shēma h. Saskaņā ar iepriekš aprakstīto algoritmu jūs varat iedomāties, kā

sVEIKI. = f. ( sVEIKI. -1 , M. )

Kā sākotnējais hash kods h 0. Veikt kādu nemainīgu. Šifrēšana tiek veikta vienkāršā nomaiņas režīmā. Izmantot noteiktā metode Bloka lielums sakrīt ar atslēgas garumu un hash vērtības lielums būs vienības garums.

Vēl viens veids, kā izmantot bloka šifrēšanu vienkāršā nomaiņas režīmā, ir iespējams: ziņu elementi tiek šifrēti ar hash vērtībām, kas iegūtas iepriekšējā posmā:

sVEIKI. = f. ( M. , sVEIKI. -1 ,)

Faktiski vairākas vairākas shēmas par bloka šifra izmantošanu, lai izveidotu hash funkciju. Ļaut būt M i. - avota ziņojuma bloks, \\ t sVEIKI. - Hash funkcijas vērtība i. -skatuve, f. - Bloķēt algoritmu, kas izmantots vienkāršā nomaiņas režīmā - 2. moduļa papildināšanas darbība pēc tam iespējama, piemēram, šādas hash funkcijas veido shēmas:

Galvenais trūkums Hash funkcijas, kas paredzētas, pamatojoties uz bloka algoritmiem, ir salīdzinoši mazs ātrums. Nepieciešamais kriptoskops var nodrošināt arī mazāku skaitu operāciju ievades datiem. Ir ātrākas hashing algoritmi (visbiežāk tie - MD5, SHA-1, SHA-2 un GOST R 34,11-94).

3. A algoritmu pārskatīšana hash funkciju veidošanai.

Pašlaik tiek piedāvāti un praktiski tiek izmantoti dažādi speciālie algoritmi, lai aprēķinātu hash funkciju. Slavenākie algoritmi ir MD5, SHA-1, SHA-2 un citas SHA versijas, kā arī vietējā algoritms, kas izklāstīts GOST R 34.11-94.

Algoritms Md5 Parādījās divdesmitā gadsimta 90. gadu sākumā MD4 Hash veidošanās algoritma uzlabošanas rezultātā. Simboli nosaukumā "MD" vidējais ziņojums Digest - ziņojuma kopsavilkums. Algoritmu MD4 un MD5 - R. RIVEST autors (R.RIVEST). MD5 izmantošanas rezultātā patvaļīgs ziņojums veidojas 128 bitu hash. Ievades datus apstrādā 512 bitu bloki. Algoritms izmanto elementāru loģiskās operācijas (Inversija, savienojums, 2. moduļa pievienošana, cikliskās maiņas uc), kā arī parastais aritmētiskais papildinājums. Šo algoritma elementāro funkciju visaptveroša atkārtošana nodrošina, ka pēc apstrādes rezultāts ir labi sajaukts. Tāpēc ir maz ticams, ka diviem ziņojumiem, kas izvēlēti nejauši bija tāds pats hash kods. MD5 algoritmam ir šāds īpašums: katrs no iegūtās hash vērtības ir funkcija no katra ieraksta bitiem. Tiek uzskatīts, ka MD5 ir spēcīgākā hash funkcija 128 bitu hash vērtībai.

Algoritms Sha Droša hash algoritms - drošu hash algoritmu) izstrādāja ASV standartu un tehnoloģiju institūts (NIST), un 1993. gadā publicēja kā amerikāņu federālo informācijas standartu. Sha-1, kā arī MD5, pamatojoties uz MD4 algoritmu. Sha-1 veido 160 bitu hash, pamatojoties uz avota apstrādi 512 bitu blokiem. Sha-1 algoritms izmanto arī vienkāršas loģiskas un aritmētiskas darbības. Svarīgākā atšķirība starp SHA-1 no MD5 ir tas, ka Hash Code Sha-1 ir 32 biti ilgāk par Hash kodu MD5. Ja mēs pieņemam, ka abi algoritmi ir vienādi grūtībās ar kriptanalīzi, tad Sha-1 ir izturīgāks algoritms. Izmantojot uzbrukumu ar rupju spēku (frontālo uzbrukumu), ir grūtāk izveidot patvaļīgu ziņojumu, kurai ir dots hash kods, un tas ir arī grūtāk izveidot divus ziņojumus, kuriem ir tāds pats hash kods.

2001. gadā Nacionālais standartu un tehnoloģiju institūts ASV pieņēma trīs Hash funkcijas kā standartu ar lielāku garumu Hash kodu nekā Sha-1. Bieži vien šīs hash funkcijas sauc par SHA-2 vai SHA-256, SHA-384 un SHA-512 (garums hash kodu, ko rada algoritmi, ir norādīts nosaukumā). Šie algoritmi atšķiras ne tikai ar izveidoto hash koda garumu, bet arī izmantotās iekšējās funkcijas un pārstrādātā bloka garums (SHA-256 vienības garums - 512 un SHA-384 un SHA-512 bloka garums ir 1024 biti). SHA algoritma pakāpeniski uzlabojumi izraisa tās kriptiskās pretestības pieaugumu. Neskatoties uz atšķirībām algoritmiem, kas aplūkoti viens no otra, visi no tiem ir tālāka attīstība Sha-1 un MD4, un ir līdzīga struktūra.

Krievijā tiek pieņemts GOST P34.11-94, kas ir iekšzemes standarts Hash funkcijām. Tās struktūra ir diezgan atšķirīga no Sha-1.2 vai MD5 algoritmu struktūras, kas balstās uz MD4 algoritmu. Hash koda garums, ko izveidojis algoritms GOST R 34.11-94, ir 256 biti. Algoritms tiek secīgi apstrādāts ar avota ziņojumu ar blokiem 256 biti pa labi pa kreisi. Algoritms parametrs ir sākums vektors Hash - patvaļīga fiksētā vērtība ir arī 256 biti. Algoritmā, GOST R 34.11-94, permutācijas operācijas, bīdes, aritmētiskā papildinājums, pievienošana 2. moduļam papildu funkcija GOST 34,11-94 izmanto algoritmu saskaņā ar GOST 28147-89 vienkāršā nomaiņas režīmā.

4. Prasības hash funkcijām

Hash funkcija tiek saukta par vienvirziena funkciju, kas paredzēta, lai saņemtu apkopojumu vai "pirkstu nospiedumu" failu, ziņas vai kādu datu bloku.

Hash kodu izveido pēc funkcijas N. :

h \u003d h (m)

Kur M. ir vēstījums par patvaļīgu garumu un h. Tas ir fiksēts garuma hash kods.

Apsveriet prasības, par kurām hash funkcija ir jāatbilst tā, lai to varētu izmantot kā ziņojuma autentifikatoru. Apsveriet ļoti vienkāršu hash funkcijas piemēru. Tad mēs analizējam vairākas pieejas hash funkcijas būvniecībai.

Hash funkcija N. To izmanto, lai autentificētu ziņojumus, jābūt šādām īpašībām:

1. Hash funkcija N. Tas jāpiemēro jebkura garuma datu blokam.

2. Hash funkcija N. Izveido fiksētu garuma izeju.

3. N (m) salīdzinoši viegli (polinomijas laikam) aprēķina par jebkuru vērtību M. .

4. Attiecībā uz jebkuru doto hash kodu h. Ir acīmredzami neiespējami atrast M. tāds, ka H (m) \u003d h .

5. Jebkurā gadījumā h. Tas ir skaitļoti iespējams to atrast

H. (y) \u003d h (x).

6. Tas ir skaitļošanas, nav iespējams atrast patvaļīgu pāri ( h. , y. ) tāds, ka H (y) \u003d h (x) .

Pirmajām trim īpašībām ir nepieciešama hash funkcija, lai izveidotu hash kodu jebkuram ziņojumam.

Ceturtā īpašība nosaka prasību par vienpusību hash funkciju: viegli izveidot hash kodu šim ziņojumam, bet nav iespējams atgūt ziņojumu par šo hash kodu. Šis īpašums ir svarīgs, ja autentifikācija, izmantojot hash funkciju ietver slepenu vērtību. Slepena vērtība pati nevar nosūtīt, tomēr, ja hash funkcija nav vienpusēja, ienaidnieks var viegli atklāt slepeno vērtību šādi. Pārvietojot pārskaitījumu, uzbrucējs saņem ziņojumu M. un hash kodu C \u003d H (SAB || m) . Ja uzbrucējs var apgriezt hash funkciju, tad tas var iegūt SAB || M \u003d h-1 (c) . Tā kā uzbrucējs tagad zina un M. un SAB || M. , saņemt SAB. diezgan vienkārši.

Piektais īpašums nodrošina, ka nav iespējams atrast citu ziņojumu, kura funkcijas vērtība sakrīt ar hash funkcijas vērtību Šis ziņojums. Tas neļauj autentifikatoram viltus, izmantojot šifrētu hash kodu. Šajā gadījumā pretinieks var izlasīt ziņojumu un, tādēļ izveidot savu hash kodu. Bet, tā kā ienaidniekam nav slepenā atslēga, tam nav iespējas mainīt ziņojumu, lai saņēmējs to neatrastu. Ja šis īpašums nav izpildīts, uzbrucējam ir iespēja veikt šādu darbību secību: lai pārtvertu ziņojumu un tā šifrētu hash kodu, aprēķinātu ziņu hash kodu, izveidojiet alternatīvu ziņojumu ar to pašu hash kodu, nomainiet sākotnējo ziņojumu uz viltotu. Tā kā šo ziņojumu hash kodi sakrīt, saņēmējs neatklāj aizvietošanu.

Hash funkcija, kas atbilst pirmajām piecām īpašībām sauc par vienkāršu vai vāju hash funkciju. Ja tiek veikta sestā īpašība, tad šo funkciju sauc par spēcīgu hash funkciju. Sestais īpašums aizsargā pret klases uzbrukumiem, kas pazīstami kā uzbrukums "dzimšanas diena".

5. Vienkāršas hash funkcijas

Visas hash funkcijas tiek veiktas šādi. Ievades vērtība (ziņojums, fails, utt) tiek uzskatīta par secību n. --bit bloki. Ievades vērtība tiek apstrādāta secīgi bloku aiz ierīces, un ir izveidots. m. -Bed hash koda vērtība.

Viens no vienkāršākajiem hash funkcijas piemēriem ir katra bloka XOR bitu virzītājs:

Ar I. - i. Bitu hash kods, 1 <= i <= n .

k. - numurs n. --bit bloki ievadi.

b ij. – i. Bit b. j. Bloķēt.

Tad viss ziņojums ir šifrēts, ieskaitot Hash kodu, CCS režīmā, lai izveidotu šifrētu blokus Y1, Y2, ..., YN + 1. Pēc definīcijas man ir:

Bet xn + 1 ir hash kods:

Tā kā iepriekšējās vienlīdzības komponentus var aprēķināt jebkurā secībā, tāpēc Hash kods netiks mainīts, ja šifrētie bloki tiks pārkārtoti.

NIST ierosinātais sākotnējais standarts izmantoja vienkāršu XOR, kas tika izmantots 64 bitu ziņojumu blokiem, tad viss ziņojums ir šifrēts, izmantojot CCS režīmu.

"Dzimšanas dienas paradokss"

Pirms apsvērt sarežģītākas hash funkcijas, ir nepieciešams analizēt vienu konkrētu uzbrukumu vienkāršām hash funkcijām.

Tā sauktais "dzimšanas dienas paradokss" ir šāds. Pieņemsim, hash funkcijas izejas vērtību skaits N. vienāds n. . Kas būtu numurs k. uz konkrēto vērtību X. un vērtības Y1 Yk. Varbūtība, ka vismaz viens yi tika veikta vienlīdzība

H (x) \u003d h (y)

būtu vairāk nekā 0,5.

Vienam Y. varbūtība, ka H (x) \u003d h (y) , vienāds 1 / N. .

Attiecīgi varbūtība, ka , vienāds 1 - 1 / n .

Ja jūs izveidojat k. Vērtības, varbūtība, ka nesadalīšanās būs vienāda ar varbūtību produkta, kas atbilst vienai vērtībai, t.i. (1 - 1 / n) k .

Līdz ar to vismaz vienas sakritības varbūtība ir vienāda

1 - (1 - 1 / n) k

Tāpēc mēs to uzzinājām m. -Bed hash kods ir pietiekami, lai izvēlētos 2m-1 Ziņojumi, lai hash kodu nejaušības varbūtība bija lielāka par 0,5.

Tagad apsveriet šādu uzdevumu: apzīmējiet P (n, k) varbūtība, ka kopumā k. elementi, no kuriem katrs var veikt n. Vērtības, ir vismaz divas ar tām pašām vērtībām. Kas būtu vienāds k. uz P (n, k) būtu vairāk 0,5 ?

Dažādu veidu, kā izvēlēties elementus tādā veidā, ka tam nav dubultā, vienāda

n (N - 1) ... (N - K + 1) \u003d N! / (N-K)!

Visi iespējamie veidi, kā izvēlēties elementus vienādi n K.

Varbūtība, ka nav divvietīga ir vienāda n! / (N - k)! N K

Iespēja, ka ir attiecīgi dublikāts

1 - N! / (N-k)! Nk P (n, k) \u003d 1 - n! / ((n - k)! x nk) \u003d 1 - (n x (n - 1) x ... x (n - k-1)) / nk \u003d 1 - [(N - 1) / N x (N-2) / N x ... x (n - k + 1) / n] \u003d 1 - [(1-1 / n) x (1 - 2 / n) x ... x (1 - (k-1) / n)]

Ja hash kodam ir garums m. Bit, ti.e. Pieņemt 2m. Vērtības, T.

Līdzīgu rezultātu sauc par "dzimšanas dienas paradoksu", jo saskaņā ar iepriekš minētajiem argumentiem, lai iegūtu divu cilvēku dzimšanas gadījumu nejaušības varbūtību, kas ir lielāks par 0,5, grupā jābūt tikai 23 cilvēkiem. Šis rezultāts šķiet awesome, varbūt tāpēc, ka katrai personai grupā ir varbūtība, ka kāda cilvēka dzimšanas diena grupā sakrīt ar savu dzimšanas dienu, ir diezgan maza.

Atgriezīsimies ar hash funkciju īpašībām. Pieņemsim, ka tiek izmantots 64 bitu hash kods. Var uzskatīt, ka tas ir pilnīgi pietiekams, un tāpēc ir drošs garums hash kodam. Piemēram, ja šifrēts hash kods No Nosūtīts ar atbilstošu nešifrētu ziņojumu M. , tad ienaidniekam būs jāatrod M ' tāds, ka

N (m) \u003d n (m) ,

lai aizstātu ziņojumu un maldinātu saņēmēju. Vidēji ienaidniekam vajadzētu izlauzties 263 ziņojumos, lai to atrastu, ka hash kods ir vienāds ar aizturēto ziņojumu.

Tomēr ir iespējams dažādi uzbrukumi, kas balstīti uz "dzimšanas dienas paradoksu". Iespējama šāda stratēģija:

1. Ienaidnieks rada 2 m / 2 Ziņu opcijas, no kurām katrai ir kāda konkrēta nozīme. Ienaidnieks sagatavo tādu pašu ziņu skaitu, no kuriem katrs ir viltots un ir paredzēts, lai aizstātu šo ziņojumu.

2. Divas ziņu kopas tiek salīdzinātas, meklējot pāris ziņojumus, kuriem ir tāds pats hash kods. Panākumu varbūtība saskaņā ar "dzimšanas dienas paradoksu" ir lielāka par 0,5. Ja atbilstošais pāris nav atrasts, papildu avots un viltus ziņojumi tiek izveidoti, līdz tiek atrasts tvaiks.

3. Uzbrucējs piedāvā sūtītājam sākotnējo ziņojumu par parakstu. Pēc tam šo parakstu var piestiprināt pie viltotas izvēles, lai pārsūtītu saņēmēju. Tā kā abām iespējām ir tāds pats hash kods, tiks izveidots tāds pats paraksts. Ienaidnieks būs pārliecināts par panākumiem, pat nezinot šifrēšanas atslēgu.

Tādējādi, ja izmanto 64 bitu hash kodu, nepieciešamā aprēķinu sarežģītība ir aptuveni 232.

Visbeidzot, mēs atzīmējam, ka hash koda garumam jābūt diezgan lielam. Garums vienāds ar 64 bitiem pašlaik neuzskata par drošu. Vēlams, lai garums veido 100 bitu secību.

Izmantojot šifrētu bloku ķēdi

Ir dažādas hash funkcijas, kas balstītas uz šifrētu bloku ķēdes izveidi, bet neizmantojot slepeno atslēgu. Vienu no šīm hash funkcijām ierosināja Rabin. Ziņojums M. Sadaliet fiksētā garuma blokos M1, m2 ,. . . , Mn. un izmantojot simetrisku šifrēšanas algoritmu, piemēram, des, lai aprēķinātu hash kodu G. Šādā veidā:

H 0 - sākotnējā nozīme N I. = E mi. G. = H n.

Tas ir līdzīgs šifrēšanas lietošanai CSA režīmā, bet šajā gadījumā nav slepenas atslēgas. Tāpat kā jebkuras vienkāršas hash funkcijas gadījumā, šis algoritms ir uzņēmīgs pret "dzimšanas dienas uzbrukumu", un, ja šifrēšanas algoritms ir des, un tikai 64 bitu hash kods tiek izveidots, sistēma tiek uzskatīta par diezgan neaizsargāta.

Var būt citi uzbrukumi, piemēram, "dzimšanas diena", kas ir iespējams, pat ja ienaidniekam ir piekļuve tikai vienam ziņojumam un atbilstošajam šifrētajam hash kodam un nevar saņemt vairākus ziņojumus un šifrētus hash kodus. Iespējams šāds scenārijs: Pieņemsim, ka ienaidnieks aizturēja ziņojumu ar autentifikatoru šifrētā hash koda veidā, un ir zināms, ka nešifrētajam hash kodam ir garums m. biti. Pēc tam ienaidniekam ir jāveic šādas darbības:

· Izmantojot iepriekš aprakstīto algoritmu, aprēķiniet unenrypted hash kodu G. .

· Izveidojiet viltotu ziņojumu formā Q1, Q2 ,. . . , QN-2 .

· Aprēķināt N i \u003d e qi priekš 1 <= i <= N-2 .

· Izveidot 2 m / 2 Izlases bloki H. Un katram šādam blokam H. aprēķināt EH. . Izveidot papildus 2 m / 2 Pietiekami daudz bloku Y. un katram blokam Y. aprēķināt D y [g] kur D. - dekorēšanas funkcija, kas atbilst E. . Pamatojoties uz "dzimšanas dienas paradoksu", mēs varam teikt, ka ar augstu varbūtības pakāpi, šī secība satur blokus H. un Y. tāds, ka E x \u003d d y [y] .

· Izveidot ziņu Q1, Q2 ,. . . , QN-2, x, y . Šim ziņojumam ir hash kods G. Un tāpēc to var izmantot ar šifrētu autentifikatoru.

Šis uzbrukuma veids ir pazīstams kā uzbrukums "tikšanās vidū". Dažādos pētījumos tiek piedāvātas izsmalcinātas metodes, lai uzlabotu pieeju, kas balstīta uz bloka ķēdi. Piemēram, Devis un cena aprakstīja šādu iespēju:

Vēl viena iespēja ir iespējama:

Tomēr abām šīm shēmām ir arī neaizsargātības dažādos uzbrukumos. Vispārīgāk, var pierādīt, ka kāda veida "dzimšanas dienas uzbrukums" ir veiksmīga ar jebkuru hash algoritmu, kas ietver šifrētu bloku ķēdes izmantošanu, neizmantojot slepeno atslēgu.

Turpmākie pētījumi bija vērsti atrast citas pieejas, lai izveidotu hashing funkcijas.

MD5 hash funkcija

Apsveriet MD5 ziņojumu Digest algoritmu (RFC 1321), ko izstrādājusi Ron Rivesom no MIT.

MD5 izpildes loģika

Algoritms saņem patvaļīgu garumu pie ievades un izveido 128 partijas ziņojumu, kas sagremo kā izeju. Algoritmu veido šādas darbības:

Fig. 8.1.MD5 izpildes loģika

1. solis: trūkstošo bitu pievienošana

Ziņojums tiek papildināts tā, lai tā garums kļūtu vienāds ar 448 modulo 512 (). Tas nozīmē, ka pievienotā ziņojuma garums ar 64 bitiem ir mazāks par numuru, vairāki 512. papildinājums vienmēr tiek veikts, pat ja ziņojumam ir vēlamais garums. Piemēram, ja ziņojuma ilgums ir 448, to papildina 512 biti līdz 960 bitiem. Tādējādi pievienoto bitu skaits ir robežās no 1 līdz 512.

Pievienošana sastāv no vienības, kurai vajadzīgais nulles skaits seko.

2. solis: pievienošana garums

64 bitu attēlojums avota garuma (pirms pievienojot) ziņojumus bitos ir pievienots rezultātiem pirmo soli. Ja sākotnējais garums ir lielāks par 2,64, tiek izmantoti tikai pēdējie 64 biti. Tādējādi lauks satur avota ziņojuma garumu ar 2. moduli 64.

Pirmo divu soļu rezultātā tiek izveidots ziņojums, kuru garums ir vairāki 512 biti. Šis paplašinātais ziņojums ir pārstāvēts kā 512 bitu bloku secība 0, y 1 ,. . ., Y L-1, savukārt paplašinātā ziņojuma kopējais garums ir vienāds ar L * 512 bitiem. Tādējādi saņemto uzlaboto ziņu garums ir vairāk nekā sešpadsmit 32 bitu vārdi.

Fig. 8.2.Paplašināta ziņojuma struktūra

3. solis: MD-Bufera inicializācija

Tiek izmantots 128 bitu buferis starpposma un galīgo rezultātu uzglabāšanai. Buferi var pārstāvēt kā četri 32 bitu reģistri (A, B, C, D). Šos reģistrus inicializē ar šādiem heksadecimālajiem numuriem:

A \u003d 01234567 B \u003d 89ABCDEF C \u003d FEDCBA98 D \u003d 76543210

4. solis: 512 bitu (16 lirisko) bloku secības apstrāde

Algoritma pamatā ir modulis, kas sastāv no četriem cikliskām procedūrām, kas apzīmētas kā HMD5. Četriem cikliem ir līdzīga struktūra, bet katrs cikls izmanto savu elementāro loģisko funkciju, ko apzīmē ar f f, f g, f h un f i, attiecīgi.

Fig. 8.3.Apstrāde nākamo 512 bitu bloku

Katrs cikls notiek kā ieejas pašreizējais 512 bitu bloks Y q, pašlaik apstrādāts, un ABCD bufera 128 bitu vērtību, kas ir starpposma vingrinājums, un maina šī bufera saturu. Katrs cikls izmanto arī ceturto daļu 64 elementu tabulas t, pamatojoties uz grēka funkciju. I-th elements t, apzīmēts ar t [i], ir vienāds ar visu daļu no 2 32 * abs (grēks (i)), es esmu iestatīts radiānos. Tā abs (grēks (i)) ir skaitlis starp 0 un 1, katrs elements t ir vesels, ko var pārstāvēt 32 biti. Tabulā ir iekļauts "izlases" 32 bitu vērtību komplekts, kurām jānovērš ievades datu pareizība.

Lai iegūtu MD Q + 1, četru ciklu ražu veido 22. modulis ar MD Q. Papildinājums tiek veikts neatkarīgi katram no četriem vārdiem buferī.

CLS S ir cikliska pāreja pa kreisi no 32 bitu argumentiem bitiem.

X [k] - M - K-O 32 bitu vārds Q-Ohm 512 ziņu blokā.

T [i] - i-o, 32 bitu vārds matricā T.

+ - 2. moduļa pievienošana 32.

Katrā no četriem algoritma cikliem tiek izmantota viena no četrām elementārajām loģiskajām funkcijām. Katrs elementārā iezīme saņem trīs 32 bitu vārdus pie ieejas un izeja rada vienu 32 bitu vārdu. Katra funkcija ir daudzās partijas loģiskās operācijas, t.i. NTH izejas bit ir funkcija no N-B bitu trim ieejām. Elementārās funkcijas ir šādas:

32 bitu vārdu sērija satur pašreizējā 512 bitu ieejas bloka vērtību, kas pašlaik tiek apstrādāts. Katrs cikls darbojas 16 reizes, un tā kā katrs ievades ziņojuma bloks tiek apstrādāts četros ciklos, tad katra ievades vienība tiek apstrādāta saskaņā ar diagrammu, kas parādīta 1. attēlā. 4, 64 reizes. Ja jūs iesniedzat ieejas 512 bitu bloku formā sešpadsmit 32 bitu vārdus, katrs ieeja 32 bitu vārdu tiek izmantots četras reizes, vienu reizi katrā ciklā, un katrs tabulas elements, kas sastāv no 64 32 bitu Vārdi, tiek izmantoti tikai vienu reizi. Pēc katra cikla soļa cikliskā pāreja pa kreisi no četriem vārdiem A, B, C un D notiek. Katrā posmā tikai viens no četriem ABCD bufera izmaiņu vārdiem. Līdz ar to katrs bufera vārds mainās 16 reizes, un pēc tam beidzas 17. reize, lai iegūtu šīs vienības galīgo produkciju.

sagremot.

2. Ātrums: programmas īstenošana algoritma jāveic diezgan ātri. Jo īpaši algoritms ir pietiekami ātri uz 32 bitu arhitektūras. Tāpēc algoritms ir balstīts uz vienkāršu elementāru operāciju kopumu virs 32 bitu vārdiem.

3. Vienkāršība un kompaktums: Algoritmam jābūt vienkāršam aprakstā un viegli programmēt bez lielām programmām vai aizstājējzīmēm. Šīs īpašības ir ne tikai acīmredzamas programmas priekšrocības, bet arī vēlams drošības ziņā, jo, lai analizētu iespējamos vājos punktus, ir labāk, lai būtu vienkāršs algoritms.

4. Vēlamā ar Little-Endian arhitektūru: dažas procesora arhitektūras (piemēram, Intel 80xxx līnija) uzglabāt vārdus, kurus atstāja baitu apakšējās baitu adreses (maz-endian). Citi (piemēram, Sun Sparchstation) uzglabāt pareizos baitus vārda pozīcijā Junior Byte adreses (Big MD4 papildu konstante pirmajā ciklā netiek piemērota. Līdzīga papildu konstante tiek izmantota katram solim otrajā ciklā. Vēl viens papildus Pastāvīgs tiek izmantots katram no soļiem trešajā ciklā. tas ir, ir maz ticams, ka divi ziņojumi, kas izvēlēti pēc nejaušības, pat tad, ja viņiem ir acīmredzami līdzīgi modeļi, bija tādi paši sagremot, kas rada tādu pašu izvades vērtību. Tas nozīmē, ka MD5 izpilde pār vienu bloku 512 biti novedīs pie Tas pats izeja divām dažādām ieejas vērtībām ABCD buferī. Kaut arī šīs pieejas paplašināšanas metode veiksmīgai uzbrukumam MD5 nepastāv.