Amaliy ish Mavzu: O’rtada uchrashish hujum usuli

1. 
   amaliy ish
   

Mavzu: O’rtada uchrashish hujum usuli
Аgar kriptoalgoritmning maxfiy kalitlar toʼplami kompozitsiya amaliga nisbatan berk boʼlsa, yaʼni har qanday ikki kalit zi va zj uchun shunday kalit zk topilsinki, har qanday matnni ketma-ket zi va zj kalitlarida shifrlash natijasi shu matnni zk bilan shifrlangan matnga aynan boʼlsin, yaʼni

F(zj, F(zi, x))=F(zk, x).

Unda bu xossadan foydalanib, shifrlash kalitini topish mumkin, yaʼni zk ni topish uchun ekvivalent juftlik < zi, zj > ni topish kifoya. Bu usul "tugʼilgan kunlar paradoksi"ga asoslanadi. Maʼlumki, tugʼilgan kunlar tekis taqsimlangan deb hisoblansa, 24 kishilik guruhda r=0,5 ehtimollik bilan ikki kishining tugʼilgan kuni bir xil chiqadi.

Umumiy holda bu paradoks quyidagicha ifodalanadi: agar a n predmetlar n ta predmet orasidan qaytarilish bilan tanlansa, ikki predmetning bir xil boʼlish ehtimoli.

Faraz qilinsinki, ochiq matn x va u ning shifrogrammasi u maʼlum. x uchun tasodifiy tarzda kalitlar toʼplami zl va shifrogrammalar w=F(zl, x) toʼplamini saqlovchi maʼlumotlar bazasi (MB) tuzamiz va shifrogrammalarni w boʼyicha tartibga solamiz. MB hajmini 0((p#{z}) ga teng qilib olamiz.

Soʼngra tasodifan zl1 kalitni olib, u shifrmatnni ochamiz va natija v=F(zl1,u) ni MB bilan taqqoslaymiz. Аgar v biror w bilan teng chiqsa, kalit zll izlangan kalit z ga ekvivalent boʼladi.

Vaqt boʼyicha usul murakkabligi

Koʼpaytuvchi log#{z} saralash murakkabligini hisobga oladi.

Zarur xotira 0((r #{z}log#{z}) bit yoki 0((r #{z}) blokdan iborat. Blok uzunligi va kalit uzunligi cheklangan doimiyga farq qiladi deb faraz qilinadi.

Bu usul kalitlar toʼplami yarimgruppa boʼlgan qism toʼplamni oʼz ichiga olgan boʼlsa ham qoʼllanilishi mumkin. Bu usulning boshqa qoʼllanilishini toʼplam yarimgruppa boʼlmagan hol uchun xesh-funktsiyalar misolida namoyish etish mumkin.

Masalan, ERIni soxtalashtirish uchun bitta xesh-obrazga ega ikki matn topish lozim. Undan soʼng imzolangan xabarni boshqa oʼsha xesh-obrazga ega boʼlgan xabar bilan almashtirib qoʼyish mumkin. Bunday ikki xabarni topishni "oʼzaro uchrashish" usulida amalga oshirilsa, izlash murakkabligi

0((p #{z}) boʼladi.

Bunda #{z} mumkin boʼlgan xesh-obrazlar soni. Аmerikalik matematik D. Shenks tomonidan taklif etiltan bu algoritm ehtimollik algoritmidir.

Topshiriq

1. 
   Tug’ilgan kun paradoksiga alohida misol topib uni bajaring
   
2. 
   “O’rtada uchrashish” kriptotahlil usulini tanlagan tug’ilgan kun paradoksingiz orqali izohlang
   

Javoblar

1)Ikki kishining tug’ilgan kuni bir kunda bo’lish ehtimolligi tahminan 70 % bo’lsa guruhda necha kishi borligini toping:

import math

def find( p ):

return math.ceil(math.sqrt(2 * 365 *

math.log(1/(1-p))));

print(find(0.7))

2) N bo’lgan xonada ikkita odamning tug’ilgan kuni bir xil bo’lishi ehtimoli P(bir xil) bo’lsin. P(boshqa) osongina topib olishimiz mumkin ya’ni:

P(bir xil) = 1- P(boshqa)

P(har xil) 1*(364/365) * (363/365) * (362/365) * (1-(n-1)/365)…….sifatida yozilishi mumkin.

Bu ifodani Teylor seriyasi yordamida taxmin qilish mumkin.