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


Download 33.88 Kb.
Sana21.11.2020
Hajmi33.88 Kb.
#149496
Bog'liq
4-top

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*х1⊕ 0*х2= х0 3=11=1*y0⊕ 1*y1= y0⊕ y1

011== 0*х0⊕ 1*х1⊕ 1*х2= х1⊕ х2 10=1*y0⊕ 0*y1= y0

100= 1*х0⊕ 0*х1⊕ 0*х2= х0 01=0*y0⊕ 1*y1= y1

010= 0*х0⊕ 1*х1⊕ 0*х2= х1

01=0*y0⊕ 1*y1= y1

10=1*y0⊕ 0*y1= y0

001= 0*х0⊕ 0*х1⊕ 1*х2= х2 01= 0*y0⊕ 1*y1= y1

001= 0*х0⊕ 0*х1⊕ 1*х2= х2 10=1*y0⊕ 0*y1= y0

001= 0*х0⊕ 0*х1⊕ 1*х2= х2 11=y0⊕ *y1



Яна юқоридаги жадвалдаги S-босни кўриб чиқилса, учта кириш битларини х0х1х2 ва иккита чиқиш битларини y0y1 каби белгилаб олинади. Жадвалнинг сатри х0 қийматни, устунни х1х2 қийматларини белгилайди. Қуйидаги 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


х1= y1 6/8=3/4=0,75=75%

х0⊕ х2= y0⊕1

Юқоридаги 3-жадвал натижалари шуни кўрсатадики, масалан, y0 =x0⊕ x2 ⊕1, y0 нинг х0⊕ х2 га тенг бўлиш имконияти 0 га тенг, унга 1 ни ХОR амали билан қўшиб бемалол 1 қийматга амаштиришимиз мумкин ва y0⊕y1= x1⊕ x2 тенгликнинг бажарилиш еҳтимоли ¾ . Ушбу маълумотлардан фойдаланиб, биз S-боксларни чизиқли функсиялар билан алмаштириб таҳлил қилиш мумкин. Натижада ночизиқли S-бокслардан чизиқли тенгламаларни ҳосил қилиб олиш, бу ерда чизиқли тенгламалар аниқлиликка асосланган бўлиши шарт эмас, лекин бу тенгламаларни муҳим бўлмаган эҳтимолликлар билан бажариш имконияти мавжуд.

Бу чизиқли эҳтимоллик тенгламаларидан DES шифрлаш блокларига хужум фойдалироқ бўлиши учун бу ёдашувни кенгайтиришга харакат килиш керак. Натижада калитни топишга қаратилган чизиқли тенгламаларни ечиш имкониятига ега бўлинади. Худди дифференциал таҳлилда бўлгани каби барча роундлар учун “кетма-кетлик занжири” каби боғланган тенгламалар системасини ҳосил қилиш мумкин.

Чизиқли функсиялар билан DES алгоритми S-боксларининг қанчалик яқин еҳтимолик билан ифодалаш мумкин? DES алгоритмининг ҳар бир S-бокси ночизиқли комбинациялар асосида лойиҳалаштирилгани учун кириш битлари чиқиш битига яхши эҳтимоллик билан алмашади. Бироқ, кириш битларининг чизиқли комбинацияси орқали тахмин қилинган чиқиш битларининг чизиқли комбинациясини аниқлаш мумкин. Натижада DES алгоритмини муаффақиятли чизиқли криптоанализ қилиш мумкин.

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

ТDES алгоритмининг чизиқли криптоанализи

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

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

y0y1y2 y3= Sboxleft(x0 x1x2x3x4x5)

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



y1= x 2 va y2=x3 (4.1)

¾ эҳтимоллик билан бажарилади. Бунга ўхшаш аппросия тенгламаларига асосланган чизиқли таҳлилни ривожлантириш учун ушбу усулни барча роундларга кетма-кет қўллаш шарт.

Очиқ матн P = (L0,R0)дан R0=r0r1r2r3r4r5r6 r7 ўнг қисми танлаб олинади. Кейин кенгайтириш функсиясидан қуйидагига эга бўлинади
expend(R0)= expend (r0r1r2r3r4r5r6 r7)= r4r7r2r1r5r7r0 r2 r6r5r0 r3. (4.2)

