vprašanja:

1. Koncept zgoščevalne funkcije.

2. Uporaba algoritmov blokovnega šifriranja za oblikovanje zgoščevalne funkcije.

3. Pregled algoritmov za generiranje zgoščevalnih funkcij.

1. Koncept zgoščevalne funkcije

Zgoščevalna funkcija(hash function) je matematična ali druga funkcija, ki za niz poljubne dolžine izračuna neko celoštevilsko vrednost ali kakšen drug niz fiksne dolžine. Matematično se lahko zapiše takole:

h = H(M) ,

Kje M – izvirno sporočilo, včasih imenovano prototip , A h – rezultat, imenovan zgoščena vrednost (in tudi hash koda oz povzetek sporočila(iz angleščine povzetek sporočila)).

Pomen zgoščevalne funkcije je določiti značilno lastnost predslike - vrednost zgoščevalne funkcije. Ta vrednost ima običajno neko fiksno velikost, na primer 64 ali 128 bitov. Zgoščevalno kodo je mogoče dodatno analizirati, da se reši kakršna koli težava. Na primer, zgoščevanje se lahko uporablja za primerjavo podatkov: če imata dve podatkovni matriki različni zgoščevalni kodi, sta matriki zagotovljeno različni; če so enaki, so nizi najverjetneje enaki. Na splošno ni ujemanja ena proti ena med izvornimi podatki in zgoščevalno kodo zaradi dejstva, da je število vrednosti zgoščene funkcije vedno manjše od števila možnosti vhodnih podatkov. Posledično obstaja veliko vhodnih sporočil, ki dajejo enake zgoščene kode (take situacije imenujemo trki ). Verjetnost kolizij ima pomembno vlogo pri ocenjevanju kakovosti zgoščevalnih funkcij.

Zgoščevalne funkcije se pogosto uporabljajo v sodobni kriptografiji.

Najenostavnejšo zgoščevalno funkcijo je mogoče sestaviti z operacijo vsote po modulu 2 na naslednji način: pridobite vhodni niz, dodajte vse bajte po modulu 2 in vrnite bajt rezultata kot zgoščeno vrednost. Dolžina vrednosti zgoščevalne funkcije bo v tem primeru 8 bitov, ne glede na velikost vhodnega sporočila.

Recimo, da je izvirno sporočilo, prevedeno v digitalno obliko, naslednje (v šestnajstiški obliki):

2 B1 4 A9 5 FE4

Pretvorimo sporočilo v binarno obliko, zapišimo bajte enega pod drugim in seštejmo bite v vsakem stolpcu po modulu 2:

0010 1011

0001 0100

1010 1001

0101 1111

1110 0100

——————-

0010 1101

rezultat: 0010 1101 oz 2 D in bo vrednost zgoščevalne funkcije.

Vendar pa takšne zgoščevalne funkcije ni mogoče uporabiti za kriptografske namene, kot je generiranje elektronskega podpisa, saj je zelo enostavno spremeniti vsebino podpisanega sporočila, ne da bi spremenili vrednost kontrolne vsote.

Zato obravnavana zgoščevalna funkcija ni primerna za kriptografske aplikacije. V kriptografiji se zgoščevalna funkcija šteje za dobro, če je težko ustvariti dve predsoli z enako zgoščeno vrednostjo in tudi, če izhod funkcije ni izrecno odvisen od vhoda.

Oblikujmo osnovne zahteve za kriptografske zgoščevalne funkcije:

· zgoščevalna funkcija mora biti uporabna za sporočilo katere koli velikosti;

· izračun vrednosti funkcije mora biti izveden dovolj hitro;

· ob znani vrednosti zgoščevalne funkcije bi moralo biti težko (skoraj nemogoče) najti ustrezen prototip M ;

· z znanim sporočilom M mora biti težko najti drugo objavo M' z enako zgoščeno vrednostjo kot izvirno sporočilo;

· Težko bi moralo biti najti kateri koli par naključno različnih sporočil z enako zgoščeno vrednostjo.

Ustvarjanje zgoščevalne funkcije, ki izpolnjuje vse zgornje zahteve, ni lahka naloga. Zapomniti si je treba tudi, da vhod funkcije prejme podatke poljubne velikosti in rezultat zgoščevanja ne sme biti enak za podatke različnih velikosti.

Trenutno so v praksi zgoščevalne funkcije funkcije, ki obdelajo vhodno sporočilo blok za blokom in izračunajo zgoščeno vrednost h i za vsak blok M i vhodno sporočilo na podlagi odvisnosti obrazca

h i = H(M i ,h i-1),

Kje h i-1 – rezultat, dobljen pri izračunu zgoščevalne funkcije za prejšnji blok vhodnih podatkov.

Posledično je rezultat zgoščevalne funkcije h n je funkcija vseh n bloki vhodnih sporočil.

2. Uporaba algoritmov blokovnega šifriranja za ustvarjanje zgoščevalne funkcije.

Algoritem blokovnega simetričnega šifriranja se lahko uporablja kot zgoščevalna funkcija. Če je uporabljeni blokovni algoritem kriptografsko močan, bo zgoščevalna funkcija, ki temelji na njem, varna.

Najenostavnejši način uporabe blokirnega algoritma za pridobitev zgoščene kode je šifriranje sporočila v načinu CBC ( Cipher Block Chaining – način veriženja blokov šifriranega besedila). V tem primeru je sporočilo predstavljeno kot zaporedje blokov, katerih dolžina je enaka dolžini bloka šifrirnega algoritma. Če je potrebno, je zadnji blok na desni obložen z ničlami, da se ustvari blok zahtevane dolžine. Zgoščena vrednost bo zadnji šifrirani blok besedila. Pod pogojem, da je uporabljen zanesljiv algoritem za šifriranje blokov, bo imela dobljena zgoščena vrednost naslednje lastnosti:

· skoraj nemogoče je izračunati zgoščeno vrednost za dano odprto matriko informacij brez poznavanja šifrirnega ključa;

· skoraj nemogoče je izbrati odprte podatke za dano zgoščeno vrednost brez poznavanja šifrirnega ključa.

Tako ustvarjena zgoščena vrednost se običajno kliče imitacijski vložek oz avtentifikator in se uporablja za preverjanje celovitosti sporočila. Tako je imitacijski vložek kontrolna kombinacija, ki je odvisna od odprtih podatkov in informacije o tajnem ključu. Namen uporabe imitativnega vstavljanja je zaznavanje vseh naključnih ali namernih sprememb v informacijskem nizu. Vrednost, ki jo pridobi zgoščevalna funkcija pri obdelavi vhodnega sporočila, se pripne sporočilu v trenutku, ko je znano, da je sporočilo pravilno. Prejemnik preveri celovitost sporočila tako, da izračuna imitirano sporočilo prejetega sporočila in ga primerja s prejeto zgoščeno kodo, ki mora biti posredovana na varen način. Ena od takih varnih metod bi lahko bila šifriranje imitativnega vložka z zasebnim ključem pošiljatelja, tj. ustvarjanje podpisa. Dobljeno zgoščeno kodo je možno tudi šifrirati s simetričnim šifrirnim algoritmom, če imata pošiljatelj in prejemnik skupni simetrični šifrirni ključ.

Naveden postopek pridobivanja in uporabe imitacijskih vložkov je opisan v domačem standardu GOST 28147-89. Standard predlaga uporabo spodnjih 32 bitov bloka, pridobljenega na izhodu celotne operacije šifriranja sporočila v načinu veriženja šifriranih blokov, za nadzor celovitosti poslanega sporočila. Na enak način se lahko kateri koli algoritem blokovnega simetričnega šifriranja uporabi za ustvarjanje lažnega vstavka.

Drug možen način uporabe blokovne šifre za ustvarjanje zgoščene kode je naslednji. Izvirno sporočilo se obdela zaporedno v blokih. Zadnji blok je po potrebi dopolnjen z ničlami; včasih se zadnjemu bloku doda dolžina sporočila v obliki binarnega števila. Na vsaki stopnji šifriramo zgoščeno vrednost, pridobljeno na prejšnji stopnji, pri čemer kot ključ uporabimo trenutni blok sporočila. Zadnja prejeta šifrirana vrednost bo končni rezultat zgoščevanja.

Torej, če je običajna shema šifriranja sporočil M z uporabo blokovne šifre f na ključu TO smo posneli kot E= f(M,K) , nato shemo za pridobitev zgoščene kode h z uporabo zgoraj opisanega algoritma lahko predstavimo kot

h i = f ( h i -1 , M )

Kot začetno zgoščeno kodo h 0 vzemite nekaj konstante. Šifriranje se izvaja v preprostem nadomestnem načinu. Pri uporabi te metode je velikost bloka enaka dolžini ključa, velikost zgoščene vrednosti pa bo dolžina bloka.

Možen je tudi drug način uporabe blokovne šifre v načinu preproste zamenjave: elementi sporočila so šifrirani z zgoščenimi vrednostmi, pridobljenimi v prejšnjem koraku:

h i = f ( M , h i -1 ,)

Pravzaprav obstaja več drugih možnih shem za uporabo blokovne šifre za ustvarjanje zgoščevalne funkcije. Pustiti M i – originalni blok sporočila, h i – vrednost zgoščevalne funkcije vklopljena jaz - na tej stopnji, f – algoritem za šifriranje blokov, ki se uporablja v načinu enostavne zamenjave;

V vseh teh shemah je dolžina generirane zgoščene vrednosti enaka dolžini šifrirnega bloka. Vse te, pa tudi nekatere druge sheme za uporabo blokovnega šifrirnega algoritma za izračun zgoščenih vrednosti, je mogoče uporabiti v praksi.

Glavna pomanjkljivost zgoščevalnih funkcij, zasnovanih na blokovnih algoritmih, je razmeroma nizka hitrost delovanja. Zahtevano kriptografsko moč je mogoče doseči z manj operacijami na vhodnih podatkih. Obstajajo hitrejši algoritmi zgoščevanja (najpogostejši med njimi so MD5, SHA-1, SHA-2 in GOST R 34.11-94).

3. Pregled algoritmov za generiranje zgoščevalnih funkcij.

Trenutno so bili predlagani in se v praksi uporabljajo različni posebni algoritmi za izračun hash funkcije. Najbolj znani algoritmi so MD5, SHA-1, SHA-2 in druge različice SHA, pa tudi domači algoritem, določen v GOST R 34.11-94.

Algoritem MD5 se je pojavil v zgodnjih 90. letih dvajsetega stoletja kot rezultat izboljšave algoritma za generiranje zgoščevalne funkcije MD4. Znaki v imenu "MD" pomenijo Message Digest - povzetek sporočila. Avtor algoritmov MD4 in MD5 je R. Rivest. Uporaba MD5 za poljubno sporočilo ustvari 128-bitno zgoščeno vrednost. Vhodni podatki se obdelujejo v blokih po 512 bitov. Algoritem uporablja osnovne logične operacije (inverzijo, konjunkcijo, seštevanje po modulu 2, ciklične premike itd.), pa tudi navadno aritmetično seštevanje. Kompleksno ponavljanje teh osnovnih funkcij algoritma zagotavlja, da je rezultat po obdelavi dobro premešan. Zato je malo verjetno, da bosta dve naključno izbrani sporočili imeli enako zgoščeno kodo. Algoritem MD5 ima naslednjo lastnost: vsak bit dobljene zgoščene vrednosti je funkcija vsakega bita vhoda. MD5 velja za najmočnejšo zgoščevalno funkcijo za 128-bitno zgoščeno vrednost.

Algoritem SHA(Secure Hash Algorithm) je razvil Nacionalni inštitut za standarde in tehnologijo ZDA (NIST) in ga leta 1993 objavil kot zvezni informacijski standard ZDA. SHA-1, tako kot MD5, temelji na algoritmu MD4. SHA-1 ustvari 160-bitno zgoščeno vrednost z obdelavo izvirnega sporočila v 512-bitnih blokih. Algoritem SHA-1 uporablja tudi preproste logične in aritmetične operacije. Najpomembnejša razlika med SHA-1 in MD5 je, da je zgoščevalna koda SHA-1 32 bitov daljša od zgoščevalne kode MD5. Ob predpostavki, da sta oba algoritma enako zahtevna za kriptoanalizo, je SHA-1 močnejši algoritem. Z uporabo brute force napada (brute force attack) je težje ustvariti poljubno sporočilo, ki ima dano zgoščeno kodo, prav tako je težje ustvariti dve sporočili, ki imata enako zgoščeno kodo.

