Қазақша рефераттар

RSA алгоритмі туралы қазақша реферат

RSA криптожүйесі туралы

RSA криптожүйесін Рон Ривест (Ron Rivest), Ади Шамир (Adi Shamir) және Леонард Адлеман (Leonard Adleman) 1978 жылы ұсынған. Бұл алгоритм үлкен санды жай көбейткіштерге жіктеу есебінің күрделілігіне сүйенеді. Практикада RSA-ның беріктігі үлкен сандар арифметикасындағы есептердің күрделілігімен және кілт ұзындығын дұрыс таңдаумен қамтамасыз етіледі.

Негізгі идея

RSA екі кілтке негізделеді: ашық кілт (Public key) және жабық кілт (Private key). Ашық кілт шифрлау үшін жарияланады, ал жабық кілт құпия сақталып, дешифрлау және қолтаңба қою үшін қолданылады.

Терминдер

p, q
Екі үлкен кездейсоқ жай сан.
n = p·q
Модуль; ашық кілттің негізгі бөлігі.
φ(n) = (p−1)(q−1)
Эйлер функциясы (RSA есептеулерінде қолданылады).
e, d
e — ашық экспонента, d — оған кері мән (жабық экспонента).

RSA алгоритмінің қадамдары

1) Кілттерді генерациялау

  • p және q — екі үлкен жай сан таңдалады.
  • n = p·q есептеледі.
  • φ(n) = (p−1)(q−1) табылады.
  • e саны φ(n)-мен өзара жай болып таңдалады: gcd(e, φ(n)) = 1.
  • Кеңейтілген Евклид алгоритмі арқылы d табылады: d·e ≡ 1 (mod φ(n)).

2) Шифрлау

Хабар m алдын ала n-нен кіші блоктарға бөлінеді. Екілік деректер үшін блок ұзындығы l ең үлкен мән ретінде алынады, мұнда 2^l < n шарты орындалады.

Формула

cᵢ = mᵢ^e mod n

3) Дешифрлау

Қабылдаушы жабық кілт d арқылы бастапқы блоктарды қалпына келтіреді.

Формула

mᵢ = cᵢ^d mod n

Себебі d·e ≡ 1 (mod φ(n)), сондықтан m^(de) ≡ m (mod n) теңдігі орындалады (тиісті шарттарда).

Есептеу тиімділігі: неге жылдам әдіс керек?

Дәрежелеуді кезекпен көбейту арқылы тікелей есептеу өте тиімсіз: x^b мәніне жету үшін көптеген көбейту амалдары керек болады, әрі аралық нәтижелер өте үлкен сандарға айналады. Одан кейін модуль бойынша қалдықты табу да қымбатқа түседі.

Сондықтан RSA тәжірибеде дәрежелеуді тиімді есептеу үшін квадраттау және көбейту (square-and-multiply) әдісін қолданады: әр қадамда нәтиже mod n бойынша қысқартылып отырады, сол арқылы аралық мәндер шамадан тыс өсіп кетпейді.

RSA авторлары келтірген тест мысал

RSA авторлары алгоритм жұмысын көрсету үшін мына сөйлемді бастапқы мәтін ретінде алған: ITS ALL GREEC TO ME. Әр символ 5 разрядпен кодталады: бос орын — 0, A — 1, B — 2, …, Z — 26. Осылайша үлкен сан ретінде мына мән алынған:

Кодталған хабар

m₁ = 09201900011212000718050511002015001305

Ашық кілт

e = 9007

n = 11438162575788886766923577997614661201021829672124236256265184293570693524573389783059712363958705058989075147599290026879543541

Шифрмәтін

c = 1999351314978051004523171227402606474232040170589146310370371740625997160894892750439920962672582675012893554461353823769748026

Қадамдық мысал (шағын сандармен)

Есептеу логикасын толық көрсету үшін шағын сандармен мысал қарастырайық. Жай сандар ретінде p = 11, q = 17 таңдаймыз. Сонда n = 187, ал φ(n) = 160. gcd(e, 160) = 1 шарты орындалатындай e = 7 болсын.

d мәнін табу

Жабық кілт d мына теңдеуден табылады: 7d ≡ 1 (mod 160). Кеңейтілген Евклид алгоритмі үшін бөлулер тізбегі:

160 = 22·7 + 6

7 = 1·6 + 1

6 = 6·1 + 0

Нәтижесінде d = 23 алынады. Ашық кілт: (e, n) = (7, 187), жабық кілт: d = 23.

Шифрлау және дешифрлау

Қолайлылық үшін бастапқы хабарды M = 9 деп алайық. Шифрлау:

Шифрлау

C = 9^7 mod 187 = 70

Дешифрлау:

Дешифрлау

M = 70^23 mod 187 = 9

Үлкен сандармен жұмыс істегенде есептеулерді тиімді жүргізу үшін аралық нәтижені әр қадамда mod n бойынша қысқартып отыратын square-and-multiply тәсілі қолданылады.

RSA және электрондық қолтаңба

RSA алгоритмі шифрлау үшін ғана емес, электрондық қолтаңба қою үшін де қолданылады. Мысалы, Арман (A) Болатқа (B) қолтаңба қойылған хабар жіберсін. Екі тараптың кілттері:

A тараптың кілттері

Ашық: (nA, eA)
Жабық: dA

B тараптың кілттері

Ашық: (nB, eB)
Жабық: dB

Қолтаңба қою және жіберу

  1. Арман алдымен хабарды өзінің жабық кілтімен «қолтаңбалайды»: c = m^dA mod nA
  2. Содан кейін Болаттың ашық кілтімен шифрлайды: α = c^eB mod nB
  3. Алынған α мәнін Болатқа жібереді.

Тексеру және растау

  1. Болат алдымен өз жабық кілтімен ашады: β = α^dB mod nB
  2. Осыдан кейін Арманның ашық кілті арқылы тексереді (мәні c қайта шығады). Нәтижесінде Болат хабарды шынымен Арман жібергеніне көз жеткізеді.
  3. Бұл схема аутентификация мен мойындамауды болдырмау (non-repudiation) қасиеттерін қамтамасыз етеді: Арман кейіннен «мен жіберген жоқпын» деп бас тарта алмайды, өйткені хабарда оның электрондық қолтаңбасы бар.