CN1831754A - 一种椭圆曲线密码系统及实现方法 - Google Patents

Abstract

一种椭圆曲线密码系统及实现方法，包括有限域算法模块，用于利用Montgom ery算术实现大素数域中的运算；点加与倍点算法模块，实现椭圆曲线上的点加运算与倍点运算；标量乘算法模块，用于实现所述椭圆曲线密码系统的标量乘运算；DH密钥协商算法模块，用于调用标量乘算法模块，完成密钥协商；数字签名与验证模块，用于调用标量乘算法模块，完成对消息的数字签名与验证过程。其提供了一种适合硬件实现的椭圆曲线密码系统及实现方法，无需显式执行耗时的模归约运算，使其同时适合软件与硬件实现。

Description

一种椭圆曲线密码系统及实现方法

技术领域

本发明涉及电子设备的数字内容保护系统，特别是涉及一种椭圆曲线密码系统及实现方法。

背景技术

随着信息技术的不断发展和应用，电子信息的安全性问题变得越来越重要。而密码学作为信息安全的核心，在信息安全中扮演着极为重要的角色。密码学的发展中有两个重要的里程碑：1949年Shanon的“保密通信中的数学理论”和1976年Diffie和Hellman的“密码学的新方向”。Shanon的理论是对密码学的研究变成具有一定理论系统的科学；“密码学的新方向”一文提出了公开密钥密码的思想，开创了公钥密码学的新纪元。公钥密码提出后，立刻受到了人们的普遍关注。从1976年以来，人们提出了大量公钥密码体制的实现方案。所有这些方案的安全性都是基于求解某个数学难题的，截至目前为止，有如下三类既具有一定安全性又易于实现的数学难题：

1.基于大数分解问题(IFP)的公钥密码系统，其中包括RSA体制和Rabin体制；

2.基于有限域上离散对数问题(DLP)的公钥密码体制，其中主要包括ElGamal类加密体制和签名方案，Diffie-Hellman密钥交换方案，Schnorr签名方案和Nyberg-Ruppel签名方案等；

3.基于椭圆曲线离散对数问题(ECDLP)的公钥密码体制，其中主要包括椭圆曲线型的Diffie-Hellman密钥交换方案，椭圆曲线型的MQV密钥交换方案；椭圆曲线型的数字签名算法。

将椭圆曲线用于密码算法，于1985年由Koblitz和Victor Miller分别独立地提出。它问世以来一直是密码分析学的研究对象。现在，在商业和政府的用途中，椭圆曲线密码系统(ECC)都被认为是安全的。根据已知的密码分析学知识，椭圆曲线密码系统相比于传统的密码系统来说提供了更高的安全性。例如，相比基于RSA和ELGamal的加密与数字签名算法和基于Diffie-Hellman密钥协商算法来说，椭圆曲线密码系统具有更短的密钥和更有效的算法。而这两方面的优势使得椭圆曲线密码系统比起传统的密码系统来说更实用，且能广泛用于存储量和计算量受限的环境下，如移动电话和个人数字助理。同样的原因使得椭圆曲线密码系统也倍受高要求系统的青睐，如安全网络设备(这些设备经常用到公钥运算)。

椭圆曲线密码系统(ECC)相对于RSA和DSA等系统吸引人的最主要原因是其安全性是基于有限域上的椭圆曲线上的点群中的离散对数问题ECDLP，ECDLP是比因子分解问题更难的问题，许多密码专家认为它是指数级的难度，即解决其数学问题--椭圆曲线离散对数问题(ECDLP)的已知最好的算法也要用完全指数时间。与之相比，RSA和DSA等其它公钥密码系统所基于的数学问题--因数分解问题(IFP)和离散对数问题(DLP)都是亚指数时间算法，与RSA和DSA等系统相比，椭圆曲线密码系统具有如下更好的优势：

1.安全性更高

密码算法的安全性能通过该算法的抗攻击强度来反映。表1.1描述了椭圆曲线密码系统和其它几种公钥密码算法抗攻击强度的比较。我们可以看到，与其他公钥算法相比，椭圆曲线密码系统抗攻击性具有绝对的优势。如160bit的椭圆曲线密码系统可提供与1024bit的RSA、DSA相当的安全强度，而210bit的椭圆曲线密码系统则与2048bit RSA、DSA具有相同的安全强度。

        表1.1  ECC与RSA/DSA抗攻击性能比较

RSA/DSA密钥长度(比特)	ECC密钥长度(比特)	RSA和ECC密钥长度比率	所需工作量MIPS年
				512	106	5∶1	104
768	132	6∶1	108
				1024	160	7∶1	1011
2048	210	10∶1	1020
				21,000	600	35∶1	1078

其中MIPS年表示每秒钟能运行一百万次指令的计算机运行一年的工作量

2.计算量小，处理速度快

虽然在RSA中可以通过选取较小的公钥(如3)的方法提高公钥处理的速度，既提高加密和签名验证的速度，使其在加密和签名验证上与椭圆曲线密码系统有可比性，但在私钥的处理速度上(解密和签名)椭圆曲线密码系统比RSA、DSA要快。表1.2描述了椭圆曲线密码系统与RSA、DSA在密钥生成，签名和验证速度的比较。

                      表1.2  ECC与RSA/DSA计算速度比较

	ECDSA GF(2n)standard	ECDSA GF(2n)improved	ECDSAGF(p)	RSA	DSA
						key generation	13.0	11.7	5.5	1s	22.7
signature	13.3	11.3	6.3	43.3	23.6
						verification	68	60	26	0.65	28.3

其中，ECC算法为191bit，RSA/DSA为1024bit。随着安全强度的增加，ECC比RSA/DSA运算的速度提高的更快。

3.存储空间少

