Dsa ға кілттер құрау алгоритмі dsa қол қою және тексеру алгоритмдері

Кіріспе

Қазіргі күндерде ақпаратты өңдеудің жылдамдығының, сақтау және тасымалдау қауіпсіздігінің маңызы қатты өскендіктен, электронды – ақпараттық жүйелердің күнделікті өмірге қарыштап енуі түсінікті жайт. Сонымен қатар ақпаратқа қатысты жасалатын қылмыс түрлерінің көбейуіне байланысты, ақпаратты кез – келген деңгейде қорғай білу информатика және техника саласының өзекті мәселелеріне айналды.

Алдыңыздағы жұмыс ақпаратты қорғау және тексеру (авторизация) құралдарының кең тараған түрі – электронды қол қою сұлбаларына, соның ішінде – DSA сұлбасын қарастырады.

Электронды қол дегеніміз – тек қол қойылған хабарлама мәтініне байланысты және қол қоюшыға ғана белгілі құпия сан. Қойылған қолдар тексерілетіндей болуы тиіс. Хабарға қойылған қолдың, шынымен хабарды жазған адамға жату\жатпауын тексеру(авторизация) сол адамның құпия кілтінің көмегінсіз - ақ тексерілетіндей болуы қажет. Электронды қолдың негізгі қызметі – алынған хабардың өзінің шынайы авторына тиіс\тиіс еместігін тексеру, және оның тасымал кезіндегі қауіпсіздігін қамтамасыз ету.

DSA жұмыс механизмі – хабарласушы жақтардың әрқайсысы қос кілттен құрайды (ашық және құпия) да, ашық кілтті қолданып, ұзындығы шектеулі мәтінге(хабарға) қол қояды, сонан соң хабар алушыға жібереді (ашық кілт жасырусыз жарияланады). Егер хабар жеткізілу барысында, басқа бір жақ осы хабарды оқуға немесе өзгеруге әрекеттенсе, хабар мәтіні автоматты түрде танымастай болып өзгертіледі. Хабар алушы жақ, автордың ашық кілтін қолданып, алынған хабардың авторға тиістілігін (өзгертілмегендігін) тексереді. Егер тиістілік анықталса – хабар қабылданады, анықталмаса – қабылданбай, авторға арнайы ескерпе жіберіледі.

DSA (Digital signature algorithm) – 1991 жылдың тамыз айында АҚШ – тың Ұлттық Стандарттар және Технологиялар Институтымен(NIST) ұсынылған. Кейін DSA - АҚШ – тың Федералды Ақпарат Өңдеу Стандарты (FIPS 186) болып қабылданып, DSS (Digital Signature Standart) атанды.

Осы жұмыста қолданылмайтын, бірақ DSS – қа қатысты көптеген түсініктер мен анықтамалар, жұмыс көлемін керексіз көбейтпеу мақсатында, әдейі алынып тасталды. Бұнда қолданылатын барлық түсініктер мен амалдар математикада кеңінен таныс, сондықтан оларға тоқталмаймыз.

DSA – ға кілттер құрау алгоритмі

1. 
   2¹⁵⁹ 160 болатындай q жай санын таңдау керек;
   

2. 
   0  t  8 қанағаттандыратын t санын таңдау және q : (p-1) болатындай, сонымен қатар 2^511+64t 512+64t орындалатындай p санын таңдау қажет;
   

3.1) болатын g элементін таңдап, санын есептейміз;

3.2) Егер болған жағдайда, 3.1 бабына оралып,  - ны қайта есептеу керек;

4. 
   1  t  q-1 аралығынан кездейсоқ а бүтін санын таңдаймыз;
   

4. 
   санын есептеу керек;
   

4. 
   Шыққан нәтижелерден: Ашық кілт – (p,q,,y); Құпия кілт – а.
   

Кездейсоқ алынған санның жай\жай емес екендігін тексеру Миллер – Рабин жай санды анықтау ықтималдық тесті арқылы «оңай» іске асады.

Бізге n – тақ натурал саны берілсін. RANDOM(1, n-1) – 1  t  n-1 аралығында, ықтималдығы бірдей, а бүтін санын беретін кездейсоқ сандар генераторы болсын. Енді n-1 санын екілік жүйеде жазып: , - ді есептейміз. Есептеудің әрбір қадамында біз, mod n бойынша квадраты 1 ге тең, 1 мен n-1 ден өзгеше сан алған\алмағанымызды тексеріп отырамыз. Осы -ны есептеуді бөлек бір процедура – GOOD NUMBER (a, n) дейік:

%n-1=(bk,bk-1,....b0) – n-1 дің екілік жүйеде жазылуы%

1. 
   d  1
   
2. 
   for i  k downto 0
   
3. 
   do x  d
   
4. 
   d  (d*d) (mod n)
   
5. 
   if d = 1 & x 1& x  n-1
   
6. 
   then return TRUE
   