3 амалий ишдаги 4-тенгламадаги F функсиянинг таърифидан, S-боксга биринчи риоунддаги кириш қийматини expand(R0) ⊕K1 тенгликдан олиш мумкин. Кейин, 4.2-тенглама ва К1 роунд калити таърифидан, чап S-боксга биринчи роундда кириш қийматини қуйидагига тенглигини кўриш мумкин



r4r7r2r1r4r5 r7⊕ k2k4k5k6k7k12.

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



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

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

ТDES алгоритмида ( DES алгоритмида бўлгани каби) S-боксдан чиқиш қийматлари олдинги қадамдаги чап ярим блоки билан ХОR амали билан қўшилади. Демак L0=l0l1l2 l3l4l5l6l7 ва R1= r’0 r’1 r’2 r’3 r’4 r’5 r’6 r’7 бўлсин, кейин бу S-боксдан биринчи роундда чиқиш қийматлари r’0 r’1 r’2 r’3 ни чап блок l0l1l2 l3 билан ХОR амали орқали қўшилади. Ушбу белгиларни 21-тенглама орқали бирлаштириб, қуйидагига эга бўлинади
r’1= r2⊕ k5⊕ l1 va r’2= r1⊕ k6⊕ l2, (4.4)

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

4.4-тенглама натижасида, барча роундлар учун 19-тенгламадагидек чизиқли аппроксия тенгламаларини тузиш мумкин. Улар қуйида 4.2-жадвалда тасвирланган. Чизиқли кириптотаҳлил бу очиқ техтни билиш хужуми (known plaintext attack) бўлгани учун, бунда ҳужумчи очиқ матнни P = p0p1..p15 ва шунга мос шифрматнни C=c0c1c2..c15 билади.

4.2-жадвалнинг охирги сатрида L4=c0c1c2c4c5c6c7 эканлиги келтирилган.

Ушбу тенгламаларни қуйидагича қайта ёзиш мумкин

k0⊕k1=c1⊕p10 (4.5)

ва

k7⊕k2=c2⊕p9 (4.6)

юқоридаги тенгламаларнинг ҳар иккаласи ҳам (¾)3 еҳтимоллик билан бажарилади. c1, c2, p9 va p10 маълумлигидан, k0, k1, k2 ва k7 калит битлари ҳақида баъзи маълумотларга эга бўлинади.

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 =p0p1p2..p15 ва унга мос шифрмат C=c0c1c2..c15 берилган бўлсин. Ҳар бир жуфтлик учун increment қийматини қуйидагиларга қараб мос равишда амалга ошириб, ушбу

c1⊕p10=0 ёки c1⊕p10=1

ёки ушбу тенглама бажарилади



c2⊕p9=0 yoki c2⊕p9=1.

100 та танлаб олинган очиқ матнлардан фойдаланилганда қуйидаги натижалар олинган:



c1⊕p10=0 38 марта бажарилди

c1⊕p10=1 62 марта бажарилди

c2⊕p9=0 62 марта бажарилди

c2⊕p9=1 38 марта бажарилди.

Ушбу ҳолатдан, қуйидаги ҳулосага келиш мумкин. 23-тенгламадан келиб чиқиб катта 62% ли эҳтимолликни инобатга олиб



k0⊕k1=1

ва 24-тенглама катта 62% ли эҳтимоллик билан қуйидагига тенг



k7⊕k2=0

Ушбу мисолда ҳақиқий калит



K = 1010 0011 0101 0110,

ва бундан k0⊕k1=1 ёки k0⊕k1=0 осонлик билан аниқланадики. Бу чизиқли ҳужум орқали аниқланди.

