Úgy gondolom, sokan tisztában vannak azzal, hogy 2007 óta az Egyesült Államok Nemzeti Szabványügyi és Technológiai Intézete (NIST) versenyt rendez az SHA-1 helyettesítésére szolgáló hash algoritmus és egy SHA-2 algoritmuscsalád kidolgozására. Ez a téma azonban valamilyen oknál fogva figyelmen kívül marad az oldalon. Valójában ez hozott el hozzád. Figyelmébe ajánlom a hash algoritmusokról szóló cikksorozatot. Ebben a ciklusban együtt tanulmányozzuk a hash függvények alapjait, átgondoljuk a leghíresebb hash algoritmusokat, belecsöppenünk az SHA-3 verseny atmoszférájába, és átgondoljuk azokat az algoritmusokat, amelyek azt állítják, hogy megnyerik, ezeket mindenképpen teszteljük. Ezenkívül, ha lehetséges, az orosz hashelési szabványokat is figyelembe veszik.

Magamról

Az Információbiztonsági Tanszék hallgatója.

A hashelésről

Jelenleg szinte egyetlen kriptográfiai alkalmazás sem teljes a hash használata nélkül.
A hash függvények olyan függvények, amelyek egy tetszőleges üzenetet vagy adathalmazt, általában bináris ábécében írnak, "tömörítenek" valamilyen fix hosszúságú bitkombinációba, amelyet konvolúciónak neveznek. A hash-függvények számos alkalmazási lehetőséget kínálnak statisztikai kísérletekben, logikai eszközök tesztelésében, algoritmusok felépítésében a gyors kereséshez és az adatbázisokban lévő rekordok integritásának ellenőrzéséhez. A hash függvények fő követelménye az értékek eloszlásának egységessége az argumentumértékek véletlenszerű megválasztásával.
A kriptográfiai hash függvény minden olyan hash függvény, amely kriptográfiailag biztonságos, azaz számos, a kriptográfiai alkalmazásokra jellemző követelményt kielégít. A kriptográfiában a hash függvényeket a következő problémák megoldására használják:
- adatintegritás-ellenőrző rendszerek kiépítése azok továbbítása vagy tárolása során,
- adatforrás hitelesítés.

A hash függvény bármely függvény h:X -> Y, könnyen kiszámítható és olyan, hogy bármilyen üzenethez M jelentése h(M) = H (konvolúció) fix bithosszúsággal rendelkezik. x- az összes üzenet készlete, Y- rögzített hosszúságú bináris vektorok halmaza.

A hash függvények általában az úgynevezett egylépéses összehúzó függvények alapján épülnek fel y \u003d f (x 1, x 2) két változó, ahol x 1, x2és y- bináris hosszúságú vektorok m, nés n illetve, és n a konvolúció hossza, és m- üzenetblokk hossza.
Az érték megszerzéséhez h(M) az üzenetet először hosszúságú blokkokra bontják m(Ugyanakkor, ha az üzenet hossza nem többszöröse m akkor az utolsó blokk valamilyen speciális módon kiegészítésre kerül a teljesre), majd a kapott blokkra M 1 , M 2 ,..., M N alkalmazza a következő szekvenciális eljárást a konvolúció kiszámításához:

H o \u003d v,
Hi = f(Mi,Hi-1), i = 1,..., N,
h(M) = H N

Itt v- valamilyen állandó, gyakran inicializáló vektornak nevezik. Kiszáll
különböző okokból, és lehet titkos állandó vagy véletlenszerű adatok halmaza (például dátum és idő kiválasztása).
Ezzel a megközelítéssel a hash függvény tulajdonságait teljes mértékben az egylépéses összehúzó függvény tulajdonságai határozzák meg.

A kriptográfiai hash függvényeknek két fontos típusa van – kulcsos és kulcs nélküli. A kulcsfontosságú hash függvényeket üzenethitelesítési kódoknak nevezzük. Lehetővé teszik, hogy további eszközök nélkül garantáljuk mind az adatforrás helyességét, mind az adatok sértetlenségét a kölcsönösen megbízható felhasználókkal rendelkező rendszerekben.
A kulcs nélküli hash függvényeket hibafelismerő kódoknak nevezzük. További eszközök (például titkosítás) segítségével lehetővé teszik az adatok sértetlenségének garantálását. Ezek a hash függvények megbízható és nem megbízható felhasználókkal rendelkező rendszerekben is használhatók.

A statisztikai tulajdonságokról és követelményekről

Mint mondtam, a hash függvények fő követelménye az értékek egyenletes eloszlása ​​az argumentumértékek véletlenszerű megválasztásával. A kriptográfiai hash függvényeknél az is fontos, hogy az argumentum legkisebb változása esetén a függvény értéke nagymértékben megváltozzon. Ezt hívják lavinaeffektusnak.

Nak nek kulcsfunkciók a kivonatolás a következő követelményekkel rendelkezik:
- a gyártás lehetetlensége,
- a módosítás lehetetlensége.

Az első követelmény azt jelenti, hogy nagyon nehéz egy üzenetet a megfelelő hajtási értékkel egyeztetni. A második az, hogy egy adott, ismert hajtási értékkel rendelkező üzenethez egy másik, a megfelelő hajtási értékkel rendelkező üzenetet egyeztetni kell.

A kulcsnélküli funkciók követelményei a következők:
- egyirányú,
- ütközésállóság,
- ellenállás a második prototípus megtalálásával szemben.

Az egyirányúság alatt azt értjük, hogy egy adott konvolúciós érték alapján nagyon bonyolult az üzenet megtalálása. Meg kell jegyezni, hogy a Ebben a pillanatban nincs hash függvény használatban a bevált egyirányú funkcióval.
Az ütközésállóság alatt azt értjük, hogy nehéz megtalálni az azonos hajtási értékű üzenetpárt. Általában az, hogy a kriptoanalizátorok találják meg az ütközések létrehozásának módját, az első jele az algoritmus elavultságának és gyors cseréjének szükségességének.
A második előkép megtalálásával szembeni ellenállás alatt azt a nehézséget értjük, hogy egy adott, ismert hajtási értékű üzenethez azonos hajtási értékű második üzenetet találunk.