椭圆曲线密码系统的密钥尺寸和系统参数与RSA/DSA相比要小得多，意味着它所占的存储空间要少得多。这对于密码算法在IC卡和无线环境中的应用具有特别重要的意义。

4.带宽要求低

当对长消息进行加解密时，三类密码系统有相同的带宽要求，但应用于短消息时，椭圆曲线密码系统带宽要求要低得多。带宽要求低使椭圆曲线密码系统在无线网络中具有广阔的应用前景。

由上面的优点我们可以看到，随着计算能力的提高需要密钥长度的增加，椭圆曲线密码系统相对其它公钥密码系统更吸引我们的关注。其每比特更高的安全性所带来的优点包括：更高的速度，更低的能量消耗，节约带宽，提高存储效率。这些优点在一些对于带宽、处理器能力或存储有限制的应用中显得尤为重要。

发明内容

本发明的目的在于提供一种椭圆曲线密码系统及实现方法，为高层认证协议的实现提供底层模块。

为实现本发明的目的而提供的一种椭圆曲线密码系统，包括：

(一)有限域算法模块，用于利用Montgomery算术实现大素数域中的运算。

所述的有限域算法模块包括模加运算模块、模减运算模块、模乘运算模块、模平方运算模块、模归约运算模块、求逆运算模块。

所述的模乘运算模块为CIOS-Montgomery乘法算法模块。

所述的模平方运算模块为SRCIL-Montgomery平方算法模块。

所述的求逆运算模块为指数求逆算法模块。

本发明的椭圆曲线密码系统还包括：

(二)点加与倍点算法模块，用于在利用Montgomery算术实现有限域算法的基础上实现椭圆曲线上的点加运算与倍点运算，其调用有限域算法模块，输入参数为Montgomery域中元素，因而运算结果依然在Montgomery域中。

所述点加运算与倍点运算为优化点加与倍点算法运算。

(三)标量乘算法模块，用于实现所述椭圆曲线密码系统的核心运算：标量乘运算，其输入参数为素数域中元素，运算前转化为Montgomery域中，运算结果转化回素数域中。

所述标量乘运算采用NAF随机标量乘算法。

(四)DH密钥协商算法模块，用于调用标量乘算法模块，完成密钥协商，其输入参数为素数域中元素，运算前转化为Montgomery域中，运算结果转化回素数域中。

(五)数字签名与验证模块，用于调用标量乘算法模块，完成对消息的数字签名与验证过程，其输入参数为素数域中元素，运算前转化为Montgomery域中，运算结果转化回素数域中。

本发明还提供一种椭圆曲线密码系统的实现方法，包括下列步骤：

(一)利用Montgomery算数实现椭圆曲线密码系统中的大素数域中的运算。

所述运算包括模加运算、模减运算、模乘运算、模平方运算、模归约运算、求逆运算。

所述模乘运算模块为CIOS-Montgomery乘法算法。

所述的模平方运算为SRCIL-Montgomery平方算法。

所述的求逆运算模块为指数求逆算法模块。

本发明的椭圆曲线密码系统实现方法，还包括下列步骤：

(二)在利用Montgomery算数实现有限域算法的基础上实现椭圆曲线上的点加运算与倍点运算，其调用有限域算法模块，输入参数为Montgomery域中元素，因而运算结果依然在Montgomery域中。

所述点加运算与倍点运算为优化点加与倍点算法运算。

(三)标量乘运算，其输入参数为素数域中元素，运算前转化为Montgomery域中，运算结果转化回素数域中。

所述标量乘运算采用NAF随机标量乘算法。

(四)调用DH密钥协商算法模块，通过标量乘算法模块，完成密钥协商，其输入参数为素数域中元素，运算前转化为Montgomery域中，运算结果转化回素数域中。

(五)调用数字签名与验证模块，通过标量乘算法模块，完成对消息的数字签名与验证过程，其输入参数为素数域中元素，运算前转化为Montgomery域中，运算结果转化回素数域中。

本发明的有益效果是：本发明提供了一种适合硬件实现的椭圆曲线密码系统及实现方法，其采用了Montgomery算数来实现大素数域中的各种运算，实现椭圆曲线密码系统的所需所有算数运算能够在Montgomery域中进行：模加/模减、模乘以及求逆运算，无需显式执行耗时的模归约运算，使其同时适合软件与硬件实现。

附图说明

图1为椭圆曲线密码系统层次体系结构图；

图2为素数域与Montgomery域元素之间的转换关系。

具体实施方式

下面结合附图1、2进一步详细说明本发明的椭圆曲线密码系统及方法。

椭圆曲线的定义：

一条椭圆曲线是在射影平面上满足方程：

Y²Z+a₁XYZ+a₃YZ²＝X³+a₂X²Z+a₄X²+a₆Z³----------------[3-1]的所有点的集合，且曲线上的每个点都是非奇异或者光滑的。

其中，Y²Z+a₁XYZ+a₃YZ²＝X³+a₂X²Z+a₄X²+a₆Z³是维尔斯特拉斯方程(Weierstrass，Karl Theodor Wilhelm Weierstrass，1815-1897)，是一个齐次方程。

所谓“非奇异”或“光滑”的，在数学中是指曲线上任意一点的偏导数F_x(x，y，z)，F_y(x，y，z)，F_z(x，y，z)不能同时为0。

设椭圆曲线上有一个无穷远点O∞(0∶1∶0)，因为这个点满足方程[3-1]，

x＝X/Z，y＝Y/Z代入方程[3-1]得到：

Y²+a₁xy+a₃y＝x³+a₂x²+a₄x+a₆-------------------------[3-2]

其中，(x，y)为普通平面直角坐标系上的坐标。

也就是说满足方程[3-2]的光滑曲线加上一个无穷远点O∞，组成了椭圆曲线。

