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 2l<n теңсіздігі орындалатындай ең үлкен сан. Шифрмәтін келесі формуламен анықталады:

ci = mie mod n

3)  Дешифрлау үшін mi = cid mod n есептелінеді.

Расында, (1), (2) және (3) формулаларын қолдана отырып алатынымыз

cid mod n = (mie mod n)d mod n = mied mod n = mik φ(n)+1 mod n = (((mik)φ(n) mod n) * (mi mod n)) mod n = mi.

Ең алдымен осы криптожүйедегі шифрлау жылдамдығын қарастырайық. Егер біз x-тың b дәрежесін тізбектей есептесек: х-ты х-қа көбейтіп х2-ты тапсақ, сонан соң х-қа көбейтіп х3-ты тапсақ, осылайша жалғастырып ең соңында хb-ны тапсақ, онда бұл есептеулерді жүзеге асыру үшін bn2-тан көп қарапайым амал қажет, ендеше өте жылдам компьютермен осы bn2  2300*3002 амалды есептегеннің өзінде сұмдық көп уақыт кетеді. Сонан соң шыққан өте үлкен санды тағы 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

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

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

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

q1 = 22; q2 = 1; q3 = 6

t0 = 0; t1 = 1; t2 = 0-22*1 = -22; t3 = 1+1*22 = 23;

d = t3 = 23.

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

C = 97 mod 187 = ((92)3*9) mod 187 = (((81)2 mod 187)*(729 mod 187)) mod 187 = (16 mod 187)*(168 mod 187) mod 187 = 70.

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

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

7023 mod 187 = ((702)11*70) mod 187 = 9.

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

A: Public nA, eA, Private dA

B: Public nB, eB, Private dB.

Арман алдымен m хабарын өзінің жабық кілтімен шифрлайды: c = mdA mod nA. Содан кейін Болаттың ашық кілтімен α = ceB mod nB шифрлайды.

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

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