Ez volt az elméleti rész, ami hasznos lesz számunkra a jövőben...

A népszerű hash algoritmusokról

Algoritmusok CRC16/32- ellenőrző összeg (nem kriptográfiai konverzió).

Algoritmusok MD2/4/5/6. Ron Rivest, az RSA algoritmus egyik szerzőjének alkotásai.
Az MD5 algoritmus egykor nagyon népszerű volt, de a kilencvenes évek végén megjelentek a hackelés első előfeltételei, mára pedig rohamosan csökken a népszerűsége.
Az MD6 algoritmus konstruktív szempontból nagyon érdekes algoritmus. Nevezték az SHA-3 versenyre, de sajnos a szerzőknek nem sikerült a színvonalat hozniuk, és ez az algoritmus nem szerepel a második fordulóba jutott jelöltek listáján.

Vonalzó algoritmusok SHA Ma széles körben használt algoritmusok. Aktív átmenet van az SHA-1-ről az SHA-2-verziószabványra. Az SHA-2 az SHA224, SHA256, SHA384 és SHA512 algoritmusok gyűjtőneve. Az SHA224 és az SHA384 lényegében az SHA256 és az SHA512 analógjai, csak a konvolúció kiszámítása után a benne lévő információk egy részét eldobják. Csak a régebbi berendezésekkel való kompatibilitás biztosítására használhatók.

Orosz szabvány - GOST 34.11-94.

A következő cikkben

Az MD algoritmusok áttekintése (MD4, MD5, MD6).

Irodalom

A. P. Alferov, A kriptográfia alapjai.

Bruce Schneier, Alkalmazott kriptográfia.

A kivonatolás egy speciális módszer az adatok címzésére (valamilyen térköz-algoritmus) egyedi kulcsaikkal ( kulcs ) hogy gyorsan megtalálja a szükséges információkat.

Alapfogalmak

Hash táblázat

A hash tábla egy szabályos tömb, amelynek speciális címe valamilyen függvény (Hash függvény) adja meg.

hash függvény

Egy függvény, amely egy adatelem kulcsát a táblázat valamely indexévé alakítja ( hash tábla), nak, nek hívják hash függvény vagy hash függvény :

én = h (kulcs );

ahol kulcs- átalakítható kulcs, én- eredményül kapott táblázatindex, azaz. a kulcs például egész számok halmazában jelenik meg ( hash címek ), amelyeket később az adatok eléréséhez használunk.

A kivonatolás ilyen módon egy olyan technika, amely magában foglalja egy kulcs értékének felhasználását egy speciális táblában elfoglalt helyzetének meghatározására.

A terjedési függvény azonban képes számos az egyedi kulcsértékek ugyanazt a pozícióértéket adják én a hash táblázatban. Meghívásra kerül az a helyzet, amikor két vagy több kulcs ugyanazt az indexet (hash címet) kapja ütközés (ütközés) a kivonatolásban, ezért a kivonatolási sémának tartalmaznia kell konfliktusmegoldó algoritmus , a műveletek sorrendjének meghatározása, ha a pozíció én=h(kulcs) már foglalt egy másik kulccsal rendelkező bejegyzést.

Számos kivonatolási séma létezik, amelyek különböznek a használt hash függvénytől. h(kulcs) és konfliktusmegoldó algoritmusok.

A hash függvény megadásának leggyakoribb módja a következő: felosztási módszer.

A kezdeti adatok: - valamilyen egész kulcs kulcsés az asztal mérete m. Ennek a függvénynek az eredménye, hogy a kulcsot elosztjuk a táblázat méretével. Egy ilyen függvény általános formája a C/C++ programozási nyelvben:

