ЎЗБЕКИСТОН РЕСПУБЛИКАСИ АХБОРОТ ТЕХНОЛОГИЯЛАРИ

ВА КОММУНИКАЦИЯЛАРИНИ РИВОЖЛАНТИРИШ ВАЗИРЛИГИ

ТОШКЕНТ АХБОРОТ ТЕХНОЛОГИЯЛАРИ УНИВЕРСИТЕТИ

«Криптология ва дискрет математика» кафедраси

“Амалий криптоанализ УСУЛЛАРИ”

фанидан

5А330501 – Компьютер инжиниринги (“Ахборот хавфсизлиги, криптография ва криптоанализ”) мутахассислиги талабалари

учун амалий машғулотларни бажаришга

УСЛУБИЙ КЎРСАТМА

Tошкент – 2016

Ушбу услубий кўрсатма компьютер тармоқлари ва тизимларида ахборотларни ҳимоялаш учун қўлланиладиган бардошли криптографик алгоритмлар  яратиш бўйича истиқболли масалаларни  ўз ичига қамраб олади. Бу фанни ўқитишдан мақсад талабаларда криптографик алгоритмларнинг бардошлилигини оширишни таъминлаш билан боғлиқ масалаларни ечишда замонавий криптоанализ усулларининг ўрни ва истиқболли йўналишлари профилига мос билим, кўникма ва малакани шакллантиришдир.

Тузувчилар:
Ахмедова О.П.	«Криптология ва дискрет математика» кафедраси мудири
Тақризчилар:
Расулов О.Х.		“UNICON.UZ” ДУК Ахборот хавфсизлиги ва криптология илмий-тадқиқот департаменти  бошлиғи
Ганиев А.А.		ТАТУ, “Ахборот хавфсизлигини   таъминлаш” кафедраси мудири, т.ф.н.

Ушбу услубий кўрсатма “Криптология ва дискрет математика” кафедраси мажлисида кўриб чиқилган ва маъқулланган.

(___  _________ 2016 йил _____-баённома)

Услубий кўрсатма “Ахборот хавфсизлиги” факультетининг илмий-услубий кенгашида тасдиқланган.

(___  _________ 2016 йил _____-баённома)

Услубий кўрсатма Тошкент ахборот технологиялари университети илмий-услубий кенгашида тасдиқланган.

(___  _________ 2016 йил _____-баённома)

ÓТошкент ахборот технологиялари университети, 2016 й.

1-АМАЛИЙ МАШҒУЛОТ

Мавзу: Классик шифрларнинг криптоанализи: Цезарь ва Атбаш шифрлари

Ишдан мақсад: Ушбу амалий машғулотни бажариш жараёнида классик шифрларни криптоанализ жараёни бўйича назарий ва амалий маълумотларга эга бўлиш.

Назарий қисм

Атбаш шифридан фойдаланиб шифрматн яратишда дастлабки матнга тегишли алифбонинг биринчи ҳарфи охиргисига, иккинчи ҳарфи ундан аввалгисига ва ҳ.к. алмаштирилган (1-расм).

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

Z

Y

X

W

V

U

T

S

R

Q

P

O

N

M

L

K

J

I

H

G

F

E

D

C

B

A

1-расм. Атбаш усулида шифрлаш

Цезарь шифрида дастлабки матннинг қандай берилиши аҳамиятга эга эмас. Цезарь усулида шифрлаш дастлабки матнга тегишли алифбо ҳарфи ўрнига шифрлаш калити k қадамга сурилган ўринда жойлашган алифбо ҳарфини қўйиш асосида амалга оширилади. Бунда суриш алифбо ҳарфлари сони 26 га тенг бўлган модуль бўйича бажарилади. Алифбо ҳарфлари бошидан охири томон, охиридан қайта бош томондан бошлаб даврий равишда суриб борилади.

Масалан, k=3 ҳол учун қуйидаги кўринишга эга бўламиз:

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

2-расм. Цезарь усулида шифрлаш

Ишни бажариш учун вазифа ва топшириқлар

1. Цезарь шифрининг моҳиятини тушунган ҳолда бирор бир хабарни шифрланг ва шифрланган хабарни криптоанализ қилиш учун 3-томонга беринг.

2. Цезарь усулида шифрланган қуйидаги шифрматннинг очиқ матнини топинг: FTQYBRTQUHKHMGBABFHRTETLA.

3. Атбаш шифрининг моҳиятини тушунган ҳолда бирор бир хабарни шифрланг ва шифрланган хабарни криптоанализ қилиш учун                 3-томонга беринг.

4. Атбаш усулида шифрланган қуйидаги шифрматннинг очиқ матннини  топинг: EZGZMNZQWZTLSPZYRNFJZWWZHWRI.

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

1. Цезарь шифрини калитни билмаган ҳолда қанча вариантда ошиш мумкин?

2. Атбаш усули ёрдамида шифрланган матнни калитни билмаган ҳолда қанча вариантда ошиш мумкин?

Фойдаланилган адабиётлар

1. Хасанов П., Хасанов Х., Ахмедова О., Давлатов А. Криптоанализ ва унинг махсус усуллари. Ўқув қўлланма.– Тошкент, 2010.

2. Акбаров Д.Е. Ахборот хавфсизлигини таъминлашнинг криптографик усуллари ва уларнинг қўлланишлари. Тошкент. ”Ўзбекистон маркаси “, 2009.

3. Арипов М.М., Пудовченко Ю.Е. Основы криптологии.- Ташкент: 2004.

2-АМАЛИЙ МАШҒУЛОТ

Мавзу: Полибий ва Вижинер шифрининг криптоанализи

Ишдан мақсад: Ушбу амалий машғулотни бажариш жараёнида Полибий ва Вижинер шифрининг криптоанализи жараёни бўйича назарий ва амалий маълумотларга эга бўлиш.

Назарий қисм

Милоддан аввалги II асрда қадимги Грецияда “Полибий квадрати”  деб аталмиш шифр машҳур бўлган. Шифрлаш жадвали 5 та сатр ва 5 та устундан тузилган бўлиб, улар 1 дан 5 гача рақамлар билан белгиланган ва жадвал хоналарида 25 та ҳарф жойлашган.

	A	B	C	D	E
A	A	B	C	D	E
B	F	G	H	I	K
C	L	M	N	O	P
D	Q	R	S	T	U
E	V	W	X	Y	Z

Шифрматн дастлабки матнга тегишли жадвал хонасидаги ҳарфларни сатр ва устун рақамлари жуфтлиги билан алмаштириш натижасида ҳосил этилган. Шифрлаш жадвалида ҳарфларнинг жойлашиш тартиби шифрлаш калити вазифасини ўтаган. 

Виженер тизими ҳам Цезарь тизимига ўхшаш бўлиб, унда калит қадам-бақадам ўзгаради. Шифрматн ҳосил қилиш ва уни дастлабки матнга ўгиришда Виженер квадратидан фойдаланилади. Ҳар бир устун 0,1,2,..,25 калитли Цезарь тизими каби қаралиши мумкин. Шифрлаш учун дастлабки матн ҳарфлари квадрат жадвал сатридан Цезарь тизими калитини эса квадрат жадвал устунидан ўқилади.

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

R

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

S

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

T

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

U

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

V

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

W

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

1-расм.  Виженер квадрати

Ишни бажариш учун вазифа ва топшириқлар

