International

DES Kriptanalizi haqida ma'lumot

Download 333,85 Kb.

bet	2/7
Sana	22.06.2022
Hajmi	333,85 Kb.
	#691740

1 2 3 4 5 6 7

Bog'liq
eng-uzb to`liq

DES Kriptanalizi haqida ma'lumot

DES kabi raund takrorlangan blokli shifrda shifrlangan matn oddiy matnga g raund funksiyasini iterativ ravishda qo'llash orqali hisoblanadi.
^Ci ⁼^g⁽^Ci ⁻¹^,^Ki⁾^,ⁱ⁼¹^,²^,^.^.^.^,^r,
^{Bu yerda C}0 ^{- ochiq matn, K}i ^{- yumaloq kalit va C}r ^-shifrlangan matn. Dumaloq funksiya odatda S qutilari, arifmetik amallar va bitli XORing [1] dan foydalanishga asoslanadi.
Blok uzunligi 2 n va r raundli Feistel shifrlash quyidagicha aniqlanadi.
funktsiya:
g: GF(2) ⁿ×GF(2) ⁿ×GF(2) ^m×GF(2) ⁿGF(2) ⁿ
g: (X, Y, Z) = (Y, F(Y, Z) +X).
Shunday qilib, berilgan ochiq matn P= (P^L, P^R) va
^r raundli kalitlar ^K1^,^K2^,^.^.^.^,^K^r^,^shifrlangan
^C⁼⁽^C^L^,^C^R⁾^{har bir turda quyidagicha hisoblanadi}

O`rnatish C⁰^L=P^L, C⁰^R=P^R;

^Hisoblash⁽^Cⁱ^L^,^Rⁱ^L⁾⁼⁽^C^Ri-1^,^F⁽^C^R^i-1^,^Ki⁾⁺^C^Li-1⁾^uchuni= 1,2, . . . , r;

Set, C^L=C^L_r_,C^R=C^R_rraundli kalit esa