Юқоридаги чизиқли криптоанализда калит маълумотининг икки битини тиклаш келтирилган. Бутун К калитни қайта тиклаш учун қолган номаълум битларни ҳам тўлиқ аниқлаш керак. Бу тахминан 213 та шифрлашни бажариш ва чизиқли криптоанализни амалга оширишни талаб қилади. Бу ҳужум жуда муҳим аҳамиятга эга бўлмаса ҳам самарали ҳужум ҳисобланади, шунинг учун қилинган таҳлил ТDES алгоритмининг хавфсиз алгоритм эмаслигини кўрсатди.
Топшириқ


Сатр

Устун


00

01

10

11

0

10

01

11

00

1

01

10

11

01

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


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

javob

  1. Чизиқли криптоанализ усулининг моҳиятини тушунтиринг.


Чизиқли криптоанализ усули. Замонавий чизиқли криптоанализ усули Япониялик криптограф M.Matsui томонидан 1993 йилда DES шифрлаш алгоритмига қарши ҳужум тури сифатида ишлаб чиқилган.

Ушбу криптоанализ усулининг моҳияти танлаб олинган очиқ матн M ва мавжуд шифрматн C битларини XOR амали ёрдамида қўшиш ва натижада калит битларини аниқлашдан иборат:

𝑀[𝑖1, 𝑖2, … . 𝑖𝑛 ) ⊕ 𝐶[𝑗1,𝑗2, … .𝑗𝑛 ] = 𝐾[𝑘1, 𝑘2, … . 𝑘𝑛],

бу ерда 𝑀[𝑖1, 𝑖2, … . 𝑖𝑛 ) = 𝑀[𝑖1 ) ⊕ 𝑀[𝑖2 ) ⊕ …. 𝑀[𝑖𝑛 )

С[𝑖1, 𝑖2, … . 𝑖𝑛 ) = С[𝑖1 ) ⊕ С[𝑖2 ) ⊕ …. С[𝑖𝑛 )

𝐾[𝑖1, 𝑖2, … . 𝑖𝑛 ) = 𝐾[𝑖1 ) ⊕ 𝐾[𝑖2 ) ⊕ …. 𝐾[𝑖𝑛 )

Натижада юқоридаги тенгликдан энг яқин чизиқли аппроксимацияни аниқлаш, яъни таҳлил қилинаётган алгоритм акслантиришлари хоссаларидан келиб чиқиб, энг самарали чизиқли боғланишни танлашдан иборат. Танланган аппроксимация тенгламаларида тенгликнинг чап томонининг қиймати 0 ёки 1 эканлигини аниқлаш учун етарлича кўп миқдордаги очиқ матн ва шифр матн жуфтликлари устида статистик таҳлил олиб бориш керак бўлади. Натижада, фақат калит битлари иштирок этган тенгламалар системасига эга бўлинади. Ушбу тенгламалар системасини ечиш орқали калит битларини аниқлаш мумкин бўлади.


  1. TDES алгоритмининг чизиқли қриптоанализи қандай аималга оширилади?

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

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

y0y1y2 y3= Sboxleft(x0 x1x2x3x4x5)

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



y1= x 2 va y2=x3 (4.1)

¾ эҳтимоллик билан бажарилади. Бунга ўхшаш аппросия тенгламаларига асосланган чизиқли таҳлилни ривожлантириш учун ушбу усулни барча роундларга кетма-кет қўллаш шарт.

Очиқ матн P = (L0,R0)дан R0=r0r1r2r3r4r5r6 r7 ўнг қисми танлаб олинади. Кейин кенгайтириш функсиясидан қуйидагига эга бўлинади
expend(R0)= expend (r0r1r2r3r4r5r6 r7)= r4r7r2r1r5r7r0 r2 r6r5r0 r3. (4.2)

3 амалий ишдаги 4-тенгламадаги F функсиянинг таърифидан, S-боксга биринчи риоунддаги кириш қийматини expand(R0) ⊕K1 тенгликдан олиш мумкин. Кейин, 4.2-тенглама ва К1 роунд калити таърифидан, чап S-боксга биринчи роундда кириш қийматини қуйидагига тенглигини кўриш мумкин



r4r7r2r1r4r5 r7⊕ k2k4k5k6k7k12.

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



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

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

Do'stlaringiz bilan baham:



Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling