椭圆曲线点加运算硬件实现数学原理

有限域取模运算:

设$f(x)=x^m + x^k +1 $

设$c(x)=c_{2m-2}x^{2m-2} + c_{2m-3}x^{2m-3} +…c_{m}x^{m}+ …c_{2}x^{2} + c_{1}x +c_0 $

$c(x)=(c_{2m-2}{x}^{m-2}+c_{2m-3}{x}^{m-3}+c_{2m-4}{x}^{m-4}+...c_m)(x^k+1)+c_{m-1}{x}^{m-1}+c_{m-2}{x}^{m-2}+...c_{1}x+c_0$

根据同余性质： $x^m\equiv x^k+1mod(x^m+x^k+1)$ 所以$x^{2m-2}\equiv x^{m-2}(x^k+1)mod(x^m+x^k+1)$

在$c(x)$ 两边同时加上$c_{2m-2}f(x)x^{m-2}$ 得：

$$\begin{gathered} c(x)+c_{2m-2}f(x)x^{m-2}=(c_{2m-2}{x}^{m-2}+c_{2m-3}{x}^{m-3}+c_{2m-4}{x}^{m-4}+...c_m)(x^k+1)+c_{m-1}{x}^{m-1}+c_{m-2}{x}^{m-2}+...c_{1}x+c_0+c_{2m-2}(x^m+x^k+1)x^{m-2} \\ =((c_{2m-2}+c_{2m-2})x^{m-2}+c_{2m-3}{x}^{m-3}...+c_m)(x^k+1)+c_{m-1}{x}^{m-1}+c_{m-2}{x}^{m-2}+...c_{1}x+c_0+c_{2m-2}{x}^{k+m-2}+c_{2m-2}{x}^{m-2} \end{gathered}$$

这样可以消去$c(x)$ 中$x^{m-2}$ 项，以此类推，在左右两边同时加上$c_{2m-2}{x}^{m-2}{c}_{2m-3}{x}^{m-3}{c}_{2m-4}{x}^{m-4}...$ 可以同时计算32位，硬件一个周期完成32位的约减。通过这样不断约减直到$x^{m-1}$ 即为最后结果。

以$f(x)=x^{257}+x^{12}+1$ 为例： $ m=257 k=12 2(m-1)=512$

约减的最后一位是$x^m$所以约减顺序如下：$ [512-481] [480-449] [448-417] [416-385] [384-353] [352-321] [320-289] [288-257] $ 需要进行8次循环，8个周期。

$$\begin{gathered} c(x)+c_{2m-2}f(x)x^{m-2}+c_{2m-3}f(x)x^{m-3}+c_{2m-4}f(x)x^{m-4}+...+c_{2m-33}f(x)x^{m-33}=((c_{2m-2}+c_{2m-2})x^{m-2}+(c_{2m-3}+c_{2m-3})x^{m-3} \\ +...(c_{2m-33}+c_{2m-33})x^{m-33}+c_{2m-34}{x}^{m-34}+...c_m)(x^k+1)+c_{m-1}{x}^{m-1}+c_{m-2}{x}^{m-2}+...c_0+ \\ {c}_{2m-2}{x}^{k+m-2}+c_{2m-2}{x}^{m-2}+c_{2m-3}{x}^{k+m-3}+c_{2m-3}{x}^{m-3}+...c_{2m-33}{x}^{k+m-33}+c_{2m-33}{x}^{m-33} \\ =(c_{2m-34}{x}^{m-34}+...c_m)(x^k+1)+c_{m-1}{x}^{m-1}+c_{m-2}{x}^{m-2}+...c_0+c_{2m-2}{x}^{k+m-2}+c_{2m-2}{x}^{m-2}+c_{2m-3}{x}^{k+m-3}+c_{2m-3}{x}^{m-3}+...c_{2m-33}{x}^{k+m-33}+c_{2m-33}{x}^{m-33} \end{gathered}$$

当$k-a>=0$ 时将其转为$x^{k-a}(x^k+1)$ 与前项合并。

第一次循环： (循环中+为异或运算)

$$\begin{gathered} c(x)=(c_{480}{x}^{223}+c_{479}{x}^{222}+c_{478}{x}^{221}+...+c_{258}x+c_{257}+c_{512}{x}^{10}+c_{511}{x}^9+c_{510}{x}^8+...c_{502})(x^k+1) \\ +(c_{501}{x}^{256}+c_{500}{x}^{255}+c_{499}{x}^{254}+...c_{481}{x}^{236})+(c_{512}{x}^{255}+c_{511}{x}^{254}+...c_{481}{x}^{224}) \end{gathered}$$

