Алгоритмдер және деректер структурасы


ПОӘК 042-18.39.1.206/01-2013



жүктеу 2,07 Mb.
Pdf просмотр
бет13/35
Дата15.01.2020
өлшемі2,07 Mb.
#26613
1   ...   9   10   11   12   13   14   15   16   ...   35

ПОӘК 042-18.39.1.206/01-2013 

10.09.2013 ж.  № 1 басылым  

81 беттің 29 

 

 

-  Алгебралық теңдеулердің түбірлерін табу. 



Ашық кілтті криптожүйені келесі 3 бағытта қолдануға болады: 

-  Деректердің қауіпсіздігін қамтамассыз ету үшін. 

-  Кілт тарату тәсілі ретінде. 

-  Аутентификация үшін. 



 

RSA  криптожүйесі.  RSA  криптожүйесін    Рон  Ривест  (Ron  Rivest),  Ади  Шамир  (Adi 

Shamir)  және  Леонард  Адлеман  (Leonard  Adleman)  ойлап  тапқан.  Алгоритм  үлкен  санды  жай 

көбейткіштерге жіктеу есебінің қиындығына сүйенген. 

Алгоритм  сипаттамасын  берер  алдында  сандар  теориясынан  кейбір  мәліметтерді  еске 

түсірейік. 

Анықтама.  a  және  b  бүтін  сандарын  n  модулі  бойынша  салыстырмалы  дейді  егер  a-b 

айырымы n–ге қалдықсыз бөлінетін болса. 

Біз n



1 деп есептейміз. a, b, n сандарының арасындағы қатынас былай жазылады  



 b(mod n). 



Мысал 25 

 4(mod 7), -5 



 34 (mod 13) 

Анықтама.  n  модулі  бойынша  белгілі  бір  a  санымен  салыстырмалы  сандардың  жэиыны 

сынып деп аталады. Ол a деп белгіленеді.  

Мысал. 6 модулі бойынша 5 сыныбы: {...-7, -1, 5, 11, 178, 23 ...} 

Модулярлық  арифметиканы  компьютерлік  есептеулерге  қолдану  үшін  біз  тек  қана 

шектелген мәндер диапозонын қарастырумыз керек. Сондықтан негізінен  a сыныбындағы ең кіші 

оң санмен жұмыс істейді. Сандар теориясында мұндай санның бар екендігі және де ол а-ны n-ге 

бөлгендегі қалдыққа тең екендігі дәлелденген. 

Ескерту. Программалау тілдерінде mod функциясы басқаша анықталуы мүмкін. 

Модулярлық  арифметика  қарапайым  арифметикаға  ұқсас.  Ол  коммутативті,  ассоциативті 

және дистрибутивті. 

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

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