椭圆曲线是连续的，并不适合用于加密，因此，一般地，要把适合加密的椭圆曲线定义在有限域上。

有限域是一种只由有限个元素组成的域。

给出一个有限域F_p，这个域只有有限个元素，即F_p中只有p(p为素数)个元素0，1，2……p-2，p-1。

定义F_p的加法(a+b)法则是a+b≡c(mod p)；即，(a+b)÷p的余数和c÷p的余数相同；

F_p的乘法(a×b)法则是a×b≡c(mod p)；

F_p的除法(a÷b)法则是a/b≡c(mod p)；即a×b^-1≡c(mod p)；(b^-1也是一个0到p-1之间的整数，但满足b×b^-1≡1(mod p))。

F_p的单位元是1，零元是0。

但是，并不是所有的有限域上的椭圆曲线都适合加密，其中对于定义在大素数域上的椭圆曲线是适合于加密的椭圆曲线，大素数域上的椭圆曲线可通过同构映射将一般的曲线方程变换为特别简单的形式：y²＝x³+ax+b，其中曲线参数a，b∈F_p并且满足4a³+27b²≠0(mod p)。

因此，满足下列方程的所有点(x，y)，再加上无穷远点O∞，构成一条定义在大素数域F_p上的椭圆曲线。

Y²＝x³+ax+b(mod p)

其中x，y属于0到p-1间的大素数，并将这条椭圆曲线记为E_p(a，b)。

公开密钥算法总是要基于一个数学上的难题。比如RSA密码系统依据的是：给定两个大素数p、q很容易相乘得到n，而对n进行因式分解却相对困难。

考虑如下等式：

