2.DSS,即DSA,当初的设计是用于数字签名而不用于密钥交换的算法,最初的设计是用来替换RSA的,是在ElGamal和Schorr数字签名方案的基础上设计的,这里不详细介绍这两个算法,有兴趣的同学可以自己去找找相关资料。与DH一样的密码数学基础,即素数域上中的模幂运算,最重要的区别构造p(大素数)时要使p-1可以被另一个称作q的素数除尽。与RSA不同的是,DSA签名结果是由两个值r和s(160位)组成。
算法原理:
1)参数介绍
p:L bits长的素数。L是64的倍数,范围是512到1024;
q:p - 1的160bits的素因子;
g:g = h^((p-1)/q) modp,h满足h < p - 1, h^((p-1)/q)mod p > 1;
x:x <q,x为私钥;
y:y = g^x mod p ,( p, q, g, y )为公钥;
以上参数中p, q, g以及y为公匙,x为私匙必须保密!任何第三方用户想要从Y解密成X 都必须解决整数有限域离散对数难题。
注:
a)、整数p, q,g 可以公开,也可仅由一组特定用户共享。
b)、私钥x 和 公钥 y 称为一个密钥对 (x,y) ,私钥只能由签名者本人独自持有,公钥则可以公开发布。密钥对可以在一段时间内持续使用。
2)签名过程
P产生随机数k,k < q;
P计算r = ( g^k mod p ) modq
s = ( k^(-1) (H(m) + xr)) modq
签名结果是( m, r, s)。
注:
a)、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 的逆元。BTW:有兴趣实现的童鞋,可以参照GNUMP, 求k的模数逆元可以用GNU MP的mpz_invert函数.
b)、SHA(M):M的Hash值,M为待签署的明文或明文的Hash值。SHA是Oneway-Hash函数,DSS中选用SHA1( FIPS180: Secure Hash Algorithm),此时SHA(M) 为160bits长的数字串(16进制),可以参与数学计算(事实上SHA1函数生成的是字符串,因此必须把它转化为数字串)。
c)、最终的签名就是整数对( r , s ),它们和 M一起发送到验证方。
d)、尽管r 和 s 为 0 的概率相当小,但只要有任何一个为0, 必须重新生成 k,并重新计算 r和 s 。
3)验证过程
w =s^(-1)mod q
u1 = (H( m ) * w ) mod q
u2 = (r * w ) mod q
v = ((g^u1 * y^u2 ) mod p ) mod q
若v = r,则认为签名有效。
注:
a)、验证通过说明:签名( r, s )有效,即(r , s , M )确为发送方的真实签名结果,真实性可以高度信任,M 未被窜改,为有效信息。
b)、验证失败说明:签名( r , s )无效,即(r, s , M) 不可靠,或者M被窜改过,或者签名是伪造的,或者M的签名有误,M 为无效信息。
举个简单的例子:
参数选取:
1)取p=23,q=11是(p-1)=22的素因子。(p-1)/q=2(这两个数基本上是符合条件的比较小数字了,如果q取的太小,后面很多地方取值就体现不出来了))
2)g =h^((p-1)/q) mod p。取h=12,g=12^2 mod 23 =6<>1,满足条件,生成Zp*中唯一的q阶循环了群。
3)选择x=8,满足1<8<q
4)计算y= g^x mod p=6^8 mod 23 = 1679616 mod 23 = 18
所以公钥p=23,q=11,g=6,y=18
签名过程:
1)选择随机数k=7, 满足k<q
2)计算 r = ( g^k mod p ) mod q = (6^7 mod 23) mod 11 = 3 mod 11 =3
3)计算k^(-1) mod q=8
4)为了方便计算,随便取h(m)=10
5)s=k^(-1)(h(m)+xr) mod q =8*(10+8*3) mod 11 = 8
所以消息m的签名值r=3,s=8
验证过程:
1)计算w = (s^-1) mod q = 7
2)计算 u1 = (h(m)*w) mod q = 10*7 mod 11 = 4
3)计算 u2 = ( r * w ) mod q = 3*7 mod 11 = 10
4)计算v = (( g^u1 * y^u2 ) mod p ) mod q = ((6^4*18^10) mod23)mod11=3 mod 11 = 3
最后判断v是否与r相等,以决定是否通过了验证
证明公式:
因为:r=(g^k mod p) mod q;
s=(h(m)+xr)k^(-1) mod q;
w=s^(-1) mod q
u1 =(h(m)*w) mod q
u2 = (r * w ) mod q
v = ((g^u1 * y^u2 ) mod p ) mod q
所以:v = (( g^u1 * y^u2 ) mod p ) mod q
= ((g^(h(m)*w) * y^(r*w) mod p ) mod q
= ((g^(h(m)*w) * g^(x*r*w) mod p ) mod q mod p ) mod q
= ((g^((h(m)+(x*r)*w) mod p ) mod q mod p ) mod q
= ((g^(s*k*w) mod p ) mod q mod p ) mod q
= ((g^k mod p ) mod q mod p ) mod q
= r
所以,最后验证的时候只要v=r的时候,即可认为通过验证,这个推理等式用到了费尔马定理:
安全性分析:
DSA只能与SHA-1一起使用,而RSA可以与任何摘要算法一起使用。DSA签名不包括摘要标识符,所以如果允许多种摘要算法就会使DSA遭受前面RSA里面介绍的那种替换攻击。DSA主要依赖于整数有限域离散对数难题。素数P 必须足够大,且p-1至少包含一个大素数因子以抵抗Pohlig &Hellman算法的攻击。M一般都应采用信息的HASH值(官方推荐为SHA算法)。DSA的安全性主要依赖于p和g,若选取不当则签名容易伪造,应保证g对于p-1的大素数因子不可约。DSA算法在破解时关键的参数就是X 根据 Y = G^X mod P 只要知道 P,G,Y,Q 且能分解出 X 就可以伪造R,S写出KeyGen了。个人观点DSA的安全性要次于ECC 与RSA不相上下。但是有一点,就是DSA算法的验证过程R,S 是以明文形式出现的,这点很容易被利用。
BTW:与RSA不同的是,RSA是对签名数据“解密”后再比对摘要值,而DSA中摘要值是需要参与计算的。