Алгоритмдер жєне деректер структурасы

Алгоритм сипаттамасын берер алдында сандар теориясынан кейбір мәліметтерді еске түсірейік.

Біз 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)

a^p-11(mod p) .

a ^(p)-11(mod n). (3)

r₀ > r₁>0 оң бүтін сандары берілсін. Олардың ең үлкен ортақ бөлгішін (ЕҮОБ) табу үшін келесі есептеулер тізбегі орындалады.

r₀ = q₁ r₁ +r₂ , 021

r₁ = q₂ r₂ +r₃< r₂

...........................

r_m-2 = q_m-1 r_m-1 + r_m , 0mm-1

r_m-1 = q_mr_m

ЕҮОБ (r₀ ,r₁)=r_m

Кеңейтілген Евклид алгоритмі.

Келесі сандық тізбек анықтайық {t_i}^m_i=0 мұндағы

t₀=0, t_1=1, t_j=t_j-2-q_j-1t_j-1, j2 (4)

Лемма. Егер ЕҮОБ (r₀ ,r₁)=1

t_mr₁^-1(mod r₀) (немесе r₁ t_m1(mod r₀)) (5)

Ал енді алгоитмді сипаттайық:

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

2. 
   m хабарды шифрлау үшіноны алдын ала n-нен кіші блоктарға бөлінеді. Екілік деректер үшін ұзындығы l–ге тең блоктар алынады, мұндағы l 2^li=m_i^emod n
   
3. 
   Дешифрлау үшін m_i=c_i^d есептелінеді.
   

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

Тұтынушы 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

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

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

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

d=t₃=23

Ашық кілттер e=7, n=187 жариялап, жабық кілтті d=23 құпияда сақтаймыз. Қолайлылық үшін бастапқы мәтін ретінде M=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) mod187=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

=^dB mod n_B =c^eBdBmod n_B = v^(nB)k+1 mod n_B=(c^k)^(nB) c mod n_B=c

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