RSA алгоритмі

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

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

Алгоритмнің беріктілігі дискреттік логарифмді есептеудің қиындығы мен үлкен сандардың қиындығының мәніне негізделеді.

Сиппатамасы:

1)  Екі үлкен кездейсоқ жай p және q сандары таңдап алынады. Көбейтіндісі табылады n = p*q. Енді (p-1)*(q-1) санымен өзара жай кездейсоқ e саны таңдап алынады. Кеңейтілген алгоритмнің көмегімен келесі d кері саны есептелінеді

de ≡ 1(mod(p-1)(q-1))

2)  m хабарды шифрлау үшін оны алдын ала n-нен кіші блоктарға бөледі. Екілік деректер үшін ұзындығы l-ге тең блоктар алынады, мұндағы l 2^l<n теңсіздігі орындалатындай ең үлкен сан. Шифрмәтін келесі формуламен анықталады:

c_i = m_i^e mod n

3)  Дешифрлау үшін m_i = c_i^d mod n есептелінеді.

Расында, (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.

Ең алдымен осы криптожүйедегі шифрлау жылдамдығын қарастырайық. Егер біз x-тың b дәрежесін тізбектей есептесек: х-ты х-қа көбейтіп х²-ты тапсақ, сонан соң х-қа көбейтіп х³-ты тапсақ, осылайша жалғастырып ең соңында х^b-ны тапсақ, онда бұл есептеулерді жүзеге асыру үшін bn²-тан көп қарапайым амал қажет, ендеше өте жылдам компьютермен осы bn²  2³⁰⁰*300² амалды есептегеннің өзінде сұмдық көп уақыт кетеді. Сонан соң шыққан өте үлкен санды тағы n-ға бөліп қалдығын есептеу қажет. Әрине, бұл әдісті іс жүзінде асыру мүмкін емес.

Тұтынушы n,e кілттерін ашық деп (Public key) жариялайды, ал d кілті жабық кілт болып саналады (Private key).

RSA aвторлары криптожүйенің жұмысын түсіндіру үшін келесі тестілік мысал келтіреді. Бастапқы мәтін ретінде төмендегі сөйлем таңдап алынған:

ITS ALL GREEC TO ME

Әр символға 5 разряд арнап, бос орынды – 0, А әрпін – 1, В әрпін – 2, … , Z әрпін – 26 деп кодтаған. Келесі үлкен сан алған m1 =

09201900011212000718050511002015001305.

Ашық кілттердің мәні ретінде е = 9007, n =

11438162575788886766923577997614661201021829672124236256265184293570693524573389783059712363958705058989075147599290026879543541

деп алынған.

Сонда шифрланған санның түрі келесідей болып шықты:

с=1999351314978051004523171227402606474232040170589146310370371740625997160894892750439920962672582675012893554461353823769748026.

Енді біз есептеу алгоритімін толық сипаттайтын мысал келтірейік.

Мысал. Жай сандар ретінде p = 11, q = 17 таңдап алайық. Онда n = p*q = 187, φ(n) = (p-1)*(q-1) = 160.

Кез-келген φ(n)-мен өзара жай e санын таңдайық, яғни (e, 160) = 1. Мысалға, e = 7 болсын. Келесі теңдеуден d жабық кілтін табу керек:

7d = 1 mod 160

Алдында келтірілген кеңейтілген Евклид алгоритмін қолданамыз. Енді Евклид алгоритміне сүйеніп q_i мәндерін табу үшін келесі есептеулер тізбегін табамыз:

160 = 22*7+6, 7 =1*6+1, 6 = 6*1.

Ақыры алатынымыз:

q₁ = 22; q₂ = 1; q₃ = 6

t₀ = 0; t₁ = 1; t₂ = 0-22*1 = -22; t₃ = 1+1*22 = 23;

d = t₃ = 23.

Ашық кілттер е = 7, n = 187 жариялап, жабық кілтті d = 23 құпияда сақтаймыз. Қолайлылық үшін бастапқы мәтін ретінде М = 9 деп алып, С шифрланған мәтінің табамыз.

C = 9⁷ mod 187 = ((9²)³*9) mod 187 = (((81)² mod 187)*(729 mod 187)) mod 187 = (16 mod 187)*(168 mod 187) mod 187 = 70.

Шифрлау кезінде өте үлкен сандармен жұмыс істемеу үшін сандарды біртіндеп алдымен квадраттап нәтижені n модулі бойынша алады. Сонда n² санынан артық сан пайда болмайды. Бұл тәсілді «квадраттау да, көбейту» (ағылшынша «square-and-multiply») деп атайды.

Хабарды алушы оны дешифрлау үшін d жабық кілтін қолданады:

70²³ mod 187 = ((70²)¹¹*70) mod 187 = 9.

Алгоритм RSA – ді шифрлау үшін ғана емес қолтаңба алу үшін де қолдануға болады. Арман (А) жолдасы Болатқа (Б) қолтаңба қойылған шифрланған хабарды жіберуі керек болсын. Арман мен Болат өздерінің ашық және жабық кілттерін табады.

A: Public n_A, e_A, Private d_A

B: Public n_B, e_B, Private d_B.

Арман алдымен m хабарын өзінің жабық кілтімен шифрлайды: c = m^d_A mod n_A. Содан кейін Болаттың ашық кілтімен α = c^e_B mod n_B шифрлайды.

Алынған α мәнін Болатқа жібереді. Болат хабарды алдымен өзінің жабық кілтін қолданып ашады да соңынан Арманның ашық β = α^d_B mod n_B = c^e_B^d_B mod n_B = c^φ(n_B^{) k+1} mod n_B = (c^k)^φ(nB) c mod n_B = c кілтін қолданады.

Бұл есептеулерді орындай отырып, Болат жіберілген хабардың иесі шынымен Арман екендігіне қол жеткізеді, ал Арман кейіннен бұл құжаттан бас тарта алмайды, өйткені құжатта оның электрондық қолы қойылған.