CN102109974A

CN102109974A - 适用于椭圆曲线密码安全保护的随机点生成方法

Info

Publication number: CN102109974A
Application number: CN200910202023XA
Authority: CN
Inventors: 马博; 包斯刚
Original assignee: Shanghai Huahong Integrated Circuit Co Ltd
Current assignee: Shanghai Huahong Integrated Circuit Co Ltd
Priority date: 2009-12-24
Filing date: 2009-12-24
Publication date: 2011-06-29

Abstract

本发明公开了一种适用于ECC(椭圆曲线密码)安全保护的随机点生成方法，包括如下步骤：步骤1，得到某个椭圆曲线上除无穷远点之外的一个固定点P；步骤2，选取一个随机数r；步骤3，计算r与P的标量乘法，得到计算结果Q；步骤4，判断Q是否为无穷远点，若为无穷远点，则转到步骤2；否则，进入下一步；步骤5，得到某个椭圆曲线上的随机点Q。由于通过上述方法能够避免传统方法中大数的开方或解一元二次方程运算，也就避免了大量模乘运算，因此本发明中的方法能够大幅改善椭圆曲线上随机点生成的运算速度和时间。

Description

适用于椭圆曲线密码安全保护的随机点生成方法

技术领域

本发明涉及ECC(椭圆曲线密码)安全保护中需要对椭圆曲线上的点进行掩码的方法，具体涉及一种适用于ECC安全保护的随机点生成方法，尤其适用于包含ECC算法的芯片的应用。

背景技术

ECC(椭圆曲线密码)算法容易受到DPA(差分功耗分析)攻击，对抗这种攻击的一种防御措施就是在公钥生成过程中用椭圆曲线上一个随机点对计算的输入点进行掩码，用掩码后的点和标量计算公钥，然后对计算结果进行恢复处理，最后得出正确的公钥。这样，每次生成公钥时芯片的功耗公钥都会随机变化，消除了功耗和密钥之间的相关性，达到保护密钥的目的。

根据传统方法描述，生成椭圆曲线上随机点最简单的方法就是随机选取某个椭圆曲线定义域内的横坐标，通过该椭圆曲线方程计算出纵坐标。但是，椭圆曲线方程中纵坐标都是二次项式，计算纵坐标的值就需要进行开方或解一元二次方程运算，而开方或解一元二次方程运算又是通过大量的模乘运算实现的，所消耗的时间代价十分巨大。

下面是椭圆曲线算术中的大数开方或解一元二次方程算法：

1.有限域Fp中求平方根：

p为质数，g为满足0≤g＜p的整数。g的根为整数y，满足y²≡g(mod p)(式中符号“≡”表示等式两边都做mod p运算)。如果g＝0，只有一个根0；如果g≠0，g有0个或2个根。若一个根为y，那么另一个根为p-y。

输入：域Fp，g；

输出：g的平方根y。

算法1：当p≡3(mod 4)，计算整数u＝(p-3)/4。

1)计算y＝g^u+1 mod p

2)计算z＝y² mod p.

如果z＝g，表示有两个根，那么输出y；否则表示没有根，输出“nosquare roots exist.(没有平方根存在)”。

算法2：当p≡5(mod8)，计算整数u＝(p-5)/80。

1)计算γ＝(2g)^umodp

2)计算i＝2gγ²modp

3)计算y＝gγ(i-1)modp

4)计算z＝y²modp

5)如果z＝g，表示有两个根，那么输出y；否则表示没有根，输出“没有平方根存在”。

算法3：当p≡1(mod4)，计算整数u＝(p-1)/4。

1)令Q＝g；

2)产生随机数0≤P＜p；

3)计算Lucas序列元素：

U＝U_2u+1modp，V＝V_2u+1modp；

其中元素U和V的计算方法为：

U₀＝0，U₁＝1，U_k＝PU_k-1-QU_k-2，k＞2；

V₀＝2，V₁＝P，V_k＝PV_k-1-QV_k-2，k＞2。

