PDF《SM2椭圆曲线公钥密码算法》

37 D.2.1 Fp上椭圆曲线方程参数的验证・38 D.2.2 F2m 上椭圆曲线方程参数的验证

38 参考文献

39 III 前前前言言言《SM2椭圆曲线公钥密码算法》分为四个部分: 第1部分:总则 第2部分:数字签名算法 第3部分:密钥交换协议 第4部分:公钥加密算法 本部分为第1部分. 本部分的附录A、附录B、附录C和附录D为资料性附录. IV 引引引言言言N.Koblitz和V.Miller在1985年各自独立地提出将椭圆曲线应用于公钥密码系统.椭圆曲线公钥密码 所基于的曲线性质如下: 有限域上椭圆曲线在点加运算下构成有限交换群,且其阶与基域规模相近;

类似于有限域乘法群中的乘幂运算,椭圆曲线多倍点运算构成一个单向函数. 在多倍点运算中,已知多倍点与基点,求解倍数的问题称为椭圆曲线离散对数问题.对于一般椭 圆曲线的离散对数问题,目前只存在指数级计算复杂度的求解方法.与大数分解问题及有限域上离散 对数问题相比,椭圆曲线离散对数问题的求解难度要大得多.因此,在相同安全程度要求下,椭圆曲 线密码较其它公钥密码所需的密钥规模要小得多. 本部分描述必要的数学基础知识与一般技术,以帮助实现其它各部分所规定的密码机制. V SM2椭圆曲线公钥密码算法 第1部分:总则

1 范范范围 围围本部分给出了SM2椭圆曲线公钥密码算法涉及的必要数学基础知识与相关密码技术,以帮助实现 其它各部分所规定的密码机制. 本部分适用于基域为素域和二元扩域的椭圆曲线公钥密码算法.

2 符符符号 号 号和 和 和缩 缩 缩略 略 略语 语语下列符号和缩略语适用于本部分. a,b:Fq中的元素,它们定义Fq上的一条椭圆曲线E. B:MOV阈.正数B,使得求取FqB 上的离散对数至少与求取Fq上的椭圆曲线离散对数一样困难. deg(f):多项式 f(x)的次数. E:有限域上由a和b定义的一条椭圆曲线. E(Fq):Fq上椭圆曲线E的所有有理点(包括无穷远点O)组成的集合. ECDLP:椭圆曲线离散对数问题. Fp:包含p个元素的素域. Fq:包含q个元素的素域. F? q :由Fq中所有非零元构成的乘法群. F2m :包含2m 个元素的二元扩域. G:椭圆曲线的一个基点,其阶为素数. gcd(x,y):x和y的最大公因子. h:余因子,h = #E(Fq)/n,其中n是基点G的阶. Le ftRotate( ):循环左移运算. lmax:余因子h的最大素因子的上界. m:二元扩域F2m 关于F2的扩张次数. modf(x):模多项式f(x)的运算.若f(x)是二元域上的多项式,则所有系数执行模2运算. modn:模n运算.例如,23mod7=2. n:基点G的阶(n是#E(Fq)的素因子). O:椭圆曲线上的一个特殊点,称为无穷远点或零点,是椭圆曲线加法群的单位元. P:P = (xP,yP)是椭圆曲线上除O之外的一个点,其坐标xP,yP满足椭圆曲线方程. P1 +P2:椭圆曲线E上两个点P1与P2的和. p:大于3的素数. q:有限域Fq中元素的数目. rmin:基点G的阶n的下界. Tr( ):迹函数. xP:点P的x坐标. x?1 modn:使得x・y ≡

1 (modn)成立的唯一整数y,1 ≤ y ≤ n?1,gcd(x,n)=1. x ∥ y:x与y的拼接,其中x和y是比特串或字节串. x ≡ y (modn):x与y模n同余.亦即,x modn = y modn. yP:点P的y坐标. ? yP:yP的点压缩表示. Zp:整数模p的剩余类环.

1 ?G?:基点G生成的循环群. [k]P:椭圆曲线上点P的k倍点,即:[k]P = P+P+・・・+P k个 ,其中k是正整数. [x,y]:大于或等于x且小于或等于y的整数的集合. ?x?:顶函数,大于或等于x的最小整数.例如,?7? = 7, ?8.3? = 9. ?x?:底函数,小于或等于x的最大整数.例如,?7? = 7, ?8.3? = 8. #E(Fq):E(Fq)上点的数目,称为椭圆曲线E(Fq)的阶. ?:长度相等的两个比特串按比特的异或运算.