O‘zbеkistоn rеspublikаsi raqamli texnologiyalar vаzirligi muhаmmаd аl-xоrаzmiy nоmidаgi tоshkеnt аxbоrоt tеxnоlоgiyаlаri univеrsitеti sаmаrqаnd filiаli

Chastota

о	0.09	о	0.038	о	0.016	о	0.007
е,ё	0.072	л	0.035	е	0.016	ш	0.006
a	0.062	к	0.028	б	0.014	ю	0.006
и	0.062	м	0.026	ь,ъ	0.014	ц	0.004
н	0.053	д	0.025	г	0.013	щ	0.003
т	0.053	п	0.023	ч	0.012	э	0.003
с	0.045	у	0.021	й	0.01	ф	0.002
р	0.04	я	0.018	x	0.009

Yuqorida aytib oʼtilgan printsiplar hozirgi kunda keng tarqalgan

parollarni tanlash boʼyicha dasturlarda qoʼllaniladi. Parollarni tanlash
boʼyicha dastur avvalo ehtimolligi katta boʼlgan parollarni tanlaydi.
ehtimolligi kichik boʼlgan parollarni keyinga olib qoʼyadi. Bunda 35
parollarni tanlash jarayoni oʼn va yuz marttalab kamayadi. Quyidagi
4-jadvalda parollarni tanlashda olingan qator natijalar keltirilgan.
Parollarni tanlash natijasi
4-jadval

Tanlash murakkabligi	Tanlash vaqti	Protsessor turi
2,08⋅	15 minut	486DX/4-100
5,68⋅	8 soat	Pentium-120

4- Pollard usuli «Oʼrtada uchrashish» usuli

Pollard usuli grafik shaklda "oʼrtada uchrashish" usuliga biroz

oʼxshashdir. Unda "tasodifiy akslantirish grafida uchrashish" masalasi
yechiladi. Bu yerda ham ikkita grafning boshlangʼich tugunlaridan chiqib toki
ildiz tugunidan oʼtuvchi sikl hosil boʼlguncha qarama-qarshi yoʼnalishda
harakat davom etadi. Uchrashish murakkabligi 0,5ϕ(p /8)#Ì , yakuniy
murakkablik 6,5ϕ(p /8)# Ì .
Pollard usuli siklik gruppada diskret logarifm masalasini yechish
uchun qisman ekvivalent kalitlarni topishda qoʼllaniladi. Bular bir xil
xesh-funktsiya beruvchi ikki argumentni topishda ham asqotadi.
Diskret logarifmlash masalasiga tadbiqan bu usul avvalgi "oʼrtada
uchrashish" usuliga nisbatan katta xotiradan voz kechish imkonini yaratadi.
MBni sortlash zarurati ham yoʼqoladi. Shu tufayli vaqt boʼyicha
murakkablik 0(log#M) marta kam boʼlib, murakkablik O(ϕ#M) qadam, xotira
hajmi O(1) blokdan iborat.
«Oʼrtada uchrashish» usuli
Аgar kriptoalgoritmning maxfiy kalitlar toʼplami kompozitsiya
amaliga nisbatan berk boʼlsa, yaʼni har qanday ikki kalit zi va zj uchun shunday 36
kalit zk topilsinki, har qanday matni 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
a / 2 2
r 1 ye− = − .
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.
Vaqt boʼyicha usul murakkabligi
O(ϕ#{z}log#{z}).
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 37
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 [1, 6, 25] bu algoritm ehtimollik
algoritmidir