钱吉成老婆周红:椭圆曲线数字签名算法（ECDSA）（

椭圆曲线数字签名算法（ECDSA）（一）

转载

椭圆曲线

数字签名

ecdsa

摘要
椭圆曲线数字签名算法（ECDSA）是使用椭圆曲线对数字签名算法（DSA）的模拟。
ECDSA于1999年成为ANSI标准，并于2000年成为IEEE和NIST标准。它在1998年既已为ISO所接受，并且包含它的其他一些标准亦在ISO的考虑之中。与普通的离散对数问题（discrete logarithm problem  DLP）和大数分解问题（integer factorization problem  IFP）不同，椭圆曲线离散对数问题（elliptic curve discrete logarithm problem  ECDLP）没有亚指数时间的解决方法。
因此椭圆曲线密码的单位比特强度要高于其他公钥体制。
本文将详细论述ANSIX9.62标准及其协议,安全，实现，互操作性方面的问题。

1、介绍
数字签名算法（DSA）在联邦信息处理标准FIPS中有详细论述，称为数字签名标准。它的安全性基于素域上的离散对数问题。椭圆曲线密码（ECC）由Neal Koblitz和Victor Miller于1985年发明。它可以看作是椭圆曲线对先前基于离散对数问题（DLP）的密码系统的模拟，只是群元素由素域中的元素数换为有限域上的椭圆曲线上的点。椭圆曲线密码体制的安全性基于椭圆曲线离散对数问题（ECDLP）的难解性。椭圆曲线离散对数问题远难于离散对数问题，椭圆曲线密码系统的单位比特强度要远高于传统的离散对数系统。因此在使用较短的密钥的情况下，ECC可以达到于DL系统相同的安全级别。这带来的好处就是计算参数更小，密钥更短，运算速度更快，签名也更加短小。因此椭圆曲线密码尤其适用于处理能力、存储空间、带宽及功耗受限的场合。

ECDSA是椭圆曲线对DSA的模拟。ECDSA首先由Scott和Vanstone在1992年为了响应NIST对数字签名标准（DSS）的要求而提出。ECDSA于1998年作为ISO标准被采纳，在1999年作为ANSI标准被采纳，并于2000年成为IEEE和FIPS标准。包含它的其他一些标准亦在ISO的考虑之中。本文中我们将介绍ANSI X9.62标准。也将介绍一些签名的基础知识以及协议、安全性、实现、互操作性方面的问题。

本文其他部分的安排如下：

第二节中我们将回顾数字签名方案和DSA，
第三节和第四节将分别介绍有限域和椭圆曲线，
第五节将讲述域参数的产生和参数有效性的验证，
第六节将讲述密钥对的产生和公钥有效性的验证，
第七节的内容是ECDSA的签名和验证过程。第八章论证ECDSA的安全性，
第九节和第十节讲述的是ECDSA协议和实现方面的问题。

2、数字签名方案

2.1背景知识
数字签名的目的是提供一个手写签名的数字化副本。签名是一个依赖于签名者私钥和被签名一段消息的比特串。签名必须是可验证的，即如果对签名的真实性存在疑问，必须由一个中立的第三方作出公正的裁决，并且无需知道签名者的私钥。对签名的抵赖以及伪造签名应该能被发现。

本文论述的是非对称摘要数字签名。“非对称”即用户的密钥对各不相同。用户的私钥用于签名，其他用户用他的公钥来检验签名的真实性。摘要是指对一段消息先用哈希函数进行摘要计算，尔后再对消息摘要进行签名，而不是消息。

安全性：
从理论上讲，在选择消息攻击下，数字签名应该是不可伪造的。这一概念由Goldwasser，Micali和Rivest提出。更一般的讲就是攻击者获得用户A的摘要和签名，但他无法用其他的摘要来伪造这样一个签名。

应用：
数字签名方案用于以下一些用途：数据完整性（确保数据没有被未知或未授权的中间人改变），数据源认证（确保数据的来源是可信的），不可否认性（确保用户不能对自己的行为进行抵赖）。数字签名是密码学协议的基本组成部分，并且可以提供其他一些服务如：身份认证（FIPS 196，ISO/IEC 9798-3），密钥传递前的认证（ANSI X9.63，ISO/IEC 11770-3），经验证的密钥协商（ISO/IEC 11770-3）。

分类：
数字签名方案可以根据所基于的数学难题进行分类：
1、基于大整数分解（IF）的方案，安全性基于大整数分解的难度。实例有RSA方案和Rabin方案。
2、基于离散对数（DL）的方案，安全性基于有限域上普通的离散对数问题。实例包ElGamal，Schnorr，DSA和Nyberg-Rueppel方案。
3、基于椭圆曲线（EC）的方案，安全性基于椭圆曲线离散对数问题。

2.2数字签名算法

DSA于1991年由NIST提出，并在FIPS186中得到确认。DSA可以看作是ElGamal签名方案的一个变形。其安全性建立在素域上的离散对数问题的困难性之上。

DSA参数的产生：
每个用户的安全参数产生如下：
1、选择160比特的素数q和1024比特的素数p，满足  。
2、在有限域中寻找q阶循环子群的生成元g，具体方法是在选取元素h计算g= mod p，当g≠1时即找到满足要求的g。
3、域参数就是p，q和g。

DSA密钥对的产生：
每个拥有域参数p，q和g进行如下操作：
1、选择随机或伪随机数x满足12、计算。
3、用户的私钥是x，公钥是y。

DSA签名过程：
1、选择随机或伪随机数k满足12、计算，若r=0则返回第一步。
3、计算。
4、计算e=SHA-1(m)。
5、计算，若s=0则返回第一步。
6、对消息m的签名就是(r,s)。

DSA签名的验证：
为了验证(r,s)是对m的签名，需要使用签名者的域参数(p,q,g)和公钥y进行如下运算：
1、验证r，s在区间[1,q-1]中。
2、计算e=SHA-1(m)。
3、计算。
4、计算和
5、计算及。
6、如果则认可此签名。

安全性分析：

由于r和s均小于q，故DSA签名长度小于320比特。DSA的安全性依赖于两个方面，它们都基于离散对数问题的难解性，一个是Zp*上的离散对数问题，目前已有数域筛算法去加以解决，这是一种亚指数级的算法。其平均运算时间为：

其中c约为1.923，若p是1024比特的素数，则上式的计算量是无法接受的。因此目前1024比特的DSA可以应付现有攻击。另一个是q阶子群上的离散对数问题，给定p，q，g和y，，要寻找x，目前最好的算法是Pollard’s Rho算法，大约要做步。若q是160比特的，则该算法在计算上不可行，因此DSA是很安全的。DSA的安全性主要取决于p和q的尺寸。增加其中一个的尺寸而不增加另一个的尺寸对安全性的提高并无益处。此外，对两种离散对数问题解决算法的提高都会削弱DSA。

安全参数的产生：

DSA的早期版本受到了一些批评，因此FIPS186推出了一种新模式以产生素数p和q以及“可证明的随机性”。它可以防止用户故意构造一个利于破译的素数（例如可以由CA来产生域参数并发送给用户）。FIPS指定了两个模式，分别使用SHA-1和DES，产生伪随机私钥x。FIPS186指定使用这两种模式以及其他经过FIPS认可的安全模式。