Қазақстан республикасы білім және ғылым министрлігі павлодар мемлекеттік педагогикалық институты

 
100 
4.  143-дан  аспайтын  және  143-пен  өзара  жай  болатын  натурал  сандардың  саның 
табыңыз. 
5. 187 мен 153 сандардың ең үлкен ортақ бөлгішін анықтаңыз. 
6. Есептеңіз 
 
модулі 10 бойынша 3
8
 
 
модулі 11 бойынша 3
8
5
7
 
7.  Жалпыланған  Евклид  алгоритмы  көмегімен  33х  +  16y  =  ЕҮОБ(33,16)  теңдеуге 
сай келетін х және у сандарды табыңыз. 
8. Есептеңіз 
  7
-1
 mod 10 
  3
-1
 mod 11 
 
 
 
 
11 АШЫҚ КІЛТІ БАР КРИПТОГРАФИЯЛЫҚ АЛГОРИТМДЕР ЖӘНЕ ОЛАРДЫ 
ПАЙДАЛАНУ 
 
Бұл бөлімде ең танымал ашық кілті бар криптографиялық алгоритмдер келтірілген: 
RSA,  Диффи-Хеллман  алгоритмы,  Эль-Гамаль  алгоритмы.  Әрбіреуінің  сипаттауы  толық 
мысалмен  қоса  беріледі.  Және  де  бұл  бөлімде  эллиптикалық  қисықтарға  негізделген 
криптографиялық жүйелердің жұмыс принципы тұжырымдалған. 
Бөлім  мақсаты:  ашық  кілті  бар  кейбір  криптографиялық  алгоритмдердің  жұмыс 
принципын зерттеу.  
 
11.1 RSA алгоритмы 
 
Негізгі мәліметтер 
Ашық кілті бар шифрлау алгоритмы RSA ХХ ғасырдың 70-ші жылдары ұсынылған 
болатын.  Оның  аты  авторлар  фамилиясының  бірінші  әріптерінен  жиңалған:  Р.Ривест 
(R.Rivest),  А.Шамир  (A.Shamir)  және  Л.Адлеман  (L.Adleman).  RSA  алгоритмы 
криптографиялық  жүйелерде  ең  кең  тараған  және  жиі  қолданылытың  ассиметриялық 
алгоритмы болып табылады.  
Алгоритмның негізінде мына факт жатыр: үлкен санды жай көбейткіштерге жіктеу 
өте  күрделі  есеп.  RSA  криптографиялық  жүйе  сандар  теориясындаға  келесі  екі  фактіге 
негізделеді: 
1.  сан жай ма деп тексеру есебі аса қиын емес; 
2.  n = pq ( р мен q — жай сандар) түрлі сандарды көбейткіштерге жіктеу есебі өте 
қиын, егер біз тек  n-ды ғана білетін болсак, ал р мен q — ұлкен сандар болса 
(мұны факторизациялау есебі деп атайды). 
RSA  алгоритмы  шифрлаудың  блокты  алгоритмы,  мұнда  шифрланған  және 
шифрланбаған деректер 0 мен n - 1 аралығында кейбір n үшін бүтін сандар түрде берілу 
керек.   
 
Шифрлау  
Сөйтіп  алгоритмды  қарастырайық.  Абонент  А  шифрланған  хабарды  абонент  Б-ға 
бергісі келеді. Бұл жағдайда абонент Б  екі кілт дайындау керек (ашық кілт; жабық кілт) 
және өзінің ашық кілтің пайдаланушы А-ға жібереді.  
Бірінші  кезең  ашық  пен  жабық  кілтті  жасау  (генерациялау).  Ол  үшін  алдымен 
екі үлкен жай сан таңдап алынады Р және Q.  Сосын көбейтіндісі есептеледі N: 
N = PQ. 
Осыдан кейін көмекші сан анықталады f: 

 
101 
f = (Р - l)(Q - 1). 
 