^Ki ^GF(2)^m^.^C0
Ta'rif 1. DESga o'xshash takrorlangan shifr Feistel shifridir, bu erda F [5] sifatida aniqlanadi:
^F^:^GF⁽²⁾^m^→^GF⁽²⁾ⁿ^{; F}⁽^X,Ki⁾⁼^P⁽^f⁽^E⁽^X⁾^⊕^Ki⁾⁾^,
^qayerdaki^Ki^G^F⁽²⁾^m^;^f^:^GF⁽²⁾^m^→^GF⁽²⁾ⁿ^{, m}^≥ⁿ^{kuchsiz raund funksiya bo`lsin}; E: GF(2)ⁿ→GF(2)^m kengayish xaritasi bo'lishi kerak; Hamda P: GF(2)ⁿ→GF(2)ⁿalmashtirish bo`lsin.
Bu yerda DES [9] uchun 1-ta'rifning ixtisoslashuvi quyidagicha ishlatilgan:
^Mⁿ⁼^mⁿ^|^mⁿ⁼^b0^b1 ^bo`lsin^.^.^.^bⁿ₋1^,^bⁱ^^Σ2 ^{bu yerda}^,^mⁿ^{n-bitli qator}^;^{Σ2 = 0}^,^{1 = GF(2)}^.^bi ^{bu yerda}ⁱ^th^blok^bo`lib,^and^mn^∈^GF(2)ⁿ^{n-bitli blokdan tashkil topgan xabardir}^.^{Keyinchalik DES kriptotizimi}^χDES ^{tomonidan beriladi}^:
^χDES ⁼^<^m56 ^,^m64^,^m64^,^TDES ^>

^{bu yerda}^,^m56 ^bu^56-bit^kalit^,^m64 ^esa^{oddiy yoki shifrlangan matnning 64-bitli bloki va}^TDES ^{bu shifrlash/shifrlashni o'zgartirish}
^t^k⁽^m64⁾⁼^T^DES⁽^m56^,^m64^);^k⁼¹^,^·^·^·^,¹⁰^,.
^va^tk ^{bu berilgan kompozitsiyadir}^:
t_k =IP ⁻¹◦T8◦T7◦. . .◦T2◦T1◦IP,
bu yerda IP 64 bitning dastlabki almashinishi va ^Tj^{ning har biri}^j⁼¹^,^·^·^·^,¹⁰^{bu shifrlash mavzusining o`zgarishidir}.
1990 yilda Biham va Shamir [1] DESga o'xshash kriptotizimlarni buzishi mumkin bo'lgan va differensial kriptotahlil DK deb nomlanuvchi kriptoanalitik hujum turini ishlab chiqdilar. Ular XOR operatsiyasidan foydalangan holda ochiq matn haqidagi bilimlarni oraliq tur haqidagi bilimga ko'tarish imkonini beruvchi n-raund xarakteristikani tasvirladilar. Har bir tur xarakteristikasi aniq matn farqiga ega ^ΩP, n-raunddagi ma'lumotlarning ma'lum XOR ^ΩP va ehtimollik ^p^Ω (bunda ochiq matn farqi ^ΩT bo'lgan tasodifiy juftliklar qo'llanilganda ^ΩP). To'g'ridan-to'g'ri matn farqi ^ΩP bo'lgan va ma'lum bir kalit yordamida o'sha davrdagi ma'lumotlarning XOR i ^ΩT bo'lgan har qanday juftlik ushbu kalit va n-raundli xarakteristikaga nisbatan o'ng juftlik deyiladi. Boshqa har qanday juftlik noto'g'ri juftlikdir. Shuning uchun to'g'ri juftliklar barcha mumkin bo'lgan juftlarning p ^Ω qismini tashkil qiladi.
^{DK raundli kalit}^Kn^{ni topishga harakat qiladi. U holda}^ΩP^{farqli ikkita P,P}^∗^{ochiq matn uchun kriptoanalitik}^Kn^{uchun quyidagi tenglamani yecha oladi:}

^F-1(Cn,Kn) ⊕^{F-1(Cn,Kn)-1=}^ΩT

Yechimlar nomzodning raundli kalitlari. DK usulini quyidagicha umumlashtirish mumkin [5]:

1-qadam.Yuqori ehtimollik bilan mos dumaloq xarakteristikani toping.
2-qadam. Farqi ^ΩP bo'lgan P,P ∗ ochiq matnli juftlikni bir xilda tanlang va bu juftlikning shifrlanishini oling. Nomzodning yumaloq kalitlarini aniqlang, shunda ularning har biri kuzatilgan chiqish farqiga olib kelishi mumkin edi. Har bir nomzodning tur kaliti hisoblagichini oshiring.
3-qadam. 2-bosqichni bitta raundli kalit boshqa raundli kalitlarga qaraganda sezilarli darajada tez-tez sanalganligi aniqlanmaguncha takrorlang. Nomzodning haqiqiy kaliti bo'lish uchun ushbu kalitni oling.
Biham va Shamir DES ning cheklangan versiyalarida o‘tkazilgan tajribalar natijasida hujumning murakkabligi taxminan c/p^Ω ekanligini aniqladilar, bu erda p ^Ω foydalanilayotgan xarakteristikaning ehtimoli, c esa 2p^Ω foydalanilgan xarakteristikaning ehtimoli. Keyin taxminan m×p^Ω juftliklar to'g'ri juftliklar bo'lib, ularning har biri boshqa qiymatlar orasida to'g'ri kalit qiymatini taklif qilishi mumkin. Ba'zi hollarda tajovuzkor ushlangan shifrlangan matnlar yordamida ochiq matn uchun juftlarni noto'g'ri juftlar sifatida tasniflashi mumkin. Bunday holda, bunday juftliklar tashlanadi va ularni tahlil qilishda foydalanmaslik kerak. Biz izlayotgan kalitning mumkin boʻlgan qiymatlari soni k boʻlsin,  har bir tashlanmaydigan ochiq matnlar juftligi tomonidan

taklif qilingan kalitlar soni va  oʻchirilmagan juftlarning barcha juftlarga nisbati boʻlsin. Tasodifiy kalitni taklif qilishning o'rtacha soni quyidagilar bilan berilishi mumkin:
Ya'ni, f(S) har doim 1 dan kichik bo'ladi, bundan tashqari ⁿsr ⁼ⁿP ^{. Bu}^Holland^{sxemasi teoremasining bajarilishini va vakilning kutilgan soni}^m^{(S, t+1) ni kafolatlaydi.}

S/N=
m×γ×λ _.k
t+1 vaqtidagi S sxemasi har doim S ning oldingi t vaqtidagi sonidan (S, t) katta yoki teng. Keyin
m(S, t+ 1)≥m(S, t), bu sonini bildiradi
sxemalar o'sib bormoqda va bu teoremani isbotlaydi.

Shunday qilib, S/N o'ng kalitni tasodifiy kalitning necha marta hisoblashini aniqlaydi, ya'ni,
Eng yaxshi xromosoma to`g`ri juftⁿP ^{ni to`liq qondiradigan xromosoma bo`lganligi sababli,}^{eng yaxshi xromosoma}^Cr ^{ni 1 ga yetkazadi}^.

S/N= ^k^×^p^Ω_.
^λ^×^γ^O`rtacha^,^Cr ⁼¹^Σ^s^Cr^,^{bu yerda s xromosoma}

DK hujumining muvaffaqiyati uchun zaruriy shart S/N >1 va hujumning kutilayotgan muvaffaqiyati bu nisbat bilan ortadi. Aslida, DK hujumlari shifrlangan kalitni taklif qilish uchun xotira va vaqtni sarflaydigan ko'p sonli to'g'ri juftliklarni talab qiladi. Boshqa tomondan, GA to'g'ridan-to'g'ri xromosomalar shaklida ifodalangan kalitlar populyatsiyasiga qo'llanilishi mumkin emas. Shuning uchun, to'g'ri juftlarni aniqlash uchun DK kerak. Bunga har bir turda har bir S-boxning to'g'ri chiqish farqiga olib keladigan kirish farqini tekshirish orqali erishiladi. Bunday juftliklar kalitning pastki kalitlarini olish uchun kerak.
Keyingi ishlarda GA dan ba'zi DES-8 kriptotizimlarining kalitlarini ikki usul bilan hisoblash uchun foydalanilgan.

Tegishli xarakteristikalar bilan amalga oshirish uchun saqlangan bir qator DC ishlab chiqarilgan o'ng juftliklardan foydalanish..
Genetik jihatdan to'g'ri juftlarni yaratish.

Download 333,85 Kb.

Do'stlaringiz bilan baham:

1 2 3 4 5 6 7