CN102394747B - 一种快速嵌入明文到椭圆曲线上一点的方法 - Google Patents

Abstract

本发明公开了一种快速嵌入明文到椭圆曲线上一点的方法，其包含：1、设椭圆曲线方程f(x)=x^3+a*x+b=y^2；2、设椭圆曲线上一点的横坐标Xi=256M＋i，M为明文；3、求t0＝f（Xi）^（p-1）/2modp，p为素数，p－1＝2^n×q，其中q为奇数，n>=1，判断t0的值，若t0=-1，转到步骤2；若t0=1，f（Xi）模p有平方根，跳转到步骤4；4、判断n的值，若n=1，则Y=f（Xi）^(p+1)/4modp，跳转到步骤8，若n≠1，跳转到步骤5；5、随机选择一个小于p大于0的大数u，u^(p-1)/2＝－1modp；6、设中间变量g=u^q，d＝f（Xi）^q，w＝f（Xi）^(q＋1)/2；7、采用逐次递减法计算d的阶为1；8、确定椭圆曲线上一点的纵坐标Y。本发明提高了明文嵌入到椭圆曲线上一点的速度。

Description

一种快速嵌入明文到椭圆曲线上一点的方法

技术领域

本发明涉及一种信息加密技术，具体涉及一种快速嵌入明文到椭圆曲线上一点的方法。

背景技术

进入21世纪以来，互联网在中国得到突发猛进的发展，根据CNNIC(中国互联网络信息中心)统计数字显示，截至2011年6月，中国网民规模达到4.85亿，较2010年底增加2770万人；互联网普及率攀升至36.2%，较2010年提高1.9个百分点。随着信息技术的发展与应用，网上交易如网上银行、电子政务和电子商务也变得越来越普遍。随之带来的安全问题也越来越严重，统计显示2011年上半年，遇到过病毒或木马攻击的网民达到2.17亿，比例为44.7%；有过账号或密码被盗经历的网民达到1.21亿人，占24.9%，较2010年增加3.1个百分点。因此在电子政务、电子商务等网络事务中就需要防止别人窃取并篡改重要信息，如攻击者通过监听网络得到收发双方的信息、攻击者截取中间信息并进行篡改。

为了解决上面的问题，需要对在网络上传输的信息进行加密，也就是在交互的双方建立一条安全通道，别人不能够窃取到这些信息，即使窃取到了，也不能看到真实信息。传统的加密算法采用的是对称密码体制，通信双方共享同一密钥，它的优点是加密易于用硬件实现，加解密速度都很快，但是存在安全隐患，密钥在交换的时候容易被人窃取。而现代公钥密码体制是非对称密码体制，仅要求密钥的交换是保真的，而不要求其是保密的。每个实体选择一个密钥对（e，d），其中e是公钥，而d是私钥，私钥是需要保密。由公钥是不能计算出私钥。目前，公钥密钥算法主要有两种，一种是RSA，另外一种就是椭圆曲线密码ECC（Elliptic Curve Cryptography），其公钥为椭圆曲线上一点，私钥为一大数，通过公钥乘以私钥即可得到所要加密的内容。

椭圆曲线密码ECC的运用方法如下：

1、ECC参数组（p,Fp,a,b,n,G（Gx，Gy）），其中，p：素域Fp的阶；a,b：椭圆曲线y^2=x^3+a*x+b的系数；G：基点（在椭圆曲线上选定的一点）；n：基点G的（素数）阶；Gx,Gy：基点的x和y坐标。

2、ECC密钥对的生成：输入：参数组D＝（p,Fp,a,b,n,G（Gx，Gy））；输出：公钥Q，私钥d。其流程为（1）、选择d，范围[1,n－1]；（2）、计算Q=dG；（3）、返回（Q，d）。

3、基本的ECC加密流程：输入：公钥Q，明文Plain，输出：密文C0 & C1。（1）将输入明文表示成前面已选定的椭圆曲线上的一个点M。（2）随机选择整数k, 该整数的范围为[1,n]。（3）计算C0 = kG（4）计算C1 = k*Q + Plain（5）返回C0、C1。

4、基本的ECC解密流程：输入：私钥d，密文C0、C1，输出：明文Decipher。（1）计算Decipher = C1 – d* C0；（2）返回Decipher。

ECC相对于RSA系统吸引人的主要原因是其安全性是基于有限域上的椭圆曲线上的点群中的离散对数问题ECDLP，ECDLP是比因子分解问题更难的问题，160bit的椭圆曲线密码系统可提供与1024bit的RSA相当的安全强度，而224bit的椭圆曲线密码系统则与2048bit的RSA具有相同的安全强度。故越来越多的应用选择了用椭圆曲线密码系统作为加密系统。为了运用椭圆曲线密码，需要把明文信息映射为椭圆曲线上一点，才能对该信息运用椭圆曲线密码系统。目前，把明文嵌入到椭圆曲线上一点的实现算法大多采用概率算法，大多数的研究也都是基于概率算法的基础上寻找快速算法，但不甚理想，因此找到一种快速的明文嵌入方法尤其必要。

