1 amaliy ish Mavzu: Kriptografiyaning matematik asosi

Sana	04.11.2020
Hajmi	0.51 Mb.
	#140712

Bog'liq
1-amaliy ish

Ishni bajarilish tartibi va qo’yilgan vazifa
Nazorat savollari

1 - amaliy ish

Mavzu: Kriptografiyaning matematik asosi

Ishdan maqsad: O’zaro tub sonlar va modul amali xossalari, sanoq sistemasi,

mantiqiy amallar haqida amaliy ko’nikmalarga ega bo’lish.

Nazariy qism

Natural sonlar to‘plamini N ={1, 2,3, … } va butun sonlar to‘plamini Z={0,

1, 2, 3, … } ko‘rinishda belgilaymiz.

Noldan farqli bo‘lgan a soni va v sonlar Z –to‘plamga tegishli, ya’ni a,b Z

bo‘lib, a 0 bo‘lsin., agarda shunday s soni mavjud bo‘lib, v=as tenglik bajarilsa, u

holda, a soni v sonini bo‘ladi deyiladi.

Berilgan a va v sonlarni bo‘luvchi butun son, ularning umumiy bo‘luvchisi

deyiladi. Umumiy bo‘luvchilar ichida eng kattasi eng katta umumiy bo‘luvchi

(EKUB) deyiladi va (a, v) ko‘rinishda belgilanadi. Agarda a va v sonlarning eng

katta umumiy bo‘luchisi 1, (a, v)=1 bo‘lsa, a va v sonlar o‘zaro tub deyiladi.

Berilgan natural son p>1 tub deyiladi, agarda bu son o‘zi p va 1 dan boshqa

natural songa bo‘linmasa.

Misol uchun: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, tub sonlar, ular sanoqli va

cheksiz quvvatli to‘plamni tashkil etadi. Kelgusida, barcha butun sonlarni modul

(xarakteristika) deb ataluvchi biror fiksirlangan natural n soniga bo‘lganda

qoladigan qoldiqlar bilan bog‘liq holda qaraymiz. Bunda cheksiz quvvatli

(elementlari soni cheksiz) bo‘lgan barcha butun sonlar to‘plamiga, 0 dan n-1 gacha

bo‘lgan butun sonlarni o‘z ichiga oladigan chekli, quvvati n ga teng bo‘lgan

{0; 1; 2; 3;…;n-1}

–to‘plam mos qo‘yiladi. Bu quyidagicha amalga oshiriladi: a va n –natural

sonlar bo‘lsa, “a sonini n soniga qoldiq bilan bo‘lish”, deganda ushbu

a=qn+r, bu yerda 0

r <n,

shartni qanoatlantiruvchi natural q va r sonlarini topish tushuniladi. Bu oxirgi

tenglikda qoldiq deb ataluvchi r soni nolga teng bo‘lsa r=0, natural a soni n soniga

bo‘linadi yoki n soni a sonining bo‘luvchisi deyiladi.

Butun a va b sonlari modul n bo‘ycha taqqoslanadigan deyiladi, agarda ularni

n ga bo‘lganda qoladigan qoldiqlari teng bo‘lsa, hamda,

a b(mod n)

deb yoziladi. Bundan esa a va b sonlar ayirmasining n ga qoldiqsiz bo‘linishi kelib

chiqadi.

Qoldiqni ifodalash uchun ushbu

b=a mod n

tenglikdan foydalaniladi, hamda b=a mod n tenglikni qanoatlantiruvchi b

sonini topish a sonini modul n bo‘yicha keltirish deyiladi.

Biror n modul bo‘yicha qo‘shish, ayirish va ko‘paytirish amallariga nisbatan

quyidagi kommutativlik, assotsiativlik va distributivlik munosabatlari o‘rinli:

(a+b)mod n=((a mod n)+(b mod n))mod 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,

(a· (b+c)mod n=(((a·b) mod n)+(a·c) mod n))mod n.

Quyida modul amallari bilan bog‘liq bir nechta misollar keltirib o‘tilgan:

1. b=a mod n tenglikda a>n>0 bo‘lgan holda, natijani hisoblash uchun a ni n

ga bo‘lib, qoldig‘i olinadi. Masalan, 12mod5=2; 15mod6=3;

2. b=a mod n tenglikda n>0 va a<0 bo‘lgan holda, a ga toki yig‘inda noldan

