Mirzo ulug’bek nomidagi

6.4-tasdiq.

h : X  У
xesh funksiya berilgan bo‘lib,
Х  2У
bo‘lsin.

Agarda h funksiyaning teskarisini topishning samarali algoritmi mavjud bo‘lsa, u

holda h funksiyaning kolliziyalarini muvaffaqiyatli topishning ehtimoli

katta bo‘lgan ehtimoliy algoritmi mavjud bo‘ladi.

¹ dan
2

Bir tomonlama funksiya uchun xesh qiymatlari teng bo‘lgan ikkita ma’lumotni tanlash yoki xesh qiymatlari teng bo‘lgan ikkita ma’lumotni qidirish

murakkablik darajasi
О(2ⁿ )
bilan baholanadi. SHu bilan birga kolliziyani qidirish

murakkablik darajasi
О(2^{n / 2} )
bilan baholanadi, chunki bu holatda “tug‘ilgan kun”

paradoksiga asoslangan hujumni qo‘llash mumkin.

Quyida bloklab shifrlash algoritmlari asosida qurilgan xesh funksiyalarga misollar ko‘rib o‘tiladi.

k
E <sup>-bloklab shifrlash algoritmi, n -blokning uzunligi, l -kalit uzunligi va G


uzunligi</sup> n ^{bo‘lgan vektorga l uzunlikdagi vektorni mos qo‘yuvchi biror}

k
^{akslantirish bo‘lsin.} E ^{-bloklab shifrlash algoritmi asosida qurilgan quyidagi bir}

qadamli siquvchi funksiyalar ko‘riladi:

1. 
   f (x, H )  E_x (H )  H
   
2. 
   f (x, H )  E_{G ( x)} (x)  x
   

^v) f (x, H )  E_{G ( x)} (x)  x  H
(Devis-Meyer); (Matias-Meyer-Oseas); (Miaguchi-Prinel).

Bu keltirilgan bir qadamli siquvchi funksiyalardan foydalanib qurilgan ^{ixtiyoriy xesh funksiya qiymatining uzunligi o‘lchami} n ^{bo‘lgan blok uzunligiga teng vektor bo‘ladi. Agar bu uzunlik etarli bo‘lmasa, u holda bir qadamli} f ^{funksiyani uzunligining o‘lchami undan ikki marta katta bo‘lgan} f ^{ funksiya bilan almashtirish mumkin. Buni masalan,} f ^{funksiyani ikki marta qo‘llash va undan} keyin yarim bloklarni aralashtirish bilan quyidagi formula asosida amalga oshirish mumkin:
f ^(x, H₁ , H₂ )   ( f (x, H₁ ), f (x, H₂ )) ^,

bu erdagi  funksiya ixtiyoriy
a,b, c, d ^{-yarim bloklarni}
 ((a,b),(c, d))  (a, d,c,b)

qoida bo‘yicha almashtiradi. Bunday usul Matias-Meyer-Oseas sxemasidan foydalanib, MDC-2 bir qadamli funksiyasini qurishda qo‘llanilgan.

Umuman olganda bloklab shifrlash algoritmlaridan foydalanilib quriladigan kalitsiz xesh funksiyalarda blok uzunligi xesh qiymat uzunligiga teng bo‘ladigan sxemalar mavjud. Quyida ushbu tipdagi algoritmlarning umumiy sxemasi keltirilgan:

0 H
H  I ^,

i A
H  E (B)  C ^.

^{Bu erda} I _H
-boshlang‘ich tasodifiy qiymat, A, B va C lar
M , H ,(M  H ) ^ga

i i1 i i1

i
^{teng bo‘lishi mumkin,} M
-kiruvchi blok,
Н ^{-iteratsiyaning i – qadami. Ushbu}

i
algoritmlarning ko‘rinishi quyidagicha:

