А. Ж. Асамбаев криптография негіздері



жүктеу 2.01 Mb.
Pdf просмотр
бет13/19
Дата15.03.2017
өлшемі2.01 Mb.
1   ...   9   10   11   12   13   14   15   16   ...   19

3-ші қасиет. Егер 
a   b (mod m
онда 
a
k
   b
k
 (mod m),  k   N
Мысалы, 25   4 (mod 7) болғандықтан, онда 5
2
   2
2
 (mod 7). 
4-ші қасиет. Егер 
ac   bc (mod m) 
және c  m-мен өзара жай болса, 
онда 
a   b (mod m). 
Мысалы, 1200   45 (mod 7) белгілі, ал 1200 = 15 80 және 45 = 15 3, онда 
80   3 (mod 7). 
5-ші қасиет. Егер 
ac   bc (mod mc) 
онда 
a   b (mod m). 
Мысалы, егер 44   4 (mod 4(10)) онда 11   1 (mod 10). 
 
10.5 Ферманың кіші теоремасы 
 
RSA  жүйесі  бойынша  шифрлау  алгоритмның  негізінде  XVII  ғасырдың  басында 
француз  математигі  Пьер  Ферма  (Pierre  Fermat)  тұжырымдаған  теорема  жатыр.  Оны 
«Ферманың кіші теоремасы» деп жиі атайды, және танымал «Ферманың ұлы теоремасы» 
мен  шатастырмау  керек.  Оны  да  ол  дәлелдемей  тұжырымдаған  болатын,  ал  дәлелденген 
тек  1993-94  жылдары.  Леонард  Эйлер  1760  жылы  Ферманың  кіші  теоремасын  дәлелдеп, 
оның  Ферма-Эйлер  теоремасы  деп  аталатын  жалпылауын  тапқан  болатын.  Дәл  осы 
теорема шифрлау/дешифрлау RSA алгоритмда пайдаланады.  
Ферманың кіші теоремасы келесі түрде тұжырымдалады. Егер р – жай сан, ал m – 
р-ға бөлінбейтің кез келген сан болса, онда  
m
p-1
   1 (mod р), 
яғни m
p-1
 саны р-ға бөлінгенде қалдықта 1 береді.  
Мысалы, р=11, m = 3 болсын. 3
10
 mod 11 біргі тең болама тексерейік: 
3
10
 mod 11 = 3
2
(((3
2
)
2
)
2
) mod 11 = 9(4
2
) mod 11 = 144 mod 11 = 1 
Эйлер тұжырымдаған және дәлелдеген жалпылау кез келген модуль үшін әділетті, 
бірақ  RSA  жүйеде  дербес  жағдайы  пайдаланылады  –  онда  модуль  тек  екі  түрлі  жай 
сандарының  көбейтінідісі  болып  табылады.  Сондықтан  осы  жағдайы  үшін  теореманың 
тұжырымдамасын қарастырайық. 
Ферма-Эйлер теоремасы (RSA жүйенің жағдайы үшін). Егер  p мен  q – екі  түрлі 
жай сандар, ал m – p мен q-ға бөлінбейтің кез келген сан болса, онда 
m
(p-1)(q-1)
   1 (mod рq). 
Мысалы,  р = 11, q = 5 (pq = 55), m = 3 болсын. 3
40
   1 (mod 55) біргі тең болатының 
тексерейік: 
3
40
 mod 55 = (3
5
)

mod 55 = 23
4
 mod 55 = 279841 mod 55 = 1. 
 
 

 
97 
10.6 Ең үлкен ортақ бөлгіш 
 
а мен b — екі бүтін оң сандар болсын. а мен b сандардың ең үлкен ортақ бөлгіші - 
бұл а-ны да b-ны да бөлетін ең үлкен с саны: 
с = ЕҮОБ(ab). 
Мысалы,  ЕҮОБ(25,35) = 5. 
Ең  үлкен  ортақ  бөлгішті  табу  үшін  келесі,  Евклид  алгоритмы  деп  аталатын, 
алгоритмды пайдалануға болады. 
Алгоритм NOD(бүтін abc); 
Басы 
   1. a<>b болғанша орындау керек: 
         1.1. Егер a>b онда a:=a-b, әйтпесе b:=b-a
   2. c:=a
Соңы. 
 
Алгоритм орындалғаннан кейін нәтижесі с айнымалының ішінде болады.  
Евклид алгоритмы көмегімен ЕҮОБ(18,9) есептеп көрейік: 
a:    18    9 
b:     9    9 
c:     9    9 
Мұнда әрбір баған алгоритмның кезекті итерациясы болып табылады. Процесс жүргізіледі 
b    a-ға  тең  болғанша.  Сонда  с  айнымалыға  жауап  жазылады,  біздің  жағдайда  9.  Дәл  осы 
ЕҮОБ(18,9)-ң мәні.  
 
10.7 Евклидтың жалпыланған алгоритмы 
 
Көптеген  криптографиялық  жүйелер  үшін  Евклидтың  жалпыланған  алгоритмы 
актуальды, онымен келесі теорема байланысады. 
Теоремаа мен  b — екі  бүтін оң сандар болсын. Сонда  х пен у бүтін (оң емес те 
болу мүмкін) сандар бар болады, олар үшін  
ах + by = ЕҮОБ(a,b). 
Евклидтың  жалпыланған  алгоритмы  ЕҮОБ(а,  b)-ны  және  жоғары  жазылған 
теңдеуге сай келетін ху іздеп табу үшін қызмет етеді. Үш жол енгізейік U = (u
1
,u
2
,u
3
), V = 
(v
1
,v
2
,v
3
) және T = (t
1
,t
2
,t
3
). 
Алгоритм келесі түрде жазылады (кіру параметрде шарт a b орындалу керек). 
Алгоритм ЕЖА(бүтін ab); 
Басы 
  1. U = (a,1,0), V = (b,0,1). 
  2. v1 <> 0 болғанша орындау керек: 
    2.1. u1 div v1; 
    2.2. =(u1 mod v1, u2–qv2, u3–qv3); 
    2.3. U=VV=T
  3. U=(ЕҮОБ(a,b),x,y)). 
