5、ECDSA域参数

ECDSA的域参数包括一条合适的椭圆曲线和其上一个基点G。域参数可以全局公开，也可以只对单个用户公开。5.1部分讲述域参数应该满足的要求，5.2部分讲解如何产生随机曲线，5.3部分介绍了一种产生域参数的方法，5.4部分给出了验证域参数是否符合要求的方法。

5.1域参数

为了提高实现效率，基域尺寸和参数的选择都有限制：另外，为了抵抗已知的攻击方式，曲线的选择和基点的阶都有一定的限制。

对域的要求
基域的阶要么q等于p,要么等于。前者模一个大素数p，后者模一个多项式或正规基。

对曲线的要求
为了抵抗Pollard’s rho和Pohlig Hellman攻击。E上的点的个数应能被一个大素数n整除。ANSI  X9.62规定n应大于和。应选择E使得为素数或近似素数。定义辅因子，其中n为素数，h非常小。

选择曲线时应注意的一些其他事项
为了抵抗MOV和FR攻击，曲线应是非超奇异（即要求p不能整除）的。更一般的，应当满足n不能整除，1≤k≤C，一般取C为20。最后，为了抵抗SSSA对反常曲线的攻击，不得取反常曲线（即不得等于q）。
为了抵御上面提到的和将来可能出现的对这些特殊曲线的攻击，应使用随机方式选取一条椭圆曲线满足能被一个大素数整除，满足上述一系列条件的随机曲线不甚可能被这些攻击方式所攻破。可以使用随机数发生器（如SHA-1一类的单向函数）来产生曲线的系数。5.2中介绍了一种类似FIPS-186的模式以产生随机曲线。

域参数的概述
1.域尺寸q，q=p或。
2.域的表示方法FR和其中元素的表示方法。
3.至少160比特长度的随机比特串。
4.两个域参数a和b。
5.基点G(xG,yG)。
6.点G的阶n>160bit，n>4sqrt(q)。
7.辅因子。

5.2用随机方法产生椭圆曲线

本节讲述如何用随机方法产生椭圆曲线。随机参数使用SHA-1来产生。使用这种方法产生的椭圆曲线具有良好的随机性，可以避免性质较差的曲线的产生。

q=p的情况
下面要使用到这些参数：
算法1.产生一条随机椭圆曲线。
输入：域尺寸p。
输出：至少160比特的比特串，参数a，b，它们确定了一条Fp上的椭圆曲线。
1．选择一个长度g大于160比特的随机比特串SeedE。
2.计算H=SHA-1(SeedE)，c0表示H的右起v长比特串。
3.W0是H的左起v长比特串。
4.z是比特串SeedE所表示的整数。
5.for i from 1 to s do
  (1)是 的比特串。
  (2)计算Wi=SHA-1()。
6.W是比特串W0||W1||……||Ws。
7.r是比特串W所表示的整数。
8.若r=0或4r+27=0 modp则返回第一步。
9.选择随机整数a,b∈Fp，不能同时为0，要求（可以让a,b同时为r）。
10.选定的曲线为。
11.输出SeedE，a，b。

上的椭圆曲线同构类
两条定义在上的椭圆曲线E1:和E2:在上同构的充要条件是存在u∈使得（同构的椭圆曲线可以认为是相同的，若E1同构于E2，则E1()同构于E2()）。若E1同构于E2且b1不为0，则有。奇异椭圆曲线：曲线E:，4a*a*a+27b*b=0 modp，要么是a,b同时为0，要么是a*a*a/b*b=-27/4。若r∈Fp，r≠0，r≠-27/4，则存在两个曲线同构群E: ，a*a*a/b*b=r modp。算法1的第9步中(a,b)就只有两种选择。第8步中的限制条件确保曲线不是异常曲线。另外我们注意到算法1产生的曲线不会发生a,b有一个为0而另一个不为0的情况，这无关紧要因为这些曲线只是所有曲线中微不足道的一部分，任何算法都不可能完全随机地来产生曲线。

上的扭曲线
两条非同构曲线：E1: ，E2: y2=x3+ac2x+bc3，c∈，是一个非模p二次剩余，则称E1,E2相互扭转。它们的r是相等的。它们的阶满足：#E1()+ #E2()=2p+2，若能计算出其中一条曲线的阶，另一条曲线的阶可轻易得出。

算法2.证明一条曲线是在上随机产生的。
输入：域尺寸p，长度g≥160bit的比特串SeedE，域参数a,b。
1.计算H=SHA-1(SeedE)，c0是H的右起v长比特串。
2. W0是H的左起v长比特串。
3. z是比特串SeedE所表示的整数。
4. for i from 1 to s do
  (1)是的比特串。
(2)计算Wi=SHA-1()。
5. W是比特串W0||W1||……||Ws。
6. r是比特串W所表示的整数。
7. 验证是否成立，成立则接受，反之则拒绝。

q=的情况
下面要使用到这些参数：
算法3：产生上的一条随机椭圆曲线。
输入：域尺寸。
输出：至少160比特的比特串，参数a，b，它们确定了一条上的椭圆曲线。
1. 选择一个长度g大于160比特的随机比特串SeedE。
2. 计算H=SHA-1(SeedE)，b0表示H的右起v长比特串。
3. z是比特串SeedE所表示的整数。
4. for i from 1 to s do
  (1)是的比特串。
(2)计算bi=SHA-1()。
5. b是比特串b0||b1||……||bs。
6.若b=0则返回第一步。
7.a是上的随机数。
8.上的椭圆曲线E:。
9.输出SeedE，a，b。

上的椭圆曲线同构类
上的两条曲线E1: ，E2: 在上同构的充要条件是b1= b2且TR(a1)= TR(a2)，TR(ß)= ß +ß2+ ß4+……+ ß2^(m-1)。同构的椭圆曲线可以认为是相同的，若E1同构于E2，则E1()同构于E2()。下面是F2m上的一个典型的椭圆曲线同构类{ |b∈,b≠0,a∈{0, ß }}，其中ß∈，是一个满足TR(ß)=1的固定元素（若m是奇数，则令ß=1）。因此对于已经选定的b，算法3中的步骤7中a只有两种选择。

上的扭曲线
两条不同构的曲线E1: ，E2: ，b1= b2=b，TR(a1)≠TR(a2)，则这两条曲线互称为扭曲线。它们的阶满足#E1()+ #E2()=2p+2，若能计算出其中一条曲线的阶，另一条曲线的阶可轻易得出。上的椭圆曲线的阶总是偶数，若TR(a1)=0，则#E1()=0 mod4，若TR(a1)=1，则#E1()=2 mod4。
算法4. 证明一条曲线是在F2m上随机产生的。
输入：域尺寸，长度g≥160bit的比特串SeedE，域参数a,b。
输出：判断算法3产生的曲线是否是随机的。
1. 计算H=SHA-1(SeedE)，b0表示H的右起v长比特串。
2. z是比特串SeedE所表示的整数。
3. for i from 1 to s do
  (1)是的比特串。
(2)计算bi=SHA-1()。
4. b’是比特串b0||b1||……||bs。
5.若b=b’，则接受反之则拒绝。