CN1610291A - 数据加密及解密的方法 - Google Patents

Abstract

本发明公开了一种数据加密及解密的方法，当发送方向接收方发送数据时，对所要发送的数据依照伪加加密的方法进行加密处理；相应地，在接收数据的一方则采用与伪加加密方法对应的方法进行解密；本发明充分利用了伪加的特点，得到了一个具有新的明文嵌入方法，并得到在适应性选择密文攻击下语义安全的加密体制，该特点也是其与传统椭圆曲线密码体制最大的区别。本发明给出了一种非常简洁的明文嵌入方式，并可以在解密时验证密文的合法性，以此提供了更高级别的数据安全性。本发明对于数据的加密和解密相比于现有的基于椭圆曲线的加密、解密处理在适应性选择密文攻击下，其语义更加安全。

Description

数据加密及解密的方法

技术领域

本发明涉及一种数据加密及解密的方法，特别涉及一种在具有新的明文嵌入方式的椭圆曲线群上，适应性选择密文攻击下语义安全的加密和相应的解密方法，属于计算机及通信安全技术领域。

背景技术

自从1976年迪菲(Diffie)和赫尔曼(Hellman)提出公钥加密体制的思想后，密码学家和数学家为了该思想的具体实现已经研究了近三十年，但到目前为止，安全有效的公钥加密体制仍是非常有限的，依据其基于的难题，大致可以将其分为三类：基于对大数分解难题的加密体制、基于有限域离散对数问题的加密体制和基于椭圆曲线离散对数问题的加密体制。其中，由于还没有找到解决椭圆曲线离散对数问题的次(亚)指数时间算法，所以基于椭圆曲线离散对数问题的加密体制具有前两类加密体制无法比拟的优点，例如：在相同的安全强度下，系统参数和密钥的尺寸较短(如160bits的椭圆曲线公钥密码(Elliptic Curve Cryptography，简称ECC)和1024bits的RSA具有相当的安全强度)，选择余地较大等。

椭圆曲线公钥密码是于1985年由V.Miller和N.Koblitz各自独立提出的，随后提出的椭圆曲线密码体制几乎都是将已有的基于有限域上离散对数问题的密码体制平移到椭圆曲线群上而得到。美国电子电气工程师协会标准IEEE P1363中提到的椭圆曲线加密体制ECES(Elliptic CurveEncryption Scheme)，来源于ElGamal体制，由于它的加密算法具有扩展性，故它不是适应性选择密文攻击下不可区分的(Indistinguishabilityunder adaptive chosen-ciphertext attack，IND-CCA2)，而是选择明文攻击下不可区分的(Indistinguishability under chosen-plaintextattack，IND-CPA)；2000年，M.Abdalla等人提出了在标准模型下安全的加密体制DHIES(基于迪菲-赫尔曼问题的加密体制)，由于其效率和ElGamal相当，而安全级别较高，故被一些标准所采用，如ANSI X9.63(ANSI是美国国家标准化组织American National Standards Institute的简称)和SECG(The Standards for Efficient Cryptography Group，椭圆密码组标准)。将DHIES应用于椭圆曲线群便获得椭圆曲线集成加密体制ECIES(Elliptic Curve Integrated Encryption System)，它是美国Certicom公司向欧洲负责关于签名、完整性和加密新方案的组织NESSIE(New European schemes for Signatures，Integrity and Encryption)提交的椭圆曲线混合加密体制，目前其安全性的结论是在一般群模型中，如果对称加密体制是选择明文攻击下语意安全的，而且Hash函数是理想的，则ECIES体制是IND-CCA2安全的，但由于椭圆曲线群具有特殊的性质，而一般群谕示忽略了该特点，故这仅能被看作是理论上的结论。日本电报电话公共公司NTT(Nippon Telegraph and Telephone Public Corporation)实验室构造了一系列可证安全的椭圆曲线加密体制：PSEC-1(PSEC的变种1，PSEC为可证明安全的椭圆曲线加密体制，是Provably Secure EllipticCurve encryption scheme的简写)、PSEC-2(PSEC的变种2)和PSEC-3(PSEC的变种3)，在随机谕示模型下如果椭圆曲线判定迪菲-赫尔曼问题ECDDHP(Elliptic Curve Decision Diffie-Hellman Problem)难解，则PSEC-1是IND-CCA2安全的；如果椭圆曲线计算迪菲-赫尔曼问题(ECCDHP)难解，则带有填充的PSEC-2是IND-CCA2安全的；如果ECCDHP难解且对称加密体制是被动攻击下安全的，则带有对称加密体制的PSEC-2是IND-CCA2安全的；如果椭圆曲线Gap迪菲-赫尔曼问题(ECGDHP)是难解的，则PSEC-3是IND-CCA2安全的。它们均被提交给NESSIE，但由于NTT公司随后基于PSEC提出了一种密钥封装机制--PSEC-KEM(PSEC Key EncapsulationMechanism)，故将PSEC-1和PSEC-2撤回。

上述的ECIES体制、PSEC-2和PSEC-3均是混合加密体制，即体制中包括有对称加密体制，其密文尺寸分别是明文尺寸的三倍、三倍和四倍(假设对称加密体制的明文尺寸和密文尺寸相当，杂凑函数(Hash函数)的输出尺寸和安全参数相当，并采用了椭圆曲线点的压缩技术)；虽然PSEC-1不需要对称加密体制，但其安全性基于ECDDHP难解这一前提，如果ECCDHP可解，则ECDDHP必可解，故该前提不比ECCDHP难解强，基于ECDDHP难解下的安全性不比基于ECCDHP难解下的安全性高。

发明内容

本发明的一个目的是提供一种数据加密的方法，基于伪加运算的具有新的明文嵌入方式，适应性地选择密文下语义安全的椭圆曲线。

本发明的另一个目的是提供一种数据解密的方法，具体是对于采用上述加密方法获得的加密数据进行解密，获得加密前的原始数据。

当发送方向接收方发送数据时，对所要发送的数据依照伪加加密的方法进行加密处理：

首先，随机选取一个整数k，且该整数k满足：1＜k＜n；

