首页 > 代码库 > 密码学之《数字签名》
密码学之《数字签名》
周六要考密码学了，恰逢身体不舒服，没心情看数字什么的，来整理整理数字签名的一点儿知识点~简简单单的几行文字，看官笑看即可~
什么是数字签名？有毛用？
数字签名主要用于对数字消息进行签名，以防消息的冒名伪造或篡改，也可以用作通信双方的身份鉴别。
为什么数字签名有这样那样的作用？
数字签名有这样几个特性：
1. 可信。任何人都可以验证签名的有效性
2. 不可伪造。除了合法的签名者，任何其他人伪造签名是困难的。
3. 不可复制。对一个消息的签名不能通过复制变成另一个消息的签名，若是复制得到，任何人都能检测出来，从而拒绝签名信息。
4. 不可篡改。一旦签名消息被篡改，任何人都可以发现消息与签名之间的不一致性。
5. 不可抵赖。签名者不能否认自己的签名。
既然数字签名这么刁扎天，那具体怎么实现呢？
数字签名的基础是公钥密码。至于公钥密码，之后再做整理。
这里介绍三种数字签名，RSA签名方案，EIGamal签名方案，DSA签名方案。
RSA签名方案过程：
1. A用保密密钥对消息m加密，密文s就是A对消息的签名
2. A将签名的消息（m,s）发给B
3. B用A的公开密钥对s进行解密，得到m‘。如果m‘=m，则为有效签名。
加密和解密的过程以及密钥的生成的过程都和RSA算法一致（细节见：http://www.cnblogs.com/kuoaidebb/p/4111865.html）
这样的签名方案有几个缺点。首先，对任意y，任何人都可以计算x=y^e mod n，任何人都可以伪造对随机消息x的签名y。其实，如果消息x1和x2的签名分别为y1,y2，任何知道x1,y1,x2,y2的人都可以伪造对消息x1x2的签名y1y2。这是因为在RSA中，Sig(x1,x2)=Sig(x1)Sig(x2).最后，是如果要加密的消息比较长，需要先对消息进行分组，然后对每组消息进行签名。这样做的后果是签名变长，签名速度变慢。解决上述问题的方法之一，是对消息进行签名之间做Hash变换，再对变换后的消息进行签名。
EIGamal签名方案过程：
1. 选取大素数p,g.p,g公开
2. 随机选取整数x作为保密密钥，1<=x<=p-2，计算公开密钥y=g^x mod p
3. 签名：秘密选取整数k（1<=k<=p-2）,对消息m的签名如下：
r=g^k mod p
Sig(m)=(r, (m-xr)*k^-1 mod (p-1))
4. 签名验证：对得到的签名（r,o）,如果满足如下条件，则为有效签名。
y^r * r^o = g^m mod p
DSA签名过程：
细节比较繁琐，就不仔细列举了，原理跟上面的两种差不多，唯一特殊的一点是在加密之前对明文做了hash处理。
附上python版的实现，其中hash加密用了sha-1，从git上下载了一下稍微改了一下：
dsa.py#coding:utf-8from random import randintimport mathfrom sys import exitfrom sha1 import sha1# n^-1 mod udef ExtendedEuclid(n,u): x1=y2=1 x2=y1=0 if n>u: x3,y3=[n,u] else: x3,y3=[u,n] while 1: if y3==0: return x3+u elif y3==1: return y2+u q=x3/y3 t1,t2,t3=[x1-q*y1,x2-q*y2,x3-q*y3] x1,x2,x3=[y1,y2,y3] y1,y2,y3=[t1,t2,t3]def cal_g(p,q): h=randint(1,p-1) temp=h ** ((p-1)/q) % p if temp > 1: return temp; else: cal_g(p,q)if __name__==‘__main__‘: p=839 q=419 g=cal_g(p,q) message=raw_input(‘请输入要加密的消息内容： ‘) x = int(raw_input(‘请选择密钥，0~%d之间任意整数: ‘ %(q))) y = g ** x % p print "公开参数如下：p：%d,q：%d,g：%d,y(公钥)：%d" %(p,q,g,y) print "当前的私钥为：x：%d" %(x) k = randint(0,q) r = g ** k %p % q; s = ( ExtendedEuclid(k,q) * ( (long(sha1(message),16)+x*r)%q ) )%q; print("签名结果为：(r,s):(%d,%d)" %(r,s)) w = ExtendedEuclid(s,q); u1 = long(sha1(message),16)*w % q u2 = r*w % q if (g**u1 * y**u2 %p)%q == r: print "签名可用" else: print "签名不可用"sha1.py#coding:utf-8import structdef _left_rotate(n, b): return ((n << b) | (n >> (32 - b))) & 0xffffffff def sha1(message): h0 = 0x67452301 h1 = 0xEFCDAB89 h2 = 0x98BADCFE h3 = 0x10325476 h4 = 0xC3D2E1F0 original_byte_len = len(message) original_bit_len = original_byte_len * 8 message += b‘\x80‘ #填充一位1 message += b‘\x00‘ * ((56 - (original_byte_len + 1) % 64) % 64) # 填充0到第448位 message += struct.pack(b‘>Q‘, original_bit_len) #最后64位填充前消息长度的前64位 for i in range(0, len(message), 64): # every range for 512 byte w = [0] * 80 for j in range(16): w[j] = struct.unpack(b‘>I‘, message[i + j*4:i + j*4 + 4])[0] for j in range(16, 80): w[j] = _left_rotate(w[j-3] ^ w[j-8] ^ w[j-14] ^ w[j-16], 1) a = h0 b = h1 c = h2 d = h3 e = h4 for i in range(80): if 0 <= i <= 19: f = d ^ (b & (c ^ d)) k = 0x5A827999 elif 20 <= i <= 39: f = b ^ c ^ d k = 0x6ED9EBA1 elif 40 <= i <= 59: f = (b & c) | (b & d) | (c & d) k = 0x8F1BBCDC elif 60 <= i <= 79: f = b ^ c ^ d k = 0xCA62C1D6 a, b, c, d, e = ((_left_rotate(a, 5) + f + e + k + w[i]) & 0xffffffff, a, _left_rotate(b, 30), c, d) h0 = (h0 + a) & 0xffffffff h1 = (h1 + b) & 0xffffffff h2 = (h2 + c) & 0xffffffff h3 = (h3 + d) & 0xffffffff h4 = (h4 + e) & 0xffffffff return ‘%08x%08x%08x%08x%08x‘ % (h0, h1, h2, h3, h4)
参考资料：
《现代密码学》第二版 陈鲁生等著
密码学之《数字签名》