SM椭圆曲线参数选取

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

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

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

4、，首先在有限域GF( pl ) ( pl =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,求解比特用SEEDM Fp中的元素a,b(D.1p37 参数生成)a)任意选择长度至少为192的比特用SEEDb)计算H = H256(SEED,并记 H = (h255 ; h254; . ; h0);c)置R =2 hi2i,其中i取从0到255的整数；d)置 r = R moqb;e)任意选择Fp中的元素a和b,使r2三a3 (modp);f) 若(4a3+27b2) mod p=0,则转步骤 a)

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

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

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

9、行时间大约只需要几分钟，它可以快速 地将阶能被小素数整除的候选曲线淘汰，因此常用于早期中止策略。1999年，Satoh提出了计算小特征有限域上阶的全新方法 Satoh方法，该方法的一些变体如 Satoh 一 Skjemaa 一 Taguchi(SST)和算术几何中值(AGM1(法，在二进制域的情况下速度非常快，可以很快 地生成适合密码学用途的椭圆曲线。三.基点的选取及其阶次要求椭圆曲线密码体制并不是运行在整个 EC元素构成的阿贝尔群上，而是运行在由其基点 G生成的子群中，为了提高曲线的安全性，选择的基点 G的阶就是#£的一个大素因子。根 据前面得到的参数p, a, b和n,利用下面的算法可以求出具有大素数阶的基点：随着参数a,b,p确定，这条曲线y2=x3+ax+b就定下来了。先随机产生0至Up-1间的整 数作为基点x坐标