1. Полибий шифрининг моҳиятини тушунган ҳолда бирор бир хабарни шифрланг ва шифрланган хабарни криптоанализ қилиш учун 3-томонга беринг.

2. Полибий усулида шифрланган қуйидаги шифрматннинг очиқ матнини топинг: ADAAEACAADD.

3. Вижинер шифрининг моҳиятини тушунган ҳолда бирор бир хабарни шифрланг ва шифрланган хабарни криптоанализ қилиш учун 3-томонга беринг.

4. Вижинер усулида INSON калит сўз билан шифрланган қуйидаги шифрматнни топинг: ANQZBDQXOBTDSHAIFZWAO

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

1. Полибий усулида калитни билмаган ҳолда қанча вариантда ошиш мумкин?

2. Вижинер усулида шифрланган матнни калитни билмаган ҳолда қанча вариантда ошиш мумкин?

Фойдаланилган адабиётлар

1. Хасанов П., Хасанов Х., Ахмедова О., Давлатов А. Криптоанализ ва унинг махсус усуллари. Ўқув қўлланма.– Тошкент, 2010.

2. Акбаров Д.Е. Ахборот хавфсизлигини таъминлашнинг криптографик усуллари ва уларнинг қўлланишлари. Тошкент. ”Ўзбекистон маркаси “, 2009.

3. Арипов М.М., Пудовченко Ю.Е. Основы криптологии.- Ташкент: 2004.

3-АМАЛИЙ МАШҒУЛОТ

Мавзу: Евклиднинг умумлашган алгоритми, модул арифметикаси

Ишдан мақсад: Ушбу амалий машғулотни бажариш жараёнида Полибий ва Вижинер шифрининг криптоанализи жараёни бўйича назарий ва амалий маълумотларга эга бўлиш.

Назарий қисм

Берилган а ва b сонларни бўлувчи бутун сон, уларнинг умумий бўлувчиси дейилади.  Умумий бўлувчилар ичида энг каттаси энг катта умумий бўлувчи (EКUB) дейилади ва EКUB(а, b) кўринишда белгиланади. Агарда а ва b сонларнинг энг катта умумий бўлувчиси 1, EКUB (а, b)=1 бўлса,  а ва b сонлар ўзаро туб дейилади. Энг катта умумий бўлувчиларни топишга оид тасдиқларни келтирамиз.

1-лемма. Агар b сони а сонини бўлса, у ҳолда бу сонларнинг энг катта умумий бўлувчиси EКUB (а, b)= b, яъни а сонининг умумий бўлувчилари тўплами b сонининг умумий бўлувчилари тўплами билан устма-уст тушади.

2-лемма. Агар a=bq+c бўлса, у ҳолда а ва b сонларининг энг катта умумий бўлувчиси b ва с сонларининг энг катта умумий бўлувчиси билан устма-уст тушади, яъни EКUB (a, b)= EКUB (b, c):  а ва b сонларининг умумий бўлувчилари тўплами b ва с  сонларининг умумий бўлувчилари тўплами билан устма-уст тушади.

Юқорида келтирилган леммалардан EКUBни топиш – Евклид алгоритми келиб чиқади.

Ҳақиқатан ҳам қуйидаги бўлиш амалларини бажарамиз: 

a=bq₁+r₁,            0 r₁<b,

b=r₁q₂+r₂,       0 r₂<r₁,

…………,        …………,

r_n-2=r_n-1 q_n+r_n,       0 r_n<r_n-1,

  r_n-1 =r_nq_n+1.

У ҳолда EКUB (a, b)= EКUB (b, r₁)=…=(r_n-2, r_n-1)= r_n  .

Берилган натурал сон p>1 туб дейилади, агарда бу сон ўзи p ва 1 дан бошқа натурал сонга бўлинмаса. Мисол учун: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ..., туб сонлар, улар саноқли ва чексиз қувватли тўпламни ташкил этади.

Келгусида барча бутун сонларни модуль (характеристика) деб аталувчи бирор фиксирланган натурал n сонига бўлганда қоладиган қолдиқлар билан боғлиқ ҳолда қараймиз. Бунда чексиз қувватли (элементлари сони чексиз) бўлган барча бутун сонлар тўпламига, 0 дан n-1 гача бўлган бутун сонларни ўз ичига оладиган чекли, қуввати  n га тенг бўлган {0; 1; 2; 3;…;n-1} – тўплам мос қўйилади.  Бу қуйидагича амалга оширилади: а ва n – натурал сонлар бўлса, “а сонини n сонига қолдиқ билан бўлиш”, деганда ушбу

а=qn+r,    бу ерда 0 r <n,

шартни қаноатлантирувчи натурал  q ва r сонларини топиш тушунилади. Бу охирги тенгликда қолдиқ деб аталувчи r сони нолга тенг бўлса r=0, натурал а сони n сонига бўлинади ёки n сони  а сонининг бўлувчиси дейилади.

Бутун a ва b сонлари модуль n бўйча таққосланадиган дейилади, агарда уларни  n га бўлганда қоладиган қолдиқлари тенг бўлса,

ab(mod n)

деб ёзилади. Бундан эса a ва b сонлар айирмасининг n га қолдиқсиз бўлиниши келиб чиқади.

Қолдиқни ифодалаш учун ушбу

b=a (mod n)

тенгликдан фойдаланилади ҳамда b=a (mod n) тенгликни қаноатлантирувчи b сонини топиш a сонини модуль  n бўйича келтириш дейилади.

Ихтиёрий бутун b сони учун ушбу

M={a₀ ,a₁ ,…, a_n-1 Z:  0 a_k ; k=0,1,…,n-1}

тўпламга тегишли a_kb (mod n) муносабатни қаноатлантирувчи сон a_k , k{0,1,…, n-1} мавжуд бўлса, тўплам M модуль n бўйича тўлиқ чегирмалар синфи дейилади. Кўриниб турибдики, тўлиқ чегирмалар синфи

M={a₀ ,a₁ ,…, a_n-1 Z:  0 a_k ; k=0,1,…,n-1} ={0,1, …,n-1}.

Бирор n модуль бўйича қўшиш, айириш ва кўпайтириш амалларига нисбатан қуйидаги коммутативлик, ассоциативлик ва дистрибутивлик муносабатлари ўринли:

(a+b)(mod n)=((a mod n)+(b mod n))(mod n),

(a-b)(mod n)=((a mod n)-(b mod n))(mod n),

(ab)(mod n)=((a mod n) (b mod n))(mod n),

a(b+c)(mod n)=(((ab) mod n)+(ac) mod n))(mod n).

Ишни бажариш учун вазифа ва топшириқлар

1. 1000 гача бўлган сонлар ичида туб ва ўзаро туб сонларни аниқланг.

2. Леммалар  асосида Евклид алгоритмини келтириб чиқаринг.

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

1. Евклиднинг умумлашган алгоритмининг моҳиятини тушунтиринг.

2. Модул арифметикасида қандай муносабатлар  қаноатлантирилади? 

Фойдаланилган адабиётлар

1. Акбаров Д., Хасанов П., Хасанов Х., Ахмедова О. Криптографиянинг математик асослари. Ўқув қўлланма.– Тошкент, 2010.

2. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии. Учебное пособие. — М.: Гелиос-АРВ, 2001.

3. Акбаров Д.Е. Ахборот хавфсизлигини таъминлашнинг криптографик усуллари ва уларнинг қўлланишлари. Тошкент. ”Ўзбекистон маркаси “, 2009.