int h (int kulcs , int m ) {

Mert m= 10 hash függvény a kulcs legkisebb jelentőségű számjegyét adja vissza.

m=100 esetén a hash függvény a kulcs két legkisebb jelentőségű számjegyét adja vissza.

A vizsgált példákban a hash függvény én=h(kulcs) csak azt a pozíciót határozza meg, ahonnan a billentyűvel meg kell keresni (vagy kezdetben el kell helyezni a táblázatban) a bejegyzést kulcs. Ezután valamilyen hash-sémát (algoritmust) kell használnia.

Kivonatolási sémák

A legtöbb probléma esetén két vagy több kulcs ugyanúgy kivonatolva van, de nem foglalhatják el ugyanazt a cellát a hash táblában. Van két lehetséges opciók: vagy keressen egy másik pozíciót az új kulcshoz, vagy hozzon létre egy külön listát minden egyes hash tábla indexéhez, amelyben az ehhez az indexhez leképezett összes kulcs elhelyezhető.

Ez a változat a két klasszikus kivonatolási séma:

kivonatolás nyílt címzéssel lineáris szondázással - lineáris szonda nyisd ki megszólítás.

lánckivonat (listákkal), vagy ún. többdimenziós hash - láncolás val vel különálló listákon;

Nyílt címzési módszer lineáris tapintással . Kezdetben a hash tábla összes cellája, amely egy normál egydimenziós tömb, üresként van megjelölve. Ezért új kulcs hozzáadásakor ellenőrzik, hogy az adott cella foglalt-e. Ha a cella foglalt, akkor az algoritmus körben keres, amíg nincs üres hely („nyitott cím”).

Azok. a homogén kulcsokkal rendelkező elemek a kapott index közelében helyezkednek el.

A jövőben a keresés során először keresse meg a pozíciót a kulcs segítségével én táblázatban, és ha a kulcs nem egyezik, akkor a következő keresés a konfliktusfeloldó algoritmus szerint történik, a pozícióból kiindulva. én. .

Láncos módszer a domináns stratégia . Ebben az esetben én a kiválasztott hash függvényből kapott h(kulcs)=én, indexként kezeljük a listák hash-táblázatába, azaz. kulcs előbb kulcs a következő bejegyzés a pozícióra van leképezve én = h(kulcs) táblázatok. Ha a pozíció szabad, akkor a kulcsos elem kerül bele. kulcs, ha foglalt, akkor konfliktusfeloldó algoritmust dolgoznak ki, aminek eredményeként az ilyen kulcsok egy listában kerülnek elhelyezésre én-a hash tábla cellája. Például

Ennek eredményeként van egy táblázatunk a hivatkozott listák vagy fák tömbjével.

A hash tábla feltöltésének (olvasásának) folyamata egyszerű, de az elemek eléréséhez a következő műveletekre van szükség:

Index számítás én;

Keressen a megfelelő láncban.

Új elem hozzáadásakor a keresés javítása érdekében a beszúrási algoritmust nem a lista végén, hanem sorrendben használhatjuk, pl. elem hozzáadása Jó helyen.

Példa a közvetlen címzési módszer megvalósítására lineáris szondázással . A kiindulási adat 7 rekord (az egyszerűség kedvéért az információs rész csak egész számokból áll), a deklarált szerkezeti típusból:

intkey; // Kulcs

intinfo; // Információ

(59,1), (70,3), (96,5), (81,7), (13,8), (41,2), (79,9); hash táblázat mérete m=10.

hash függvény én=h(adat) =adat.kulcs%tíz; azok. maradék 10-zel való osztás után - én.

A kiindulási adatok alapján szekvenciálisan kitöltjük a hash táblát.

Az első öt kulcs kivonatolása különféle indexeket (kivonatcímeket) eredményez:

Az első ütközés a 81-es és 41-es billentyűk között történik - az 1-es indexű hely foglalt. Ezért átnézzük a hash táblát, hogy megtaláljuk a legközelebbi szabad helyet, ebben az esetben az én = 2.

A következő 79 gomb szintén ütközést generál: a 9. pozíció már foglalt. Az algoritmus hatékonysága meredeken csökken, mert 6 próba (összehasonlítás) kellett a szabad hely megtalálásához, az index ingyenesnek bizonyult én= 4.

Ennek a módszernek a mintáinak teljes száma elemenként 1-től n-1-ig terjed, ahol n a hash-tábla mérete.

A láncolási módszer megvalósítása az előző példához. Strukturális típust deklarálunk egy listaelemhez (egyirányú):

intkey; // Kulcs

intinfo; // Információ

zap*Next; // Mutató erre következő elem a listán

A kiindulási adatok alapján szekvenciálisan kiegészítéssel töltjük ki a hash táblát új elem a lista végére, ha a hely már foglalt.

Az első öt kulcs kivonatolása, mint az előző esetben, különböző indexeket (kivonatcímeket) ad: 9, 0, 6, 1 és 3.

Ütközés esetén az új elem a lista végére kerül. Ezért a 41 kulcsos elem a 81 kulcsos elem után, a 79 kulcsos elem pedig az 59 kulcsos elem után kerül elhelyezésre.

Egyéni feladatok

1. Bináris fák. A véletlenszám-generátor program segítségével szerezzen 10 értéket 1 és 99 között, és építsen fel egy bináris fát.

Kerülőt tesz:

1.a Bejárás balról jobbra: Bal-Gyökér-Jobb: először a bal oldali részfát látogassa meg, majd a gyökeret, végül a jobb oldali részfát.

(Vagy fordítva, jobbról balra: Jobb-Gyökér-Bal)

1.b Bejárás fentről lefelé: Gyökér-Bal-Jobb: a részfák gyökerének meglátogatása.

1. Bejárás alulról felfelé: Bal-jobb-Gyökér: a részfák után a gyökér meglátogatása

A legkülönfélébb iparágakban információs technológiák találja meg a hash függvényeket. Egyrészt arra szolgálnak, hogy nagymértékben leegyszerűsítsék a felhasználók közötti adatcserét és bizonyos célokra használt fájlok feldolgozását, másrészt optimalizálják a megfelelő erőforrásokhoz való hozzáférés szabályozását biztosító algoritmusokat. A hash függvény az egyik kulcsfontosságú eszközök az adatok jelszavas védelmének biztosítása, valamint az EDS segítségével aláírt dokumentumok cseréjének megszervezése. A fájlok gyorsítótárazására számos szabvány létezik. Sokukat orosz szakemberek fejlesztették ki. Melyek a hash függvények típusai? Melyek a gyakorlati alkalmazásuk fő mechanizmusai?

Ami?

Először is vizsgáljuk meg a hash függvény fogalmát. Ezt a kifejezést általában olyan algoritmusként értelmezik, amely bizonyos mennyiségű információt matematikai módszerekkel rövidebb karaktersorozattá alakít át. A hash függvény gyakorlati jelentősége számos területen nyomon követhető. Így használhatók a fájlok és programok integritásának ellenőrzésére. A titkosítási algoritmusokban kriptográfiai hash függvényeket is használnak.

Jellemzők

Tekintsük a vizsgált algoritmusok legfontosabb jellemzőit. Ezek között:

• belső algoritmusok jelenléte az eredeti hosszúságú adatok rövidebb karaktersorozattá alakítására;
• nyitottság a kriptográfiai ellenőrzéshez;
• olyan algoritmusok jelenléte, amelyek lehetővé teszik az eredeti adatok biztonságos titkosítását;
• alkalmazkodóképesség a dekódoláshoz kis használatával számítási teljesítmény.

A hash függvény további fontos tulajdonságai a következők:

• tetszőleges hosszúságú kezdeti adattömbök feldolgozásának képessége;
• rögzített hosszúságú kivonatolt blokkokat generál;
• egyenletesen elosztja a függvényértékeket a kimeneten.

A vizsgált algoritmusok érzékenységet is feltételeznek a bemeneti adatokra 1 bites szinten. Vagyis még ha relatíve legalább 1 betű megváltozik a forrásdokumentumban, a hash függvény másképp fog kinézni.

A hash függvényekkel szemben támasztott követelmények

Az adott területen gyakorlati használatra szánt hash-függvényekre számos követelmény vonatkozik. Először is, a megfelelő algoritmusnak érzékenynek kell lennie a kivonatolt dokumentumok belső szerkezetének változásaira. Vagyis a hash függvényt fel kell ismerni, amikor arról van szó szöveges fájl, bekezdés-permutáció, elválasztás. Egyrészt a dokumentum tartalma nem változik, másrészt a szerkezete korrigálásra kerül, és ezt a folyamatot fel kell ismerni a kivonatolás során. Másodszor, a vizsgált algoritmusnak úgy kell átalakítania az adatokat, hogy a fordított művelet (a hash eredeti dokumentummá alakítása) a gyakorlatban lehetetlen legyen. Harmadszor, a hash függvénynek olyan algoritmusok használatát kell magában foglalnia, amelyek gyakorlatilag kizárják annak lehetőségét, hogy ugyanazt a karaktersorozatot hash formájában képezzék, más szóval az úgynevezett ütközések megjelenését. Lényegüket egy kicsit később tárgyaljuk.

A felsorolt ​​követelmények, amelyeknek a hash függvény algoritmusának meg kell felelnie, elsősorban összetett matematikai megközelítések alkalmazásával érhető el.

Szerkezet

Vizsgáljuk meg, milyen lehet a vizsgált függvények felépítése. Mint fentebb megjegyeztük, a vizsgált algoritmusokkal szemben támasztott fő követelmények között szerepel az egyirányú titkosítás biztosítása. Akinek csak hash áll a rendelkezésére, annak gyakorlatilag nem szabad hozzájutnia az eredeti dokumentumhoz.

Milyen struktúrában ábrázolható egy ilyen célra használt hash függvény? Összeállítására a következő példa lehet: H (hash, azaz hash) = f (T (szöveg), H1), ahol H1 a T szövegfeldolgozó algoritmus. Ez a funkcióúgy hasítja a T-t, hogy a H1 ismerete nélkül gyakorlatilag lehetetlen lesz teljes értékű fájlként megnyitni.

Hash függvények használata a gyakorlatban: Fájlok letöltése

Vizsgáljuk meg most részletesebben a hash függvények gyakorlati használatának lehetőségeit. A megfelelő algoritmusok használata használható szkriptek írásakor az internetes szerverekről fájlok letöltéséhez.

A legtöbb esetben minden fájlhoz egy bizonyos ellenőrző összeget határoznak meg - ez a hash. Ennek meg kell egyeznie a kiszolgálón található és a felhasználó számítógépére letöltött objektumnál. Ha nem ez a helyzet, akkor előfordulhat, hogy a fájl nem nyílik meg, vagy hibásan indul el.

Hash függvény és digitális aláírás

A digitális aláírást tartalmazó dokumentumok cseréjének megszervezésében elterjedt a hash függvények alkalmazása. Ebben az esetben az aláírt fájl kivonatolása megtörténik, így a címzett ellenőrizni tudja, hogy az eredeti-e. Bár a hash függvény formálisan nem szerepel a szerkezetben elektronikus kulcs, rögzíthető annak a hardvernek a flash memóriájában, amellyel a dokumentumokat aláírják, mint például az eToken.

Az elektronikus aláírás egy fájl titkosítása nyilvános és privát kulcsokkal. Ez azt jelenti, hogy a forrásfájlhoz egy privát kulccsal titkosított üzenetet csatolnak, és a digitális aláírást a nyilvános kulcs. Ha mindkét dokumentum hash funkciója megegyezik, akkor a címzett fájlja hiteles, a feladó aláírása pedig helyes.

A kivonatolás, mint fentebb megjegyeztük, nem közvetlenül az EDS összetevője, azonban lehetővé teszi az algoritmusok nagyon hatékony optimalizálását a Elektronikus aláírás. Tehát csak a hash titkosítható, maga a dokumentum nem. Ennek eredményeként jelentősen megnő a fájlfeldolgozás sebessége, ugyanakkor hatékonyabb EDS védelmi mechanizmusok biztosítására nyílik lehetőség, hiszen a számítási műveletek során ebben az esetben nem a kiindulási adatok feldolgozására, hanem annak biztosítására kerül a hangsúly. az aláírás kriptográfiai erőssége. A hash funkció számos adattípus aláírását is lehetővé teszi, nem csak szöveget.

Jelszó-ellenőrző

A kivonatolás másik lehetséges alkalmazási területe a jelszó-ellenőrző algoritmusok szervezése, amelyek célja az egyes fájlforrásokhoz való hozzáférés megkülönböztetése. Hogyan lehet bizonyos típusú hash függvényeket bevonni az ilyen problémák megoldásába? Nagyon egyszerű.

A tény az, hogy a legtöbb szerveren, amelyekhez a hozzáférést megkülönböztetik, a jelszavakat kivonatolt értékek formájában tárolják. Ez teljesen logikus – ha a jelszavakat eredeti szöveges formájukban mutatnák be, a hozzájuk jutott hackerek könnyen elolvashatnák a titkos adatokat. Viszont a hash alapján nem egyszerű kiszámítani a jelszót.

Hogyan történik a felhasználói hozzáférés ellenőrzése a vizsgált algoritmusok használatakor? A felhasználó által beírt jelszót a rendszer ellenőrzi a szerveren tárolt hash függvényben rögzítettekkel. Ha a szövegblokkok értékei megegyeznek, a felhasználó megkapja a szükséges hozzáférést az erőforrásokhoz.

A legegyszerűbb hash függvény jelszóellenőrző eszközként használható. A gyakorlatban azonban az informatikai szakemberek leggyakrabban összetett, többlépcsős kriptográfiai algoritmusokat használnak. Jellemzően ezeket egészítik ki a biztonságos csatornás adatátviteli szabványok használatával, így a hackerek nem tudják észlelni vagy kitalálni a felhasználó számítógépéről a szerverekre továbbított jelszót, mielőtt azt a kivonatolt szövegblokkokkal ellenőrzik.

Hash függvény ütközések

A hash függvények elméletében egy olyan jelenséget biztosítanak, mint az ütközés. Mi a lényege? A hash ütközés olyan helyzet, amelyben két különböző fájlnak ugyanaz a hash kódja. Ez akkor lehetséges, ha a cél karaktersorozat hossza kicsi. Ebben az esetben nagyobb lesz a hash egyezés valószínűsége.

Az ütközések elkerülése érdekében különösen ajánlott egy kettős algoritmus, az úgynevezett "hash függvény hash" használata. Ez magában foglalja a nyílt és zárt kód kialakítását. A kritikus problémák megoldásában sok programozó azt javasolja, hogy ne használjon hash függvényeket olyan esetekben, amikor ez nem szükséges, és mindig tesztelje a megfelelő algoritmusokat bizonyos kulcsokkal való legjobb kompatibilitás érdekében.

Megjelenés története

A hash függvények elméletének megalapítóinak Carter, Wegman, Simonson, Bierbrouer kutatók tekinthetők. Az első verziókban a megfelelő algoritmusokat eszközként használták tetszőleges hosszúságú karaktersorozatok egyedi képeinek előállítására, amelyek későbbi azonosítását és hitelességének ellenőrzését szolgálták. A hashnek viszont a megadott kritériumoknak megfelelően 30-512 bit hosszúságúnak kell lennie. Különlegességként hasznos ingatlan megfelelő funkciókat, figyelembe vették, hogy alkalmas-e forrásként való felhasználásra a fájlok gyors kereséséhez vagy rendezéséhez.

Népszerű kivonatolási szabványok

Most nézzük meg, milyen népszerű szabványokban ábrázolhatók a hash függvények. Az egyik a CRC. Ez az algoritmus ciklikus kód ellenőrző összegnek is nevezik. Ezt a szabványt az egyszerűség és egyben sokoldalúság jellemzi - ezen keresztül az adatok legszélesebb körét tudja kivonatolni. A CRC az egyik leggyakoribb nem kriptográfiai algoritmus.

Az MD4 és MD5 szabványokat viszont széles körben használják a titkosításban. Egy másik népszerű kriptográfiai algoritmus az SHA-1. Különösen a 160 bites hash mérete jellemzi, ami nagyobb, mint az MD5 - ez a szabvány 128 bitet támogat. Vannak orosz szabványok, amelyek szabályozzák a hash függvények használatát - GOST R 34.11-94, valamint a GOST R 34.11-2012, amely felváltotta. Megjegyzendő, hogy az Orosz Föderációban elfogadott algoritmusok által biztosított hash érték 256 bit.

A kérdéses szabványok többféleképpen osztályozhatók. Például vannak olyanok, amelyek blokk- és speciális algoritmusokat használnak. Az első típusú szabványokon alapuló számítások egyszerűsége gyakran együtt jár azok alacsony sebességével. Ezért a blokk algoritmusok alternatívájaként olyanok is használhatók, amelyek kisebb mennyiségű szükséges számítási műveletet tartalmaznak. Szokásos a nagy sebességű szabványokra hivatkozni, különösen a fent említett MD4, MD5 és SHA szabványokra. Nézzük meg részletesebben a speciális kivonatolási algoritmusok sajátosságait az SHA példáján.

Az SHA algoritmus jellemzői

Az SHA szabványon alapuló hash függvények alkalmazása leggyakrabban az eszközfejlesztés területén valósul meg digitális aláírás DSA dokumentumok. Ahogy fentebb megjegyeztük, SHA algoritmus támogatja a 160 bites hash-t (amely egy karaktersorozat úgynevezett "kivonatát" biztosítja). Kezdetben a szóban forgó szabvány az adattömböt 512 bites blokkokra osztja. Ha szükséges, ha az utolsó blokk hossza nem éri el a megadott értéket, akkor a fájlszerkezetet 1-gyel és a szükséges számú nullával töltjük ki. Ezenkívül a megfelelő blokk végén egy kód kerül beírásra, amely rögzíti az üzenet hosszát. A vizsgált algoritmus 80 logikai függvényt tartalmaz, amelyeken keresztül 3 szó kerül feldolgozásra, 32 bitben ábrázolva. Az SHA szabvány 4 konstans használatát is előírja.

Kivonatoló algoritmusok összehasonlítása

Vizsgáljuk meg, hogyan korrelálnak a különböző szabványokhoz kapcsolódó hash-függvények tulajdonságai az orosz GOST R 34.11-94 szabvány és az amerikai SHA jellemzőinek összehasonlításával, amelyet fentebb tárgyaltunk. Először is meg kell jegyezni, hogy az Orosz Föderációban kifejlesztett algoritmus 1 ciklusonként 4 titkosítási művelet végrehajtását foglalja magában. Ez 128 körnek felel meg. Viszont 1 kör alatt SHA használatakor kb. 20 parancs kiszámítása várható, míg összesen 80 kör van, így az SHA használata 512 bit kezdeti adat feldolgozását teszi lehetővé 1 cikluson belül. Míg az orosz szabvány 256 bites adatciklusban képes műveleteket végrehajtani.

A legújabb orosz algoritmus sajátosságai

Fentebb megjegyeztük, hogy a GOST R 34.11-94 szabványt egy újabb váltotta fel - GOST R 34.11-2012 Stribog. Vizsgáljuk meg részletesebben a sajátosságait.

Keresztül ezt a szabványt megvalósíthatók, mint a fent tárgyalt algoritmusok esetében, kriptográfiai hash függvények. Megjegyzendő, hogy a legújabb orosz szabvány 512 bites bemeneti adatblokkot támogat. A GOST R 34.11-2012 fő előnyei:

• magas szintű védelem a titkosítások feltörésével szemben;
• megbízhatóság, amelyet a bevált tervek használata támaszt alá;
• a hash függvény gyors kiszámítása, a transzformációk hiánya az algoritmusban, amelyek megnehezítik a függvény felépítését és lassítják a számítást.

Az új orosz szabvány jelentős előnyei kriptográfiai titkosítás lehetővé teszi annak alkalmazását a legszigorúbb kritériumoknak megfelelő munkafolyamat megszervezésében, amelyet a szabályozó jogszabályok előírnak.

A kriptográfiai hash függvények sajátosságai

Nézzük meg részletesebben, hogy az általunk vizsgált algoritmustípusok hogyan használhatók a kriptográfia területén. A megfelelő funkciókkal szemben támasztott fő követelmény az ütközésekkel szembeni ellenállás, amit fentebb említettünk. Vagyis nem szabad duplikált hash értékeket generálni, ha ezek az értékek már jelen vannak a szomszédos algoritmus szerkezetében. A kriptográfiai funkcióknak a fent említett egyéb kritériumoknak is meg kell felelniük. Nyilvánvaló, hogy mindig van valamilyen elméleti lehetőség a gyógyulásra forrás fájl hash alapján, különösen, ha van egy hatékony számítástechnikai eszköz. Ezt a forgatókönyvet azonban az erős titkosítási algoritmusoknak köszönhetően minimálisra kell csökkenteni. Így nagyon nehéz lesz kiszámítani egy hash függvényt, ha annak számítási erőssége megfelel a 2^(n/2) képletnek.

A kriptográfiai algoritmusok másik fontos kritériuma a hash változása abban az esetben, ha a kezdeti adattömböt javítják. Fentebb megjegyeztük, hogy a titkosítási szabványok érzékenységének 1 bitesnek kell lennie. Így ez a tulajdonság kulcsfontosságú tényező a fájlokhoz való hozzáférés megbízható jelszavas védelmének biztosításában.

Iteratív sémák

Vizsgáljuk meg most, hogyan lehet kriptográfiai kivonatoló algoritmusokat felépíteni. A probléma megoldásának leggyakoribb sémája az iteratív szekvenciális modell alkalmazása. Az úgynevezett kontrakciós függvény használatán alapul, amelyben a bemeneti bitek száma lényegesen nagyobb, mint a kimeneten rögzített bitek száma.

Természetesen a tömörítési függvénynek meg kell felelnie a szükséges kriptográfiai erősségi kritériumoknak. Az interaktív sémában a bemeneti adatfolyam feldolgozásának első művelete blokkokra van osztva, amelyek méretét bitben számítják ki. A megfelelő algoritmus adott számú bitből álló ideiglenes változókat is használ. Első értékként egy jól ismert számot használunk, míg a következő adatblokkokat a szóban forgó függvény értékével kombináljuk a kimeneten. A hash érték lesz az utolsó iteráció bitkimenete, amely figyelembe veszi a teljes bemeneti adatfolyamot, beleértve az első értéket is. A hashelés úgynevezett "lavinaeffektusa" biztosított.

Az iteratív sémaként megvalósított kivonatolás fő nehézsége az, hogy néha nehéz kivonatfüggvényeket létrehozni, ha a bemeneti adatfolyam nem azonos annak a blokknak a méretével, amelyre a kezdeti adattömb fel van osztva. De ebben az esetben a kivonatolási szabványba algoritmusokat lehet írni, amelyek segítségével az eredeti adatfolyam így vagy úgy bővíthető.

Egyes esetekben úgynevezett multi-pass algoritmusok is részt vehetnek az adatfeldolgozás folyamatában egy iteratív séma keretében. Egy még intenzívebb "lavinahatás" kialakulását javasolják. Egy ilyen forgatókönyv ismétlődő adattömbök kialakításával jár, és csak a második helyen áll a bővítés.

Blokk algoritmus

A tömörítési funkció egy blokk-algoritmuson is alapulhat, amellyel a titkosítást végrehajtják. Tehát a biztonsági szint növelése érdekében kulcsként használhatja azokat az adatblokkokat, amelyek az aktuális iteráció során hashelésnek vannak kitéve, és bemenetként az azt megelőző tömörítési funkció végrehajtása során kapott műveletek eredményét. . Ennek eredményeként az utolsó iteráció adja az algoritmus kimenetét. A hash biztonsága korrelál az alkalmazott algoritmus robusztusságával.

Azonban, mint fentebb megjegyeztük, figyelembe véve különböző fajták hash függvények, blokk algoritmusok gyakran együtt jár a nagy számítási teljesítmény használatának szükségességével. Ha ezek nem állnak rendelkezésre, előfordulhat, hogy a fájlfeldolgozási sebesség nem elegendő a hash függvények használatával kapcsolatos gyakorlati problémák megoldásához. Ugyanakkor a szükséges kriptográfiai erősség a forrásadatfolyamokkal végzett kis számú művelettel is megvalósítható, különösen az általunk vizsgált algoritmusok - MD5, SHA és orosz kriptográfiai titkosítási szabványok - alkalmasak az ilyen problémák megoldására.

Mi az a hash? A hash függvény az információ matematikai átalakítása egy bizonyos hosszúságú rövid sztringgé.

Miért van erre szükség? A hash függvény elemzését gyakran használják a fontos fájlok integritásának ellenőrzésére operációs rendszer, fontos programokat, fontos adatok. A monitorozás szükség szerint és rendszeresen is elvégezhető.

Hogyan történik? Először határozza meg, hogy mely fájlok sértetlenségét kell figyelni. Minden egyes fájlhoz egy speciális algoritmus szerint számítják ki a hash értékét, és az eredményt elmentik. A szükséges idő elteltével hasonló számítást végeznek, és az eredményeket összehasonlítják. Ha az értékek eltérnek, akkor a fájlban lévő információk megváltoztak.

Milyen jellemzőkkel kell rendelkeznie egy hash függvénynek?

• képesnek kell lennie tetszőleges hosszúságú adatok fix adatokká történő átalakítására;
• nyílt algoritmussal kell rendelkeznie, hogy a kriptográfiai erőssége vizsgálható legyen;
• egyoldalú legyen, vagyis ne legyen matematikai lehetőség a kiindulási adatok meghatározására az eredményből;
• "ellen kell állnia" az ütközéseknek, azaz nem szabad ugyanazokat az értékeket előállítania a különböző bemeneti adatokhoz;
• nem igényel nagy számítási erőforrásokat;
• a bemeneti adatok legkisebb változása esetén az eredménynek jelentősen meg kell változnia.

Melyek a népszerű kivonatolási algoritmusok? Jelenleg a következő hash függvények vannak használatban:

• A CRC a ciklikus redundancia kódja vagy ellenőrző összege. Az algoritmus nagyon egyszerű, a kívánt kimeneti hossztól függően számos változata van. Nem kriptográfiai!
• Az MD 5 egy nagyon népszerű algoritmus. Mint ő előző verzió Az MD 4 egy kriptográfiai funkció. A hash mérete 128 bit.
• Az SHA -1 szintén nagyon népszerű kriptográfiai funkció. A hash mérete 160 bit.
• A GOST R 34.11-94 egy orosz kriptográfiai szabvány a hash függvény kiszámítására. A hash mérete 256 bit.

Mikor használhatja a rendszergazda ezeket az algoritmusokat? Gyakran előfordul, hogy bármilyen tartalom, például a gyártó webhelyéről származó programok, zenék, filmek vagy egyéb információk letöltésekor egy bizonyos algoritmussal kiszámított ellenőrzőösszeg érték történik. Biztonsági okokból a letöltés után önállóan ki kell számítania a hash függvényt, és össze kell hasonlítania az értéket a webhelyen vagy a fájl mellékletében feltüntetett értékkel. Csinált már ilyet?

Mi a kényelmesebb a hash kiszámításához? Jelenleg számos ilyen segédprogram létezik, mind fizetős, mind ingyenesen használható. Nekem személy szerint tetszett a HashTab. Először is, a telepítés során a segédprogram fülként van beágyazva a fájl tulajdonságaiba, másodszor lehetővé teszi nagyszámú kivonatolási algoritmus kiválasztását, harmadszor pedig ingyenes privát, nem kereskedelmi használatra.

Mi az orosz? Amint fentebb említettük, Oroszországban létezik egy GOST R 34.11-94 kivonatolási szabvány, amelyet számos információbiztonsági eszköz gyártója széles körben használ. Az egyik ilyen eszköz a rögzítési és vezérlőprogram. kezdeti állapot Szoftver csomag"FIX". Ez a program az információbiztonsági eszközök használatának hatékonyságának ellenőrzésére szolgál.

FIX (2.0.1-es verzió) Windows 9x/NT/2000/XP rendszerhez

• Adott fájlok ellenőrző összegeinek kiszámítása az 5 implementált algoritmus egyikével.
• A szoftvercsomag kezdeti állapotának rögzítése és utólagos ellenőrzése.
• A szoftvercsomagok verzióinak összehasonlítása.
• Könyvtárak rögzítése és vezérlése.
• Meghatározott fájlok (könyvtárak) változásainak szabályozása.
• Riportok generálása TXT, HTML, SV formátumban.
• A termék 2013. június 01-ig rendelkezik az NDV 3 No. 913 szerinti FSTEC tanúsítvánnyal.

És mi a helyzet az ECP-vel? A hash függvény számításának eredménye a felhasználó titkos kulcsával együtt a kriptográfiai algoritmus bemenetére kerül, ahol a digitális aláírás kiszámításra kerül. Szigorúan véve a hash függvény nem része az EDS-algoritmusnak, de ezt gyakran szándékosan teszik, a nyilvános kulcsú támadások kizárása érdekében.

Manapság számos e-kereskedelmi alkalmazás lehetővé teszi a tárolást A titkos kulcs felhasználó a token privát területén (ruToken, eToken) anélkül műszaki megvalósíthatóság onnan kinyerni. Maga a token nagyon korlátozott memóriaterülettel rendelkezik, kilobájtban mérve. Egy dokumentum aláírásához nincs mód arra, hogy a dokumentumot magára a tokenre vigyük át, de nagyon egyszerű a dokumentum hash-jét átvinni a tokenre, és a kimeneten EDS-t kapni.

Hash táblázatok

Hash táblázat(kevert tábla, táblázat számított címekkel) van műveleteket támogató dinamikus halmaz elem hozzáadása, keresése és törlése, valamint speciális módszerek alkalmazása megszólítás.

A fő különbség a táblázatok és más dinamikus halmazok között az elem cím számítás kulcsérték szerint.

A hash-megvalósítás ötlete az, hogy egy nagy tömbbel való munka több kis készlettel való munkavégzésre redukálódik.

Például egy notebook. A könyv lapjait betűk jelölik. Egy betűvel jelölt oldal az adott betűvel kezdődő vezetékneveket tartalmazza. A vezetéknevek nagy halmaza 28 részhalmazra oszlik. Kereséskor a könyv azonnal megnyílik a kívánt betűre, és a keresés felgyorsul.

A programozási hash táblázatban- ez szerkezet adatok, amelyek párokat tárolnak (kulcs vagy index + érték), és amelyekkel három műveletet hajtanak végre: új pár hozzáadása, kulcs szerinti pár keresése és törlése.

Keresés a hash táblákban két szakaszban hajtják végre:

az első lépés - egy konvertáló hash függvény kiszámítása kulcs táblázatban keressen cím:

második lépés az ilyen kulcsok feldolgozása során felmerülő konfliktusok feloldásának folyamata.

Ha egy különböző értékeket táblázat kulcsait hash függvény generálja ugyanaz címeket, állítólag ez felmerül ütközés(konfliktus, összecsapás).

Hash függvények

A hash funkció fő célja, hogy megfeleljen a különböző kulcsok ha lehetséges különféle nem negatív egész számok.

Témák hash funkciója jobb, hogyan Kevésbé azonosértékeket generál.

A hash függvényt úgy kell megválasztani, hogy a következő tulajdonságok teljesüljenek:

a hash függvény a halmaz elemein van definiálva és veszi egész szám nem negatívértékek;

hash függvény könnyen kiszámítható;

A hash függvény eltarthat különféleértékek kb Ugyanolyan valószínű(ütközés-minimalizálás);

a rokonai érvértékek hash függvény veszi távoliértékeket egymástól.

Egy jó hash függvény felépítéséhez ismernie kell a kulcsok eloszlását. Ha ismert a kulcseloszlás, akkor ideális esetben a kulcssűrűségnek és a hash érték sűrűség-eloszlásának azonosnak kell lennie.

Hadd p ( kulcs ) - a kulcskérelmek elosztási sűrűsége. Ekkor ideális esetben a táblabeviteli kérések eloszlási sűrűsége az g ( H ( kulcs )) legyen olyan, hogy átlagosan az elemek száma, kat. ikerláncokban kellett átmenni, ez minimális volt.

Példa.

Legyen egy készlet kulcsok

{0, 1, 4, 5, 6, 7, 8, 9, 15, 20, 30, 40}

és engedje az asztal 4 bejárat.

Összeállíthat egy hash függvényt:

h(kulcs) = kulcs % 4 .

Akkor a következőket kapod címek bemenetekhez

{0, 1, 2, 3} táblázatok:

h(kulcs)

Belépési szám
Maximális lánchossz
% találat

3 0,5+1,5 0,25+0,5 0,08+1 0,17 ≈ 2,1 listaelem.

Példa más hash függvénnyel.

h(kulcs)

Belépési szám
% találat

Átlagosan ez fog tartani 4 1,5 0,25 = 1,5 listaelem.

Ha ez egy információkereső rendszer, akkor a keresési teljesítménye körülbelül 25%-kal nő.

Módszerek hash függvények létrehozására

Moduláris hash

Egy egyszerű, hatékony és gyakran használt kivonatolási módszer.

A táblázat mérete a következőképpen van kiválasztva egyszerű számok més a hash függvényt úgy számítjuk ki az osztály többi része:

h(kulcs) = kulcs % m

kulcs– a kulcs egész számértéke,

m- a hash értékek száma (kivonattábla bejegyzései).

Az ilyen függvényt ún modulárisés változik 0 előtt ( m - 1 ).

Moduláris hash függvény a C++ nyelven:

typedefintHashIndexType;

HashIndexTypeHash(intkulcs)

{ Visszatéréskulcs % m; }

Példa

kulcs = {1, 3, 56, 4, 32, 40, 23, 7, 41,13, 6,7}

Hadd m = 5

h(kulcs) = {1, 3, 1, 4, 2, 0, 3, 2, 1, 3, 1, 2}

A választás számít m.A kulcsok véletlenszerű elosztásához meg kell venni egyszerű szám.

Multiplikatív módszer

Hash függvény:

h(kulcs) =

0 < A < 1 egy állandó.

12 mod5 = 2 (a maradék a 12-t 5-tel osztva).

5,04 mod1= 0,04 (kiemelkedik tört rész)

Példa

kulcs = 123456

m = 10000

A = 0,6180339887499 = 0,618…

h(kulcs) = =

additív módszer

Arra használják vonalak változó hosszúságú (asztalméret m egyenlő 256).

{ HashIndexType h = 0;

míg (*str)

h += (*str)++;

Visszatérésh;

Az additív módszer hátránya, hogy a hasonló szavakat és anagrammákat nem különböztetik meg, pl. h(XY ) = h(YX )

additív módszer, ahol a kulcs egy karakterlánc. A hash függvényben a karakterlánc egész számmá alakul úgy, hogy összeadja az összes karaktert, és visszaadja a maradékot, miután elosztja m (általában asztalméret m = 256).int h(char *kulcs, int m) (int s = 0;while(*key)s += *kulcs++;return s % m;) ABCés taxi.Ez a metódus kissé módosítható, az eredményt a kulcskarakterlánc első és utolsó karakterének összegzésével kapjuk meg. 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és amc.

a hash függvény veszi a kulcsot, és abból kiszámítja a táblázatban szereplő címet (a cím lehet egy index a tömbben, amelyhez a láncok kapcsolódnak), azaz például megkaphatja a 3-as számot az "abcd" karakterláncból ", és az "efgh" karakterláncból megkaphatja a 7-es számot, majd a lánc első szerkezetét átveszi a hash-en, vagy a hash-en keresztül a keresés folytatódik a lánc mentén, amíg meg nem találja az "abcd"-t a struktúrák láncában a hash-ből , vagy az "efgh" a hash-ből származó struktúrák láncában található, amikor az "abcd "-vel rendelkező struktúrát megtaláljuk, a többi adatot a rendszer veszi és visszaadja, vagy általában az összeset (címét), így átveheti belőle a többi adatot, és létrejön a struktúrák lánca, mert sok különböző kulcsok, ugyanazzal a címmel rendelkeznek a táblázatban, azaz például az "abcd" hash függvénye 3-at, a "zxf9"-re pedig 3-at is visszaadhat, tehát egy láncba kapcsolódnak, amely a harmadik indexen lóg. tömb ......

A H tömb magát a kulcs-érték párokat tárolja. Az elembeillesztési algoritmus a H tömb celláit bizonyos sorrendben ellenőrzi, amíg meg nem találjuk az első szabad cellát, amelybe az új elemet írjuk.

A keresési algoritmus a hash tábla celláiban a beszúrással megegyező sorrendben keres, amíg vagy a kívánt kulcsú elemet vagy egy szabad cellát (ami azt jelenti, hogy nincs elem a hash táblában) nem talál.

XOR

Változó hosszúságú karakterláncokhoz használatos. A módszer hasonló az additív módszerhez, de hasonló szavakat különböztet meg. Abból áll, hogy az "exkluzív VAGY" műveletet egymás után alkalmazzák a karakterlánc elemeire

typedef unsigned char HashIndexType;

unsigned char Rand8;

HashIndexType Hash(char *str)

( előjel nélküli karakter h = 0;

míg (*str) h = Rand8;

Visszatérésh; }

Itt Rand8 – egy táblázat 256 nyolcbites véletlen számokból.

asztal mérete<= 65536

typedef unsigned short int HashIndexType;

unsigned char Rand8;

HashIndexType Hash(char *str)

( HashIndexType h; előjel nélküli karakter h1, h2;

if (*str == 0) 0-t ad vissza;

h1 = *str; h2 = *str + 1; str++;

míg (*str)

( h1 = Rand8; h2 = Rand8;

str++; )

h = ((HashIndexType)h1<< 8) | (HashIndexType)h2;

vissza h % HashTableSize )

Egyetemes kivonatolás

Arra utal véletlen során egy hash függvény kiválasztása valamelyik halmazból teljesítés programokat.

Ha a szorzómódszerben használjuk mint DE utósorozat véletlenértékeket fix szám helyett, egy univerzális hash függvényt kap.

Azonban a véletlen számok generálására is ideje lesz nagy.

Használható álvéletlen számok.

// pszeudo-véletlenszám-generátor

typedefintHashIndexType;

HashIndexTypeHash(char*v, int m)

( int h, a = 31415, b = 27183;

for(h = 0;*v != 0; v++, a = a*b % (m - l))

h = (a*h + *v) % m;

return(h< 0) ? (h + m) : h;