SM2 - $F_{2^m}$ - IPS99技术分享

标签：输出椭圆运算比特元素 SM2 曲线

1 符号和缩略语
$a,b$：$F_q$中的元素，它们定义$F_q$上的一条椭圆曲线$E$。
$E$：有限域上由$a$和$b$定义的一条椭圆曲线。
$E⁡(F_q)$：$F_q$上椭圆曲线$E$的所以有理点（包括无穷远点$O$）组成的集合。
$F_p$：包含$p$个元素的素域。
$F_q$：包含$q$个元素的有限域。
$F_q^*$：由$F_q$中所有非零元构成的乘法群。
$F_{2^m}$：包含$2^m$个元素的二元扩域。
$G$：椭圆曲线的一个基点，其阶为素数。
$\mbox{gcd}(x,y)$：$x$和$y$的最大公因子。
$h$：余因子，$H=♯⁡E⁡(F_q)⁄n$，其中$n$是基点$G$的阶。
$m$：二元扩域$F_{2^m}$关于$F_2$的扩张次数。
$\mbox{mod }f⁡(x)$：模多项式$f⁡(x)$的运算。若$f⁡(x)$是二元域上的的多项式，则所有系数执行模$2$运算。
$\mbox{mod }n$：模$n$运算。
$n$：基点$G$的阶（$n$是$♯⁡E⁡(F_q)$的素因子）。
$O$：椭圆曲线上的一个特殊点，称为无穷远点或零点，是椭圆曲线加法群的单位元。
$P$：$P=(x_P,y_P )$是椭圆曲线上除$O$之外的一个点，其坐标$x_P$，$y_P$满足椭圆曲线方程。
$P_1+P_2$：椭圆曲线$E$上两个点$P_1$和$P_2$的和。
$p$：大于$3$的素数
$q$：有限域$F_q$中元素的数目。
$x_P$：点$P$的$x$坐标。
$x^{-1} \mbox{ mod } n$：使得$x⋅y≡1(\mbox{mod } n)$成立的唯一整数$y$，$1≤y≤n-1$，$\mbox{gcd} ⁡(x,n)=1$。
$x‖y$：$x$与$y$的拼接，其中$x$和$y$是比特串或字节串。
$x≡y(\mbox{mod } n)$：$x$与$y$模$n$同余。亦即，$x \mbox{ mod }n=y \mbox{ mod } n$。
$y_P$：点$P$的$y$坐标。
$Z_p$：整数模$p$的剩余类环。
$〈G〉$：基点$G$生成的循环群。
$[k]P$：椭圆曲线上点$P$的$k$倍点，即：$\lbrack k\rbrack P = \underset{k\text{个}}{\underbrace{P + P + \cdots + P}}$，其中$k$是正整数。
$[x,y]$：大于或等于$x$且小于或等于$y$的整数的集合。
$⌈x⌉$：顶函数，大于或等于$x$的最小整数。例如，$⌈7⌉=7$，$⌈8.3⌉=9$。
$⌊x⌋$：底函数，小于或等于$y$的最大整数。例如，$⌊7⌋=7$，$⌊8.3⌋=8$。
$♯⁡E⁡(F_q )$：$E⁡(F_q )$上点的数目，称为椭圆曲线$E⁡(F_q )$的阶。
$⊕$：长度相等的两个比特串按比特的异或运算。

2 二元扩域$F_{2^m}$
当$q$是$2$的方幂$2^m$时，二元扩域$F_{2^m}$可以看成$F_2$上的$m$维向量空间，其元素可用长度为$m$的比特串表示。
$F_{2^m}$中的元素有多种表示方法，其中最常用的两种方法是多项式基（PB）表示（参见2.2.1）和正规基（NB）表示（参见2.2.2）。基的选择原则是使得$F_{2^m}$中的运算效率尽可能高。SM2并没有规定基的选择。下面以多项式基表示为例说明二元扩域$F_{2^m}$。
设$F_2$上$m$次不可约多项式$f⁡(x)=x^m+f_{m-1} x^{m-1}+⋯+f_2 x^2+f_1 x+f_0$（其中$f_i∈F_2$，$i=0,1,…,m-1$）是二元扩域$F_{2^m}$的约化多项式。$F_{2^m}$由$F_2$上所有次数低于$m$的多项式构成。多项式集合$\{x^{m-1},x^{m-2},…,x,1\}$是$F_{2^m}$是$F_2$的一组基，称为多项式基。$F_{2^m}$中的任意一个元素$a⁡(x)=a_{m-1} x^{m-1}+a_{m-2} x^{m-2}+⋯+a_1 x+a_0$在$F_2$上的系数恰好构成了长度为$m$的比特串，用$a=(a_{m-1},a_{m-2},…,a_1,a_0)$表示。

零元$0$用全0比特串表示；
乘法单位元$1$用比特串00…001表示；
两个域元素的加法为比特串的按比特异或运算；
域元素$a$和$b$的乘法定义如下：设$a$和$b$对应的$F_2$上多项式为$a⁡(x)$和$b⁡(x)$，则$a⋅b$定义为多项式$(a⁡(x) b⁡(x) )\mbox{ mod }f⁡(x)$对应的比特串；