然后，计算F(k)，F(k)P，F(k)Q_A；其中：F(k)为k的Hash函数值，F(k)P为椭圆曲线点P的F(k)倍点，F(k)Q_A椭圆曲线点Q_A的F(k)倍点；F(k)为小于n的正整数，F(k)P和F(k)Q_A均为椭圆曲线上的点；

再进一步依照如下公式对被加密数据进行处理：

m’＝m||0^λ’，其中，m为被加密的数据，m’是加密过程中形成的中间数据，λ′为所要添加的0的数量；λ′可以采用多种方式获得，例如：取安全参数的三分之一等；这里的安全参数是指该密码算法自身安全的程度的数量刻画，例如：192比特就是一个比1024比特的RSA更安全的安全参数；

再计算G(k)；如果x(F(k)Q_A)＝m′G(k)，则重新选取整数k，重复上述的步骤；否则开始计算密文的步骤；其中：G(k)为k的Hash函数值；x(F(k)Q_A)为椭圆曲线点F(k)Q_A的x坐标值；

最后，依照如下公式计算密文C：

C＝(C₁，C₂)＝(F(k)P，F(k)Q_A+(m′G(k)，H(m′G(k))k))；

其中，密文C具有二个元素C₁和C₂；C₁＝F(k)P；C₂＝F(k)Q_A+F(k)Q_A+(m′G(k)，H(m′G(k))k)；H(m′G(k))为m′G(k)的Hash函数值；

如果C₂的x坐标属于集合{m′G(k)，x(F(k)Q_A)}，则重新选取整数k，重复上述的步骤；否则输出密文C。

为了使接收加密数据的一方在接收到采用上述加密放法进行加密的数据以后，能够对加密数据进行还原，本发明还提供相应的解密方法，对于所述的密文C，具体的解密步骤如下：

首先，计算Q′＝d_AC₁，如果x(Q′)＝x(C₂)，则拒绝接收密文数据；其中，Q′是椭圆曲线点，d_A是解密方的私钥数据，x(Q′)、x(C₂)分别为Q′和C₂的x坐标；

再计算(M，r)＝C₂-Q′，如果M＝x(C₂)或x(Q′)，则拒绝接收密文数据；其中，M、r分别是仿射平面上一个点的x坐标和y坐标；

进一步计算f＝H(M)r；其中，H(M)是M的Hash函数值；如果F(f)P＝C₁，且M的后λ′比特值为0，则接收的明文m为M的前λ-λ′比特；否则拒绝接收；其中，F(f)P为椭圆曲线点P的F(f)倍点；λ′为加密过程中所添加的0的数量；λ为安全参数，该参数基本上可以看作是上述M的长度。

本发明充分利用了伪加的特点，得到了一个具有新的明文嵌入方法，并得到在适应性选择密文攻击下语义安全的加密体制，该特点也是其与传统椭圆曲线密码体制最大的区别。本发明给出了一种非常简洁的明文嵌入方式，并可以在解密时验证密文的合法性，以此提供了更高级别的数据安全性。本发明对于数据的加密和解密相比于现有的基于椭圆曲线的加密、解密处理在适应性选择密文攻击下，其语义更加安全。

具体实施方式

以下结合具体的实施例对本发明作进一步的详细说明：

在给出具体加密方案之前，首先对伪加运算给出描述：仿射平面F_P ²上，x坐标不同的两个点可以唯一地确定该平面上的维尔斯特拉斯(Weierstrass)方程Y²＝X³+a₄X+a₆，其中X，Y是变量，a₄、a₆是域F_p中的元素，p是一个大素数。如果其所确定的三次曲线是椭圆曲线的话，则它们的加法点的坐标完全由它们自身所决定。

本发明利用该性质，定义了一种新的运算：伪加。

设P₁＝(x₁，y₁)，P₂＝(x₂，y₂)是仿射平面F_P ²上两个点，而且x₁≠x₂，如下定义伪加运算：

1、P₁+P₂＝P₃＝(x₃，y₃)其中x₃，y₃满足下式：

$x_3={\left(\frac{y_2-y_1}{x_2-x_1}\right)}^2-x_1-x_2,y_3=\frac{y_2-y_1}{x_2-x_1}(x_1-x_3)-y_1$

2、-P₁＝(x₁，-y₁)

3、P₁-P₂＝P₁+(-P₂)

设P，Q是仿射平面F_P ²上的两个点，而且x坐标不相同，则P和Q唯一确定一条仿射曲线E(P，Q)：Y²＝X³+aX+b，使得P，Q是该仿射曲线上的点，其中a，b为域F_p的元素，由x坐标不同的点P和Q唯一确定，F_P是p个元素的有限域，p是一个素数，而P是一个点，它的两个坐标是F_P中的元素。在此，对于曲线E(P，Q)上的所有非奇异点补充定义倍点运算，该运算公式与椭圆曲线的倍点运算公式完全相同：

设曲线E(P，Q)：Y²＝X³+aX+b，P₁＝(x₁，y₁)是该曲线上的非奇异点，则2P＝(x₃，y₃)，其中：

x₃＝λ²-2x₁

y₃＝λ(x₁-x₃)-y₁

$\mathrm{\λ}=\frac{{3x}_1^2+a}{2y_1}$

如果4a³+27b²≠0modp，则该曲线是椭圆曲线，如上定义的伪加运算“+”即为椭圆曲线点的加法，椭圆曲线上的所有有理点在“+”运算和倍点运算下构成群，无穷远点0是其零点，“-”是“+”的逆运算；若4a³+27b²＝0modp，则该曲线是奇异的，而且仅有一个奇异点，其上的所有非奇异点在“+”运算和倍点运算下也构成一个群，无穷远点0是其零点，“-”是“+”的逆运算。