katta bo‘lgunga qadar n qo‘shiladi. Masalan, -5mod6=1; -12mod5=3;

3. b=a mod n tenglikda a kasr son bo‘lgan holda, tenglik quyidagi

(b*c)modn=1 tenglikka keltiriladi. a=1/c ga teng bo‘lsa, s butun son bo‘ladi. Olingan

tenglikdan b ning o‘rniga qiymat berish orqali tenglik bajaralishi tekshiriladi.

Tenglik bajarilsa, unda b ga o‘zlashtiriladi. Bu usul ko‘p vaqt talab etadi. Shuning

uchun amalda Evklidning kengaytirilgan aalgoritmining xususiy holidan

foydalaniladi. Ushbu algoritmning ketma-ketligi quyidagicha:

(e*d)modn=1 tenglikda e va n ma’lum bo‘lib, d ni topish talab etilsin. Buning

uchun quyidagi belgilanishlar kiritiladi a=n va b=e. Uchta elementdan iborat

bo‘lgan, uchta to‘plam quyidagicha tuziladi:

U={a, 1, 0}, V={b, 0, 1}, T={U[1]modV[1], U[2]-[U[1]/V[1]]*V[2], U[3]-

[U[1]/V[1]]*V[3]}. Bu yerda dastlabki qiymatlardan U va V to‘plamlar hosil

qilinadi va ular asosida T to‘plam hisoblanadi. Agar T to‘plamning birinchi elementi

T[1]=1 ga teng bo‘lganda hisoblanishlar to‘xtatiladi va d=T[3] ga teng bo‘ladi. Aks

holda, V to‘plamning qiymatlari U to‘plamga, T to‘plamning qiymatlari V

to‘plamga o‘zlashtiriladi (U=V, V=T) va ular asosida yangidan T to‘plam

hisoblanadi va yana T[1]=1 tengiligi tekshiriladi. Ushbu ketma-ketlik T[1]=1 tenglik

bajarrilgunga qadar amalga oshiriladi va teng bo‘lgan holda d=T[3] deb olinadi va

hisoblashlar to‘xtatiladi.

Masalan, (d*8)mod23=1; a=23, b=8; U holda to‘plamlar: U={23, 1, 0}, V={8,

0, 1} va T={23mod8, 1-[23/8]*0, 0-[23/8]*1}={7, 1, -2} Demak, T[1]=1 shart

bajarilmadi. U=V={8, 0, 1}, V=T={7, 1, -2}, T={8mod7, 0-[8/7]*1, 1-[8/7]*(-

2)}={1, -1, 3}. Demak T[1]=1 ga teng va d=T[3]=3. Natijani:

(3*8)mod23=1 tengligi bilan isbotlash mumkin.

Kompyuter elektron-raqamli qurilmdir. Elektron qurilma deyilishiga sabab,

har qanday ma’lumot kompyuterda elektr signallari orqali qayta ishlanadi. Raqamli

deyilishiga sabab har qanday ma’lumot sonlar yordamida tasvirlanadi. Aniqroq

aytganda har qanday ma’lumot kompyuterda ikkita butun son birlar va nollar

yordamida tasvirlanadi va qayta ishlanadi. Shuning uchun ma’lumotlarni bunday

tasvirlanishi ikkili formada tasvirlanish deb qabul qilingan.

Sanoq sistemalari ma’lumotlarni kompyuterda saqlanishi va qayta

ishlanishidagi asosiy tushunchalardan biri hisoblanadi.

Sonlarni ma’lum sondagi raqamlar, belgilar orqali tasvirlash usullari va

qoidalari majmuasiga sanoq sistemasi deb ataladi.

1.1-jadval

Sanoq sistemasi

3

4

100

101

110

111

1000

1001

100

1010

101

10 A

1011

102

1100

110

12 C

1101

111

13 D

1110

112

1111

120

10000

121

100

16 10

Ikkilik sanoq sistemasida faqat ikkita: 0 va 1 raqamlaridan tashkil topgan. Shu

sistemada qo‘shish, ayirish va ko‘paytirish amalari quyidagicha bajariladi (1.2-jadval).

1.2-jadval

Ikkilik sanoq sistemasi ustida amallar

Qo‘shish Ayirish Ko‘paytirish

0+0=0

0-0=0

0*0=0

0+1=1

