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) 系统参数：全局公钥KUG：p,q,g。p,q,g 作为系统参数，供所有用户使用，在系统内公开。
q: 选择素数q，位长为160，即 $2^{159}<q<2^{160}$
p: 随机生成L位的素数 $p=kq+1$ ，这里L在512到1024之间,且为64的倍数
g: 随机选择整数h，计算 $g=h^{(p-1)/q} mod\ p$ ,其中 $1<h<(p-1)$ ， $g>1$ , $g^q≡1(mod\ p)$

(2) 用户私钥：用户选取一个私钥x，x 随机或伪随机整数, 其中 $1≤x≤q-1$
(3) 用户公钥：用户的公钥y， $y= g^{x} mod( p)$ ，公开。
与用户每条消息相关的秘密值k
k: 随机或伪随机整数, 其中0

2. 签名过程

对待签消息M
输入：(（g,p,q,x),M) ， M为要签名的消息
(1) 生成一随机整数 k, $0<k<q$ ；
(2) 计算 $r=(g^k\ mod\ p)mod\ q$ ；
(3) 计算 $s=k^{-1}(H(m)+xr)mod\ q。$
则输出 $(r,s)$ 为签名人对M的签名。
注：
H(M)使用SHA-1生成的M的散列码
r不依赖消息，是k和全局公钥的函数。故对一个消息存在许多签名
离散对数的困难：从r恢复k是很困难的，从s恢复x是不可行的

这里写图片描述

3. 验证过程

(1) 输入：((g,p,q,y),M,(r ′,s ′ ))
(2)计算 $w=(s′)^{-1} mod\ q$
(3) 计算 $u_{1}=[H(M ′)w] mod\ q, u_{2}=( r ′) w mod\ q$
(4)计算 $v=[(g^{u1}y^{u2})mod\ p] mod\ q$
正确性证明：
验证：如 v=r ′则签名有效

其中M ′,r ′,s ′ 为接收端得到的M,r,s版本
这里写图片描述

DSA签名特点

DSS的签名比验证快得多
DSS不能用于加密或者密钥分配
$s^{-1} mod\ q$ 要存在s ≠ 0 mod q,如果发生,接收者可拒绝该签名. 要求重新构造该签名,实际上, s ≡ 0 mod q的概率非常小
签名产生的计算任务有：
1）计算 $g^kmod\ 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=3^{ p-1/11} mod\ p=3^6 mod\ 67=59$
$x=5 ， y=g^x \ mod\ p=62$
$KU=（59 ，67，11，62）$
$KR=（59，67，11，5）$
签名:
令 $H(M)=4,k=3$
$R=(g^k mod\ p) mod\ q=(59^3 mod 67) mod 11=2$
$S=k^{-1} (H(M)+rx) mod\ q=3^{-1}(4+2 ×5) mod 11=1$
$(r,s)=(2,1)$
验证
验证 $（ r´，s´）=（2，1）$
$w=s´^{ -1} mod \ q=1^{-1} mod\ 11=1$
$U_{1}=H（M）×w mod q=4 ×1 mod\ 11=4$
$U_{2}=r´ ×w mod\ q=2 ×1 mod\ 11 =2$
$V=g^{u1} ×y^{u2} mod\ p\ mod\ q =59^4 × 62^2 mod 67 mod 11 =2$
因为 $v= r´ ，（2，1）$ 是 $H（M）$ 的签名

更多精彩内容