基于环Zn上圆锥曲线的双难题公钥加密体制

近年来，基于圆锥曲线密码体制的研究引起了学者们的关注，那么今天，我们就在前人研究的基础上提出了基于环Zn上圆锥曲线的双密钥公开加密体制，从而实现了圆锥曲线上的基于大整数分解与圆锥曲线上的离散对数双困难问题的加密体制，并给出了数值模拟。

一、基于环Zn上圆锥曲线的相关知识

1、环Zn上的圆锥曲线

设Zn是一个模n的剩余类环，定义环Zn上的圆锥曲线是同余方程：

在Zn上的解（x，y）的集，这里n=pq，p，q为两个不同的奇素数，（a，n）=（b，n）=1。a是模p的二次非剩余，b是模q的二次非剩余，且p+1=2r，q+1=2s，其中r，s是素数，则曲线的阶Nn=2rs，可以对圆锥曲线Cn（a，b）上的点定义一个加法运算。圆锥曲线上的点的集合在该加法作用下构成一个有限交换群，在此圆锥曲线上阶为Nn=2rs的点G称为基点。圆锥曲线上的离散对数问题定义为：由基点G生成的群S={G，2G，NnG}

给定M，N∈S，求出整数e使得M=eN是非常困难的，称为圆锥曲线上的离散对数问题。

2、基于环Zn上圆锥曲线的RSA公钥密码体制

首先选定一条圆锥曲线：y2≡ax2-bx（modn）其中a，b∈Zn，（a，n）=（b，n）=1，n=pq，p，q为两个不同的大素数，满足（a/p）=-1，（a/q）=-1，且p+1=2r，q+1=2s，其中：r，s也为素数，令Nn=2rs，任取1＜e＜Nn，且（e，Nn）=1，计算ed=1（modNn）则：

（1）参数选择

公钥：e，n，a，b

私钥：d，p，q

（2）加密算法

计算C=eP1（m）（modn）

（3）解密算法

dC=deP1（m）=（1+hNn）P1（m）=P1（m）

对P1（m）使用译码算法即得明文m。

3、基于环Zn上圆锥曲线的E1Gamal加密算法

首先选定一条圆锥曲线：y2≡ax2-bx（modn）其中a，b∈Zn，（a，n）=（b，n）=1，n=pq，p，q为两个不同的大素数满足（a/p）=-1，（a/q）=-1，且p+1=2r，q+1=2s，其中：r，s也为素数，令Nn=2rs，选取G∈Cn（a，b），其阶为Nn=2rs，即G为基点。任取1＜e＜Nn，计算Y=eG。

公开：n，a，b，G，Y

私钥：e

加密算法：

任取k，计算C1=kG，C2=P1（m）⊕kY，密文C=（C1，C2）

解密算法：

计算C2⊕（-eC1）=P1（m），对P1（m）用译码算法得明文。

显然，系统安全性基于圆锥曲线上计算离散对数的困难性。

二、基于环Zn上的圆锥曲线的双密钥公开加密体制

首先选定一条圆锥曲线：Cn（a，b）y2≡ax2-bx（modn）其中a，b∈Zn，（a，n）=（b，n）=1，n=pq，p，q为两个不同的大素数满足（a/p）=-1，（a/q）=-1。且p+1=2r，q+1=2s，其中：r，s也为素数，令Nn=2rs，选取G∈Cn（a，b），其阶为Nn=2rs，即G为基点。任取1＜x＜Nn，计算Y=xG。再计算3×d≡1（modNn）。

公钥：n，G，Y，3

私钥：x，d，Nn

所谓双密钥就是指d和x，分别是基于大整数分解难题与圆锥曲线离散对数难题的密钥。其中解密密钥d与RSA中的解密密钥相似，而RSA体制中的公钥这里用常数3代替，当然这里公开钥值也不一定是3，可以根据情况选取，只要保证是个小常数，从而节省系统开销。

具体加密过程通信双方首先要共享一个会话密钥：设KAB为用户A，B之间进行通信对话的公开密钥（会话密钥），若A为通信发起者，则A取B的公钥（nB，GB，YB，3），用户B保存自己的私钥（xB，dB，NnB），用户A随机地选择一个数k，1＜k＜n/2，并依下列各式计算出KAB，ZA，C：

KAB=kY；

ZA=kG；

C=3ZA。

然后，将C值传送给用户B，用户B收到C值后，再用私钥xB和dB计算出ZA和KA：

ZA=dBC=3dBZA=（1+hNn）ZA=ZA0；

KAB=xBZA。

加密方法：

设用户A向用户B传送需加密的明文序列为{m1，m2，mi}，先将明文序列嵌入圆锥曲线的点P1（mi），A用户用会话密钥KAB通过下面的方法对生成的明文数据块mi加密的一对密钥Ki，1和Ki，2：

Ki，1=Ki-1，1⊕KAB=iKAB=P1（ki）；

