椭圆曲线参数选取

《椭圆曲线参数选取》由会员分享，可在线阅读，更多相关《椭圆曲线参数选取（5页珍藏版）》请在金锄头文库上搜索。

1、关于SM2椭圆曲线参数选取 一安全的椭圆曲线的选取1. 椭圆曲线上的公钥密码体制的安全性是建立在椭圆曲线离散对数的 基础上, 但并不是所有椭圆曲线都可以应用到公钥密码体制中 , 为了保证 其安全性，必须选取安全椭圆曲线，即只有选到合适的有限域GF(p)和椭圆 曲线(ECC)，能够抵抗攻击ECDLP算法的攻击，才能保证所选ECC的安全性。若某椭圆曲线存在优于皿/2级(n是基点阶次)计算复杂度的攻击方法, 则称此曲线为弱椭圆曲线。Fp上的超奇异椭圆曲线(有限域Fp的特征整除 q+l-#E (Fp)和Fp上的异常曲线(#E (Fp)二p)都是弱椭圆曲线。(国密 局文档p4, p25A.4抗攻击椭圆曲

2、线满足的条件)。下面是选取曲线时应遵循 的原则：(一种椭圆曲线参数生成的快速算法)(1) 为了抗击Pollard-P攻击，所选取椭圆曲线的阶#E(GF(p)的分解 式中应该包含一个大的素数因子，目前应不小于160bi t；(2) 为了抗击Weil对和Tate对的攻击，对于1 WkW30, n不能除pl (不宜选取超奇异椭圆曲线)；(3) 为了抗击Semaev-Smart-Satoh-Araki的攻击所选曲线的阶不能等 于该曲线所定义的有限域的阶，即#E(F)#p (不宜选取异常椭圆曲线)；P(4) 对于二进制域GF(2m)的度m不宜为合数。Gaudry， Hess和Smart 提出，若m有小约

3、数l (1=4)，存在比Pollards rho算法更快求解ECDLP 的方法。(5) 选择GF(p)的子域H,满足它的阶|H|是#已的最大素因子n,并 在H上实现ECC。2. 一般来说有4 种寻找安全椭圆曲线的方法:(椭圆曲线密码体制及其 参数生成的研究.2006.DR)(1) 有限域GF( p)上随机生成一椭圆曲线，直接计算其阶，判断阶是 否为大素数或含大素数因子, 若是即确定,否则继续选取曲线, 直至符合条 件。(2) 取具有一定特殊性椭圆曲线的系数， 计算该椭圆曲线的阶， 对该 阶进行判断， 直至找到所需要的安全曲线。(3) 如果p = 2m ,其中m能被一个比较小的整数d整除，首先在

4、有限 域GF(p1) ( p1 = 2 d )上选择一椭圆曲线E,并计算其阶，根据此值，利 用Weil定理2计算该曲线在其扩域GF( p)上的阶，若此阶符合安全标 准，再找曲线E在域GF( p)上的嵌入E,则E即为所需的安全椭圆曲线。(4) 首先给出具有安全条件的曲线阶， 然后构造一具有此阶的椭圆曲 线。目前国内外比较流行的计算椭圆曲线阶的算法有 complex multiplication算法、SEA算法、Satoh算法。应用广泛的椭圆曲线公钥 密码体制(ECC)中大多是基于特征2的有限域上。3. 尽管ECC的参数选取方法有许多种，应用最多的是随机选择方法，它 是根据任意给定曲线的系数，计算

5、曲线的阶直到找到素数(或近素数)阶的椭 圆曲线。(1) 参数p的选取：p当然越大越安全，但越大，计算速度会变慢，200 位左右可以满足一般安全要求；(2) 参数a、b的选取：已知素域的规模p,求解比特串SEED及Fp中的元素a, b(D.1p37参数生成)a）任意选择长度至少为192的比特串SEED；b）计算H = H256（SEED），并记H = （h255； h254； .； h0）；c）置R =3ii2i，其中i取从0到255的整数；d）置 r = R modp；e）任意选择Fp中的元素a和b，使r2三a3 （modp）；f）若（4a3+27b2）modp=0，则转步骤a）；g）所选择的

