Circular bog'liq ro'yxat

2.2. Elektron hújjet almasiiuvida kesh-funktsiyalar klassifikatsiyasi.
Kriptografik qosımshalarda giltli xesh-funktsiyalarına tómendegi tiykarǵı talaplar qóyıladı.
-maǵlıwmattıń dereksi qay jerde ekenligin biliwdiń múmkin emesligi;
-ózgertiwdiń múmkin emesligi;
Dáslepki talapda tuwrı xesh-funktsiya ma`nisin xabar jıynaw (podbor), payda etiwdiń joqarı quramalılıǵın belgileydi. Ekinshi talap bolsa xesh- funktsiyalar ma`nisi málim bolǵan berilgen xabar ushın basqa tuwrı xesh- funktsiyalar ma`nisin xabardı saralawdıń, tabıwdıń joqarı quramalıliligini belgileydi.
Geyde bul ayrıqshalıqlar birlesedi hám kúshli ózgeshelik payda etedi, bul esaplaw tuwrılıǵı ózgesheligi bolıp tabıladı. Bul talap xesh-funktsiyası ma`nisi
málim bolǵan {xl,... Xt} xabarlar kompleksi ushın taǵı bir sonday tuwrı bahalı x, x=xi (i=ll…t) xabardı payda etiwdiń quramalılıǵın anıqlaydı, yaǵnıy h (x) =h (xi), ie{l,... t}.
Aytıp ótiw kerek, bul erda hám balshıq jerde pát berilip atırǵan “ quramalılıq” sonday esaplaw quramalılıǵın ańlatadıki, bul halda qurılıp atırǵan másele sheshimi ushın esaplaw texnikasınan paydalanıw real waqıtta múmkin emes.
Giltli funktsiyalardan táreplerde bir birine isenim bolsaǵana qollanıladı hám olarda ulıwma jasırın gilt bolıwı múmkin. Bunday shártli jaǵdayda sistemadan xabardı alǵanlıqtan tabıw yamasa onı ózgertiwden qorǵawdı támiyinlew talap etilmeydi. Shuning ushın giltli xesh-funktsiyalardan kolliziyalarga sabırlılıq talap etilmeydi.
Ádetde xesh-funktsiyalarǵa hújim imitatsiyada, yaǵnıy derekten chikkan xabarlar bos kanaldan uzatılǵanda ámelge asıriladı.
Sonı da aytıw kerek, esaplaw sabırlılıǵı ózgeshelikinen xesh-funktsiyada ko’llanilayotgan giltni anıqlaw múmkin emesligi túsip qaladı, sebebi gilt ma`nisi qálegen maǵlıwmatlar kompleksi ushın xesh-funktsiyalar ma`nisin esaplaw imkaniyatın beredi. Shu menen birge qayta tastıyıqlaw nadurıs, sebebi xesh-funktsiyalar ma`nisin tolıq tekseriw járdeminde bilip alıw birpara jaǵdaylardaǵana múmkin.
Mısal retinde bir qádemli qısıwshı funktsiya kurishidagi keń tarqalǵan
FK (x, N) =Ek (x © N)
funktsiyanı qaray shıǵamız, bul erda EK – bloklı shifrlaw algoritmlı.
M xabardıń h (M) ma`nisin esaplaw ushın M xabar p – bitli bloklar kurinishiga keltiriledi, M1 M2,... Mn. Eger bul halda xabar uzınlıǵı blok uzınlıǵına márteli bolmasa, halda sungi blok qandayda bir usıl menen toltırıp alınadı. Xesh-funktsiyalar ma`nisin esaplaw algoritmı tómendegi kóriniste:
Np=0,
HI=Ek (Ml®Hi-l), i=l,.. ., N, (2)
h (M) =HN.
Bul algoritm arnawlı bloklı shifrlaw rejimine uyqas túsedi, biraq ayırmashılıǵı sonda, retinde H1 N2.., Np pútkil shifr tekst emes, bálki onıń sońǵı uffe alınadı. Bunday rejim GOST 28147-89 da imitovstavkani tańlaw rejimi dep ataladı.
Giltli xesh-funktsiya jaratıwdıń taǵı bir hasası giltsiz xesh-funktsiya bolıwı múmkin. Bul túrde xesh-funktsiya ma`nisin esaplaw ushın gilt baslanǵısh xabarǵa qistiriladi.
Eger giltni baslanǵısh xabardıń aqırı yamasa basına qosılsa, ol halda bul birpara jaǵdaylarda xabardı ózgertiwdi ámelge asırıwǵa sebep bolatuǵın kemshilikke alıp keliwi múmkin.
Mısalı, gilt hk (X) =h (K, X) formulaǵa tıykarlanıp xabar basına qosılsin. Eger h funktsiya (1) formula boyınsha bir qádemli qısıwshı funktsiyaǵa tıykarlanıp qurılǵan bolsa, ol halda anıq bahalar M hám H=h (k, m) lar boyınsha qálegen xabarlar ushın bul funktsiya ma`nisin esaplaw múmkin. Xabar M’ menen shuǵıllanǵan qálegen (M, M’) xarakteristikaında bolıwı múmkin. Bul funktsiyanıń esaplanıwı proceduranıń iterativligi menen tusintiriledi, yaǵnıy N’ – h (k, M, M’) bahanı esaplaw ushın k giltni biliw talap etilmeydi, “ orali? “ ma`nisiniń ózi etarli, sol sebepli bunday funktsiya ózgertiwlerge sabırlı emes.
Bunday kamlichiliklarning aldın alıw eń jaqsı jolı, xabarǵa gilt bir ret emes eki ret qoyılıwı bolıp tabıladı.
H=h (k, y, M, k),
H=h (k, ol I, h (k, u2, M)),
bul erday, yi hám u2- p blok uzınlıǵına márteli ulchamdagi k giltga? O’shimcha.
Ani? Giltsiz xesh-funktsiya h ushın bunday jantasıw nátiyjeli? Isoblanadi hám xesh-funktsiya giltiga? Ujumlarga sabırlı funktsiya jaratıw imkaniyatın beredi. Bul usıl kemshiligi xesh-funktsiya? Iymati uzınlıǵında. Pútinlikti tekseriwde ádetde p – xesh-funktsiya? Iymati 32-64 shegara? Isoblanadi, autentifikatsiya ushın bolsa p>128 shárt atqarılıwı kerek.
Juwmaq qilib aytqanda, bloklı shifrlawdı yamasa giltsiz xesh-funktsiyanı? O’llashga tiykarlanmagan giltli xesh-funktsiyalar barki, olar zamanagóy jeke kompyuterlerde nátiyjeli ámelge asıriladı. Mısal retinde MAA (Message Anthon Arcator Algothm) algoritmınan paydalanatuǵın ISO 8731-2 standarta menen tasdi? Langan giltli xesh-funktsiyanı keltiriw múmkin.
Giltsiz xesh-funktsiyalardan ádetde? Úyindegi qásiyetleri bolıwı talap etiledi:
1) bir tárepke jóneltirilganlik
2) kolliziyaga sabırlılıq
3) ekinshi nusqanıń payda bolıwına sabırlılıq
Shu ayrıqshalıqlarǵa iye bolǵan giltsiz xesh-funktsiyalar yu? Ori quramalılıqqa iye boladı.
Mısalı, CRC-32 xesh-funktsiya, ózinde qadaǵalaw summasın sa? Laydi hám chizi? Li akslantirish? Isoblanadi, sol sebepli yu? Oridagi ayrıqshalıqlardan qandayda-birın? Oni? Tirmaydi.
Giltsiz xesh-funktsiyalardan paydalanıw yu? Orida? Aralgan bloklı shifrlaw algoritmına tiykarlanǵan (2) funktsiyada? Aralgan edi.
2) ózgeshelikti kanoatlantiruvchi xesh-funktsiyaǵa uffer jaratıw ushın gk I =Ek (X) ®X formulaǵa tiykarlanǵan funktsiyanı? Araymiz, bul formulada Ek- bloklı shifrlaw algoritmı.
Bunday funktsiya eki argument boyınsha? Am bir tárepli jóneltirilgen? Isoblanadi. Shuning ushın bul formula tiykarında (1)? Oida boyınsha xesh- funktsiyalar ani? Lanishi múmkin, bul processda bolsa bir? Adamli si? Uvchi funktsiyanı? Úyindegi formulalardan birinen ani? Lash múmkin:
f (x, H) =EH (X) @X
yamasa
f (x, H) =Ex (H) @H
Funktsiyalardan birinshisi Rossiya standart xesh-funktsiyasına tiykarlanǵan, ekinshisi bolsa amerikanıń SHA standartına tiykarlanǵan.
1-tasdik. Eger h xesh-funktsiyası bir? Adamli si? Uvchi f funktsiyaǵa (1)? Oida boyınsha jaratılǵan bolsa, ol? Olda f funktsiyanıń kolliziyaga sabırlılıǵı kelip chikadi.? A? i? atdan? Am, eger f funktsiya kolliziyaga iye bolsa, ol? Olda qandayda bir i? adamda f funktsiyanıń? Am kolliziyasi ámeldegi boladı. (f (Xi, X2) funktsiya kolliziyasini ani? Lashda bir ózgeriwshili funktsiya sıyaqlı? Arash kerek, bunda X/, X2 ózgeriwshiler bir kiretuǵın vektorǵa atlar tartıp júretuǵın tramvaytenatsiya? Ilinadi).