1-0=1

0*1=0

1+0=1

10-1=1 1*0=0

1+1=10

1*1=1

Sakkizlik sanoq sistemasida 1 dan 7 raqamgacha va 8 dan boshlab 10 dan boshlab

davom etadigan raqamlardan tashkil topgan. Ushbu sistemada qo‘shish, ayirish va

ko‘paytirish amalari quyidagicha bajariladi (1.3-jadval).

1.3-jadval

Sakkizlik sanoq sistemasida qo’shish

+ 0

1

2

1.4-jadval

Sakkizlik sanoq sistemasida ko’paytirish

0

1

O’n oltillik sanoq sistemasida 1 dan 9 raqamg va A dan F gacha harflardan tashkil

topgan. Ushbu sistemada qo‘shish, ayirish va ko‘paytirish amalari quyidagicha bajariladi

(6-jadval).

1.5-jadval

O’n oltillik sanoq sistemasida qo’shish

+ 0 1 2 3 4 5 6 7

9 A

1 1 2 3 4 5 6 7 8

A B

2 2 3 4 5 6 7 8 9

B C

3 3 4 5 6 7 8 9 A

C D

4 4 5 6 7 8 9 A B

D E

5 5 6 7 8 9 A B C

E F

6 6 7 8 9 A B C D

F 10

7 7 8 9 A B C D E

10 11

8 8 9 A B C D E F

11 12

9 9 A B C D E F 10

12 13

A A B C D E F 10 11

13 14

B B C D E F 10 11 12

14 15

C C D E F 10 11 12 13

15 16

1A 1B

D D E F 10 11 12 13 14

16 17

1A 1B 1С

E E F 10 11 12 13 14 15

17 18

1A 1B 1С 1D

F F 10 11 12 13 14 15 16

18 19

1A 1B 1C 1D 1E

1.6-jadval

O’n oltilik sanoq sistemasida ko’paytirish

x 1

10 12 14 16 18 1A 1C 1E

12 15 18 1B 1E 21 24 27 2A 2D

10 14 18 1C 20 24 28 2C 30 34 38 3C

14 19 1E 23 28 2D 32 37 3C 41 46 4B

6

C

12 18 1E 24 2A 30 36 3C 42 48 4E 54 5A

15 1C 23 2A 31 38 3F 48 4D 54 5B 62 69

10 18 20 28 30 38 40 48 50 58 60 68 70 78

12 1B 24 2D 36 3F 48 51 5A 63 6C 75 7E 87

14 1E 28 32 3C 46 50 5A 64 6E 78 82 8C 96

16 21 2C 37 42 4D 58 63 6E 78 84 8F 9A A5

18 24 30 3C 48 54 60 6C 78 84 90 9C A8 B4

1A 27 34 41 4E 5B 88 75 82 8F 90 A9 B6 C3

1C 2A 38 46 54 62 70 7E 8C 9A A8 B6 C4 D2

1E 2D 2C 4B 5A 69 78 87 96 A5 B4 C3 D2 E1

Mantiqiy amallar

Protsessor tarkibidagi arifmetik-mantiqiy qurilmaning ishlash prinsipini

tushunish uchun avval insonning mantiqiy fikrlash va xulosa chiqarish usullarini

ko’rib chiqamiz.

Insonlar kundalik hayotda o’zaro muloqot qilish uchun turli mulohazalardan

foydalanishadi. Ma’lumki, mulohaza – narsa yoki hodisalarning xususiyatini

anglatuvchi darak gapdir. Boshqacha aytganda, mulohaza – rost yoki yolg’onligi

haqida so’z yuritish mumkin bo’lgan darak gap.

Mulohazalar sodda va murakkab bo‘lishi mumkin. Biror shart yoki usul bilan

bog‘lanmagan hamda faqat bir holatni ifodalovchi mulohazalar sodda

mulohazalar deyiladi. Sodda mulohazalar ustida amallar bajarib, murakkab

mulohazalarni hosil qilish mumkin. Odatda murakkab mulohazalar sodda

mulohazalardan “VA”, “YОKI” kabi bog‘lovchilar, “EMAS” shaklidagi

ko‘makchilar yordamida tuziladi.

Mulohazalarni lotin alifbosi harflari bilan belgilash (masalan, A= “Bugun

havo issiq”) qabul qilingan. Har bir mulohaza faqat ikkita: “rost” yoki “yolg‘on”