​ $$\begin{gathered} =(c_{480}{x}^{223}+c_{479}{x}^{222}+c_{478}{x}^{221}+...(c_{267}+c_{512})x^{10}+(c_{266}+c_{511})x^9+(c_{265}+c_{510})x^8+...(c_{257}+c_{502}))(x^k+1) \\ +(c_{501}{x}^{256}+c_{500}{x}^{255}+c_{499}{x}^{254}+...c_{481}{x}^{236})+(c_{512}{x}^{255}+c_{511}{x}^{254}+...c_{481}{x}^{224}) \end{gathered}$$

此次循环在一个周期内约减了32位，除去控制信号只需要一个512位寄存器然后对自己进行64次异或运算即可，之后的循环只需添加控制信号即可而不需要额外寄存器，8个循环后即可得到m位约减结果。

有限域平方运算：

令$A(x)={\sum }_{i=0}^{n-1}{a}_i{x}^i$ 为$GF(2^n)$上的任意元素

以$n=5$为例：

$$\begin{gathered} (a_4{x}^4+a_3{x}^3+a_2{x}^2+a_{1}x+a_0)\ast (a_4{x}^4+a_3{x}^3+a_2{x}^2+a_{1}x+a_0)=(a_4{a}_4)x^8+(a_3{a}_4+a_3{a}_4)x^7+(a_2{a}_4+a_3{a}_3+a_2{a}_4)x^6+ \\ (a_1{a}_4+a_4{a}_1+a_2{a}_3+a_3{a}_2)x^5+(a_1{a}_3+a_3{a}_1+a_2{a}_2+a_0{a}_4+a_4{a}_0)x^4+(a_0{a}_3+a_3{a}_0+a_1{a}_2+a_2{a}_1)x^3+(a_0{a}_2+a_2{a}_0+a_1{a}_1)x^2+(a_0{a}_1+a_1{a}_0)x+a_0{a}_0 \end{gathered}$$

$=(a_4{a}_4)x^8+(a_3{a}_3)x^6+(a_2{a}_2)x^4+(a_1{a}_1)x^2+a_0{a}_0$

$A^2(x)$ 结果的奇数项为0

所以$q(x)={\sum }_{i=0}^{n-1}{q}_i{x}_i=A^2(x)modf(x)=a_0+a_1{x}^2+...a_{n-1}{x}^{2n-2}modf(x)$

令$A(x^2)={\sum }_{i=0}^{n-1}{a}_i{x}^{2i}={\sum }_{i=0}^{2n-2}{b}_i{x}_i$,其中当i为偶数$b_i=a_{i/2}$，当i为奇数时$b_i=0$

令$c_i=sum_{i=0}^{n + 2i}b_ix^i mod f(x) $ 当$i$为偶数时，令$i=0,1,2,\frac{n}{2}-1$ 当$i$为奇数时令$i=0，1，\mathrm{2...}\frac{n-3}{2}$

n为偶数时：$q(x)={\sum }_{i=0}^{2n-2}{b}_i{x}^{i}modf(x)=c_{\frac{n}{2}-1}$ (只需令$b_i$ 在奇数位为0即可)

n为奇数时：$q(x)={\sum }_{i=0}^{2n-2}{b}_i{x}^{i}modf(x)=c_{\frac{n-3}{2}}+b_{2n-2}{x}^{2n-2}modf(x)$

n为偶数时: $b_n=a_{\frac{n}{2}},c_0={\sum }_{i=0}^{n-1}{b}_i{x}^i+b_n+b_n{x}^k$ 利用同余性质$x^m\equiv x^k+1mod(x^m+x^k+1)$

n为奇数时：$b_n =0 , c_0 =sum_{i=0}^{n-1}b_ixi $

以奇数为例：（n为奇数时最高项$x^{n+2i}$为0） 引入$c_i$ 的目的是时刻保持$x$最高次项在$n$以下

$c_1={\sum }_{i=0}^{n+2i-1}{b}_i{x}^i=c_0+b_{n+1}{x}^{n+1}={\sum }_{i=0}^{n-1}{b}_i{x}^i+b_{n+1}x+b_{n+1}{x}^{k+1}$

$c_2 =c_1+b_{n+3}x^{n+3} =sum_{i=0}^{n-1}b_ixi +b_{n+1}x +b_{n+1}x^{{n+1}+b_{n+3}x}{3} +b_{n+3}x^{k+3} $

$...$