Leta 2001 je ameriški nacionalni inštitut za standarde in tehnologijo sprejel tri zgoščevalne funkcije z daljšo dolžino zgoščevalne kode kot SHA-1 kot standard. Te zgoščevalne funkcije se pogosto imenujejo SHA-2 ali SHA-256, SHA-384 in SHA-512 (ime označuje dolžino zgoščevalne kode, ki jo ustvarijo algoritmi). Ti algoritmi se ne razlikujejo le po dolžini ustvarjene zgoščene kode, temveč tudi po uporabljenih notranjih funkcijah in dolžini obdelanega bloka (SHA-256 ima dolžino bloka 512, medtem ko imata SHA-384 in SHA-512 blok dolžina 1024 bitov). Postopne izboljšave algoritma SHA vodijo do povečanja njegove kriptografske moči. Kljub razlikam med obravnavanimi algoritmi so vsi nadaljnji razvoj SHA-1 in MD4 in imajo podobno strukturo.

Rusija je sprejela GOST R34.11-94, ki je domači standard za zgoščevalne funkcije. Njegova struktura se precej razlikuje od strukture algoritmov SHA-1,2 ali MD5, ki temeljijo na algoritmu MD4. Dolžina zgoščene kode, ustvarjene z algoritmom GOST R 34.11-94, je 256 bitov. Algoritem zaporedno obdela izvirno sporočilo v blokih po 256 bitov od desne proti levi. Parameter algoritma je začetni vektor zgoščevanja – poljubna fiksna vrednost, dolga tudi 256 bitov. Algoritem GOST R 34.11-94 uporablja operacije permutacije, premika, aritmetičnega seštevanja, seštevanja po modulu 2. Kot pomožna funkcija GOST 34.11-94 uporablja algoritem po GOST 28147-89 v načinu preproste zamenjave.

4. Zahteve za zgoščevalne funkcije

Zgoščevalna funkcija je enosmerna funkcija, namenjena pridobivanju povzetka ali prstnega odtisa datoteke, sporočila ali nekega bloka podatkov.

Zgoščevalno kodo ustvari funkcija n :

h = H(M)

Kje M je sporočilo poljubne dolžine in h je zgoščena koda fiksne dolžine.

Oglejmo si zahteve, ki jih mora izpolnjevati zgoščevalna funkcija, da se lahko uporablja kot avtentifikator sporočil. Oglejmo si zelo preprost primer zgoščevalne funkcije. Nato bomo analizirali več pristopov k izdelavi zgoščevalne funkcije.

Zgoščevalna funkcija n , ki se uporablja za preverjanje pristnosti sporočil, mora imeti naslednje lastnosti:

1. Zgoščevalna funkcija n je treba uporabiti za podatkovni blok poljubne dolžine.

2. Zgoščevalna funkcija n ustvari izhod s fiksno dolžino.

3. N (M) razmeroma enostavno (v polinomskem času) izračunati za katero koli vrednost M .

4. Za katero koli vrednost zgoščene kode h računalniško nemogoče najti M tako da H (M) = h .

5. Za vse X to je računsko nemogoče najti

H (y) = H(x).

6. Računalniško je nemogoče najti poljuben par ( X , l ) tako, da H(y) = H(x) .

Prve tri lastnosti zahtevajo zgoščevalno funkcijo za izdelavo zgoščevalne kode za katero koli sporočilo.

Četrta lastnost določa zahtevo, da je zgoščevalna funkcija enostranska: preprosto je ustvariti zgoščevalno kodo iz danega sporočila, vendar je nemogoče rekonstruirati sporočilo iz dane zgoščevalne kode. Ta lastnost je pomembna, če preverjanje pristnosti zgoščevanja vključuje tajno vrednost. Sama skrivna vrednost morda ne bo poslana, če pa zgoščevalna funkcija ni enosmerna, lahko nasprotnik zlahka razkrije skrivno vrednost, kot sledi. Ko je prenos prestrežen, napadalec prejme sporočilo M in hash kodo C = H (SAB || M) . Če lahko napadalec obrne zgoščeno funkcijo, potem lahko pridobi SAB || M=H-1(C) . Ker napadalec zdaj ve in M in SAB || M , dobiti SAB čisto preprosto.

Peta lastnost zagotavlja, da ni mogoče najti drugega sporočila, katerega zgoščena vrednost se ujema z zgoščeno vrednostjo tega sporočila. To preprečuje ponarejanje avtentifikatorja pri uporabi šifrirane zgoščene kode. V tem primeru lahko nasprotnik prebere sporočilo in tako ustvari njegovo zgoščeno kodo. Ker pa nasprotnik nima skrivnega ključa, ne more spremeniti sporočila, ne da bi ga prejemnik zaznal. Če ta lastnost ni izpolnjena, ima napadalec možnost izvesti naslednje zaporedje dejanj: prestreči sporočilo in njegovo šifrirano zgoščeno kodo, izračunati zgoščeno kodo sporočila, ustvariti alternativno sporočilo z isto zgoščeno kodo, zamenjati izvirno sporočilo z lažnim. Ker so zgoščene vrednosti teh sporočil enake, prejemnik ne bo zaznal ponarejanja.

Zgoščevalna funkcija, ki izpolnjuje prvih pet lastnosti, se imenuje preprosta ali šibka zgoščevalna funkcija. Če je poleg tega izpolnjena še šesta lastnost, se taka funkcija imenuje močna zgoščevalna funkcija. Šesta lastnost ščiti pred vrsto napadov, znanih kot rojstni napad.

5. Enostavne zgoščevalne funkcije

Vse zgoščevalne funkcije se izvajajo na naslednji način. Vhodna vrednost (sporočilo, datoteka itd.) se obravnava kot zaporedje n -bitni bloki. Vhodna vrednost se obdela zaporedno blok za blokom in a m -bitna vrednost zgoščene kode.

Eden najpreprostejših primerov zgoščevalne funkcije je bitni XOR vsakega bloka:

Z i - jaz bit zgoščene kode, 1 <= i <= n .

k - številka n -bitni vhodni bloki.

b ij – jaz th bit in j -th blok.

Celotno sporočilo je nato šifrirano, vključno z zgoščeno kodo, v načinu CBC, da se ustvarijo šifrirani bloki Y1, Y2, ..., YN+1. Po definiciji SHS imamo: Toda XN+1 je zgoščena koda: Ker je člene v prejšnji enakosti mogoče ovrednotiti v poljubnem vrstnem redu, zgoščena koda torej ne bo spremenjena, če so šifrirani bloki prerazporejeni. Prvotni standard, ki ga je predlagal NIST, je uporabljal preprost XOR, ki je bil uporabljen za 64-bitne bloke sporočil, nato pa je bilo celotno sporočilo šifrirano v načinu CBC. "Paradoks rojstnega dne" Preden pogledamo kompleksnejše zgoščevalne funkcije, je treba analizirati en specifičen napad na preproste zgoščevalne funkcije. Tako imenovani "paradoks rojstnega dne" je naslednji. Recimo število izhodnih vrednosti zgoščevalne funkcije n enako n . Kakšna naj bo številka? k tako da za določeno vrednost X in vrednote Y1, ,Yk verjetnost, da za vsaj enega Yi velja enakost H(X) = H(Y) bi bil večji od 0,5. Za enega Y verjetnost, da H(X) = H(Y) , je enako 1/n . V skladu s tem je verjetnost, da , je enako 1 – 1/n . Če ustvarjate k vrednosti, potem je verjetnost, da za nobeno od njih ne bo ujemanja, enaka zmnožku verjetnosti, ki ustreza eni vrednosti, tj. (1 – 1/n)k . Zato je verjetnost vsaj enega ujemanja 1 - (1 - 1/n)k Tako smo ugotovili, da za m -bitna zgoščena koda je dovolj za izbiro 2m-1 sporočila, tako da je verjetnost ujemanja zgoščenih kod večja od 0,5. Zdaj razmislite o naslednji težavi: označimo P(n,k) verjetnost, da v nizu k elementov, od katerih lahko vsak zase n vrednosti, obstajata vsaj dva z enakimi vrednostmi. Čemu bi moral biti enak? k , do P(n,k) bi bilo več 0,5 ? Število različnih načinov za izbiro elementov tako, da ni dvojnikov, je enako n(n-1) ... (n-k+1)=n!/(n-k)! Skupno število možnih načinov izbire elementov je n k Verjetnost, da ni dvojnikov, je enaka n!/(n-k)!n k Verjetnost, da obstajajo dvojniki, je ustrezno enaka 1 - n!/(n-k)!nk P(n, k) = 1 - n! / ((n-k)! x nk) = 1 - (n x (n-1) x ... x (n-k-1)) / nk = 1 - [ (n-1)/n x (n-2)/n x ... x (n-k+1)/n] = 1 - [(1- 1/n) x (1 - 2/n) x ... x (1 - (k-1)/n)] Če ima hash koda dolžino m bit, tj. sprejme 2m vrednote, torej Ta rezultat se imenuje "paradoks rojstnega dne", ker mora biti v skladu z zgornjim sklepanjem, da je verjetnost, da imata dve osebi isti rojstni dan večja od 0,5, v skupini le 23 ljudi. Ta rezultat se zdi presenetljiv, morda zato, ker je za vsakega posameznika v skupini verjetnost, da bo njegov rojstni dan sovpadal z rojstnim dnem nekoga drugega v skupini, precej majhna. Vrnimo se k obravnavi lastnosti zgoščevalnih funkcij. Predpostavimo, da je uporabljena 64-bitna zgoščena koda. Menimo, da je to zadostna in zato varna dolžina zgoščene kode. Na primer, če je šifrirana zgoščena koda Z prenese z ustreznim nešifriranim sporočilom M , potem bo moral sovražnik najti M' tako da N (M") = N (M) , z namenom zamenjave sporočila in zavajanja prejemnika. V povprečju mora nasprotnik preiskati 263 sporočil, da najde tisto, katerega zgoščena koda je enaka prestreženemu sporočilu. Možne pa so različne vrste napadov, ki temeljijo na paradoksu rojstnega dne. Možna je naslednja strategija: 1. Sovražnik ustvarja 2m/2 možnosti sporočil, od katerih ima vsaka poseben pomen. Nasprotnik pripravi enako število sporočil, od katerih je vsako lažno in naj bi nadomestilo pravo sporočilo. 2. Oba niza sporočil se primerjata, da se najde par sporočil, ki imata isto zgoščeno kodo. Verjetnost uspeha po "paradoksu rojstnega dne" je večja od 0,5. Če ujemajočega se para ni mogoče najti, se ustvarijo dodatna izvirna in lažna sporočila, dokler se ne najde par. 3. Napadalec ponudi pošiljatelju originalno različico sporočila v podpis. Ta podpis lahko nato pripnete ponarejeni različici za prenos prejemniku. Ker imata obe možnosti enako razpršilno kodo, bo ustvarjen isti podpis. Sovražnik bo prepričan v uspeh tudi brez poznavanja šifrirnega ključa. Če je torej uporabljena 64-bitna zgoščena koda, je zahtevana računska kompleksnost reda 232. Na koncu upoštevajte, da mora biti dolžina zgoščene kode dovolj velika. Dolžina 64 bitov trenutno ni varna. Zaželeno je, da je dolžina reda velikosti 100 bitov. Uporaba šifrirane verige blokov Obstajajo različne zgoščevalne funkcije, ki temeljijo na ustvarjanju verige šifriranih blokov, vendar brez uporabe skrivnega ključa. Eno takih zgoščevalnih funkcij je predlagal Rabin. Sporočilo M je razdeljen na bloke fiksne dolžine M1, M2, . . . , MN in za izračun zgoščene kode uporablja simetrični algoritem šifriranja, kot je DES G na naslednji način: H 0 - začetna vrednost N i = E Mi G = H N To je podobno uporabi šifriranja CBC, vendar v tem primeru ni skrivnega ključa. Kot pri vsaki preprosti zgoščevalni funkciji je tudi ta algoritem dovzeten za "rojstnodnevni napad" in če je šifrirni algoritem DES in je ustvarjena samo 64-bitna zgoščevalna koda, se sistem šteje za zelo ranljivega. Izvedejo se lahko drugi napadi rojstnega dne, ki so možni, tudi če ima nasprotnik dostop do samo enega sporočila in njegove ustrezne šifrirane zgoščene kode in ne more pridobiti več parov sporočil in šifriranih zgoščenih kod. Možen je naslednji scenarij: predpostavimo, da je nasprotnik prestregel sporočilo z avtentifikatorjem v obliki šifrirane zgoščene kode in je znano, da ima nešifrirana zgoščena koda dolžino m bitov Nato mora sovražnik izvesti naslednja dejanja: · Z uporabo zgoraj opisanega algoritma izračunajte nešifrirano zgoščeno kodo G . · Ustvarite lažno sporočilo v obrazcu Q1, Q2, . . . , QN-2 . · Izračunaj N i = E Qi Za 1 <= i <= N-2 . · Ustvari 2m/2 naključni bloki X in za vsak tak blok X izračunati E X . Ustvari dodatne 2m/2 naključni blok Y in za vsak blok Y izračunati D D [G] , Kje D – ustrezna funkcija dekodiranja E . Na podlagi paradoksa rojstnega dne je zelo verjetno, da bo to zaporedje vsebovalo bloke X in Y tako da E X = D Y [Y] . · Ustvarite sporočilo Q1, Q2, . . . , QN-2, X, Y . To sporočilo ima zgoščeno kodo G in se zato lahko uporablja v povezavi s šifriranim avtentifikatorjem. Ta oblika napada je znana kot napad "srečanje na sredini". Različne študije predlagajo bolj subtilne metode za izboljšanje pristopa, ki temelji na verigi blokov. Na primer, Davis in Price sta opisala naslednje: Možna je še ena možnost: Vendar imata obe shemi tudi ranljivosti pri različnih napadih. Na splošno je mogoče dokazati, da neka oblika "napada na rojstni dan" uspe s katerim koli algoritmom zgoščevanja, ki vključuje uporabo verige šifriranih blokov brez uporabe skrivnega ključa. Nadaljnje raziskave so bile usmerjene v iskanje drugih pristopov za ustvarjanje funkcij zgoščevanja. Zgoščevalna funkcija MD5 Razmislite o algoritmu za prebavo sporočil MD5 (RFC 1321), ki ga je razvil Ron Rivest z MIT. Logika izvajanja MD5 Algoritem kot vhod prejme sporočilo poljubne dolžine in kot izhod ustvari izvleček sporočila 128 bitov. Algoritem je sestavljen iz naslednjih korakov: riž. 8.1. Logika izvajanja MD5 1. korak: Dodajte manjkajoče dele Sporočilo je podloženo tako, da njegova dolžina postane 448 modulo 512(). To pomeni, da je dolžina priloženega sporočila 64 bitov manjša od večkratnika 512. Pripenjanje se vedno izvede, tudi če je sporočilo pravilne dolžine. Na primer, če je sporočilo dolgo 448 bitov, je dopolnjeno s 512 bitov, tako da je 960 bitov. Tako se število dodanih bitov giblje od 1 do 512. Seštevek je sestavljen iz enice, ki ji sledi zahtevano število ničel. 2. korak: dodajte dolžino Rezultatu prvega koraka je dodana 64-bitna predstavitev dolžine izvirnega (pred dodajanjem) sporočila v bitih. Če je prvotna dolžina večja od 2 64, se uporabi samo zadnjih 64 bitov. Tako polje vsebuje dolžino izvirnega sporočila po modulu 2 64. Prva dva koraka ustvarita sporočilo, katerega dolžina je večkratnik 512 bitov. To razširjeno sporočilo je predstavljeno kot zaporedje 512-bitnih blokov Y 0 , Y 1 , . . ., Y L-1, pri čemer je skupna dolžina razširjenega sporočila L * 512 bitov. Tako je dolžina prejetega razširjenega sporočila večkratnik šestnajstih 32-bitnih besed. riž. 8.2. Razširjena struktura sporočila 3. korak: Inicializirajte medpomnilnik MD 128-bitni medpomnilnik se uporablja za shranjevanje vmesnih in končnih rezultatov zgoščevalne funkcije. Medpomnilnik je lahko predstavljen kot štirje 32-bitni registri (A, B, C, D). Ti registri so inicializirani z naslednjimi šestnajstiškimi številkami: A = 01234567 B = 89ABCDEF C = FEDCBA98 D = 76543210 4. korak: Obdelajte zaporedje 512-bitnih (16-besednih) blokov Osnova algoritma je modul, sestavljen iz štirih cikličnih procesov, označenih kot HMD5. Štiri zanke imajo podobno strukturo, vendar vsaka zanka uporablja drugačno osnovno logično funkcijo, označeno z f F , f G , f H in f I . riž. 8.3. Obdelava naslednjega 512-bitnega bloka Vsaka zanka vzame kot vhod trenutni 512-bitni blok Y q, ki se trenutno obdeluje, in 128-bitno vrednost medpomnilnika ABCD, ki je vmesna prebavljena vrednost, in spremeni vsebino tega medpomnilnika. Vsaka zanka uporablja tudi četrtino 64-elementne tabele T, zgrajene iz funkcije sin. I-ti element T, označen s T[i], ima vrednost, ki je enaka celemu delu 2 32 * abs (sin (i)), i je podan v radianih. Ker je abs(sin(i)) število med 0 in 1, je vsak element T celo število, ki ga je mogoče predstaviti z 32 biti. Tabela ponuja "naključni" niz 32-bitnih vrednosti, ki bi morale odpraviti kakršno koli pravilnost v vhodnih podatkih. Za pridobitev MD q+1 se izhod štirih zank prišteje modulo 2 32 k MD q. Dodajanje se izvede neodvisno za vsako od štirih besed v medpomnilniku.