（K0，1=1）Ki，2=kiG；

加密过程：

i=3P1（mi）⊕Ki，2；

解密方法：

用户B用自己的私钥按上文描述的方法计算出会话密钥KAB，再用KAB计算出Ki，1和Ki，2。

解密过程：

P1（mi）=dB（Ci，Ki，2）。

译码算法得mi。

三、基于环Zn上的圆锥曲线的双密钥公开加密体制的数值模拟

首先B选定一条圆锥曲线：Cn（2，1）y2≡2x2-x（mod65），即a=2，b=1，n=65，p=5，q=13，r=（p+1）/2=3，s=（q+1）/2=7，Nn=2rs=42，G=P1（2）=（32，64），取x=11，Y=xG=11G=P1（58）。

5×d≡1（mod42）

公钥：n=65，G=P1（2）；Y=P1（58），5

私钥：x=11，d=17，Nn=42。

用户A为通信发起者，其随机选取k=5，计算出KAB，ZA，C：

KAB=5P1（58）=P1（37）；

ZA=5P1（2）=P1（3）；

C=5P1（3）=P1（32）。

用户A将C值发给用B，B通过私钥计算出的KAB：

ZA=17P1（32）=P1（3）；

KAB=11P1（3）=P1（37）。

设用户A向用户B传送需加密的明文序列为{m1=24，m2=18}，先将明文序列嵌入圆锥曲线的点， P1 （24），P1 （18），A用户用会话密钥KAB通过下面的方法对生成的明文数据块m1， m2加密的一对密钥K1，1，K2，1和K1，2，K2，2：

K1，1=KAB=P1（37），K1，2=37G=37P1（2）=P1（62）；

K2，1=2P1（37）=P1（44），K2，2=44G=44P1（2）=P1（34）；

加密过程：

C1=5P1（24）⊕P1（62）=P1（36）⊕P1（62）=P1（48）

C2=5P1（18）⊕P1（34）=P1（22）⊕P1（34）=P1（25）

传送（C1，C2）

解密过程：

用户B同样通过会话密钥KAB计算出加密的密钥，从而进行解密。

P1（m1）=d（C1，K1，2）=17（P1（48），P1（62））=17P1（36）=P1（24）；

P1（m2）=d（C2，K2，2）=17（P1（25），P1（34））=17P1（22）=P1（18）。

通过明文译码算法得到明文m1=24，m2=18。

四、基于环Zn上圆锥曲线的双难题公钥加密体制安全性与性能分析

1、安全性分析

从会话密钥KAB的计算过程可以看出，用户B要得到KAB必须要用的密钥dB和xB，而求解它们分别是大整数分解困难问题与圆锥曲线上的离散对数难题。攻击者即使成功分解了大整数，从而得到密钥dB，但也只能得到ZA，要想计算出KAB还需要计算xB，这是一个圆锥曲线上的计算离散对数的难题。反过来攻击者若能够得到xB，无法解密C，还需要得到dB，而这是一个求解大整数分解难题。所以本体制是一个基于双难题的密码体制，攻击者必须同时攻克双难题，才能破解本系统，这使本系统有较高的安全性。

为了提高系统效率，在文件加密中使用了小常数作为公钥，在有限域上双密钥公开加密体制会受到小加密指数的算法攻击，使系统存在安全隐患，基于大整数分解困难问题的安全性存在漏洞。而由于圆锥曲线上的RSA体制能够抵抗小加密指数攻击，因此本文提出的在圆锥曲线上的双密钥公开加密体制可以抵抗小加密指数的攻击，使本体制在保持效率的同时具有更好的安全性。

本体制在加密与解密过程中对会话密钥进行了迭代计算，并对明文的加密采用了分组加密，使同样的明文可以对应不同的密文，从而使安全性有了一定的提高。

2、性能分析

在本体制中，对于一个数据块mi的加密，需要用到一个圆锥曲线上点的倍乘运算，但由于其倍数为小常数（为3），故此运算量可以忽略。对于解密数据块Ci，需要两次圆锥曲线上的倍乘运算，这个运算量相当于圆锥曲线上的RSA或ElGamal的单个运算量。同时，由于圆锥曲线中明文嵌入、阶的计算及点的运算都比较容易，特别是在群（Cn（a，b），⊕）中逆元计算十分容易，以及在引进标准二进制计算群元素的情况下，比著名的“平方-和-乘法”算法节约1/4计算量。这使本体制易于实现。

本文将双密钥公开加密体制在圆锥曲线上进行了模拟，从而实现了圆锥曲线上的基于大整数分解困难与圆锥曲线上的离散对数困难问题的加密体制，并进行数值模拟，分析了该体制的安全性与效率，与原有体制相比，本体制在保证原有效率的同时还能够抵抗小加密指数攻击，从而提高了系统的安全性。而且圆锥曲线上的各种运算比较容易，使本体制易于实现，具有一定应用价值。

admin普通用户

海报分享