4- амалий машғулот Мавзу: Симметрик блокли шифрлар учун чизиқли криптоанализ усули

4- амалий машғулот

Мавзу: Симметрик блокли шифрлар учун чизиқли криптоанализ усули

Қизиғи шундаки, чизиқли криптоанализ ҳам дифференциал таҳлил каби симметрик блокли шифрларнинг ночизиқли қисмларига қаратилади. Чизиқли криптоанализ дифференциал криптоанализдан бир неча йил кейин ишлаб чиилган бўлсада, у консептуал жиҳатдан оддий, DES алгоритми учун анча самарали ва фақатгина known plaintext( очиқ матнни билиш) хужуми асосида таҳлил қилиш кифоя, chosen plaintext(очиқ матнларни танлаш) хужумини талаб қилмайди.
Дифференциал криптоанализда кириш ва чиқиш фарқларига эътибор қаратиларса, чизиқли таҳлилнинг мақсади ночизиқли қисмларни чизиқли тенгламалар билан тахминий ифодалашга қаратилади. Математиклар учун чизиқли тенгламаларни ечиш осон, агар шундай эҳтимолликлар топилса, бу хужумни шифрматнга қаратиш мумкин. DES алгоритмининг ночизиқли қисми бу S-бокслардир, шунинг учун чизиқли криптоанализ S-бокслар устида амалга оширилади.

Сатр	Устун				(1)
	00	01	10	11
0	10	01	11	00
1	00	10	01	11

х0	х1	х2	y0	y1
0	0	0	1	0
0	0	1	0	1
0	1	0	1	1
0	1	1	0	0
1	0	0	0	0
1	0	1	1	0
1	1	0	0	1
1	1	1	1	1

К/ч	1	2	3
1	4	4	3
2	6
3		4	6
4	4		4
5		0
6
7

4=100= 1*х₀⊕ 0*х₁⊕ 0*х₂= х_{0 3}=11=1*y₀⊕ 1*y₁= y₀⊕ y₁

011== 0*х₀⊕ 1*х₁⊕ 1*х₂= х₁⊕ х₂ 10=1*y₀⊕ 0*y₁= y₀
100= 1*х₀⊕ 0*х₁⊕ 0*х₂= х₀ 01=0*y₀⊕ 1*y₁= y₁
010= 0*х₀⊕ 1*х₁⊕ 0*х₂= х₁
01=0*y₀⊕ 1*y₁= y₁
10=1*y₀⊕ 0*y₁= y₀
001= 0*х₀⊕ 0*х₁⊕ 1*х₂= х₂ 01= 0*y₀⊕ 1*y₁= y₁
001= 0*х₀⊕ 0*х₁⊕ 1*х₂= х₂ 10=1*y₀⊕ 0*y₁= y₀
001= 0*х₀⊕ 0*х₁⊕ 1*х₂= х₂ 11=y₀⊕ *y₁
Яна юқоридаги жадвалдаги S-босни кўриб чиқилса, учта кириш битларини х₀х₁х₂ ва иккита чиқиш битларини y₀y₁ каби белгилаб олинади. Жадвалнинг сатри х₀ қийматни, устунни х₁х₂ қийматларини белгилайди. Қуйидаги 4.1-жадвалда кириш ва чиқиш битларининг тенг бўлиш эҳтимоллиги кўриб чиқилган. Жадвалда “4” га тенг бўлмаган қийматлар тасодифий бўлмаган, яъни чиқиш битининг тасодифий алмашмаганини билдиради.
4.1-жадвал: S-бокснинг чизиқли таҳлили

Криш битлари	Чиқиш битлари
	y0	y1	y0⊕ y1
0	4	4	4
х0	4	4	4
х1	4	6	2
х2	4	4	4
х0⊕ х1	4	2	2
х0⊕ х2	0	4	4
х1⊕ х2	4	6	6
х0⊕ х1 ⊕ х2	4	6	2