CLS s – ciklični levi premik za s bitov 32-bitnega argumenta.

X [k] – M – k-ta 32-bitna beseda v q-tem bloku sporočil 512.

T [i] – i-ta 32-bitna beseda v matriki T.

+ – seštevek modulo 2 32.

V vsakem od štirih ciklov algoritma je uporabljena ena od štirih osnovnih logičnih funkcij. Vsaka atomska funkcija sprejme tri 32-bitne besede kot vhod in proizvede eno 32-bitno besedo kot izhod. Vsaka funkcija je niz bitnih logičnih operacij, tj. N-ti bit izhoda je funkcija n-tega bita od treh vhodov. Osnovne funkcije so naslednje:

Matrika 32-bitnih besed X vsebuje vrednost trenutnega 512-bitnega vhodnega bloka, ki je trenutno v obdelavi. Vsaka zanka se izvede 16-krat in ker je vsak blok vhodnega sporočila obdelan v štirih zankah, je vsak blok vhodnega sporočila obdelan v skladu s shemo, prikazano na sl. 4, 64-krat. Če si 512-bitni vhodni blok predstavljamo kot šestnajst 32-bitnih besed, potem je vsaka 32-bitna vhodna beseda uporabljena štirikrat, enkrat v vsakem ciklu, in vsak element tabele T, sestavljene iz 64 32-bitnih besed, je uporabljen samo enkrat enkrat. Po vsakem koraku zanke se štiri besede A, B, C in D zavrtijo v levo. Na vsakem koraku se spremeni samo ena od štirih besed medpomnilnika ABCD. Zato se vsaka beseda vmesnega pomnilnika spremeni 16-krat in nato 17-krat na koncu, da se ustvari končni izhod tega bloka.

prebaviti.

2. Hitrost: programska izvedba algoritma mora biti dovolj hitra. Zlasti mora biti algoritem dovolj hiter na 32-bitni arhitekturi. Zato algoritem temelji na preprostem nizu elementarnih operacij na 32-bitnih besedah.

3. Enostavnost in kompaktnost: algoritem mora biti preprost za opis in programiranje, brez velikih programov ali nadomestnih tabel. Te značilnosti nimajo le očitnih programskih prednosti, ampak so zaželene tudi z varnostnega vidika, saj je bolje imeti preprost algoritem za analizo možnih šibkih točk.

4. Arhitektura Little-endian je zaželena: Nekatere arhitekture procesorjev (kot je linija Intel 80xxx) shranijo leve bajte besede na mesto naslova bajtov Little-endian. Drugi (kot je SUN Sparcstation) shranijo desne bajte besede na naslovni položaj nizkega bajta (velika dodatna konstanta MD4 v prvi zanki se ne uporablja. Podobna dodatna konstanta se uporablja za vsakega od korakov v drugi zanki Druga dodatna konstanta se uporablja za vsakega od korakov v tretji zanki. Zgoščena koda je funkcija vsakega bita vhoda je malo verjetno, da sta dve sporočili izbrani naključno, čeprav imata enak izhodni vzorec povzroči enak izhod za dve različni vhodni vrednosti v medpomnilniku ABCD. Na MD5 ni možnosti za razširitev tega pristopa do uspešnega napada.

In tako naprej.). Izbira ene ali druge zgoščevalne funkcije je odvisna od posebnosti problema, ki ga rešujemo. Najenostavnejši primeri zgoščevalnih funkcij so kontrolna vsota ali CRC.

Na splošno med izvornimi podatki in zgoščeno kodo ni ujemanja ena proti ena. Zato obstaja veliko nizov podatkov, ki dajejo enake zgoščene kode - tako imenovane kolizije. Verjetnost kolizij ima pomembno vlogo pri ocenjevanju "kakovosti" zgoščevalnih funkcij.

Kontrolne vsote

Nezapleteni, izjemno hitri in enostavno implementirani v algoritme strojne opreme, ki se uporabljajo za zaščito pred nenamernimi popačenji, vključno z napakami strojne opreme.

Hitrost izračuna je več deset in stokrat hitrejša od kriptografskih zgoščevalnih funkcij in veliko enostavnejša v strojni izvedbi.

Cena za tako visoko hitrost je pomanjkanje kriptografske moči - preprosta priložnost za prilagoditev sporočila vnaprej znani količini. Poleg tega so kontrolne vsote (običajno: 32 bitov) običajno nižje kot kriptografske zgoščene vrednosti (običajno: 128, 160 in 256 bitov), ​​kar pomeni, da lahko pride do nenamernih kolizij.

Najenostavnejši primer takšnega algoritma je razdelitev sporočila na 32- ali 16-bitne besede in njihovo seštevanje, kar se uporablja na primer v TCP/IP.

Praviloma je takšen algoritem potreben za sledenje tipičnim napakam strojne opreme, kot je več zaporednih napačnih bitov na dano dolžino. Tako imenovana družina algoritmov "ciklična redundancijska koda" izpolnjuje te zahteve. Sem spada na primer CRC32, ki se uporablja v opremi ZIP.

Kriptografske zgoščevalne funkcije

Med številnimi obstoječimi zgoščevalnimi funkcijami je običajno razlikovati kriptografsko močne zgoščevalne funkcije, ki se uporabljajo v kriptografiji. Najprej mora imeti funkcijo zgoščevanja, odporno na kripto odporen na trke dve vrsti:

Uporaba zgoščevanja

Zgoščevalne funkcije se uporabljajo tudi v nekaterih podatkovnih strukturah – zgoščevalnih tabelah in kartezičnih drevesih. Zahteve za zgoščevalno funkcijo so v tem primeru drugačne:

• dobro mešanje podatkov
• hiter algoritem izračuna

Usklajevanje podatkov

Na splošno lahko to aplikacijo opišemo kot preverjanje, ali so nekatere informacije enake izvirniku, brez uporabe izvirnika. Za uskladitev se uporabi zgoščena vrednost informacij, ki se preverjajo. Obstajata dve glavni področji te aplikacije:

Preverjanje napak

Na primer, kontrolna vsota se lahko prenaša po komunikacijskem kanalu skupaj z glavnim besedilom. Na prejemnem koncu je mogoče kontrolno vsoto ponovno izračunati in primerjati s poslano vrednostjo. Če se odkrije neskladje, to pomeni, da je med prenosom prišlo do popačenja in je mogoče zahtevati ponovno predvajanje.