由运算性质可知：当且仅当P，Q全为E(P，Q)上的非奇异点，且R(＝P+Q)，P、Q的x坐标两两不同时，可在不知道P，Q所确定的曲线E(PQ的具体方程的情况下，由R(＝P+Q)和P求得Q(＝R-P)。注意到R，P，Q的x坐标两两不同蕴含了P，Q全为非奇异点，所以P，Q全为非奇异点的概率至少为1-6/(p-1)，其中p是一个大素数。也就是说：两个x坐标不相同的点P，Q，记R＝P+Q，在1-6/(p-1)概率下可由其中的任意两点计算出另一点。本发明充分利用了这个特点，得到了一个具有新的明文嵌入方法，并得到在适应性选择密文攻击下语义安全的加密体制，该特点也是其与传统椭圆曲线密码体制最大的区别。

设E：Y²＝X³+aX+b是有限域F_p上的椭圆曲线，E(F_p)是指E的所有F_p有理点和0组成的群。对于E(F_p)中的任意一点P，存在最小的整数n，使得nP＝0，称n为点P的阶，则点P可以生成一个n阶循环群。椭圆曲线公钥密码体制绝大多数都构建在阶为大素数的点生成的循环群上，称该点为基点。以下若不做特殊说明，则一律用大写字母表示曲线上的点，小写字母表示有限域上的元素，x(P)，y(P)表示点P的x坐标和y坐标，相异点间的加法为上述的伪加，倍点运算为椭圆曲线上定义的倍点运算。

设系统参数为(p，a，b，P，n)，其中p是一个大素数，由所要求的安全强度，即安全参数λ所确定；a，b是有限域F_p中的元素，其决定一条椭圆曲线E：Y²＝X³+aX+b。P是E的F_p有理点，其阶为n，n是一个大素数且和p的尺寸相当。每个用户A拥有自己的用户参数(SK_a，PK_a)＝(d_a，Q_a)，其中Q_a＝d_aP，d_a为小于n的正整数，d_a和Q_a分别称为用户A的私钥和公钥，公钥是公开的，可以被任何人知晓，而私钥是私有的，仅由用户A自己知道。H(.)、F(.)、G(.)均是{0，1}^λ→{0，1}^λ的Hash函数，λ′是任意整数满足1/2^λ′是λ的可忽略函数，在此不妨令λ′＝λ/4。在体制的实现中，为了减少数据越界的可能性，强制令各Hash函数值的最高8比特为0。

如果用户B想发送消息m∈{0，1}^λ-λ′给用户A，则用户B进行以下的加密操作：

首先，随机选取一个整数k，1＜k＜n；再计算k的Hash函数值F(k)，椭圆曲线点P的F(k)倍点F(k)P记为C₁，椭圆曲线点Q_a的F(k)倍点F(k)Q_a；然后在m后添加λ′个0得到m′，即m′＝m||0^λ′；再计算k的Hash函数值G(k)，若F(k)Q_a的x坐标值x(F(k)Q_a)＝m′G(k)，则返回重新选取整数k；最后，计算密文C＝(C₁，C₂)＝(C₁，F(k)Q_a+(m′G(k)，H(m′G(k))k)，若仿射平面点C₂的x坐标属于集合{m′G(k)，x(F(k)Q_a)}，则返回重新选取整数k；否则，输出密文C。

在用户A接收到用户B法送的密文C后，进行以下的解密操作来恢复明文m：

1、首先，计算椭圆曲线点C₁的d_a倍点d_aC₁记为Q′，若x(Q′)＝x(C₂)则拒绝接收；

2、再计算仿射平面上的点C₂-Q′记为(M，r)，M，r均为有限域F_p中的元素，若M＝x(C₂)或x(Q′)，则拒绝接收；

3、进一步计算H(M)r记为f；

4、若椭圆曲线点P的F(f)倍点F(f)P为椭圆曲线点C₁且MG(f)的后λ′比特为0，则接收明文m为MG(f)的前λ-λ′比特；否则拒绝接收。

以下，是采用本发明对数据进行加密而获得高安全性的数学证明：

假设椭圆曲线群的阶近似为p，并有一半的m使得m³+am+b是模p的二次剩余，则有以下结论说明在加密过程中返回1的概率很小。

引理1.对于随机选取的k和m，x(kQ_a)＝m的概率至多为2/p。

引理2.记R＝kP+(m，Hash(m)k)，其中，x(kP)≠m，则x(R)∈{m，x(kP)}的概率是可忽略的。

证明假设kP＝(c，d)，则d²＝c³+ac+b，c，d完全由k决定。以下将Hash(.)简记为h(.)。若x(R)＝m，由伪加公式得：

$m={\left(\frac{h\left(m\right)\⊕k-d}{m-c}\right)}^2-m-c$

利用关系式d²＝c³+ac+b可以将上式中的d替换掉，得到下式：

(h(m)k)⁴+(h(m)k)²(6m²c-4m³+2ac+2b)-4(h(m)k)(c³+ac+b)

+4m⁶-12m⁵c-9m²c²-4m³(ac+b)+6m²(ac+b)+a²c²+b²+2abc＝0

如果对于给定的k，上式成立的概率是不可忽略的，则意味着Hash函数h(.)以不可忽略的概率满足上式，在k固定的条件下，对于满足上式的Hash函数值e，把m当做未知数，通过求解六次方程便可以得到e的原像，即若对于给定的k，上式成立的概率是不可忽略的，那么Hash函数h(.)不满足单向性的要求，所以对于任意的k，上式成立的概率均是可以忽略的，则x(R)＝m的概率是可忽略的。若x(R)＝c，同理可得：

(h(m)k)²+c³+ac+b-m³-2m²c+3mc²)²＝4(h(m)k)²(c³+ac+b)

因为Hash函数h(.)是单向的，所以上式成立的概率也是可忽略的。由上知x(R)∈{m，x(kP)}的概率是可忽略的。

上述引理说明：加密过程返回1的概率是可忽略的，而加密、解密均只需要两次椭圆曲线点的倍乘和一次伪加，故可以认为：该本发明所采用的加密方法是有效的，其合理性是显然的。参见IEEE P1363标准，如果使用点的压缩技术，则该体制产生的密文有三倍的明文扩张，即密文尺寸是明文尺寸的三倍。

基于两个相异点的伪加不依赖于曲线本身，上述方法对ElGamal加密体制中的明文嵌入方式作了改变，即将m嵌入到点(m′G(k），H(m′G(k))k))，而不是将其嵌入到系统参数所确定的椭圆曲线上的点。这使得明文嵌入非常自然、简单。除此之外，该体制还具有以下几个特点：它通过解密过程中的第4步可以验证密文的合法性，这使得伪造合法的密文变得非常困难(除非通过选择明文)；它使用了不同的椭圆曲线群来进行运算。即除了系统参数所确定的椭圆曲线外，还有一条由F(k)Q_a和(m′G(k)，H(m′G(k)k)确定的曲线，该曲线是随m和k而变化的，除非知道用户A的私钥，否则不可能知道当前运算所在的椭圆曲线群。

上述加密体制的加密时间复杂度为2次标量乘法，与ElGamal体制的效率相当；带验证的解密的时间复杂度为2次标量乘法，比ElGamal体制多一次标量乘法。若不带验证，则效率相当。如果采用点的压缩技术，其有3倍的明文扩张。为描述方便起见，这里仅给出了基域特征为大素数下的体制，当特征为2时，伪加以及体制的描述是极其类似的。

该加密体制作为ElGamal体制的变形，其安全性基于椭圆曲线计算迪菲-赫尔曼问题(ECCDHP)。它给出了一种非常简洁的明文嵌入方式，并可以验证密文的合法性，以此提供了更高级别的安全性。在随机谕示模型(random oracle model)下，证明了该加密体制是适应性选择密文下语义安全的(IND-CCA2)。

在随机谕示模型(random oracle model)下，证明了如果椭圆曲线计算迪菲-赫尔曼问题(ECCDHP)难解，则该加密体制是适应性选择密文攻击下语义安全的(IND-CCA2)，由于该证明是基于ECCDHP的，故其安全性可能高于PSEC-1。它不是一种混合加密体制，其运算仅包括椭圆曲线点的倍乘、伪加运算和杂凑函数，不需要应用对称加密体制。该加密体制利用全新的伪加运算，将明文嵌入到仿射平面中点的x坐标，给出了一种非常简洁的明文嵌入方式，并可以验证密文的合法性。

在该密码体制的实现中，首先面临的是系统参数(p，a，b，P，n)的选择问题。从安全角度考虑，为抵抗一些已知的攻击算法，可以对系统参数进行特殊的限制：

1.n＞2¹⁶⁰且 $n>4\sqrt{p};$

2.椭圆曲线是非超奇异的(non-supersingular)，即p不整除p+1-#E(F_p)；

3.基点P的阶n不整除p^k-1(1≤k≤C)，实际中常取C＝20；

4.椭圆曲线是非异常的(non-anomalous)，即#E(F_p)≠p。

该实施方式取基域F_p为标准IEEEP1363所建议的有限域，Hash函数G(.)，F(.)和H(.)均为SHA1并强制其Hash函数值的最高8比特为0，大素数p的比特数为λ。随机选取椭圆曲线的参数a，b，利用SEA算法计算它的阶，然后把满足以上要求的椭圆曲线作为系统参数。在本发明的具体实施中，需要椭圆曲线点加算法、伪加算法、椭圆曲线倍点算法以及椭圆曲线点的标量乘法，以下逐一给出各算法。

由于伪加算法与椭圆曲线x坐标相异的两个点的点加算法相同，故不单独列出来。

本发明一个具体的实施例中，密钥生成过程如下：

1、随机选择一个整数d_A，1＜d_A＜n，采用NAF编码和标量乘法算法计算Q_A＝d_AP；

2、将d_A作为私钥，Q_A作为公钥。

具体的加密步骤是：将消息数据m根据3λ/4进行分组m₁m₂...m_d，一次对一个分组进行加密，例如：将一个分组的消息m加密后传送。

2.1找到公开密钥Q_A；

2.2选择一个随机数k，1＜k＜n；

2.3计算f＝SHA1(k)；

2.4采用NAF编码和标量乘法算法计算fP记为C₁；

2.5将m转化为域中元素m’＝m||0^λ/4；

2.6采用NAF编码和标量乘法算法计fQ_A记为Q’，若x(Q’)等于m’f则执行2.2；

2.7利用点加算法计算Q’+(m’f，SHA1(m’f)k)记为C₂，若x(C₂)，x(Q’)和m’f两两不同，则发送加密数据(C₁，C₂)，否则，返回2.2。

解密过程：收到加密数据(C₁，C₂)后，实施如下解密过程：

3.1采用NAF编码和标量乘法算法计算点Q’＝d_AC₁，若x(Q’)等于x(C₂)则拒绝接收；

3.2采用点加算法计算(M，r)＝C₂-Q’，若M等于x(C₂)或x(Q’)则拒绝接收；

3.3计算k＝SHA1(M)r；

3.4计算f＝SHA1(k)；

3.5计算m’＝Mf

3.6采用NAF编码和标量乘法算法计算，若fP等于C₁且m’的后λ/4比特为0，则接收明文m为m’的前3/4比特；否则拒绝接收。

上述的点加算法如下：

当对于一个数据进行加密时，对于输入的椭圆曲线y²＝x³+ax+b，和该曲线上的点P₀＝(x₀，y₀)和点P₁＝(x₁，y₁)；

A1、如果P₀＝0，则输出点P₂即为P₁

A2、如果P₁＝0，则输出点P₂即为P₀

A3、如果x₀≠x₁

A3.1计算λ←(y₀-y₁)/(x₀-x₁)mod p；是指将(y0-y1)/(x0-x1)mod p赋值给λ；

A3.2执行第A7步

A4、如果y₀≠y₁，输出P₂←O

A5、如果y₀＝0，输出P₂←O

A6、计算λ←(3x²+a)/(2y₁)mod p

A7、计算x₂←λ²-x₀-x₁ mod p

A8、计算y₂←(x₁-x₂)λ-y₁ mod p

A9、输出P₂←(x₂，y₂)

注：若要减点P＝(x，y)，只要加点-P＝(x，-y)。

上述的椭圆曲线上倍点算法如下：

输入：椭圆曲线E，E上点P(X₁，Y₁，Z₁)，P≠O

输出：(X₃，，Y₃，Z₃)＝2P

B1、计算λ₁←3X₁ ²+aZ₁ ⁴；

B2、计算Z₃←2Y₁Z₁

B3、计算λ₂，←4X₁Y₁ ²；

B4、计算X₃←λ₁ ²-2λ₂；

B5、计算λ₃←8Y₁ ⁴；

B6、计算Y₃←λ₁(λ₂-X₃)-λ₃；

B7、输出(X₃，Y₃，Z₃)

上述的NAF编码算法如下：

输入：整数 $k={\mathrm{\Σ}}_{j=0}^{l-1}{k}_j{2}^j,k_j\∈\left\{\mathrm{0,1}\right\}.$

输出：NAF $k={\mathrm{\Σ}}_{i=0}^l{s}_i{2}^i,s_i\∈\{-\mathrm{1,0,1}\}$

C1、c₀←0，k_l←0，k_l+1←0；

C2、j←0

C3.如果j≠l+1

C3.1计算

C3.2计算s_j←k_j+c_j-2c_j+1

C3.3计算j＝j+1

C3.4转入第3步

C4、输出(s_ls_l-1，...，s₁，s₀)₂

上述的NAF标量乘法算法如下：

输入：椭圆曲线上一点P，整数k的NAF(s_ls_l-1，...，s₁，s₀)₂，s_l＝1；

输出：Q＝kP；

D1、Q←O；

D2、j←l；

D3、如果j≠-1

D3.1计算Q←2Q

D3.2如果s_j＝1计算Q←Q+P

D3.3如果s_j＝-1计算Q←Q+P

D3.4计算j＝j-1

D3.5转入第3步

D4、输出Q.

以上各算法给出了本发明所描述的椭圆曲线加密体制的具体实施方式，以下给出在该方式下运行获得的一组试验数据，其中各个数据均以十六进制述表达。

系统参数：

λ：192

p：fffffffffffffffffffffffffffffffeffffffffffffffff

a：fffffffffffffffffffffffffffffffefffffffffffffffc

b：02d5134233c1f7f4f50706f02882d85e767294c7230612c2

P.x：df00000129200001db000001ffbe800169ea40011de3ec01

P.y：46b19ab9a84501afc6c94ce6fb9ae8f21a93fedb9ec6881f

n：fffffffffffffffffffffffe75432f994b9b16ef54c39393

d_A：83cedad356f4f6cf573ff873b789add938df2ec7d5d2753b

Q_A.x：1f18bcacb74087835ae629a87968f0d57adb39110ec1fd70

Q_A.Y：53b96505a207de2442510c7f01c80c4cffcdaf40099fa0a1加密时：

m：00000000000000000313233343536373839

m’：00000000000000000313233343536373839000000000000

k：9296decb12fc6d896ffd58ade5b03a3f1e235d0556e3f57d

f：09cf3ae17aad817332dd1e4fe8d41c50d8b7ee7152ac5b6

C₁.x：362b32f9f9b3c21c1df13631ea7155f23d04d4853ce048db

C₁.y：f7cbaa643bccce14f252660b0104542f86a8a5f89f7c1c5

fQ_A.x：fa529d8354bbb6bd3289b906f1b3337914628f6cf75a354c

fQ_A.y：91f142b803c9ba20ece5012f02bc9511cb4412b881bbbd7a

m’f：09cf3ae17aad817331ce3d7cab877f235b27ee7152ac5b6

SHA1(m’f)k：

92d183184e2365cc9b2673ddc3f49bf2a3c57cb6b5c3ea36

C₂.x：6edaa4c686f938464514b379720f10dd4ba8a353e1a9e6de

C₂.y：2f47f3be8875cc0417fbfacf87993ea4893595ddf610b43解密后：

Q′.x：fa529d8354bbb6bd3289b906f1b3337914628f6cf75a354c

Q′.y：91f142b803c9ba20ece5012f02bc9511cb4412b881bbbd7a

M：09cf3ae17aad817331ce3d7cab877f235b27ee7152ac5b6

r：92d183184e2365cc9b2673ddc3f49bf2a3c57cb6b5c3ea36

SHA1(M)：0475dd35cdf0845f4db2b702644a1cdbde621b3e3201f4b

k：9296decb12fc6d896ffd58ade5b03a3f1e235d0556e3f57d

f＝SHA1(k)：09cf3ae17aad817332dd1e4fe8d41c50d8b7ee7152ac5b6

m’f：00000000000000000313233343536373839000000000000

fP.x：362b32f9f9b3c21c1df13631ea7155f23d04d4853ce048db

fP.y：f7cbaa643bccce14f252660b0104542f86a8a5f89f7c1c5

m：00000000000000000313233343536373839；

在使用INTEL公司PentiumIV 1.7G微处理器、256M内存储器的计算机，并在WINDOWS98操作系统的环境下，用ANSIC编程语言实现特征为p以及特征为2的的有限域上的体制，其中p＝2¹⁹²-2⁶⁴+1，F_2m，m＝193，生成多项式f(x)＝x¹⁹³+x¹⁵+1；实现效率如下表所示：

内容	*Fp	Fp	*F2m	F2m
					密钥生成	1.21	5.43	0.67	2.48
加密	6.70	10.95	3.29	5.43
					ECES 加密	6.76	10.53	3.20	5.26
解密	6.50	11.57	3.12	5.42
					解密(不带验证)	5.26	5.95	2.59	2.45
ECES解密	5.51	5.48	2.62	2.53
					倍乘	1.20	5.32	0.65	2.39

表中的各项指标都是在执行1000次的速度，单位为秒；*栏下的指标是允许的预处理速度。

若F_p上的运算采用汇编语言编写，192比特的点的倍乘速度为1.81秒(1000次)，下表列出了p＝2²⁵⁶下执行1000次的速度，单位为秒：

内容	ANSI C	汇编
			密钥生成	2.25	0.93
加密	18.93	6.35
			解密	18.64	6.35
解密(不带验证)	16.2	5.43

用型号为MCS51的单片机实现的加/解密效率见下表，其中MCS51主要存贮器配置：256B的内部RAM，64KB的外部RAM，64KB的程序区ROM.时钟频率：1M时钟周期/秒(晶振频率：12MHZ)。取F_p，p＝2¹⁹²-2⁶⁴-1和F_2m，m＝193，其生成多项式为x¹⁹³+x¹⁵+1。

功能	Fp(秒/次)	F2m(秒/次)
			密钥生成	4.89	4.34
加密	25.32	20.84
			ECES加密	25.19	20.74
解密(不带验证)	20.43	16.21
			ECES解密	20.42	16.21
解密(带存储)	25.33	20.10
			倍乘(带预存储)	4.77	4.32
倍乘(不带预存储)	19.96	16.4

注：F_p的外部RAM占用1.5K，ROM占用9K程序，6K预存储值；F_2m的外部RAM占用：2K(带预存储)/1.2K(不带预存储)，ROM占用：7K程序，6K预存储值。

以下，给出了该加密体制是在适应性选择密文下语义安全的详细证明。

一、安全的定义

假设U是一个概率算法，则A(x₁，x₂，...；r)表示输入为x₁，x₂，...，随机数为r时算法A的输出；y←A(x₁，x₂，...)表示随机选择r，令y等于A(x₁，x₂，...；r)；若存在r使得A(x₁，x₂，...；r)＝y，则称y是A(x₁，x₂，...)的输出；如果S是一个有限集合，则x←S表示从集合S中依据均匀分布随机地选取x，若a既不是一个集合也不是一个算法，则x←a表示将a的值赋给x。

定义1.公钥加密体制是由算法组成的三元组：PE＝(KG，Enc，Dec)，其中

KG：密钥生成算法，是一个概率算法，输入为安全参数1^λ(λ∈N)，输出为一对公私钥(pk，sk)；

Enc：加密算法，是一个概率算法，输入为公钥pk和明文x∈{0，1}^*，输出为密文y；

Dec：解密算法，是一个确定型算法，输入为私钥sk和密文y，输出为明文x∈{0，1}^*或特殊字符，该字符表示输入的密文不是有效密文，即不存在x∈{0，1}^*使得其密文为y。

对于由密钥生成算法得到的任意的公私钥对(pk，sk)和任意的明文x∈{0，1}^*，若y是Enc_pk(x)的输出，则一定有Dec_sk(y)＝x。因为公钥加密体制需要保证现实传输的信息的安全，所以，以上的三个算法(KG，Enc，Dec)均是以安全参数为尺度的多项式时间算法。

公钥加密体制的安全性的定义可以首先分别考虑攻击者可能的攻击目标(goals)和可能的攻击模型(attack model)，然后通过组合攻击模型和攻击目标给出各种级别的安全性的定义。

依据攻击目标的不同，体制的安全性分析主要考虑单向性(OW，oneway)、语义安全(SS，semantic security)、密文的不可区分性(IND，indistinguishability of encryptions)和非扩展性(non-malleability，NM)。简单的说，单向性就是指由目标密文y求得相应的明文x＝Dec_sk(y)非常困难；语义安全的就是指从目标密文y获得相应明文x的任何信息均是计算不可行的；密文的不可区分性是指已知两个明文和某个明文所对应的一个密文，无法判断该密文相应的明文是哪一个。可以认为密文的不可区分性和语义安全均是单向性概念的提升，它们都涵盖在传统的保密性要求中，单向性是加密体制安全的最低要求，如果体制是密文不可区分的或语义安全的，则该体制一定是单向的，所以本文不讨论任何单向性的性质。非扩展性就是指从目标密文y求得另外一个不同的密文y′，使得其相应的密文x，x′间存在“有意义的联系”(如x′＝x+1)，它提升了现实中的密文防篡改的思想。

攻击模型表述了攻击者所具有的能力，可以分为选择明文攻击(chosen-plaintextattack，CPA)、非适应性选择密文攻击(non-adaptivechosen-ciphertext attack，CCA1)和适应性选择密文攻击(adaptivechosen-ciphertext attack，CCA2)。CPA赋予攻击者自由选择明文并获得相应密文的权利，对于公钥加密体制而言，攻击者知道公钥即具有了选择明文攻击的能力；CCA1的形式化定义是由两位学者Naor和Yung给出的，其中攻击者除了知道公钥外，还可以访问解密谕示(该外部装置是解密算法)，但攻击者只在得到目标密文之前具有访问解密谕示的权利(非适应性是指对解密谕示的访问不依赖于目标密文)，依据其特点，非适应性选择密文攻击也被称为午夜攻击(midnight attack)或午餐攻击(lunchtimeattack，Lunch-breakattack)；CCA2是由两位学者Rackoff和Simon提出的，其中攻击者既知道公钥也可以访问解密谕示，而且其对解密谕示的访问是没有限制的，即使在获得目标密文之后攻击者仍然可以访问解密谕示，但是他不能将目标密文自身作为解密谕示的输入(适应性的是指对解密谕示的访问依赖于目标密文)。

组合上述的攻击目标和攻击模型，可以得到各种不同的安全性的定义，下面仅给出不可区分性的形式化定义，其包括了最高级别的安全性--适应性选择密文下语义安全的IND-CCA2。

根据攻击者U在不同阶段具有不同的输入，可以将其看做两个概率算法(U₁，U₂)，其中U₁和U₂的作用依赖于攻击者的目标。在密文的不可区分性的定义中，算法U₁的输入为pk，输出为(x₀，x₂，s)，前两项是两个相同长度的明文，s是攻击者想要保留的信息；从x₀，x₁中随机选择一个记为x_b，挑战密文y为x_b的密文，算法U₂的输入为(x₀，x₁，s)和挑战密文y它试图输出正确的b。

定义2(IND-CPA，IND-CCA1，IND-CCA2).假设PE＝(KG，Enc，Dec)是一个公钥加密体制，A＝(A₁，A₂)是一个攻击者，H(.)是随机谕示，对于任意的atk∈{cpa，cca1，cca2}和任意的λ∈N，令

${\mathrm{Adv}}_{\mathrm{PE},A}^{\mathrm{ind}-\mathrm{atk}}\left(\mathrm{\λ}\right)=\mathrm{Pr}[\mathrm{Ex}{p}_{\mathrm{PE},A}^{\mathrm{ind}-\mathrm{atk}-1}\left(\mathrm{\λ}\right)=1]-\mathrm{Pr}[E{\mathrm{xp}}_{\mathrm{PE},A}^{\mathrm{ind}-\mathrm{atk}-0}\left(\mathrm{\λ}\right)=1]$

其中取b∈{0，1}，定义实验Exp_PE，A ^ind-atk-d(λ)为

$(\mathrm{pk},\mathrm{sk})\stackrel{R}{\←}\mathrm{KG}\left(\mathrm{\λ}\right);$

$(x_0,x_1,s)\←A_1^{O_1(\·),H(\·)}\left(\mathrm{pk}\right);$

y←Enc_pk(x_b)；

$d\←A_2^{O_2(\·),H(\·)}(x_0,x_1,s,y);$

Return d。

如果atk＝cpa，则O₁(.)＝，O₂(.)＝；如果atk＝cca1，则O₁(.)＝Dec_sk(.)，O₂(.)＝；如果atk＝cca2，则O₁(.)＝De_sk(.)，O₂(.)＝Dec_sk(.)；还要求|x₀|＝|x₁|，算法A₂不能利用解密谕示获得y的明文。如果对于任意多项式时间的攻击者A，均有Exp_PE，A ^ind-atk(·)是可忽略的函数，则称公钥加密体制PE是IND-ATK意义下安全的。

二、安全性分析

从体制本身来看，由于本发明的运算基于不同的椭圆曲线群，而且“+”几乎没有结合律(例如：仿射平面R²上三点P＝(1，2)，Q＝(2，3)，R＝(3，1)，由伪加公式得(P+Q)+R＝(-2，1)+(3，1)＝(-1，-1)，而P+(Q+R)＝(1，2)+(-1，-9)＝(121/4，-1303/8)。)，所以由m的密文得到R(m)的密文是非常困难的，其中R是一个非平凡的关系，即直观上该体制具有非扩展的性质，这是与ElGamal体制的最明显的区别，也是安全性提高的一个原因。Hash函数的使用进一步加强了该体制的安全性。本节将证明该体制是IND-CCA2安全的。为方便起见，以下简记该加密体制为∏。

定理1.在ECCDHP难解的条件下，∏是IND-CCA2安全的。

证明 设∏存在IND-CCA2意义下的攻击者A＝(A₁，A₂)，A访问随机谕示G(.)，H(.)和F(.)所得的相应记录分别被称为G-表、H-表和F-表，记做τ_G＝{(g_i，G_i)}，τ_H＝{(h_i，H_i)}，τ_F＝{(f_i，F_i)}其长度(访问的次数)分别用q_G，q_H，q_F表示。则可以如下构造ECCDHP的求解算法B。设B的输入为P，Q＝aP，Y＝bP，其目的是计算R＝abP。

B将P，Q作为A₁的输入调用A₁，由于A₁可以访问随机谕示和解密谕示，所以B需要模拟随机谕示和解密谕示。设A₁向随机谕示G(.)查询g，若g在查询记录中，则将记录中相应的输出值作为对A的应答；否则，随机选取其值域中的数作为对A₁的应答，同时将k和该随机数作为一对输入、输出添加在记录中。B模拟随机谕示H(.)和F(.)的动作与模拟G(.)的方式相同。设A₁向解密谕示访问y＝(C₁，C₂)，如果分别在G-表、F-表和H-表存在(g_i，G_i)，(f₁，F₁)，(h_j，H_j)，满足f₁＝g_i，F₁P＝C₁，C₂＝F₁Q+(h_j，H_jf₁)，计算M＝h_jG_i，若M的低λ′比特为0，则输出M的高λ-λ′比特作为明文输出，其它情况均输出空串。在A₁中止时，不妨设A₁的输出为(m₀，m₁，s)。

B随机选择C₂ ^*∈{0，1}^2λ，令y^*＝(C₁ ^*＝Y，C₂ ^*)，B将(m₀，m₁，s，y^*)作为A₂的输入，调用A₂，其模拟解密谕示和随机谕示的过程均同上。

在A中止后，B从H-表中随机挑选(h，H)，如果存在t使得R＝C₂ ^*-(h，t)∈E，则输出R；否则，重新从H-表中选取(h，H)；若在H-表中不存在上述关系式，则随机输出E的点作为R。

以下记F*＝log_PY，(s*，t*)＝C₂ ^*-F*Q，h*＝s*，k*＝t*H(h*)。利用E的方程和伪加公式，可知C₂ ^*-(h，t)∈E是关于t的六次方程，其至多有六个解，令AskH表示事件：A向H(.)访问了h*，则B输出正确的ECDH解的概率 ${\mathrm{\ϵ}}^{\′}\≥\frac{\mathrm{Pr}\left[\mathrm{AskH}\right]}{{6q}_H}.$

为保证A的正确调用，首先B必须正确模拟解密谕示，其次B还要保证目标密文y^*合法。Bad表示解密谕示的应答有误或y^*不是合法密文。设A成功的概率为(1+ε)/2，如果B正确地调用了A，因为y^*与m₀，m₁完全无关，故A输出正确结果的概率为1/2，则

(1+ε)/2≤1/2(1-Pr[Bad])+Pr[Bad]，

可得Pr[Bad]≥ε。显然

Pr[AskH]≥Pr[AskH∧Bad]＝Pr[Bad]-Pr[Bad∧﹁AskH]≥ε-Pr[Bad|﹁AskH]

在没有向H(.)访问h*的前提下，仅当A向G(.)或F(.)访问了k*(记为AskK)或解密谕示的应答有误(记为DBad)时，Bad才可能发生，即

Pr[Bad|﹁AskH]≤Pr[AskK|﹁AskH]+Pr[DBad|﹁AskH∧﹁AskK]

如果h*没有被访问，则H(h*)完全随机，所以k*＝t*H(h*)完全随机，故k*被访问的概率不大于(q_G+q_F)/2^λ，即

$\mathrm{Pr}\left[\mathrm{AskK}\right|\⫬\mathrm{AskH}]\≤\frac{q_G+q_F}{2^{\mathrm{\λ}}}.$

以下的讨论均基于k*，h*没有被访问的前提条件。

假设A向解密谕示的输入为y(C₁，C₁)，记F＝logPC₁，(s，t)＝C₂-FQ，k＝H(s)t，h＝s，Pr′[.]＝Pr[·|﹁AskH∧﹁AskK]。

如果h，k均被查询，则输出结果一定正确；如果h被查询但k没有向G(.)或F(.)查询，则输出结果为空串，如果结果不真，那么y一定是合法密文，以下分情况讨论：因为h被查询，所以k确定，而k*随机，故k＝k*的概率不大于2^-λ，在k＝k*的条件下y是合法密文的概率至多为1，则k＝k*时，模拟应答出错的概率不大于2^-λ；如果k≠k*且k没有向G(.)访问，y是合法密文意味着sG(k)的低λ′比特为0，因为k≠k*且k没有向G(.)访问，所以y是合法密文的概率不大于2^-λ′；如果k≠k*且k没有向F(.)访问，y是合法密文意味着F(k)＝log_pC₁，因为k≠k*且k没有向F(.)访问，所以y是合法密文的概率不大于2^-λ；如果h没有被查询，则输出结果为空串，如果结果不真，那么y一定是合法密文，即F(k)＝log_PC₁且sG(k)的低λ′比特为0，如果h＝h*，因为h*也没有被查询，所以H(h)完全随机；如果k≠k*，因为h没有被查询，所以H(h)完全随机；故在h没有被查询的条件下，H(h)是完全随机的，则k＝tH(h)是完全随机的，故F(k)＝log_PC₁的概率不大于2^-2，sG(k)的低λ′比特为0的概率不大于2^-λ′则在h没有被访问的条件下，模拟应答出错的概率不大于2^-λ。

综合以上分析，可知Pr[DBad|﹁AskK∧﹁AskH]≤3q_D/2^λ+q_D/2^λ，则

$\mathrm{Pr}\left[\mathrm{Bad}\right|\⫬\mathrm{AskH}]\≤\frac{q_G+q_F+3q_D}{2^{\mathrm{\λ}}}+\frac{q_D}{2^{{\mathrm{\λ}}^{\′}}}$

$\mathrm{Pr}\left[\mathrm{AskH}\right]\≥\mathrm{\ϵ}-\mathrm{Pr}\left[\mathrm{Bad}\right|\⫬\mathrm{AskH}]\≥\mathrm{\ϵ}-(\frac{q_G+q_F+3q_D}{2^{\mathrm{\λ}}}+\frac{q_D}{2^{{\mathrm{\λ}}^{\′}}})$

故B输出正确的ECDH解的概率

${\mathrm{\ϵ}}^{\′}\≥\frac{\mathrm{Pr}\left[\mathrm{AskH}\right]}{{6q}_H}\≥\frac{\mathrm{\ϵ}}{{6q}_H}-\frac{q_G+q_F+3q_D}{{6q}_H{2}^{\mathrm{\λ}}}-\frac{q_D}{{6q}_H{2}^{{\mathrm{\λ}}^{\′}}}$

从上式知，如果ε是不可忽略的，则ε′一定是不可忽略的，设A的运行时间为t，则B的运行时间t′＝t+q_Ht_f，其中t_f表示在F_p上求解六次方程所需的时间，显然如果A是多项式时间的，则B一定也是多项式时间的，由上知若∏不是IND-CCA2安全的，则ECCDHP可解，这是矛盾的，故在ECCDHP难解的条件下，∏是IND-CCA2安全的。

最后应说明的是：以上实施例仅用以说明本发明而并非限制本发明所描述的技术方案；因此，尽管本说明书参照上述的各个实施例对本发明已进行了详细的说明，但是，本领域的普通技术人员应当理解，仍然可以对本发明进行修改或者等同替换；而一切不脱离本发明的精神和范围的技术方案及其改进，其均应涵盖在本发明的权利要求范围当中。

Claims (2)

1、一种数据加密的方法，其特征在于：当发送方向接收方发送数据时，对所要发送的数据依照伪加加密的方法进行加密处理；加密的处理步骤如下：

步骤10：随机选取一个整数k，且该整数k满足：1＜k＜n；其中，n是椭圆曲线基点的阶数；

步骤11：计算F(k)，F(k)P，F(k)Q_A；其中：

F(k)为k的Hash函数值，F(k)P为椭圆曲线点P的F(k)倍点，F(k)Q_A为椭圆曲线点Q_A的F(k)倍点；

F(k)为小于n的正整数，F(k)P和F(k)Q_A均为椭圆曲线上的点；

步骤12：依照如下公式对被加密数据进行处理：

m’＝m||0^λ’，其中，

m为被加密的数据，m’是加密过程中的数据，λ′为所要添加的0的数量；

步骤13：计算G(k)；如果x(F(k)Q_A)＝m′G(k)，则执行步骤10；否则执行步骤14；

其中：G(k)为k的Hash函数值；

x(F(k)Q_A)为是椭圆曲线点F(k)Q_A的x坐标值；

步骤14：依照如下公式计算密文C：

C＝(C₁，C₂)＝(F(k)P，F(k)Q_A+(m′G(k)，H(m′G(k))k))；

其中，C为密文数据集合，C₁和C₂为C的二个元素；并且，

C₁＝F(k)P；

C₂＝F(k)Q_A+F(k)Q_A+(m′G(k)，H(m′G(k))k)；

H(m′G(k))为m′G(k)的Hash函数值；

步骤15：如果C₂的x坐标属于集合{m′G(k)，x(F(k)Q_A)}，则执行步骤10；否则输出密文C。

2、一种解密依权利要求1所述方法加密的数据的方法，其特征在于：当接收方接收到发送方加密的密文数据时，依照如下的方法对其进行解密，将加密数据还原数据；所述解密的步骤如下：

步骤20：计算Q′＝d_AC₁，如果x(Q′)＝x(C₂)，则拒绝接收密文数据；其中，

Q′是椭圆曲线点，d_A是解密方的私钥数据，x(Q′)、x(C₂)分别为Q′和C₂的X坐标；

步骤21：计算(M，r)＝C₂-Q′，如果M＝x(C₂)或x(Q′)，则拒绝接收密文数据；其中，M、r分别是仿射平面上一个点的x坐标和y坐标；

步骤22：计算f＝H(M)r；其中，H(M)是M的Hash函数值；

步骤23：如果F(f)P＝C₁，且M的后λ′比特值为0，则接收的明文m为M的前λ-λ′比特；否则拒绝接收；

其中，F(f)P为椭圆曲线点P的F(f)倍点；

λ′为加密过程中所添加的0的数量；

λ为安全参数。