Дәріс тақырыбы: Алгебралық құрлымдар. Комбинаторика элементтері (2 сағат) Негізгі сұрақтар



жүктеу 170,73 Kb.
бет3/6
Дата03.02.2022
өлшемі170,73 Kb.
#35462
1   2   3   4   5   6
Дәріс № 10

Диффи-Хелмон

1976 ж. Американдық криптологтар У.Диффи және М.Хелмон ашық кілтпен криптографияны жасап шығарды. Олар кілттің екі түрін қолдануды ұсынды- ашық және құпия .1-сурет Диффи- Хеллман алгаритмін бірге құпия кілттер  құру үшін қолдну мысалыкелтірілге*(n-1)/н екі пайдаланушы (Айбота және Ержан) қорғалған қатынас арнасын ұйымдастырады деп есептейік.

 I-қадам. Айбота мен Ержан Джәне Имәндері жайында келіседі.

                Айбота________ Интернет _________ Ержан



II-қадам. Айботамен Ержан Уа және Ув мәндерін есептейді, нәтижелерімен алмасады.  

                    Айбота                 Интернет                Ержан

                  Уа=gKa(modN)                  Ув=gKb(modN)

 III-қадам Айбота мен Ержан құпия кілт к мәндерін есептейді.

   Е^=(Уа)ка)(modN)           К*=(Уа)кв)(modN)           

                                 К=К*=gКаКв)(modN)           

 

                        1-сурет.Диффи Хелмнан алгаритмы.



