[算法][安全技术]数字签名算法(DSA)

soloforce

[color="Red"]06-9-25 更新，使描述更加严格准确，并增添了注解

      信息交流中，接收方希望收到的信息未被窜改(信息完整性)，还希望接收到的信息确由自己认定的发送方所发(信息来源有效性)，那么接收方和发送方就可以约定，共同使用DSA（Digital Signature Algorithm）来实现。 本文仅仅阐述DSA的内部算法机制，不涉及实际应用。

一、算法中应用了下述参数：

2. p：一个素模数，其值满足: 2^(L-1) < p < 2^L，其中L是64的倍数，且满足 512 ≤ L ≤ 1024 。
3. q：(p-1) 的素因子，其值满足 2^159 < q < 2^160 。
4. g：g = powm(h, (p-1)/q, p) 。h为满足1< h < p - 1 的任意整数，从而有 powm(h, (p-1)/q, p) > 1 。
5. x：私钥。 x为一个随机或伪随机生成的整数，其值满足 0 < x < q 。
6. y：公钥。 y = powm(g, x, p)  。

复制代码

注：
1、整数 p, q, g 可以公开，也可仅由一组特定用户共享。
2、私钥 x 和 公钥 y 称为一个密钥对 (x,y) ， 私钥只能由签名者本人独自持有，公钥则可以公开发布。密钥对可以在一段时间内持续使用。
3、符号约定： powm(x,y,z)表示 (x^y) mod z, 即 (x的y次方) 模 z 。"mod"为求模运算符;  "^" 为幂运算符; 下文的"*"为乘法运算符。


二、签名产生过程如下：

2. 1、产生一个随机数k，其值满足0< k < q 。
3. 2、计算 r := powm(g, k, p) mod q ，其值满足 r >0 。
4. 3、计算 s := ( k^(-1) ( SHA(M) + x*r) ) mod q  ，其值满足 s >0 。

复制代码

注：
1、k^(-1) 表示整数k关于某个模数的逆元，并非指 k 的倒数。k在每次签名时都要重新生成。逆元：满足 (a*b) mod m =1 的a和b互为关于模数 m 的逆元，表示为 a=b^(-1) 或 b=a^(-1) , 如 (2*5) mod 3 = 1 ， 则 2 和 5 互为 模数3 的逆元。
2、SHA(M )：M的Hash值，M为待签署的明文或明文的Hash值。SHA是Oneway-Hash函数，DSS中选用SHA1( FIPS180: Secure Hash Algorithm )，此时SHA(M) 为160bits长的数字串（16进制），可以参与数学计算（事实上SHA1函数生成的是字符串，因此必须把它转化为数字串）。
3、最终的签名就是整数对( r , s )， 它们和 M 一起发送到验证方。
4、尽管 r 和 s 为 0 的概率相当小，但只要有任何一个为0, 必须重新生成 k ，并重新计算 r 和 s 。

三、验证签名过程

我们用 ( r', s', M' ) 来表示验证方通过某种途径获得的签名结果，之所以这样表示是因为你不能保证你这个签名结果一定是发送方生成的真签名，相反有可能被人窜改过，甚至掉了包。 为了描述简便，下面仍用 (r ,s ,M) 代替 (r', s', M') 。

为了验证( r, s, M )的签名是否确由发送方所签，验证方需要有 (g, p, q, y) ，验证过程如下：

2. 1、计算 w := s^(-1) mod q
3. 2、计算 u1 := ( SHA( M ) * w ) mod q
4. 3、计算 u2 := ( r * w ) mod q
5. 4、计算 v := (( (g^u1) * (y^u2) ) mod p ) mod q
6.               =( (g^u1 mod p)*(y^u2 mod p)  mod p ) mod q
7.               =( powm(g, u1, p) * powm(y, u2, p) mod p ) mod q
8. 5、若 v 等于 r，则通过验证，否则验证失败。

复制代码

注：
1、验证通过说明： 签名( r, s )有效，即(r , s , M )确为发送方的真实签名结果，真实性可以高度信任， M 未被窜改，为有效信息。  
2、验证失败说明：签名( r , s )无效，即(r, s , M) 不可靠，或者M被窜改过，或者签名是伪造的，或者M的签名有误，M 为无效信息。



一个合法签名(v=r)的示例：

2. TYPE        VARIABLE        VALUE
3. --------------------------------------------------
4. INT        p                6233588875466341566113630330275552873486878881674315000002391717203321165179184214016765668971399206470119049322960064240805978144781601456277748229517456259470647256047322405573206363800989129316236832607243718624184346100338941861715113988130251202574293338708575332978108008918240726077115306442121
5. INT        q                903569344808636464092554330241160515973915296479
6. INT        h                5617340149999429357173922259444725005473756431426262623250212661845560951746034436629637139204723993805223352831791160578553487063641461476347311756161374931104306998638124995644999453677069074074881907291444693514751014063404215893401993467690259368337679102595598904604195740119948843816009803062508
7. INT        g                1790280416633283691024656667553831515509379601966536379609622193784265347750992685294786283074032431990483382660794741449452697905240380032247426972245376314961319619940551686559535555710850888797350763947257978363297675331290475120987389290807548518382474677239002809417088237196403049028357341663344
8. INT        x                782159191612971075573697422869323625442262251798
9. INT        y                428662872613907949904392807134053168832414726802217938446245276305001200081744237890469501753334989755048852344631371576877868294217441080715251214169309375504847087351208653750897014193771018725958242609964883327073175436981360290377344334846799556150281115624613815338348282996480828438366398894855
10. INT        k                613972186927431426477068128739378962039704133097
11. INT        r                620017649822009426489171972454697774699511948653
12. INT        M                903569344808636464092554330241160515973915295245
13. INT        s                467455930475117112435374629373787232532646390225
14. INT        u1                126857088795884412567619382641907325870411225466
15. INT        u2                174543778192883631168060332820251594858530028956
16. INT        v                620017649822009426489171972454697774699511948653
17. INT        w                874177423511115116461865681462969002226081404190

复制代码

注：上述数值由GNU MP高精度数学库计算生成。h，k，M随机取得。

soloforce

这两天搞GnuPG，重刷了一下这篇文章

感兴趣的朋友可以参考 http://www.itl.nist.gov/fipspubs/fip186.htm ，我就是根据这个来描述的。

Iambitious

赞，不愧为伟大的版主。

soloforce

不敢当，我只是翻译了一下，再稍作注释而已。大家可以多谈谈自己的想法和思路或者实现方式。

fanisky

在实现此算法中，我卡在了 模数的逆元这里，也就是

3、计算 s := ( k^(-1) ( SHA(M) + x*r) ) mod q  ，其值满足 s >0 。

这里s的计算，k^(-1) ( SHA(M) + x*r) 这个的值，始终找不到合适的算法，高手能否给个演算？或者给个实现的函数？

因为k是随机数，不是素数，网上一些互素的算法都用不上。郁闷呢。

soloforce

求k的模数逆元可以用GNU MP的mpz_invert函数

fanisky

大数很麻烦

还要请教下q和p的生成。。。。

首先是判定素数。。。麻烦死

另外一个问题是，从http://www.itl.nist.gov/fipspubs/fip186.htm 这里看，先生成q，再生成p，用q生成p的算法，也挺麻烦的，我有点看不懂，版主能就给稍微讲解一下阿。

soloforce

兄弟还是看看GNU MP的用户手册吧
关于大整数次方模运算、求素数等等，都可以在mpz_xxx系列函数中找到。手册可以去官方网站下载: http://gmplib.org/gmp-man-4.2.2.pdf