发明内容

本发明提供一种快速嵌入明文到椭圆曲线上一点的方法，提高了把明文嵌入到椭圆曲线上一点的速度，提高加密性能。

为实现上述目的，本发明提供一种快速嵌入明文到椭圆曲线上一点的方法，其特点是，该方法包含以下步骤：

步骤1、设椭圆曲线方程f(x)=x^3+a*x +b=y^2，x为横坐标，y为纵坐标，该椭圆曲线方程定义为有限域Fp上的椭圆曲线，p为素数；

步骤2、设椭圆曲线上一点的横坐标Xi=M×k＋i，其中M为明文，令k＝256，i＝0，横坐标Xi相对应的纵坐标设为Y；

步骤3、采用欧拉准则判断f（Xi）是否有平方根，设t0＝f（Xi）^（p-1）/2 mod p，p为素数，p－1＝2^n×q，其中q为奇数，n>=1；

判断t0的值，若t0=-1，f（Xi）属于模p的非平方剩余集合，即f（Xi）模p没有平方根，则令i=i+1，并跳转到步骤2；

若t0=1，f（Xi）属于模p的平方剩余集合，即f（Xi）模p有平方根，则跳转到步骤4；

步骤4、判断步骤3中n的值是否等于1；

若n=1，p＝4×（q+1）/2 – 1，表示p=3mod4，且由f（Xi）^（p-1）/2 mod p＝1得f（Xi）^（（p+1）/4）^2mod p= f（Xi），则赋值椭圆曲线上一点的纵坐标Y= f（Xi）^(p+1)/4 mod p，并跳转到步骤8；

若n≠1，则跳转到步骤5；

步骤5、随机选择一个小于p大于0的大数u，其中u^(p-1)/2 ＝－1 mod p，即u属于模p的非平方剩余集合；

步骤6、计算f（Xi）的平方根Y的值，设中间变量g= u ^q，d=f（Xi）^q，w=f（Xi）^(q＋1)/2；

步骤7、采用逐次递减方法使d的阶为1，从而快速求出f（Xi）的平方根Y；

步骤7.1、设中间参数r＝n；

步骤7.2、设中间参数m，其初始值设为0；

步骤7.3、计算d模p的阶，设c＝d^2^m mod p，计算c的值，判断c的值是否等于1；

若c＝1，表示d模p的阶为2^m，因为f（Xi）是模p的平方剩余，则m≤（r-1），并跳转到步骤7.4，

若c≠1，则将m的值增大1，m＝m＋1，并跳转至步骤7.3；

步骤7.4、设t=g^（2^（r-m－1））mod p，对g、d、w的赋值进行更新，其更新的关系式如下：

g＝t*t mod p；d＝d*g mod p；w＝w*t mod p；

步骤7.5、判断d是否等于1，若d=1，则w为f（Xi）的平方根，即Y =w，跳转到步骤8，若否，则将m的值赋给r，转到步骤7.2；

步骤8、计算得出椭圆曲线上一点的纵坐标Y的值，确定椭圆上一点（Xi，Y），根据Xi=M×k＋i，算得明文M。

本发明一种快速嵌入明文到椭圆曲线上一点的方法和现有技术相比，其优点在于，本发明的模乘和模幂使用硬件的Montgomery算法实现；第二，采用逐次递减方法使得d的阶为1，从而快速求出f（Xi）的平方根Y，实现加快了运算速度；第三，明文乘以256再赋值给Xi，这样解密时只需要将解密后的数据再去掉最后一个字节即可得到明文。

附图说明

图1为本发明一种快速嵌入明文到椭圆曲线上一点的方法的总流程图；

图2为本发明一种快速嵌入明文到椭圆曲线上一点的方法中将d的阶逐次递减为1的方法流程图。

具体实施方式

以下结合附图说明对本发明的实施例作进一步详细描述，但本实施例并不用于限制本发明，凡是采用本发明的相似结构、方法及其相似变化，均应列入本发明的保护范围。

如图1所示，本发明公开了一种快速嵌入明文到椭圆曲线上一点的方法，该方法包含以下步骤：

步骤1、设椭圆曲线方程f（x）=x^{^3} +a*x +b=y^{^2}是定义在有限域Fp上的椭圆曲线，其中x为椭圆曲线上的横坐标，y为椭圆曲线上的纵坐标。有限域Fp表示：p为素数，以p为模，则模p的全体余数的集合{0，1，2……（p－1）}关于模p的加法和乘法构成一个p阶有限域即有限域中的元素只有p个，并用符号Fp表示。