Соңы. 
 
Алгоритм аяқталғаннан кейін нәтижесі жолында болады. Алгоритмдағы div операциясы 
– бұл бүтін сандық бөлу операция.  
Мысалы.  а  =  18,  b  =  9  болсын.  Теңдеуге  сай  келетін  х  және  у  сандарды  іздеп 
табайық 
18х + 9y = ЕҮОБ(18,9). 
 
Алгоритмды қадам бойынша орындайық: 
 

 
98 




u
1
  u
2
  u
3
  v
1
  v
2
  v
3
 
t
1
 
t
2
 
t
3
 
18 div 9 = 2  18  1  0  9  0  1  18 mod 9 = 0  1 - 2 0 = 1  0 - 2 1 = -2 
 
9  0  1  0  1  -2 
 
 
 
 
Нәтижесінде аламыз = (ЕҮОБ(a,b),x,y)) = (9,0,1). 
Тексереміз:  18 0 + 9 1 = 9 = ЕҮОБ(18,9). 
 
10.8 Модулі бойынша инверсия 
 
Криптографияның көптеген есептерінде берілген сm сандар үшін іздеп табу керек 
d < m санды, ол үшін  
cd mod m = 1. 
Осындай болады тек сонда ғана, егер с мен m сандар өзара жай болатын болса. 
cd mod m=1 теңдеуге сай келетін d саны, модулі m бойынша с инверсиясы деп 
аталады  және  жиі  белгіленеді    с
-1
  mod  m.  Инверсия  үшін  берілген  белгіле    cd  mod  m=1 
теңдеуді былай жазуға болатынымен байланысты 

-1
 mod m = 1. 
Сонымен,    модулі  m  бойынша  есептеулерде  с
-1
-ге  көбейту  с-ға  бөлуге  сәйкес 
болады. 
Модулі m бойынша инверсияны Евклидтың жалпыланған алгоритмы көмегімен де 
есептеуге болады.  
Мұны көрсетейік. Төменірек  жазылған теңдеудің мағынасы  – кейбір бүтін  үшін 
cd  –  km  =  1  теңдеу  орын  алады.  с  мен  d  өзара  жай  болатының  еске  алып,  бұл  теңдеуді 
келесі түрде өзгертуге болады: 
m(-k) + cd = ЕҮОБ(m,c). 
Демек,  біз  Евклидтың  жалпыланған  алгоритмы  көмегімен  с
-1
  mod  m  (немесе  d 
санды  табу)  есептей  аламыз.  Бұл  кезде  айнымалы  k  мәні  бізге  керек  емес.  Егер  d  саны 
теріс болып табылса, онда оған қосу керек, өйткені анықтама бойынша  a mod m  саны 
{0,1,...,m-1}жиыннан алынады.  
Мысал  қарастырайық.  m=9,  c=5  болсын.  5
-1
  mod  9  табайық.  Барлық  есептеуді 
қадам  бойынша  жазып  отырып,  Евклидтың  жалпыланған  алгоритмы  бойынша  есептеуді 
жүргізейік.  
 




u
1
  u
2
  u
3
  v
1
  v
2
  v
3
 
t
1
 
t
2
 
t
3
 
9 div 5 = 1  9  1  0  5  0  1  9 mod 5 = 4  1 - 1 0 = 1  0 - 1 1 = -1 
5 div 4 = 1  5  0  1  4  1  -1  5 mod 4 = 1  0 - 1 1 = -1  1 - 1 (-1) = 2 
4 div 1 = 4  4  1  -1  1  -1  2  4 mod 1 = 0  1 - 4 0 = 1  -1 - 4 2 = 7 
 
1  -1  2  0  1  7 
 
 
 
 
Сонымен, аламыз 5
-1
 mod 9 = 2.  Тексереміз:  5 2 mod 9 = 10 mod 9 = 1. 
 
 
 
 
 
 

 
99 
Негізгі терминдер 
 
Евклид  алгоритмы  –  екі  санның  ең  үлкен  ортақ  бөлгішін  іздеп  табуға  мүмкін 
беретін математикалық алгоритм. 
Өзара жай сандар – ортақ бөлгіштері жоқ (бірден басқа) сандар. 
Факторизациялау  есебі  –  көбейткенде  берілген  санды  беретін  екі  не  одан  көп 
натурал сандарды табу. 
Модулі  бойынша  инверсия  –  берілген  санға  модуль  бойынша  көбейткенде 
нәтижесінде бірді беретің натурал сан. 
Көбейткіштерге канондық жіктеу -  барлық көбейткіштер жай болып өсу ретінде 
жазылған көбейткіштерге жіктеу.  
Ферманың  кіші  теоремасы  –  RSA  жүйесі  бойынша  шифрлаудың  негізінде 
жататын танымал теоремасы. 
а мен  b сандардың  ең үлкен ортақ бөлгіші - а-ны да  b-ны да бөлетін ең үлкен  с 
саны:  с = ЕҮОБ(ab). 
Арифметиканың негізгі  теоремасы - кез келген бірден  үлкен натурал сан не өзі 
жай  болады,  не  жай  бөлгіштердің  көбейтіндісіне  жалғыз  ғана  тәсілмен  жіктелу  мүмкін 
(егер көбейткіштердің жол ретін еске алмайтын болсақ). 
Жай сан - өзінен және бірден басқа бөлгіштері болмайтын натурал сан. 
Құрама сан - өзінен және бірден басқа тағы да бір санға бөлінетің натурал сан. 
Эйлер  функциясы  -  n-нан  аспайтын  және  n-мен  өзара  жай  болатын  натурал 
сандардың саның есептеуге мүмкіндік беретін функция. Белгіленеді  (n). 
 
Сұрақтар 
 
