前言

        先来看数字签名（Digital Signature）的Wikipedia定义

A digital signature is a mathematical scheme for demonstrating the authenticity of digital messages or documents. A valid digital signature gives a recipient reason to believe that the message was created by a known sender (authentication), that the sender cannot deny having sent the message (non-repudiation), and that the message was not altered in transit (integrity).

        数字签名方案有如下3个意义：

① 验证消息来源，使得消息接收方（receiver）相信消息的确来自消息发送方（sender）；

② 不可否认性，即若签名σ 是消息m 的一个有效签名，而σ 只有receiver 能够产生，那么receiver 无法否认m 就是来自它；

③ 消息完整性，数字签名方案可以用来保证消息m 没有被篡改过（由于公钥密码算法比较耗时，且可签名的消息空间M有特殊限制，通常是先对document 计算消息验证码，然后对消息验证码签名）。

 

DSA签名方案

        DSA签名方案，Digital Signature Algorithm，先来看Wikipedia对它的介绍

The Digital Signature Algorithm (DSA) is a Federal Information Processing Standard for digital signatures. It was proposed by the National Institute of Standards and Technology (NIST) in August 1991 for use in their Digital Signature Standard (DSS) and adopted as FIPS 186 in 1993. DSA is a variant of the ElGamal Signature Scheme.

        DSA是ElGamal签名方案的变种，被美国NIST作为DSS(DigitalSignature Standard)。其安全性依赖于离散对数难题的，这里不作扩展，仅从应用入手，有兴趣可以自学Jonathan Katz, Yehuda Lindell 编著的现代密码学一书。

        DSA方案∏ = (KeyGen, Sign, Vrfy) ，私钥sk = x，公钥pk = (param, y)，其中param = (p, q, g)，y = g^x mod p. 其中，

Sign算法如下：

Vrfy算法如下：

        容易验证DSA签名方案的正确性：即只要σ = (r, s) 是m 的一个有效签名，则v = r.

        DSA数字签名方案安全性基于离散对数难题，这里不作安全性证明（利用规约）。我们从应用入手，分析DSA方案的弱点，以引起注意：DSA方案Sign算法参数的选取需要重点考虑。

        （1）若k 值选取过小，敌手A 可以通过穷举轻易找到k，注意，k 若找到了，r 和s 已知（作为签名σ 发送出去），Hash函数H 又是公开的算法，那么可以轻易计算得到x（考虑s 的计算等式），即私钥sk.

                                                                      x = (sk - H(m)) / r

这是非常致命的。

        （2）若敌手A 监听到2 次使用相同k 值的签名（通过判断r 1 = r 2），我们有

        回到第（1）个问题。

        所以k 值的随机选取算法我们不要自己实现，其值必须足够大且一定要保证足够的随机性（即保证上述问题（2）出现的概率为可忽略）。下面给出Python代码（PryCrypto 官网的Demo）

#!/usr/bin/python#coding=utf-8from Crypto.Random import randomfrom Crypto.PublicKey import DSAfrom Crypto.Hash import SHAmessage = "Hello"key = DSA.generate(1024)h = SHA.new(message).digest()k = random.StrongRandom().randint(1, key.q-1)# print ksig = key.sign(h, k)# print sigif key.verify(h, sig):    print "OK"else:    print "Invalid Signature"

 

RSA签名方案

        RSA签名方案很著名，业界多采用RSA签名方案，这里不作详细介绍，直接上代码

#!/usr/bin/python#coding=utf-8from Crypto.PublicKey import RSAfrom Crypto.Signature import PKCS1_v1_5from Crypto.Hash import MD5from Crypto import Random# 伪随机数生成器random_generator = Random.new().read# 生成2048比特秘钥对(pk, sk)rsa = RSA.generate(2048, random_generator)private_pem = rsa.exportKey()with open('master-privatekey.pem', 'w') as f:    f.write(private_pem)public_pem = rsa.publickey().exportKey()with open('master-publickey.pem', 'w') as f:    f.write(public_pem)message = 'To be signed'# 对消息进行签名h = MD5.new(message)private_key = RSA.importKey(open('master-privatekey.pem').read())signer = PKCS1_v1_5.new(private_key)signature = signer.sign(h)# 对消息进行签名验证h = MD5.new(message)public_key = RSA.importKey(open('master-publickey.pem', 'r').read())verifier = PKCS1_v1_5.new(public_key)if verifier.verify(h, signature):    print "OK"else:    print "Invalid Signature"

 

ECC签名方案

        RSA 与 DSA 各有优缺点，那有没一个更好的选择呢？答案是肯定的，那就是ECC（Elliptic Curves Cryptography），即椭圆曲线算法，有兴趣可以自己查阅其Wikipedia词条或相关文献。这里仅从应用方面入手，简单介绍它取代RSA的可能性，及其Python示例。

        ECC有如下优点：

（1）相同密钥长度下，安全性能更高，如160位ECC已经与1024位RSA、DSA有相同的安全强度。

（2）计算量小，处理速度快，在私钥的处理速度上（解密和签名），ECC远 比RSA、DSA快得多。 （3）存储空间占用小 ECC的密钥尺寸和系统参数与RSA、DSA相比要小得多， 所以占用的存储空间小得多。 （4）带宽要求低使得ECC具有广泛得应用前景。

        Python调用ECC算法需要用到PyEcc模块：

PyECC is a simple Python module for performing Elliptical Curve Cryptography.

        PyEcc安装步骤如下：

git clone https://github.com/rtyler/PyECC.gitcd PyECCsudo python setup.py install

        安装过程中可能出现错误：

编译gcrypt.h：没有那个文件或目录

        需要我们先安装libgcrypt-dev

sudo apt-get install libgcrypt-dev

        再次安装时可能出现错误：

cc1plus: warnings being treated as errors

        原因是 Makefile 里面 gcc 的参数多了一个"-Werror"，即把警告也当成错误来处理，我们修改setup.py文件，找到-Werror把它删除掉，再次安装PyECC就可以了。我们可以在tests.py文件中找到PyECC的用法，这里给出一个ECC签名示例：

#!/usr/bin/python#coding=utf-8import pyeccDEFAULT_DATA = 'This message will be signed\n'DEFAULT_PUBKEY = '#&M=6cSQ}m6C(hUz-7j@E=>oS#TL3F[F[a[q9S;RhMh+F#gP|Q6R}lhT_e7b'DEFAULT_PRIVKEY = '!!![t{l5N^uZd=Bg(P#N|PH#IN8I0,Jq/PvdVNi^PxR,(5~p-o[^hPE#40.<|'ecc = pyecc.ECC(public=DEFAULT_PUBKEY, private=DEFAULT_PRIVKEY)signature = ecc.sign(DEFAULT_DATA)print signatureecc = pyecc.ECC(public=DEFAULT_PUBKEY)print ecc.verify(DEFAULT_DATA, signature)

        关于公钥pk、私钥sk的生成，可以用pyecc.ECC.generate()（详见tests.py，60x8 bits），也可以用，需要安装seccure。

sudo apt-get install seccure

        用法如下：

% seccure-keyAssuming curve p160.Enter private key: my private keyThe public key is: 8W;>i^H0qi|J&$coR5MFpR*Vn

        具体见。

 

Reference