1-қадам. Екі пайдаланушы алдын ала N модулі (N жай сан болуы керек )және g € zn(1≤ g

 Айбота мен Ержан бір-бірінен тәуелсіз, Ка және Кв кездейсоқ үлкен бүтін сандарды таңдайды. Бұл сандар құпия кілттер. Оларды пайдаланушылар құпия түрде сақтайды.

 2-қадам. Әрі қарай Диффи- Хеллман алгаритімі қолданылады. Айбота  Уа=gKa(modN) ашық кілтін ,ал Ержан-Ув=gKв(modN )ашық кілтін есептейді. Сосын олар есептелгенУа және Ув ашық кілттер мәндерімен қорғалған ара бойынша алмасады.

 3-қадам. Олар келесі салыстырымдарды пайдаланып ортақ құпия кілтті есептейді  Айбота: (К=Ув)кА=(gкв (modN))

Ержан:  К*=(Уа)кв=(gка)кв (modN)

Мұнда К= К*, өйткені деректерді шифрлау және кері шифрлау кезінде DES кілті ретінде пайдаланылады.

Екі пайдаланушы С=Ек (М)=Мк(modN)шешу түрлендіруін (RSA-сияқты) қолданып хабарларды шифрлау мүмкін

Хабар алушы кері шифрлауда орындау үшін К*К*=1(Mod N-1)салыстыру көмегімен кері шифрлау кілтін табады, ал содан соң М=Дк(с)=ск*(modN)хабарды қалпына келтіреді.

Мысалы Модуль N=47,ал қарапайым элемент g=23дейін. Ка=12(mod47)ж2не Кв=33(mod47)деп таңдаған болсын.

 Олар К ортақ құпия кілтті алу үшін алдын ала дербес ашық кілттердің мәндерін есептейді: Уа=дка=23¹²=27(mod47)

                   Ув=дкn=23³³=33(mod47)

Енді А және В пайдаланушылары Іа және Ув өз мәндерімен алмасып ортақ құпия кілтін есептейді:

К=(Ув)кА=(Уа)кв=33¹²=27³³=23¹²*³³=25(mod47)

Одан кейін, олар К*К*=1(Mod N-1)салыстыруын қолданып, кері шифрлау құпия кілтін К*=35(mod47) табад.

М=16 болғанда криптограмма С=Мк=16 25=21(mod47) болады, хабар алушы хабарды қалпына келтіреді.
Кодтаудың қарапайым жүйесі хабарлама немесе сөздің әр әріптерін ереже бойынша басқа белгіге ауыстыру болып табылады. Мысалы, Юлий Цезарь өзінің сиқырлы хабарламаларында бірінші әріптерін алфавиттің төртінші әріпіне, ал екінші әріпін алфавиттің бесінші әріпіне және т.б ауыстырған болатын. Ал D,B әріптерін E, Z, C және т.б әріптерге ауыстырған. Қарапайым ауыстыру әдістері сияқты кодтау А.К. Дойлдың «Пляшущие человечки» және Э. Поның «Золотой жук»атты қызықты әңгімелерінде айтылған.

Қазақ және орыс алфавиттері


Реттік

нөмірі


Әріптер

1.

 А

2.

Ә

3.

Б

4.

В

5.

Г

6.

Ғ

7.

Д

8.

Е

9.

Ё

10.

Ж

11.

З

12.

И

13.

Й

14.

К

15.

Қ

16.

Л

17.

М

18. 

Н

19. 

Ң

20.

О

21. 

Ө

22. 

П

23. 

Р

24. 

С

25. 

Т

26. 

У

27. 

Ұ

28. 

ү

29. 

Ф

30. 

Х

31. 

Һ

32. 

Ц

33

Ч

34

Ш

35

Щ

36

Ъ

37

Ы

38

І

39

Ь

40

Э

41

Ю

42. 

я




Реттік

нөмірі


Әріптер

1.

 А

2.

Б

3.

В

4.

Г

5.

Д

6.

Е

7.

Ё

8.

Ж

9.

З

10.

И

11.

Й

12.

К

13.

Л

14.

М

15.

Н

16.

О

17.

П

18. 

Р

19. 

С

20.

Т

21. 

У

22. 

Ф

23. 

Х

24. 

Ц

25. 

Ч

26. 

Ш

27. 

Щ

28. 

Ь

29. 

Ы

30. 

Ъ

31. 

Э

32. 

Ю

33. 

Я

Қарапайым шифрлеуді кодтау өте оңайға түседі, себебі бұл тілдің өзінің белгілері болады. Мысалы ағылшын тілінде көбінесе Е әріптері кездесетін болса, орыс тілдерінде О әріптері де жиі кездеседі. Сондықтан орыс тілінде сөйлесу мәнерінде көбінесе О әріпі кездесетіні мәлім. Бұл шындық сөздің ұзындығына байланысты өсетін болады. Жетілген шифрлерді орналастыру кезінде олар қажет түрде өзара ауысады. Мысалы берілген ұзындықта сөзді жазып, барлық әріптер тең болатындай бөлшекке бөліп жазамыз. Мысалы мына хабарлама, «ТЕОРИЯИНФОРМАЦИИ» жолдың ұзындығын төрт әріптен құрайтындай етіп алатын болсақ, онда шифрленген сөзіміз мынадай күйде болады «ТИФАЕЯОЦОИРИРНМИ». Осылайша шифрлеу кезінде мынадай тік төрт бұрыш пайда болды:




Т

Е

О

Р

И

Я

И

Н

Ф

О

Р

М

А

Ц

И

И

Орналастыру шифрін кодтау бір тәжірибеде көрінбейді, ол үшін қосымша анықтама білу керек. Кодтаудың бір кемшілігі, ұқсас шифрлерді қандай түрде болсын кодтан шеше алатын болсақ, онда кейін басқа да сөздерді кодтан шешуге әбден мүмкін.

Мысалы,қарастырылған сөзімізді кодтан шешу үшін біз «РЫБЫ» кілттін қолданатын болсақ, «РНМИ ОИРИ ТИФА ЕЯОЦ» сөзін аламыз. Кілтті сөзбен немесе кілтсіз сөздер XVI ғасырларда анықталған, қазір де қолданылуда. Ол екі негізгі сатыдан тұрады. Біріншісі саты кодтарды құрау амалы. Ол әрқашан бұл шифрді қолданушыларға мәлім. Екінші сатысы бұл негізгі хабарламадан жіберілетін және хабарламаның кодын шешу онсыз мүмкін емес кілт болып табылады.



Кілтті қолданудың ең оңай түрі : хабарлама астына бірінен соң бірі кілт жазылып отырады. Егер белгішелердің санынан алынған сан көп болса онда одан ортақ сан алынып тасталады. Алынған сандар символдың коды болып табылады. Мысалы, қарастырған хабарламамызды алып, оған «КИБЕРНЕТИКА» кілттік сөзін қолданатын болсақ. Онда кодталған сөзіміз былай болады: «ЮОРЦЪНОБЮЪСШЙШЩЪ»


Т

Е

О

Р

И

Я

И

Н

Ф

О

Р

М

А

Ц

И

И

20

6

16

18

10

33

10

15

22

16

18

14

1

24

10

10

К

И

Б

Е

Р

Н

Е

Т

И

К

А

К

И

Б

Е

Р

12

10

2

6

18

15

6

20

10

12

1

12

10

2

6

18

32

16

18

24

28

15

16

2

32

28

19

26

11

26

16

28

Ю

О

Р

Ц

Ь

Н

О

Б

Ю

Ь

С

Ш

Й

Ш

О

Ь

Егер кілт сөзі үшін кез келген сөзді алатын болсақ, онда шешілмейтін сөз шығады.

Қарапайым шифрлеуді қолдана отырып, «мәліметтр қоры» сөйлемін кодтайық:



м

а

л

и

м

е

т

т

е

р

к

о

р

ы

14

1

13

10

14

6

20

20

6

18

12

16

18

29

к

о

д

к

о

д

к

о

д

к

о

д

к

о

12

16

5

12

16

5

12

16

5

12

16

5

12

16

26

17

18

22

30

11

32

4

11

30

28

21

30

13

ш

п

р

ф

ь

й

ю

г

й

ь

ъ

ф

ь

м

Кодталған сөзіміз: «шпрфьйюгйьъфьм»
Комбинаторика. Орналастыру және теру. Орналастыру және функционал бейнелеу. Ендіру және шығару формуласы. Жиындарды бөліктеу.

Комбинаториканың негізгі есебі–қайта санау және ақырлы жиын элементтерін тізбектеу.

Егер берілген ақырлы жиын элементтерінің қаншасының берілген бір қасиетке ие екендігін анықтау қажет болса бұл қайта санау есебі, ал берілген қасиетке ие барлық элементтерді анықтау керек болса, бұл тізімдеу есебі Комбиторика есебін дәлелдеуде екі ереже жиі қолданылады. Олар: қосу және көбейту ережелері.

Егер Х n элементтерден тұратын ақырлы жиын болса, Х объектісін Х тен n тәсілмен алуға болады дейді және Х=n болып белгіленеді.

Егер Х1,…,Хn–қос қостан қиылыспайтын жиындар болса, яғни Хi Хj= (ij), онда

-қосу ережесі. (1)

Бұл ережені k=2 үшін былай жазуға болады: Егер х объектісі m тәсілмен таңдалса, ал у басқа n тәсілмен таңдалса, онда "не х, не у" таңдау m+n тәсілмен іске асырылады (х және у элементтерін бір уақытта таңдау болмайды).

Көбейту ережесі. Егер х объектісін m тәсілмен таңдауға болса, және осындай таңдаудан кейін у объектісін өз кезегінде n тәсілмен таңдауға болса, онда реттелген (х, у) жұбын mn тәсілмен таңдауға болады.(х, у – таңдаулары тәуелсіз).

Жалпы жағдайда, егер х1 объектілері n1 тәсілмен таңдалса, одан кейін х2 n2 тәсілмен таңдалса және кез келген 2im-1 үшін х1, х2,…,хi объектілерін таңдағаннан кейін хi+1 объектісін ni+1 тәсілмен таңдауға боллатын болса, онда m объектіден құралған (х1, х2, …, хm) реттелген тізбегі n1 n2… nm тәсілмен таңдалады.

Х={х1, …, хn} жиынынан алынған хi1, …, хir элементтерінің жиынтығы n элементтен алынған r көлемді таңдама деп аталады.

Егер элементтердің орналасу тәртібі берілген болса, таңдама реттеген деп, ал орналасу тәртібіне белгілі бір шарт қойылмаса, таңдама реттелмеген деп аталады.

Таңдамаларда элементтердің қайталануы да, қайталанбауы да мүмкін.

Элементтері қайталануы мүмкін (n, r) - таңдамасы (n, r)-қайталама таңдамасы деп аталады. Ал егер реттелген (n, r) таңдаманың элементтері қос қостап әр түрлі болса, (n, r) қайталанбайтын таңдама немесе жай ғана (n, r)-орналасу деп аталады.

(n, n)-қайталанбайтын орналасу Х жиынын алмастыру деп аталады.

Элементтері қайталануы мүмкін реттелмеген (n, r)-таңдама, қайталанба (n, r)-теру деп аталады. Егер реттелмеген (n, r) таңдаманың элементтері қос қостан әр түрлі болса, онда ол қайталанбайтын (n, r)-теруі немесе жай ғана (n, r) теруі деп аталады. Кез келген (n, r)-теруін n-элементті жиынның r-элементті ішкі жиыны деп қарауға болады.

Мысал, айталық Х={1, 2, 3} болсын.

1) (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3) - (3, 2)-қайталама орналастырулар.