Gospodinjski analog zgoščevanja je v tem primeru lahko tehnika, ko se med premikanjem število kosov prtljage shrani v spomin. Potem, če želite preveriti, se vam ni treba spomniti vsakega kovčka, ampak jih samo preštejte. Ujemanje pomeni, da noben kovček ni izgubljen. To pomeni, da je število kosov prtljage njegova zgoščena koda.

Preverjanje gesla

V večini primerov gesla niso shranjena na ciljih, shranjene so samo njihove zgoščene vrednosti. Shranjevanje gesel ni priporočljivo, saj bo v primeru nepooblaščenega dostopa do datoteke s frazami napadalec izvedel vsa gesla in jih bo lahko takoj uporabil, pri shranjevanju zgoščevalnih vrednosti pa se bo naučil samo zgoščevalnih vrednosti. ​​ki jih ni mogoče spremeniti v izvirne podatke, v tem primeru geslo. Med postopkom avtentikacije se zgoščena vrednost vnesenega gesla izračuna in primerja s shranjeno.

Primer v tem primeru bi bil GNU/Linux in Microsoft Windows XP. Shranjujejo samo zgoščene vrednosti gesel iz uporabniških računov.

Pospešite pridobivanje podatkov

Na primer, ko so besedilna polja zapisana v bazo podatkov, je mogoče izračunati njihovo zgoščevalno kodo in podatke postaviti v razdelek, ki ustreza tej zgoščevalni kodi. Potem boste morali pri iskanju podatkov najprej izračunati zgoščeno kodo besedila in takoj boste vedeli, v katerem delu ga morate iskati, to pomeni, da ne boste morali iskati po celotni bazi podatkov, ampak le v enem delu (to močno pospeši iskanje).

Pogost analog zgoščevanja v tem primeru je lahko umeščanje besed v slovar po abecednem vrstnem redu. Prva črka besede je njena zgoščevalna koda, pri iskanju pa ne pregledamo celotnega slovarja, temveč samo želeno črko.

Seznam algoritmov

• SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512)
• RIPEMD-160
• RIPEMD-320
• Snefru
• Tiger (Whirlpool
• Internetna kontrolna vsota IP (RFC 1071)

Povezave

Fundacija Wikimedia. 2010.

• Heshan Moheyan
• Hash koda

Oglejte si, kaj je "zgoščevalna funkcija" v drugih slovarjih:

Zgoščevalna funkcija- funkcija, ki izvaja zgoščevanje podatkovnega polja s preslikavo vrednosti iz (zelo) velikega nabora vrednosti v (bistveno) manjši nabor vrednosti. V angleščini: Hash function Glej tudi: Kriptografski algoritmi Finančni... ... Finančni slovar

kriptografsko zgoščevalno funkcijo- Funkcija, ki pretvori besedilo poljubne dolžine v besedilo fiksne (v večini primerov manjše) dolžine. Glavna uporaba zgoščevalnih funkcij je v shemi digitalnega podpisa. Ker se zgoščevalna funkcija izračuna hitreje kot digitalni podpis, potem namesto... ...

Enosmerna zgoščevalna funkcija- hash funkcija, ki je računsko nepovratna funkcija. V angleščini: One way hash function Glej tudi: Cryptographic algorithms Financial Dictionary Finam... Finančni slovar

TIGER - zgoščevalna funkcija- Zgoščevalna funkcija TIGER, ki sta jo leta 1996 razvila Ros Anderson in Eli Beham. Zgoščevalna funkcija TIGER je nova hitra zgoščevalna funkcija, ki je zasnovana tako, da je zelo hitra v sodobnih računalnikih, zlasti v 64-bitnih računalnikih. TIGER... ... Wikipedia

enosmerna zgoščevalna funkcija- Za enosmerno funkcijo je računsko nemogoče najti dva različna argumenta, pri katerih sta njeni vrednosti enaki. [] Teme informacijska varnost EN enosmerna zgoščevalna funkcija ... Priročnik za tehnične prevajalce

Tiger (zgoščena funkcija)- Tiger hash funkcija, ki sta jo leta 1995 razvila Ros Anderson in Eli Beham. Tiger je bil zasnovan za posebno hitro delovanje na 64-bitnih računalnikih. Tiger nima patentnih omejitev, lahko ga prosto uporabljate z... ... Wikipedijo

hash funkcija- zgoščevalna funkcija 1. Funkcija, ki nadzoruje proces vnašanja podatkov v zgoščevalno tabelo, določanje (naslovov prostih celic. 2. Funkcija, ki predstavlja preslikavo fragmenta odprtega sporočila v šifriran niz fiksne dolžine. v ... ... Priročnik za tehnične prevajalce

Zgoščena tabela- Zgoščevalna tabela je v programiranju podatkovna struktura, ki implementira vmesnik asociativnega polja, in sicer omogoča shranjevanje parov (ključ, vrednost) in izvajanje treh operacij: operacijo dodajanja novega para, operacijo iskanja in brisanje delovanje... Wikipedia

Hash koda- Zgoščevanje (včasih zgoščevanje, angleško hashing) pretvorba vhodnega podatkovnega niza poljubne dolžine v izhodni bitni niz fiksne dolžine. Take transformacije imenujemo tudi zgoščevalne funkcije ali konvolucijske funkcije, njihovi rezultati pa... ... Wikipedia

Trk zgoščene funkcije- Trk zgoščevalne funkcije H sta dva različna vhodna podatkovna bloka x in y, tako da je H(x) = H(y). Trki obstajajo pri večini zgoščevalnih funkcij, vendar je pri "dobrih" zgoščevalnih funkcijah pogostost njihovega pojavljanja blizu teoretičnega minimuma. V... ... Wikipediji

Pogosto pri nalaganju torrentov ali samih datotek v opisu piše nekaj takega kot "ad33e486d0578a892b8vbd8b19e28754" (na primer v ex.ua), pogosto s predpono "md5". To je zgoščevalna koda – rezultat, ki ga zgoščevalna funkcija ustvari po obdelavi vhodnih podatkov. Prevedeno iz angleščine hash pomeni zmešnjava, marihuana, trava ali jed iz drobno sesekljanega mesa in zelenjave. zelo, zelo težko, lahko bi rekli skoraj nemogoče. Potem se pojavi vprašanje: "Zakaj je vse to sploh potrebno?" O tem bomo razpravljali v tem članku.

Kaj je zgoščevalna funkcija in kako deluje?

Ta funkcija je zasnovana za pretvorbo dohodnih podatkov poljubno velike velikosti v rezultat s fiksno dolžino. Postopek takšne pretvorbe imenujemo zgoščevanje, rezultat pa je zgoščevanje ali zgoščena koda. Včasih se uporabljata tudi besedi »prstni odtis« ali »pregled sporočila«, vendar sta v praksi veliko manj pogosti. Obstaja veliko različnih algoritmov, kako lahko katero koli podatkovno matriko pretvorite v določeno zaporedje znakov določene dolžine. Najbolj razširjen algoritem se imenuje md5, ki je bil razvit že leta 1991. Kljub dejstvu, da je danes md5 nekoliko zastarel in ni priporočljiv za uporabo, je še vedno v uporabi in pogosto namesto besede "hash code" spletna mesta preprosto napišejo md5 in navedejo samo kodo.

Zakaj je potrebna zgoščevalna funkcija?

Ob poznavanju rezultata je skoraj nemogoče določiti vhodne podatke, a isti vhodni podatki dajejo enak rezultat. Zato se funkcija zgoščevanja (imenovana tudi funkcija konvolucije) pogosto uporablja za shranjevanje zelo pomembnih informacij, kot so geslo, prijava, ID številka in drugi osebni podatki. Namesto da bi primerjali informacije, ki jih uporabnik vnese, s tistimi, ki so shranjeni v bazi podatkov, se primerjajo njihove zgoščene vrednosti. To zagotavlja, da v primeru nenamernega uhajanja informacij nihče ne bo mogel uporabiti pomembnih podatkov za lastne namene. S primerjavo zgoščene kode je prav tako priročno preveriti, ali se datoteke pravilno prenašajo iz interneta, še posebej, če je med prenosom prišlo do prekinitev povezave.

Zgoščevalne funkcije: kaj so? T

Odvisno od namena je zgoščevalna funkcija lahko ena od treh vrst:

1. Funkcija za preverjanje celovitosti informacij

Ko se dogaja prek omrežja, se izračuna razpršitev paketa in ta rezultat se prav tako prenese skupaj z datoteko. Po prejemu se zgoščevalna koda ponovno izračuna in primerja z vrednostjo, prejeto po omrežju. Če se koda ne ujema, to pomeni napake in poškodovani paket bo ponovno poslan. Ta funkcija ima visoko hitrost izračuna, vendar majhno število zgoščenih vrednosti in slabo stabilnost. Primer te vrste: CRC32, ki ima le 232 različnih vrednosti.

2. Kriptografska funkcija

Uporablja se za zaščito pred (ND). Omogočajo preverjanje, ali je prišlo do poškodbe podatkov zaradi nesreče med prenosom datotek po omrežju. Pravi hash je v tem primeru javno dostopen, hash dobljene datoteke pa je mogoče izračunati s številnimi različnimi programi. Takšne funkcije imajo dolgo in stabilno življenjsko dobo, iskanje kolizij (možnega sovpadanja rezultatov iz različnih izvornih podatkov) pa je zelo težavno. To so funkcije, ki se uporabljajo za shranjevanje gesel (SH1, SH2, MD5) in drugih dragocenih informacij v bazi podatkov.

3. Funkcija, zasnovana za ustvarjanje učinkovite strukture podatkov

Njegov cilj je kompaktna in dokaj urejena organizacija informacij v posebni strukturi, imenovani zgoščena tabela. Takšna tabela vam omogoča dodajanje novih informacij, brisanje informacij in iskanje potrebnih podatkov z zelo veliko hitrostjo.

12. maj 2010 ob 01:28

Hash algoritmi

• Varnost informacij

Verjamem, da veliko ljudi ve, da ameriški nacionalni inštitut za standarde in tehnologijo (NIST) od leta 2007 organizira natečaj za razvoj zgoščevalnega algoritma, ki bi nadomestil SHA-1 in družino algoritmov SHA-2. Vendar je bila ta tema na spletnem mestu iz nekega razloga zanemarjena. Pravzaprav me je to pripeljalo do tebe. Predstavljam vam vrsto člankov, posvečenih zgoščevalnim algoritmom. V tej seriji bomo skupaj preučili osnove zgoščevalnih funkcij, razmislili o najbolj znanih algoritmih zgoščevanja, se potopili v ozračje tekmovanja SHA-3 in razmislili o algoritmih, ki trdijo, da bodo zmagali, in jih bomo zagotovo preizkusili. Če bo mogoče, bodo upoštevani tudi ruski standardi zgoščevanja.

O meni

Študent Katedre za informacijsko varnost.

O zgoščevanju

Dandanes skoraj nobena kriptografska aplikacija ni popolna brez uporabe zgoščevanja.
Zgoščevalne funkcije so funkcije, namenjene "stiskanju" poljubnega sporočila ali niza podatkov, običajno zapisanega v binarni abecedi, v nek bitni vzorec s fiksno dolžino, imenovan konvolucija. Zgoščevalne funkcije imajo različne aplikacije pri izvajanju statističnih poskusov, testiranju logičnih naprav in konstruiranju algoritmov za hitro iskanje in preverjanje celovitosti zapisov v zbirkah podatkov. Glavna zahteva za zgoščevalne funkcije je enakomerna porazdelitev njihovih vrednosti, ko so vrednosti argumentov naključno izbrane.
Kriptografska zgoščevalna funkcija je katera koli zgoščevalna funkcija, ki je kriptografsko stabilna, kar pomeni, da izpolnjuje številne zahteve, specifične za kriptografske aplikacije. V kriptografiji se zgoščevalne funkcije uporabljajo za reševanje naslednjih težav:
- izgradnja sistemov za spremljanje celovitosti podatkov med njihovim prenosom ali shranjevanjem,
- avtentikacija vira podatkov.

Vsaka funkcija se imenuje zgoščevalna funkcija h:X -> Y, enostavno izračunljiva in taka, da za vsako sporočilo M pomen h(M) = H (konvolucija) ima fiksno dolžino bita. X- nabor vseh sporočil, Y- niz binarnih vektorjev fiksne dolžine.

Zgoščevalne funkcije so praviloma zgrajene na podlagi tako imenovanih enostopenjskih kompresijskih funkcij y = f(x 1, x 2) dve spremenljivki, kjer x 1, x 2 in l- binarni vektorji dolžine m, n in n v skladu s tem in n je konvolucijska dolžina in m- dolžina bloka sporočila.
Da bi dobili vrednost h(M) sporočilo je najprej razdeljeno na bloke po dolžini m(hkrati, če dolžina sporočila ni večkratnik m nato se zadnji blok dopolnjuje na nek poseben način, dokler ni dokončan), in nato do nastalih blokov M 1, M 2,.., M N uporabite naslednji zaporedni postopek za izračun konvolucije:

H o = v,
H i = f(M i ,H i-1), i = 1,.., N,
h(M) = H N

Tukaj v- neka konstanta, pogosto imenovana inicializacijski vektor. Ona gre ven
iz različnih razlogov in je lahko skrivna konstanta ali nabor naključnih podatkov (na primer vzorec datuma in ure).
S tem pristopom so lastnosti zgoščevalne funkcije popolnoma določene z lastnostmi enostopenjske kompresijske funkcije.

Obstajata dve pomembni vrsti kriptografskih zgoščevalnih funkcij - ključ in brez ključa. Ključne zgoščevalne funkcije se imenujejo kode za preverjanje pristnosti sporočil. Omogočajo, da brez dodatnih sredstev zagotovimo tako pravilnost vira podatkov kot celovitost podatkov v sistemih z uporabniki, ki si med seboj zaupajo.
Funkcije zgoščevanja brez ključa se imenujejo kode za odkrivanje napak. Omogočajo zagotavljanje celovitosti podatkov z dodatnimi sredstvi (na primer šifriranje). Te zgoščevalne funkcije je mogoče uporabiti v sistemih z zaupanja vrednimi in nezaupljivimi uporabniki.

O statističnih lastnostih in zahtevah

Kot sem že rekel, je glavna zahteva za hash funkcije enakomerna porazdelitev njihovih vrednosti, ko so vrednosti argumentov naključno izbrane. Za kriptografske zgoščevalne funkcije je pomembno tudi, da že najmanjša sprememba argumenta povzroči močno spremembo vrednosti funkcije. To se imenuje učinek plazu.

Ključne funkcije zgoščevanja imajo naslednje zahteve:
- nezmožnost izdelave,
- nezmožnost spreminjanja.

Prva zahteva pomeni, da je zelo težko najti sporočilo s pravilno vrednostjo strnjenja. Druga je velika težava pri izbiri drugega sporočila s pravilno vrednostjo konvolucije za dano sporočilo z znano vrednostjo konvolucije.

Zahteve za funkcije brez ključa so:
- enosmernost,
- odpornost proti trkom,
- odpor do iskanja druge praslike.

Enosmernost se nanaša na veliko težavo pri iskanju sporočila na podlagi dane vrednosti konvolucije. Upoštevati je treba, da trenutno ni v uporabi zgoščevalnih funkcij z dokazano enosmernostjo.
Odpornost na trčenje se nanaša na težavo pri iskanju para sporočil z enakimi vrednostmi konvolucije. Običajno odkritje načina za konstruiranje kolizij s strani kriptoanalitikov služi kot prvi signal, da algoritem postaja zastarel in da ga je treba hitro zamenjati.
Odpor do iskanja druge predslike se nanaša na težave pri iskanju drugega sporočila z enako vrednostjo konvolucije za dano sporočilo z znano vrednostjo konvolucije.

To je bil teoretični del, ki nam bo koristil v prihodnje...

O priljubljenih algoritmih zgoščevanja

Algoritmi CRC16/32- kontrolna vsota (ne kriptografska pretvorba).

Algoritmi MD2/4/5/6. So stvaritev Rona Rivesta, enega od avtorjev algoritma RSA.
Algoritem MD5 je bil nekoč zelo priljubljen, vendar so se prvi predpogoji za hekanje pojavili v poznih devetdesetih letih, zdaj pa njegova priljubljenost hitro upada.
Algoritem MD6 je z oblikovalskega vidika zelo zanimiv algoritem. Bil je nominiran za tekmovanje SHA-3, vendar avtorji žal niso imeli časa, da bi ga standardizirali in tega algoritma ni na seznamu kandidatov, ki so prešli drugi krog.

Algoritmi ravnila SHA Algoritmi, ki se danes pogosto uporabljajo. Obstaja aktiven prehod s standardov različice SHA-1 na SHA-2. SHA-2 je skupno ime za algoritme SHA224, SHA256, SHA384 in SHA512. SHA224 in SHA384 sta v bistvu analoga SHA256 oziroma SHA512, le po izračunu konvolucije se nekatere informacije v njem zavržejo. Uporabljati jih je treba le za zagotovitev združljivosti z opremo starejših modelov.

ruski standard - GOST 34.11-94.

V naslednjem članku

Pregled algoritmov MD (MD4, MD5, MD6).

Literatura

A. P. Alferov, Osnove kriptografije.

Bruce Schneier, Uporabna kriptografija.

Pri izmenjavi elektronskih dokumentov po komunikacijskem omrežju se znatno zmanjšajo stroški obdelave in hrambe dokumentov ter pospeši njihovo iskanje. Toda pri tem se pojavi problem avtentikacije avtorja dokumenta in dokumenta samega, tj. ugotavljanje pristnosti avtorja in odsotnosti sprememb v prejetem dokumentu. V konvencionalni (papirni) informatiki so ti problemi rešeni zaradi dejstva, da so informacije v dokumentu in lastnoročni podpis avtorja strogo vezani na fizični medij (papir). Pri elektronskih dokumentih na strojnih medijih te povezave ni.

Namen avtentikacije elektronskih dokumentov je zaščititi pred možnimi vrstami zlonamernih dejanj, ki vključujejo:

• aktivno prestrezanje- vsiljivec, ki se poveže z omrežjem, prestreže dokumente (datoteke) in jih spremeni;
• maškarada- naročnik C pošlje dokument naročniku B v imenu naročnika A;
• odpadništvo- naročnik A izjavi, da ni poslal sporočila naročniku B, čeprav ga je v resnici;
• zamenjava- naročnik B spremeni ali ustvari nov dokument in izjavi, da ga je prejel od naročnika A;
• ponovite- naročnik C ponovi predhodno posredovan dokument, ki ga je naročnik A poslal naročniku B.

Tovrstna zlonamerna dejanja lahko povzročijo veliko škodo bančnim in komercialnim strukturam, državnim podjetjem in organizacijam ter posameznikom, ki pri svojih dejavnostih uporabljajo računalniške informacijske tehnologije.

Pri obdelavi dokumentov v elektronski obliki so tradicionalni načini ugotavljanja pristnosti z lastnoročnim podpisom in žigom na papirnem dokumentu popolnoma neprimerni. Bistveno nova rešitev je elektronski digitalni podpis ( EDS).

Elektronski digitalni podpis se uporablja za avtentikacijo besedil, ki se prenašajo po telekomunikacijskih kanalih. Funkcionalno je podoben običajnemu lastnoročnemu podpisu in ima svoje glavne prednosti:

• potrjuje, da podpisano besedilo izhaja od osebe, ki je podpisala;
• tej osebi ne daje možnosti, da zavrne obveznosti, povezane s podpisanim besedilom;
• zagotavlja celovitost podpisanega besedila.

Digitalni podpis je razmeroma majhna količina dodatnih digitalnih informacij, ki se prenašajo skupaj s podpisanim besedilom.

Sistem digitalnega podpisovanja vključuje dva postopka: 1) postopek podpisovanja; 2) postopek overitve podpisa. Postopek podpisovanja uporablja tajni ključ pošiljatelja sporočila, postopek preverjanja podpisa pa javni ključ pošiljatelja.

