Maišymo istorija
Bendroji maišos funkcija yra specialus programavimo funkcijos tipas, naudojamas susieti savavališko dydžio duomenis su fiksuoto dydžio. Maišos funkcijos atsirado iš poreikio suspausti duomenų, kad sumažėtų atminties, reikalingos dideliems failams laikyti, kiekis. Populiariausias maišos funkcijos naudojimo atvejis yra kita specifinė duomenų struktūra, vadinama a maišos lentelė, kuri plačiai naudojama greitam duomenų paieškai. Maišos funkcijos padeda pagreitinti lentelės ar duomenų bazės paiešką, nustatant bet kokius du tiksliai tuos pačius maišus.
Jie taip pat padeda susumuoti milžiniškų failų, tokių kaip mp3, PDF ar vaizdai, žymes, kad būtų galima valdyti darbą su šiais gana dideliais failų tipais. Norint greitai identifikuoti, pagrindinis maišos funkcijų reikalavimas yra tas, kad jos išvestis fiksuoto ilgio raidinių ir skaitinių simbolių eilutę.
Nors pagrindinė maišos funkcijos atsiradimo priežastis atsirado dėl poreikio suspausti turinį, antrinė nauda netrukus tapo maišos pagrindine dalimi: unikalūs unikalūs identifikatoriai. Geriausia, kai maišant kelis pranešimus, jokie du skirtingi pranešimai niekada neturėtų grąžinti to paties maišos. Du skirtingi maišos pranešimai, kurių rezultatas yra tas pats išvesties maišos, vadinami a susidūrimas.
Žvelgiant iš duomenų bazės valdymo perspektyvos, tai reikštų, kad du skirtingi objektai galiausiai laikomi toje pačioje ląstelėje – nieko gero, jei norima apibrėžti unikalius unikalius identifikatorius. Jei atsižvelgsime į maišos funkciją su begaliniai įėjimai (tai reiškia, kad mes galime išmaišyti bet kokią eilutę), galime tiksliai išsiaiškinti, kodėl susidūrimai iš tikrųjų yra neišvengiamas.
Balandžių skylės principas
Kriptografijos matematikoje egzistuoja sąvoka, vadinama balandžių skylės principas kuriame teigiama, kad jei (n) elementų sutalpinsime į (m) erdves kur n > m, tada iš principo yra bent viena erdvė (m), kurią užima daugiau nei du elementai (n).
Pavyzdžiui, penki asmenys tikrina savo paltus viename iš trijų galimų kailių. Pagal balandžių skylės principą, kadangi sandėliuojamų paltų skaičius (n) yra didesnis už turimus kubitus (m), garantuojama, kad bent vienoje kubike telpa daugiau nei vienas kailis.
Paprastai programinės įrangos inžinierius domina maišos funkcijos su begalinis domenas (tai reiškia, kad jie ima visų įmanomų ilgių įvesties eilutes) ir a baigtinis diapazonas. Vėlgi vadovaujantis balandžių skylės principu, nes mūsų diapazonas (n) yra mažesnis nei mūsų domenas (m), tai reiškia, kad turi įvykti bent vienas susidūrimas. Todėl efektyvi maišos funkcija tik leidžia kuo labiau sumažinti susidūrimų skaičių – kodėl tai svarbu, paaiškės po akimirkos, tačiau kol kas grįžkime prie maišų istorijos.
Maišos funkcijos atsirado griežtai dėl duomenų bazės priežiūros & valdymo poreikiai, kurie pirmiausia skatino greitį, jų naudingumas greitai vystėsi. Speciali maišos funkcijų šaka, kuri skatino privatumą, saugumą, & netrukus į lauką pateko skaidrumas; maišos funkcijų šaka, kuri išliks šio straipsnio dėmesio centre: kriptografinės maišos funkcijos.
Kriptografinis maišymas
Kriptografinės maišos funkcijos, kaip taikliai suprantamas iš pavadinimo, palaiko absoliučiai nenutrūkstamų pranešimų išsaugojimą. Nors susidūrimų sumažinimas yra gera kitų maišos funkcijų, konkrečiai kriptografinių funkcijų, praktika, tačiau susidūrimų sumažinimas yra a reikalavimas. Užuot maksimaliai padidinę greitos duomenų bazės ar lentelių paieškos scenarijaus naudingumą, kriptografinės maišos funkcijos yra kuriamos atsižvelgiant į rungimosi scenarijų: tokį, kuriame kodų pertraukiklis (kriptoanalitikas) aktyviai bando sukelti susidūrimą. Dabar apibrėžsime standartinius maišos funkcijų žymėjimus & nustatyti maišos funkcijos principus kriptografijos perspektyvoje.
Maišos funkcijos žymėjimas
Bendroje kriptografinio maišos funkcijoje yra du įėjimai: pranešimas, kurį ji suspaus, arba maiša (x) & viešasis (-ieji) raktas (-ai), kuris (-iai) nurodo fiksuoto ilgio mūsų maišos išvestį raidiniais ir skaitmeniniais ženklais. Mūsų maišos rezultatas yra vadinamas pranešimo santrauka arba tiesiog santrauka (x *). Tai atrodo taip:
H (s, x) = x *
Pabrėžkime šį užrašą, eidami per realaus gyvenimo pavyzdį, kaip maišyti eilutę naudojant anksčiau standartinę maišos funkciją, pavadintą MD5. Tarkime, kad norime naudoti MD5 „Hello World!“ Maišos stygos. Mes taip pat žinome, kad pagal numatytuosius nustatymus MD5 visada pateikia 128 bitų eilutę (0 & 1 ’). Šis žymėjimas atrodytų taip:
H (128, x) = ed076287532e86365e841e92bfc50d8c
Tiesą sakant, jei einate į priekį & pabandykite pateikti MD5 maišos funkcija „Hello World!“ patys turėtumėte pamatyti tą patį gautą maišos variantą. Nuostabu. Dabar pereikime prie susidūrimo žymėjimo nustatymo; be ankstesnių kintamųjų H, s, x, & x * dabar pristatome antrą pranešimą (x ’). Skaitmeniškai susidūrimas įvyksta maišant du skirtingus pranešimus (x & x ’) gaunamas tas pats pranešimo santrauka (x *):
Jei H (128, x) = H (128, x ’), sakoma, kad mūsų maišos funkcija (H) susiduria ties x & x ’.
Dabar mes nustatėme žymėjimą dabartiniu maišos funkcijos kriptografijos standartu; jei priešininkas gali realiai (kalbant skaičiavimais) sukelti susidūrimą, maišos funkcija nebelaikoma praktiškai saugia.
Uždarymo mintys iki kito karto
Paskutinis matematinis apibrėžimas yra tas, kur gyvena patrauklus maišos funkcijos praktiškumas. Maišos funkcijos atsirado dėl poreikio suspausti & išleisti standartizuotus vienodus duomenis, kad būtų patogiau saugoti, o tai reiškia, kad jie išspjauna pseudo atsitiktines a fiksuoto ilgio. Vis dėlto norint sukurti a visiškai atsparus susidūrimams maišos funkcija, kiekviename pranešime (x) turi būti maišos išvestis tokio pat ilgio kaip ir įvestis. Neturėdami fiksuoto ilgio maišų, mes prarandame galimybę jas naudoti kaip patogią duomenų struktūrą, tačiau priskirdami fiksuotą ilgį, mes padarome savo maišos funkciją ne visiškai susidūrusią.
PS – aš tikiu, kad kai kurie iš jūsų išmaniųjų slapukų pastebėjo, kad MD5 pavyzdyje mes pažymėjome maišos funkciją, kuri pateikia ilgio eilutę 128, dar mūsų „Labas pasaulis!“ maišas grąžino a 32 raidinė ir skaitinė simbolių eilutė. Grįžk kitą kartą & gilinsimės į maišos funkcijas, kad paaiškintume, kur atsirado šis skirtumas.