步骤2、设椭圆曲线上一点的横坐标Xi=M×k＋i，椭圆方程上一点的纵坐标为Y，其中M为明文，令k＝256，说明将明文乘以256再赋值给Xi，并且i＝0。与该横坐标Xi相对应的纵坐标设为Y。

256=2⁸，在本实施例中采用解密时只需要将解密后的数据再去掉最后一个字节即可得到明文的解密要求。所以取k=256，实现上述的要求。

步骤3、 由于椭圆曲线方程f（x）=x^³ +a*x +b=y^²中，f（x）有平方根，所以本发明中求得的f（Xi），如果要满足f（Xi）=Y^{^2}，则须满足f（Xi）有平方根的要求。

根据欧拉准则可用来简单判定一个数z（z≠0 mod p）是否有二次剩余（即z有平方根）还是非剩余。所以本发明中，通过欧拉准则判断f（Xi）是否有二次剩余还是非剩余，即判断f（Xi）是否有平方根。

所以根据欧拉准则，设t0＝f（Xi）^^（p-1）/2 mod p，并求t0的值。p为素数，作为有限域Fp的阶，p－1＝2^ⁿ×q，其中q为奇数，n>=1。

其中mod运算为模运算，本发明中主要有模乘和模幂运算，该模乘和模幂采用Montgomery模乘（a*b mod n）的方法实现。

判断t0的值，若t0=-1，表示f（Xi）属于模p的非平方剩余集合，即f（Xi）模p没有平方根，则令i=i+1，选取下一点Xi，并跳转到步骤2，并将更新Xi的带入f（x）。

若t0=1，则f（Xi）^^（p-1）/2 mod p=1，表示f（Xi）属于模p的平方剩余集合，即f（Xi）模p有平方根。说明该Xi所对应的f（Xi）满足步骤3中提出的f（x）有平方根，f（x）符合椭圆曲线方程，则跳转到步骤4，进行求出f（Xi）。

步骤4、判断上述步骤3中的n的值是否等于1。

若是，n=1时，则p＝2×q＋1＝2×（q＋1）－1＝4×（q+1）/2 – 1，其中q为奇数，则（q+1）/2为整数，所以根据p＝4×（q+1）/2 – 1可得p＝3mod4，则(p+1)/4为整数。

又根据上述t0=f（Xi）^^（p-1）/2 mod p=1，两边同乘以一个f（Xi）得f（Xi）^^（p+1）/2 mod p= f（Xi），可得f（Xi）^^{（（p+1）/4）^2}mod p= f（Xi），

则可赋值Y= f（Xi）^^(p+1)/4 mod p，根据公式f（Xi）^^(p+1)/4 mod p可直接计算出f（Xi）的平方根（即椭圆曲线上一点的纵坐标Y），并跳转到步骤8。

若否，n≠1，则跳转到步骤5，继续求f（Xi）。

步骤5、 随机选择一个小于p（有限域Fp的阶）大于0的大数u，其满足u^{^(p-1)/2} ＝－1 mod p，即u属于模p的非平方剩余集合。

步骤6、采用逐次递减方法计算f（Xi）的平方根Y的值，设三个中间变量g= u ^{^q}；d＝f（Xi）^^q；w＝f（Xi）^^(q＋1)/2。

可知，w^{^2}= f（Xi）^^(q＋1)＝f（Xi）^^(q)×f（Xi）＝f（Xi）×d，故当d等于1的时候，w^²= f（Xi）= Y^²，w即为f（Xi）的平方根（即椭圆曲线上一点的纵坐标Y）。

步骤7、如图2所示，采用逐次递减方法使d的阶为1，从而快速求出f（Xi）的平方根Y。阶的意义为：称使d^^s = 1的最小正整数s为d的阶。

步骤7.1、设一个中间参数r＝n，该n为步骤2中的n。

步骤7.2、设中间参数m，其m的初始值设为0。

步骤7.3、计算d模p的阶。设中间变量c，赋值c＝d^^{2^m} mod p ，并通过计算c，判断c的值是否等于1，来计算d模p的阶。

若c＝1，表示d模p的阶为2^^m，而根据步骤3可知f（Xi）是模p的平方剩余，所以f（Xi）^^（p-1）/2 mod p=1，即f（Xi）^^{(2^(n-1)*q)} mod p=1，即d^^{2^（n－1）} mod p=1，又因为中间参数r＝n，所以m最大只可能是（r-1），并跳转到步骤7.4。

若c≠1，则将m的值增大1，m＝m＋1，并跳转至步骤7.3，再带入c＝d^{^2^m} mod p。