1.  Жай  және  құрама  санның  анықтамасын  беріңіз.  Жай  және  құрама  сандарының 
үш-үштен мысалдарын келтіріңіз. 
2. «Өзара жай сандар» ұғымының анықтамасын беріңіз. Өзара жай сандардың және 
өзара жай болмайтын сандардың мысалдарын келтіріңіз. 
3. Арифметиканың негізгі теоремасын тұжырымдап беріңіз. 
4. Факторизациялау есебі деген не? 
5. Ең үлкен ортақ бөлгіші анықтамасын беріңіз. 
6. Екі санның ең үлкен ортақ бөлгішін табу үшін Евклид алгоритмды тұжырымдап 
беріңіз. 
7. Ферманың кіші теоремасын тұжырымдап беріңіз. 
8. Ферма-Эйлер теоремасын тұжырымдап беріңіз (RSA жүйесінің жағдайы үшін). 
9. Жалпыланған (кеңейтілген) Евклид алгоритмын тұжырымдап беріңіз. 
10.  «Модуль  бойынша  алу  операцияны»  орындау  принциптерін  тұжырымдап 
беріңіз. Осы операцияның орындау мысалдарын келтіріп түсіндіріп беріңіз. 
11. Модулі бойынша инверсия деген не? 
 
Жаттығулар 
 
1.  37, 59, 67, 93, 101, 111, 231 сандар жай сан болама? 
2. Өзара жай сандар болама: 
 
16 мен 37 
 
16, 37 және 38 
 
5, 9, 27 және 54 
 
2, 4, 7, 15, 59 
3.  59-дан  аспайтын  және  59-бен  өзара  жай  болатын  натурал  сандардың  саның 
табыңыз. 

 
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 аралығында кейбір үшін бүтін сандар түрде берілу 
керек.   
 
Шифрлау  
Сөйтіп  алгоритмды  қарастырайық.  Абонент  А  шифрланған  хабарды  абонент  Б-ға 
бергісі келеді. Бұл жағдайда абонент Б  екі кілт дайындау керек (ашық кілт; жабық кілт) 
және өзінің ашық кілтің пайдаланушы А-ға жібереді.  
Бірінші  кезең  ашық  пен  жабық  кілтті  жасау  (генерациялау).  Ол  үшін  алдымен 
екі үлкен жай сан таңдап алынады Р және Q.  Сосын көбейтіндісі есептеледі N
N = PQ
Осыдан кейін көмекші сан анықталады f

 
101 
f = (Р - l)(Q - 1). 
 
Сонан  соң  кездейсоқ  таңдап  алынады  d  <  f  саны  және  ол  f–пен  өзара  жай  болу 
керек. 
Онан әрі е санды табу керек, ол үшін 
еd mod f = 1. 
Сандар және N пайдаланушының ашық кілті болып табылады, ал е мәні – жабық 
кілт.  
Сонымен, бұл кезеңде пайдаланушының қолында кестеде көрсетілген ақпарат болу 
керек:   
 
Ашық кілт  Жабық кілт 
Жүйе пайдаланушысы 
Nd 

 
 