$A(x^2)=c_{\frac{n-1}{2}}={\sum }_{i=0}^{2n-2}{b}_i{x}^i=c_{\frac{n-3}{2}}+b_{2n-2}{x}^{2n-2}={\sum }_{i=0}^{n-1}{b}_i{x}^i+b_{n+1}x+b_{n+1}{x}^{k+1}+b_{n+3}{x}^3+b_{n+3}{x}^{k+3}+...b_{2n-2}{x}^{n-2}+b_{2n-2}{x}^{k+n-2}$

对于$c_{\frac{n-1}{2}}$中x次项大于n的利用同余性质进行削减。

以$n=257k=12$ 为例2:

综上：

$i<k(12)$ : $i$为奇数：$q_i=b_{n+i}$

​ $i$为偶数：$q_i=b_{2n-k+i}+b_i$

$k=<i<2k$: $i$为奇数：$q_i=b_{n+i}+b_{n+i-k}$

​ $i$为偶数：$q_i=b_{2n-2k+i}+b_i$

$2k=<(n-1)i$ :$i$为奇数：$q_i=b_{n+i}+b_{n+i-k}$

​ $i$为偶数： $q_i=b_i$

平方在硬件上的实现就是对自身做异或运算，可以在一个周期内完成。

有限域模逆运算：

取$F^{2m}$ 域上一元素$A(x)$ ，它与$f(x)$ 最大公因式为1（$gcd(f(x),A(x))=1$），于是存在$B(x),C(x)$使得$A(x)B(x)=f(x)C(x)+1$，即$A(x)B(x)=1mod(f(x))$ ，利用扩展欧几里得定理求解：

基本原理为：

设$a=f(x)b=A(x)$

$r_0=a,r_1=b$

$s_0=1s_1=0$ $t_0=0t_1=1$

依次执行下列运算：

$r_0=r_1{q}_1+r_2$ $s_{i+1}=s_{i-1}-s_i{q}_i$ $t_{i+1}=t_{i-1}-t_i{q}_i$ 下同

$r_1=r_2{q}_2+r_3$

$r_2=r_3{q}_3+r_4$

$r_3=r_4{q}_4+r_5$

$r_{n-1}=r_n{q}_n+r_{n+1}$

当$r_{n+1}$ 为1时停止运算。

计算$s_i$$t_i$的目的是时刻保持 $a{s}_i+b{t}_i=r_i$ 当$r_i$为1时 $f(x)s_i +A(x)t_i =1 $ $t_i$ 即为$A(x)$ 的逆

多项式的模逆运算由于其没有负数的概念，减法运算为异或运算，$s_i{t}_i$没有正负之分，为解决这一问题，当进行上述循环时，$r_n$ 第一个为1的位数小于$r_{n+1}$首位为1的位数时，在下一循环中使用的$s_{i-1}{s}_i$ $t_{i-1}{t}_i$ 两两互换，并在之后的计算中使用互换之后的数据。

以$a=100101b=11011$为例：

下述+为异或运算

1.$r_0=r_1{q}_1+r_2=b\ast 2(q_1)+(b/2+a)=b\ast 2+010011(r_2)$ ##多项式的求余只需将除数左移将最高位的1对齐后进行异或运算即可

​ $s_2=s_0+s_1{q}_1=000001+000000=000001$

​ $t_2=t_0+t_1{q}_1=000000+000010=000010$

2.$r_1=r_2{q}_2+r_3=010011\ast 1+001000$

​ $s_3=s_1+s_2{q}_2=000000+000001=000001$

​ $t_3=t_1+t_2{q}_2=000001+000010=000011$

3.$r_2=001000\ast 2+000011$

​ $s_4=000011$

​ $t_4=000010+000110=000100$

4.$r_3=000011(r_4)\ast 4+000100(r_5)$

​ $s_5=001101$

​ $t_5=010011$

5.由于上述$r_4$ 第一个为1的位是1，$r_5$ 第一个为1的位是2，所以$s_4与s_5$ ，$t_4与t_5$ ，$r_4与r_5$进行互换

$r_4(r_5)=r_5(r_4)\ast q5+r_6=000100=000011\ast 2+000010$

​ $s_6=s_4(s_5)+s_5(s_4)q_5=001011$

​ $t_6=t_4(t_5)+t_5(t_4)q_5=011011$

6.$r-5=000010\ast 1+000001$

​ $t_7=011011+000100=11111$

$t_7$即为b的逆。

.

最后

以上就是现实鲜花最近收集整理的关于椭圆曲线点加运算硬件实现数学原理的全部内容，更多相关椭圆曲线点加运算硬件实现数学原理内容请搜索靠谱客的其他文章。