1.	Нi = ЕHi-1(Мi) Мi
2.	^Нi ^=^ЕHi-1 ^(^Мi^^Нi-1^)^^Мi ^Нi-1
3.	^Нi ^=^EHi-1 ^(^Мi^)^Нi-1 ^Мi
4.	^Нi^=^ЕHi-1 ^(^Мi ^EНi-1^)^Мi
5.	^Нi ^=^ЕMi ^(^Нi-1^)^Нi-1
6.	Нi = ЕMi (МіНi-1) МiНi-1
7.	^Нi ^=^ЕMi ^(^Нi-1^)^^Мi ^Нi-1
8.	^Нi ^=^EMi ^(^Мi ^Нi-1^)^Нi-1
9.	^Нi ^=^ЕMi Hi-1^(^Мі^)^Мi
10.	^Нi ^=^ЕMi Hi-1^(^Нi-1^)^Нi-1
11.	^Ні ^=^ЕMi Hi-1^(^Mi^)^Ні-1
12.	^Нi ^=^ЕMi Hi-1^(^Нi-1^)^Мi

Boshqa kalitsiz xesh funksiyalarga MD4, MD5 va SHA xesh funksiyalari misol bo‘la oladi. Bu algoritmlar 32 razryadli EHMlarda samarali qo‘llanilishga mo‘ljallanib, maxsus loyihalashtirilgan algoritmlardir.

Bu algoritmlardan foydalanilganda berilgan M ma’lumot uzunligi
т  512
bit

bo‘lgan bloklarga ajratiladi. Oxirgi blok ma’lumot oxiriga blokning uzunligi 448 bit bo‘lguncha 1000....000 kombinatsiyani qo‘shish bilan hosil qilinadi, undan

keyin ma’lumot uzunligini ifodalovchi 64 bitli kombinatsiya qo‘shiladi. Keyin
f (x, H )  E_H (H )  H ^{formula bilan berilgan bir qadamli siquvchi funksiyadan}
foydalanib, (5.1) tartibotga (protseduraga) asosan xesh qiymat hisoblanadi. Bu erda

x – uzunligi
т  512
^{bit bo‘lgan ma’lumot bloki, N – n bitlik blok,} Е
-bloklar

х

х
to‘plamidagi biror akslantirish. Boshlang‘ich vektorning qiymati aniqlashda beriladi.
Е ^{akslantirishni}

GOST R 34.11-94 xesh funksiya standartida
n  т  512
qiymatlar qabul

qilingan.
H_i 


f (x_i , H_i1 )
qiymatlarni ketma-ket hisoblashda foydalaniladigan bir

qadamli
f (x, H)
siquvchi funksiya har biri 256 bit kalitga ega bo‘lgan va 64 bit

uzunlikdagi bloklar bilan amallar bajaruvchi to‘rtta parallel ishlovchi bloklab shifrlash sxemasi (GOST 28147-89) negizida qurilgan. Har bir kalit mos ravishda

i
^kiruvchi х
ma’lumot bloki va
^Hi 1
qiymatning biror chiziqli funksiyasi

ko‘rinishida hisoblanadi.
H ^{qiymat kiruvchi}
х ^{ma’lumot bloki va
H}i 1
qiymat

i

i

N
^{shifrlanishi natijasining chiziqli funksiyasi bo‘ladi.} H
bloklar ketma-ketligi uchun hisoblagandan keyin
qiymatni
M₁ , M ₂ ,…, M _N

H  h(M ) 
f (Z  M _N , f (L, H_N ))

formulaga asosan yana ikki qadam hisoblash bajariladi. Bu erda Z – ma’lumot barcha bloklarining modulь ikki bo‘yicha yig‘indisi, L – ma’lumot uzunligi.
Hozirgi kunda ko‘plab davlat standartlari xesh funksiyalarining algoritmlari kalitsiz xesh funksiya algoritmlaridir. Bunga misol qilib Rossiyaning GOST P 34.11-94 xesh funksiya davlat standartini, AQSHning federal standarti FIPS PUB 180 da keltirilgan SHA-0, FIPS PUB 180-1 da keltirilgan SHA-1, FIPS PUB 180-2 da keltirilgan SHA-256, SHA-384, SHA-512 xesh funksiyalarini, Belarusь Respublikasining xesh funksiya davlat standarti STB 1176.1 – 99 ni, AQSHning federal standarti SHA turidagi xesh funksiyalarni yaratishga asos bo‘lgan MD turidagi xesh funksiyalar va ularning modifikatsiyalari MD2, MD4 va MD5 xesh funksiyalarini (AQSHning federal standarti aynan MD5 xesh funksiyasi asosida ishlab chiqilgan), Evropa Hamjamiyatining RACE dasturi doirasida MD4 asosida ishlab chiqilgan RIPE-MD va uning modifikatsiyalari RIPEMD-160, RIPEMD-