3. 
   hám 2) ayrıqshalıqlar ortasında óz-ara bo? Li? Lik bar.
   

2- tasdik. Eger xesh-funktsiyalar kolliziyaga sabırlı bolsa, ol? Olda bul funktsiya ekinshi nusqanıń payda bolıwına? Am sabırlı.
3- tasdik. Kolliziyalarga sabırlı xesh-funktsiyalar bir tárepleme bolıwı shárt emes.
Mısal retinde h (x) =x si? Maydigan funktsiyanı keltiriw múmkin, bul funktsiya kolliziyalarga hám ekinshi nusqanıń tabılıwı sabırlı, biraq bir tárepke yunalgirilgan? Isoblanilmaydi.
Si? Uvchi xesh-funktsiyalar uffer retinde
h (x) – (1 – x), eger x dıń bitli uzınlıǵı n ga teń bolsa,
h (x) – (0 – g (x)), eger x dıń bitli uzınlıǵı n den úlken bolsa
shárt menen ani? Lanadigan ci? Uvchi funktsiyanı? Arash múmkin, bul erda g (x)- kolliziyaga sabırlı bolǵan n bitli ci? Uvchi funktsiya. Bunnan tash? uff, h funktsiya kolliziyaga hám ekinshi nusqanıń taplilishiga sabırlı, biraq bir tárepke jóneltirilgen emes.
4- Tasdik. H:x~^y – xesh-funktsiya bulsin, bul erda| x|>2[u|. Ol? Olda eger h funktsiyaǵa shaqırıqtıń nátiyjeli algoritmı bolsa, ol? Olda h
funktsiyanıń kolliziyasini ½ den úlken e? timol menen tabıwdıń algoritmı bar.
Tastıyıq. Tosınarlı x- xabardı tańlaymiz. Y=h (x), x’=h? 1 (ol)? Isoblaymiz hám x hám x’ salıstırıladı. Bul algoritm r>1/2 kurinishdagi extimolga iye kórsetiledi. E? timol muvaffa? Iyati retinde x den far? Li x ni? Urıw túsiniledi.
Xi=XiOl... Uxm – bul erda X klasslarga bólingen bolıp,? Ar bir klass birdey xesh-funktsiya? Iymatiga iye bolǵan xabarlar bolsın. Kórinip turıptı, olda,
m<\u\. Bul erda? Úyindegi munasábet orınlı :
I m I t
R-T. ZSF~Z< p=” “ ><>
I L I /=1 xeX/ I l I /=1
\X\ -\x\ 2
Tasdi? Tastıyıqlandi.
Kóriw múmkin, bir tárepleme funktsiya ushın onıń hákisin tabıwdıń quramalılıǵı 0 (2”) shama menen ba? Olanadi. Shu menen birge kolliziyani? Idiruv 0 (2 p2) menen ba? Olanadi, sebebi bul? Olatda “ tu? Ilgan kun” paradoksiga tiykarlanǵan? Ujum? O’llanilishi múmkin.
Bloklardı akslantirishga tiykarlanǵan qandayda bir algoritmǵa tiykarlanǵan xesh- funktsiyalarǵa uffer karaymiz.
Ek – bloklı shifrlaw algoritmın menen, n-blok ulchami, / - gilt ulchami hám G – qandayda bir tiykarlantirish. EK algoritmǵa tıykarlanıp? Urılǵan? Úyindegi bir kadamli si? Uvchi funktsiyanı karaymiz.
a) f (x, N) =EX (N) ®N (Devis – Meyer);
b) f (x, N) =Eg (H) (X) ®X (Memuac – Meyer – Oseas);
v) f (x, N) =ES (n/x) ®x®N (Miaguchi – Prinel’);
Qálegen (1)? Oidaga tiykarlanǵan bir? Adamni si? Uvchi funktsiyalardıń? Iymati blok razmeriga teń bolǵan n uzınlıqtaǵı uffer esaplanadi.
Eger bul shama etarli bolmasa, onı úlkenlestiriw múmkin, almastırıwda f funktsiyanı f ga kiymatlarini eki ret úlkenlashtirib ózgertiw kerek. Bunı f funktsiyanı 2 ret? Ayta isletip hám bunda? Úyindegi formuladan paydalanǵan? Olda uffer almastıruvni? O’llab beriwi múmkin.
F (x, Hh N2) = K (fix, H,), f (x, H2)),
bul erda p qálegen a, b, c, d yarım bloklardan shólkemlesken bolıwı múmkin jáne bul erda p ((a, ‘), (c, d)) = (a, d, c, b). Bunday sxemadan paydalanılǵan konstruktsiya bir kiymatli MD-2 funktsiyası bolıp tabıladı.
Giltsiz xesh-funktsiyalarǵa uffer retinde MD-4, MD-5 hám SHA sıyaqlı algoritmlardı keltiriw múmkin. Bul funktsiyalar p uzınlıǵı daǵı bloklar menen isleydi, MD4 ushın n-128, MD5 hám SHA xesh-funktsiyalarda bolsa p=160.
Kórsetilgen algaritmlar 32-razryadlı jeke kompyuterlerde nátiyjeli ámelge asıriladı.
Olardan paydalanıwda baslan? Ish M xabar t=512 bıyt O’zunlikdagi bloklarǵa bólinedi. Sońǵı blok aqırına 10... O kombinatsiyasınan ibarat ketma- ketlik? O’shilib 448 bitga keltiriledi,? Alǵan 64 bıyt bolsa xabardıń bitli uzınlıǵı esaplanıp, ol sunggi? Osil? Ilingan 448 bitga? O’shiladi. Shu jol menen 512 bitli sunggi blok qáliplestiredi. Keyininen (1) proceduraǵa tıykarlanıp xesh-funktsiya? Iymati esaplanadi,? Isoblashda 1-? Adamli si? Uvchi f (X, H) =Ex (H) ®H formula menen berilgen funktsiyadan paydalanıladı, bul erda x – t=512 bitli xabar uffe uzınlıǵı, N – p bitli bloklar, Ex – bloklardı akslantirish tuplami. Baslanǵısh uffer? Iymati Ex hákisleniwdiń xarakteristikaında ani? Lanadi.
GOST 34. 11-94 xesh-funktsiyasında p=t-512? Iymat? Abul? Ilingan. Hj=F (X, Hi-1)? Iymatlar izbe-izligin? Isoblashda paydalaniletuǵın bir? Adamli si? Uvchi funktsiya? Ar biri 256 bitli giltler menen isleytuǵın turtta paralel’ isleytuǵın bloklı shifrlaw sistemasına tiykarlanǵan. Giltlerdiń? Ar birine uyqas? Olda baslan? Ish X xabar hám Hi? Iymat bloklarǵa bo? Li? Túrde qandayda bir chizi? Li funktsiya járdeminde esaplanadi. Hi? Iymat baslan? Ish X xabar uffe hám Hi? Iymatga tiykarlanǵan chizi? Li funktsiya, N ni? Isoblash procesi Mi, M2,-Mn bloklar izbe-izliklaridagi? Úyindegi formulaǵa tiykarlanǵan yaǵnıy eki kadam? O’llaniladi.
H=h (m) =f (Z® MN, f (L, HN)),
Bul erda Z –barlıq xabar bloklarınıń modul boyınsha summası, L-xabar uzınlıǵı.