Pri generiranju elektronskega podpisa pošiljatelj najprej izračuna hash funkcija h(M) podpisanega besedila M. Izračunana vrednost zgoščevalne funkcije h(M) je en kratek blok informacij m, ki označuje celotno besedilo M kot celoto. Število m je nato šifrirano s tajnim ključem pošiljatelja. Nastali par številk predstavlja digitalni podpis za dano besedilo M.

Pri preverjanju digitalnega podpisa prejemnik sporočila ponovno izračuna zgoščevalno funkcijo m = h(M) besedila M, prejetega po kanalu, nato pa z javnim ključem pošiljatelja preveri, ali prejeti podpis ustreza izračunani vrednosti zgoščevalne funkcije. m.

Temeljna točka v sistemu EDS je nezmožnost ponarejanja digitalnega podpisa uporabnika brez poznavanja njegovega tajnega podpisnega ključa.

Vsako datoteko lahko uporabite kot podpisan dokument. Podpisana datoteka se ustvari iz nepodpisane datoteke z dodajanjem enega ali več elektronskih podpisov.

Vsak podpis vsebuje naslednje podatke:

• datum podpisa;
• datum poteka veljavnosti ključa za ta podpis;
• podatki o osebi, ki je podpisala datoteko (polno ime, položaj, kratko ime podjetja);
• ID podpisnika (ime javnega ključa);
• dejanski digitalni podpis.

2. Enosmerne zgoščevalne funkcije

Zgoščevalna funkcija hash- fino sesekljajte in premešajte) je zasnovan za stiskanje podpisanega dokumenta na več deset ali sto bitov. Zgoščevalna funkcija h(·) vzame kot argument sporočilo (dokument) M poljubne dolžine in vrne zgoščeno vrednost h(M)=H fiksne dolžine. Običajno so zgoščene informacije stisnjena binarna predstavitev osnovnega sporočila poljubne dolžine. Upoštevati je treba, da je vrednost zgoščevalne funkcije h(M) na kompleksen način odvisna od dokumenta M in ne omogoča obnovitve samega dokumenta M.

Zgoščevalna funkcija mora izpolnjevati številne pogoje:

1. zgoščevalna funkcija mora biti občutljiva na vse vrste sprememb v besedilu M, kot so vstavitve, emisije, permutacije itd.;
2. zgoščevalna funkcija mora imeti lastnost ireverzibilnosti, to pomeni, da mora biti naloga izbire dokumenta M", ki bi imel zahtevano vrednost zgoščevalne funkcije, računsko nerešljiva;
3. verjetnost, da se zgoščevalni vrednosti dveh različnih dokumentov (ne glede na njuni dolžini) ujemata, bi morala biti zanemarljiva.

Večina zgoščenih funkcij temelji na enosmerni funkciji f(·), ki proizvede izhodno vrednost dolžine n, ko ji dodelimo dve vhodni vrednosti dolžine n. Ti vhodi so izvorni besedilni blok M in zgoščena vrednost H i-1 prejšnjega besedilnega bloka (slika 1).

Slika 1. Konstrukcija enosmerne zgoščevalne funkcije

Н i = f(М i, Н i-1).

Zgoščena vrednost, izračunana ob vnosu zadnjega bloka besedila, postane zgoščena vrednost celotnega sporočila M.

Posledično enosmerna zgoščevalna funkcija vedno proizvede izhod fiksne dolžine n (ne glede na dolžino vhodnega besedila).

Osnove zgoščevalnih funkcij

Splošno sprejeto načelo za konstruiranje zgoščevalnih funkcij je iterativno zaporedno vezje. V skladu s to tehniko je jedro algoritma pretvorba k bitov v n bitov. Vrednost n je dolžina rezultata zgoščevalne funkcije, k pa je poljubno število, večje od n. Osnovna transformacija mora imeti vse lastnosti zgoščevalne funkcije, tj. ireverzibilnost in nezmožnost invariantne spremembe vhodnih podatkov.

Zgoščevanje se izvede z uporabo vmesne pomožne spremenljivke n bitov. Za začetno vrednost je izbrana poljubna vrednost, ki je vsem poznana, na primer 0.