4. Венбо Мао. Современная криптография. Теория и практика. – Москва - Санкт-Петербург - Киев: Лори Вильямс, 2005.

4-АМАЛИЙ МАШҒУЛОТ

Мавзу: Криптоанализнинг универсал усуллари: тўлиқ танлаш усули, калит бўйича ҳужум

Ишдан мақсад: Ушбу амалий машғулотни бажариш жараёнида частотавий анализ ва Поллард усуллари бўйича назарий ва амалий маълумотларга эга бўлиш.

Назарий қисм

Тўлиқ танлаш, яъни калитларнинг барча мумкин бўлган вариантларини танлаш усули, криптотаҳлилчининг носимметрик криптотизим  алгоритмини ва ошкора калитни билган ҳолда барча мумкин бўлган калитларни танлаш ва синаб кўришга асосланади. Симметрик криптотизимларда ҳам шифрматн ва очиқ матн асосида тўлиқ танлаш усули қўлланилади. Криптотаҳлилчилар кўпинча компьютер ёрдамида калитларни тўлиқ танлаш усулидан фойдаланиб шифрларни ошкор этадилар. Криптотаҳлил жараёнида миллиард калитларни  секундига минглаб калит тезликда танлашга тўғри келади.

Фараз қилинсин, бузғунчи учун бир ёки бир неча (x, y) жуфтлик маълум бўлсин. Осонлик учун ҳар қандай жуфтлик (x, y) учун E_k(x)=y муносабатни қаноатлантирувчи ягона k  калит мавжуд бўлсин. Мумкин бўлган калитлар тўпламини тартибга солинади ва K даги калитларни кетма-кет равишда E_k(x)=y тенглик бажарилишига текшириб чиқилади. Агар  kÎK  калитнинг бир вариантини текшириш бир амал ёрдамида ҳисобланса, унда калитларни тўлиқ танлаш учун |K| амал талаб этилади.  Бунда                         |K| - тўпламдаги элементлар сони. Шифрлаш схемасида калит тасодифий ва тенг эҳтимоллик билан K тўпламдан танланган бўлсин. Бунда калит 1/|K| эҳтимоллик билан билан топилади ва тўлиқ танлаш усулининг иш ҳажми 1 га тенг бўлади.

Мисол учун шахсий калит узунлиги 100 бит бўлса, унда барча  шахсий калитлар сони   2¹⁰⁰ га тенг, яъни калитлар тўплами қуввати |K|=2¹⁰⁰. Шахсий калит узунлиги 56 бит бўлганда, барча мумкин бўлган шахсий калитлар сони |K|=2⁵⁶» 0.5*10¹⁷ га тенг. Бунда, агар  ҳисоблаш қурилмаси ҳар битта махфий калитга мос ошкора калитни ҳисоблаш ва уни ҳеч қийинчиликсиз таққослаш учун 10^-6 секунд вақт сарфласа, 24 соатда  барча калитларни синаб чиқиш учун 5.787*10⁵ та ЭҲМ керак бўлади.

Шунинг учун ҳам шахсий ва шифрлашда фойдаланиладиган калитни топишни мураккаблаштириш мақсадида шахсий калитлар узунлиги 127-159 битдан  катта бўлган узунликда генерацияланади.

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

Симметрик криптотизимларда фойдаланиш учун мўлжалланган сифатли калит тасодифий иккилик тўпламини ифодалайди. Агар  n разрядли калит талаб этилса, калитни  генерациялаш жараёнида мумкин бўлган 2ⁿ вариантлардан бир хил эҳтимоллик билан  танлаб олиш керак.

Носимметрик криптотизимларда фойдаланиш учун мўлжалланган сифатли калитларни генерациялаш  эса анча қийин жараён бўлиб, юқорида айтилганидек бу тизимда фойдаланиладиган калитлар муайян математик хоссаларга эга бўлиши лозим. Масалан, RSA тизимида шифрлаш модули иккита катта туб сонларнинг кўпайтмаси кўринишида бўлади.

 Псевдотасодифий генераторлар ёрдамида бардошли криптотизимларни яратиш мумкин. Яхши тасодифий сон генераторлари   ишлаб чиқишда мураккаб бўлиб, уларнинг ишончлилиги аппарат ва дастурий таъминотнинг афзаллигига боғлиқ бўлади.

Ишни бажариш учун вазифа ва топшириқлар

1. Шахсий калит узунлиги 228 бит бўлганда, барча мумкин бўлган шахсий калитлар сони ва барча калитларни синаб чиқиш учун кетадиган вақтни ҳисобланг. 

2. RSA тизимида шифрлаш модули иккита катта туб сонларнинг кўпайтмаси  бўлса, туб кўпайтувчиларни топишга доир мисоллар келтиринг.

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

1. Тўлиқ танлаш усулининг моҳияти нимадан иборат?  

2. Калит бўйича ҳужум қандай амалга оширилади?

Фойдаланилган адабиётлар

1. Хасанов П., Хасанов Х., Ахмедова О., Давлатов А. Криптотаҳлил ва унинг махсус усуллари. Ўқув қўлланма.– Тошкент, 2010.

2. Авдошин С.М., Савельева А.А. «Криптоанализ: современное состояние и перспективы развития», Государственный университет – Высшая Школа Экономики.

3. Жуков А.Е. «Криптоанализ по побочным каналам (Side Channel Attacks)», Пособие  по курсу «Криптографические методы защиты информации» Москва – 2004.

5-АМАЛИЙ МАШҒУЛОТ

Мавзу: Частотавий анализ усули, Поллард усули

Ишдан мақсад: Ушбу амалий машғулотни бажариш жараёнида частотавий анализ ва Поллард усуллари бўйича назарий ва амалий маълумотларга эга бўлиш.

Назарий қисм

Частотавий, яъни статистик  характеристикалар усулида  симметрик ёки носимметрик криптотизим криптотаҳлилчиси шифрматндаги белгилар, ҳарфлар, сўзларнинг такрорланишлари сонини (частоталарини) ҳисоблаб,   очиқ  матн қайси тилда ёзилганини аниқлайди. Сўнгра эса, шифрматн шифр белгилари параметрларини очиқ  матн қайси тилда ёзилган бўлса, шу тилнинг параметрлари билан солиштиради. Масалан, инглиз тилида E ҳарфи частотаси юқори, шифрматнда L ҳарфи частотаси юқори. Шифрматндаги L ҳарфини E ҳарфи билан алмаштирилади, яъни шифрматн ва очиқ матн ёзилган тил частоталарини камайиш тартибида ёзиб, тартиби тўғри келган белгилар ўзаро алмаштирилади. Кейин шифрматн биграмма, триграмма ва          k-граммаларининг такрорланишлар сонини топиб, очиқ матн ёзилган тил биграмма, триграмма ва k-граммалари билан мос ҳолда  алмаштиради. Биграмма, триграмма, k-грамма деганда, матнда иккита, учта ва k-та белгининг кетма-кет келиши тушунилади. Масалан, инглиз тилида th, in,  is, er, he, en, биграммалари, рус тилида ст, но, ен, то, на биграммалари, сто, ено, нов, тов, ова триграммалари кўп учрайди. Қуйидаги 1-жадвалда  рус тили ҳарфларининг пайдо бўлишининг нисбий частотаси келтирилган

1-жадвал

Рус тили ҳарфларининг пайдо бўлишининг нисбий частотаси

Ҳарф	Частота	Ҳарф	Частота	Ҳарф	Частота	Ҳарф	Частота
о	0.09	о	0.038	о	0.016	о	0.007
е,ё	0.072	л	0.035	ы	0.016	ш	0.006
а	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	х	0.009

Юқорида айтиб ўтилган принциплар ҳозирги кунда кенг тарқалган  паролларни танлаш бўйича дастурларда қўлланилади. Паролларни танлаш бўйича дастур аввало эҳтимоллиги катта бўлган паролларни танлайди. эҳтимоллиги кичик бўлган паролларни кейинга олиб қўяди. Бунда паролларни танлаш жараёни ўн ва юз мартталаб камаяди. Қуйидаги                       2-жадвалда паролларни танлашда олинган қатор натижалар келтирилган.

  2-жадвал

Паролларни танлаш натижалари

Танлаш мураккаблиги	Танлаш вақти	Процессор  тури
2,08⋅10^11	15 минут	486DX/4-100
5,68⋅10^10	8 соат	Pentium-120

Поллард усули график шаклда "ўртада учрашиш" усулига бироз ўхшашдир. Унда "тасодифий акслантириш графида учрашиш" масаласи ечилади. Бу ерда ҳам иккита графнинг бошланғич тугунларидан чиқиб токи илдиз тугунидан ўтувчи цикл ҳосил бўлгунча қарама-қарши йўналишда ҳаракат давом этади. Учрашиш мураккаблиги , якуний мураккаблик .

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