步骤7.4、设中间变量t，该t=g^^{（2^（r-m-1））}mod p，采用t对g、d、w的赋值进行更新。g、d、w更新的关系式如下：

g＝t*t mod p；

d＝d*g mod p；

w＝w*t mod p；

根据上述关系式，计算得更新后g、d、w的值。

很明显每次循环之后g的阶也为2^^m，因为g＝t×t mod p＝g^^{（2^（n-m））}mod p，则g^^{（2^m）}mod p＝g^^{（2^n）}mod p＝u^^{(（2^n）*q)}mod p= u^^(p-1)mod p=u^^((p-1)/2)mod p × u^^((p-1)/2)mod p=(-1)*(-1)=1，从而d=d×g的阶就变为2^（m-1），因为d^2^(m－1）mod p=d^{^2^(m－1）}mod p×g^{^2^(m－1）}mod p=(-1) ×(-1) = 1。

步骤7.5、判断d是否等于1，若d=1，则w即为f（Xi）的平方根，椭圆曲线上一点纵坐标Y等于w的值，并跳转到步骤8。若d≠1，则将m赋值给r，r＝m，并转到步骤7.2。

步骤8、得出椭圆曲线f（x）=x^{^3} +a*x +b=y^{^2}上一点的纵坐标Y，同时确定了Xi的值，即得出椭圆曲线上一点（Xi，Y）。该确定Xi除以256即获得被加密的明文M。

尽管本发明的内容已经通过上述优选实施例作了详细介绍，但应当认识到上述的描述不应被认为是对本发明的限制。在本领域技术人员阅读了上述内容后，对于本发明的多种修改和替代都将是显而易见的。因此，本发明的保护范围应由所附的权利要求来限定。

Claims (2)

1.一种快速嵌入明文到椭圆曲线上一点的方法，其特征在于，该方法包含以下步骤：

步骤1、设椭圆曲线方程f(x)=x^{^3}+a*x +b=y^{^2}，x为横坐标，y为纵坐标，该椭圆曲线方程定义为有限域Fp上的椭圆曲线，p为素数；

步骤2、设椭圆曲线上一点的横坐标Xi=M×k＋i，其中M为明文，令k＝256，i＝0，横坐标Xi相对应的纵坐标设为Y；

步骤3、采用欧拉准则判断f（Xi）是否有平方根，设t0＝f（Xi）^^（p-1）/2 mod p，p为素数，p－1＝2^n×q，其中q为奇数，n>=1；

判断t0的值，若t0=-1，f（Xi）属于模p的非平方剩余集合，即f（Xi）模p没有平方根，则令i=i+1，并跳转到步骤2；

若t0=1，f（Xi）属于模p的平方剩余集合，即f（Xi）模p有平方根，则跳转到步骤4；

步骤4、判断步骤3中n的值是否等于1；

若n=1，则p＝4×（q+1）/2 – 1，可以得出p=3mod4，且由f（Xi）^^（p-1）/2 mod p＝1得f（Xi）^^{（（p+1）/4）^2}mod p= f（Xi），则赋值椭圆曲线上一点的纵坐标Y= f（Xi）^^(p+1)/4 mod p，并跳转到步骤8；

若n≠1，则跳转到步骤5；

步骤5、随机选择一个小于p大于0的大数u，其中u^(p-1)/2 ＝－1 mod p，即u属于模p的非平方剩余集合；

步骤6、计算f（Xi）的平方根Y的值，设中间变量g= u ^^q，d=f（Xi）^^q，w=f（Xi）^^(q＋1)/2；

步骤7、采用逐次递减方法使d的阶为1，从而快速求出f（Xi）的平方根Y；

步骤8、计算得出椭圆曲线上一点的纵坐标Y的值，确定椭圆上一点（Xi，Y），根据Xi=M×k＋i，算得明文M。

2.如权利要求1所述的一种快速嵌入明文到椭圆曲线上一点的方法，其特征在于，所述的步骤7包含以下步骤：

步骤7.1、设中间参数r＝n；

步骤7.2、设中间参数m，其初始值设为0；

步骤7.3、计算d模p的阶，设c＝d^^{2^m} mod p，计算c的值，判断c的值是否等于1；

若c＝1，表示d模p的阶为2^m，因为f（Xi）是模p的平方剩余，则m≤（r-1），并跳转到步骤7.4，

若c≠1，则将m的值增大1，m＝m＋1，并跳转至步骤7.3；

步骤7.4、设t=g^^{（2^（r-m－1））}mod p，对g、d、w的赋值进行更新，其更新的关系式如下：

g＝t*t mod p；d＝d*g mod p；w＝w*t mod p；

步骤7.5、判断d是否等于1，若d=1，则w为f（Xi）的平方根，即Y =w，跳转到步骤8，若否，则将m的值赋给r，转到步骤7.2。