Manau, daugelis žino, kad nuo 2007 m. JAV Nacionalinis standartų ir technologijų institutas (NIST) rengia konkursą sukurti maišos algoritmą, kuris pakeistų SHA-1, ir SHA-2 algoritmų šeimą. Tačiau ši tema dėl tam tikrų priežasčių svetainėje nekreipiama dėmesio. Tai iš tikrųjų atvedė mane pas jus. Atkreipiu jūsų dėmesį į keletą straipsnių apie maišos algoritmus. Šiame cikle kartu išnagrinėsime maišos funkcijų pagrindus, apsvarstysime garsiausius maišos algoritmus, pasinersime į SHA-3 konkurso atmosferą ir apsvarstysime algoritmus, pretenduojančius jį laimėti, būtinai juos išbandysime. Taip pat, jei įmanoma, bus atsižvelgta į rusiškus maišos standartus.
Apie save
Informacijos saugumo katedros studentas.Apie maišą
Šiuo metu beveik nė viena kriptografijos programa nėra baigta nenaudojant maišos.Maišos funkcijos yra funkcijos, skirtos "suspausti" savavališką pranešimą arba duomenų rinkinį, paprastai užrašytą dvejetaine abėcėle, į tam tikrą fiksuoto ilgio bitų derinį, vadinamą konvoliucija. Maišos funkcijos turi daugybę pritaikymų atliekant statistinius eksperimentus, testuojant loginius įrenginius, kuriant algoritmus, skirtus greitai paieškai ir duomenų bazių įrašų vientisumui tikrinti. Pagrindinis reikalavimas maišos funkcijoms yra jų reikšmių pasiskirstymo vienodumas atsitiktinai pasirenkant argumentų reikšmes.
Kriptografinė maišos funkcija yra bet kokia maišos funkcija, kuri yra kriptografiškai saugi, tai yra, ji atitinka daugybę kriptografinėms programoms būdingų reikalavimų. Kriptografijoje maišos funkcijos naudojamos šioms problemoms išspręsti:
- kurti duomenų vientisumo kontrolės sistemas jų perdavimo ar saugojimo metu,
- duomenų šaltinio autentifikavimas.
Maišos funkcija yra bet kokia funkcija h:X -> Y, lengvai apskaičiuojamas ir skirtas bet kokiam pranešimui M prasmė h(M) = H (konvoliucija) turi fiksuotą bitų ilgį. X- visų pranešimų rinkinys, Y- fiksuoto ilgio dvejetainių vektorių rinkinys.
Paprastai maišos funkcijos kuriamos remiantis vadinamosiomis vieno žingsnio susitraukimo funkcijomis y \u003d f (x 1, x 2) du kintamieji, kur x 1, x2 ir y- dvejetainiai ilgio vektoriai m, n ir n atitinkamai ir n yra konvoliucijos ilgis ir m- pranešimų bloko ilgis.
Norėdami gauti vertę h(M) pranešimas pirmiausia suskaidomas į ilgio blokus m(tuo pačiu metu, jei pranešimo ilgis nėra kartotinis m tada paskutinis blokas kokiu nors specialiu būdu papildomas iki pilno), o po to prie gautų blokų M 1 , M 2 , .., M N taikykite šią nuoseklią konvoliucijos apskaičiavimo procedūrą:
H o \u003d v,
H i = f(M i , H i-1), i = 1,..., N,
h(M) = H N
Čia v- tam tikra konstanta, ji dažnai vadinama inicijavimo vektoriumi. Ji išlipa
dėl įvairių priežasčių ir gali būti slapta konstanta arba atsitiktinių duomenų rinkinys (pavyzdžiui, datos ir laiko pasirinkimas).
Taikant šį metodą maišos funkcijos savybes visiškai lemia vieno žingsnio susitraukimo funkcijos savybės.
Yra du svarbūs kriptografinių maišos funkcijų tipai – su raktais ir be raktų. Pagrindinės maišos funkcijos vadinamos pranešimų autentifikavimo kodais. Jie leidžia be papildomų priemonių garantuoti tiek duomenų šaltinio teisingumą, tiek duomenų vientisumą sistemose su abipusiai pasitikinčiais vartotojais.
Beraktės maišos funkcijos vadinamos klaidų aptikimo kodais. Jie leidžia papildomomis priemonėmis (pavyzdžiui, šifravimu) užtikrinti duomenų vientisumą. Šios maišos funkcijos gali būti naudojamos sistemose su pasitikinčiais ir nepasitikinčiais vartotojais.
Apie statistines savybes ir reikalavimus
Kaip sakiau, pagrindinis reikalavimas maišos funkcijoms yra vienodas jų reikšmių paskirstymas atsitiktinai pasirenkant argumentų reikšmes. Kriptografinėms maišos funkcijoms taip pat svarbu, kad menkiausiai pasikeitus argumentui, funkcijos reikšmė labai pasikeistų. Tai vadinama lavinos efektu.
Į pagrindines funkcijas maiša turi šiuos reikalavimus:
- gamybos neįmanoma,
- modifikavimo neįmanoma.
Pirmasis reikalavimas reiškia, kad labai sunku suderinti pranešimą su teisinga lankstymo verte. Antrasis yra didelis sudėtingumas suderinti tam tikrą pranešimą su žinoma išlenkimo verte kitą pranešimą su teisinga išlenkimo verte.
Berakčių funkcijų reikalavimai yra šie:
- vienakryptis,
- atsparumas susidūrimams,
- pasipriešinimas ieškant antrojo prototipo.
Vienakryptis suprantamas kaip didelis sudėtingumas ieškant pranešimo pagal tam tikrą konvoliucijos reikšmę. Reikėtų pažymėti, kad ant Šis momentas nenaudojamos maišos funkcijos su įrodyta vienpuse.
Atsparumas susidūrimui suprantamas kaip sunkumas rasti pranešimų porą su tomis pačiomis lankstymo reikšmėmis. Paprastai kriptovaliutų suradimas būdo, kaip sukurti susidūrimus, yra pirmasis signalas apie algoritmo pasenimą ir būtinybę jį greitai pakeisti.
Pasipriešinimas ieškant antrojo pirminio vaizdo suprantamas kaip sunkumas rasti antrą pranešimą su tokia pačia lenkimo verte duotam pranešimui su žinoma lenkimo verte.
Tai buvo teorinė dalis, kuri mums pravers ateityje...
Apie populiarius maišos algoritmus
Algoritmai CRC16/32- kontrolinė suma (ne kriptografinis konvertavimas).
Algoritmai MD2/4/5/6. Juos sukūrė Ronas Rivestas, vienas iš RSA algoritmo autorių.
MD5 algoritmas kažkada buvo labai populiarus, tačiau pirmosios prielaidos įsilaužti atsirado 9 dešimtmečio pabaigoje, o dabar jo populiarumas sparčiai mažėja.
MD6 algoritmas yra labai įdomus konstruktyviu požiūriu. Jis buvo nominuotas SHA-3 konkursui, bet, deja, autoriams nepavyko jo suvesti iki standarto, o šio algoritmo nėra į antrąjį turą patekusių kandidatų sąraše.
Liniuotės algoritmai SHAŠiandien plačiai naudojami algoritmai. Vyksta aktyvus perėjimas nuo SHA-1 prie SHA-2 versijos standartų. SHA-2 yra bendras SHA224, SHA256, SHA384 ir SHA512 algoritmų pavadinimas. SHA224 ir SHA384 iš esmės yra atitinkamai SHA256 ir SHA512 analogai, tik apskaičiavus konvoliuciją dalis joje esančios informacijos atmetama. Jie turėtų būti naudojami tik siekiant užtikrinti suderinamumą su senesnio modelio įranga.
Rusijos standartas - GOST 34.11-94.
Kitame straipsnyje
MD algoritmų apžvalga (MD4, MD5, MD6).
Literatūra
A. P. Alferovas, Kriptografijos pagrindai.
Bruce Schneier, Taikomoji kriptografija.
Maiša yra specialus duomenų adresavimo metodas (tam tikras tarpų algoritmas) pagal jų unikalius raktus ( Raktas ) kad greitai rastumėte reikiamą informaciją.
Pagrindinės sąvokos
Hash lentelė
Maišos lentelė yra įprastas masyvas su specialiu adresu, kurį suteikia kokia nors funkcija (hash funkcija).
maišos funkcija
Funkcija, kuri konvertuoja duomenų elemento raktą į tam tikrą lentelės indeksą ( maišos lentelė), vadinamas maišos funkcija arba maišos funkcija :
i = h (Raktas );
kur Raktas- konvertuojamas raktas, i- gautas lentelės indeksas, t.y. raktas rodomas, pavyzdžiui, sveikųjų skaičių ( maišos adresai ), kurie vėliau naudojami norint pasiekti duomenis.
Maišos keitimas šiuo būdu yra būdas, kai naudojamas rakto vertės nustatymas jo vietai specialioje lentelėje.
Tačiau sklaidos funkcija gali kelis unikalios rakto reikšmės suteikia tą pačią pozicijos vertę i maišos lentelėje. Iškviečiama situacija, kai du ar daugiau raktų gauna tą patį indeksą (maišos adresą). susidūrimas (susidūrimas) maišos sistemoje.Todėl maišos schema turi apimti konfliktų sprendimo algoritmas , apibrėžiantis veiksmų tvarką, jei pozicija i=h(Raktas) jau užimtas įrašas su kitu raktu.
Yra daug maišos schemų, kurios skiriasi naudojama maišos funkcija. h(Raktas) ir konfliktų sprendimo algoritmus.
Dažniausias maišos funkcijos nustatymo metodas yra: padalijimo metodas.
Pradiniai duomenys yra: - tam tikras sveikasis raktas Raktas ir stalo dydis m. Šios funkcijos rezultatas yra likusi dalis padalijus šį raktą iš lentelės dydžio. Bendra tokios funkcijos forma C/C++ programavimo kalba:
tarpt h (tarpt Raktas , tarpt m ) {
Dėl m= 10 maišos funkcija grąžina mažiausiai reikšmingą rakto skaitmenį.
Jei m = 100, maišos funkcija grąžina du mažiausiai reikšmingus rakto skaitmenis.
Nagrinėjamuose pavyzdžiuose maišos funkcija i=h(Raktas). Raktas. Toliau reikia naudoti tam tikrą maišos schemą (algoritmą).
Maišos schemos
Daugumoje problemų du ar daugiau raktų maišos yra vienodai, tačiau jie negali užimti to paties maišos lentelės langelio. Yra du galimi variantai: arba suraskite kitą naujojo rakto vietą, arba sukurkite atskirą kiekvieno maišos lentelės indekso sąrašą, kuriame būtų patalpinti visi šiam indeksui priskirti raktai.
Šie variantai yra dvi klasikinės maišos schemos:
maiša naudojant atvirą adresą naudojant tiesinį zondavimą - linijinis zondas atviras kreipiantis.
grandininė maiša (su sąrašais) arba vadinamoji daugiamatė maiša – grandininis su atskirti sąrašus;
Atviras adresavimo metodas su tiesiniu zondavimu . Iš pradžių visi maišos lentelės, kuri yra įprastas vienmatis masyvas, langeliai yra pažymėti kaip neužimti. Todėl pridedant naują raktą yra patikrinama, ar duotas langelis yra užimtas. Jei langelis užimtas, algoritmas ieško apskritime, kol lieka tuščia vieta („atviras adresas“).
Tie. elementai su vienarūšiais raktais dedami šalia gauto indekso.
Ateityje atlikdami paiešką pirmiausia suraskite poziciją pagal raktą i lentelėje, o jei raktas nesutampa, tada tolesnė paieška atliekama pagal konflikto sprendimo algoritmą, pradedant nuo padėties i. .
Grandinės metodas yra dominuojanti strategija . Tokiu atveju i gautas iš pasirinktos maišos funkcijos h(Raktas)=i, traktuojamas kaip indeksas į sąrašų maišos lentelę, t.y. raktas pirmas Raktas kitas įrašas susietas su pozicija i = h(Raktas) lenteles. Jei padėtis laisva, tada elementas su raktu dedamas į jį. Raktas, jei jis užimtas, tada parengiamas konfliktų sprendimo algoritmas, dėl kurio tokie raktai dedami į sąrašą, pradedant nuo i-ta maišos lentelės ląstelė. Pavyzdžiui
Dėl to turime susietų sąrašų arba medžių masyvo lentelę.
Maišos lentelės užpildymo (skaitymo) procesas yra paprastas, tačiau norint pasiekti elementus reikia atlikti šias operacijas:
Indekso apskaičiavimas i;
Ieškokite atitinkamoje grandinėje.
Norėdami pagerinti paiešką pridedant naują elementą, galite naudoti įterpimo algoritmą ne sąrašo pabaigoje, o su tvarka, t.y. pridėti elementą prie Tinkama vieta.
Tiesioginio adresavimo metodo su tiesiniu zondavimu įgyvendinimo pavyzdys . Pradiniai duomenys yra 7 įrašai (paprastumo dėlei informacinę dalį sudaro tik sveikieji duomenys), deklaruoto struktūrinio tipo:
įvesties raktas; // Raktas
intinfo; // Informacija
(59,1), (70,3), (96,5), (81,7), (13,8), (41,2), (79,9); maišos lentelės dydis m=10.
maišos funkcija i=h(duomenis) =duomenis.Raktas% dešimt; tie. likutis padalijus iš 10 - i.
Remdamiesi pradiniais duomenimis, nuosekliai pildome maišos lentelę.
Sumaišius pirmuosius penkis raktus, gaunami skirtingi indeksai (maišos adresai):
Pirmasis susidūrimas įvyksta tarp klavišų 81 ir 41 - vieta su indeksu 1 yra užimta. Todėl mes žiūrime per maišos lentelę, kad surastume artimiausią laisvą vietą, šiuo atveju ji yra i = 2.
Kitas klavišas 79 taip pat generuoja susidūrimą: 9 padėtis jau užimta. Algoritmo efektyvumas smarkiai krenta, nes laisvos vietos radimui prireikė 6 bandymų (palyginimų), indeksas pasirodė nemokamas i= 4.
Bendras šio metodo pavyzdžių skaičius yra nuo 1 iki n-1 mėginių vienam elementui, kur n yra maišos lentelės dydis.
Grandininio metodo įgyvendinimas ankstesniam pavyzdžiui. Mes deklaruojame sąrašo elemento struktūrinį tipą (vienakryptis):
įvesties raktas; // Raktas
intinfo; // Informacija
zap*Kitas; // Nukreipkite į kitas elementas sąraše
Remdamiesi pradiniais duomenimis, maišos lentelę nuosekliai užpildome pridedant naujas elementas iki sąrašo pabaigos, jei vieta jau užimta.
Sujungus pirmuosius penkis raktus, kaip ir ankstesniu atveju, gaunami skirtingi indeksai (maišos adresai): 9, 0, 6, 1 ir 3.
Kai įvyksta susidūrimas, naujas elementas įtraukiamas į sąrašo pabaigą. Todėl elementas su raktu 41 dedamas po elemento su raktu 81, o elementas su raktu 79 dedamas po elemento su raktu 59.
Individualios užduotys
1. Dvejetainiai medžiai. Naudodamiesi atsitiktinių skaičių generatoriaus programa, gaukite 10 reikšmių nuo 1 iki 99 ir sukurkite dvejetainį medį.
Padarykite aplinkkelį:
1.a Perėjimas iš kairės į dešinę: Kairė-Šaknis-Dešinė: pirmiausia aplankykite kairįjį pomedį, tada šaknį ir galiausiai dešinįjį pomedį.
(Arba atvirkščiai, iš dešinės į kairę: dešinė-šaknis-kairė)
1.b Perėjimas iš viršaus į apačią: Šaknis-Kairė-Dešinė: aplankykite šaknį iki pomedžių.
1. Perėjimas iš apačios į viršų: kairė-dešinė-šaknis: aplankykite šaknį po pomedžių
Įvairiose pramonės šakose informacines technologijas rasti jų naudojimo maišos funkcijas. Jie skirti, viena vertus, labai supaprastinti keitimąsi duomenimis tarp vartotojų ir tam tikriems tikslams naudojamų failų apdorojimą, kita vertus, optimizuoti algoritmus, užtikrinančius prieigos prie atitinkamų išteklių kontrolę. Maišos funkcija yra viena iš pagrindiniai instrumentai užtikrinant duomenų apsaugą slaptažodžiu, taip pat organizuojant keitimąsi dokumentais, pasirašytais naudojant EDS. Yra daug standartų, pagal kuriuos failai gali būti talpykloje. Daugelį jų sukūrė Rusijos specialistai. Kokie yra maišos funkcijų tipai? Kokie yra pagrindiniai jų praktinio taikymo mechanizmai?
Kas tai yra?
Pirmiausia panagrinėkime maišos funkcijos sampratą. Šis terminas paprastai suprantamas kaip algoritmas, skirtas tam tikram informacijos kiekiui konvertuoti į trumpesnę simbolių seką naudojant matematinius metodus. Praktinę maišos funkcijos svarbą galima atsekti įvairiose srityse. Taigi, jie gali būti naudojami tikrinant failų ir programų vientisumą. Taip pat šifravimo algoritmuose naudojamos kriptografinės maišos funkcijos.
Charakteristikos
Panagrinėkime pagrindines tiriamų algoritmų charakteristikas. Tarp jų:
- vidinių algoritmų, skirtų konvertuoti pradinio ilgio duomenis į trumpesnę simbolių seką, buvimas;
- atvirumas kriptografiniam patikrinimui;
- algoritmų, leidžiančių saugiai užšifruoti pradinius duomenis, buvimas;
- prisitaikymas prie iššifravimo naudojant mažą skaičiavimo galia.
Kitos svarbios maišos funkcijos savybės:
- galimybė apdoroti savavališko ilgio pradinių duomenų matricas;
- generuoti fiksuoto ilgio maišos blokus;
- tolygiai paskirstyti funkcijų reikšmes išvestyje.
Nagrinėjami algoritmai taip pat prisiima jautrumą įvesties duomenims 1 bito lygiu. Tai yra, net jei, santykinai kalbant, bent 1 raidė pasikeičia šaltinio dokumente, maišos funkcija atrodys kitaip.
Reikalavimai maišos funkcijoms
Yra keletas reikalavimų maišos funkcijoms, skirtoms praktiniam naudojimui konkrečioje srityje. Pirma, atitinkamas algoritmas turi būti jautrus maišos dokumentų vidinės struktūros pokyčiams. Tai yra, maišos funkcija turėtų būti atpažinta, kai kalbama apie tekstinis failas, pastraipos permutacija, brūkšnelis. Viena vertus, dokumento turinys nesikeičia, kita vertus, koreguojama jo struktūra, o maišos metu šis procesas turi būti atpažįstamas. Antra, nagrinėjamas algoritmas turi transformuoti duomenis taip, kad atvirkštinė operacija (maišos pavertimas pirminiu dokumentu) praktiškai būtų neįmanomas. Trečia, maišos funkcija turėtų apimti tokius algoritmus, kurie praktiškai pašalina galimybę sudaryti tą pačią simbolių seką maišos pavidalu, kitaip tariant, vadinamųjų susidūrimų atsiradimą. Jų esmę apsvarstysime šiek tiek vėliau.
Nurodytus reikalavimus, kuriuos turi atitikti maišos funkcijos algoritmas, galima pasiekti daugiausia naudojant sudėtingus matematinius metodus.
Struktūra
Panagrinėkime, kokia gali būti nagrinėjamų funkcijų struktūra. Kaip minėjome aukščiau, vienas iš pagrindinių nagrinėjamiems algoritmams keliamų reikalavimų yra vienakrypčio šifravimo užtikrinimas. Asmuo, turintis tik maišą, praktiškai neturėtų turėti galimybės gauti originalaus dokumento pagal jį.
Kokioje struktūroje gali būti pavaizduota tokiems tikslams naudojama maišos funkcija? Jo sudarymo pavyzdys gali būti toks: H (hash, tai yra maiša) = f (T (tekstas), H1), kur H1 yra teksto apdorojimo algoritmas T. Ši funkcija maišos T taip, kad be žinios apie H1 bus praktiškai neįmanoma atidaryti kaip visaverčio failo.
Maišos funkcijų naudojimas praktikoje: failų atsisiuntimas
Dabar išsamiau išnagrinėkime maišos funkcijų naudojimo praktikoje galimybes. Rašant scenarijus failams atsisiųsti iš interneto serverių galima naudoti tinkamus algoritmus.
Daugeliu atvejų kiekvienam failui nustatoma tam tikra kontrolinė suma – tai yra maiša. Jis turi būti toks pat objekto, esančio serveryje ir atsisiųstas į vartotojo kompiuterį, atveju. Jei taip nėra, failas gali neatsidaryti arba prasidėti netinkamai.
Maišos funkcija ir skaitmeninis parašas
Maišos funkcijų naudojimas yra įprastas organizuojant apsikeitimą dokumentais, kuriuose yra skaitmeninis parašas. Tokiu atveju pasirašytas failas sumaišomas, kad jo gavėjas galėtų patikrinti, ar jis tikras. Nors maišos funkcija formaliai nėra įtraukta į struktūrą elektroninis raktas, jį galima pataisyti aparatinės įrangos, su kuria pasirašomi dokumentai, „flash“ atmintyje, pvz., „eToken“.
Elektroninis parašas yra failo šifravimas naudojant viešuosius ir privačius raktus. Tai reiškia, kad pranešimas, užšifruotas privačiu raktu, pridedamas prie šaltinio failo, o skaitmeninis parašas patikrinamas naudojant viešasis raktas. Jei abiejų dokumentų maišos funkcija sutampa, gavėjo failas atpažįstamas kaip autentiškas, o siuntėjo parašas – teisingas.
Maišos naudojimas, kaip minėjome aukščiau, nėra tiesiogiai EDS komponentas, tačiau jis leidžia labai efektyviai optimizuoti naudojimo algoritmus. Elektroninis parašas. Taigi, užšifruoti galima tik maišą, o ne patį dokumentą. Dėl to žymiai padidėja failų apdorojimo greitis, tuo pačiu atsiranda galimybė numatyti efektyvesnius EDS apsaugos mechanizmus, nes skaičiavimo operacijose šiuo atveju dėmesys bus skiriamas ne pradinių duomenų apdorojimui, o kriptografinis parašo stiprumas. Maišos funkcija taip pat leidžia pasirašyti įvairių tipų duomenis, ne tik tekstą.
Slaptažodžio tikrintuvas
Kita galima maišos taikymo sritis yra slaptažodžio tikrinimo algoritmų, skirtų atskirti prieigą prie tam tikrų failų išteklių, organizavimas. Kaip tam tikro tipo maišos funkcijos gali būti naudojamos sprendžiant tokias problemas? Labai paprasta.
Faktas yra tas, kad daugumoje serverių, prie kurių priėjimas yra diferencijuojamas, slaptažodžiai saugomi maišos verčių pavidalu. Tai gana logiška – jei slaptažodžiai būtų pateikti originalia teksto forma, prie jų priėję programišiai galėtų nesunkiai perskaityti slaptus duomenis. Savo ruožtu, remiantis maiša, nėra lengva apskaičiuoti slaptažodį.
Kaip tikrinama vartotojo prieiga, kai naudojami svarstomi algoritmai? Vartotojo įvestas slaptažodis tikrinamas pagal tai, kas nustatyta maišos funkcijoje, kuri saugoma serveryje. Jei teksto blokų reikšmės sutampa, vartotojas gauna reikiamą prieigą prie išteklių.
Paprasčiausia maišos funkcija gali būti naudojama kaip slaptažodžio tikrinimo priemonė. Tačiau praktikoje IT specialistai dažniausiai naudoja sudėtingus kelių pakopų kriptografinius algoritmus. Paprastai jie papildomi naudojant saugaus kanalo duomenų perdavimo standartus, kad įsilaužėliai negalėtų aptikti ar išsiaiškinti slaptažodžio, perduodamo iš vartotojo kompiuterio į serverius, kol jis nėra patikrintas pagal maišos teksto blokus.
Maišos funkcijų susidūrimai
Maišos funkcijų teorijoje numatytas toks reiškinys kaip susidūrimas. Kokia jo esmė? Maišos susidūrimas yra situacija, kai du skirtingi failai turi tą patį maišos kodą. Tai įmanoma, jei tikslinės simbolių sekos ilgis yra mažas. Tokiu atveju maišos atitikties tikimybė bus didesnė.
Siekiant išvengti susidūrimo, visų pirma rekomenduojama naudoti dvigubą algoritmą, vadinamą „maišos funkcijos maiša“. Tai apima atvirojo ir uždarojo kodo formavimą. Daugelis programuotojų, spręsdami kritines problemas, rekomenduoja nenaudoti maišos funkcijų tais atvejais, kai tai nėra būtina, ir visada išbandyti atitinkamus algoritmus, kad būtų geriausias suderinamumas su tam tikrais raktais.
Išvaizdos istorija
Maišos funkcijų teorijos pradininkais galima laikyti tyrinėtojus Carteris, Wegmanas, Simonsonas, Bierbroueris. Pirmosiose versijose atitinkami algoritmai buvo naudojami kaip įrankiai unikaliems savavališko ilgio simbolių sekų vaizdams generuoti, siekiant vėliau juos identifikuoti ir patikrinti autentiškumą. Savo ruožtu maiša pagal nurodytus kriterijus turėtų būti 30–512 bitų ilgio. Kaip ypatinga naudingą turtą tinkamas funkcijas, buvo svarstomas jo tinkamumas naudoti kaip išteklius greitai ieškant failų ar juos rūšiuojant.
Populiarūs maišos standartai
Dabar panagrinėkime, kokiuose populiariuose standartuose gali būti pavaizduotos maišos funkcijos. Vienas iš jų yra CRC. Šis algoritmas yra ciklinis kodas, dar vadinama kontroline suma. Šis standartas pasižymi paprastumu ir tuo pačiu universalumu – per jį galite maišyti plačiausią duomenų spektrą. CRC yra vienas iš labiausiai paplitusių nekriptografinių algoritmų.
Savo ruožtu MD4 ir MD5 standartai plačiai naudojami šifravimui. Kitas populiarus kriptografinis algoritmas yra SHA-1. Visų pirma, jam būdingas 160 bitų maišos dydis, kuris yra didesnis nei MD5 – šis standartas palaiko 128 bitus. Yra Rusijos standartai, reglamentuojantys maišos funkcijų naudojimą - GOST R 34.11-94, taip pat jį pakeitęs GOST R 34.11-2012. Galima pastebėti, kad Rusijos Federacijoje priimtų algoritmų pateikta maišos reikšmė yra 256 bitai.
Aptariamus standartus galima klasifikuoti įvairiais būdais. Pavyzdžiui, yra tokių, kurie naudoja blokinius ir specializuotus algoritmus. Skaičiavimų, pagrįstų pirmojo tipo standartais, paprastumą dažnai lydi mažas jų greitis. Todėl kaip alternatyvą blokų algoritmams galima naudoti tuos, kurie apima mažesnį kiekį būtinų skaičiavimo operacijų. Įprasta remtis didelės spartos standartais, ypač pirmiau minėtais MD4, MD5 ir SHA. Išsamiau apsvarstykime specialių maišos algoritmų specifiką SHA pavyzdyje.
SHA algoritmo ypatybės
Maišos funkcijų naudojimas remiantis SHA standartu dažniausiai atliekamas įrankių kūrimo srityje Elektroninis parašas DSA dokumentai. Kaip minėjome aukščiau, SHA algoritmas palaiko 160 bitų maišą (suteikia vadinamąjį simbolių sekos „sutraukimą“). Iš pradžių svarstomas standartas padalija duomenų masyvą į 512 bitų blokus. Jei reikia, paskutinio bloko ilgis nesiekia nurodyto skaičiaus, failo struktūra užpildoma 1 ir reikiamu nulių skaičiumi. Taip pat atitinkamo bloko pabaigoje įvedamas kodas, fiksuojantis pranešimo ilgį. Nagrinėjamas algoritmas apima 80 loginių funkcijų, per kurias apdorojami 3 žodžiai, pavaizduoti 32 bitais. SHA standartas taip pat numato naudoti 4 konstantas.
Maišos algoritmų palyginimas
Panagrinėkime, kaip koreliuoja maišos funkcijų, susijusių su skirtingais standartais, savybės, naudodamiesi Rusijos standarto GOST R 34.11-94 ir Amerikos SHA charakteristikų palyginimo pavyzdžiu, kurį aptarėme aukščiau. Visų pirma, reikia pažymėti, kad Rusijos Federacijoje sukurtas algoritmas apima 4 šifravimo operacijų įgyvendinimą per 1 ciklą. Tai atitinka 128 raundus. Savo ruožtu per 1 raundą naudojant SHA tikimasi suskaičiuoti apie 20 komandų, o iš viso – 80. Taigi naudojant SHA per 1 ciklą galima apdoroti 512 bitų pradinių duomenų. Nors Rusijos standartas gali atlikti operacijas 256 bitų duomenų cikle.
Naujausio rusiško algoritmo specifika
Aukščiau pažymėjome, kad GOST R 34.11-94 standartas buvo pakeistas naujesniu - GOST R 34.11-2012 Stribog. Panagrinėkime jo specifiką išsamiau.
Per šis standartas gali būti įgyvendintos, kaip ir aukščiau aptartų algoritmų atveju, kriptografinės maišos funkcijos. Galima pastebėti, kad naujausias Rusijos standartas palaiko 512 bitų įvesties duomenų bloką. Pagrindiniai GOST R 34.11-2012 pranašumai:
- aukšto lygio apsauga nuo šifrų įtrūkimų;
- patikimumas, pagrįstas patikrintų dizainų naudojimu;
- greitas maišos funkcijos apskaičiavimas, nebuvimas algoritme transformacijų, kurios apsunkina funkcijos konstravimą ir sulėtina skaičiavimą.
Pastebėti naujojo Rusijos standarto pranašumai kriptografinis šifravimas leidžia jį naudoti organizuojant darbo eigą, atitinkančią griežčiausius kriterijus, numatytus norminių teisės aktų nuostatose.
Kriptografinių maišos funkcijų specifika
Leiskite mums išsamiau apsvarstyti, kaip mūsų tiriamų algoritmų tipai gali būti naudojami kriptografijos srityje. Pagrindinis reikalavimas atitinkamoms funkcijoms yra atsparumas susidūrimams, kurį minėjome aukščiau. Tai yra, pasikartojančios maišos reikšmės neturėtų būti generuojamos, jei šios reikšmės jau yra gretimo algoritmo struktūroje. Kitus aukščiau nurodytus kriterijus taip pat turi atitikti kriptografinės funkcijos. Akivaizdu, kad visada yra tam tikra teorinė galimybė pasveikti šaltinio failą pagrįsta maiša, ypač jei yra galingas skaičiavimo įrankis. Tačiau šis scenarijus turėtų būti sumažintas dėl stiprių šifravimo algoritmų. Taigi, bus labai sunku apskaičiuoti maišos funkciją, jei jos skaičiavimo stiprumas atitinka formulę 2^(n/2).
Kitas svarbus kriptografinio algoritmo kriterijus yra maišos pasikeitimas tuo atveju, jei pradinis duomenų masyvas yra pataisytas. Aukščiau pažymėjome, kad šifravimo standartai turėtų turėti 1 bito jautrumą. Taigi ši savybė yra pagrindinis veiksnys užtikrinant patikimą prieigos prie failų apsaugą slaptažodžiu.
Iteracinės schemos
Dabar panagrinėkime, kaip galima sukurti kriptografinius maišos algoritmus. Tarp dažniausiai pasitaikančių šios problemos sprendimo schemų yra iteracinio nuoseklaus modelio naudojimas. Jis pagrįstas vadinamosios susitraukimo funkcijos naudojimu, kai įvesties bitų skaičius yra žymiai didesnis nei fiksuotų išvestyje.
Žinoma, suspaudimo funkcija turi atitikti būtinus kriptografinio stiprumo kriterijus. Interaktyvioje schemoje pirmoji įvesties duomenų srauto apdorojimo operacija yra padalinta į blokus, kurių dydis skaičiuojamas bitais. Atitinkamas algoritmas taip pat naudoja laikinus tam tikro bitų skaičiaus kintamuosius. Gerai žinomas skaičius naudojamas kaip pirmoji reikšmė, o paskesni duomenų blokai išvestyje derinami su atitinkamos funkcijos reikšme. Maišos reikšmė tampa paskutinės iteracijos bitų išvestimi, kai atsižvelgiama į visą įvesties srautą, įskaitant pirmąją reikšmę. Suteikiamas vadinamasis maišos „lavinos efektas“.
Pagrindinis sunkumas, apibūdinantis maišą, įgyvendintą kaip pasikartojančią schemą, yra tas, kad maišos funkcijas kartais sunku sukurti, jei įvesties srautas nėra identiškas bloko, į kurį padalintas pradinis duomenų masyvas, dydžiui. Tačiau šiuo atveju maišos standarte gali būti įrašyti algoritmai, kurių pagalba pradinis srautas gali būti vienaip ar kitaip išplėstas.
Kai kuriais atvejais duomenų apdorojimo procese iteracinės schemos rėmuose gali būti naudojami vadinamieji kelių praėjimų algoritmai. Jie siūlo formuotis dar intensyvesniam „lavinos efektui“. Toks scenarijus apima pasikartojančių duomenų masyvų formavimą, o tik antroje vietoje yra išplėtimas.
Blokavimo algoritmas
Suspaudimo funkcija taip pat gali būti pagrįsta bloko algoritmu, pagal kurį atliekamas šifravimas. Taigi, norėdami padidinti saugumo lygį, kaip raktą galite naudoti duomenų blokus, kuriems dabartinės iteracijos metu taikoma maiša, o kaip įvestį operacijų rezultatą, gautą vykdant glaudinimo funkciją prieš tai. . Dėl to paskutinė iteracija pateiks algoritmo išvestį. Maišos saugumas bus susijęs su naudojamo algoritmo patikimumu.
Tačiau, kaip minėjome aukščiau, atsižvelgiant į Skirtingos rūšys maišos funkcijos, blokų algoritmus dažnai lydi poreikis naudoti didelę skaičiavimo galią. Jei jų nėra, failų apdorojimo sparta gali būti nepakankama, kad būtų išspręstos praktinės problemos, susijusios su maišos funkcijų naudojimu. Tuo pačiu metu reikiamą kriptografinį stiprumą taip pat galima pasiekti atlikus nedidelį skaičių operacijų su šaltinio duomenų srautais, visų pirma, mūsų apsvarstyti algoritmai - MD5, SHA ir Rusijos kriptografinio šifravimo standartai - yra pritaikyti tokioms problemoms spręsti.
Kas yra maiša? Maišos funkcija yra matematinė informacijos transformacija į trumpą tam tikro ilgio eilutę.
Kam to reikia? Maišos funkcijos analizė dažnai naudojama svarbių failų vientisumui patikrinti Operacinė sistema, svarbias programas, svarbūs duomenys. Stebėsena gali būti atliekama tiek pagal poreikį, tiek reguliariai.
Kaip tai daroma? Pirmiausia nustatykite, kurių failų vientisumą reikia valdyti. Kiekvienam failui pagal specialų algoritmą apskaičiuojama jos maišos reikšmė, o rezultatas išsaugomas. Praėjus reikiamam laikui, atliekamas panašus skaičiavimas ir palyginami rezultatai. Jei reikšmės skiriasi, tada faile esanti informacija buvo pakeista.
Kokias savybes turi turėti maišos funkcija?
- turi mokėti atlikti savavališko ilgio duomenų transformacijas į fiksuotus;
- turi turėti atvirą algoritmą, kad būtų galima ištirti jo kriptografinį stiprumą;
- turėtų būti vienpusis, tai yra, neturėtų būti matematinės galimybės iš rezultato nustatyti pradinius duomenis;
- turėtų „atsispirti“ susidūrimams, tai yra, neturėtų sukurti tų pačių verčių skirtingiems įvesties duomenims;
- neturėtų reikalauti didelių skaičiavimo išteklių;
- esant menkiausiam įvesties duomenų pakeitimui, rezultatas turėtų gerokai pasikeisti.
Kokie yra populiarūs maišos algoritmai?Šiuo metu naudojamos šios maišos funkcijos:
- CRC reiškia ciklinio atleidimo kodą arba kontrolinę sumą. Algoritmas yra labai paprastas, jis turi daugybę variantų, priklausomai nuo reikiamo išvesties ilgio. Ar ne kriptografinis!
- MD 5 yra labai populiarus algoritmas. Kaip jis ankstesnė versija MD 4 yra kriptografinė funkcija. Maišos dydis yra 128 bitai.
- SHA -1 taip pat yra labai populiari kriptografinė funkcija. Maišos dydis yra 160 bitų.
- GOST R 34.11-94 yra rusiškas kriptografinis standartas maišos funkcijos skaičiavimui. Maišos dydis yra 256 bitai.
Kada sistemos administratorius gali naudoti šiuos algoritmus? Dažnai atsisiunčiant bet kokį turinį, pavyzdžiui, programas iš gamintojo svetainės, muziką, filmus ar kitą informaciją, atsiranda kontrolinės sumos reikšmė, apskaičiuojama naudojant tam tikrą algoritmą. Saugumo sumetimais atsisiuntę turite savarankiškai apskaičiuoti maišos funkciją ir palyginti vertę su tuo, kas nurodyta svetainėje arba failo priede. Ar jūs kada nors tai padarėte?
Kaip patogiau apskaičiuoti maišą? Dabar yra daugybė tokių paslaugų, tiek mokamų, tiek nemokamų. Man asmeniškai HashTab patiko. Pirma, diegimo metu įrankis yra įterpiamas kaip skirtukas failo ypatybėse, antra, leidžia pasirinkti daugybę maišos algoritmų ir, trečia, ji yra nemokama privačiam nekomerciniam naudojimui.
Kas yra rusiškas? Kaip minėta aukščiau, Rusijoje galioja maišos standartas GOST R 34.11-94, kurį plačiai naudoja daugelis informacijos saugos priemonių gamintojų. Viena iš šių priemonių yra fiksavimo ir valdymo programa. pradinė būsena programinės įrangos paketą"FIX". Ši programa yra informacijos saugumo priemonių naudojimo efektyvumo stebėjimo priemonė.
FIX (2.0.1 versija), skirta Windows 9x/NT/2000/XP
- Duotų failų kontrolinių sumų apskaičiavimas naudojant vieną iš 5 įdiegtų algoritmų.
- Programinės įrangos paketo pradinės būsenos fiksavimas ir vėlesnis valdymas.
- Programinės įrangos paketų versijų palyginimas.
- Katalogų taisymas ir valdymas.
- Nurodytų failų (katalogų) pakeitimų kontrolė.
- Ataskaitų generavimas TXT, HTML, SV formatais.
- Gaminys turi FSTEC sertifikatą pagal NDV 3 Nr. 913 iki 2013 m. birželio 1 d.
O kaip su ECP? Maišos funkcijos skaičiavimo rezultatas kartu su vartotojo slaptuoju raktu patenka į kriptografinio algoritmo įvestį, kur apskaičiuojamas skaitmeninis parašas. Griežtai kalbant, maišos funkcija nėra EDS algoritmo dalis, tačiau dažnai tai daroma specialiai, kad būtų išvengta viešojo rakto atakos.
Šiais laikais daugelis elektroninės prekybos programų leidžia saugoti Slaptas raktas vartotojas privačioje prieigos rakto srityje (ruToken, eToken) be technines galimybes išgaunant jį iš ten. Pats žetonas turi labai ribotą atminties sritį, matuojamą kilobaitais. Norint pasirašyti dokumentą, jokiu būdu negalima perkelti dokumento į patį žetoną, tačiau labai paprasta perkelti dokumento maišą į žetoną ir gauti EDS išvestyje.
Maišos lentelės
Hash lentelė(sumaišyta lentelė, lentelė su apskaičiuotais adresais) yra dinaminių rinkinių palaikymo operacijos elemento pridėjimas, paieška ir ištrynimas bei specialių metodų naudojimas kreipiantis.
Pagrindinis skirtumas tarp lentelių ir kitų dinaminių rinkinių yra elemento adreso skaičiavimas pagal rakto vertę.
Maišos diegimo idėja yra ta, kad darbas su vienu dideliu masyvu sumažinamas iki darbo su daugybe mažų rinkinių.
Pavyzdžiui, užrašų knygelė. Knygos puslapiai pažymėti raidėmis. Raide pažymėtame puslapyje yra pavardės, prasidedančios šia raide. Didelis pavardžių rinkinys suskirstytas į 28 pogrupius. Ieškant knyga iškart atsidaro ant norimos raidės ir paieška paspartinama.
Programavimo maišos lentelėje- tai yra struktūra duomenys, kuriuose saugomos poros (raktas arba indeksas + reikšmė) ir su kuriais atliekamos trys operacijos: naujos poros pridėjimas, poros paieška ir trynimas pagal raktą.
Ieškokite maišos lentelėse atliekamas dviem etapais:
Pirmasžingsnis – maišos funkcijos, kuri konvertuoja, apskaičiavimas Raktas ieškoti skaičiuoklėje adresu:
antražingsnis yra konfliktų, susijusių su tokių raktų apdorojimu, sprendimo procesas.
Jeigu skirtingos vertybės lentelės raktų maišos funkcija generuoja tas pats adresus, sakoma, kad kyla susidūrimas(konfliktas, susidūrimas).
Maišos funkcijos
Pagrindinis maišos funkcijos tikslas yra suderinti įvairius raktai jei įmanoma įvairių ne neigiamas visas numeriai.
Temų maišos funkcija geriau, kaip mažiau identiški ji generuoja vertybes.
Maišos funkcija turi būti parinkta taip, kad būtų įvykdytos šios savybės:
maišos funkcija yra apibrėžta aibės elementuose ir užima sveikasis skaičius neneigiamas vertybės;
maišos funkcija lengva apskaičiuoti;
maišos funkcija gali užtrukti įvairių vertės nuo maždaug vienodai tikėtina(susidūrimų sumažinimas);
ant giminės argumentų vertės maišos funkcija tolimas vertybes viena nuo kitos.
Norėdami sukurti gerą maišos funkciją, turite žinoti raktų pasiskirstymą. Jei rakto pasiskirstymas yra žinomas, idealiu atveju rakto tankis ir maišos reikšmės tankio pasiskirstymas turėtų būti identiški.
Leisti p ( Raktas ) - pagrindinių užklausų paskirstymo tankis. Tada idealiu atveju lentelės įvesties užklausų paskirstymo tankis yra g ( H ( Raktas )) būti toks, kad vidutiniškai elementų skaičius, kat. reikėjo praeiti dvynių grandinėmis, tai buvo minimaliai.
Pavyzdys.
Tegul būna rinkinys raktai
{0, 1, 4, 5, 6, 7, 8, 9, 15, 20, 30, 40}
ir tegu stalas leidžia 4 įėjimas.
Galite sukurti maišos funkciją:
h(Raktas) = Raktas % 4 .
Tada gausite šiuos dalykus adresusįvestims
{0, 1, 2, 3} lentelės:
|
h(Raktas) |
|
Įėjimo numeris | ||||
|
Maksimalus grandinės ilgis | ||||
|
% paspaudimų | ||||
3 0,5 + 1,5 0,25 + 0,5 0,08 + 1 0,17 ≈ 2,1 sąrašo elementas.
Pavyzdys su kita maišos funkcija.
|
h(Raktas) |
|
Įėjimo numeris | ||||
|
% paspaudimų |
Vidutiniškai tai užtruks 4 1,5 0,25 = 1,5 sąrašo elementas.
Jei tai yra informacijos paieškos sistema, jos paieškos našumas padidės apie 25%.
Maišos funkcijų konstravimo metodai
Modulinė maiša
Paprastas, efektyvus ir dažniausiai naudojamas maišos metodas.
Lentelės dydis pasirenkamas kaip paprastas numeriai m o maišos funkcija apskaičiuojama kaip likusią divizijos dalį:
h(Raktas) = Raktas % m
Raktas– sveikoji skaitinė rakto reikšmė,
m- maišos verčių skaičius (maišos lentelės įrašai).
Tokia funkcija vadinama modulinis ir keičiasi nuo 0 prieš ( m - 1 ).
Modulinė maišos funkcija C++:
typedeftarptHashIndexType;
HashIndexTypeMaiša(tarptRaktas)
{ grąžintiRaktas % m; }
Pavyzdys
Raktas = {1, 3, 56, 4, 32, 40, 23, 7, 41,13, 6,7}
Leisti m = 5
h(Raktas) = {1, 3, 1, 4, 2, 0, 3, 2, 1, 3, 1, 2}
Pasirinkimas yra svarbus m.Norėdami gauti atsitiktinį raktų pasiskirstymą, turite paimti paprastas numerį.
Daugybos metodas
Maišos funkcija:
h(raktas) =
0 < A < 1 yra konstanta.
12 mod5 = 2 (likutis 12 padalijus iš 5).
5,04 mod1= 0,04 (išsiskiria trupmeninė dalis)
Pavyzdys
Raktas = 123456
m = 10000
A = 0,6180339887499 = 0,618…
h(Raktas) = =
priedų metodas
Naudojamas linijos kintamo ilgio (stalo dydis m lygus 256).
{ HashIndexType h = 0;
o (*str)
h += (*str)++;
grąžintih;
Adityvinio metodo trūkumas yra tas, kad neskiriami panašūs žodžiai ir anagramos, t.y. h(XY ) = h(YX )
priedų metodas, kur raktas yra simbolių eilutė. Maišos funkcijoje eilutė paverčiama sveikuoju skaičiumi, sudedant visus simbolius ir grąžinant likutį, padalijus iš m (dažniausiai stalo dydis m = 256).int h(char *key, int m) (int s = 0;while(*key)s += *key++;return s % m;) abc ir Taksi.Šį metodą galima šiek tiek modifikuoti ir gauti rezultatą susumavus tik pirmuosius ir paskutinius rakto eilutės simbolius. int h(char *key, int m) (int len = strlen(key), s = 0;if (len< 2) // Если длина ключа равна 0 или 1,s = key; // возвратить keyelse s = key + key;return s % m;}В этом случае коллизии будут возникать только в строках, например, abc ir amc.
maišos funkcija paima raktą ir iš jo apskaičiuoja adresą lentelėje (adresas gali būti indeksas masyve, prie kurio prijungtos grandinės), tai yra, pavyzdžiui, ji gali gauti skaičių 3 iš eilutės "abcd ", o iš eilutės "efgh" gali gauti skaičių 7 ir tada pirmoji grandinės struktūra paimama per maišą arba per maišą paieška tęsiama grandinėje, kol struktūrų grandinėje iš maišos randama "abcd" , arba "efgh" randamas struktūrų grandinėje iš maišos, kai randama struktūra su "abcd ", paimami ir grąžinami likę jos duomenys arba grąžinami visi bendrai (jos adresas), kad jūs gali paimti iš jo likusius duomenis, ir sukuriama struktūrų grandinė, nes daugelis skirtingi raktai, turi tą patį adresą lentelėje, tai yra, pavyzdžiui, maišos funkcija „abcd“ gali grąžinti 3, o „zxf9“ taip pat gali grąžinti 3, taigi jie yra susieti į grandinę, kuri kabo ant trečiojo indekso indekso. masyvas ......
Masyve H saugomos pačios rakto-reikšmių poros. Elementų įterpimo algoritmas tam tikra tvarka tikrina masyvo H langelius, kol randamas pirmasis laisvas langelis, kuriame bus rašomas naujas elementas.
Paieškos algoritmas maišos lentelės langeliuose ieško ta pačia tvarka, kaip ir įterpiant, kol randamas elementas su norimu raktu arba laisva langelis (tai reiškia, kad maišos lentelėje elemento nėra).
XOR
Naudojamas kintamo ilgio stygoms. Metodas panašus į adityvinį metodą, tačiau išskiria panašius žodžius. Jį sudaro tai, kad „išskirtinė ARBA“ operacija nuosekliai taikoma eilutės elementams
typedef unsigned char HashIndexType;
nepasirašytas char Rand8;
HashIndexType Maiša (char * str)
(nežymėtas simbolis h = 0;
tuo tarpu (*str) h = Rand8;
grąžintih; }
Čia Rand8 – 256 aštuonių bitų atsitiktinių skaičių lentelė.
stalo dydis<= 65536
typedef unsigned short int HashIndexType;
nepasirašytas char Rand8;
HashIndexType Maiša (char * str)
( HashIndexType h; nepasirašytas simbolis h1, h2;
if (*str == 0) grąžinti 0;
h1 = *str; h2 = *str + 1; str++;
o (*str)
( h1 = Rand8; h2 = Rand8;
str++; )
h = ((HashIndexType)h1<< 8) | (HashIndexType)h2;
grąžinimo h % HashTableSize )
Universalus maišos
Reiškia atsitiktinis maišos funkcijos pasirinkimas iš kai kurių rinkinių metu išpildymas programas.
Jei dauginimo metodu naudoti kaip BET seka atsitiktinis reikšmes, o ne fiksuotą skaičių, gausite universalią maišos funkciją.
Tačiau taip pat reikės laiko generuoti atsitiktinius skaičius didelis.
Gali būti naudojamas pseudoatsitiktinis numeriai.
// pseudoatsitiktinių skaičių generatorius
typedeftarptHashIndexType;
HashIndexTypeMaiša (char*v, intm)
( int h, a = 31415, b = 27183;
for(h = 0;*v != 0; v++, a = a*b % (m - l))
h = (a*h + *v) % m;
grįžti (h< 0) ? (h + m) : h;