2.1 有限域上的椭圆曲线
有限域$F_q$上的椭圆曲线是由点组成的集合。在仿射坐标系下，椭圆曲线上点$P$（非无穷远点）的坐标表示为$P=(x_P,y_P )$，其中$x_P$，$y_P$为满足一定方程的域元素，分别称为点$P$的$x$坐标和$y$坐标。此处，称$F_q$为基域。
2.1.1 $F_{2^m}$上的椭圆曲线
定义在$F_{2^m}$上的椭圆曲线方程为：

$y^2+xy=x^3+ax^2+b$，$a,b∈F_{2^m}$，且$b≠0$椭圆曲线$E⁡(F_{2^m})$定义为：
$E⁡(F_{2^m})=\{(x,y)│y^2+xy=x^3+ax^2+b,x,y∈F_{2^m}\}∪\{O\}$，其中$O$是无穷远点。
椭圆曲线$E⁡(F_{2^m})$上的点的数目用$♯⁡E⁡(F_{2^m})$表示，称为椭圆曲线$E⁡(F_{2^m})$的阶。

2.1.2 $F_{2^m}$上的椭圆曲线群
椭圆曲线$E⁡(F_{2^m})$上的点按照下面的加法运算规则，构成一个交换群：

$O+O=O$；
$∀P=(x,y)∈E⁡(F_{2^m})\backslash\{O\}$，$P+O=O+P=P$；
$∀P=(x,y)∈E⁡(F_{2^m})\backslash\{O\}$，$P$的逆元素$-P=(x,-y)$，$P+(-P)=O$；
两个非互逆的不同点相加的规则：
点$P_1=(x_1,y_1 )∈E⁡(F_{2^m})\backslash\{O\}$，$P_2=(x_2,y_2 )∈E⁡(F_{2^m})\backslash\{O\}$，且$x_1≠x_2$，设$P_3=(x_3,y_3 )=P_1+P_2$，则$\left\{ \begin{array}{l} {x_{3} = \lambda^{2} + \lambda + x_{1} + x_{2} + a} \\ {y_{3} = \lambda\left( {x_{1} + x_{3}} \right) + x_{3} + y_{1}} \end{array} \right.$其中$\lambda = \frac{y_{1} + y_{2}}{x_{1} + x_{2}}$
倍点规则：
设$P_1=(x_1,y_1 )∈E⁡(F_{2^m})\backslash\{O\}$，且$x_1≠0$，$P_3=(x_3,y_3 )=P_1+P_1$，
则$\left\{ \begin{array}{l} {x_{3} = \lambda^{2} + \lambda + a} \\ {y_{3} = x_{1}^{2} + \left( {\lambda + 1} \right)x_{3}} \end{array} \right.$其中$\lambda = x_{1} + \frac{y_{1}}{x_{1}}$

2.2 二元扩域$F_{2^m}$的定义
由$2^m$个元素构成的有限域$F_{2^m}$是$F_2$的$m$次扩张，称为$m$次二元扩域。$F_{2^m}$可以看成$F_2$上维数为$m$向量空间，也就是说，在$F_{2^m}$存在$m$个元素$α_0,α_1,…,α_{m-1}$，使得$∀α∈F_{2^m}$，$α$可以唯一表示为：$α=a_0 α_0+a_1 α_1+⋯+a_{m-1} α_{m-1}$，其中$a_i∈F_2$（$i=0,1,…,m-1$），称$\{α_0,α_1,…,α_{m-1} \}$为$F_{2^m}$在$F_2$上的基。给定这样一组基，就可以由向量$(a_0,a_1,…,a_{m-1})$来表示域元素$α$。$F_{2^m}$在$F_2$上的基有多种选择，域元素的加法在不同的基下的元素规则是一致的，都可以通过向量按分量异或运算得到；域元素的乘法在不同的基下有不同的运算规则（如用多项式基表示和用正规基表示时其运算规则就不一致）。
2.2.1 多项式基
设$F_2$上$m$次不可约多项式$f⁡(x)=x^m+f_{m-1} x^{m-1}+⋯+f_2 x^2+f_1 x+f_0$（其中$f_i∈F_2$，$i=0,1,…,m-1$）是二元扩域$F_{2^m}$的约化多项式。$F_{2^m}$由$F_2$上所有次数低于$m$的多项式构成，即：

$F_{2^m}=\{a_{m-1} x^{m-1}+a_{m-2} x^{m-2}+⋯+a_1 x+a_0│a_i∈F_2,i=0,1,…,m-1\}$多项式集合$\{x^{m-1},x^{m-2},…,x,1\}$是$F_{2^m}$作为向量空间在$F_2$上的一组基，称为多项式基。
域元素集合$a_{m-1} x^{m-1}+a_{m-2} x^{m-2}+⋯+a_1 x+a_0$相对多项式基可以由长度为$m$的比特串$(a_{m-1} a_{m-2}…a_1 a_0 )$来表示，所以$F_{2^m}=\{(a_{m-1} a_{m-2}…a_1 a_0 )│a_i∈F_2,i=0,1,…,m-1\}$乘法单位元$1$由$(00…01)$表示，零元由$(00…00)$表示。域元素的加法和乘法定义如下：
——加法运算
$∀(a_{m-1} a_{m-2}…a_1 a_0 ),(b_{m-1} b_{m-2}…b_1 b_0 )∈F_{2^m}$，则$(a_{m-1} a_{m-2}…a_1 a_0 )+(b_{m-1} b_{m-2}…b_1 b_0 )=(c_{m-1} c_{m-2}…c_1 c_0 )$，其中$c_i=a_i⊕b_i$，$i=0,1,…,m-1$，亦即，加法运算按分位异或运算执行。
——乘法运算
$∀(a_{m-1} a_{m-2}…a_1 a_0 ),(b_{m-1} b_{m-2}…b_1 b_0 )∈F_{2^m}$，则$(a_{m-1} a_{m-2}…a_1 a_0 )⋅(b_{m-1} b_{m-2}…b_1 b_0 )=(r_{m-1} r_{m-2}…r_1 r_0 )$，其中多项式$(r_{m-1} x^{m-1}+r_{m-2} x^{m-2}+⋯+r_1 x+r_0 )$是$(a_{m-1} x^{m-1}+a_{m-2} x^{m-2}+⋯+a_1 x+a_0 )⋅(b_{m-1} x^{m-1}+b_{m-2} x^{m-2}+⋯+b_1 x+b_0 )$在$F_2$上$\mbox{mod }f⁡(x)$的余式。
注意，$F_{2^m}$恰包含$2^m$个元素。记$F_{2^m}^*$是由$F_{2^m}$中所有非零元构成的乘法群，$F_{2^m}^*$是循环群，在$F_{2^m}$中至少存在一个元素$g$，使得$F_{2^m}$中任一非零元都可以由$g$的一个方幂并表示，称$g$为$F_{2^m}^*$的生成元（或本原元），即：$F_{2^m}^*=\{g^i│0≤i≤2^m-2\}$。设$a=g^i∈F_{2^m}^*$，其中$0≤i≤2^m-2$，则$a$的乘法逆元为：$a^{-1}=g^{2^m-1-i}$。

2.2.2 正规基
形如$\{β,β^2,β^{2^2},…,β^{2^{m-1}}\}$的基就是$F_{2^m}$在$F_2$上的一组正规基，其中$β∈F_{2^m}$。这样的基总是存在的。$∀α∈F_{2^m}$，则$α=a_0 β^{2^0}+a_1 β^{2^1}+⋯+a_{m-1} β^{2^{m-1}}$，其中$a_i∈F_2$（$i=0,1,…,m-1$），并记为$α=(a_0 a_1 a_2…a_{m-2} a_{m-1} )$，域元素$α$由长度为$m$的比特串表示。所以$F_{2^m}=\{(a_0 a_1 a_2…a_{m-2} a_{m-1} )│a_i∈F_2,0≤i≤m-1\}$，乘法单位元$1$由$m$个1的比特串$(11…1)$表示，零元由$m$个0的比特串$(00…0)$表示。
在正规基表示下，$F_{2^m}$中求平方运算时循环右移运算：

$\forall\alpha \in F_{2^{m}},\alpha = a_{0}\beta^{2^{0}} + a_{1}\beta^{2^{1}} + \ldots + a_{m - 1}\beta^{2^{m - 1}} = \left( {a_{0}a_{1}a_{2}\ldots a_{m - 2}a_{m - 1}} \right),\alpha^{2} = \left( {\sum\limits_{i = 0}^{m - 1}{a_{i}\beta^{2^{i}}}} \right)^{2} = {\sum\limits_{i = 0}^{m - 1}{a_{i}^{2}\beta^{2^{i + 1}}}} = {\sum\limits_{i = 0}^{m - 1}{a_{i}\beta^{2^{i}}}} = \left( {a_{m - 1}a_{0}\ldots a_{m - 2}} \right)$在这种情况下，求平方运算只是长度为$m$的比特串的循环移位，便于在硬件上实现。

2.2.3 高斯正规基
由2.2.2节可知，$F_{2^m}$在$F_2$上的正规基是形式为$N=\{β,β^2,β^{2^2},…,β^{2^{m-1}}\}$的一组基，其中$β∈F_{2^m}$。正规基表示在求取元素的平方时有计算优势，但对于一般意义下的不同元素的乘法运算不太方便。因此，通常专用一种称为高斯正规基的基，对这样的基，乘法既简单又有效。
当$m$不能被$8$整除时$F_{2^m}$存在高斯正规基。高斯正规基的类型$T$是指在此基下度量乘法运算复杂度的一个正整数。一般情况下，类型$T$愈小，乘法效率愈高。对于给定的$m$和$T$，域$F_{2^m}$至多有一个类型$T$的高斯正规基。在所有正规基中，类型1和类型2的高斯正规基有最有效的乘法运算，因而也称它们为最优正规基。类型1的高斯正规基称为Ⅰ型最优正规基，类型2的高斯正规基称为Ⅱ型最优正规基。
有限域$F_{2^m}$中的元素$a$在高斯正规基下可以由长度为$m$的比特串$(a_{m-1} a_{m-2}…a_1 a_0 )$来表示。

乘法单位元$1$由$m$个1的比特串表示；
零元$0$由$m$个0的比特串表示；
两个域元素的加法由比特串对位异或运算完成；
域元素的乘法在2.2.3.3节中描述。

2.2.3.1 选择正规基的规则
选择$F_{2^m}$存在的最小类型的高斯正规基。

2.2.3.2 高斯正规基的检验
给定类型$T$，利用下述算法可以检验$F_{2^m}$（$m$大于$1$且不能被$8$整除）中类型$T$的高斯正规基的存在性。
输入：大于$1$且不被$8$整除的整数$m$，正整数$T$。
输出：若$F_{2^m}$存在一个类型$T$的高斯正规基，输出“正确”；否则输出“错误”。

计算$p=T⋅m+1$；
若$p$不是素数，则输出“错误”并停止；
计算$2$模$p$的阶$k$；
计算$u=T⋅m⁄k$；
计算$d=\mbox{gcd}⁡(u,m)$；
若$d=1$，则输出“正确”；否则输出“错误”。

2.2.3.3 高斯正规基下的乘法算法
对于任意给定的高斯正规基，其乘法运算包含三部分：乘法预运算；给定两个元素后，其乘积的第一项$c_0$的公式，计算两个元素的乘积。下面对这三部分进行详细描述：
——乘法预运算：
输入：大于$1$的整数$m$，正整数$T$，其中在$F_{2^m}$上存在类型T的高斯正规基$B$。
输出：相对于$B$的序列$f⁡(1),f⁡(2),…,f⁡(p-1)$。

计算$p=T⋅m+1$；
产生模$p$阶为$T$的整数$u$；
计算序列$f⁡(1),f⁡(2),…,f⁡(p-1)$；
3.1. 置$w=1$；
3.2. 从$j=0$到$T-1$执行：
3.2.1. 置$n=w$；
3.2.2. 从$i=0$到$m-1$执行：
3.2.2.1. 置$f⁡(n)=i$；
3.2.2.2. 置$n=2n\mbox{ mod }p$；
3.2.2.3. 置$w=u⋅w\mbox{ mod }p$；
输出序列$f⁡(1),f⁡(2),…,f⁡(p-1)$。

——给定在高斯正规基$B$表示下的两个域元素$a$和$b$，其乘积的第一项$c_0$的公式：
记$c_0=F⁡(a,b)$。
输入：大于$1$的整数$m$，正整数$T$（其中在$F_{2^m}$上存在类型T的高斯正规基$B$）及在高斯正规基$B$表示下的两个域元素$a$、$b$。
输出：在高斯正规基$B$表示下的两个域元素$a$、$b$乘积的第一项$c_0$的公式。

利用乘法预运算得到输出序列$f⁡(1),f⁡(2),…,f⁡(p-1)$；
$T$为偶数，则$J=0$，否则$J = {\sum\limits_{k = 1}^{m}\left( {a_{k - 1}b_{{m/2} + k - 1} + a_{{m/2} + k - 1}b_{k - 1}} \right)}$
输出公式$c_{0} = J + {\sum\limits_{k = 1}^{p - 2}{a_{f{({k + 1})}}b_{f{({p - k})}}}}$

——利用域元素$a$和$b$乘积的第一项$c_0$的公式，计算域元素$a$和$b$的乘积：
对$u=(u_0 u_1…u_{m-1} )，v=(v_0 v_1…v_{m-1} )$，设$F⁡(u,v)$是以$c_0=F⁡(a,b)$导出的表达式。
输入：大于$1$的整数$m$，正整数$T$（其中在$F_{2^m}$上存在类型$T$的高斯正规基$B$）及在高斯正规基$B$表示下的两个域元素$a$、$b$。
输出：积$(c_0 c_1…c_{m-1} )=(a_0 a_1…a_{m-1} )×(b_0 b_1…b_{m-1} )$。

置$(u_0 u_1…u_{m-1} )=(a_0 a_1…a_{m-1} )$；
置$(v_0 v_1…v_{m-1} )=(b_0 b_1…b_{m-1} )$；
对$k$从$0$到$m-1$执行：
3.1. 计算$c_k=F⁡(u,v)$；
3.2. 置$u=LeftRotate⁡(u)$，并置$v=LeftRotate⁡(v)$，其中$LeftRotate⁡()$表示循环左移1位运算，即$LeftRotate⁡(u)=LeftRotate⁡(u_0 u_1…u_{m-1} )=(u_1 u_2…u_{m-1} u_0 )$；
输出$c=(c_0 c_1…c_{m-1} )$。

2.3 $F_{2^m}$上椭圆曲线的定义
2.3.1 概述
$F_{2^m}$上椭圆曲线常用的表示形式有两种：仿射坐标表示和射影坐标表示。

2.3.2 仿射坐标表示
$F_{2^m}$上非超奇异椭圆曲线方程在仿射坐标系下可以简化为$y^2+xy=x^3+ax^2+b$，其中$a,b∈F_{2^m}$，且$b≠0$。椭圆曲线上的点集记为$E⁡(F_{2^m})=\{(x,y)│y^2+xy=x^3+ax^2+b,x,y∈F_{2^m}\}∪\{O\}$，其中$O$是椭圆曲线的无穷远点，又称为零点。
$E⁡(F_{2^m})$上的点按照下面的加法运算规则，构成一个阿贝尔群：

$O+O=O$；
$∀P=(x,y)∈E⁡(F_{2^m})\backslash\{O\}$，$P+O=O+P=P$；
$∀P=(x,y)∈E⁡(F_{2^m})\backslash\{O\}$，$P$的逆元素$-P=(x,x+y)$，$P+(-P)=O$；
两个非互逆的不同点相加的规则：
设$P_1=(x_1,y_1 )∈E⁡(F_{2^m})\backslash\{O\}$，$P_2=(x_2,y_2 )∈E⁡(F_{2^m})\backslash\{O\}$，且$x_1≠x_2$，设$P_3=(x_3,y_3 )=P_1+P_2≠O$，则：$\left\{ \begin{array}{l} {x_{3} = \lambda^{2} + \lambda + x_{1} + x_{2} + a} \\ {y_{3} = \lambda\left( {x_{1} + x_{3}} \right) + x_{3} + y_{1}} \end{array} \right.$其中$λ=\frac{y_1+y_2}{x_1+x_2}$；
倍点规则：
设$P_1=(x_1,y_1 )∈E⁡(F_{2^m})\backslash\{O\}$且$x_1≠0$，$P_3=(x_3,y_3 )=P_1+P_1$，则：$\left\{ \begin{array}{l} {x_{3} = \lambda^{2} + \lambda + a} \\ {y_{3} = x_{1}^{2} + \left( {\lambda + 1} \right)x_{3}} \end{array} \right.$其中$λ=x_1+\frac{y_1}{x_1}$。

2.3.3 射影坐标表示
2.3.3.1 标准射影坐标系
$F_{2^m}$上非超奇异椭圆曲线方程在标准射影坐标系下可以简化为$y^2 z+xyz=x^3+ax^2 z+bz^3$，其中$a,b∈F_{2^m}$，且$b≠0$。$E⁡(F_{2^m})=\{(x,y,z)│y^2 z+xyz=x^3+ax^2 z+bz^3,x,y,z∈F_{2^m}\}$。对于$(x_1,y_1,z_1 )$和$(x_2,y_2,z_2 )$，若存在某个$u∈F_{2^m}$且$u≠0$，使得：$x_1=ux_2$，$y_1=uy_2$，$z_1=uz_2$，则称这两个三元组等价，表示同一个点。
若$z≠0$，记$X=x⁄z$，$Y=y⁄z$，则可从标准射影坐标表示转化为仿射坐标表示：$Y^2+XY=X^3+aX^2+b$；
若$z=0$，$(0,1,0)$对应的仿射坐标系下的点即无穷远点$O$。
标准射影坐标系下，$E⁡(F_{2^m})$上点的加法运算定义如下：
椭圆曲线$E⁡(F_{2^m})$上的点按照下面的加法运算规则，构成一个交换群：

$O+O=O$；
$∀P=(x,y,z)∈E⁡(F_{2^m})\backslash\{O\}$，则$P+O=O+P=P$；
$∀P=(x,y,z)∈E⁡(F_{2^m})\backslash\{O\}$，$P$的逆元素$-P=(ux,u(x+y),uz)$，$u∈F_{2^m}$且$u≠0$，$P+(-P)=O$；
设点$P_1=(x_1,y_1,z_1 )∈E⁡(F_{2^m})\backslash\{O\}$，$P_2=(x_2,y_2,z_2 )∈E⁡(F_{2^m})\backslash\{O\}$，$P_3=P_1+P_2=(x_3,y_3,z_3 )≠O$，
若$P_1≠P_2$，则：
$λ_1=x_1 z_2$，$λ_2=x_2 z_1$，$λ_3=λ_1+λ_2$，$λ_4=y_1 z_2$，$λ_5=y_2 z_1$，$λ_6=λ_4+λ_5$，$λ_7=z_1 z_2$，$λ_8=λ_3^2$，$λ_9=λ_8 λ_7$，$λ_10=λ_3 λ_8$，$λ_11=λ_6 λ_7 (λ_6+λ_3 )+λ_10+aλ_9$，$x_3=λ_3 λ_11$，$y_3=λ_6 (λ_1 λ_8+λ_11 )+x_3+λ_10 λ_4$，$z_3=λ_3 λ_9$；
若$P_1=P_2$，则：
$λ_1=x_1 z_1$，$λ_2=x_1^2$，$λ_3=λ_2+y_1 z_1$，$λ_4=λ_1^2$，$λ_5=λ_3 (λ_1+λ_3 )+aλ_4$，$x_3=λ_1 λ_5$，$y_3=λ_2^2 λ_1+λ_3 λ_5+x_3$，$z_3=λ_1 λ_4$。

2.3.3.2 Jacobian加重映射坐标系
$F_{2^m}$上非超奇异椭圆曲线方程在Jacobian加重射影坐标系下可以简化为$y^2 z+xyz=x^3+ax^2 z^2+bz^6$，其中$a,b∈F_{2^m}$，且$b≠0$。$E⁡(F_{2^m})=\{(x,y,z)│y^2 z+xyz=x^3+ax^2 z^2+bz^6,x,y,z∈F_{2^m}\}$。对于$(x_1,y_1,z_1 )$和$(x_2,y_2,z_2 )$，若存在某个$u∈F_{2^m}$且$u≠0$，使得：$x_1=u^2 x_2$，$y_1=u^3 y_2$，$z_1=uz_2$，则称这两个三元组等价，表示同一个点。
若$z≠0$，记$X=x⁄z^2$，$Y=y⁄z^3$，则可从Jacobian加重射影坐标表示转化为仿射坐标表示：$Y^2+XY=X^3+aX^2+b$；
若$z=0$，$(1,1,0)$对应的仿射坐标系下的点即无穷远点$O$。
Jacobian加重射影坐标系下，$E⁡(F_{2^m})$上点的加法运算定义如下：
椭圆曲线$E⁡(F_{2^m})$上的点按照下面的加法运算规则，构成一个交换群：

$O+O=O$；
$∀P=(x,y,z)∈E⁡(F_{2^m})\backslash\{O\}$，则$P+O=O+P=P$；
$∀P=(x,y,z)∈E⁡(F_{2^m})\backslash\{O\}$，$P$的逆元素$-P=(u^2 x,u^2 x+u^3 y,uz)$，$u∈F_{2^m}$且$u≠0$，$P+(-P)=O$；
设点$P_1=(x_1,y_1,z_1 )∈E⁡(F_{2^m})\backslash\{O\}$，$P_2=(x_2,y_2,z_2 )∈E⁡(F_{2^m})\backslash\{O\}$，$P_3=P_1+P_2=(x_3,y_3,z_3 )≠O$，
若$P_1≠P_2$，则：
$λ_1=x_1 z_2^2$，$λ_2=x_2 z_1^2$，$λ_3=λ_1+λ_2$，$λ_4=y_1 z_2^3$，$λ_5=y_2 z_1^3$，$λ_6=λ_4+λ_5$，$λ_7=z_1 λ_3$，$λ_8=λ_6 x_2+λ_7 y_2$，$z_3=λ_7 z_2$，$λ_9=λ_6+z_3$，$x_3=az_3^2+λ_6 λ_9+λ_3^3$，$y_3=λ_9 x_3-λ_8 λ_7^2$；
若$P_1=P_2$，则：
$z_3=x_1 z_1^2$，$x_3=x_1^4+bz_1^8$，$λ=z_3+x_1^2+y_1 z_1$，$y_3=x_1^4 z_3+λx_3$。

2.4 $F_{2^m}$上椭圆曲线的阶
$F_{2^m}$上一条椭圆曲线E的阶是指点集$E⁡(F_{2^m})$中元素的个数，记为$♯⁡E⁡(F_{2^m})$。
由Hasse定理知：$2^m+1-2p^{1⁄2}≤♯⁡E⁡(F_{2^m}) ≤2^m+1+2p^{1⁄2}$。

3 椭圆曲线多倍点运算
3.1 概述
设$P$是椭圆曲线$E$上阶为$N$的点，$k$为正整数，$P$的$k$倍点为$Q$，即

$Q = \lbrack k\rbrack P = \underset{k\text{个}}{\underbrace{P + P + \cdots + P}}$

3.2 椭圆曲线多倍点运算的实现
椭圆曲线多倍点运算的实现有多种方法，这里给出三种方法，以下都假设$1≤k<N$。
算法一：二进制展开法
输入：点$P$，$l$比特的整数$k = {\sum\limits_{j = 0}^{l - 1}{k_{j}2^{j}}}$，$k_j∈\{0,1\}$。
输出：$Q=[k]P$。

置$Q=O$;
$j$从$l-1$下降到$0$执行：
2.1. $Q=[2]Q$；
2.2. 若$k_j=1$，则$Q=Q+P$；
输出$Q$。

算法二：加减法
输入：点$P$，$l$比特的整数$k = {\sum\limits_{j = 0}^{l - 1}{k_{j}2^{j}}}$，$k_j∈\{0,1\}$。
输出：$Q=[k]P$。

设$3k$的二进制表示是$h_r h_{r-1}…h_1 h_0$，其中最高位$h_r$为$1$；
设$k$的二进制表示是$k_r k_{r-1}…k_1 k_0$，显然$r=l$或$l+1$；
置$Q=P$；
对$i$从$r-1$下降到$1$执行：
4.1. $Q=[2]Q$；
4.2. 若$h_i=1$，且$k_i=0$，则$Q=Q+P$；
4.3. 若$h_i=0$，且$k_i=1$，则$Q=Q-P$；
输出$Q$。

算法三：滑动窗法
输入：点$P$，$l$比特的整数$ k = {\sum\limits_{j = 0}^{l - 1}{k_{j}2^{j}}}$，$k_j∈\{0,1\}$。
输出：$Q=[k]P$。
设窗口长度$r>1$。
预计算

$P_1=P$，$P_2=[2]P$；
$i$从$1$到$2^{r-1}-1$计算$P_{2i+1}=P_{2i-1}+P_2$；
置$j=l-1$，$Q=O$。

主循环

当$j≥0$执行：
4.1. 若$k_j=0$，则$Q=[2]Q$，$j=j-1$；
4.2. 否则
4.2.1. 令$t$是使$j-t+1≤r$且$k_t=1$的最小整数；
4.2.2. $ h_{j} = {\sum\limits_{i = 0}^{j - t}{k_{t + i}2^{i}}}$；
4.2.3. $Q=[2^{j-t+1}]Q+P_{h_j}$；
4.2.4. 置$j=t-1$；
输出$Q$。

4 $F_{2^m}$上椭圆曲线系统参数及其验证
椭圆曲线系统参数是可以公开的，系统的安全性不依赖于对这些参数的保密。
4.1 $F_{2^m}$上椭圆曲线系统参数
$F_{2^m}$上椭圆曲线系统参数包括：

域的规模$q=2^m$，对$F_{2^m}$中元素表示法的标识，一个$F_2$上的$m$次约化多项式；
（选项）一个长度至少为192的比特串$SEED$；
$F_{2^m}$中的两个元素$a$和$b$，它们定义椭圆曲线E的方程：$y^2+xy=x^3+ax^2+b$；
基点$G=(x_G,y_G )∈E⁡(F_{2^m})$，$G≠O$；
基点$G$的阶$n$（要求：$n>2^{191}$且$n>2^{2+m⁄2}$）；
（选项）余因子$h=♯⁡E⁡(F_{2^m})⁄n$。

4.2 $F_{2^m}$上椭圆曲线系统参数的验证
椭圆曲线系统参数的生成者应验证下面的条件。椭圆曲线系统参数的用户可以选择验证这些条件。
输入：$F_{2^m}$上椭圆曲线系统参数的集合。
输出：若椭圆曲线系统参数是有效的，则输出“有效”；否则输出“无效”。

对某个$m$，验证$q=2^m$；若所用的是TPB，则验证约化多项式是$F_2$上的不可约三项式；若所用的是PPB，则验证不存在$m$次不可约三项式，且约化多项式是$F_2$上的不可约五项式；若所用的是GNB，则验证$m$不能被$8$整除；
验证$a$、$b$、$x_G$和$y_G$是长度为$m$的比特串；
若按照4.3节描述的方法拟随机产生椭圆曲线，验证$SEED$是长度至少为192的比特串，且$a$，$b$由$SEED$派生得到；
验证$b≠0$；
在$F_{2^m}$中验证$y_G^2+x_G y_G=x_G^3+ax_G^2+b$；
验证$n$是素数，$n>2^{191}$且$n>2^{2+m⁄2}$（参见4.5节）；
验证$[n]G=O$；
（选项）计算$h'=⌊(2^{m⁄2}+1)^2⁄n⌋$，并验证$h=h'$；
验证抗MOV攻击条件成立（参见4.6.1节）；
若以上任何一个验证失败，则输出“无效”；否则，输出“有效”。

4.3 $F_{2^m}$上椭圆曲线系统参数的拟随机生成
输入：域的规模$q=2^m$，$F_{2^m}$的约化多项式$f⁡(x)=x^m+f_{m-1} x^{m-1}+⋯+f_2 x^2+f_1 x+f_0$（其中$f_i∈F_2$，$i=0,1,…,m-1$）。
输出：比特串$SEED$及$F_{2^m}$中的元素$a$，$b$。

任意选择长度至少为192的比特串$SEED$；
计算$H=H_{256}⁡(SEED)$，并记$H=(h_{255},h_{254},…,h_0 )$；
若$i≥256$，令$h_i=1$，置比特串$HH=(h_{m-1},h_{m-2},…,h_0 )$，$b$为与$HH$对应的$F_{2^m}$中的元素；
若$b=0$，则转步骤1；
取$a$为$F_{2^m}$中的任意元素；
所选择的$F_{2^m}$上的椭圆曲线为$E:y^2+xy=x^3+ax^2+b$；
输出$(SEED,a,b)$。

4.4 $F_{2^m}$上椭圆曲线系统参数拟随机生成的验证
输入：比特串$SEED$及$F_{2^m}$中的元素$a$，$b$。
输出：输入参数“有效”或“无效”。

计算$H'=H_{256}⁡(SEED)$，并记$H'=(h_{255},h_{254},…,h_0 )$；
若$i≥256$，令$h_i=1$，置比特串$HH'=(h_{m-1},h_{m-2},…,h_0 )$，$b'$为与$HH'$对应的$F_{2^m}$中的元素；
若$b'=b$，则输出“有效”；否则输出“无效”。

4.5 概率素性检查
$u$是一个大的正整数，下面的改了算法（Miller-Rabin检测）将确定$u$使素数还是合数。
输入：一个大的奇数$u$和一个大的正整数$T$。
输出：“概率素数”或“合数”。

计算$v$和奇数$w$，使得$u-1=2^v⋅w$；
对$j$从$1$到$T$执行：
2.1. 在区间$[2,u-1]$中选取随机数$a$；
2.2. 置$b=a^w\mbox{ mod }u$；
2.3. 若$b=1$或$u-1$，转到步骤2.6；
2.4. 对$i$从$1$到$v-1$执行：
2.4.1. 置$b=b^2\mbox{ mod }u$；
2.4.2. 若$b=u-1$，转到步骤2.6；
2.4.3. 若$b=1$，输出“合数”并终止；
2.4.4. 下一个$i$；
2.5. 输出“合数”，并终止；
2.6. 下一个$j$；
输出“概率素数”。

若算法输出“合数”，则$u$是一个合数。若算法输出“概率素数”，在$u$是合数的概率小于$2^{-2T}$。这样，通过选取足够大的$T$，误差可以忽略。

4.6 安全椭圆曲线满足的条件
4.6.1 抗MOV攻击条件
A. Menezes、T. Okamoto、S. Vanstone、G. Frey和H. Rück的约化攻击将有限域$F_q$上的椭圆曲线离散对数问题约化为$F_{q^B}$（$B>1$）上的离散对数问题。这个攻击方法只有在$B$较小时是实用的，大多数椭圆曲线不符合这种情况。抗MOV攻击条件确保一条椭圆曲线不易受此约化方法攻击。多数$F_q$上的椭圆曲线确实满足抗MOV攻击条件。
在验证抗MOV攻击条件之前，必须选择一个MOV阈，它是使得求取$F_{q^B}$上的离散对数问题至少与求取$F_q$上的椭圆曲线离散对数问题同样难的一个正整数$B$。对于$q>2^{191}$的标准，要求{B≥27}。选择$B≥27$也限制了对非超奇异椭圆曲线的选取。
下述算法用于验证椭圆曲线系统参数是否满足抗MOV攻击条件。
输入：MOV阈$B$，素数幂$q$和素数$n$（$n$是$♯⁡E⁡(F_q )$ 的素因子，其中$E⁡(F_q )$是$F_q$上的椭圆曲线）。
输出：若$F_q$上包含$n$阶基点的椭圆曲线满足抗MOV攻击条件，则输出“正确”；否则输出“错误”。

置$t=1$；
对$i$从$1$到$B$执行：
2.1. 置$t=(t⋅q)\mbox{ mod }n$；
2.2. 若$t=1$，则输出“错误”并结束；
输出“正确”。

5 密钥对的生成与公钥的验证
5.1 密钥对的生成
输入：一个有效的$F_q$（$q=2^m$）上椭圆曲线系统参数的集合。
输出：与椭圆曲线系统参数相关的一个密钥对$(d,P)$。

用随机数发生器产生整数$d∈[2,n-2]$；
$G$为基点，计算点$P=(x_P,y_P )=[d]G$;
密钥对是$(d,P)$，其中$d$为私钥，$P$为公钥。

5.2 $F_{2^m}$上椭圆曲线公钥的验证
输入：一个有效的$F_{2^m}$上椭圆曲线系统参数集合及一个相关的公钥$P$。
输出：对于给定的椭圆曲线系统参数，若公钥$P$是有效的，则输出“有效”；否则输出“无效”。

验证$P$不是无穷远点$O$；
验证公钥$P$的坐标$x_P$和$y_P$是域$F_{2^m}$中的元素（即验证$x_P$和$y_P$是长度为$m$的比特串）；
在$F_{2^m}$中验证$y_P^2+x_P y_P=x_P^3+ax_P^2+b$；
验证$[n]P=O$；
若通过了所有验证，则输出“有效”；否则输出“无效”。

6 曲线示例：$F_{2^m}$上椭圆曲线
椭圆曲线方程为：$y^2+xy=x^3+ax^2+b$
示例1：$F_{2^m}$-193曲线

基域生成多项式：$x^{193}+x^{15}+1$

系数$a$：	0
系数$b$：	00	2FE22037	B624DBEB	C4C618E1	3FD998B1	A18E1EE0	D05C46FB

基点$G=(x,y)$，其阶记为$n$。

坐标$x$：	00	D78D47E8	5C936440	71BC1C21	2CF994E4	D21293AA	D8060A84
坐标$y$：	00	615B9E98	A31B7B2F	DDEEECB7	6B5D8755	86293725	F9D2FC0C
阶$n$：		80000000	00000000	00000000	43E9885C	46BF45D8	C5EBF3A1

示例2：$F_{2^m}$-256曲线

基域生成多项式：$x^{257}+x^{12}+1$

系数$a$：	0
系数$b$：	00	E78BCD09	746C2023	78A7E72B	12BCE002	66B9627E	CB0B5A25	367AD1AD	4CC6242B

基点$G=(x,y)$，其阶记为$n$。

坐标$x$：	00	CDB9CA7F	1E6B0441	F658343F	4B10297C	0EF9B649	1082400A	42E7A748	5735FADD
坐标$y$：	00	3DE74DA6	5951C4D7	6DC89220	D5F7777A	611B1C38	BAE260B1	75951DC8	060C2B3E
阶$n$：		7FFFFFFF	FFFFFFFF	FFFFFFFF	FFFFFFFF	BC972CF7	E6B6F900	945B3C6A	0CF6161D

参考
GM/T 0003.1—2012

标签：输出,椭圆,运算,比特,元素,SM2,曲线
From： https://www.cnblogs.com/miro-cnblogs/p/18474434

SM2 - $F_{2^m}$

相关文章

赞助商

阅读排行