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).
Достарыңызбен бөлісу: |