7. 
   if bi = 1
   
8. 
   then d  (d*a) (mod n)
   
9. 
   if d  1
   
10. 
    then return TRUE
    
11. 
    return FALSE
    

5 – 6 жолдарда біз 1 мен n-1 ге тең емес(де) тривиалды емес, 1 - ден квадрат түбір алған\алмағанымызды тексереміз. Егер ондай сан табылса, онда n – саны құрама, олай болса TRUE мәні қабылданады.

Енді d – ның қандай мәндер қабылдайтынын көрелік. болсын. Онда d – mod n бойынша келесі мәндерді қабылдайды:

(*)

Егер 1 ден алынған тривиалды емес квадрат түбірлер, осы (*) тізбегінен табылмаса, (9) жолда шартына тексереміз. Егер ол орындалмай, болса, онда n – саны құрама деген сөз. Бұл жағдайда TRUE мәні қабылданады. Басқа жағдайларда FALSE қабылданады.

Сонымен, егер а – n үшін «жақсы» сан болса, GOOD NUMBER (a, n) процедурасы TRUE мәнін қабылдайды, n – құрама сан. Егер FALSE мәні қабылданса, а – n үшін «жаман» сан, және ол сан барлық тексерулерден өтті.

Миллер – Рабин тестінде біз осы кездейсоқ сандар генераторын t рет қолданамыз (t – алгоритм параметрі):

1. 
   for j 1 to t
   
2. 
   do a  RANDOM (1, n-1)
   
3. 
   if GOOD NUMBER (a, n)
   
4. 
   then return COMPOSITE
   
5. 
   return PRIME
   

Сонымен, егер соңында біз COMPOSITE мәнін алсақ, n – құрама сан деген сөз. Ал егер PRIME мәнін алсақ, онда барлық кездейсоқ қабылданған а мәндері n үшін «жаман» деген сөз. Ал t санының өсуімен, PRIME мәні жағдайында, n – нің құрама сан болуының ықтималдығы 0 ге ұмтылатынын көрсетуге болады (Нижегородский Государственный Университет им. Н. И. Лобачевского, «Компьютерная алгебра», 90 – 105 беттер). Миллер – Рабин тестінің мәні осында.

Осы жұмыстың аяқ жағындағы, кілт құрау процедурасына жазылған компьтерлік бағдарламада, осы Миллер – Рабин алгоритмі, p,q жай сандарын таңдауда қолданылған (ассемблер) .

DSA – да қол қою және тексеру алгоритмдері
Түсініктеме: Хабар беруші жақ, ұзындығы шектеулі, m хабарына қол қояды. Хабар алушы жақ осы қолды хабар берушінің ашық кілті арқылы тексере алады.

1. 
   Қол қою процедурасы.
   

(b) санын есептейміз;

(c) есептейміз;

(d) санын есептейміз;

(e) m хабарының электронды қолы - (r,s) қосағы болады.

2. 
   Тексеру процедурасы ((r,s) – қолы қойылған m хабары алынды, (p,q,,y) ашық кілті белгілі делік).
   

(b) 0 < r< q және 0 < s < q шарттарына тексереміз, егер олар орындалмаса қолды қабылдамаймыз;

(c) және h(m) мәндерін есептейміз;

(d) мәндерін есептейміз;

(e) санын есептейміз;

(f) v=r болған жағдайда ғана қолды қабылдаймыз.

1. 
   (параметрлердің ұсынылатын өлшемдері). Кілт құрау алгоритміндегі q параметрінің өлшемі (FIPS 186 – ға сәйкес) 160 bit болуы , ал p мәні 64, 512 және 1024 bit өлшемді болуы ұсынылады. FIPS 186 1024 биттен үлкен жай сандармен жұмыс істемейді.
   
2. 
   (сәтсіздік ықтималдығы). Қойылған қолды тексеру процедурасында мәнін есептеуді қажет етеді. Ал s = 1 жағдайда s^-1 табылмайды! Бұндай жағдайды болдырмау үшін, қол қоюшы s  0 екенін тексеріп отыруы керек. Бірақ егер s - Z_q ден алынған кездейсоқ сан болса, s = 0 болу ықтималдығы шамамен (1/2) ¹⁶⁰ тең. Сонымен қатар, қол қоюшы r  0 екенін де қадағалап отыруы тиіс.
   

1. 
   A. Menezes, P.van Oorschot, S. Vanstone “Handbook of Applied Cryptography”, CRC press, 1996; 2, 4, 9, 11 – бөлімдер;
   
2. 
   Е. Р. Байсалов «Криптографияның математикалық негіздері», Алматы, «Қазақ Университеті», 2003;
   
3. 
   Ш. Ж. Мусиралиева «Прикладная криптография», Алматы, Издательство «Print S», 2004;
   
4. 
   Нижегородский Государственный Университет им. Н. И. Лобачевского, «Компьютерная алгебра», 2002;