ПОӘК 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 сандарының арасындағы қатынас былай жазылады
a
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-мен өзара жай саны үшін келесі салыстыру
ақиқат
a
(p)-1
1(mod n). (3)
Евклид алгоритмі
r
0
> r
1
>0 оң бүтін сандары берілсін. Олардың ең үлкен ортақ бөлгішін (ЕҮОБ) табу үшін
келесі есептеулер тізбегі орындалады.
r
0
= q
1
r
1
+r
2
, 0
2
1
r
1
= q
2
r
2
+r
3
< r
2
...........................
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
k
(n)+1
mod n = (((m
i
k
)
(n)
mod n) * (m
i
mod n )) mod n =
m
i
Тұтынушы 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