Vhodni podatki so razdeljeni na bloke (k-n) bitov. Pri vsaki iteraciji zgoščevanja se naslednji (k-n)-bitni del vhodnih podatkov združi z vrednostjo vmesne vrednosti, pridobljene pri prejšnji iteraciji, na dobljenem k-bitnem bloku pa se izvede osnovna transformacija. Posledično se celotno vhodno besedilo "pomeša" z začetno vrednostjo pomožne vrednosti. Zaradi narave transformacije se pogosto imenuje osnovna funkcija kompresijsko. Vrednost pomožne vrednosti po zadnji iteraciji gre na izhod zgoščevalne funkcije (slika 2). Včasih se na dobljeni vrednosti izvedejo dodatne transformacije. Toda če je funkcija stiskanja zasnovana z zadostno stopnjo odpornosti, so te transformacije nepotrebne.

Pri iterativnem oblikovanju zgoščevalne funkcije se pojavita dve povezani vprašanji: kako ravnati s podatki, ki niso večkratnik (k-n), in kako dodati dolžino dokumenta zgoščeni vsoti, če je to potrebno. Obstajata dve možnosti za rešitev teh težav. Pri prvi možnosti se na začetek dokumenta pred zgoščevanjem doda polje s fiksno dolžino (na primer 32 bitov), ​​v katerem je izvorna dolžina besedila zapisana v binarni obliki. Kombinirani podatkovni blok je nato dopolnjen z ničlami ​​do najbližjega večkratnika (k-n) velikosti velikosti. Pri drugi možnosti je dokument na desni strani obložen z enim bitom »1« in nato do velikosti večkratnika (k-n) bitov z biti »0«. Pri tej možnosti ni potrebe po polju dolžine - nobena dva različna dokumenta po poravnavi vzdolž meje dela ne bosta postala enaka.

Poleg bolj priljubljenih algoritmov zgoščevanja z enim prehodom obstajajo tudi algoritmi zgoščevanja z več prehodi. V tem primeru se blok vhodnih podatkov na stopnji razširitve večkrat ponovi in ​​šele nato razširi do najbližje meje dela.

Slika 2. Iterativna zgoščevalna funkcija

Enosmerne zgoščevalne funkcije, ki temeljijo na algoritmih simetričnih blokov

Enosmerno zgoščevalno funkcijo je mogoče sestaviti z algoritmom simetričnega bloka. Najbolj očiten pristop je šifriranje sporočila M z uporabo blokovnega algoritma v načinu CBC ali CFB z uporabo fiksnega ključa in nekega inicializacijskega vektorja IV. Zadnji blok šifriranega besedila lahko obravnavamo kot zgoščevalno vrednost sporočila M. S tem pristopom ni vedno mogoče izdelati varne enosmerne zgoščevalne funkcije, vedno pa je mogoče pridobiti kodo za preverjanje pristnosti sporočila MAC (Preverjanje pristnosti sporočila Koda).

Varnejšo različico zgoščevalne funkcije lahko dobite z uporabo bloka sporočil kot ključa, prejšnje zgoščene vrednosti kot vhoda in trenutne zgoščene vrednosti kot izhoda. Prave zgoščene funkcije so zasnovane tako, da so še bolj zapletene. Dolžina bloka je običajno določena z dolžino ključa, dolžina zgoščene vrednosti pa je enaka dolžini bloka.

Ker je večina blokovnih algoritmov 64-bitnih, so nekatere sheme zgoščevanja zasnovane tako, da je vrednost zgoščevanja dvakrat daljša od dolžine bloka.

Ob predpostavki, da je nastala zgoščevalna funkcija pravilna, varnost sheme zgoščevanja temelji na varnosti osnovnega algoritma blokov. Shema zgoščevanja, v kateri je dolžina zgoščene vrednosti enaka dolžini bloka, je prikazana na sliki 3. Njeno delo opisujejo izrazi:

H 0 = I n, H i = E A (B) Å C, kjer je Å dodatek po modulu 2 (izključni ALI); I n - neka naključna začetna vrednost; A, B, C lahko zavzamejo vrednosti M i, H i-1, (M i Å H i-1) ali pa so konstante.

Slika 3. Posplošena shema za generiranje zgoščevalne funkcije

Sporočilo M je razdeljeno na bloke M i sprejete dolžine, ki se obdelujejo enega za drugim.

Tri različne spremenljivke A, B, C lahko zavzamejo eno od štirih možnih vrednosti, tako da načeloma lahko dobite 64 variant splošnega tokokroga te vrste. Od teh je 52 različic bodisi trivialno šibkih bodisi nevarnih. Preostalih 12 varnih shem zgoščevanja, v katerih je dolžina zgoščene vrednosti enaka dolžini bloka, je navedenih v tabeli 1.

Tabela 1

Številka sheme Funkcija zgoščevanja 1 H i = E H i-1 (M i) Å M i 2 N i = E H i-1 (M i Å N i-1) Å M i Å N i-1 3 N i = E H i-1 (M i) Å M i Å N i-1 4 H i = E H i-1 (M i Å H i-1) Å M i 5 Н i = Е M i (Н i-1) Å Н i-1 6 N i = E M i (M i Å N i-1) Å M i Å N i-1 7 N i = E M i (H i-1) Å M i Å N i-1 8 N i = E M i (M i Å N i-1) Å N i-1 9 H i = E M i Å H i-1 (M i) Å M i 10 H i = E M i Å H i-1 (H i-1) Å H i-1 11 H i = E M i Å H i-1 (M i) Å H i-1 12 H i = E M i Å H i-1 (H i-1) Å M i

Prve štiri sheme zgoščevanja, ki so varne pred vsemi napadi, so prikazane na sliki 4.

Slika 4. Štiri varne sheme zgoščevanja

Pomanjkljivost zgoščevalnih funkcij, zasnovanih na bločnih algoritmih, je njihova nekoliko zmanjšana hitrost delovanja. Bistvo je, da je enako moč glede na dve glavni zahtevi za zgoščevalno funkcijo mogoče doseči v veliko manjšem številu operacij na vhodnih podatkih. Toda za to mora biti algoritem na začetku zasnovan posebej na podlagi tandemov zahtev (odpornost, hitrost). Nato obravnavamo tri neodvisne kripto-močne algoritme zgoščevanja, ki se danes najpogosteje uporabljajo.

algoritem MD5

Algoritem MD5(Message Digest #5), ki ga je oblikoval Ronald Rivers. MD5 uporablja 4 iterativne pretvorbe na treh 32-bitnih vrednostih U, V in W:

F(U,V,W)=(U IN V) ALI ((NE U) IN W) g(U,V,W)=(U IN W) ALI (V IN (NE W)) h(U, V,W)=U XOR V XOR W k(U,V,W)=V XOR (U ALI (NE W)).

Algoritem uporablja naslednje konstante:

• začetne konstante vmesnih količin - H=67452301 16, H=EFCDAB89 16, H=98BADCFE 16, H=10325476 16;
• aditivne konstante v krogih so y[j]=HIGHEST_32_BITS(ABS(SIN(j+1))) j=0...63, kjer funkcija HIGHEST_32_BITS(X) loči najpomembnejših 32 bitov od binarne predstavitve frakcijskega število X in operand SIN(j+1) velja za radiane;
• matrika vrstnega reda izbire celic v krogih - z = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 1, 6, 11, 0 , 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12, 5, 8, 11, 4, 1, 4, 7, 10, 13, 0, 3, 6, 9 , 12, 15, 2, 0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9);
• matrika bitnih cikličnih premikov v levo - s = (7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21).

Na začetni stopnji se vhodni podatkovni blok dopolni z enim bitom "1". Nato se mu doda dovolj bitov "0", tako da je ostanek pri deljenju bloka s 512 448. Nazadnje se bloku doda 64-bitna vrednost, ki shrani prvotno dolžino dokumenta. Nastali vhodni tok ima dolžino, ki je večkratnik 512 bitov.

Vsak 512-bitni blok, predstavljen kot 16 32-bitnih vrednosti X...X, se prenese skozi funkcijo stiskanja, ki ga premeša s pomožnim blokom (H,H,H,H):

(A,B,C,D) = (H,H,H,H) cikel v j od 0 do 15 T = (A + f(B,C,D) + x] + y[j]) ROL s [j] (A,B,C,D) = (D,B+T,B,C) cikel ob koncu_cikla z j od 16 do 31 T = (A + g(B,C,D) + x] + y [j]) ROL s[j] (A,B,C,D) = (D,B+T,B,C) cikel konca_cikla na j od 32 do 47 T = (A + h(B,C,D) ) + x] + y[j]) ROL s[j] (A,B,C,D) = (D,B+T,B,C) cikel konca_cikla na j od 48 do 63 T = (A + k (B,C,D) + x] + y[j]) ROL s[j] (A,B,C,D) = (D,B+T,B,C) konec_cikla (H,H,H, H) = (H+A,H+B,H+C,H+D)

Ko gredo vsi 512-bitni bloki skozi postopek mešanja, so začasne spremenljivke H,H,H,H, 128-bitna vrednost pa je posredovana izhodu funkcije zgoščevanja.

Algoritem MD5, ki temelji na predhodnem razvoju Ronalda Riversa MD4, je bil namenjen zagotavljanju še večje meje varnosti pred kripto napadi. MD5 je zelo podoben MD4. Razlika je v najenostavnejših spremembah algoritmov prekrivanja in v tem, da ima MD4 48 prehodov glavne transformacije, MD5 pa 64. Kljub veliki popularnosti je MD4 "počasi, a zanesljivo" razbit. Najprej so se pojavile publikacije o napadih na poenostavljeni algoritem. Nato so trdili, da je mogoče najti dva vhodna bloka funkcije stiskanja MD4, ki ustvarita enak izhod. Končno se je leta 1995 izkazalo, da je za iskanje trka, tj. V manj kot minuti lahko ustvarite "razpršitveni dvojnik" za poljuben dokument in lahko dosežete "smiselnost" ponarejenega dokumenta (tj. prisotnost v njem samo znakov ASCII z določenimi "razumnimi" zakoni o lokaciji) v samo nekaj dni.

Algoritem varnega zgoščevanja SHA

Varen algoritem zgoščevanja SHA (Algoritem varnega zgoščevanja) sta leta 1992 razvila NIST in ameriška NSA v okviru standarda varnega zgoščevanja SHS (Secure Hash Standard). Algoritem zgoščevanja SHA je namenjen uporabi v povezavi z algoritmom za digitalni podpis DSA.

Ko je vhodno sporočilo M poljubne dolžine, manjše od 264 bitov, algoritem SHA proizvede 160-bitno izhodno sporočilo, imenovano izvleček sporočila MD (Message Digest). Ta povzetek sporočila se nato uporabi kot vhod v algoritem DSA, ki izračuna digitalni podpis sporočila M. Generiranje digitalnega podpisa za povzetek sporočila namesto sporočila samega izboljša učinkovitost postopka podpisovanja, saj je povzetek sporočila običajno veliko krajši od samega sporočila.

Isti izvleček sporočila mora izračunati uporabnik, ki preveri prejeti podpis, pri čemer uporabi prejeto sporočilo M kot vhod v algoritem SHA.

Algoritem zgoščevanja SHA se imenuje varen, ker je zasnovan tako, da je računsko nemogoče rekonstruirati sporočilo, ki ustreza danemu izvlečku, in tudi najti dve različni sporočili, ki bosta dali isti izvleček. Vsaka sprememba sporočila med prenosom bo zelo verjetno spremenila povzetek in sprejeti digitalni podpis ne bo preverjen.

Oglejmo si podrobneje delovanje algoritma zgoščevanja SHA. Najprej je prvotno sporočilo M podloženo, tako da postane večkratnik 512 bitov. Polnjenje sporočila se izvede tako, da se najprej doda 1, ki ji sledi toliko ničel, kolikor je potrebno, da se ustvari sporočilo, ki je 64 bitov krajše od večkratnika števila 512, in na koncu doda 64-bitna predstavitev dolžine izvirnega sporočila.

Pet 32-bitnih spremenljivk je inicializiranih v obliki:

A = 0x67452301 B = 0xEFCDAB89 C = 0x98BADCFE D = 0x10325476 E = 0xC3D2E1F0

Nato se začne glavna zanka algoritma. Obdela 512 bitov sporočila enega za drugim za vse 512-bitne bloke, ki so prisotni v sporočilu. Prvih pet spremenljivk A, B, C, D, E se kopirajo v druge spremenljivke a, b, c, d, e:

A = A, b = B, c = C, d = D, e = E