K＝kG[其中K，G为E_p(a，b)上的点，k为小于n(n是点G的阶)的整数，不难发现，给定k和G，根据加法法则，计算K很容易；但给定K和G，求k就相当困难了。

这就是椭圆曲线密码系统基于的数学难题。把点G称为基点(base point)，k(k＜n，n为基点G的阶)称为私有密钥(private key)，K称为公开密钥(publickey)。

本发明是采用了Montgomery算数来实现大素数域中的各种运算，从而实现椭圆曲线密码的系统和方法。

如图2所示Montgomery算数由Peter Montgomery提出，其核心运算是Montgomery乘法，由于Montgomery乘法既不需要计算及其耗时的除法也不需要利用商估值技术，因此它简化了模归约运算。

从数学的角度来看，Montgomery域与素数域GF(p)是同构的，GF(p)中的每一个元素在Montgomery域都有一个唯一与之对应的元素。元素a∈GF(p)在Montgomery域中表示为a′＝a·R mod p，其中R称为Montgomery常数(R必须大于p)。Montgomery常数R与大素数域的特征必须互素，即gcd(R，p)＝1。通常选取R是2的幂次：R＝2^m，其中m反映了硬件的规模，较佳为R＝2¹⁹²。

利用Montgomery算数完成素数域运算需要将操作数由素数域转化到Montgomery域，转化可利用Montgomery乘法完成：a′＝MonMul(a，R²)＝a·R²/R mod p＝a·R mod p。

在系统中通过硬件实现Montgomery乘法算法，则这种转化在硬件实现时不再需要其它的运算，因此也不需要附加的硬件资源，转化时Montgomery常数R＝2^m mod p已经被预计算，即计算R²需要一些花费，但对于每个模p仅需计算一次。

由Montgomery域转化到素数域也可利用Montgomery乘法完成：a＝MonMul(a′，1)＝a′·1/R mod p＝a·R·1/R mod p＝a mod p；b与a的运算方式是一样的，即对b有下式成立b＝MonMul(b′，1)＝b′·1/R mod p＝b·R·1/R mod p＝b mod p。当在Montgomery域中执行大量算数运算时，这种转化的花费可以忽略，因为只需在所有运算开始和结束时进行一次。本发明中的椭圆曲线密码系统运算开始时所有的操作数被转化到Montgomery域中接着在Montgomery域完成所有椭圆曲线上的点运算，最后运算结果被转化到大素数域。

这样，本发明利用大整数的Montgomery表示可以有效地实现素数域中的模运算，而且在Montgomery域中无需显式执行耗时的模归约运算，实现椭圆曲线密码系统的所需的所有算数运算能够在Montgomery域中进行：模加/模减、模乘、求逆运算、模平方运算以及模归约运算。

模加运算：a+b mod p＝MonAdd(a’，b’)＝(a+b)R mod p＝a’+b’mod p

模乘运算：a·bmod p＝MonMul(a’，b’)＝(a·b)R mod p＝a’·b’/R mod p

求逆运算：a^-1 mod p＝MonInv(a’)＝a^-1R mod p＝a’^-1R2 mod p

模减运算：a-b mod p＝MonSub(a’，b’)＝(a-b)R mod p＝a’-b’mod p

模平方运算：a²mod p＝MonSq(a’²)＝(a²)R mod p＝a’²/R mod p

模归约运算：r＝cR^-1 mod p

其中，MonMul：模乘运算；MonAdd：模加运算；MonInv：求逆运算；MonSub：模减运算；MonSq：模平方运算

下面结合图1详细说明本发明实施例的椭圆曲线密码系统：

如图1所示，本实施例的椭圆曲线密码系统包括：

有限域算法模块，用于利用Montgomery算数实现大素数域中的加法运算、乘法运算、平方运算以及求逆运算。

这里的大素数域就是指的一般的素数域F_p，p是大于2的素数。

所述的有限域算法模块包括模加运算模块、模减运算模块、模乘运算模块、模平方运算模块、模归约运算模块、求逆运算模块。

所述的模乘运算模块为CIOS-Montgomery乘法算法模块(CoarselyIntegrated Operand Scanning)，该算法模块占用的资源最少，速度最快。

CIOS-Montgomery乘法算法的原理是：该算法集成了乘法与归约步骤。具体地说，此算法并没有直接计算a与b的乘积然后对该乘积进行归约，而是对乘法和归约在外层循环中交替进行，这样做是由于在第i次外层循环中归约步骤所用到的值m仅依赖于s[i]的值，而在乘法的第i次循环中s[i]的值已经计算完毕。

所述的模平方运算模块为SRCIL-Montgomery平方算法模块(SquaringReduction with Inner Loop)，该算法速度最快。SRCIL-Montgomery平方算法原理是：该算法去除了一般Montgomery平方算法中的冗余部分并最大化算法软件并行的能力，其基本思想是使用了一个单独的循环计算a_i×a_i、去掉了进位的延迟并且通过改变循环的结构去掉冗余的部分。

所述的求逆运算模块为指数求逆算法模块，用费马小定理实现有限域中的求逆运算，即b＝a^p-2(mod p)，其能够利用硬件电路板上的Montgomery乘法器资源，该算法模块在有Montgomery乘法器的硬件电路板上的执行时间约为二元扩展欧几里得算法执行时间的70％。

本实施例中的椭圆曲线密码系统，还包括：

点加与倍点算法模块，用于在利用Montgomery算数实现有限域算法的基础上实现椭圆曲线上的点加运算与倍点运算，其采用优化点加与倍点算法实现群运算，调用有限域算法模块，输入参数为Montgomery域中元素，因而运算结果依然在Montgomery域中。

标量乘算法模块，用于实现所述椭圆曲线密码系统的核心运算：标量乘运算，其输入参数为素数域中元素，运算前转化为Montgomery域中，运算结果转化回素数域中。所述标量乘模块中的运算采用NAF随机标量乘算法。

NAF随机点标量乘算法原理是：NAF随机点标量乘算法首先对标量进行NAF编码，即标量k的NAF表示为 ${\mathrm{\Σ}}_{i=0}^l{k}_i{2}^i$ ，其中k_i∈{0，±1}并且相邻的k_i中至少有一个为0。通过这种编码方式可以有效地计算标量乘，NAF标量乘算法期望的运行时间约为(m/3)A+mD，其中m＝[log₂p]，A表示点加运算，D表示倍点运算。

DH密钥协商算法模块，用于调用标量乘算法模块，完成密钥协商。其输入参数为素数域中元素，运算前转化为Montgomery域中，运算结果转化回素数域中。

EC-Diffie-Hellman密钥协商是从一个主体的私钥和另一个主体的公钥导出一个共享的秘密值，此处两个主体具有相同的EC域参数。如果双方能够正确的执行完该协议，则他们将得到相同的结果。该算法可被一些方案调用以产生一个共享的秘密钥，其中，所输入的密钥是有效的。

数字签名与验证模块，用于调用标量乘算法模块，完成对消息的数字签名与验证过程。其输入参数为素数域中元素，运算前转化为Montgomery域中，运算结果转化回素数域中。

椭圆曲线数字签名与验证算法(Elliptic Curve Digital Signature Algorithm，ECDSA)是类似于DSA(Digital Signature Algorithm)的一种基于椭圆曲线的数字签名与验证算法，其不象一般的离散对数问题和整数分解问题，椭圆曲线离散对数问题没有亚指数算法，正由于这点，使得采用椭圆曲线离散对数的算法的每比特强度在实质上更强了。

ECDSA的主要参数包括：定义在有限域GF(p)上的椭圆曲线E，E上的GF(p)-有理点的个数#E(GF(p))可被一个大素数n整除，一个基点G∈E(GF(p))，可记为：D＝(p，a，b，G，n，h)，(d，Q)，Hash函数H。

将D＝(p，a，b，G，n，h)，Hash函数H，Q公开，d保密。

在本实施例的椭圆曲线密码系统中，首先需要实现底层有限域中的各种基本的运算包括：加法运算、乘法运算、平方运算以及求逆运算；其次在有限域算法库的基础上实现椭圆曲线上的点加运算与倍点运算；最后实现椭圆曲线密码系统的核心运算：标量乘运算；通过调用标量乘算法模块，完成密钥协商；通过调用标量乘算法模块，完成对消息的数字签名与验证过程。

下面结合本发明的椭圆曲线密码系统，进一步详细描述本发明的椭圆曲线密码系统的实现方法，包括下列步骤：

(一)利用Montgomery算数实现大素数域中的加法运算、乘法运算、平方运算以及求逆运算。

这里的大素数域就是指的一般的素数域F_p，p是大于2的素数。

◆模加运算：

modadd算法：

输入：整数a，b∈[0，p-1]，a＝(a_t-1，a_t-2，…，a₁，a₀)，b＝(b_t-1，b_t-2，…，b₁，b₀)。

输出：c＝a+b mod p。

1.c₀←Add(a₀，b₀)，//低32比特相加

2.For i from 1 to t-1 do：c_i←Add(a_i，b_i)+carry(a_i-1，b_i-1).//a与b进行带进位的32比特加法

3.If c≥p，then c←c-p.//如果carry(a_t-1，b_t-1)≠0，则最后的运算结果有进位执行减p运算

4.Return(c).//返回运算结果

其中，Add(a_i，b_i)：＝(a_i+b_i)mod2³²，carry(a_i，b_i)：＝(a_i+b_i)/2³²

◆模减运算：

modsub算法：

减运算和加运算是非常类似的，不同的是它要用到借位。

输入：整数a，b∈[0，p-1]，a＝(a_t-1，a_t-2，…，a₁，a₀)，b＝(b_t-1，b_t-2，…，b₁，b₀)。

输出：c＝a-b mod p。

1.borrow←0.//初始化将借位borrow赋予0

2.For i from 0 to t-1 do：//a与b进行带进位的32比特加法

2.1. c_i←(a_i-b_i-borrow)mod2³²  //32比特减法运算结果

2.2. If^ai-bi-borrow≥0，then borrow←0；otherwise borrow←1.//32比特减法结果为正则借位borrow为0，否则借位borrow为1

3.If borrow＞0，then c←c+p.//如果运算最后还有借位则执行加p运算

4.Return(c).//返回运算结果

由于在modadd中用到了a-b(a≥b)，这只是modsub的一个特殊情况，只须将上面算法中的第3步去掉即可。

◆模乘运算：

Montgomery乘法有多种实现方式，本实施例采用了最为有效的CIOS-Montgomery乘法算法(Coarsely Integrated Operand Scanning)，该算法占用的资源最少，速度最快。

输入：整数a，b∈[0，p-1]，a＝(a_t-1，a_t-2，…，a₁，a₀)，b＝(b_t-1，b_t-2，…，b₁，b₀)。

输出：c＝abR^-1 mod p

1.For i from 0 to t-1 do：s[i]←0.//初始化存储运算结果的数组

s6←0，s7←0  //初始化临时变量

2.For i from 0 to t-1 do：

2.1. C←0.//初始化临时变量

2.2. Forj from 0 to t-1 do：//a与b进行32比特乘法

计算(C，S)＝s[j]+a_jb_i+C，//32比特乘法的中间结果

令t[j]←S.//存储32比特进位

2.3.(C，S)←s6+C，s6←S，s7←C.//存储最高位的运算结果

2.4.C←0，m＝s[0]*p’[0]mod 2³²，(C，S)＝s[0]+m*p[0].//对最低32比特进行归约

2.5.Forj form 1 to t-1 do：//逐段归约

计算(C，S)＝s[j]+m*p[j]+C，//32比特中间结果归约

令s[j-1]←S.//存储32比特进位

2.6.(C，S)←s6+C，s[t-1]←S，s6←s7+C  //存储归约结果

3. If s6！＝0  //有进位

3.1 C＝1；//初始化临时变量

3.2 For i from 0 to t-1 do：//逐段进行进位纠正

计算(C，S)＝s[i]+～p[i]+C，//进位纠正

令s[i]←S.//存储32比特进位

4.Return((S_t-1，…，s₁，s₀))  //返回运算结果

这里C，S都是32比特的字，(C，S)是C，S的连接，它是64比特；

p’[0]＝-p[0]^-1 mod 2³²，其中p[0]是192比特素数p的最低32比特(最低的字)。

◆模平方运算：

Montgomery平方也有多种实现方式，本实施例采用了最为有效的SRCIL-Montgomery平方算法(Squaring Reduction with Inner Loop)，该算法速度最快。

输入：整数a，b∈[0，p-1]，a＝(a_t-1，a_t-2，…，a₁，a₀)。

输出：c＝a²R^-1 mod p

1.For i from 0 to t-1 do：(s[2i+1]，s[2i])←a_i×a_i；//计算第i段相乘结果

2.For i from 0 to t-1 do：//对第1步运算结果进行归约

2.1 m＝s[i]×p′[0]mod 2³²；//计算每段归约值

2.2 Forj from 0 to i do：//逐段归约

(C，s[i+j])＝s[i+j]+m×p[j]+C；//32比特中间结果归约

2.3 C₁＝0；C₂＝0；//初始化临时变量

2.4 Forj from i+1 to t-1 do：//计算a_i与a_j的乘积并进行归约

2.4.1 s_long＝2×C₁+C+s[i+j]  //存储中间结果

2.4.2 (C₁，S)＝a_i×a_j；//计算a_i与a_j的乘积

2.4.3 (C，s[i+j]＝s_long+2×S；//与低段运算结果的进位相加

2.4.4 (C₂，s[i+j]＝m×p[j]+s[i+j]+C₂.//32比特中间段归约

2.5 (prevcar，s[i+t])＝C+2×C₁+C₂+s[i+t]+prevcar；//存储最高32比特

3.s[2t]＝s[2t]+prevcar；//存储最高位的进位

4.For i from 0 to t-1 do：s[i]←s[i+t]  //将运算结果移至低t个单元

5.If s[2t]！＝0//若进位不等于0

1.1 C＝1；//初始化临时变量

1.2 For i from 0 to t-1 do：//逐段进行进位纠正

计算(C，S)＝s[i]+～p[i]+C；//进位纠正

令s[i]←S.//存储32比特进位

6.Return((s_t-1，…，s₁，s₀))  //返回运算结果

其中，C，C₁，C₂，S都是32比特的字，(C，S)是C，S的连接，它是64比特；p’[0]＝-p[0]^-1 mod 2³²，其中p[0]是192比特素数p的最低32比特(最低的字)。

◆Montgomery模归约算法：

输入：c＝(c_2t-1，…，c₁，c₀)

输出：r＝cR^-1 mod p.

1.For i from 0 to t-1 do：//归约

1.1 C＝0；//初始化临时变量

1.2 m＝c_i*p’[0]；//计算每段归约值

1.3 Forj from 0 to t-1 do：//逐段归约

计算(C，S)＝c_i+j+m*p[j]+C；//32比特中间结果归约

1.4 (prevcar，s[i+t])＝C+s[i+t]+prevcar；//存储最高32比特

2.For i from 0 to t-1 do：c[i]←c[i+t]  //将运算结果移至低t个单元

3.If prevcar！＝0  //若进位不等于0

3.1 C＝1；//初始化临时变量

3.2 For i from 0 to t-1 do：//逐段进行进位纠正

计算(C，S)＝c[i]+～p[i]+C；//进位纠正

令r[i]←S  //存储32比特进位

4.Return((r_t-1，…，r₁，r₀))  //返回运算结果

◆Montgomery求逆算法：

考虑到利用硬件电路板上的Montgomery乘法器资源，因此本实施例考虑用费马小定理实现有限域中的求逆运算，即b＝a^p-2(mod p)。该算法在有Montgomery乘法器的硬件电路板上的执行时间约为二元扩展欧几里得(Euclid)算法执行时间的70％。

输入：整数a∈[0，p-1]，a＝(a_t-1，a_t-2，…，a₁，a₀)

输出：b＝a^-1 mod p.

1. a＝a·R mod p；//将a变换到Montgomery域

2. x＝1·R mod p；//将1变换到Montgomery域

3.For i from j-1 down to 0 do：//计算模指数

3.1  x＝MontMult( x， x)；//模平方运算

3.2 If e_i＝1 then  x＝MontMult( x， a)；

//如果p-2的当前比特是1则执行模乘运算

4.Return b＝MontMult( x，1).//返回运算结果至素数域

◆除法：

有限域中的除法运算是乘法和求逆的组合，本领域普通技术人员能够根据本实施例中关于乘法与求逆的描述，实现本发明的除法运算，因此，在本实施例中不再详细描述。

(二)在利用Montgomery算数实现有限域算法的基础上实现椭圆曲线上的点加运算与倍点运算，本实施例采用优化的点加与倍点算法实现群运算，调用有限域算法模块，输入参数为Montgomery域中元素，因而运算结果依然在Montgomery域中。

对于群运算，本实施例对IEEEP1363标准中的点加以及倍点算法进行了优化，采用了与IEEEP1363标准(IEEEP1363标准的参考文献：IEEE std1363-2000：Standard specifications for public-key cryptography，2000，standards.ieee.org/catalog/oils/busarch.html)中不同的运算顺序，从而使得算法所需要的临时变量最少，优化算法如下：

◆点加(elliptic_add)

GF(p)上椭圆曲线y²＝x³+ax+b的点加公式的Modified-Jacobian坐标形式是：

$P=(X_1,Y_1,Z_1{,\mathrm{aZ}}_1^4),$ $Q=(X_2,Y_2,Z_2,{\mathrm{aZ}}_2^4),$ 且 $P+Q=(X_3,Y_3,Z_3,{\mathrm{aZ}}_3^4)$

这里 $U_1=X_1{Z}_2^2,$ $U_2=X_2{Z}_1^2,$ $S_1=Y_1{Z}_2^3,$ $S_2=Y_2{Z}_1^3,$ H＝U₂-U₁，T＝S₂-S₁，X₃＝-H³-2U₁H²+T²，Y₃＝-S₁H³+T(U₁H²-X₃)，Z₃＝Z₁Z₂H，

${\mathrm{aZ}}_3^4=a{\left(Z_3\right)}^4.$

其算法如下：

输入：p，a，b，Q_in＝(X，Y，Z)，P＝(X₂，Y₂).

输出：Q_out＝(X，Y，Z，aZ⁴)＝Q_in+P.

1.If(P＝＝O)       //判断是否点P是无穷远点

     aZ⁴＝a*Z⁴ if necessary    //需要时计算aZ⁴的值

     return Q_out    //返回点加结果

2.If(Z＝＝0)       //判断是否点Q_in是无穷远点

     Q_out＝P       //点加结果为P

     return Q_out   //返回点加结果

3.aZ⁴＝Z²        //计算Z²

4.T₁＝X₂*aZ⁴    //计算U₂＝X₂Z²

5.T₁＝T₁-X       //计算H＝U₂-U₁

6.aZ⁴＝Z*aZ⁴     //计算Z³

7.aZ⁴＝Y₂*aZ⁴   //计算Y₂＝Y₂Z³

8.aZ⁴＝aZ⁴-Y     //计算T＝S₂-S₁

9.Z＝Z*T₁        //计算Z₃＝ZH

10.If(T₁＝＝0)     //如果U₂＝U₁

      If(aZ⁴＝＝0)   //如果P＝Q_in

      Q_out＝P      //初始化Q_out

      Double(Q_out)     //此时计算结果为2P

      return Q_out     //返回点加结果

else              //此时P＝-Q_in

    Z＝0          //此时计算结果为无穷远点

    aZ⁴＝0       //此时计算结果为无穷远点

    return Q_out  //返回点加结果

11. $T_2=T_1^2$             //计算H²

12.T₁＝T₁*T₂     //计算H³

13.Y＝T₁*Y        //计算S₁H³

14.T₂＝X*T₂      //计算U₁H²

15.X＝(aZ⁴)²     //计算T²

16.X＝X-T₁        //计算T²-H³

17.X＝X-T₂        //计算T²-U₁H²-H³

18.X＝X-T₂        //计算X₃＝T²-2U₁H²-H³

19.T₂＝T₂-X      //计算U₁H²-X₃

20.T₂＝aZ⁴*T₂    //计算T(U₁H²-X₃)

21.Y＝T₂-Y       //计算Y₃＝T(U₁H²-X₃)-S₁H³

22.aZ⁴＝Z²       //计算Z²

23.aZ⁴＝(aZ⁴)²  //计算Z⁴

24.If(a＝＝p-3)  //如果a＝p-3

      aZ⁴＝0-3aZ⁴    //计算-3Z⁴

    else

      aZ⁴＝a*aZ⁴     //计算aZ⁴

这个算法需要9次域乘法、5次域平方和2个临时变量。

◆倍点(elliptic_doubl)

GF(p)上椭圆曲线y²＝x³+ax+b的倍点公式的Modified-Jacobian坐标形式是：

$Q_{\mathrm{in}}=(X_1,Y_1,Z_1,a{Z}_1^4),$ $Q_{\mathrm{out}}={2Q}_{\mathrm{in}}=(X_3,Y_3,Z_3,{\mathrm{aZ}}_3^4)$

这里： $S={4X}_1{Y}_1^2,$ $U={8Y}_1^4,$ $M={3X}_1^2+\left({\mathrm{aZ}}_1^4\right),$ T＝M²-2S，X₃＝T，Y₃＝M(S-T)-U，Z₃＝2Y₁Z₁， ${\mathrm{aZ}}_3^4=2U{\left({\mathrm{aZ}}_1\right)}^4$

其算法如下：

输入：p，a＝-3，b，Q_in＝(X，Y，Z，aZ⁴).

输出：Q_out＝(X，Y，Z，aZ⁴)＝2 Q_in.

1.If(Z＝＝0)return Qout  //如果Qin是无穷远点输出结果

2.T1＝2Y              //计算2Y

3.Z＝T1*Z             //计算Z3＝2YZ

4.Y＝Y2                   //计算Y2

5.T1＝2X              //计算2X

6.T1＝2T1                 //计算4X

7.T1＝T1*Y           //计算S＝4XY2

8.T2＝X2                 //计算X2

9. X＝2T2                //计算2X2

10.T2＝X+T2             //计算3X2

11.T2＝T2+aZ4           //计算M＝3X2+aZ4

12. $X=T_2^2$          //计算M2

13.X＝X-T1             //计算M2-S

14.X＝X-T1             //计算X3＝T＝M2-2S

15.T1＝T1-X        //计算S-T

16.T2＝T2*T1           //计算M(S-T)

17.Y＝2Y           //计算2Y2

18.Y＝Y2               //计算4Y4

19.Y＝2Y           //计算U＝8Y4

20.T1＝2Y          //计算2U

21.aZ4＝T1*aZ4        //计算2U(aZ4)

22.Y＝T2-Y        //计算Y3＝M(S-T)-U

本实施例选取的a＝p-3，上面算法仅需4次域乘法以及4次域平方。

(三)实现所述椭圆曲线密码系统的核心运算：标量乘运算，其输入参数为素数域中元素，运算前转化为Montgomery域中，运算结果转化回素数域中。所述标量乘模块中的运算采用NAF随机标量乘算法。

对于标量乘算法，考虑到硬件实现标量乘算法时是采用有限状态机对标量的状态进行编码的，因此为了减少有限状态机控制逻辑的复杂性以及存储空间的大小本实施例对标量进行了NAF编码并采用了下面的随机点标量乘算法，该算法无需进行预计算。

◆随机点标量乘

随机点标量乘算法对标量进行NAF(non-adjacent form)编码，下面将这一算法描述如下：

输入：整数 $k={\mathrm{\Σ}}_{i=0}^{l-1}{b}_i{2}^i,$ 其中b_i∈{0，1}且b_l＝b_l+1＝0，椭圆曲线上的点P

输出：椭圆曲线上的点Q，Q＝kP

/*对标量进行NAF(non-adjacent form)编码： 其中k_i∈{0，±1}*/

1.α←0    //初始化临时变量

2.For i from 0 to l do：//NAF(non-adiacent form)编码

k_i←b_i+α-2β，//计算NAF编码并存储在k_i中

α←β，

/*由标量的NAF表示计算标量乘*/

3.For i from l down to 0 do：//计算标量乘

3.1.Q←2Q    //倍点运算

3.2.If k_i≠0 then：//k_i不为零时需要执行点加运算

        If k_i＝＝1，then Q←Q+P；//k_i＝1时执行Q+P

        Else Q←Q-P              //k_i＝-1时执行Q+(-P)

Return(Q)              //返回标量乘运算结果

(四)用于调用标量乘算法模块，完成对消息的数字签名与验证过程。其输入参数为素数域中元素，运算前转化为Montgomery域中，运算结果转化回素数域中。

DH密钥协商算法：

EC-Diffie-Hellman密钥协商是从一个主体的私钥和另一个主体的公钥导出一个共享的秘密值，此处两个主体具有相同的EC域参数。如果双方能够正确的执行完该协议，则他们将得到相同的结果。该算法可被一些方案调用以产生一个共享的秘密钥，其中，所输入的密钥是有效的。

输入：

——EC基本参数q，a，b，n和G以及相应的密钥s和W′(对于s和W′，基本参数应该一样)

——主体自己的私钥s

——另一主体的公钥W′

其中：私钥s，EC基本参数q，a，b，r和G，以及公钥W′是有效的；所有的密钥都和同一基本参数相关。

输出：导出的共享秘密值z∈GF(q)；或者“error”

操作.共享的秘密值z必须按照以下步骤进行：

1.计算椭圆曲线点P＝s W′.

2.如果P＝O输出“error”并停止。

3.令z＝xP，既点P的x坐标。

4.输出z作为共享的秘密钥。

(五)调用标量乘算法模块，完成对消息的数字签名与验证过程。其输入参数为素数域中元素，运算前转化为Montgomery域中，运算结果转化回素数域中。

椭圆曲线数字签名与验证算法(ECDSA)：

ECDSA(Elliptic Curve Digital Signature Algorithm)是类似于DSA(DigitalSignature Algorithm)的一种基于椭圆曲线的数字签字与验证算法。不象一般的离散对数问题和整数分解问题，椭圆曲线离散对数问题没有亚指数算法，正由于这点，使得采用椭圆曲线离散对数的算法的每比特强度在实质上更强了。

ECDSA的主要参数包括：定义在有限域GF(p)上的椭圆曲线E，E上的GF(p)-有理点的个数#E(GF(p))可被一个大素数n整除，一个基点G∈E(GF(p))。我们可记为：D＝(p，a，b，G，n，h)，(d，Q)，Hash函数H。

将D＝(p，a，b，G，n，h)，Hash函数H，Q公开，d保密。

◆签名生成：

签名者A利用上面的参数及公私钥对如下对一消息m进行签名：

1.随机或伪随机地选择一个整数 $k{\∈}_R{Z}_n^{*};$

2.计算kG＝(x₁，y₁)，r＝x₁ mod n，如果r＝0，则返回到1；

3.计算k^-1 mod n；

4.计算e＝H(m)；

5.计算s＝k^-1(e+dr)mod n，如果s＝0，则返回到1。

其中，(r，s)是A对消息m的签名。

◆签名验证：

验证者B如下验证(r，s)是A对消息m的签名：

1.验证r，s是[1，n-1]中的整数；

2.计算e＝H(m)；

3.计算w＝s^-1 mod n；

4.计算u₁＝ew mod n，u₂＝rw mod n；

5.计算X＝u_iG+u₂Q＝(x₁，y₁)，如果X＝O，则拒绝这个签名，否则，计算v＝x₁ mod n，当且仅当v＝r时接受这个签名。

本发明提供了一种适合硬件实现的椭圆曲线密码系统及实现方法，其采用了Montgomery算数来实现大素数域中的各种运算，实现椭圆曲线密码系统的所需所有算数运算能够在Montgomery域中进行：模加/模减、模乘以及求逆运算，无需显示执行耗时的模归约运算，使其同时适合软件与硬件实现。

本实施例是为了使本领域普通技术人员理解而对本发明所进行的详细描述，但本领域普通技术人员可以想到，在不脱离本发明的权利要求所涵盖的范围内还可以做出其它的变化和修改，其均在本发明的保护范围内。

Claims (22)

1.一种椭圆曲线密码系统，其特征在于，包括有限域算法模块，用于利用Montgomery算术实现大素数域中的运算。

2.根据权利要求1所述的椭圆曲线密码系统，其特征在于，所述的有限域算法模块包括模加运算模块、模减运算模块、模乘运算模块、模平方运算模块、模归约运算模块、求逆运算模块。

3.根据权利要求2所述的椭圆曲线密码系统，其特征在于，所述的模乘运算模块为CIOS-Montgomery乘法算法模块。

4.根据权利要求3所述的椭圆曲线密码系统，其特征在于，所述的模平方运算模块为SRCIL-Montgomery平方算法模块。

5.根据权利要求4所述的椭圆曲线密码系统，其特征在于，所述的求逆运算模块为指数求逆算法模块。

6.根据权利要求1～5任一项所述的椭圆曲线密码系统，其特征在于，还包括点加与倍点算法模块，用于在利用Montgomery算术实现有限域算法的基础上实现椭圆曲线上的点加运算与倍点运算，其调用有限域算法模块，输入参数为Montgomery域中元素，因而运算结果依然在Montgomery域中。

7.根据权利要求6所述的椭圆曲线密码系统，其特征在于，所述点加运算与倍点运算为优化点加与倍点算法运算。

8.根据权利要求7所述的椭圆曲线密码系统，其特征在于，还包括标量乘算法模块，用于实现所述椭圆曲线密码系统的核心运算：标量乘运算，其输入参数为素数域中元素，运算前转化为Montgomery域中，运算结果转化回素数域中。

9.根据权利要求8所述的椭圆曲线密码系统，其特征在于，所述标量乘运算采用NAF随机标量乘算法。

10.根据权利要求9所述的椭圆曲线密码系统，其特征在于，还包括DH密钥协商算法模块，用于调用标量乘算法模块，完成密钥协商，其输入参数为素数域中元素，运算前转化为Montgomery域中，运算结果转化回素数域中。

11.根据权利要求10所述的椭圆曲线密码系统，其特征在于，还包括数字签名与验证模块，用于调用标量乘算法模块，完成对消息的数字签名与验证过程，其输入参数为素数域中元素，运算前转化为Montgomery域中，运算结果转化回素数域中。

12.一种椭圆曲线密码系统的实现方法，其特征在于，包括下列步骤：

利用Montgomery算数实现椭圆曲线密码系统中的大素数域中的运算。

13.根据权利要求12所述的实现方法，其特征在于，所述运算包括模加运算、模减运算、模乘运算、模平方运算、模归约运算、求逆运算。

14.根据权利要求13所述的实现方法，其特征在于，所述模乘运算模块为CIOS-Montgomery乘法算法。

15.根据权利要求14所述的实现方法，其特征在于，所述的模平方运算为SRCIL-Montgomery平方算法。

16.根据权利要求15所述的实现方法，其特征在于，所述的求逆运算模块为指数求逆算法模块。

17.根据权利要求12～16所述的实现方法，其特征在于，还包括下列步骤：

在利用Montgomery算数实现有限域算法的基础上实现椭圆曲线上的点加运算与倍点运算，其调用有限域算法模块，输入参数为Montgomery域中元素，因而运算结果依然在Montgomery域中。

18.根据权利要求17所述的实现方法，其特征在于，所述点加运算与倍点运算为优化点加与倍点算法运算。

19.根据权利要求18所述的实现方法，其特征在于，还包括下列步骤：标量乘运算，其输入参数为素数域中元素，运算前转化为Montgomery域中，运算结果转化回素数域中。

20.根据权利要求19所述的实现方法，其特征在于，所述标量乘运算采用NAF随机标量乘算法。

21.根据权利要求20所述的实现方法，其特征在于，还包括下列步骤：

调用DH密钥协商算法模块，通过标量乘算法模块，完成密钥协商，其输入参数为素数域中元素，运算前转化为Montgomery域中，运算结果转化回素数域中。

22.根据权利要求21所述的实现方法，其特征在于，还包括下列步骤：

调用数字签名与验证模块，通过标量乘算法模块，完成对消息的数字签名与验证过程，其输入参数为素数域中元素，运算前转化为Montgomery域中，运算结果转化回素数域中。

Images