2) (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2) - (3, 2)-қайталама орналасу;

3) (1, 2, 3), (1, 3, 2), (3, 2, 1), (2, 1, 3), (3, 1, 2), (2, 3, 1) – Х жиынын алмастыру;

4) {1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {3, 3} - (3, 2)-қайталама теру;

5) {1, 2}, {1, 3}, {2, 3} - (3, 2)-қайталанбайтын теру. Қайталама теру саны (n, r)-ді , қайталанбайтын теру- .n-элементті теру саны Pn (яғни Pn= ) болып белгіленеді. Қайталама теру (n, r)-саны ,ал қайталанбайтын теру- .

1-тұжырым. =nr.

Шынында әрбір (n, r)-қайталама теру ұзхындығы r-ға тең реттелген тізбек, ал оның әр мүшесі n тәсілдің бірімен таңдалады, бұдан көбейту ережесінен =nn…n=nr.

(Дербес жағдайда бұл өрнек негізі n санау жүйесінде r позицияда жазылған әр түрлі сандардың нешеу екендігін анықтайды.).

2-тұжырым. =n(n-1)(n-2)…(n-r+1)= , rnжәне =0, r>n болғанда.

Шынында, r элементтен тұратын реттелген тізбектің бірінші мүшесі n тәсілмен таңдалады, екіншісі-(n-1) тәсілмен, соңғысы-(n–r+1) тәсілмен. Жалпыланған көбейту ережесінен ізделінді формуланы аламыз.