х₁= y₁ 6/8=3/4=0,75=75%
х₀⊕ х₂= y₀⊕1
Юқоридаги 3-жадвал натижалари шуни кўрсатадики, масалан, y₀ =x₀⊕ x₂ ⊕1, y₀ нинг х₀⊕ х₂ га тенг бўлиш имконияти 0 га тенг, унга 1 ни ХОR амали билан қўшиб бемалол 1 қийматга амаштиришимиз мумкин ва y₀⊕y₁= x₁⊕ x₂ тенгликнинг бажарилиш еҳтимоли ¾ . Ушбу маълумотлардан фойдаланиб, биз S-боксларни чизиқли функсиялар билан алмаштириб таҳлил қилиш мумкин. Натижада ночизиқли S-бокслардан чизиқли тенгламаларни ҳосил қилиб олиш, бу ерда чизиқли тенгламалар аниқлиликка асосланган бўлиши шарт эмас, лекин бу тенгламаларни муҳим бўлмаган эҳтимолликлар билан бажариш имконияти мавжуд.
Бу чизиқли эҳтимоллик тенгламаларидан DES шифрлаш блокларига хужум фойдалироқ бўлиши учун бу ёдашувни кенгайтиришга харакат килиш керак. Натижада калитни топишга қаратилган чизиқли тенгламаларни ечиш имкониятига ега бўлинади. Худди дифференциал таҳлилда бўлгани каби барча роундлар учун “кетма-кетлик занжири” каби боғланган тенгламалар системасини ҳосил қилиш мумкин.
Чизиқли функсиялар билан DES алгоритми S-боксларининг қанчалик яқин еҳтимолик билан ифодалаш мумкин? DES алгоритмининг ҳар бир S-бокси ночизиқли комбинациялар асосида лойиҳалаштирилгани учун кириш битлари чиқиш битига яхши эҳтимоллик билан алмашади. Бироқ, кириш битларининг чизиқли комбинацияси орқали тахмин қилинган чиқиш битларининг чизиқли комбинациясини аниқлаш мумкин. Натижада DES алгоритмини муаффақиятли чизиқли криптоанализ қилиш мумкин.
Дифференциал криптоанализда бўлгани каби DES алгоритмининг чизиқли таҳлили ҳам мураккаб. Чизиқли криптоанализни кўрсатиш учун, DES алгоритмига ўхшаш ТDES алгоритми ҳақида куйида маълумот берилади. Кейин ТDES алгоритмини дифференциал ва чизиқли криптоанализ қилиш мумкин бўлади.
ТDES алгоритмининг чизиқли криптоанализи
ТDES алгоритмининг чизиқли криптоанализи дифференциал криптоанализига нисбатан соддроқ ҳиссобланади. Юқорида ТDESнинг дифференциал криптоанализида ўнг S-боксга эътибор қаратган бўлса, энди чизиқли криптоанализ чап S-боксга қаратилади.
Қуйидаги белгилар билан берилган
y₀y₁y₂ y₃= Sboxleft(x₀ x₁x₂x₃x₄x₅)
ТDES алгоритмининг чап S-боксини чизиқли аппроксиоматия тенгламалари
y₁= x ₂ va y₂=x₃ (4.1)
¾ эҳтимоллик билан бажарилади. Бунга ўхшаш аппросия тенгламаларига асосланган чизиқли таҳлилни ривожлантириш учун ушбу усулни барча роундларга кетма-кет қўллаш шарт.
Очиқ матн P = (L₀,R₀)дан R₀=r₀r₁r₂r₃r₄r₅r₆ r₇ ўнг қисми танлаб олинади. Кейин кенгайтириш функсиясидан қуйидагига эга бўлинади


expend(R₀)= expend (r₀r₁r₂r₃r₄r₅r₆ r₇)= r₄r₇r₂r₁r₅r₇r₀ r₂ r₆r₅r₀ r_3. (4.2)
3 амалий ишдаги 4-тенгламадаги F функсиянинг таърифидан, S-боксга биринчи риоунддаги кириш қийматини expand(R₀) ⊕K₁ тенгликдан олиш мумкин. Кейин, 4.2-тенглама ва К₁ роунд калити таърифидан, чап S-боксга биринчи роундда кириш қийматини қуйидагига тенглигини кўриш мумкин
r₄r₇r₂r₁r₄r₅ r₇⊕ k₂k₄k₅k₆k₇k_12.
Демак y₀y₁y₂y₃ чап S-боксдан биринчи роундда чиқиш қийматлари деб қаралади. Кейин юқоридаги 19-тенглама қуйидагини назарда тутади
y₁= r₂⊕ k₅ va y₂= r₁⊕ k₆ , (4.3)
бу ердаги ҳар бир тенгликнинг бажарилиш еҳтимоллиги ¾ га тенг. Бошқа сўз билан айтганда, чап S-бокс учун, чиқишдаги 1-индехдаги бит киришдаги 2-индексдаги бит ҳисобланади, ХОR амали билан ҳисобланганда, чиқиш битининг 2-рақами кириш битининг 1 рақамига тенг бўлиши ¾ эҳтимоллик билан ҳиссобланади.
ТDES алгоритмида ( DES алгоритмида бўлгани каби) S-боксдан чиқиш қийматлари олдинги қадамдаги чап ярим блоки билан ХОR амали билан қўшилади. Демак L₀=l₀l₁l₂ l₃l₄l₅l₆l₇ ва R₁= r’₀ r’₁ r’₂ r’₃ r’₄ r’₅ r’₆ r’₇ бўлсин, кейин бу S-боксдан биринчи роундда чиқиш қийматлари r’₀ r’₁ r’₂ r’₃ ни чап блок l₀l₁l₂ l₃ билан ХОR амали орқали қўшилади. Ушбу белгиларни 21-тенглама орқали бирлаштириб, қуйидагига эга бўлинади