(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 

Анықтама. Эйлер функциясы n-нан кіші және  n-мен жай оң бүтін сандардың санына тең 

функцияны айтады. Функция 

(n) деп белгіленеді. 



Мысалға, 

(10)=4. Эйлер функциясының келесі тамаша қасиеті бар: егер n=pq, мұндағы p 



және q – жай сандар, онда 

(n)=(p-1)(q-1).                                                                              (2) 



Теорема 1 (Эйлер). Кез-келген р жай саны үшін және р-ға бөлінбейтін кез-келген а

1 саны 



үшін келесі салыстыру орындалады 

a

p-1



1(mod p) . 



Теорема 2 (Эйлер). Кез-келген n модулі мен n-мен өзара жай саны үшін келесі салыстыру 

ақиқат 


(p)-1



1(mod n).                                                                             (3) 



Евклид алгоритмі 

r



>  r

1

>0 оң бүтін сандары берілсін. Олардың ең үлкен ортақ бөлгішін (ЕҮОБ) табу үшін 



келесі есептеулер тізбегі орындалады. 

r

0



 = q

1

 r



1

 +r


,  0


2

1

 



r

1

 = q



2

 r

2



 +r

3

< r

........................... 



r

m-2


 = q

m-1


 r

m-1


 + r

m

 , 0

m

m-1 


r

m-1


 = q

m

r



m

 



ПОӘК 042-18.39.1.206/01-2013 

10.09.2013 ж.  № 1 басылым  

81 беттің 30 

 

 

ЕҮОБ (r



0

 ,r


1

)=r


m

 

Кеңейтілген Евклид алгоритмі. 



 

Келесі сандық тізбек анықтайық {t

i

}

m



i=0

 мұндағы 

t

0

=0, t



1=1, 

t

j



=t

j-2


-q

j-1


t

j-1


, j

2                                                                     (4) 



Лемма. Егер ЕҮОБ (r

0

 ,r



1

)=1 


t

m



r

1

-1



(mod r

0

) (немесе r



1

 t

m



1(mod r


0

))                                              (5) 

Ал енді алгоитмді сипаттайық: 

1.  Екі  үлкен  кездейсоқ  жай  p  және  q  сандары  таңдап  алынады.  Көбейтіндісі  табылады  n  =  pq. 

Енді (p-1)(q-1) санымен өзара жай кездейсоқ е саны таңдап алынады. Кеңейтілген алгоритмнің 

көмегімен келесі кері саны есептелінеді 

de 



 1 (mod(p-1)(q-1))  



2.  m хабарды шифрлау үшіноны алдын ала n-нен кіші блоктарға бөлінеді. Екілік деректер үшін 

ұзындығы l–ге тең блоктар алынады, мұндағы l 2

l

Шифрмәтін келесі формуламен анықталады c

i

=m

i



e

mod n       

3.  Дешифрлау үшін m

i

=c



i

d

 есептелінеді. 



 

Расында, (1), (2) және (3) формулаларын қолдана отырып, алатынбыз 

 

c

i



d

 mod n=(m

i

e

 mod n)



d

 mod n=m


i

ed

 mod n = m



i



(n)+1

 mod n = (((m

i

k

)



 (n)


mod n) * (m

i

 mod n )) mod n = 



m

 



Тұтынушы n, e кілттерін ашық деп (Public Key) жариялайды, ал b кілті жабық кілт болып 

саналады (Private key). 

 

RSA авторлары криптожүйенің жұмысын түсіндіру үшін келесі кестелік мысал келтіріледі. 



Бастапқы мәтін ретінде төмендегі сөйлем таңдап алынған. 

ITS ALL GREEC TO ME 

Әр символға 5 разряд арнап, бос орынды – 0, А әрпін – 1, В әрпін – 2,......,Z әрпін – 26 деп 

кодтаған. Келесі үлкен сан алған m1= 

09201900011212000718050511002015001305. 

Ашық кілттердің мәні ретінде е = 9007, n = 

11438162575788886766923577997614661201021829672124236256265184293 

570693524573389783059712356395870505898907514759920026879543541 

деп алған. 

Сонда шифрланған санның түрі келесідей болып шықты: 

c = 19993513149780510045231712274026064742320401705839146310370371

 

7406259971608948922750439920962672582675012893554461353823769748026 



 

Енді біз есептеу алгоритмін толық сипаттайтын мысал келтірейік. 

Мысал. Жай сандар ретінде p=11, q=17 таңдап алайық. Онда n=pq=187, 

(n)=(p-1)*(q-1)=160. 



Кез-келген 

(n)–мен  өзара  жай  е  санын  таңдайық,  яғни  (e,  160)=1.  Мысалға,  e=7  болсын. 



Келесі теңдеуден d жабық кілтін табу керек: 

7d=1 mod 160 

Алдында  келтірілген  кеңейтілген  Евклид  алгоритмін  қолданамыз  ((5)  формуласы).  Енді 

Евклид алгоритміне сүйеніп q

i

 мәндерін табу үшін келесі есептеулер тізбегін табамыз  



 

160=22*7+6 

7=1*6+1 

6=6*1 


Ақыры алатынымыз: 

q

1



=22; q

2

=1; q



3

=6 


t

0

=0; t



1

=1; t


2

=0-22*1=-22; t

3

=1+1*22=23; 



d=t

3

=23 




жүктеу 2,07 Mb.

Достарыңызбен бөлісу:
1   ...   9   10   11   12   13   14   15   16   ...   35




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

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