Салдар =Pn=n(n-1) … (n–n+1)=n!



3-тұжырым., егер rn, =0 егер r>n.

Шышында да, әр (n, r)-теруін r! әдіспен реттеуге болады, яғни -ді r! рет -ге қарағанда r! рет аз. Бұл формуладан = .

4-тұжырым. .

Шынында да Х={x1,…,xn} жиынының элементтерінен құрылған әрбір қайталанба (n, r)- В теруі үшін,r нөл мен n-1 1-ден тұратын (i-1)-ші және i бірлердің (мұндағы 2 i  n-1) арасындағы нөлдердің саны В теруіндегі xi элементтерінің санына тең, ал бірінші бірдің алдындағы нөлдердің саны В-ға енетін xi элементтерінің санына тең болатын ұзындығы (В) болатын векторды сәйкестендіруге болады.

Мысалы Х={1, 2, 3, 4}, n=4, r=6 болса, Егер В={2, 2, 3, 3, 3, 4} - (4, 6)-қайталанба теру болса онда (В) = 100100010 болады. Екінші жағынан егер (В1)=110010000, онда В1 = {3, 3, 4, 4, 4, 4}.

Бұл қайталанба (n, r)-теруімен n-1 бір және r нөлден тұратын вектор арасындағы сәйкестік. n-1 бірден және r нөлден құралған n+r-1 мөлшерлі векторлар саны тең.

= = .


жүктеу 170,73 Kb.

Достарыңызбен бөлісу:
1   2   3   4   5   6




©g.engime.org 2024
әкімшілігінің қараңыз

    Басты бет
рсетілетін қызмет
халықаралық қаржы
Астана халықаралық
қызмет регламенті
бекіту туралы
туралы ережені
орталығы туралы
субсидиялау мемлекеттік
кеңес туралы
ніндегі кеңес
орталығын басқару
қаржы орталығын
қаржы орталығы
құрамын бекіту
неркәсіптік кешен
міндетті құпия
болуына ерікті
тексерілу мемлекеттік
медициналық тексерілу
құпия медициналық
ерікті анонимді
Бастауыш тәлім
қатысуға жолдамалар
қызметшілері арасындағы
академиялық демалыс
алушыларға академиялық
білім алушыларға
ұйымдарында білім
туралы хабарландыру
конкурс туралы
мемлекеттік қызметшілері
мемлекеттік әкімшілік
органдардың мемлекеттік
мемлекеттік органдардың
барлық мемлекеттік
арналған барлық
орналасуға арналған
лауазымына орналасуға
әкімшілік лауазымына
инфекцияның болуына
жәрдемдесудің белсенді
шараларына қатысуға
саласындағы дайындаушы
ленген қосылған
шегінде бюджетке
салығы шегінде
есептелген қосылған
ұйымдарға есептелген
дайындаушы ұйымдарға
кешен саласындағы
сомасын субсидиялау