6、Fp上的椭圆曲线为E： y2 = x3+ax+b；h）输出（SEED； a, b）二椭圆曲线的阶的选取（北邮博士论文） 在椭圆曲线生成的过程中要考虑的一个重要因素就是确定椭圆曲线点的个数，即椭圆曲线的阶通常密码体制中使用的椭圆曲线E的阶#E（Fp）必须 满足以下条件:若已给定域 Fp, 要最大限度地抵抗针对 ECDLP 的 Pohlig-Hellman攻击和pollardp攻击,应使得#E（Fp）为素数或者接近素数, 即#E（Fp）=hn其中n为素数，一般来说，最小应该满足素数n216o,h非常小，比 如h=1,2,3或4;另外还要避免对特殊曲线的攻击，保证#E（Fp#p）,即椭圆曲 线E不是

7、畸形曲线；同时还要使得#E（Fp）的素因子n不能整除pt-1,其中 t=1,2,30,即椭圆曲线E不是超奇异曲线,MOV攻击法不能实现计算椭圆曲线阶的最简单的方法是直接对每个X任F（p）通过 WeierstraSS方程查找y任F（p）的解的个数，该方法在密码学域空间很大的 情况下是不可取的。在实际的阶计算中，常采用以下两种方法:复乘法和点 计数法。复乘法（CM）该方法首先选择一个满足安全性约束的阶N,然后构造阶为N的椭圆曲 线。使用这一方法的时候要先确定构造椭圆曲线的类型，再选用不同的方法 确定椭圆曲线的阶。若选取的曲线是素数域上的椭圆曲线，那么在选定阶N 后，验证阶N是否符合安全椭圆曲线的要

8、求。若满足，则利用复乘法寻找符 合参数要求的椭圆曲线。复乘法是利用具有复数乘法的椭圆曲线素性证明的 算法，来求F(p)上的椭圆曲线E。(2)点计数法1985 年, SChoof首先提出了计算任意椭圆曲线E的阶#E(Fp)的多项式 时间算法。对于实际密码系统应用中的p，该算法的实现效率较低。随后该 算法被Atkin和ElkioS等人改进，他们通过分析F(p)上的同种映射，利用 模多项式的性质，得到了改进算法sChoof 一 ElkieS 一 Atkin(sEA)算法SEA 算法是已知最好的求解任意素数域和最优扩域上椭圆曲线阶的算法，在实际 密码系统应用中，该算法的运行时间大约只需要几分钟，它可以

9、快速地将阶 能被小素数整除的候选曲线淘汰，因此常用于早期中止策略。1999 年, Satoh 提出了计算小特征有限域上阶的全新方法Satoh方法，该方法的一些变体如 Sat oh Skjemaa 一 Taguchi(SST)和算术几何中值(AGM)算法，在二进制域 的情况下速度非常快，可以很快地生成适合密码学用途的椭圆曲线。三基点的选取及其阶次要求椭圆曲线密码体制并不是运行在整个EC元素构成的阿贝尔群上，而是 运行在由其基点G生成的子群中，为了提高曲线的安全性，选择的基点G的 阶就是#E的一个大素因子。根据前面得到的参数p，a，b和n，利用下面的 算法可以求出具有大素数阶的基点：随着参数 a,b,p 确定，这条曲线 y2=x3+ax+b 就定下来了。先随机产生 0 到 p-1 间的整数作为基点 x 坐标，计算 x3+ax+b 的结果再开方就得出基点 y 坐标，必须满足 x，y 为整数，又知道椭圆曲线上的任意非无穷远点可作为 基点，得到基点G (x, y)(国密局文档p33)。由 HASSNE 公式和阿贝尔群结构定理的推论可知，在 Fp 上选取椭圆曲 线时，要求基点G的阶n4sqrt(p)(贴吧)。