DSA数字签名原理及python实现
python的加密算法一般在PyCrypto库中,这个库包含了常见的对称加密算法(DES、AES、IDEA、等)、公钥加密算法(RSA、DSA、等)、散列算法(MD5、SHA1、RIPEMD、等)。
DSA数字签名原理
1991年8月美国国家标准局(NIST)公布了数字签名标准(Digital Signature Standard, DSS)。
此标准采用的算法称为数字签名算法(Digital Signature Algorithm, DSA),它作为ElGamal和Schnorr签名算法的变种,其安全性基于离散对数难题;并且采用了Schnorr系统中,g为非本原元的做法,以降低其签名文件的长度。
方案包括初始过程、签名过程和验证过程。
1. 初始过程
(1) 系统参数:全局公钥KUG:p,q,g。p,q,g 作为系统参数,供所有用户使用,在系统内公开。
q: 选择素数q,位长为160,即
p: 随机生成L位的素数
g: 随机选择整数h,计算
(2) 用户私钥:用户选取一个私钥x,x 随机或伪随机整数, 其中
(3) 用户公钥:用户的公钥y,
与用户每条消息相关的秘密值k
k: 随机或伪随机整数, 其中0
2. 签名过程
对待签消息M
输入:((g,p,q,x),M) , M为要签名的消息
(1) 生成一随机整数 k,
(2) 计算
(3) 计算
则输出
注:
H(M)使用SHA-1生成的M的散列码
r不依赖消息,是k和全局公钥的函数。故对一个消息存在许多签名
离散对数的困难:从r恢复k是很困难的,从s恢复x是不可行的
3. 验证过程
(1) 输入:((g,p,q,y),M,(r ′,s ′ ))
(2)计算
(3) 计算
(4)计算
正确性证明:
验证:如 v=r ′则签名有效
其中M ′,r ′,s ′ 为接收端得到的M,r,s版本
DSA签名特点
- DSS的签名比验证快得多
- DSS不能用于加密或者**分配
-
s−1mod q 要存在s ≠ 0 mod q,如果发生,接收者可拒绝该签名. 要求重新构造该签名,实际上, s ≡ 0 mod q的概率非常小 - 签名产生的计算任务有:
1)计算gkmod p 求r
2)确定逆元k−1 求s
DSA签名实例
python实现DSA签名
下面是一个DSA加密的实例:
#encoding utf-8
from Crypto.Random import random
from Crypto.PublicKey import DSA
from Crypto.Hash import SHA
message = "Hello World"
key = DSA.generate(1024)
h = SHA.new(message).digest()
k = random.StrongRandom().randint(1,key.q-1)
sig = key.sign(h,k)
print "Message is ",message
print "signature is ",sig
#签名的验证
if key.verify(h,sig):
print "Signature verification is true"
else:
print "Sorry,signature verification is false"
手动DSA签名
密匙生成:
p=67=6×11+1,q=11 g=3p−1/11mod p=36mod 67=59 x=5,y=gx mod p=62 KU=(59,67,11,62) KR=(59,67,11,5) 签名:
令H(M)=4,k=3 R=(gkmod p)mod q=(593mod67)mod11=2 S=k−1(H(M)+rx)mod q=3−1(4+2×5)mod11=1 (r,s)=(2,1) 验证
验证(r´,s´)=(2,1) w=s´−1mod q=1−1mod 11=1 U1=H(M)×wmodq=4×1mod 11=4 U2=r´×wmod q=2×1mod 11=2 V=gu1×yu2mod p mod q=594×622mod67mod11=2
因为v=r´,(2,1) 是H(M) 的签名
上一篇: 如何解决PHP定时发送服务的问题