Respublikasi axborot texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot - bet 48

95
Keyingi holatda parol “tuz” yordamida xeshlangan bo’lsin. Bunda,
𝑠𝑠
𝑖𝑖
xeshlangan parol
𝑦𝑦
𝑖𝑖
ni hisoblashda foydalanilgan bo’lsin. U holda, buzg’unchi
ℎ
(
𝑆𝑆
0
,
𝑠𝑠
0
)
ni hisoblaydi va
𝑦𝑦
0
bilan taqqoslaydi, u
ℎ
(
𝑆𝑆
0
,
𝑠𝑠
1
)
ni
hisoblaydi va
𝑦𝑦
1
bilan
taqqoslaydi,
ℎ
(
𝑆𝑆
0
,
𝑠𝑠
2
)
ni hisoblaydi va
𝑦𝑦
2
bilan taqqoslaydi va tarzda davom etib,
hisoblash
ℎ
(
𝑆𝑆
0
,
𝑠𝑠
1023
)
gacha davom etadi. Shundan so’ng, ushbu jarayon
𝑆𝑆
1
,
𝑆𝑆
2
va
boshqalar uchun davom ettiriladi. Umumiy holda esa, buzg’unchi
tomonidan
bajariladigan ishlar hajmi birinchi holatdagi kabi 2
55
ga teng bo’ladi.
Bu hisoblashlar parolni xeshlashda “tuz” dan
foydalanishning afzalligini
ko’rsatadi. Biroq, amalda uchramasa ham buzg’unchining eng keng tarqalgan
parollar lug’atidan foydalanmaganini ham inobatga olish zarur.
4-holat.
Ushbu holatda buzg’unchi o’zining eng
keng tarqalgan parollar
lug’atidan foydalanib 1024 ta paroldan iborat parollar faylidan kamida bitta parolni
topishning o’zi yetarli bo’lgan shartni ifodalaydi. Dastlab, parollar faylidagi 1024 ta
paroldan bittasining buzg’unchi lug’atidagi paydo bo’lish ehtimoli
1
−
(
3
4
)
1024
≈
1
ga teng bo’ladi. Shuning uchun, fayldagi parollar buzg’unchining lug’atida
bo’lmagan holatni inobatga olish xavfsizdir.
Agar parollarni xeshlashda “tuz”dan foydalanilmagan bo’lsa, buzg’unchi
osonlik bilan o’zining lug’atidagi parollarni xeshlaydi va fayldagi 1024 parolning
xesh qiymati bilan taqqoslaydi. 1024 ta paroldan kamida bittasini lug’atda
mavjudligini aniqlashning o’zi yetarli bo’lgan uchun, buzg’unchi tomonidan
bajariladigan ish 2
20
ga teng. Biroq, buzg’unchi tajribasiga ko’ra ushbu bajariladigan
ishni kamaytirishi mumkin. Shunga qaramay, buzg’unchining lug’atida parollar
faylidagi kamida bitta parol bo’lishi mumkin deb faraz qilaylik. Natijada,
buzg’unchi o’zi kutgan parollar faylidagi bitta parolni aniqlashi uchun o’zining
lug’atidagi parollarning yarmini, 2
19
xeshlashi talab etiladi. Uchinchi holatda
bo’lgani kabi, har bir xeshlash amali 2
10
ta taqqoslashni talab etadi va shuning uchun
buzg’unchidan bajarishi
kutiladigan ish hajmi
2
19
2
10
�
= 2
9
ga teng.
Agar parolni xeshlashda “tuz”dan foydalanilmagan va lug’atdagi parollarni
xeshlash oldindan amalga oshirilgan bo’lsa, parollar faylidagi ixtiyoriy parolni
96
topish uchun qo’shimcha ish talab etilmaydi. Ya’ni, buzg’unchi parollar faylidagi
parollarni o’zining parollar lug’atining oldindan hisoblangan qiymatlari bilan
solishtiradi va natijada o’zining lug’atida mavjud bo’lgan parol aniqlanadi.
Endi amalda bo’lish ehimoli yuqori bo’lgan holat: parollar faylidagi xesh
qiymatlar “tuz”dan foydalangan va buzg’unchi eng keng tarqalgan parollar
lug’atidan foydalangan bo’lsa,
𝑦𝑦
0
,
𝑦𝑦
1
, … ,
𝑦𝑦
1023
– fayldagi xeshlangan parollar va
𝑠𝑠
0
,
𝑠𝑠
1
, … ,
𝑠𝑠
1023
– ushbu parollarga mos foydalanilgan “tuz” bo’lsin. Agar,
buzg’unchi foydalanayotgan parollar lug’ati
𝑑𝑑
0
,
𝑑𝑑
1
, … ,
𝑑𝑑
2
20
−1
bo’lsa, u
ℎ
(
𝑑𝑑
0
,
𝑠𝑠
0
) ni
hisoblaydi va
𝑦𝑦
0
bilan taqqoslaydi. Shu tartibda
ℎ
(
𝑑𝑑
1
,
𝑠𝑠
0
)ni hisoblaydi va
𝑦𝑦
0
bilan
taqqoslaydi,
ℎ
(
𝑑𝑑
2
,
𝑠𝑠
0
) hisoblaydi va
𝑦𝑦
0
bilan taqqoslaydi va h. Shunday qilib,
buzg’unchi dastlab
𝑦𝑦
0
ni parollar lug’atidagi barcha parollar uchun taqqoslaydi. Bu
holat
har bir
𝑦𝑦
𝑖𝑖
uchun amalga oshiriladi.
Agar
𝑦𝑦
0
parol lug’atda mavjud bo’lsa (1/4 ehtimollik bilan), u holda
buzg’unchi uni 2
19
ta hisoblashdan so’ng aniqlaydi. Aks holda (3/4 ehtimollik bilan),
buzg’unchidan 2
20
ta hisoblash talab etiladi. Agar buzg’unchi
𝑦𝑦
0
parolni lug’atdan
topsa, u holda o’zining ishini bajargan hisoblanadi. Aks holda, u
𝑦𝑦
1
ni hisoblashdan
oldin 2
20
ta hisoblashni bajarishi talab etiladi. Mazkur holatni davom ettirsak,
buzg’unchi tomonidan bajarilishi mumkin bo’lgan ishni taxminiy hisobi quyidagiga
teng bo’ladi:
1
4
(2
19
) +
3
4
∗
1
4
(2
20
+ 2
19
) +
�
3
4
�
2
∗
1
4
(2
∗
2
20
+ 2
19
) +
⋯
+
�
3
4
�
1023
∗
1
4
(1023
∗
2
20
+ 2
19
) < 2
22
Bu ko’rsatkichlar masalani yechish uchun talab etilayotgan hisoblashlar hajmi
katta ekanligini anglatadi.
Umumiy holda agar foydalanilgan parol zaif bo’lsa, uni aniqlash osonroq va
ixtiyoriy bir parolni buzg’unchi tomonidan aniqlab olinishi
butun tizim xavfsizligini
yo’qolishiga olib keladi.
Download