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

3- лабаратория иши

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

Топшириқ

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

Юқоридаги 3 бит кириш икки бит чиқиш қийматларига эга бўлган S-бокс учун юқори эҳтимолликка эга апроксимация тенгламаларини тузинг.

Kripto tahlil:

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

Yuqoridagi s-box dan kirish х₀ х₁ х₂ va chiqish y₀y₁ qiymatlari teng bo’lgan xollar uchun jadval hosil qilinadi:

Masalan yuqoridagi (1 )jadvaldan satr x₀=0 va ustun х₁ х₂=10 bo’lganda y₀y₁=11 qiymat to’g’ri keladi. Shu tariqa (2) jadval to’ldiriladi.

(2)

X0	X1	X2	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	1
1	0	1	1	0
1	1	0	1	1
1	1	1	0	1

апроксимация tenglamalarini tuzamiz:

1/1)

1= 001 = 0*x₀ ⊕ 0*x₁ ⊕ 1*x₂ = x₂ , 1= 01 = 0*y₀ ⊕ 1*y₁ = y₁

1/2)

1= 001 = 0*x₀ ⊕ 0*x₁ ⊕ 1*x₂ = x₂ , 2= 10 = 1*y₀ ⊕ 0*y₁ = y₀

1/3)

2= 001 = 0*x₀ ⊕ 0*x₁ ⊕ 1*x₂ = x₂ , 3= 11 = 1*y₀ ⊕ 1*y₁ = y₀⊕ y₁

///////////////////////////////

2/1)

2= 010 = 0*x₀ ⊕ 1*x₁ ⊕ 0*x₂ = x₁ , 1= 01 = 0*y₀ ⊕ 1*y₁ = y₁

2/2)

2= 010 = 0*x₀ ⊕ 1*x₁ ⊕ 0*x₂ = x₁, 2= 10 = 1*y₀ ⊕ 0*y₁ = y₀

2/3)

2= 010 = 0*x₀ ⊕ 1*x₁ ⊕ 0*x₂ = x₁, 3= 11 = 1*y₀ ⊕ 1*y₁ = y₀⊕ y₁

3/1)

/////////////////////////////////

3= 011 = 0*x₀ ⊕ 1*x₁ ⊕ 1*x₂ = x₁⊕x₂ , 1= 01 = 0*y₀ ⊕ 1*y₁ = y₁

3/2)

3= 011 = 0*x₀ ⊕ 1*x₁ ⊕ 1*x₂ = x₁⊕x₂, 2= 10 = 1*y₀ ⊕ 0*y₁ = y₀

3/3)

3= 011 = 0*x₀ ⊕ 1*x₁ ⊕ 1*x₂ = x₁⊕x₂, 3= 11 = 1*y₀ ⊕ 1*y₁ = y₀⊕ y₁

_{//////////////////////////////}

4/1)

4= 100 = 1*x₀ ⊕ 0*x₁ ⊕ 0*x₂ = x₀, 1= 01 = 0*y₀ ⊕ 1*y₁ = y₁

4/2)

4= 100 = 1*x₀ ⊕ 0*x₁ ⊕ 0*x₂ = x₀, 2= 10 = 1*y₀ ⊕ 0*y₁ = y₀

4/3)

4= 100 = 1*x₀ ⊕ 0*x₁ ⊕ 0*x₂ = x₀, 3= 11 = 1*y₀ ⊕ 1*y₁ = y₀⊕ y<sub>1

///////////////////////////</sub>

5/1)

5= 101 = 1*x₀ ⊕ 0*x₁ ⊕ 1*x₂ = x₀⊕ x₂, 1= 01 = 0*y₀ ⊕ 1*y₁ = y₁

5/2)

5= 101 = 1*x₀ ⊕ 0*x₁ ⊕ 1*x₂ = x₀⊕ x₂, 2= 10 = 1*y₀ ⊕ 0*y₁ = y₀

5/3)

5= 101 = 1*x₀ ⊕ 0*x₁ ⊕ 1*x₂ = x₀⊕ x₂, 3= 11 = 1*y₀ ⊕ 1*y₁ = y₀⊕ y₁

///////////////////////////////////

6/1)

6= 110 = 1*x₀ ⊕ 1*x₁ ⊕ 0*x₂ = x₀⊕ x₁, 1= 01 = 0*y₀ ⊕ 1*y₁ = y₁

6/2)

6= 110 = 1*x₀ ⊕ 1*x₁ ⊕ 0*x₂ = x₀⊕ x₁, 2= 10 = 1*y₀ ⊕ 0*y₁ = y₀

6/3)

6= 110 = 1*x₀ ⊕ 1*x₁ ⊕ 0*x₂ = x₀⊕ x₁, 3= 11 = 1*y₀ ⊕ 1*y₁ = y₀⊕ y₁

///////////////////////////////////

7/1)

7= 111 = 1*x₀ ⊕ 1*x₁ ⊕ 1*x₂ = x₀⊕ x₁ ⊕x₂ , 1= 01 = 0*y₀ ⊕ 1*y₁ = y₁