r’₁= r₂⊕ k₅⊕ l₁ va r’₂= r₁⊕ k₆⊕ l₂, (4.4)
бу тенгламаларнинг ҳар бири ¾ еҳтимоллик билан бажарилади Худди шунга ўхшаш натижалар кейинги роундларда такрорланади, бу ерда махсус калит битлари қисм калит K_i га боғлиқ.
4.4-тенглама натижасида, барча роундлар учун 19-тенгламадагидек чизиқли аппроксия тенгламаларини тузиш мумкин. Улар қуйида 4.2-жадвалда тасвирланган. Чизиқли кириптотаҳлил бу очиқ техтни билиш хужуми (known plaintext attack) бўлгани учун, бунда ҳужумчи очиқ матнни P = p₀p₁..p₁₅ ва шунга мос шифрматнни C=c₀c₁c₂..c₁₅ билади.
4.2-жадвалнинг охирги сатрида L₄=c₀c₁c₂c₄c₅c₆c₇ эканлиги келтирилган.
Ушбу тенгламаларни қуйидагича қайта ёзиш мумкин
k₀⊕k₁=c₁⊕p₁₀ (4.5)
ва
k₇⊕k₂=c₂⊕p₉ (4.6)
юқоридаги тенгламаларнинг ҳар иккаласи ҳам (¾)³ еҳтимоллик билан бажарилади. c₁, c₂, p₉ va p₁₀ маълумлигидан, k₀, k₁, k₂ ва k₇ калит битлари ҳақида баъзи маълумотларга эга бўлинади.
4.3-жадвал. ТDES алгоритмининг чизиқли таҳлили

(L0 ,R0) =(p0…p7,p8…p15)	1 ва 2 битлар (рақамлар 0 дан бошланган)	Бажарилиш эҳтимоллиги
L1=R0 R1=L0⊕F(R0 ,K1)	p9,p10 p9⊕p10⊕ k5, p2⊕p9⊕ k6	1 ¾
L2=R1 R2=L1⊕F(R1 ,K2)	p1⊕p10⊕ k5, p2⊕p9⊕ k6 p9⊕k6⊕k7, p1⊕k5⊕k0	¾ (¾)^2
L3=R2 R3=L2⊕F(R2 ,K3)	p2⊕ k6⊕k5, p1⊕k5⊕k0 p10⊕k0⊕k1, p9⊕k7⊕k2	(¾)^2 (¾)^3
L4=R3 R4=L3⊕F(R3 ,K4) C=(L4,R4)	p10⊕k0⊕k1, p9⊕k7⊕k2 c1=p10⊕k0⊕k1, c2=p9⊕k7⊕k2	(¾)^3 (¾)^3

4.3-Жадвал натижаларига асосланган ҳолда чизиқли ҳужумни амалга ошириш содда ҳисобланади. Маълум очиқ матн P =p₀p₁p₂..p₁₅ ва унга мос шифрмат C=c₀c₁c₂..c₁₅ берилган бўлсин. Ҳар бир жуфтлик учун increment қийматини қуйидагиларга қараб мос равишда амалга ошириб, ушбу
c₁⊕p₁₀=0 ёки c₁⊕p₁₀=1
ёки ушбу тенглама бажарилади
c₂⊕p₉=0 yoki c₂⊕p₉=1.
100 та танлаб олинган очиқ матнлардан фойдаланилганда қуйидаги натижалар олинган:
c₁⊕p₁₀=0 38 марта бажарилди
c₁⊕p₁₀=1 62 марта бажарилди
c₂⊕p₉=0 62 марта бажарилди
c₂⊕p₉=1 38 марта бажарилди.
Ушбу ҳолатдан, қуйидаги ҳулосага келиш мумкин. 23-тенгламадан келиб чиқиб катта 62% ли эҳтимолликни инобатга олиб
k₀⊕k₁=1
ва 24-тенглама катта 62% ли эҳтимоллик билан қуйидагига тенг
k₇⊕k₂=0
Ушбу мисолда ҳақиқий калит
K = 1010 0011 0101 0110,
ва бундан k₀⊕k₁=1 ёки k₀⊕k₁=0 осонлик билан аниқланадики. Бу чизиқли ҳужум орқали аниқланди.
Юқоридаги чизиқли криптоанализда калит маълумотининг икки битини тиклаш келтирилган. Бутун К калитни қайта тиклаш учун қолган номаълум битларни ҳам тўлиқ аниқлаш керак. Бу тахминан 2¹³ та шифрлашни бажариш ва чизиқли криптоанализни амалга оширишни талаб қилади. Бу ҳужум жуда муҳим аҳамиятга эга бўлмаса ҳам самарали ҳужум ҳисобланади, шунинг учун қилинган таҳлил ТDES алгоритмининг хавфсиз алгоритм эмаслигини кўрсатди.


Топшириқ