Сонан  соң  кездейсоқ  таңдап  алынады  d  <  f  саны  және  ол  f–пен  өзара  жай  болу 
керек. 
Онан әрі е санды табу керек, ол үшін 
еd mod f = 1. 
Сандар d және N пайдаланушының ашық кілті болып табылады, ал е мәні – жабық 
кілт.  
Сонымен, бұл кезеңде пайдаланушының қолында кестеде көрсетілген ақпарат болу 
керек:   
 
Ашық кілт  Жабық кілт 
Жүйе пайдаланушысы 
N, d 
e 
 
 
Пайдаланушы Б пайдаланушы А-дан шифрланған хабар алғысы келгендіктен, онда 
пайдаланушы  Б  өзінің  ашық  кілтің  (d,  N)  пайдаланушы  А-ға  жіберу  керек.  Р  мен  Q 
сандардың  енді  қажеті  жоқ,  бірақ  оларды  ешкімге  айтпаған  жөн;  ең  жақсысы  оларды 
жалпы ұмыту.  
 
Осымен кілттерді дайындау кезеңі аяқталады және деректерді шифрлау үшін  RSA 
негізгі протоколын пайдалануға болады.   
 
Екінші  кезең  –  деректерді  шифрлау.  Егер  абонент  А  кейбір  деректерді  Б 
абонентқа жібергісі келсе, ол өзінің хабарын цифрлық түрге келтіріп және оны m
1
, m
2
, m
3
, 
... блоктарға бөледі, мұнда m
i
 < N. Шифрланған хабар с
i
 блоктан тұрады.  
 
Абонент  А  өз хабарының  әрбір  блогын, пайдаланушы  Б-ның  ашық  параметрлерін 
пайдаланып, 
c
i
 = m
i
d
 mod N 
формула  бойынша  шифрлайды,  және  шифрланған  хабарды  С=(с
1
,  с
2
,  с
3
,  ...)  ашық  арна 
арқылы жібереді.  
 
Шифрланған хабарды алған абонент Б хабардың барлық блоктарын  
m
i
 = С
e
 mod N 
формула бойынша ашып оқиды. 
 
Барлық ашып оқылған блоктар тура А пайдаланушыдан шыққандай болады.  
 
Барлық  хабарларды  ұстап  алған  және  ашық  ақпаратты  білетін  қаскүнем,  Р  мен  Q 
үлкен мәндері болғанда, бастапқы хабарды табалмайды.  
 
11.2 Алгоритм бойынша есептеу алгоритмы 
 
 
Пайдаланушы А хабарды пайдаланушы Б-ға бергісі келеді. Бұл жағдайда алдымен 
пайдаланушы  Б  ашық  және  жабық  кілттерді  дайындау  керек.  Мысалы,  ол  келесі 
параметрлерді таңдап алсын: 
Р = 3, Q = 11, N = 3*11 = 33. 
Онда 
f = (Р - l)(Q - 1) = (3-1)(11-1) = 20. 
 
Сосын пайдаланушы Б  f-пен  ортақ бөлгіші жоқ кез келген d санды таңдайды (бұл 
сосын шифрланған хабарды бір мәнді қалпына келтіру үшін қажет болады). d = 13 болсын. 
Бұл сан ашық кілттін құрауышыларынын бірі болады. 
 
Онан  әрі  е  санды  табу  керек,  оны  хабарды  ашып  оқу  үшін  жабық  кілт  ретінде 
пайдалануға болады.  е мәні   
еd mod f = 1 
ара қатынасқа қанағаттандырылу керек. 
f–ң кіші мәндері үшін е–ны таңдау әдісі арқылы табуға болады. Жалпы жағдайда е–
ны  іздеу  үшін  жалпыланған  Евклид  алгоритмын  пайдалануға  болады.  Біздің  жағдайда 
келеді е=17 (тексереміз: 13*17 mod 20 = 221 mod 20 = 1).