4)如果V²＝4Q(modp)，输出y＝V/2modp并跳出程序；

5)如果U≠(1modp)，输出“没有平方根存在”并跳出程序；

6)返回步骤2)。

2.解有限域F₂ ^m中的二元方程(z²+z＝β)

如果β是有限域F₂ ^m中的元素，那么方程z²+z＝β有0或2个解。当β＝0，解为0和1；当β≠0且其中一个解为z，那么另一个解为z+1。

下面的算法为在有限域F₂ ^m中(多项式基)求方程z²+z＝β的解。

输入：域F₂ ^m，β；

输出：方程z²+z＝β的解z。

1)随机选取t∈F₂ ^m。

2)令z＝0，w＝β。

3)i从1到m-1，做以下两个步骤：

A.令z＝z²+w²t。

B.令w＝w²+β。

如果w≠0，输出“无解存在”并跳出程序。

从上述算法可以看出大数开方或解一元二次方程运算需要用到大量模乘运算，我们假设椭圆曲线为y²＝x³-3x+b，其数据长度为384位，模幂运算可以认为是模乘组合起来的，那么从上面的算法来看平均最少也需要大概576次模乘才能完成开方。可见，传统生成椭圆曲线上随机点方法所需大量模乘运算的时间代价消耗过大。

发明内容

本发明要解决的技术问题是提出了一种适用于ECC安全保护的随机点生成方法，能够通过使用随机数和椭圆曲线上固定点做标量乘法来实现椭圆曲线上随机点的生成，避免了传统方法生成椭圆曲线上随机点的大数开方或解一元二次方程运算，因此也减少了其所消耗的时间代价。

为解决上述技术问题，本发明提出了一种适用于ECC安全保护的随机点生成方法，包括如下步骤：

(1)得到某个椭圆曲线上除无穷远点之外的一个固定点P；

(2)选取一个随机数r；

(3)计算r与P的标量乘法，得到计算结果Q；

(4)判断Q是否为无穷远点，若为无穷远点，则转到步骤2；否则，进入下一步；

(5)得到某个椭圆曲线上的随机点Q。

步骤1中所述的某个椭圆曲线上的一个固定点P，包括该椭圆曲线上除无穷远点之外的任何一个固定点。

步骤2中所述的选取一个随机数r，包括随机选取一个64位或64位以内的随机数r。

步骤3中所述的r与P的标量乘法，可以采用任何公知的方法，例如从左向右的二进制方法、从右向左的二进制方法、二进制NAF算法、窗口NAF算法、标量分段算法、Montgomery算法。

步骤3中所述的r与P的标量乘法里椭圆曲线上点的坐标系，可以采用任何公知的坐标系，例如仿射坐标、标准射影坐标、Chudnovsky射影坐标、雅可比射影坐标、LD射影坐标。

步骤4中所述的判断Q是否为无穷远点，可以采用任何公知的判断方法，例如判断射影坐标中点的Z坐标是否为0、判断仿射坐标点加或倍点计算中斜率是否为无穷大。

下面对本发明适用于ECC安全保护的随机点生成方法的原理进行一下说明：

本发明适用于ECC安全保护的随机点生成方法的主体在于随机数和椭圆上一个固定点的标量乘法，只要选取足够长的随机数，便可以在保证安全性前提下快速得到该椭圆曲线上的随机点，以用于加密算法保护的点掩码措施。与传统椭圆曲线上随机点生成的方法相比，本发明中所采用的适用于ECC安全保护的随机点生成方法能够通过使用随机数和椭圆曲线上固定点做标量乘法来实现椭圆曲线上随机点的生成，减少了生成椭圆曲线上随机点所消耗的时间代价，因此能够更快速地生成椭圆曲线上的随机点。

本发明的其他优点，目的和特征将部分地在随后的描述中阐明，并且对本领域普通技术人员来说，部分内容将在审查下列内容时变得清楚，或者可以由本发明的实践而得知。利用在书面描述及其权利要求以及附图中具体指出的结构，可以实现和达到本发明的目的和其他优点。