Glavna zanka vsebuje štiri zanke po 20 operacij. Vsaka operacija izvaja nelinearno funkcijo treh od petih spremenljivk a, b, c, d, e, nato pa izvede premik in seštevanje.

Algoritem SHA ima naslednji niz nelinearnih funkcij:

F t (Х, Y, Z) = (X Ù Y) Ú ((Ø X) Ù Z) za t = 0...19, f t (Х, Y, Z) =Х Å Y Å Z za t = 20...39, f t (X, Y, Z) = (X Ù Y) Ú (X Ù Z) Ú (Y Ù Z) za t = 40...59, f t (X, Y, Z) = X Å Y Å Z za t = 60...79, kjer je t številka operacije.

Algoritem uporablja tudi štiri konstante:

K t = 0x5A827999 za t = 0...19, K t = 0x6ED9EVA1 za t = 20...39, K t = 0x8F1ВВСDС za t = 40...59, K t = 0xСА62С1D6 za t = 60... 79.

Sporočilni blok se pretvori iz šestnajstih 32-bitnih besed (M 0 ... M 15) v osemdeset 32-bitnih besed (W 0 ... W 79) z uporabo naslednjega algoritma:

W t = M t za t = 0...15, W t = (W t-3 Å W t-8 Å W t-14 Å W t-16)<<< 1 для t = 16...79,
kjer je t številka operacije, W t je t-ti podblok razširjenega sporočila,<<< S - циклический сдвиг влево на S бит.

Ob upoštevanju uvedenega zapisa lahko glavni cikel osemdesetih operacij opišemo takole:

Krožite s t od 0 do 79 TEMP = (a<<< 5) + f t (b, c, d) + е + W t + К t е = d d = с с = (b <<< 30) b = а а = ТЕМР конец_цикла

Diagram za izvedbo ene operacije je prikazan na sliki 5.

Slika 5. Shema za izvedbo ene operacije algoritma SHA

Po koncu glavne zanke se vrednosti a, b, c, d, e dodajo A, B, C, D, E in algoritem začne obdelovati naslednji 512-bitni podatkovni blok. Končni rezultat je oblikovan kot veriženje vrednosti A, B, C, D, E.

Razlike med SHA in MD5 so naslednje:

• SHA ustvari 160-bitno zgoščeno vrednost, zato je bolj odporen na grobo silo in rojstnodnevne napade kot MD5, ki ustvari 128-bitne zgoščene vrednosti.
• Funkcija stiskanja SHA je sestavljena iz 80 korakov, ne iz 64 kot pri MD5.
• Razširitev vhodnih podatkov se ne izvede s preprostim ponavljanjem v drugačnem vrstnem redu, temveč s ponavljajočo se formulo.
• Postopek mešanja je zapleten

Domača standardna zgoščevalna funkcija

ruski standard GOST R 34.11-94 definira algoritem in postopek za izračun zgoščevalne funkcije za poljubno zaporedje binarnih znakov, ki se uporabljajo v kriptografskih metodah za obdelavo in zaščito informacij. Ta standard temelji na algoritmu za šifriranje blokov GOST 28147-89, čeprav bi načeloma lahko uporabili drug algoritem za šifriranje blokov s 64-bitnim blokom in 256-bitnim ključem.

Ta zgoščena funkcija ustvari 256-bitno zgoščeno vrednost.

Funkcija stiskanja H i = f(M i, H i-1) (oba operanda M i in H i-1 sta 256-bitni vrednosti) je definirana kot sledi:

1. 4 šifrirni ključi K j, j = 1...4 so generirani z linearnim mešanjem M i, H i-1 in nekaterih konstant C j.
2. Vsak ključ K j se uporablja za šifriranje 64-bitnih podbesed h j besede H i-1 v preprostem načinu zamenjave:
   S i = E Kj (h j) . Nastalo zaporedje S 4 , S 3 , S 2 , S 1 , dolgo 256 bitov, je shranjeno v začasni spremenljivki S .
3. Vrednost H i je kompleksna, čeprav linearna, mešalna funkcija S, M i, H i-1.

Pri izračunu končne zgoščene vrednosti sporočila M se upoštevajo vrednosti treh medsebojno povezanih spremenljivk:

N n - zgoščena vrednost zadnjega bloka sporočila;
Z je vrednost kontrolne vsote, dobljene s seštevanjem modula 2 vseh blokov sporočil;
L - dolžina sporočila.

Te tri spremenljivke in podloženi zadnji blok M" sporočila so združeni v končno zgoščeno vrednost, kot sledi:

Н = f (Z Å М", f (L, f(М", Н n)))).

Ta zgoščevalna funkcija je opredeljena s standardom GOST R 34.11-94 za uporabo v povezavi z ruskim standardom za elektronski digitalni podpis.

3. Algoritmi elektronskega digitalnega podpisa

Tehnologija za uporabo sistema digitalnega podpisovanja predvideva prisotnost omrežja naročnikov, ki si med seboj pošiljajo podpisane elektronske dokumente. Za vsakega naročnika se ustvari par ključev: tajni in javni. Tajni ključ naročnik hrani kot tajen in ga uporablja za generiranje elektronskega digitalnega podpisa. Javni ključ je znan vsem ostalim uporabnikom in je namenjen preverjanju digitalnega podpisa s strani prejemnika podpisanega elektronskega dokumenta. Z drugimi besedami, javni ključ je nujno orodje, ki vam omogoča preverjanje pristnosti elektronskega dokumenta in avtorja podpisa. Javni ključ ne omogoča izračuna tajnega ključa.

Za generiranje para ključev (tajnih in javnih) se v algoritmih za digitalno podpisovanje, tako kot v asimetričnih sistemih šifriranja, uporabljajo različne matematične sheme, ki temeljijo na uporabi enosmernih funkcij. Te sheme so razdeljene v dve skupini. Ta delitev temelji na znanih kompleksnih računskih problemih:

• problem faktorizacije (faktorizacije) velikih celih števil;
• problem diskretnega logaritma.

RSA algoritem digitalnega podpisa

Prvi in ​​najbolj znan specifični sistem EDS na svetu je bil sistem RSA, katerega matematično shemo so razvili leta 1977 na Massachusetts Institute of Technology v ZDA.

Najprej morate izračunati par ključev (zasebni in javni ključ). Da bi to naredil, pošiljatelj (avtor) elektronskih dokumentov izračuna dve veliki praštevili P in Q, nato pa najde njun produkt

N = P * Q in vrednost funkcije j (N) = (P-1)(Q-1).
Nato pošiljatelj izračuna število E iz pogojev: E £ j (N), GCD (E, j (N)) = 1
in številko D iz pogojev: D < N, E*D º 1 (mod j (N)).

Par številk (E, N) je javni ključ. Avtor posreduje ta par številk svojim korespondenčnim partnerjem, da preverijo svoje digitalne podpise. Številko D je avtor shranil kot skrivni ključ za podpis.

Splošna shema za generiranje in preverjanje digitalnega podpisa RSA je prikazana na sliki 6.

Slika 6. Splošna shema digitalnega podpisa RSA

Recimo, da želi pošiljatelj podpisati sporočilo M, preden ga pošlje. Najprej se sporočilo M (informacijski blok, datoteka, tabela) stisne s pomočjo zgoščevalne funkcije h(·) v celo število m:

M = h(M).

Nato se z zgoščeno vrednostjo m in tajnim ključem D izračuna digitalni podpis S pod elektronskim dokumentom M:

S = m D (mod N).

Par (M,S) se prenese na partnerja prejemnika kot elektronski dokument M, podpisan z digitalnim podpisom S, podpis S pa generira lastnik tajnega ključa D.

Po prejemu para (M,S) prejemnik izračuna zgoščeno vrednost sporočila M na dva različna načina. Najprej obnovi zgoščeno vrednost m" z uporabo kriptografske transformacije podpisa S z uporabo javnega ključa E:

M" = S E (mod N).

Poleg tega najde rezultat zgoščevanja prejetega sporočila M z uporabo iste zgoščevalne funkcije h(·):

M = h(M).

Če se upošteva enakost izračunanih vrednosti, tj.

S E (mod N) = h (M),
potem prejemnik sprejme par (M,S) kot pristnega. Dokazano je, da lahko le imetnik tajnega ključa D oblikuje digitalni podpis S z dokumentom M, določitev tajne številke D iz javne številke E pa ni nič enostavnejša od faktoring modula N.

Poleg tega je mogoče strogo matematično dokazati, da bo rezultat preverjanja digitalnega podpisa S pozitiven le, če je bil pri izračunu S uporabljen tajni ključ D, ki ustreza javnemu ključu E. Zato se javni ključ E včasih imenuje »identifikator« podpisnika.

Slabosti algoritma za digitalno podpisovanje RSA.

1. Pri izračunu modula N, ključev E in D za sistem digitalnega podpisovanja RSA je potrebno preveriti veliko število dodatnih pogojev, kar je praktično težko izvedljivo. Neupoštevanje katerega koli od teh pogojev omogoča, da digitalni podpis ponaredi nekdo, ki takšno napako odkrije. Pri podpisovanju pomembnih dokumentov te možnosti niti teoretično ni mogoče dopustiti.
2. Za zagotovitev kriptografske trdnosti digitalnega podpisa RSA pred poskusi ponarejanja na ravni, na primer, ameriškega nacionalnega standarda za šifriranje informacij (algoritem DES), tj. 10 18 je treba pri izračunu N, D in E uporabiti cela števila vsaj 2.512 (ali približno 10.154), kar zahteva velike računske stroške, ki za 20...30 % presegajo računske stroške drugih algoritmov za digitalno podpisovanje, medtem ko ohranjanje enake ravni kriptografske moči.
3. Digitalni podpis RSA je ranljiv za tako imenovani multiplikativni napad. Z drugimi besedami, algoritem digitalnega podpisa RSA omogoča napadalcu, da brez poznavanja tajnega ključa D oblikuje podpise za tiste dokumente, katerih rezultat zgoščevanja je mogoče izračunati kot zmnožek rezultatov zgoščevanja že podpisanih dokumentov.

Primer. Predpostavimo, da lahko napadalec sestavi tri sporočila M 1, M 2, M 3, katerih zgoščene vrednosti

M 1 = h (M 1), m 2 = h (M 2), m 3 = h (M 3),

M 3 = m 1 * m 2 (mod N).

Predpostavimo tudi, da so bili pridobljeni zakoniti podpisi za dve sporočili M 1 in M ​​2

S 1 = m 1 D (mod N) S 2 = m 2 D (mod N).

Nato lahko napadalec zlahka izračuna podpis S 3 za dokument M 3, ne da bi sploh poznal tajni ključ D:

S 3 = S 1 * S 2 (mod N).

res,

S 1 * S 2 (mod N) = m 1 D * m 2 D (mod N) = (m 1 m 2) D (mod N) = m 3 D (mod N) = S 3.

Algoritem digitalnega podpisa, ki je bolj zanesljiv in priročen za implementacijo na osebnih računalnikih, je leta 1984 razvil Američan arabskega porekla Taher El Gamal. Leta 1991 je ameriški NIST pred odborom ameriškega kongresa utemeljil izbiro algoritma kot osnove za nacionalni standard.

Algoritem za digitalni podpis El Gamal (EGSA)

Ime EGSA izvira iz besed E_Gama_Signature Algorithm (algoritem za digitalni podpis El Gamal). Ideja EGSA temelji na dejstvu, da je za utemeljitev praktične nemožnosti ponarejanja digitalnega podpisa uporabiti bolj zapleten računski problem kot faktoriziranje velikega celega števila - problem diskretnega logaritma. Poleg tega se je El Gamalu uspelo izogniti očitni slabosti algoritma za digitalno podpisovanje RSA, povezani z možnostjo ponarejanja digitalnega podpisa pod nekaterimi sporočili brez določitve tajnega ključa.

Oglejmo si podrobneje algoritem digitalnega podpisa El Gamal. Če želite ustvariti par ključev (javni ključ - zasebni ključ), najprej izberite veliko praštevilo P in veliko celo število G, kjer je G< Р. Отправитель и получатель подписанного документа используют при вычислениях одинаковые большие целые числа Р (~10 308 или ~2 1024) и G (~10 154 или ~2 512), которые не являются секретными.

Pošiljatelj izbere naključno celo število X, 1< Х £ (Р-1) , и вычисляет

