x - íåêîòîðîå ÷èñëî, ìåíüøåå q; y = ax mod p .
Çàòåì îòïðàâèòåëü âû÷èñëÿåò çíà÷åíèå Y = GX mod P. ×èñëî Y ÿâëÿåòñÿ îòêðûòûì êëþ÷îì äëÿ ïðîâåðêè ïîäïèñè îòïðàâèòåëÿ. ×èñëî Y ïåðåäàåòñÿ âñåì ïîëó÷àòåëÿì äîêóìåíòîâ.
Ýòîò àëãîðèòì ïðåäóñìàòðèâàåò òàêæå èñïîëüçîâàíèå îäíîñòîðîííåé ôóíêöèè õýøèðîâàíèÿ h( . )ñîãëàñíî àëãîðèòìó áåçîïàñíîãî õýøèðîâàíèÿ SHA( Secure Hash Algorithm).
Äëÿ òîãî, ÷òîáû ïîäïèñàòü äîêóìåíò Ì, îòïðàâèòåëü õýøèðóåò åãî â öåëîå õýø-çíà÷åíèå m = h(M), 1< m < q; çàòåì ãåíåðèðóåò ñëó÷àéíîå öåëîå ÷èñëî K, 1< K < q, è âû÷èñëÿåò ÷èñëî r :
r = (G K mod P) mod q.
Çàòåì îòïðàâèòåëü âû÷èñëÿåò ñ ïîìîùüþ ñåêðåòíîãî êëþ÷à X öåëîå ÷èñëî s :
m + rX
S = ------------- mod q .
K
Ïàðà ÷èñåë r è s îáðàçóþò öèôðîâóþ ïîäïèñü S = (r, s) ïîä äîêóìåíòîì M è ïîäïèñàííîå ñîîáùåíèå ïðåäñòàâëÿåò ñîáîé òðîéêó ÷èñåë [M, r, s].
Ïîëó÷àòåëü ïîäïèñàííîãî ñîîáùåíèÿ [M, r, s] ïðîâåðÿåò âûïîëíåíèå óñëîâèé
1< r < q , 1< s < q è îòâåðãàåò ïîäïèñü, åñëè õîòÿ áû îäíî èç ýòèõ óñëîâèé íå âûïîëíåíî.
Çàòåì ïîëó÷àòåëü âû÷èñëÿåò çíà÷åíèå w = 1/s mod q, õýø-çíà÷åíèå m = h(M)
è ÷èñëà u1 = (mw) mod q, u2 = (rw) mod q. Äàëåå ïîëó÷àòåëü ñ ïîìîùüþ îòêðûòîãî êëþ÷à Y âû÷èñëÿåò çíà÷åíèå u1 u2
v = (( G Y ) mod P ) mod q
è ïðîâåðÿåò âûïîëíåíèå óñëîâèÿ v = r . Åñëè óñëîâèå v = r âûïîëíÿåòñÿ, òî ïîäïèñü
S = (r, s) ïîä äîêóìåíòîì M ïðèçíàåòñÿ ïîëó÷àòåëåì ïîäëèííîé.
Ìîæíî äîêàçàòü, ÷òî ðàâåíñòâî v = r âûïîëíÿåòñÿ òîãäà è òîëüêî òîãäà, êîãäà ïîäïèñü S = (r, s) ïîä äîêóìåíòîì M ïîëó÷åíà ñ ïîìîùüþ èìåííî òîãî ñåêðåòíîãî êëþ÷à X, èç êîòîðîãî áûë ïîëó÷åí îòêðûòûé êëþ÷ Y, òî åñòü àëãîðèòì ïîçâîëÿåò
íàäåæíî óäîñòîâåðèòüñÿ, ÷òî îòïðàâèòåëü ñîîáùåíèÿ âëàäååò èìåííî äàííûì ñåêðåòíûì êëþ÷îì X(íå ðàñêðûâàÿ ïðè ýòîì çíà÷åíèÿ êëþ÷à Õ) è ÷òî îòïðàâèòåëü ïîäïèñàë èìåííî äàííûé äîêóìåíò Ì.
Ðîññèéñêèé ñòàíäàðò öèôðîâîé ïîäïèñè ââåäåí â äåéñòâèå ñ 1995 ãîäà è îáîçíà÷àåòñÿ êàê ÃÎÑÒ Ð 34.10-94 , à îïðåäåëÿåìûé èì àëãîðèòì öèôðîâîé ïîäïèñè êîíöåïòóàëüíî áëèçîê ê àëãîðèòìó DSA.  ýòîì àëãîðèòìå èñïîëüçóþòñÿ ñëåäóþùèå ïàðàìåòðû:
p - áîëüøîå ïðîñòîå ÷èñëî äëèíîé îò 509 äî 512 áèò èëè îò 1020 äî 1024 áèò;
q - ïðîñòîé äåëèòåëü (p -1) äëèíîé îò 254 äî 256 áèò;
a - ëþáîå ÷èñëî, ìåíüøåå (p -1), ïðè÷åì èìååò ìåñòî aq = 1 mod p;
|