mantiqiy qiymatga ega bo‘lishi mumkin. Qulaylik uchun “rost” qiymatni 1 raqami

bilan, “yolg‘on” qiymatni esa 0 raqami bilan belgilab olamiz.

A va B sodda mulohazalar bir paytda rost bo‘lgandagina rost bo‘ladigan yangi

(murakkab) mulohazani hosil qilish amali mantiqiy ko‘paytirish amali deb ataladi.

Bu amalni konyunksiya (lot. conjunctio– bog’layman) deb ham atashadi.

Mantiqiy ko‘paytirish amali ikki yoki undan ortiq sodda mulohazalarni “VA”

bog‘lovchisi bilan bog‘laydi hamda “A va B” , “A and B” , “A Λ B” , “A · B” kabi

ko‘rinishda yoziladi. Mantiqiy ko‘paytirishni ifodalaydigan quyidagi jadval rostlik

jadvali deb ataladi:

1.7-jadval

Mantiqiy ko’paytirish amali

B

A Λ B

A va B mulohazalarning kamida bittasi rost bo‘lganda rost bo‘ladigan yangi

murakkab mulohazani hosil qilish amali mantiqiy qo‘shish amali deb ataladi.

Bu amalni dizyunksiya (lot. disjunctio – ajrataman) deb ham atashadi

Mantiqiy qo‘shish amali ikki yoki undan ortiq sodda mulohazalarni “YOKI”

bog‘lovchisi bilan bog‘laydi hamda va “A yoki B”, “A or B” , “A V B”, “A + B”

kabi ko‘rinishlarda yoziladi.

1.8-jadval

Mantiqiy qo‘shish amali

B

A V B

A mulohaza rost bo‘lganda yolg‘on, yolg‘on bo‘lganda esa rost qiymat

oladigan mulohaza hosil qilish amali mantiqiy inkor amali deb ataladi.

Bu amalni inversiya (lot. Inversio – to’ntaraman) deb ham atashadi Mantiqiy

inkor amali “A EMAS” , “not A” , “ ᒣ A” , “” ko‘rinishlarda yoziladi.

1.9-jadval

Mantiqiy inkor amali

ᒣ A

Ko‘rinib turibdiki, mantiqiy o‘zgaruvchilar, munosabatlar, mantiqiy amallar

va qavslar yordamida mantiqiy ifodalar hosil qilish mumkin ekan.

Mantiqiy ifodalarda mantiqiy amallar quyidagi tartibda bajariladi: inkor (¬),

mantiqiy ko

’

paytirish (

), mantiqiy qo

’

shish (v).

Teng kuchli yoki bir xil amallar ketma-ketligi bajarilayotganda amallar

chapdan o‘ngga qarab tartib bilan bajariladi, ifodada qavslar ishtirok etganda dastlab

qavslar ichidagi amallar bajariladi. Ichma-ich joylashgan qavslarda eng ichkaridagi

qavs ichidagi amallar eng avval bajariladi.

Mantiqiy amallarga doir misollar :

1–misol. A mulohaza rost qiymat qabul qilsa, “A va (A EMAS)”

mulohazaning qiymatini aniqlang.

Yechish. A rost qiymat qabul qilganligi uchun (A EMAS) yolg‘on qiymatga

ega bo‘ladi. U holda rost va yolg‘on qiymatlarning ko‘paytmasidan (“VA” amali)

yolg‘on natijaga ega bo‘lamiz. Shunday qilib, javob “yolg‘on” ekan.

2–misol. A va B mulohazalar rost qiymat qabul qilganda A Λ B V A

mulohazaning qiymatini aniqlang.

Yechish. A va B mulohazalar rost qiymatli bo‘lganligi uchun A Λ B amal rost

qiymat qabul qiladi. U holda jadvalga ko‘ra ikkita rost qiymatni mantiqiy

qo‘shishdan rost qiymat hosil bo‘ladi. Javob: rost.

3–misol. (Е > D) Λ A Λ ᒣB mantiqiy ifodaning qiymatini D = 3,2 va E = –

2,4, A = “rost” va B = “rost” bo’lganda hisoblang.

Yechish. (–2,4 >3,2) munosabat noto‘g‘ri bo‘lganligidan bu mulohaza

“yolg‘on” bo‘ladi. Demak, A mulohazaning qiymati “rost” bo’lsa ham (Е > D) Λ A

mulohaza qiymati “yolg‘on” bo’ladi. B mulohazaning qiymati “rost”, shuning uchun

ᒣB mulohaza “yolg‘on” qiymatli bo‘ladi. U holda (Е > D) Λ A Λ ᒣB mantiqiy ifoda

“yolg‘on” qiymat qabul qiladi. Javob: yolg‘on.

Ishni bajarilish tartibi va qo’yilgan vazifa

Sonning moduli, sanoq sistemasiga oid misollar berilgan bo‘lib unda

talabalar o’zning tartib raqamida berilganlarni bajarilsin va qadamma – qadam

izohlansin.

T.J.R

Modulning

xususiyatlari

n>0 va

a<0 holda

b=a mod n

ni toping ?

(e*d)modn=1

у va n

berilgan

holda d ni

toping?

- >Y

a=3; b=-4;

c=5; n=8;

a=-45;

n=7;

n=17;

e=2;

11010110

3261

4BA

a=6; b=-7;

c=8; n=8;

a=-54;

n=8;

n=19;

e=4;

10101011

2512

1AF

a=12; b=-

21;

c=13; n=8;

a=-5;

n=60;

n=17;

e=3;

10110110

2674

AA4

a=14; b=-

12;

c=13; n=8;

a=-55;

n=21;

n=23;

e=4;

10001010

2713

B1A

a=15; b=-

16;

c=17; n=8;

a=-56;

n=50;

n=23;

e=6;

11011011

3054

9A4

a=51; b=-

21;

c=12; n=8;

a=-52;

n=105;

n=23;

e=12;

10011101

2751

AA8

a=51; b=-

10;

c=53; n=8;

a=-55;

n=4;

n=23;

e=2;

11010111

2517

2BA

a=89; b=-

10;

c=56; n=8;

a=-63;

n=6;

n=29;

e=6;

11100110

3012

2DA

a=11; b=-

12;

c=13; n=8;

a=-36;

n=89;

n=29;

e=5;

11100111

3232

1AC

10.

a=45; b=-

54;

c=5; n=8;

a=-65;

n=56;

n=31;

e=4;

10101010

2677

8BA

11.

a=5; b=-96;

c=69; n=8;

a=-89;

n=98;

n=31;

e=8;

11111111

3134

EAC

12.

a=52; b=-5;

c=5; n=8;

a=-89;

n=21;

n=17;

e=9;

11111110

2513

CA1

13.

a=9; b=-8;

c=5; n=8;

a=-100;

n=33;

n=50;

e=17;

10110110

3171

B2A

14.

a=12; b=-

15;

c=18; n=8;

a=-102;

n=25;

n=37;

e=19;

11110000

2739

1BA

15.

a=40; b=-

42;

c=30; n=8;

a=-104;

n=23;

n=41;

e=7;

10111111

2615

AA9

16.

a=50; b=-9;

c=61; n=8;

a=-67;

n=23;

n=41;

e=6;

11111100

3146

31D

17.

a=8; b=-9;

c=15; n=8;

a=-47;

n=3;

n=43;

e=4;

10111011

2730

FA1

18.

a=56; b=-

65;

c=20; n=8;

a=-89;

n=12;

n=43;

e=11;

11110011

3025

E2A

19.

a=40;b=-50;

c=10; n=8;

a=-45;

n=24;

n=47;

e=8;

11011111

2519

1AE

20.

a=2; b=-3;

c=5; n=8;

a=-74;

n=69;

n=47;

e=6;

11111010

3112

B1D

21.

a=52;b=-63;

c=41; n=8;

a=-105;

n=501;

n=61;

e=31;

10111000

2740

2AD

22.

a=78; b=-8;

c=5; n=8;

a=-91;

n=19;

n=67;

e=17;

11110101

2614

7BA

23.

a=7; b=-8;

c=41; n=8;

a=-58;

n=85;

n=67;

e=4;

11011000

3024

E2D

Nazorat savollari

1. O’zaro tub sonlar, tub sonlarga ta’rif bering va misollar keltiring.

2. Modul amali xossalarini misol orqali tushuntiring.

3. Butun sonlar va ularni kriptografiyada foydalanilishi.

Download 0.51 Mb.

Do'stlaringiz bilan baham: