2-Мавзу: Криптографиянинг асосий тушунчалари ва тарихи Криптографиянинг асосий тушунчалари

Криптография ва стеганография

Криптографиянинг асосий бўлимлари

• Симметрик калитли криптография.
• Очиқ калитли криптография.
• Хеш функциялар.
• Калит криптотизимни созлаш учун ишлатилади
• Симметрик криптотизимда шифрлаш ва дешифрлашда битта калитдан фойдаланилади.
• Очиқ калитли криптотизимда шифрлашда очиқ калитдан, дешифрлашда ёпиқ калитдан фойдаланилади.
• Хеш функциялар маълумотларни бутунлигини кафолатлаш мақсадида ишлатилади

Хеш функция

• Қуйида “ℎ𝑒𝑙𝑙𝑜” хабарини турли хэш функциялардаги қийматлари келтирилган:
• 𝑀𝐷5 (ℎ𝑒𝑙𝑙𝑜) = L5𝑑41402𝑎𝑏𝑐4𝑏2𝑎76𝑏9719𝑑911017𝑐592
• 𝑆𝐻𝐴1 (ℎ𝑒𝑙𝑙𝑜) = L𝑎𝑎𝑓4𝑐61𝑑𝑑𝑐𝑐5𝑒8𝑎2𝑑𝑎𝑏𝑒𝑑𝑒0𝑓3𝑏482𝑐𝑑9𝑎𝑒𝑎9434𝑑a9434d
• 𝑆𝐻𝐴256 (ℎ𝑒𝑙𝑙𝑜) = 2𝑐𝑓24𝑑𝑏𝑎5𝑓𝑏0𝑎30𝑒26𝑒83𝑏2𝑎𝑐 5𝑏9𝑒29𝑒1𝑏161𝑒5𝑐1𝑓𝑎7425𝑒73043362938𝑏9824
• Хеш функция қуйидаги хусусиятларга эга:
• a. Бир хил кириш ҳар доим бир хил чиқишни (хэш қиймат деб аталади) тақдим этади.
• b. Бир қанча турли киришлар бир хил чиқишни тақдим этмайди.
• c. Чиқиш қийматдан кирувчи қийматни ҳосил қилишнинг имконияти мавжуд эмас (бир томонламалик).
• d. Кириш қийматини ўзгариши чиқишдаги қийматни ҳам ўзгаришига олиб келади.

Хеш функция

Криптографик акслантиришлар

• Одатда криптграфияда маълумотларни шифрлашда (дешифрлашда) қуйидаги икки турдаги акслантиришшлардан фойдаланилади.
• Улардан бири ўрнига қўйиш (substitution) акслантириш бўлса, иккинчичи ўрин алмашиш (permutation) акслантиришидир.

Цезар шифрлаш усули

• Очиқ матн: fourscoreandsevenyearsago
• Калит: 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

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

z

C

• Шифрлаш:

IRXUVFRUHDQGVHYHQBHDUVDJR

Очиқ матн

Цезар шифрлаш усули

• n бўйича суришлар n  {0,1,2,…,25}
• Калит қиймати n
• Мисол: калит n = 7

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

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

z

G

Очиқ матн
Шифр матн

Цезар усулида дешифрлар

Криптотаҳлил: Барча ҳоллар синаб кўриш

• Ўрнига қўйиш (n та силжитишдан иборат)

- лекин калит берилмаган

• Шифрматн берилган: CSYEVIXIVQMREXIH
• Қандай қилиб калитни топамиз?
• Бўлиши мумкин бўлган калитлар сони 26  барчасини синаб кўриш!
• Калитни тўлиқ қидириш
• Ечим: калит n = 4

Оддий алмаштиришлар

• Умуман олганда, харфларнинг ҳар қандай ўзгариши оддий алмаштириш калити бўлиши мумкин.

- алфавит кетма-кетлиги бўйича алмаштириш шарт эмас.

• Масалан

Очиқ мант
Шифр матн

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

J

I

C

A

X

S

E

Y

V

D

K

W

B

Q

T

Z

R

H

F

M

P

N

U

L

G

• Мумкин бўлган калитлар 26! > 288!

z

O

Калит оралиғи қанча бўлиши керак?

• Айтайлик Триди тезкор компютерга эга, улар ҳар сониясига 240 калитни синаб кўриш имконига эга.
• Бу дегани агар калит ўлчами 256 бўлса, калитни топиш учун 216 сония (18 соат) талаб қилади.
• 264 ўлчамдаги калит бўлса, ярим йилдан кўпроқ вақт кетади.
• 2128 ўлчамдаги калит бўлса, 1030 йил талаб қилинади.
• 288 ўлчамдаги калит бўлса, 8900 минг йиллик талаб қилинади.

Криптографиянинг тарихи