附图说明

下面结合附图和具体实施方式对本发明作进一步详细的说明：

图1是本发明一种适用于ECC安全保护的随机点生成方法的流程图。

具体实施方式

下面给出采用本发明方法生成椭圆曲线上随机点的实施例。

在本发明的实施例中，给定的有限域为F_p，所用的椭圆曲线方程为y²＝x³-3x+b，标量乘法的坐标系选用雅可比射影坐标，标量乘法采用从左向右的二进制方法，判断无穷远点的方法为射影坐标中点的Z坐标是否为0。

如图1所示，本发明具体的椭圆曲线上随机点的生成步骤如下所示：

步骤1，得到椭圆曲线y²＝x³-3x+b上的固定点P。该固定点P可以是该椭圆曲线上除无穷远点之外的任何一个固定点。

步骤2，选取一个随机数r＜2⁶⁵，可随机选取一个64位或64位以内的随机数r。

步骤3，采用从左向右的二进制方法计算Q＝r·P(ECC标量乘法)，标量乘法的坐标系选用雅可比射影坐标。

步骤4，判断Q是否为无穷远点(判断无穷远点的方法为射影坐标中点的Z坐标是否为0)，如果射影坐标中点的Z坐标为0，则Q是无穷远点，转到步骤2；否则，进入下一步。

步骤5，得到椭圆曲线y²＝x³+ax+b上的随机点Q。

本发明采用将一个足够长的随机数和给定椭圆曲线上的固定点做标量乘法获取椭圆曲线上的随机点。仍然假设椭圆曲线为y²＝x³-3x+b，其数据长度为384位，如果不考虑标量乘法的加速运算，坐标系选用雅可比射影坐标，假设随机数的长度为32位，那么完成一次标量乘法平均最多需要432次模乘，如果采用加速标量乘法还能更快。较传统方法而言，本发明能够通过随机数和椭圆曲线上固定点的标量乘法较快速地找到椭圆曲线上的随机点，因此避免了通过大量模乘计算求大数开方或解一元二次方程的过程，有效减短了椭圆曲线上随机点的生成时间，从而有利于目前所有包含ECC算法的芯片产品。

Claims

1.一种适用于椭圆曲线密码安全保护的随机点生成方法，其特征在于：包括如下步骤：

步骤1，得到某个椭圆曲线上除无穷远点之外的一个固定点P；

步骤2，选取一个随机数r；

步骤3，计算r与P的标量乘法，得到计算结果Q；

步骤4，判断Q是否为无穷远点，若为无穷远点，则转到步骤2；否则，进入下一步；

步骤5，得到某个椭圆曲线上的随机点Q。

2.如权利要求1所述的一种适用于椭圆曲线密码安全保护的随机点生成方法，其特征在于，步骤1中所述的某个椭圆曲线上的一个固定点P，包括该椭圆曲线上除无穷远点之外的任何一个固定点。

3.如权利要求1所述的一种适用于ECC安全保护的随机点生成方法，其特征在于，步骤2中所述的选取一个随机数r，包括随机选取一个64位或64位以内的随机数r。

4.如权利要求1所述的一种适用于椭圆曲线密码安全保护的随机点生成方法，其特征在于，步骤3中所述的r与P的标量乘法，包括从左向右的二进制方法、从右向左的二进制方法、二进制NAF算法、窗口NAF算法、标量分段算法和Montgomery算法。

5.如权利要求1所述的一种适用于椭圆曲线密码安全保护的随机点生成方法，其特征在于，步骤3中所述的r与P的标量乘法中椭圆曲线上点的坐标系包括仿射坐标、标准射影坐标、Chudnovsky射影坐标、雅可比射影坐标和LD射影坐标。

6.如权利要求1所述的一种适用于椭圆曲线密码安全保护的随机点生成方法，其特征在于，步骤4中所述的判断Q是否为无穷远点，包括如下方法：判断射影坐标中点的Z坐标是否为0，或者判断仿射坐标点加或倍点计算中斜率是否为无穷大。