Y =G X mod R.

Številka Y je javni ključ, ki se uporablja za preverjanje podpisa pošiljatelja. Številka Y je javno posredovana vsem potencialnim prejemnikom dokumentov.

Številka X je tajni ključ pošiljatelja za podpisovanje dokumentov in mora ostati tajna.

Za podpis sporočila M ga pošiljatelj najprej z zgoščevalno funkcijo h(·) zgosti v celo število m:

M = h(M), 1< m < (Р-1) , и генерирует случайное целое число К, 1 < К < (Р-1) , такое, что К и (Р-1) являются взаимно простыми. Затем отправитель вычисляет целое число а: а = G K mod Р и, применяя расширенный алгоритм Евклида, вычисляет с помощью секретного ключа Х целое число b из уравнения m = Х * а + К * b (mod (Р-1)) .

Par številk (a,b) tvori digitalni podpis S:

S=(a,b) , navedeno pod dokumentom M.

Trojček števil (M, a, b) se posreduje prejemniku, par števil (X, K) pa ostane tajen.

Po prejemu podpisanega sporočila (M, a, b) mora prejemnik preveriti, ali podpis S = (a, b) ustreza sporočilu M. Za to prejemnik najprej izračuna število

M = h(M), tj. zgosti prejeto sporočilo M.

Prejemnik nato izračuna vrednost

A = Y a a b (mod P) in prepozna sporočilo M kot pristno le, če je A = G m (mod P).

Z drugimi besedami, prejemnik preveri veljavnost relacije

Y a a b (mod P) = G m (mod P) .

Strogo matematično je mogoče dokazati, da bo zadnja enakost izpolnjena, če in samo če je bil podpis S = (a, b) pod dokumentom M pridobljen s točno tistim tajnim ključem X, iz katerega je bil pridobljen javni ključ Y. Tako je mogoče zanesljivo preveriti, ali je bil pošiljatelj sporočila M lastnik tega posebnega skrivnega ključa X, ne da bi razkril sam ključ, in da je pošiljatelj podpisal ta določen dokument M.

Upoštevati je treba, da vsak podpis El Gamal zahteva novo vrednost K, to vrednost pa je treba izbrati naključno. Če napadalec kdaj razkrije vrednost K, ki jo ponovno uporabi pošiljatelj, bo lahko razkril pošiljateljev zasebni ključ X.

Primer. Izberimo: števila P = 11, G = 2 in skrivni ključ X = 8. Izračunamo vrednost javnega ključa:

Y = G X mod P = 2 8 mod 11 = 3 .

Recimo, da ima prvotno sporočilo M zgoščeno vrednost m = 5.

Da bi izračunali digitalni podpis za sporočilo M z zgoščeno vrednostjo m = 5, najprej izberemo naključno celo število K = 9. Prepričajmo se, da sta števili K in (P-1) relativno praštevili. Dejansko je GCD (9,10) = 1. Nato izračunamo elementa a in b podpisa:

A = G K mod P = 2 9 mod 11 = 6, element b je določen z uporabo razširjenega evklidskega algoritma: m = X * a + K * b (mod(P-1)).

Z m = 5, a = 6, X = 8, K = 9, P = 11 dobimo

5 = 8 * 6 + 9 * b (mod 10) ali 9 * b = -43 (mod 10) .

Rešitev: b = 3. Digitalni podpis je par: a = 6, b = 3. Pošiljatelj nato pošlje podpisano sporočilo. Po prejemu podpisanega sporočila in javnega ključa Y = 3 prejemnik izračuna zgoščeno vrednost za sporočilo M: m = 5 in nato izračuna dve števili:

Y a a b (mod P) = 3 6 * 6 3 (mod 11) = 10 (mod 11); G m (mod P) = 2 5 (mod 11) = 10 (mod 11).

Ker sta ti dve celi števili enaki, se sporočilo, ki ga prejme prejemnik, šteje za pristno.

Opozoriti je treba, da je shema El Gamal tipičen primer pristopa, ki omogoča, da se sporočilo M pošlje v jasni obliki skupaj s priloženim avtentifikatorjem (a,b). V takih primerih je postopek za ugotavljanje pristnosti prejetega sporočila preverjanje, ali se avtentifikator ujema s sporočilom.

Shema digitalnega podpisovanja El Gamal ima številne prednosti v primerjavi s shemo digitalnega podpisovanja RSA:

1. Pri določeni stopnji moči algoritma digitalnega podpisa se cela števila, ki sodelujejo pri izračunih, zapišejo 25 % krajše, kar zmanjša kompleksnost izračunov za skoraj polovico in omogoča znatno zmanjšanje količine porabljenega pomnilnika.
2. Pri izbiri modula P je dovolj, da preverimo, ali je to število praštevilo in ali ima število (P-1) velik prafaktor (tj. samo dva dokaj lahko preverljiva pogoja).
3. Postopek generiranja podpisa s pomočjo sheme El Gamal ne omogoča izračuna digitalnih podpisov za nova sporočila brez poznavanja tajnega ključa (kot pri RSA).

Vendar pa ima algoritem za digitalno podpisovanje El Gamal tudi nekaj slabosti v primerjavi s shemo podpisovanja RSA. Zlasti dolžina digitalnega podpisa je 1,5-krat večja, kar posledično poveča čas njegovega izračuna.

Algoritem digitalnega podpisa DSA

Algoritem digitalnega podpisa DSA (Algoritem digitalnega podpisa), ki ga je leta 1991 predlagal US NIST za uporabo v standardu digitalnega podpisa DSS (Digital Signature Standard). Algoritem DSA je razvoj algoritmov za digitalno podpisovanje El Gamala in K. Schnorrja.

Pošiljatelj in prejemnik elektronskega dokumenta pri računanju uporabljata velika cela števila: G in P sta praštevili, vsako L bitov (512 £ L £ 1024); q je praštevilo, dolgo 160 bitov (številski delitelj (P-1)). Številke G, P, q so odprte in si jih lahko delijo vsi uporabniki omrežja.

Pošiljatelj izbere naključno celo število X, 1< Х < q . Число Х является секретным ключом отправителя для формирования электронной цифровой подписи.

Pošiljatelj nato izračuna vrednost

Y = G X mod P.

Številka Y je javni ključ za preverjanje podpisa pošiljatelja in se posreduje vsem prejemnikom dokumentov.

Ta algoritem uporablja tudi enosmerno zgoščevalno funkcijo h(·). Standard DSS definira algoritem varnega zgoščevanja SHA (Secure Hash Algorithm).

Za podpis dokumenta M ga pošiljatelj zgosti v celoštevilsko zgoščeno vrednost m:

M = h(M), 1

Par številk (r,s) tvori digitalni podpis

S = (r,s) pod dokumentom M.

Tako je podpisano sporočilo trojček številk (M,r,s).

Prejemnik podpisanega sporočila (M,r,s) preveri izpolnjevanje pogojev

0 < r < q, 0 < s < q и отвергает подпись, если хотя бы одно из этих условий не выполнено. Затем получатель вычисляет значение w = (1/s) mod q , хэш-значение m = h(М) и числа u 1 = (m * w) mod q , u 2 = (r * w) mod q .

V = ((G u 1 * Y u 2) mod P) mod q in preveri pogoj v = r.

Če je pogoj v = r izpolnjen, potem prejemnik prepozna podpis S=(r,s) pod dokumentom M kot pristnega.

Strogo matematično je mogoče dokazati, da bo zadnja enakost izpolnjena, če in samo če je bil podpis S = (r, s) pod dokumentom M pridobljen s točno tistim tajnim ključem X, iz katerega je bil pridobljen javni ključ Y. Tako lahko zanesljivo preverite, ali ima pošiljatelj sporočila ta skrivni ključ X (brez razkritja vrednosti ključa X) in ali je pošiljatelj podpisal ta določen dokument M.

V primerjavi z algoritmom za digitalno podpisovanje El Gamal ima algoritem DSA naslednje glavne prednosti:

1. Pri kateri koli sprejemljivi stopnji odpornosti, tj. za kateri koli par števil G in P (od 512 do 1024 bitov) so števila q, X, r, s dolga 160 bitov, kar zmanjša dolžino podpisa na 320 bitov.
2. Večina operacij s števili K, r, s, X pri izračunu podpisa se izvede po modulu števila q dolžine 160 bitov, kar skrajša čas izračuna podpisa.
3. Pri preverjanju podpisa se večina operacij s števili u 1 , u 2 , v , w izvaja tudi po modulu števila q dolžine 160 bitov, kar zmanjša količino pomnilnika in čas izračuna.

Pomanjkljivost algoritma DSA je, da je treba pri podpisovanju in preverjanju podpisa izvesti kompleksne operacije deljenja po modulu q:

S = ((m + rX)/K) (mod q), w = (1/s) (mod q),

ki ne omogoča maksimalne zmogljivosti.

Upoštevati je treba, da je dejansko izvedbo algoritma DSA mogoče pospešiti z izvedbo predhodnih izračunov. Upoštevajte, da je vrednost r neodvisna od sporočila M in njegove zgoščene vrednosti m. Vnaprej lahko ustvarite niz naključnih vrednosti K in nato izračunate vrednosti r za vsako od teh vrednosti. Prav tako je mogoče vnaprej izračunati inverzne vrednosti K -1 za vsako od vrednosti K. Potem, ko prispe sporočilo M, se lahko vrednost s izračuna za dane vrednosti r in K -1 . Ti predizračuni znatno pospešijo algoritem DSA.

Domači standard digitalnega podpisa

Domači standard digitalnega podpisa je označen kot GOST R 34.10-94. Algoritem digitalnega podpisa, ki ga določa ta standard, je konceptualno blizu algoritmu DSA. Uporablja naslednje parametre:

P - veliko praštevilo z dolžino od 509 do 512 bitov ali od 1020 do 1024 bitov;
q je preprost faktor števila (p-1), ki ima dolžino 254...256 bitov;
a - poljubno število, manjše od (p-1), in tako, da je a q mod p = 1;
x je neko število, manjše od q;
y = a x mod p.

Poleg tega ta algoritem uporablja enosmerno zgoščevalno funkcijo H(x). Standard GOST R 34.11-94 definira zgoščevalno funkcijo, ki temelji na uporabi standardnega simetričnega algoritma GOST 28147-89.

Prvi trije parametri p, q, a so odprti in so lahko skupni vsem uporabnikom omrežja. Število x je skrivni ključ. Število y je javni ključ. Če želite podpisati sporočilo m in nato preveriti podpis, se izvedejo naslednji koraki.

1. Uporabnik A ustvari naključno število k in k
2. Uporabnik A izračuna vrednosti r = (a k mod p) mod p, s = (x * r + k (H(m))) mod p. Če je H(m) mod q = 0, potem je vrednost H(m) mod q enaka ena. Če je r=0, izberite drugo vrednost za k in začnite znova.
   Digitalni podpis je sestavljen iz dveh številk: r mod 2,256 in s mod 2,256. Uporabnik A pošlje te številke uporabniku B.
3. Uporabnik B preveri prejeti podpis z izračunom v = Н(m) q-2 mod q , z 1 = (s * v) mod q , z 2 = ((q-r) * v) mod q , u = ((in z 1 * y z 2) mod p) mod p . Če je u = r, je podpis pravilen.

Razlika med tem algoritmom in algoritmom DSA je, da v DSA

S = (k -1 (x * r + (H(m)))) mod q,

kar vodi do drugačne enačbe preverjanja.

Upoštevati je treba tudi, da ima v domačem standardu digitalnega podpisa parameter q dolžino 256 bitov. Zahodni kriptografi so precej zadovoljni s q, ki je dolg približno 160 bitov. Razlika v vrednostih parametra q je odraz želje razvijalcev domačega standarda, da pridobijo varnejši podpis.

Ta standard je stopil v veljavo v začetku leta 1995.

Literatura

1. Romanets Yu.V., Timofeev P.A., Shangin V.F. Varovanje informacij v računalniških sistemih in omrežjih. Ed. V.F. Šangina. - 2. izd., revidirano. in dodatno - M .: Radio in komunikacije, 2001. - 376 str .: ilustr.
2. Koneev I.R., Belyaev A.V. Informacijska varnost podjetja. - Sankt Peterburg: BHV-Petersburg, 2003.