• Қадимий давр (қадимий давр классик шифрлари) - Цезар, Полибия квадрати
• Ўрта давр (ўрта давр классик шифрлари) - Вижинер, Атбаш
• 1 ва 2 – жахон уриши даври (1 ва 2- жахон уриши даври классик шифрлари) - Zimmermann телеграфи, Энигма шифри, SIGABA машиналарини
• Компьютер даври (замонавий шифрлар) - DES, AES, ГОСТ 28147-89, IDEA, A5/1, RC4 (барчаси симметрик) ва RSA, Эл-Гамал (очиқ калитли)

Бир мартали блокнот (Vernam шифри)

e=000 h=001 i=010 k=011 l=100 r=101 s=110 t=111

h	e	i	l	h	i	t	l	e	r
001	000	010	100	001	010	111	100	000	101

111	101	110	101	111	100	000	101	110	000
110	101	100	001	110	110	111	001	110	101
s	r	l	h	s	s	t	h	s	r

Шифрлаш: Очиқ матн  Калит = Шифрматн
Очиқ матн:
Калит:
Шифрматн:

Бир мартали блокнот: Дешифрлаш

e=000 h=001 i=010 k=011 l=100 r=101 s=110 t=111

s	r	l	h	s	s	t	h	s	r
110	101	100	001	110	110	111	001	110	101

111	101	110	101	111	100	000	101	110	000
001	000	010	100	001	010	111	100	000	101
h	e	i	l	h	i	t	l	e	r

Дешифрлаш: Шифр  Калит = Очиқ матн
Шифр матн:
Калит:
Очиқ матн:

Бир мартали блокнот

• Фараз қилинсин, бирор қонуний фойдаланувчи Алиса бир мартали блокнотдан фойдаланган ҳолда “HEILHITLER” матнини шифрлаб, ўз шериги Боб томонга юбориши талаб этилсин.
• Ушбу шифрлаш алгоритми учун қуйидаги икки ҳолатни қараб чиқиш муҳим. Биринчи ҳолатда, фараз қилинсин Алиса томонинг душмани Триди бор ва у Алиса томон қуйидаги калитдан фойдаланилган деб билади:
• Агар Триди душман ушбу калитни Боб томонга узатишни уддасидан чиқса, у ҳолда Боб томон шифрматнни дешифрлаш орқали қуйидагига эга бўлади:

101 111 000 101 111 100 000 101 110 000

H	E	I	L	H	I	T	L	E	R
001	000	010	100	001	010	111	100	000	101

Бир мартали блокнот

• Фараз қилинсин бошқача cценарий мавжуд. Алиса фойдаланувчи ўз душмани Триди томонидан қўлга олинди ва душман шифрматнга ҳам эга. Душман шифрматтни ўқий олмайди ва шунинг учун Алиса томондан унинг калитини айтишини талаб этади. Алиса томон ўзини ҳар иккала томонга “ўйнашини” айтиб, шифрматтни дешифрлаш калити деб қуйидагини айтади:
• Ушбу калит орқали душман Триди шифрматнни дешифрлаганда қуйидаги очиқ матнга эга бўлади:

Бир мартали блокнот

• Бир мартали блокнотда калитлардан фақат бир марта фойдаланишдан мақсад нима? Фараз қилайлик, қуйидаги икки очиқ матн ва битта калит 𝐾 дан фойдаланиб шифрланган: ва Криптографияда ушбу ҳолатни “хавфлилик” деб аталади ва бир мартали блокнот хавфли ҳолатда деб тушинилади, яъни фойдаланилган калит ортиқ муаммо туғдирмайди:
• = 100 010 011 000 ва
• Ҳар иккала очиқ матн ягона калит 𝐾 L110 011 101 111 шифрланган ва шифрматнлар қуйидагига тенг бўлган:

•  

Бир мартали блокнот

Кодлар китоби

Очиқ матн	Шифрматн
Februar	13605
fest	13732
finanzielle	13850
folgender	13918
Frieden	17142
Friedenschluss	17149
⋮	⋮

Зиммерман телеграми

Криптографиянинг таксаномияси

Симметрик криптотизм

• Шифрлаш ва дешифрлашда бир хил калитдан фойдаланилади
• Икки тури мавжуд: Оқимли шифрлаш, Блокли шифрлаш

Очиқ калитли криптотизим (ёки асимметрик криптотизим)

• Икки калитдан фойдаланилади, биттаси шифрлаш учун (очиқ), ва иккинчиси дешифрлаш учун (махфий)
• Рақамли имзо алгоритмлари

Хеш алгоритмлар

• Бир томонлама крипто сифатида қараш мумкин

Саволлар???

Мисоллар

• Шифр матн= ?GONXAHFB#F@S
• Калит=SINF

• Шифр матн=_@OC#DOYS*IUAL@U
• Калит=SOAT

• A=00000
• B=00001
• C=00010
• D=00011
• E=00100
• F=00101
• G=00110
• H=00111
• I=01000
• J=01001
• K=01010
• L=01011
• M=01100
• N=01101
• O=01110
• P=01111

• Q=10000
• R=10001
• S=10010
• T=10011
• U=10100
• V=10101
• W=10110
• X=10111
• Y=11000
• Z=11001
• #=11010
• !=11011
• _=11100
• @=11101
• ?=11110
• *=11111