Пайдаланушы Б пайдаланушы А-дан шифрланған хабар алғысы келгендіктен, онда 
пайдаланушы  Б  өзінің  ашық  кілтің  (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 = 13 болсын. 
Бұл сан ашық кілттін құрауышыларынын бірі болады. 
 
Онан  әрі  е  санды  табу  керек,  оны  хабарды  ашып  оқу  үшін  жабық  кілт  ретінде 
пайдалануға болады.  е мәні   
еd mod f = 1 
ара қатынасқа қанағаттандырылу керек. 
f–ң кіші мәндері үшін е–ны таңдау әдісі арқылы табуға болады. Жалпы жағдайда е
ны  іздеу  үшін  жалпыланған  Евклид  алгоритмын  пайдалануға  болады.  Біздің  жағдайда 
келеді е=17 (тексереміз: 13*17 mod 20 = 221 mod 20 = 1). 

 
102 
Енді пайдаланушы Б өз жабық кілтің 17 есте қалдыру керек, ашық кілтті (13, 33)  А 
пайдаланушыға жіберу керек және Р=3 мен Q=11 сандарды жою керек.   
Ашық  кілтті  (13,  33)  алған  пайдаланушы  А,  N=33  тең  болғанын  көріп  бастапқы 
хабарды  үш  блокқа  бөледі,  әрбіреунің  мәні  N–нан  кем.  Мысалы,  үш  блок  болсын  m
1
=8, 
m
2
=27, m
3
=5. Сосын пайдаланушы А әрбір блокты шифрлайды:  
c

= 8
13
 mod 33 = 17 
c
2
 = 27
13
 mod 33 = 15 
c
3
 = 5
13
 mod 33 = 26. 
Үш  блоктан  (17,  15,  26)  тұратын  шифрланған  хабар  Б  пайдаланушыға  жіберіледі. 
Ол өз жабық кілтін е=17 және N=33 пайдаланып, хабарды ашып оқиды:  
m
1
 = 17
17
 mod 33 = 8 
m
2
 = 15
17
 mod 33 = 27 
m
3
 = 26
17
 mod 33 = 5. 
Сонымен, абонент А-дан алынған хабарды абонент Б ашып оқыды. 
 
11.3 RSA алгоритмның тәжірибелік пайдалануының сұрақтары 
 
RSA  алгоритмға  негізделген  ашық  шифрлау  кең  тараған  шифрлау  PGP  пакетте, 
Windows  операциялық  жүйеде,  әртүрлі  Интернет-браузерлерде,  банктік  компьютерлік 
жүйелерде қолданылады. Одан басқа, әртүрлі ашық кілті бар шифрлаудың және цифрлық 
қолды  жасаудың  халықаралық  стандарттары  RSA-ны  негізгі  алгоритм  ретінде 
пайдаланады.  
Шифрлаудың  жоғары  сенімділігін  қамтамасыз  ету  үшін  мынау  қажет:  модуль 
ретінде шығатын саны өте үлкен болу керек – бірнеше жүздеген немесе мыңдаған бит. 
Тек бұл жағдайда ғана, ашық параметрі бойынша, жабық кілтті анықтау мүмкін емес деп 
күтуге болады. Мысалы, 1995 жылы 500-таңбалы модулі үшін RSA шифрын ашып алды. 
Ол үшін Интернет желі көмегімен мыңнан астам компьютер бірлесіп жұмыс істеді.    
RSA-ның  авторлары  N  модульдің  келесі  параметрлерін  пайдалануға  ұсыныс  берді 
(2004  жылы):  768  бит  –  жеке  меншік  адамдар  үшін;  1024  бит  –  коммерциялық  ақпарат 
үшін;  2048  бит  -  өте  құпиялы  ақпарат  үшін.  Олардың  ұсыныстарынан  біраз  уақыт  өтті, 
сондықтан, қазіргі пайдаланушылар кілт мөлшерін өсіруіне назар аудару керек. Бірақ, кілт 
мөлшері неғұрлым үлкен болса, соғұрлым жүйенің жұмысы баяу болады. Сондықтан, кілт 
мөлшерін қажетсіз өсіре беру мағынасыз.  
Кілт  мөлшерімен  RSA-ның  тағы  бір  жүзеге  асыру  аспектісі  байланысты  – 
есептеуіш. Алгоритмды пайдалануда есептеулер қажетті кілттерді жасау кезінде де және 
шифрлау/дешифрлау  кезінде  де.  Мұнда  кілт  мөлшері  неғұрлым  үлкен  болса,  соғұрлым 
есептерді орындау қиын болады. Аса үлкен сандармен жұмыс істеу үшін ұзын арифметика 
аппаратын  пайдалану  керек.  Көп  жүздеген  биттен  тұратын  сандар  көпшілік 
микропроцессорлардың  регистрларына  кіре  алмайды,  сондықтан  оларды  бөліктеп  өңдеу 
керек. Бұл кезде шифрлау мен дешифрлау да үлкен бүтін санды модулі бойынша бүтін 
дәрежеге  көтеруді  қосады.  Тура  есептерде  аралық  мәндер  тым  айтқысыз  болар  еді. 
Есептеу  процесті  оңайлату  үшін,  үлкен  сандармен  жұмыс  істеуге  арнайы  алгоритмдер 
пайдаланады,  олар  модульды  арифметиканың  қасиеттеріне  және  дәрежеге  көтеруді 
оптимизациялауға негізделген.  
RSA  алгоритмы  бағдарламалық  та  аппараттық  та  түрде  жүзеге  асырылады. 
Көптеген  әлемдік  фирмалар  шифрлауда  RSA  алгоритмын  орындайтын  мамандырылған 
микросхемалар шығарады. Бағдарламалық жүзеге асырулар аппараттықтан бірталай баяу.   
RSA-ның  бағдарламалық  шифрлау  артықшылықтарына  жатады:  параметрлерді  икемділік 
күйге келтіру мүмкіндігі, программалық пакеттерге интеграциялау мүмкіндігі. Толығымен 
айтқанда,  RSA-ның  бағдарламалық  та  аппараттық  та  жүзеге  асыруы,  симметриялық 
алгоритммен салыстырғанда (мысалы ГОСТ 28147-89), орындауға шамамен мың есе көп 
уақыт талап етеді. 

 
103 
RSA алгоритмы электронды цифрлық қол қоюды құрастыруға және де кілттермен 
алмасу үшін пайдалану мүмкін. Электронды қол қоюды құрастыру мүмкіндігінің себебі – 
бұл  жүйеде  құпиялы  да  ашық  та  кілттер  тең  құқылы.  Кілттердің  әрбіреуі  d  немесе  
шифрлау  үшін  де  дешифрлау  үшін  де  пайдалану  мүмкін.  Бұл  қасиет  ашық  кілті  бар 
криптожүйелердің бәрінде орындалмайды.  
 
11.4 Диффи-Хеллман алгоритмы 
 
Негізгі мәліметтер 
Осы алгоритмның алғашқы жариялауы ХХ ғасырдың 70-ші жылдары Диффи және 
Хеллман  мақаласында  шықты.  Диффи-Хеллман  алгоритмы  хабарларды  шифрлау  немесе 
электронды  қол  қоюды  құрастыру  үшін  пайдаланбайды.  Оның  міндеті  –  кілттерді 
үлестіру. Ол екі не одан көп пайдаланушыларға делдалсыз кілттермен алмасуға мүмкіндік 
береді,  сосын  бұл  кілт  симметриялық  шифрлау  үшін  қолданылады.  Бұл  қорғалған  арна 
арқылы  жіберілетің  құпиялы  кілтсіз  ақпаратты  қорғауға  мүмкіндік  беретін  алғашқы 
криптожүйе болатын. Диффи мен Хеллман ұсынған кілттерді  үлестірудің ашық  схемасы 
криптографияда кәдімгідей төңкеріс жасады, себебі классикалық криптографияның негізгі 
проблемасын шешті - кілттерді үлестіру проблемасын. 
Алгоритм дискретты логарифмды есептеу операциясының күрделігіне негізделген. 
Бұл  алгоритмде  есептеулер  кейбір  үлкен  жай  санның  Р  модулі  бойынша  жүргізіледі. 
Алдымен арнайы түрде Р–дан кіші кейбір натурал сан А таңдап алынады. Егер біз мәнді 
шифрлайтын болсақ, онда есептейміз  
Y = A
X
 mod P
Х-ты  біле  отырып  Y–ты  есептеу  оңай.  Y–тан Х-ты  есептеудің  кері  есебі  жеткілікті 
күрделі  болады.  Х  экспонентасы  Y–тын  дискретты  логарифмы  деп  аталады.  Сонымен, 
дискретты  логарифмның  есептеу  күрделігін  біліп,  Y  санды  ашық  түрде  қандай  да 
байланыс  арна  арқылы  жіберуге  болады,  өйткені  P–нын  үлкен  модулінде  бастапқы  Х 
мәнін  табу  мүмкін  емес  деп  айтуға  болады.  Кілтті  құрастыру  үшін  Диффи-Хеллман 
алгоритмы осы математикалық фактісіне негізделген. 
 
Каталог: modules -> kaf -> inf -> images
kaf -> Қазақстан Республикасы Білім және ғылым министрлігі Павлодар мемлекеттік педагогикалық институты
kaf -> Қазақстан Республикасы Білім және ғылым министрлігі Павлодар мемлекеттік педагогикалық институты
kaf -> Ерғалиев Қуаныш Советұлы Ерғалиева Самал Жанатқызы КӘсіби қазақ тілі «Дене шынықтыру және спорт»
kaf -> Қазақстан Республикасы Білім және ғылым министрлігі Павлодар мемлекеттік педагогикалық институты
images -> Т.Қ. Қойбағарова, Р. А. Ельтинова


Поделитесь с Вашими друзьями:
1   ...   9   10   11   12   13   14   15   16   ...   19


©emirsaba.org 2019
әкімшілігінің қараңыз

    Басты бет