伽罗瓦域是抽象代数下的域论分支中的内容,这部分想必很多人都比较熟悉,此处不再赘述。
最近,国密算法中的 SM2 和 SM9 已经成为国际标准,其中 SM9 算法在椭圆曲线离散对数难题的基础上,添加了若干个双线性配对难题来保证安全性。
配对的过程中,除去群 G1 中的元素与 SM2 算法一样在素域下之外,群 G2 中的元素为 GFq2 域,群 GT 中的元素为 GFq12 域。
SM9 算法大部分运算都在阔域中进行,而塔式扩张的意义在于将阔域中的元素用基域中的元素进行表示和计算。这里先按照塔式扩张的顺序 (1→2→4→12) 探讨一下阔域中的元素计算。
1. (1)
塔式扩张中的(1),就是指基域。在 SM9 算法中,是素域 Fq,其中 q 是 256 位 BN 曲线的基域特征值。
Fq 域下的元素运算,与我们日常的加减乘除运算并无差异,略去不谈。
2. (2)
塔式扩张中的(2),即域 Fq2。这是从素域向二次域的第一次扩张,扩张公式如下:
Fq2[μ] = Fq[μ] /( μ2 - α), 其中,α = -2
即:该次扩张的即约多项式为 x2 - α, α = -2
下面以具体的例子来说明该次扩张。
SM9 规范第 5 部分中,群 G2 的生成元 P2 = (xP2, yP2):
坐标 xP2:(85AEF3D0 78640C98 597B6027 B441A01F F1DD2C19 0F5E93C4 54806C11 D8806141 , 37227552 92130B08 D2AAB97F D34EC120 EE265948 D19C17AB F9B7213B AF82D65B)
坐标 yP2:(17509B09 2E845C12 66BA0D26 2CBEE6ED 0736A96F A347C8BD 856DC76B 84EBEB96 , A7CF28D5 19BE3DA6 5F317015 3D278FF2 47EFBA98 A71A0811 6215BBA5 C999A7C7)
此处,点 P2 的 x 轴和 y 轴均为域 Fq2 下的元素,且高维在前,低维在后。
按照这种表示顺序,此处定义两个域 Fq2 下的元素:
X = (a, b)
Y = (c, d)
即:
X = a * μ1 + b * μ0 = a * μ + b
Y = c * μ1 + d * μ0 = c * μ + d
加法和减法计算就是对应维度的数值在素域 q 下的加和减:
X + Y = (a, b) + (c, d) = (a + c, b + d)X - Y = (a, b) - (c, d) = (a - c, b - d)乘法:
X * Y = (a, b) * (c, d)
= (a * μ + b) * (c * μ + d)
= (a * c * μ2 + (a * d + b * c)μ + b * d) mod ( μ2 - α)
= -2 *a * c + (a * d + b * c)μ + b * d
= (a * d + b * c)μ + (b * d - 2 * a * c)
即:
X * Y = (a, b) * (c, d) = (a * d + b * c , b * d - 2 * a * c)其中,最终结果中的 * 运算均为素域 q 下的乘法运算。
求逆:
计算 X-1 = (a, b)-1
假设结果为 (x, y)
则有,(a, b) * (x, y) = (0, 1)
(0, 1) 为域 Fq2 下的单位元,相当于素域 q 下的 1。
将上式展开
(a, b) * (x, y) = (a * y + b * x)μ + (b * y - 2 * a * x)
= (a * y + b * x , b * y - 2 * a * x) = (0, 1)
相当于求解二元一次方程。
a * y + b * x = 0
b * y - 2 * a * x = 1
求解 x 和 y 的过程省去不说,可以得到求逆操作的结果为
X-1 = (a , b)-1 = ((-a) / (b2 + 2 * a2) , b / (b2 + 2 * a2))其中相关元素与计算均在素域 q 下进行。
以上便是塔式扩张的第一次扩张后的元素计算公式。
如上可知,扩张的实际作用是将阔域元素使用基域下的元素表示并按照基域下的运算规则进行运算。
SM9 算法的群 G2 中的点加与倍点计算,虽然与 SM2 的素域下运算公式一致,但实际处理时,所有元素均按照上面的公式在域 Fq2 下进行。
后面再花两个篇幅探讨第二次扩张 2→4 和第三次扩张 4→12,并推导 4 次阔域和 12 次阔域下的元素计算公式。
来源: https://www.cnblogs.com/heshuchao/p/8196307.html