Agar Momo Havo kamida 50 foiz muvaffaqiyatli bo'lishi kerak bo'lsa, nima qilish kerak

Algoritm 11.1 Oldindan tasvir hujum +
- P ≈ 1 - e ^{- k / N.} Agar Momo Havo kamida 50 foiz muvaffaqiyatli bo'lishi kerak bo'lsa, nima qilish kerak bo'l hajmi ning k ? Biz shuningdek ko'rsatdi bu qiymat ichida Jadval 11.3 uchun birinchi tug'ilgan kun muammo: k ≈ 0,69 × N , yoki k ≈ 0,69 × 2 ⁿ . In boshqa so'zlar, uchun Momo Havo uchun bo'l omadli Ko'proq dan 50 foiz, u 2 ^{n ga mutanosib bo'lgan hazm qilish ro'yxatini yaratishi kerak} .



qiyinchilik ning a oldingi tasvir hujum hisoblanadi mutanosib uchun 2 ⁿ .



Misol 11.6
A kriptografik hash funktsiyasi foydalanadi a hazm qilish ning 64 bitlar. Qanaqasiga ko'p hazm qiladi qiladi Momo Havo kerak uchun yaratmoq 0,5 dan ortiq ehtimollik bilan asl xabarni topish uchun?
Yechim
Yaratiladigan dayjestlar soni k ≈ 0,69 × 2 ⁿ ≈ 0,69 × 2 ⁶⁴ . Bu katta raqam. Xatto .. bo'lganda ham Momo Havo soniyada 2 ³⁰ (deyarli bir milliard) xabar yaratishi mumkin, bu 0,69 × 2 ³⁴ soniya yoki undan ko'proq vaqtni oladi. 500 yildan ortiq. Bu shuni anglatadiki, 64 bit o'lchamdagi xabarlar dayjesti oldindan ko'ra xavfsizdir. yoshi hujum, lekin, kabi tez orada ko'ramiz ta'minlanmagan to'qnashuv hujumiga.


Ikkinchi Oldindan tasvir Hujum
Momo Havo D = h(M) va unga mos keladigan M xabarini tutib oldi; u xohlaydi h(M ′ ) = D. Momo Havo k − 1 ta xabarlar roʻyxatini yaratishi uchun boshqa M ′ xabarini toping va 11.2 algoritmini ishga tushirish.



Algoritm 11.2 Ikkinchi oldingi tasvir hujum

Algoritm ikkinchi xabarni topishi mumkin, uning uchun D ham dayjest bo'ladi yoki bo'lishi mumkin muvaffaqiyatsiz. Nima hisoblanadi ehtimollik ning muvaffaqiyat ning bu algoritm? Shubhasiz, bu bog'liq yoqilgan ro'yxat hajmi, k , Momo Havo tomonidan tanlangan. Ehtimolni topish uchun biz ikkinchi tug'ilgan kundan foydalanamiz muammo. hazm qilish yaratilgan tomonidan dastur belgilaydi natijalar ning a tasodifiy o'zgaruvchan. Muvaffaqiyat ehtimoli P ≈ 1 - e ^{- ( k - 1)/ N dir} . Agar Momo Havo kamida 50 foiz bo'lishi kerak bo'lsa muvaffaqiyatli, k hajmi qanday bo'lishi kerak ? Biz ushbu qiymatni 11.3-jadvalda ham ko'rsatdik ikkinchi tug'ilgan kun muammosi: k ≈ 0,69 × N +1 yoki k ≈ 0,69 × 2 ⁿ + 1. Boshqacha qilib aytganda, uchun Momo Havoning 50 foizidan ko'prog'ida muvaffaqiyat qozonish uchun u ro'yxatini tuzishi kerak hazm qilish bu hisoblanadi mutanosib uchun 2 ⁿ .



n

qiyinchilik ning a ikkinchi oldingi tasvir hujum hisoblanadi mutanosib uchun 2 .


To'qnashuv Hujum
Momo Havo ehtiyojlari uchun topmoq ikki xabarlar, M va M ′ ; shunday bu h(M) = h(M ′ ). Momo Havo mumkin yaratmoq a ro'yxati k xabarlar va 11.3 Algoritmini ishga tushirish.




Collision_Attack
{
for (i = 1 to k )
{
create (M[i])
D[i] ← h (M[i]) // D [i] is a list of created digests for ( j = 1 to i − 1)
{
if (D[i] = D[ j]) return (M[i] and M[ j])
}
}
return failure
}
Algoritm 11.3 To'qnashuv hujum

Algoritm bir xil dayjestga ega ikkita xabarni topishi mumkin. Ehtimol nima - bu algoritm muvaffaqiyat qobiliyati? Shubhasiz, bu ro'yxat hajmiga bog'liq, k , tanlangan Momo Havo tomonidan. Ehtimolni topish uchun biz uchinchi tug'ilgan kun muammosidan foydalanamiz. Dijest yaratilgan tomonidan dastur belgilaydi natijalar ning a tasodifiy o'zgaruvchan. ehtimollik ning muvaffaqiyat hisoblanadi P ≈ 1 − e ^{- k ( k - 1)/2 N} . Agar Momo Havo ehtiyojlari uchun bo'l da kamida ellik foiz omadli, nima kerak k hajmi bo'lsin ? Biz ushbu qiymatni uchinchi tug'ilgan kun uchun 11.3-jadvalda ham ko'rsatdik. lem: k ≈ 1.18 × N ^1/2 , yoki k ≈ 1.18 × 2 ^{n /2} . In boshqa so'zlar, uchun Momo Havo uchun bo'l omadli Vaqtning 50 foizidan ko'prog'i, u mos keladigan hazm qilish ro'yxatini yaratishi kerak. milliy uchun 2 ^{n /2} .

qiyinchilik ning a to'qnashuv hujum hisoblanadi mutanosib uchun 2 ^{n /2} .