Дискрет логарифмлаш масаласига тадбиқан бу усул аввалги "ўртада учрашиш"  усулига нисбатан катта хотирадан воз кечиш имконини яратади. МБни сортлаш зарурати ҳам йўқолади. Шу туфайли вақт бўйича мураккаблик 0(log#M) марта кам бўлиб, мураккаблик  қадам, хотира ҳажми О(1) блокдан иборат.

Ишни бажариш учун вазифа ва топшириқлар

1. Частотавий анализ усули асосида шифрматнни криптоанализ қилинг.

2. Поллард усули асосида маълумотни криптоанализ қилинг.

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

1. Частотавий анализ усулининг моҳияти нимадан иборат?  

2. Поллард усули қандай муаммоларни ҳал этишда қўлланилади? 

Фойдаланилган адабиётлар

1. Хасанов П., Хасанов Х., Ахмедова О., Давлатов А. Криптотаҳлил ва унинг махсус усуллари. Ўқув қўлланма.– Тошкент, 2010.

2. Авдошин С.М., Савельева А.А. «Криптоанализ: современное состояние и перспективы развития», Государственный университет – Высшая Школа Экономики.

3. Жуков А.Е. «Криптоанализ по побочным каналам (Side Channel Attacks)», Пособие  по курсу «Криптографические методы защиты информации» Москва – 2004.

6-АМАЛИЙ МАШҒУЛОТ

Мавзу: «Ўртада учрашиш» усули, хэш-функция коллизияси усули

Ишдан мақсад: Ушбу амалий машғулотни бажариш жараёнида «ўртада учрашиш» ва хэш-функция коллизияси усуллари бўйича назарий ва амалий маълумотларга эга бўлиш.

Назарий қисм

Агар криптоалгоритмнинг махфий калитлар тўплами композиция амалига нисбатан берк бўлса, яъни ҳар қандай икки калит z_i ва z_j учун шундай калит z_k топилсинки, ҳар қандай матни кетма-кет z_i ва z_j калитларида шифрлаш натижаси шу матнни z_k билан шифрланган матнга айнан бўлсин, яъни

F(z_j, F(z_i, x))=F(z_k, x).

Унда бу хоссадан фойдаланиб, шифрлаш калитини топиш мумкин, яъни z_k ни топиш учун эквивалент жуфтлик < z_i,  z_j > ни топиш кифоя. Бу усул "туғилган кунлар парадокси"га асосланади. Маълумки, туғилган кунлар текис тақсимланган деб ҳисобланса, 24 кишилик гуруҳда р=0,5 эҳтимоллик билан икки кишининг туғилган куни бир хил чиқади.

Умумий ҳолда бу парадокс қуйидагича ифодаланади: агар аn предметлар n та предмет орасидан қайтарилиш билан танланса, икки предметнинг бир хил бўлиш эҳтимоли

.

Фараз қилинсинки, очиқ матн х ва у нинг шифрограммаси у маълум.                   х учун тасодифий тарзда калитлар тўплами z_l ва шифрограммалар w=F(z_l, x) тўпламини сақловчи маълумотлар базаси (МБ) тузамиз ва шифрограммаларни w бўйича тартибга соламиз. МБ ҳажмини 0((p#{z}) га тенг қилиб оламиз.

Сўнгра тасодифан z_l1 калитни олиб, у шифрматнни очамиз ва натижа v=F(z_l1,у) ни МБ билан таққослаймиз. Агар v бирор w билан тенг чиқса, калит z_ll изланган калит z га эквивалент.

Вақт бўйича усул мураккаблиги

.

Кўпайтувчи log#{z} саралаш мураккаблигини ҳисобга олади.

Зарур хотира 0((р #{z}log#{z}) бит ёки 0((р #{z}) блокдан иборат. Блок узунлиги ва калит узунлиги чекланган доимийга фарқ қилади деб фараз қилинади.

Маълумотни узатишда ёки сақлашда унинг  тўлалигини назорат қилиш учун ҳар бир маълумотнинг  хэш-қиймати ҳисобланади ва бу қиймат маълумот билан бирга сақланади ёки узатилади. Хэш-функцияларга қилинадиган асосий ҳужум бу коллизияни ҳосил қилишдир. Қўлга тушган х ва y≠х матнлар учун Н(х)≠H(y)  бўлиши - коллизияга бардошлилик хоссасидир.

“Туғилган кун парадокси”га асосланган криптоҳужум                            хэш-функцияларда коллизияларни топиш учун ишлатиладиган асосий криптоҳужумлардан биридир. Бу криптоҳужумга асосан хэш-қиймат берилганда унга мос бўлган маълумотни танлашнинг мураккаблиги О(2ⁿ) катталик билан, маълумот ва унинг хэш-қиймати берилганда, хэш-қиймати шунга тенг бўладиган бошқа маълумотни танлашнинг мураккаблиги О(2^n/2) катталик билан баҳоланади. Н(х)=H(y)  кўринишдаги иккита маълумотни “ўртада учрашиш” ёки Поллард усулидан фойдаланиб топиш мумкин.

Ишни бажариш учун вазифа ва топшириқлар

1. «Ўртада учрашиш» усули  асосида шифрматнни криптоанализ қилинг.

2. Хэш-функция коллизияси усули асосида маълумотни криптоанализ қилинг.

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

1. «Ўртада учрашиш» усулининг моҳияти нимадан иборат?  

2. Хэш-функция коллизияси усули қандай ҳолларда қўлланилади? 

Фойдаланилган адабиётлар

1. Хасанов П., Хасанов Х., Ахмедова О., Давлатов А. Криптотаҳлил ва унинг махсус усуллари. Ўқув қўлланма.– Тошкент, 2010.

2. Авдошин С.М., Савельева А.А. «Криптоанализ: современное состояние и перспективы развития», Государственный университет – Высшая Школа Экономики.

3. Жуков А.Е. «Криптоанализ по побочным каналам (Side Channel Attacks)», Пособие  по курсу «Криптографические методы защиты информации» Москва – 2004.

7-АМАЛИЙ МАШҒУЛОТ

Мавзу: Дискрет логарифмлаш муаммосига асосланган криптотизимлар криптоанализи

Ишдан мақсад: Ушбу амалий машғулотни бажариш жараёнида дискрет логарифмлаш муаммосига асосланган криптотизимлар криптоанализи усуллари бўйича назарий ва амалий маълумотларга эга бўлиш.

Назарий қисм

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

Ҳозирги кунда энг самарали ҳисобланган криптотаҳлил алгоритмлари субэкспоненциал мураккабликка эгадир. Бу алгоритмлар “index-calculus” (индексли ҳисоблаш) алгоритмлари бўлиб, фактор базасини қуришга асосланган.

Туб майдонда дискрет логарифмлаш учун биринчи субэкспоненциал алгоритм Леонард Адлеман томонидан таклиф этилган. Бироқ амалиётда бу алгоритм етарли даражада самарали бўлиб чиқмаган. Дон Копперсмит, Эндрю Одлижко ва Ричард Шреппель дискрет логарифмлаш учун “COS” номи остида субэкспоненциал алгоритмнинг ўз русумларини таклиф этдилар. Оливер Широкаур томонидан таклиф этилган сонли майдон ғалвири алгоритми p>10¹⁰⁰ бўлганда COS алгоритмининг барча модификацияларига нисбатан самаралироқ ишлайди. Сонли майдон умумлашган ғалвир усулининг мураккаблиги C=O(exp(c(ln p)^1/3 (ln ln p)^2/3)) амал билан баҳоланади, бу ерда с»1,92 .

Фараз қилинсинки, G - мультипликатив Абель группаси бўлсин. a асос бўйича дискрет логарифм b ни ҳисоблаш, шундай xÎG ни топишга келтириладики, a^x=b бўлсин. Дискрет логарифмнинг хоссалари ҳақиқий сонлар майдонидаги одатдаги логарифм хоссаларига кўп жиҳатлардан  ўхшаш. Масалан,

log_a (h*j)≡ log_a (h)+ log_a (j) (mod │G│)

кўринишдаги айният кучга эга, бу ерда │G│- группанинг тартиби,                     a -ҳосил қилувчи (генератор).

Индексли ҳисоблаш усулининг асосий ғояси шундаки, агар чекли майдон Z_p нинг баъзи элементлари учун

∏^m_i=1x_i≡∏^m_j=1y_j

 бўлса, унда

∑^m_i=1log _ax_i≡∑^m_j=1log _ay_j mod (p-1).

Охирги таққосламалардан бир қанчасини ҳосил қилингач,                             log _ax_i ва ₁log _ay_j  номаълумларга нисбатан чегирмалар ҳалқаси Z_p-1 да унча кўп номаълумларга эга бўлмаган тенгламалар системасини тузиш ва ҳал этиш мумкин. Шуни унутмаслик керакки, охирги таққосламада, ҳеч бўлмаганда log_ag қиймати маълум бўлган битта элемент g қатнашиши шарт.

Охирги таққосламани генерация қилишнинг энг осон усули, бу бирор gÎ Z_p ни танлаш, u=a^g (mod p) ҳисоблаш ва кетма-кет танлаш усулида

u=∏^k_i=1p^αi _i

муносабатни қаноатлантирувчи сонларни топишдир. Бу ерда p_i - В дан кичик туб сонлар. Агар шундай сонларни топишнинг иложи бўлса, унда u силлиқлик чегараси В га эга бўлган силлиқ элементдир.

Дискрет логарифмлаш алгоритмида ҳам факторлаш алгоритмига ўхшаш икки босқич кўзга ташланади:

- биринчи, тайёрланиш босқичида бирор чегара В танланади ва фактор базаси ва бу база асосида тенгламалар системаси шакллантирилади;

- иккинчи босқичда тенгламалар системасининг ечими топилади.

Шундай қилиб, дискрет логарифмлашнинг барча усуллари ҳам охир оқибатда тенгламалар системасини ҳал қилишга келтирилади.

Ишни бажариш учун вазифа ва топшириқлар

1. Индексли ҳисоблаш усули асосида  дискрет логарифмлаш муаммосини кичик сонлар учун ҳал этинг.

2. Қуйидагилар учун дискрет логарифмлаш масалалари ҳал этилсин:

3^x=7(mod 13).

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

1. Дискрет логарифм муаммосига таъриф беринг.

2. Замонавий дискрет логарифмлаш усулларига қандай усуллар киради?

Фойдаланилган адабиётлар

1. Хасанов П., Хасанов Х., Ахмедова О., Давлатов А. Криптоанализ ва унинг махсус усуллари. Ўқув қўлланма.– Тошкент, 2010.

2. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии. Учебное пособие. — М.: Гелиос-АРВ, 2001.

3. Авдошин С.М., Савельева А.А. «Криптоанализ: современное состояние и перспективы развития», Государственный университет – Высшая Школа Экономики.

4. Венбо Мао. Современная криптография. Теория и практика. – Москва - Санкт-Петербург - Киев: Лори Вильямс, 2005.

8-АМАЛИЙ МАШҒУЛОТ

Мавзу: Факторлаш муаммосининг мураккаблигига асосланган криптотизимларнинг криптоанализи

Ишдан мақсад: Ушбу амалий машғулотни бажариш жараёнида факторлаш муаммосининг мураккаблигига асосланган криптотизимларнинг криптоанализи усуллари бўйича назарий ва амалий маълумотларга эга бўлиш.

Назарий қисм

Факторлаш муаммосини ҳал этишга бағишланган адабиётларда келтирилган n модулни факторлаш масаласини ечишда биринчи навбатда ҳаёлга келадиган усул, бу  дан ошмайдиган туб сонларни танлаб уларга бўлиб кўришдир. Бошқа танлаш усули Фермага тегишли бўлиб, n ни квадратлар айирмаси кўринишида ифодалашга асосланган:

n=a²-b²=(a+b)(a-b).

Ферма энг катта умумий бўлувчи - EKUB(n, a-b) ни, яъни n нинг нотривиал бўлувчисини топишга ҳаракат қилишни ҳамда бунга имкон берувчи усулни ҳам таклиф этган. Агар n нинг кўпайтувчилари бир-биридан катта фарқ қилмаса, бу усул оддий танлаш усулига нисбатан тез ечим беради ва унинг мураккаблиги О() кўринишида ифодаланади, аммо ҳозирги кунда криптографик тизимларда амалда фойдаланиладиган ҳоллар учун аҳамиятга эга эмас. Лежандр мазкур ёндашувда a²≡b² (mod n) га эга бўлиш лозимлигига эътибор қаратган. Аммо, келтирилган таққослама ҳар қандай n учун етарли эмаслигини ҳам кўрсатган ва кўзланган мақсадга эришиш учун узлуксиз касрлардан фойдаланиш йўлини таклиф этган.

Компьютерлар асрида дастлабки 1970 йилларда таклиф этилган факторлаш алгоритмларидан бири (p-1) Поллард алгоритми бўлган.  Ундан сўнг (p+1) Вильямс алгоритми ва ЭЭЧлардан фойдаланишга асосланган Ленстра алгоритми ишлаб чиқилди. Кейинчалик (p-1) Поллард алгоритми (p+1) Поллард алгоритми сифатида, Поллард r -, l - усули номлари остида такомиллаштирилди. r - l - Поллард усулининг мураккаблиги I_p=Öpq/4 амал билан белгиланади.

1. Диксон усули

Фараз қилинсинки, n ни факторлаш лозим бўлсин. Агар Лежандр эътибор қаратган x²≡y² (mod n) таққосламани, яъни n га каррали бўлган, x ва y k¹0 учун x²-y²=kn, унда (x-y)(x+y)=kn бўлади. Агар кичик эҳтимоллик билан x-y=k ва x+y=n ҳосил қилинса, камида  ½ эҳтимоллик билан n ни факторлаш мумкин бўлади. Агар EKUB(n, x-y) ва EKUB(n, x+y) бўлса, унда булар n нинг фош этилган факторлари бўлади.

Масалан, 100=9 (mod 91), унда 10²=3²(mod 91),

(10-3)(10+3) = (7)(13) =0 (mod 91), демак, 7*13=91.

Умумий ҳолда факторлар EKUB(n, x-y) ва EKUB(n, x+y) ларни ҳисоблаш орқали  топилади. EKUB дан фойдаланиш  зарурлигини кўриш учун фараз қилинсинки, x=34, y=8, булар 34²=8²(mod 91) таққосламани қаноатлантиради, чунки 34² (mod 91)=64 дир. Бу мисолда x-y=26 ва x+y=42, бинобарин, EKUB(91,26)=13, EKUB(91,42)=7.

EKUB О(log a)²  дан кичик мураккабликка эга бўлган Евклид алгоритми асосида осон ҳисобланади, аммо x²≡y² (mod n) таққосламани қаноатлантирувчи ўзгарувчилар жуфтини топиш мураккаб масаладир. Бу масалани ечишни осонлаштириш учун таққосламани қаноатлантириш шартларини бироз ўзгартириш кифоя.

Масалан, 41²=32 (mod 1649) ва 43²=200 (mod 1649) бўлсин, бу ерда 32 ҳам, 200 ҳам квадратик чегирма эмас.

Бироқ, иккала тенгламадан кутилган таққослама                            (41*43)²=80² (mod 1649) берувчи 41²43²=32*200=6400 (mod 1649)  топилади.

 Бу  масалани ечиш учун фойдаланиладиган субэкcпоненциал мураккабликка эга бўлган алгоритмларда силлиқлик хусусиятига эга бўлган сонлардан фойдаланилади. Алгоритмлар мураккаблиги бу хусусиятдан фойдаланишга бўлган ёндашув билан фарқланади.

2. Квадратик ғалвир усули асослари

Факторлашнинг квадратик ғалвир усули Диксон усулига жуда ўхшаш. Иккала алгоритмда ҳам чизиқли алгебра асосларидан бир хил тарзда фойдаланилган. Яъни, аввало чегара В танланади ва В дан катта бўлмаган туб сонлардан фактор базаси шакллантирилади. Шаклланган база етарли миқдорда B-силлиқ сонларни ўз ичига олиши шарт.

Кейин кўпҳад Q(x)=( ëÖnû+x)²+n аниқланади. Бу кўпҳад квадратик бўлиб, база элементларини B-силлиқка текшириш учун фойдаланилади. Усул номида “квадратик” атамаси қатнашиши кўпҳад квадратик бўлганидан келиб чиққан.

Силлиқлик муносабатига эга бўлган сонларни танлаш учун 0 сонини ўз ичига олган интервал, масалан, [-М; M] дан ҳар бир бутун сон xÎ [-М;M] учун y=Q(x) ҳисобланади. Сўнгра n модуль бўйича y=x² ҳисобланади, бу ерда x= ëÖnû+x . Натижада Диксон алгоритмидаги каби y В-силлиқми ёки йўқлиги аниқланади. Агар y силлиқ бўлса, унда чизиқли тенгламалар системасини ечиш босқичи учун 2 модуль бўйича экспонента сифатида сақлаб қўйилади. Квадратик ғалвир усулининг Диксон усулига нисбатан устунлиги адабиётларда баён этилган ғалвир тузиш усули билан белгиланади. Ғалвир тузиш фактор базасини шакллантириш ишини осонлаштиради.

Қуйида квадратик ғалвир усулининг 1991 йилда таклиф этилган такомиллаштирилган Померанц усулининг асосий ғояси ҳақида тўхталамиз.

Фактор базаси сифатида қандайдир параметр билан чекланган s та шундай туб сон p_i лар танланадики, (n/ p_i)=1 бўлсин, бу ерда (n/ p_i) Якоби белгиси.

m= ëÖnû, Q(t)=(t+m)²-n=H(t)², бу ерда H=t+ëÖnû. t нинг деярли кичик қийматларида Q(t) нинг қиймати ҳам катта бўлмайди. Кейинги қадамда, t сонларини кўриб чиқиш ва Q(t) ларни кўпайтувчиларга ажратиш ўрнига, алгоритм биратўла “кераксиз” t ларни чиқариб ташлайди ва фактор базаси орасида фақат Q(t) нинг бўлувчилари мавжуд бўлганларини қолдиради, яъни

A=Q(t)=Õ^s_j=1p^gj_j,

Q(t) фактор базасида ажратилади. Унда B=H(t) белгилаш орқали                     B² ºA²(mod n) таққосламага эга бўлинади ва бундай таққосламаларни тўплаб, ўзгарувчиларни сафдан чиқариш орқали Диксон алгоритмидагидек X² ºY² (mod n) таққосламасига эга бўлинади, оқибатда факторлар топилади.

3. Сонли майдон ғалвири усули асослари

Ҳозирги кунда сонли майдон ғалвири усули асосида 110 ва ундан ортиқ ўнли хонали узунликдаги модулларни факторлаш учун энг тезкор алгоритмлар ишлаб чиқилган. Квадратик ғалвир усули нисбатан тўппа-тўғри мақсадга элтишга етарли бўлса ҳам, сонли майдон ғалвири усули такомиллашган математик асосларга таяниши билан истиқболлироқдир. Сонли майдон ғалвири  ўз моҳияти бўйича алгоритм эмас, балки бир неча босқичдан таркиб топган алгоритмлар мажмуасидир.

Квадратик ғалвир алгоритмининг мураккаблиги

C₁=O(exp( (ln p)^1/2 (ln ln p)^1/2)) амал билан баҳоланса, сонли майдон ғалвири  усулининг мураккаблиги C₂=O(exp(c(ln p)^1/3 (ln ln p)^2/3)) амал билан баҳоланади, бу ерда с»1,9223. Сўнги ифодада (ln p)^1/2 ҳади (ln p)^1/3 га айланган, аммо C₂ да нисбатан катта с нинг қатнашиши квадратик ғалвир алгоритми узунлиги 110 ўнли хонали бўлган модуллар қулайлигига сабаб бўлади.

n нинг бинар узунлиги x=log n га тенг олиниши келтирилган усул мураккаблилигини симметрик криптотизимлар калит узунлиги бўйича мураккаблиги билан таққослаш имконини беради.                                 

Ишни бажариш учун вазифа ва топшириқлар

1. Диксон усули асосида  n сонни факторланг.

2. Квадратик ғалвир усули асосида  n сонни факторланг.

3. Сонли майдон ғалвири усули асосида  n сонни факторланг.

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

1. Факторлаш муаммосининг мураккаблиги қандай асосланади?

2. Факторлаш муаммосининг мураккаблигига асосланган криптотизимларнинг энг самарали  криптоанализ усулларини тушунтиринг.

Фойдаланилган адабиётлар

1. Хасанов П., Хасанов Х., Ахмедова О., Давлатов А. Криптоанализ ва унинг махсус усуллари. Ўқув қўлланма.– Тошкент, 2010.

2. Хасанов Х. П. Такомиллашган диаматрицалар алгебралари ва параметрли алгебра асосида криптотизимлар яратиш усуллари ва алгоритмлари. – Тошкент, 2008.

3. Брюс Шнайер. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си – Москва: ТРИУМФ, 2002.

4. Hankerson D., Menezes A., Vanstone S. Guide to Elliptic Curve Cryptography. Springer-Verlag New York, Inc. 2004.

9-АМАЛИЙ МАШҒУЛОТ

Мавзу: Эллиптик эгри чизиқ группасида дискрет логарифмлаш муаммосига асосланган тизимларнинг криптоанализ усуллари

Ишдан мақсад: Ушбу амалий машғулотни бажариш жараёнида эллиптик эгри чизиқ группасида дискрет логарифмлаш муаммосига асосланган тизимларнинг криптоанализ усуллари бўйича назарий ва амалий маълумотларга эга бўлиш.

Назарий қисм

 ЭЭЧда нуқталарни қўшиш амали аниқланган. E(K)  ЭЭЧ нуқталар тўплами нуқталарни қўшиш амалига нисбатан чекли коммутатив (Абель) группасини ҳосил қилади.

Таъриф. ({O,(x,y)Î E(K)}; “+”) жуфтлиги кўринишидаги алгебраик структурани ЭЭЧ нуқталари группаси деб аталади.

ЭЭЧга асосланган кўпчилик криптографик алгоритмларнинг бардошлилиги ЭЭЧда дискрет логарифмлаш масаласини ечиш мураккаблиги (ECDLP) билан белгиланади.

Бугунги кунда ECDLP масаласини ечишнинг энг яхши алгоритми, ЭЭЧда нуқталарни  Öpn/2 тартибли қўшишни талаб этувчи Полларднинг                r-усулидир.

Тизимли параметрлар Полиг-Хеллман, Шенкснинг “кичкина ва катта қадамлар” r-Поллард мураккаб логарифми, индексни ҳисоблаб топишга ва шу каби бошқа ҳужумларга бардошлиликни таъминлаши лозим. 

Полиг-Хеллман алгоритми асосида базавий (генератор) нуқталар тартиби факторлаш масаласи ётади.  Алгоритм  факторлаш натижасида ҳар бир модуль бўйича олинган дискрет логарифм ечими эвазига калитни топиш мураккаблигини пасайтиради. Калитни топишда қолдиқни топиш ҳақидаги хитойча теоремадан фойдаланилади.

“Кичкина ва катта қадамлар” алгоритми тезкорлик ва хотирадан фойдаланиш ўртасидаги ўзаро мосликни таъминлайди.

ЭЭЧда дискрет логарифмлаш масаласини ечишниг маълум усулларидан энг машҳури Полларднинг r- ва l- усулларидир. ЭЭЧ нуқталарини қўшиш билан аниқланувчи Полларднинг r-усули мураккаблигини қуйидаги ифода орқали баҳолаш мумкин:

Ip=Öpq/2,

бу ерда  q – ЭЭЧ базавий нуқталари тартиби.

Адабиётларда Поллард r-усули тезлигини Ö2 мартага ошириш мумкинлиги кўрсатилган. У ҳолда  усул мураккаблиги I_p=Öpq/4 билан баҳоланади.

Поллард r-усулининг афзаллик томонларидан бири криптотаҳлил жараёнини мустақил бир нечта параллел жараёнларга ажратишдир. Бу  ҳолда ҳар бир жараённи амалга ошириш мураккаблиги I_p=Öpq/2r² ва I_p=Öpq/4 r² билан баҳоланади. Поллард l-усули мураккаблиги I_l=2Öq билан ва параллеллашда      I_l=2r^-1Öq билан баҳоланади. 

Полларднинг иккала усулининг қиёсий таҳлили Поллард l-усули Поллард r-усулига нисбатан мураккаброқлигини кўрсатади.

2004 йилда Поллард параллелланган алгоритми асосида “бузилган” ЭЭЧ калитининг энг катта узунлиги 109 битни ташкил этди. 1-жадвалда ЭЭЧда дискрет логарифмлаш масаласини ечишнинг ҳисоблаш мураккаблигини баҳолари келтирилган.

ЭЭЧда дискрет логарифмлаш масаласини Поллард r-усулидан фойдаланиб ечиш мураккаблигига тааллуқли келтирилган маълумотлар шуни кўрсатадики, ЭРИ алгоритмларида базавий нуқтаси q≥2²⁵⁶  тартибли ЭЭЧ қўлланиши ЭЭЧ базасидаги ЭРИ зарур бардошлилигининг келажакдаги истиқболини таъминлайди. Бу ГОСТ Р 34.10-2001нинг 10 йил давомида муваффақиятли эксплуатацияси ва калитни очиш мураккаблиги 3*10³⁸ арифметик амалдан иборатлиги  билан ҳам асосланади.

1-жадвал

ЭРИни бузиш мураккаблиги

Базавий нуқта G тартиби (узунлик  битларда)	Группадаги амаллар сони
128	1,63480*10^19
192	7,02141*10^28
256	3,01567*10^38
320	1,29522*10^48
352	8,48836*10^52
384	5,56293*10^57
416	3,64572*10^62
448	2,38926*10^67
480	1,56583*10^72
512	1,02618*10^77
1024	1,18824*10^154

Ишни бажариш учун вазифа ва топшириқлар

_1. y=_{ЭЭЧ коэффициентлари a=0, b=0, c=1 бўлганда  унга тегишли бўлган G(2,3) нуқтанинг тартибини топинг.}

2. Базавий нуқта G тартиби 1024 битдан юқори узунликлар учун ЭРИни бузиш мураккаблигини ҳисобланг.

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

1. ЭЭЧ группасида дискрет логарифмлаш муаммосининг мураккаблигига асосланган тизимларни энг тезкор криптотаҳлиллаш усуллари йўқлигининг асосий сабаби нимада?

2. ЭЭЧ группасида дискрет логарифмлаш муаммосини ечишнинг самарали ҳисобланган қайси криптотаҳлил усулларини биласиз?

Фойдаланилган адабиётлар

1. Хасанов П., Хасанов Х., Ахмедова О., Давлатов А. Криптоанализ ва унинг махсус усуллари. Ўқув қўлланма.– Тошкент, 2010.

2. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии. Учебное пособие. — М.: Гелиос-АРВ, 2001.

3. Hankerson D., Menezes A., Vanstone S. Guide to Elliptic Curve Cryptography. Springer-Verlag New York, Inc. 2004.

10-АМАЛИЙ МАШҒУЛОТ

Мавзу: Параметрли алгебраик структураларнинг хоссалари

Ишдан мақсад: Ушбу амалий машғулотни бажариш жараёнида параметрли алгебраик структураларнинг хоссалари бўйича назарий ва амалий маълумотларга эга бўлиш.

Назарий қисм

Параметрли алгебранинг асосий  амаллари қуйидагилардир:

1. Параметрли кўпайтириш амали

a®b º a + b + a*R*b (mod n);

бу ерда a, b, RÎF_n, параметр R>0,+, * – бутун сонлар устида қўшиш, кўпайтириш амалларининг ва ® – параметрли кўпайтириш амалининг белгилари. Параметрли кўпайтириш амали ўз моҳияти бўйича тернар амалдир.

2. Параметрли тескари элемент қуйидагича ҳисобланади:

a ^\-1 º - a(1+ aR)^-1 (mod n).

Бу ерда ^-1 - n модуль бўйича тескарилаш амалининг белгисидир.

Нолдан фарқли тўплам элементи a учун тескари элемент a^\-1 ва қарама-қарши элемент n-a мавжуд. a^\-1 параметрли тескари элемент деб аталади ва a®a^\-1 º 0 (mod n) шартини қаноатлантиради. Бу ерда                                  0 – параметрли бирлик элементи бўлиб, a®0 º a аксиомани қаноатлантиради.

Параметрли мультипликатив коммутатив группа қуйидаги хоссаларга эга.

1-хосса: агар параметрли мультипликатив коммутатив группанинг параметри жуфт сон ва модули n=2k (k - ихтиёрий натурал сон) га тенг бўлса, унинг тартиби (группа элементлари сони) 2k га тенг.

2-хосса: агар модули n туб сон бўлган параметрли мультипликатив коммутатив группанинг параметри ихтиёрий натурал сон бўлса, унинг тартиби φ(n) га тенг, бу ерда φ(n) – Эйлер пи-функцияси қиймати.

Мисол:

1) (F₈; ®), бу ерда F₈={0,1,2,3,4,5,6,7}, n=8, R=2.

2) (F _φ(7); ®) , бу ерда F₇={0,1,2,3, 5,6}, n=7, R=5.

3-хосса: агар мураккаб модулли параметрли мультипликатив коммутатив группанинг параметри модуль n билан ўзаро туб бўлса, унинг тартиби φ(n) га тенг, бу ерда φ(n) – Эйлер пи-функцияси қиймати.

4-хосса: агар мураккаб модуль n=pq, бу ерда p, q – ҳар хил туб сонлар, параметрли мультипликатив коммутатив группанинг параметри R                модуль q билан ўзаро туб бўлиб, p билан ўзаро туб бўлмаса, унинг тартиби p(q-1) га тенг.

Параметрли мультипликатив коммутатив группанинг                                        1-,  2- , 4-хоссалари анъанавий мультипликатив группа (F_n; *) хоссаларидан ўз тартиби билан фарқ қилади. Масалан, анъанавий бинар кўпайтириш амали асосида шаклланган мультипликатив группа модули 2k бўлганда, фақат тоқ элементлардан ташкил топган чекли тўпламда мавжуд бўлса, параметрли мультипликатив коммутатив группа бутун сонлар тўпламида мавжуддир. Мураккаб модуль n=pq учун параметрли мультипликатив коммутатив группанинг параметри R модуль p билан ўзаро туб бўлиб, q билан ўзаро туб бўлмаса, унинг тартиби анъанавий мультипликатив группа (F_n; *) тартибига нисбатан юқори бўлади. Булар криптотизим яратиш ва уларни таҳлиллашнинг янги имкониятларини юзага чиқариши мумкин.

Ишни бажариш учун вазифа ва топшириқлар

1. Теорема. nЄN, RЄZn, aЄZn бўлсин. a элемент R параметр билан кўпайтиришга нисбатан тескари бўлади, агарда 1+R*a элементи Zn да тескари бўлса. Ушбу ҳолда тескари элемент қуйидаги формула билан ҳисобланади:

a^\-1 = -a (1+R*a)^-1 (mod n).

Теоремани исботланг. 

2. Таъриф. nЄN ва R Є Zn бўлсин. Параметрли кўпайтириш амали қуйидаги кўринишда ифодаланиб a®b º a + b + aRb (mod n) формула асосида аниқланади. Бу ерда a, b Є Zn.

1-Лемма. Ушбу киритилган амал коммутатив  ва ассоциатив ҳисобланади.

1-Леммани исботланг.

3. 2-Лемма. Параметрли кўпайтириш амалига нисбатан 0 нейтрал элемент ҳисобланади, бунда ихтиёрий a Є Zn:

a ® 0 = a (mod n).

2-Леммани исботланг.

4. Таъриф. Тескари элемент a^\-1  – а нинг шундай элементики, уларнинг кўпайтмаси майдоннинг бирлик элементи — 0 га тенг:

a^\-1 ® a = 0.

3-Лемма. Нейтрал элемент 0 – ўз-ўзига тескари.

3-Леммани исботланг.

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

1. Параметрли алгебранинг асосий амалларини ифодаланг?

2. Параметрли алгебраик структураларнинг хоссаларининг моҳияти нимадан иборат?

Фойдаланилган адабиётлар

1. Хасанов П., Хасанов Х., Ахмедова О., Давлатов А. Криптоанализ ва унинг махсус усуллари. Ўқув қўлланма.– Тошкент, 2010.

2. Хасанов Х. П. Такомиллашган диаматрицалар алгебралари ва параметрли алгебра асосида криптотизимлар яратиш усуллари ва алгоритмлари. – Тошкент, 2008.

3. Акбаров Д.Е. Ахборот хавфсизлигини таъминлашнинг криптографик усуллари ва уларнинг қўлланишлари. Тошкент. ”Ўзбекистон маркаси “, 2009.

МУНДАРИЖА

1.	Классик шифрларнинг криптоанализи: Цезарь ва Атбаш шифрлари……………………………………………………………	3
2.	Полибий ва Вижинер шифрининг криптоанализи……………….	5
3.	Евклиднинг умумлашган алгоритми, модул арифметикаси…….	8
4.	Криптоанализнинг универсал усуллари: тўлиқ танлаш усули, калит бўйича ҳужум………………………………………………..	11
5.	Частотавий анализ усули, Поллард усули………………………...	13
6.	«Ўртада учрашиш» усули, хэш-функция коллизияси усули…….	16
7.	Дискрет логарифмлаш муаммосига асосланган криптотизимлар криптоанализи………………………………………………………	19
8.	Факторлаш муаммосининг мураккаблигига асосланган криптотизимларнинг криптоанализи……………………………...	22
9.	Эллиптик эгри чизиқ группасида дискрет логарифмлаш муаммосига асосланган тизимларнинг криптоанализ усуллари...	26
10.	Параметрли алгебраик структураларнинг хоссалари……………	30

ҚАЙДЛАР УЧУН САҲИФА

____________________________________________________________________________________________________________________

________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

__________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

“Амалий криптоанализ усуллари” фанидан амалий машғулотларни бажариш учун услубий кўрсатма

Муаллифлар	Ахмедова О.П.
Тақризчилар	Расулов О.Х. Ганиев А.А.
Масъул муҳаррир	Рахимова Н.Х.
Муҳаррир

Бичими 60х84 1/16

Босма табоғи _____ Адади____

Буюртма №____

Тошкент ахборот технологиялари университети «ALOQACHI» нашриёт – матбаа марказида Чоп этилди.

Тошкент ш., Амир Темур кўчаси, 108 – уй.