椭圆曲线加密解密方法和装置

暂无

技术领域\n本发明涉及数据加密解密，是利用椭圆曲线离散对数问题的加密 方法。\n背景技术\n密码系统分为对称密码系统和非对称密码系统。\n对称密码有时也叫传统密码算法，就是加密密钥能够从解密密要 中推算出来，反之也成立。在大多数算法中，加/解密密钥是相同的。 这些算法也叫秘密密钥算法或单密钥算法，它要求发送者和接收者在 安全通信之前，协商一个密钥。对称密码的安全性依赖于密钥，泄密 密钥就意味着任何人都能对消息进行加/解密。所以，虽然对称密码的 速度很快，但是如何将密钥安全分发给合法使用者却是一个问题。\n在专利“密码设备和方法”(“CRYPTOGRAPHIC APPARATUS METHOD”， 专利号：US4200770)中给出了一个可以在公开信道中交换密钥的方法 和设备，这个方法称为公钥密钥交换或称为Diffie-Hellman密钥交换 方法。该专利使得通信双方使用一个模幂函数协商和传递他们的秘密 信息。攻击者要想获得传递的秘密信息，必须解决离散对数问题。如 果使用的参数足够大，解离散对数问题是个难解的问题。\n公钥密码，又称非对称密码，则可以有效的解决上述问题。公钥 密码与只使用一个密钥的对称密码不同，公钥密码学是非对称的，它 使用两个独立但有着某种数学联系的密钥：公钥和私钥。这样通信中 的接收者保密其私钥，公开其公钥。这样通信双方A和B在通信时， 如果发送者A需要将明文以密文的形式发送给B，则可以首先获取B 公开的公钥，使用B的公钥加密信息，接收者B使用只有自己知道的 私钥解密密文。因为只有B拥有其私钥，所以A可以确定只有B可以 读取明文。\n专利“密码通信系统和方法”(“CRYPTOGRAPHIC COMMUNICATIONS SYSTEM AND METHOD”，专利号：US4405829)提出了Rivest，Shamir 和Adleman发明的一种公钥密码方法——RSA。RSA公钥密码方法的安 全性基于大整数因子分解问题的难解性。但随着目前对安全性要求的 不断提高，对RSA密钥长度的要求也越来也高。\n1984年，Taher ElGamal在其博士论文中提出了新的公钥加密机 制。在这个机制中，接收者使用模幂函数隐藏私钥x，计算y＝gx mod p，并将公钥y公开。具体加密算法如下：\n1、预处理过程：获得系统所需要的各项参数\n1.1：确定有限域GF(p)，即确定素数p；\n1.2：确定生成元g；\n1.3：选取随机数x，使得1≤x≤p-1，将x作为解密密钥，即 私钥；\n1.4：计算y＝gx，y作为加密密钥，即公钥；\n1.6：公开g，p，和公钥y。\n2、加密过程：\n2.1：加密方获取解密方的公开参数g，p，和公钥y；\n2.2：生成随机数k，其中1≤k≤p-1，使用公钥y，利用模幂 函数计算gk和yk；\n2.3：对于明文m计算：m yk，形成密文c＝(gk，m yk)；\n2.4：加密方将密文c发送给解密方。\n3、解密过程：\n3.1：解密方接收到密文c＝(P，Q)；\n3.2：利用私钥x，计算Px＝gk x＝(gx)k＝yk；\n3.3：计算Q*(Px)-1＝m yr(yk)-1＝m；\n4、结束。\n1985年Neal Koblitz和Victor Miller分别提出将椭圆曲线用 于公钥密码系统，并用椭圆曲线实现了已存在的公钥密码算法。基于 椭圆曲线离散对数问题难解性的密码算法被称为椭圆曲线密码算法 (Elliptic Curve Cryptography简称ECC)，成为被国际密码界所广 泛接受的公钥密码算法。\n随后，上文提及的ElGamal加密机制被移植到椭圆曲线上，基于 椭圆曲线离散对数问题难解性的ElGamal加密算法如下：\n1、预处理过程：获得椭圆曲线加密所需要的各项参数\n1.1：确定有限域GF(p)，即确定素域p；\n1.2：选取曲线参数a、b，确定椭圆曲线方程E：y2＝x3+ax+b(mod p)；\n1.3：计算曲线的阶N，选取曲线的基点G；\n1.4：选取随机数x，使得1≤x≤N-1，将x作为解密密钥，即 私钥；\n1.5：计算Y＝xG，Y作为加密密钥，即公钥；\n1.6：公开曲线E，生成元G和公钥Y。\n2、加密过程：\n2.1：加密方获取解密方的曲线E，生成元G和公钥Y；\n2.2：加密方获取适当长度的明文m，并将其嵌入曲线E，得到满 足曲线E的点Pm；\n2.3：生成随机数k，其中1≤k≤N-1，使用公钥Y，利用椭圆 曲线点乘和点加公式计算rG和Pm+kY，形成密文c＝(kG，Pm+kY)；\n2.4：加密方将密文c发送给解密方。\n3、解密过程：\n3.1：解密方接收到密文c＝(P，Q)；\n3.2：利用私钥x，计算xP＝x kG＝r(x G)＝kY；\n3.3：计算Q-xP＝Pm+kY-x kG＝Pm；\n3.4：由Pm计算得到明文m；\n4、结束。\n在上述过程中，由于椭圆曲线上的点均要满足椭圆曲线方程E： y2＝x3+ax+b(mod p)，而明文m是随机的，因此，将m本身作为点的横 坐标x时，方程可能无法求解出点的纵坐标y，从而必须要对m进行 明文嵌入。通常采用的做法是：在m后增加若干位一起作为点的横坐 标，从而进行明文嵌入。填充位越多，能够成功进行明文嵌入的可能 性就越大，但此种方法仍然是一种概率性算法，可能出现无法对某种 明文加密的情况，因此，解决这一问题显然非常重要。\nMenezes和Vanstone提出的基于椭圆曲线的公钥密码算法——MV 加密方法，克服了上述在ElGamal加密机制中的缺陷。其具体的加密 步骤描述如下：\n1、预处理过程：获得椭圆曲线加密所需要的各项参数\n1.1：确定有限域GF(p)，即确定素域p；\n1.2：选取曲线参数a、b，确定椭圆曲线方程E：y2＝x3+ax+b(mod p)；\n1.3：计算曲线的阶N，选取曲线的基点G；\n1.4：选取随机数x，使得1≤x≤N-1，将x作为解密密钥，即 私钥；\n1.5：计算Y＝xG，Y作为加密密钥，即公钥；\n1.6：公开曲线E，生成元G和公钥Y。\n2、加密过程：\n2.1：加密方获取解密方的曲线E，生成元G和公钥Y；\n2.2：加密方获取适当长度的明文m；\n2.3：生成随机数k，其中1≤k≤N-1；\n2.4：计算点P＝kG，Q＝kY＝(x0，y0)，U＝mx0 mod p\n2.5：加密方将密文c＝(P，U)发送给解密方。\n3、解密过程：\n3.1：解密方接收到密文c＝(P，U)；\n3.2：利用私钥x，计算Q＝kP＝xkG＝k(xG)＝kY＝(x0， y0)；\n3.3：取出Q的横坐标x0，计算m＝Ux0 -1 mod p，从而得到明文m。\n4、结束。\n该方法虽然解决了明文嵌入的问题，但不能兼容ElGamal加密方 法。\n发明内容\n本发明的目的提供一种新的椭圆曲线加密方法，它一方面解决了 明文嵌入问题，另一方面具有极高的灵活性，能够通过参数的选择构 造出现有的一些加密方法，再者，该方法的实现效率非常高。\n本发明提供了一种加密解密方法，系统首先确定有限域GF(q)， 选取椭圆曲线方程E；选取椭圆曲线的基点G，并计算有限域上椭圆曲 线点群的阶N。用户B作为解密方，利用这些系统参数生成自己的私 钥xB，其中1≤xB≤N-1，然后利用基点G计算点乘得到公钥YB＝xBG。 加密方A对于明文m的加密过程步骤以下：\n首先，加密者获取B的公钥YB，然后生成随机数k，使的k落在 区间[1，N-1]上，将k分别与公钥YB和曲线的基点G进行椭圆曲线点 乘运算，得到曲线上的点P＝kG，Q＝kYB；分别使用函数v和g对P 和Q进行运算，即得到v(P)，g(Q)；使用函数f对明文m进行运算， 得到f(m)，使用函数u对f(m)和g(Q)运算得到u(f(m)，g(Q))，这样 得到的(v(P)，u(f(m)，g(Q)))即为加密者对明文m的加密结果，表 示为(V，U)，其中V＝v(P)，U＝u(f(m)，g(Q))。\n解密方B接受密文(V，U)，使用r函数对B的私钥xB和V进行 运算，得到r(xB，V)，使用d函数对r(xB，V)和U进行运算得到D＝d(U， r(xB，V))，最后使用f的逆函数计算得到明文m＝f-1(D)。\n根据本发明的另一个方面提供一种采用所述椭圆曲线加密方法的 加解密装置；\n附图说明\n图1是本发明加密过程的流程图。\n图2是本发明解密过程的流程图。\n图3是本发明的加密解密装置的方框图。\n具体实施方式\n图1示出本发明的加密过程的流程图。\n在步骤101，加密方A获取解密方B公开的系统参数和公钥YB；\n在步骤102，A生成随机数k，其中1≤k≤N-1，其中N为椭圆 曲线的点群的阶；\n在步骤103，将k与基点G及B的公钥YB作椭圆曲线的点乘运算， 得到P＝kG，Q＝kYB；\n在步骤104，计算V＝v(P)，利用v函数对P作进一步数据处理， 例如对P进行压缩或扩展；\n在步骤105，加密方获取适当长度的明文m，并使用f对明文m作 预处理运算得到f(m)。其中，函数f(m)必须有逆函数，通过f-1(f(m)) 必须能够恢复出m，可以包含如下形式：\na)f(m)可以取值为：f(m)＝m，则f-1(m)＝m\nb)f(m)可以取值为：f(m)＝(m，n)，其中n为随机数，则 f-1(m，n)＝m；\nc)f(m)可以取值为：f(m)＝(m，h(m))，其中h为Hash函数，如 SHA-1、MAC等，则f-1(m，h(m))＝m；\nd)f(m)可以取值为：f(m)＝(m1，m2)，其中m＝m1||m2，||为连 接符号，则f-1(m1，m2)＝m1||m2＝m；\ne)f(m)可以取值为：f(m)＝(11(m1)，12(m2))，其中m＝m1||m2， ||为连接符号，11，12为可逆的扩展函数，则f-1(11，12)＝11 -1(11(m1)) ||12 -1(12(m2))＝m；\nf)等等。\n在步骤106，计算得到U＝u(f(m)，g(Q))，最后得到密文(U，V)， 其中V为步骤104中计算得到的v(P)。\n在步骤106中，对于函数u必须具有以下性质；设u函数形为U＝ u(x，y)，从函数u可以推得y＝u’(x，U)，这样得到的u’函数将用 于下述的解密中。\n在步骤106中，适用函数g对包含私钥xB和随机数k信息的Q点 作进一步处理，如对Q进行压缩处理或扩展处理，例如g(Q)可以取为：\na)g(Q)可以取值为：g(Q)＝Q；\nb)g(Q)可以取值为：g(Q)＝x0，或者g(Q)＝y0，其中Q＝(x0， y0)；\nc)g(Q)可以取值为：g(Q)＝x0||y0，其中Q＝(x0，y0)，||为 连接符号；\nd)g(Q)可以取值为：g(Q)＝h(x0)，或者g(Q)＝h(y0)，其中Q＝(x0， y0)，h为Hash函数，如SHA-1或MAC等；\ne)g(Q)可以取值为：g(Q)＝h(x0||y0)，或者g(Q)＝h(x0)||h(y0)， 其中Q＝(x0，y0)，||为连接符号，h为Hash函数，如SHA-1或MAC等；\nf)等等。\n在步骤207，生成密文(V，U)，加密方A将该密文发送给解密方 B。\n至此，加密过程结束。\n图2示出本发明的解密过程的流程图。\n在步骤201，解密方B接收到密文(V，U)；\n在步骤202，B获取自己的私钥xB；\n在步骤203，B使用自己的私钥xB和接收到的V作运算，得到R＝r(xB， V)；其中函数r使得可以利用私钥xB和包含了随机数信息的V中运算 得到U中包含的部分信息，满足：r(xB，V)＝g(Q)，这样得到的结果即 可以和U一起运算得到所需的明文信息，例如：\na)当取函数形为v(P)＝P，则取r(xB，V)＝g(xBV)；\nb)当取函数形为v(P)＝(x0，s)，其中P＝(x0，y0)，s取值为y0 的方向标志位，此时v的函数具有与u函数一样的性质，存在v’函 数，则取r(xB，V)＝g(xBv’(V))；\nc)当取函数形为v(P)＝xP，g(Q)＝x0，其中P＝(xP，yP)，Q＝ (x0，y0)，适当取r即可满足r(xB，V)＝g(kY)；\n在步骤204计算D＝u’(U，R)；其中函数u’与加密过程中的函 数u具有以下性质，对于z＝u(x，y)，则可以得到x＝u’(z，y)。函数 u和u’可以为如下形式；\na)u、u’可以取值为对称加解密函数，x0为明文，y0为密钥；\nb)u、u’可以取值为椭圆曲线点加、点减函数(或点减、点加函 数)，x0，y0分别为椭圆曲线上的点；\nc)u、u’可以取值为模加函数和模减函数，u(x0，y0)＝x0+y0(mod q)，d(x0，y0)＝x0-y0(mod q)；\nd)u、u’可以取值为模乘函数和逆函数，u(x0，y0)＝x0*y0(mod q)， d(x0，y0)＝x0*y0 -1(mod q)；\ne)u、u’可以取值为模2加法(异或)， $u(x_0,y_0)=d(x_0,y_0)=x_0\oplus y_0;$\nf)u、u’可以取值为同或操作， $u(x_0,y_0)=d(x_0,y_0)=x_0\otimes y_0;$\ng)等等。\n在步骤205，计算m＝f-1(D)，从而得到明文m。\n至此，解密过程结束。\n图3示出本发明的加密解密装置。加密方A和解密方B在一个通 信信道上通信时，解密方B使用密钥生成装置340生成B的密钥对： 公钥YB和私钥xB。加密方A使用加密器320，采用结合图1说明的加 密过程对明文m进行加密，并将生成的密文c发送至解密方B。解密 方B的解密器350通过结合图2说明的解密过程对密文c进行解密， 获得信息m。\n以上结合本发明的最佳实施例对本发明进行了描述，本领域的普 通技术人员可以在不偏离本发明的范围的情况下可对其作各种修改和 改变。