SM9 文档阅读笔记
本文记录自己在学习实现 SM9 中遇到的问题和个人理解. 由于实现之前没有系统学习过 SM9 涉及的相关数学知识, 因此踩了许多坑, 特此记录.
主要是一些关键性数学概念的理解, 以及一些简单的优化技巧.
扩域运算
在 SM9 中, 按如下方式进行扩域运算:
$F_{q^{12}}$ 的 $1\text{-}2\text{-}4\text{-}12$ 塔式扩张:
$$
\begin{align*}
& F_{q^{2}}[u] = F_{q}[u]/(u^2 - \alpha), && \alpha = -2 \\
& F_{q^{4}}[v] = F_{q^{2}}[v]/(v^2 - \xi), && \xi = u \\
& F_{q^{12}}[w] = F_{q^{4}}[w]/(w^3 - v), && v^2 = \xi
\end{align*}
$$
其中, 第一次的 2 次扩张约化多项式为: $x^2 - \alpha, \alpha=-2$;
第二次进行 2 次扩张的约化多项式为: $x^2 - u, u^2 = \alpha, u = \sqrt{-2}$;
第三次进行 3 次扩张的约化多项式为: $x^3-v, v^2=u, v = \sqrt{\sqrt{-2}}$.
$u$ 属于 $F_{q^{2}}$, 表示为 $(1, 0)$.
$v$ 属于 $F_{q^{4}}$, 表示为 $(0, 1, 0, 0)$, 也可以用 $F_{q^{2}}$ 元素表示为 $((0, 1), (0, 0))$.
扩域这个概念可以类比中学学过的 "复数", $ai + b$, 将实数域扩展到了复数域, 这里面的 $i$ 是 $\sqrt{-1}$.
扩展后的域元素可以用扩展前的域元素来进行表示, 这里面 $a$ 和 $b$ 都是实数域, 而 $ai + b$ 则是复数域.
因此 SM9 中将 $F_{q}$ 的元素最高扩展到了 $F_{q^{12}}$ 上, 也就是从原本的 1 项变成了 12 项. 并且需要注意扩域元素的书写方式.
例如 $F_{q^{4}}$ 上我们需要按 $F_{q^{2 \times 2}}$ 来理解, 也就是在 $F_{q^{2}}$ 上进行了 1 次 2 次扩张, 这样扩域后的元素用 $F_{q^{2}}$ 上的元素表示, 而不是简单的用 $F_{q}$ 进行表示, 两者之间需要进行转换.
具体来说可以根据扩域元素 $u$, $v$ 和 $w$ 来进行转换计算, 在 SM9 中扩域元素使用多项式进行表示, 三者之间存在如下关系.
$$
\begin{align*}
\alpha = u^2 = (v^2)^2 = ((w^3)^2)^2
\end{align*}
$$
因此有:
$$
\left\{
\begin{align*}
w &= \alpha^\frac{1}{12} \\
v &= \alpha^\frac{1}{6} = w^2 \\
u &= \alpha^\frac{1}{2} = w^6
\end{align*}
\right.
$$
所以塔式扩张下一个 $F_{q^{12}}$ 上的域元素 $X_{F_{q^{12}}}$ 可以被表示为:
$$
\begin{align*}
X &= Aw^2 + Bw + C \\
~ &= (a_1v + a_0)w^2 + (b_1v + b_0)w + (c_1v + c_0) \\
~ &= ((a_{11}u + a_{10})v + (a_{01}u + a_{00}))w^2 + ((b_{11}u + b_{10})v + (b_{01}u + b_{00}))w + ((c_{11}u + c_{10})v + (c_{01}u + c_{00})) \\
~ &= a_{11}uvw^2 + a_{10}vw^2 + a_{01}uw^2 + a_{00}w^2 + b_{11}uvw + b_{10}vw + b_{01}uw + b_{00}w + c_{11}uv + c_{10}v + c_{01}u + c_{00} \\
~ &= a_{11}w^{11} + a_{10}w^5 + a_{01}w^8 + a_{00}w^2 + b_{11}w^{10} + b_{10}w^4 + b_{01}w^7 + b_{00}w + c_{11}w^9 + c_{10}w^3 + c_{01}w^6 + c_{00} \\
~ &= (((a_{11}, a_{10}), (a_{01}, a_{00})), ((b_{11}, b_{10}), (b_{01}, b_{00})), ((c_{11}, c_{10}), (c_{01}, c_{00}))) \\
~ &= (a_{11}, b_{11}, c_{11}, a_{01}, b_{01}, c_{01}, a_{10}, b_{10}, c_{10}, a_{00}, b_{00}, c_{00})
\end{align*}
$$
幂次与系数转换关系如下:
$$
\begin{align*}
&( &11&, &10&, &9&, &8&, &7&, &6&, &5&, &4&, &3&, &2&, &1&, &0& &) \\
&(((&11&, &5&), ( &8&, &2&)), ((&10&, &4&), ( &7&, &1&)), (( &9&, &3&), ( &6&, &0&))&)
\end{align*}
$$
在这种情况下, 如果采用第二种方式表示扩域元素, 在需要将低维元素直接扩展成高维元素时, 低维元素保留在右侧, 左侧部分置零.
BN 曲线上 R-ate 对的计算
涉及的群
SM9 的双线性对涉及三个群的运算, $\mathbb{G}_1$, $\mathbb{G}_2$ 和 $\mathbb{G}_T$.
其中 $\mathbb{G}_1$, $\mathbb{G}_2$ 分别是 $F_{q}$, $F_{q^2}$ 椭圆曲线上的点群, 而 $\mathbb{G}_T$ 是 $F_{q^{12}}$ 上的域元素群.
扭曲线
R-ate 对的计算为 $f = R_a(P, Q)$, 其中 $P \in E(F_{q}), Q \in E'(F_{q^2}), f \in F_{q^{12}}$.
这里输入的 $Q$ 原本应该是 $E(F_{q^{12}})$ 上的元素, 但是 BN 曲线存在一条扭曲线 $E'(F_{q^2})$, 能够将原本需要在 $F_{q^{12}}$ 上进行的椭圆曲线点运算转换到 $F_{q^2}$ 上的椭圆曲线进行, 从而降低计算量.
转换函数与扭曲线参数 $\beta$ 有关, 记为 $\phi: E' \rightarrow E: (x, y) \mapsto (\frac{x}{\beta^{\frac{1}{3}}}, \frac{y}{\beta^{\frac{1}{2}}})$.
所以, 在 R-ate 对的计算过程中, 对于需要 $Q$ 的运算中, 只有椭圆曲线上的点运算是直接使用 $Q$ 进行计算的, 其余计算都需要先将 $Q$ 使用 $\phi$ 函数转换到 $E(F_{q^{12}})$ 上再进行计算.
R-ate 计算
除了对 $Q$ 进行点运算时在 $F_{q^2}$ 上进行, 其余的计算都在 $F_{q^{12}}$ 上进行.
例如计算 $g$ 函数时, 正确的做法是计算 $g_{\phi(T), \phi(T)}(P')$ 和 $g_{\phi(T), \phi(Q)}(P')$, 其中 $P'$ 是将 $P$ 直接扩展到 $E(F_{q^{12}})$ 的点.
以及后面计算 Frobenius 自同态的 $\pi_q$ 和 $\pi_{q^2}$ 时, 需要进行转换计算 $Q_1 = \phi^{-1}(\pi_q(\phi(Q)))$ 和 $Q_2 = \phi^{-1}(\pi_{q^2}(\phi(Q)))$.
Frobenius 优化
Frobenius 运算定义为: $\pi_q(x, y) = (x^q, y^q)$, 其中 $x, y$ 可以是扩域上的元素.
设 $x = a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1$, 则:
$$
\begin{align*}
x^q &= (a_nx_n + a_{n-1}x_{n-1} + \cdots + a_1)^q \\
~ &= \sum{(C_{q}^{i}C_{q-i}^{j}C_{q-i-j}^{k} \cdots )(a_nx_n)^i(a_{n-1}x_{n-1})^j(a_{n-2}x_{n-2})^k \cdots}
\end{align*}
$$
当 $q$ 为素数时, 由费马小定理可以知道 $a^{q} \equiv a \mod q$, 且当 $(C_{q}^{i}C_{q-i}^{j}C_{q-i-j}^{k} \cdots )$ 不为 1 时必为 $q$ 的倍数 (被 $q$ 整除).
所以在进行模 $q$ 运算后, $x^q = a_nx_n^q + a_{n-1}x_{n-1}^q + \cdots + a_1$.
可以看出来 Frobenius 运算就是在原有的系数上乘上了一个对应元素的 $q$ 次方, 在扩域元素确定的情况下, 这些值是可以被提前计算出来的, 因此将会被简化成 $n$ 次扩域乘法和 $n - 1$ 次扩域加法.
进一步, 由文献 Simplification and Hardware Parallel Design of Frobenius Mapping Algorithm Based on SM9 可以得到针对 SM9 参数的特定优化策略, 即每一项前面仅仅是乘了一个常数, 所以可以将常数值全部进行预计算从而提高后续计算速度, 此时只需要 $n - 1$ 次 $F_{q}$ 上的乘法就能完成运算.
FinalExp 优化
在 R-ate 对计算的最后, 有一步 $f = f^{\frac{q^{12} - 1}{r}}$.
这是一步在 $F_{q^{12}}$ 上的指数运算, 并且指数非常大, 常规运算时间开销非常夸张. 由文献 On the Final Exponentiation for Calculating Pairings on Ordinary Elliptic Curves 可以得到对 BN 曲线的特定优化:
$$
\frac{q^{12} - 1}{r} = (q^6 - 1)(q^2 + 1)(\frac{q^4 - q^2 + 1}{r})
$$
前半部分的 $(q^6 - 1)(q^2 + 1)$ 称为 "简单部分", 因为可以通过 Frobenius 和模逆运算快速得到结果 (并且 $q^6$ 可以仅通过共轭和取负得到结果).
后半部分的 $\frac{q^4 - q^2 + 1}{r}$ 称为 "困难部分", 文献中根据 BN 曲线 $q$ 和 $r$ 关于 $t$ 的表达式继续分解得到:
$$
\frac{q^4 - q^2 + 1}{r} = \lambda_3q^3 + \lambda_2q^2 + \lambda_1q + \lambda
$$
其中:
$$
\left\{
\begin{align*}
\lambda_3 &= 1 \\
\lambda_2 &= 6t^2 + 1 \\
\lambda_1 &= -36t^3 - 18t^2 - 12t + 1 \\
\lambda_0 &= -36t^3 - 30t^2 - 18t - 2
\end{align*}
\right.
$$
因此困难部分的指数可以表示为:
$$
\begin{align*}
\frac{q^4 - q^2 + 1}{r} = (6t^2q^2 + q^3 + q^2 + q) - (36(t^3 + t^3q) + 30t^2 + 18(t^2q + t) + 12tq + 2)
\end{align*}
$$
括号内只需要依次算出和 $t, q$ 有关的 $f$ 指数运算结果即可, 并且 $q$ 可以用 Frobenius 运算得到, 最后负号的内容一起求一次逆就行.
总结
花了一点篇幅记录了一下自己在实现 SM9 算法中遇到的问题和解决过程, 给自己补充了很多基础的密码学知识, 很多内容对于领域内人来说是基础中的基础, 但是初见还是容易让人晕头转向.
关于 SM9 的优化方法还有很多, 这里只简单提了一些, 自己实现的时候也是尽可能的加进去能看懂的优化方法了毕竟没专门研究这方面, 不能一上来就挑战地狱难度副本.
实现过程中也参考了开源的国密库 GmSSL, 毕竟调试的时候没有标准答案真的很痛苦.
最后放上自己实现的国密算法库 gmalg, 一个不依赖第三方库纯 Python 实现的国密算法库, 就不考虑性能了, 主要是学习国密算法原理能用就行.