256 va RIPEMD-320 xesh funksiyalarini, MD5 asosida ishlab chiqilgan HAVAL xesh funksiyasini va yuqoridagi xesh funksiyalar algoritmlaridan farq qiluvchi algoritmga ega bo‘lgan TIGER xesh funksiyasini keltirish mumkin [14, 29, 30, 31,
34-37].
Autentifikatsiya atamasi axborot-kommunikatsiya tarmoqlarida ma’lumotlar almashinuvi sub’ektlarining haqiqiylikni aniqlashini bildiradi. Bu ma’lumot almashishdagi barcha aspektlarga ta’lluqli bo‘lib, aloqa seansining, tomonlarning, ma’lumotning haqiqiyligini bildiradi. Bu aloqa tarmog‘i orqali uzatilgan ma’lumot manbai va mazmuni jihatidan, ma’lumotning yaratilgan vaqti hamda jo‘natilgan vaqti jihatidan tekshirganda haqiqiy bo‘lishini anglatadi.
Ma’lumot to‘laligi – ma’lumot yaratilgandan keyin uni saqlashda va uzatishda uning begonalar tomonidan o‘zgartirilmaganligiga ishonch hosil qilishni bildiradi. Ma’lumotni o‘zgartirish deganda odatda unga qo‘shimchalar qo‘shish, tushirib qoldirish, o‘zgartirish va ma’lumot qismlarining o‘rnini almashtirish tushuniladi.
Ma’lumotning manbaini autentifikatsiya qilish – qabul qilingan elektron hujjat haqiyqiy manba tomonidan yaratilganining tasdig‘ini olishdir. Bunda hujjat yaratilgan vaqt va elektron hujjatning yagonaligini tekshirish talab qilinmaydi. Hujjat yagonaligining buzilishi deganda, uni qaytadan uzatish yoki undan qaytadan foydalanish tushuniladi.
Ma’lumotning haqiqiyligi va ma’lumot manbaini autentifikatsiya qilish tushunchalari bir-biri bilan chambarchas bog‘liqdir. Haqiqatan ham, agar ma’lumot modifikatsiya qilingan bo‘lsa, uning manbai ham o‘zgaradi. Agar manba aniqlanmagan bo‘lsa, to‘lalik masalasini hal qilib bo‘lmaydi.
Endi xesh funksiyani axborot-kommunikatsiya tizimlarida qo‘llash sxemalari qarab chiqiladi:
a) A→V: E_K[M||H(M)] (5.1 a) – rasm)
-maxfiylikni ta’minlaydi (K kalit faqat A va V tomonlarga ma’lum).
-to‘lalikni ta’minlaydi (N(M) kriptografik himoyalangan).
b) A→V: M|| E_K[H(M)] (5.1 b) – rasm)
-to‘lalikni ta’minlaydi (N(M) kriptografik himoyalangan).
v) A→V:M||E_Y[H(M)] (5.1 v) – rasm)
-to‘lalikva raqamli imzoni ta’minlaydi (N(M) kriptografik
himoyalangan hamda E_Y[H(M)] ni faqat A tomon hosil qilishi mumkin).
g) A→V: E_K[M||E_Y[H(M)]] (5.1 g) – rasm)
-to‘lalikva raqamli imzoni ta’minlaydi.
-maxfiylikni ta’minlaydi (K kalit faqat A va V tomonlarga ma’lum).
d) A→V: M||H(M||S) (5.1 d) – rasm)
- to‘lalikni ta’minlaydi (S faqat A va V tomonlarga ma’lum).
e) A→V: E_K[M||H(M||S)] (5.1 e) – rasm)
-maxfiylikni ta’minlaydi (K kalit faqat A va V tomonlarga ma’lum).
-to‘lalikni ta’minlaydi (S faqat A va V tomonlarga ma’lum).