7/2)

7= 111 = 1*x₀ ⊕ 1*x₁ ⊕ 1*x₂ = x₀⊕ x₁⊕x₂, 2= 10 = 1*y₀ ⊕ 0*y₁ = y₀

7/3)

7= 111 = 1*x₀ ⊕ 1*x₁ ⊕ 1*x₂ = x₀⊕ x₁⊕x₂, 3= 11 = 1*y₀ ⊕ 1*y₁ = y₀⊕ y₁

(2) jadvaldan kiruvchi va chiquvchi qiymatlarning mos xoldagi tengligi sonlari aniqlanadi va (3) jadvalga mos xolda joylashtiriladi:

(3)

K/Ch	1	2	3
1	3	2	5
2	5	4	1
3	5	6	3
4	5	4	5
5	4	2	3
6	3	4	3
7	7	2	5

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

х₀⊕ х₁ ⊕ х₂ =y₁ 7/8=0.875

Назорат саволлари

1. 
   Чизиқли криптоанализ усулининг моҳиятини тушунтиринг
   
2. 
   TDES алгоритмининг чизиқли қриптоанализи қандай аималга оширилади?
   

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

Дифференциал криптоанализда кириш ва чиқиш фарқларига еътибор қаратиларса, чизиқли таҳлилнинг мақсади ночизиқли қисмларни чизиқли тенгламалар билан тахминий ифодалашга қаратилади. Математиклар учун чизиқли тенгламаларни йечиш осон, агар шундай еҳтимолликлар топилса, бу хужумни шифрматнга қаратиш мумкин.

2. TDES алгоритмининг чизиқли криптоанализи дифференсиал криптоанализига нисбатан соддароқ ҳисобланади. Юқорида TDES нинг дифференсиал криптоанализида ўнг S-боксга эътибор қаратган бўлса, энди чизиқли криптоанализ чап S-боксга қаратилади.

Қуйидаги белгилар билан берилган

y0y1y2 y3= Sboxleft(x0 x1x2x3x4x5)

TDES алгоритмининг чап S-боксини чизиқли аппроксиоматия тенгламалари

y1= x 2 va y2=x3 (1)

Бунга ўхшаш аппросия тенгламаларига асосланган чизиқли таҳлилни ривожлантириш учун ушбу усулни барча роундларга кетма-кет қўллаш шарт. Очиқ матн P = (L0,R0) дан R0=r0r1r2r3r4r5r6 r7 ўнг қисми танлаб олинади. Кейин кенгайтириш функсиясидан қуйидагига эга бўлинади.

expend(R0)= expend (r0r1r2r3r4r5r6 r7)= r4r7r2r1r5r7r0 r2 r6r5r0 r3. (2)

S- боксга биринчи роундда кириш қийматини қуйидагига тенг:

r4r7r2r1r4r5 r7⊕ k2k4k5k6k7k1.

Демак y0y1y2y3 чап S-боксдан биринчи роундда чиқиш қийматлари деб қаралади.

y1= r2⊕ k5 va y2= r1⊕ k6 , (3)

бу йердаги ҳар бир тенгликнинг бажарилиш йеҳтимоллиги ¾ га тенг. Бошқа сўз билан айтганда, чап S-бокс учун, чиқишдаги 1-индексдаги бит киришдаги 2-индексдаги бит ҳисобланади, ХОR амали билан ҳисобланганда, чиқиш битининг 2-рақами кириш битининг 1 рақамига тенг бўлиши ¾ еҳтимоллик билан ҳиссобланади.

TDES алгоритмида ( DES алгоритмида бўлгани каби) S-боксдан чиқиш қийматлари олдинги қадамдаги чап ярим блоки билан ХОR амали билан қўшилади. Демак L0=l0l1l2 l3l4l5l6l7 ва R1= r’0 r’1 r’2 r’3 r’4 r’5 r’6 r’7 бўлсин, кейин бу С-боксдан биринчи роундда чиқиш қийматлари r’0 r’1 r’2 r’3 ни чап блок l0l1l2l3 билан ХОR амали орқали қўшилади. Ушбу белгиларни 21-тенглама орқали бирлаштириб, қуйидагига ега бўлинади

r’₁= r₂⊕ k₅⊕ l₁ va r’₂= r₁⊕ k₆⊕ l₂,

бу тенгламаларнинг ҳар бири ¾ еҳтимоллик билан бажарилади Худди шунга ўхшаш натижалар кейинги роундларда такрорланади, бу ерда махсус калит битлари қисм калит K_i га боғлиқ.

4-тенглама натижасида, барча роундлар учун 19-тенгламадагидек чизиқли аппроксия тенгламаларини тузиш мумкин. Улар қуйида 4.2-жадвалда тасвирланган. Чизиқли кириптотаҳлил бу очиқ техтни билиш хужуми (known plaintext attack) бўлгани учун, бунда ҳужумчи очиқ матнни P = p₀p₁..p₁₅ ва шунга мос шифрматнни 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₇ калит битлари ҳақида баъзи маълумотларга эга бўлинади.