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



Дата02.07.2016
өлшемі75.69 Kb.
#173061

Мазмұны



  1. Кіріспе




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

  2. DSA - қол қою және тексеру алгоритмдері

  3. Ескертулер

  4. Қосымша - DSA – ға кілт құрау алгоритмінің бағдарламалық түрде іске асырылуы




  1. Қорытынды




  1. Қолданылған әдебиеттер


Кіріспе

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

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

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

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

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

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

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



Түсініктеме: хабарлама алмастырмақшы екі жақтың әрқайсысы ашық және құпия кілттерді құрауы қажет. Ол үшін олар төмендегі амалдарды істеуі қажет:


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




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

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

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


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




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




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


Ескерту: Осы алгоритмде қолданылған Zp - р - жай саны модулі бойынша алынған қалындылар өрісі(ақырлы). Zp* - оның циклдік мультипликативті тобы болып табылады. Бұл түсініктермен Е. Р. Байсаловтың «Криптографияның математикалық негіздері» атты кітабынан тереңірек таныса аласыздар. Сонымен қатар Алгебраның басқа да кітаптардан қарауға болады.
Ескерту: Жоғарыдағы келтірілген алгоритмде, алдымен q жай санын таңдап, оны қолданып - q: (p-1) орындалатындай p жай санын құрастырғанымыз ыңғайлы. Бұл әдіс DSS – те ресми түрде ұсынылған.

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


Енді осы Миллер – Рабин алгоритміне тоқтала кетейік.

Миллер – Рабин алгоритмі
Бұл алгоритмді келтірмес бұрын, оған «көмекші» бір алгоритмді келтіре кетейік:

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


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 – ның қандай мәндер қабылдайтынын көрелік. болсын. Онда dmod n бойынша келесі мәндерді қабылдайды:

(*)

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

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

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


MILLER-RABIN (n, 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. Қол қою процедурасы.

(а) k, 0 < k < q кездейсоқ құпия санын таңдаймыз;

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

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

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

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


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

(а) Хабар берушінің ашық кілтін (p,q,,y) аламыз;

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

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

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

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

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


Ескерту: Мұндағы h(m) – қайсыбір хэш функция (h:{0,1}*Zp), немесе белгілі SHA-1(Secure Hash Algorithm). Нақты осы жұмыста бұл функциялардың керегі жоқ, сондықтан бұларға тоқталмай – ақ қоямыз. Керек болған жағдайда - A. Menezes, P.van Oorschot, S. Vanstone “Handbook of Applied Cryptography”, CRC press, 1996 кітабының 9 – бөлімінен, 348 – беттен толық мәліметтер табасыз.

Ескертулер


  1. (параметрлердің ұсынылатын өлшемдері). Кілт құрау алгоритміндегі q параметрінің өлшемі (FIPS 186 – ға сәйкес) 160 bit болуы , ал p мәні 64, 512 және 1024 bit өлшемді болуы ұсынылады. FIPS 186 1024 биттен үлкен жай сандармен жұмыс істемейді.

  2. (сәтсіздік ықтималдығы). Қойылған қолды тексеру процедурасында мәнін есептеуді қажет етеді. Ал s = 1 жағдайда s-1 табылмайды! Бұндай жағдайды болдырмау үшін, қол қоюшы s  0 екенін тексеріп отыруы керек. Бірақ егер s - Zq ден алынған кездейсоқ сан болса, s = 0 болу ықтималдығы шамамен (1/2) 160 тең. Сонымен қатар, қол қоюшы r  0 екенін де қадағалап отыруы тиіс.


Қосымша - DSA – ға кілт құрау алгоритмінің бағдарламалық түрде іске асырылуы

program prime;

{$N+,G+}

uses crt;

label 1;

var

i,q,p,r,g,a:integer;

alf,y:longint;

ispr:boolean;
function mulmod(x,y,m:integer):integer; assembler;

asm

mov ax,x

mul y

div m

mov ax,dx

end;
function powmod(x,a,m:integer):integer;

var

r:integer;

begin

r:=1;

while a>0 do

begin

if odd(a) then r:=mulmod(r,x,m);

a:=a shr 1;

x:=mulmod(x,x,m);

end;

powmod:=r;

end;
function isprime(p:integer):boolean;

var q,i,a:integer;

const rounds=50;

begin

if odd(p) then

begin

isprime:=true;

q:=p-1;

while not odd(q) do q:=q shr 1;

for i:=1 to rounds do

begin

a:=Random(p-2)+2;

if powmod(a,p-1,p)<>1 then

begin

isprime:=false;

break;

end;

a:=powmod(a,q,p);

if a<>1 then

begin

while (a<>1) and (a<>p-1) do a:=mulmod(a,a,p);

if a=1 then

begin

isprime:=false;

break;

end;

end;

end;

end else isprime:=(p=2);

end;
begin

Randomize;

1: clrscr;

{1} ispr:=false;

while(ispr<>true) do

begin

q:=random(32767);

q:=q+2;

ispr:=isprime(q);

end;

{2} ispr:=false;i:=0;

while(ispr<>true) do

begin

i:=i+1;

if(i>32767) then goto 1;

r:=random(90);

r:=r+9;

p:=q*r+1;

ispr:=isprime(p);

end;

{3} alf:=1; i:=0;

while(alf<2) do

begin

i:=i+1;

g:=random(p-3);

g:=g+2;

alf:=1;

for i:=1 to r do alf:=alf*g;

alf:= alf mod p;

if(i>32767) then goto 1

end;

{4} a:=random(q-1);

a:=a+1;

{5} y:=1;

for i:=1 to a do y:=y*alf;

y:=y mod p;

if(y<1) then goto 1;

{6} writeln('Public key is (',p,', ',q,', ',alf,', ',y,')');

writeln('Private key is ',a);

repeat

write('');

until KeyPressed;

end.


Қорытынды
Бұл курстық жұмыста, мен алдыма қойылған негізгі мақсатты, яғни – барлық шарттарды қанағаттандыратын, кілт құрау алгоритмінің жұмыс істейтін моделін жасап шығаруды орындадым деп ойлаймын. Негізгі кездескен қиындық - өте үлкен сандармен жұмыс істеу, сонымен қатар қағазда берілген алгоритмді компьютерлік бағдарламаға өткізуде көптеген ауыртпалықтар кездесті (нақтырақ айтсақ – Миллер – Рабин тестін жасау).

Қолданылған әдебиеттер тізімі


  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;


Достарыңызбен бөлісу:




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет