在有限域中实现平方运算的方法和装置

摘要

本发明公开了一种在有限域中实现平方运算的方法和装置。当有限域GF(2ⁿ)的定义多项式表示为见右(1)式时，其中n为奇数，有限域中所包含的元素A表示为A＝(a₀，a₁，a₂，...，a_n-1，)∈GF(2ⁿ)，提供了一种计算元素A的平方的方法，该方法包括：确定预定的系数m_i，I_ij，V₀，V_ij以及V，使得系数m_i满足在1≤i≤t是一个自然数时关于k_i的预定条件，系数I_ij在2≤j≤m_i时依赖于n，k_ij以及j，n比特的系数V₀和V_ij各自依赖于n，I_ij和k_i，并且依照下面的公式获得关于m_i的系数V见右(2)式；依据k_i和n确定预定系数s_i并以s_i对系数V进行循环移位；对循环移位后的系数V与元素A进行XOR运算；并以预定的顺序重新接线XOR运算的结果同时输出平方运算的结果。

主权项

1、当一个有限域GF(2ⁿ)的定义多项式表示为$f\left(x\right)=x^n+\underset{i=1}{\overset{i}{\Sigma }}{x}^{k_i}+1$时，其中n为奇数，有限域中所包含的元素A表示为A＝(a₀，a₁，a₂，.a_n-1，)∈GF(2ⁿ)时，一种由用于取平方的装置所执行的对元素A取平方的方法，该装置包括系数计算单元、XOR运算单元和重新接线单元，该方法包括：当1≤i≤t并且i是自然数时，满足下面关于k_i的公式确定系数m_i：$\left(\begin{array}{cc}{m}_i=0& k_i=1\\ m_i=r& \frac{(r-2)n+1}{r-1}<k_i\le \frac{(r-1)n+1}{r},r\ge 2\end{array}\right.,$当2≤j≤m_i时，l_ij由下面的、基于n，k_j以及j的公式确定：$l_{\mathrm{ij}}=\frac{n-1}{2}-\left[(j-1)\frac{n-k_i}{2}\right],$V₀由下面的公式确定：当k_i是奇数时或者当k_i为偶数、j为奇数时，基于n、l_ij和k_j的、n位的V_ij如下：或者，当k_i和j都是偶数时：并且V根据关于m_i的如下公式；$\left\{\begin{array}{c}{V}_i=V_{i2}\oplus V_{i3}\oplus ···\oplus V_{i{m}_i}\\ V=V_0\oplus \underset{m_i\ne 0}{\Sigma }{V}_i\end{array}\right.,$根据k_i和n确定系数s_i，并且以s_i循环移动系数V，其中由下面公式根据k_i和n来确定s_i对经循环移动的系数V和元素A执行XOR运算；以及以预定的次序重新接线XOR运算的结果并且输出所述取平方运算的结果，其中当XOR运算的结果C’表示为C’＝c₀’c₁ ’...c_n-1’并且元素A的平方A²表示为A²＝c₀c₁...c_n-1时，所述预定的次序的含义为根据如下公式获得c_ic_i＝c_j’(i≡2j mod n)，其中，在所述系数计算单元中确定系数m_i，l_ij，V₀，V_ij和V以及确定s_i，在所述XOR运算单元中执行XOR运算，并且在所述重新接线单元中执行重新接线。