国密SM9标识密码算法推出好多年了，只是大概看过一些介绍，从来没有仔细研究，现在看到的频率越来越多，决定对照规范好好学习一下。国密SM9标识密码算法由国密局的密码行业标准GM/T 0044-2016《SM9标识密码算法》公布，这个标准共分五个部分：
- 第1部分：总则
- 第2部分：数字签名算法
- 第3部分：密钥交换协议
- 第4部分：密钥封装机制和公钥加密算法
- 第5部分：参数定义
Adi Shamir(RSA中的S)在1984年提出了标识密码（Identity-Based Cryptography）的概念，在标识密码系统中，用户的私钥由密钥生成中心（KGC）根据主密钥和用户标识计算得出，用户的公钥由用户标识唯一确定，从而不需要第三方保证其公钥的真实性。与基于证书的公钥密码系统相比，标识密码系统中的密钥股那里环节可以得到适当简化
定义
标识 identity
可以唯一确定一个实体身份的信息。标识应有实体无法否认的信息组成，如实体可以识别的名称、电子邮箱、身份证号码、电话号码等。
主密钥 master key
处于标识密码密钥分层最顶层的密钥，包括主私钥和主公钥，其中主公钥公开，主私钥由KGC秘密保存。KGC用主私钥和用户的标识生成用户的私钥。在标识密码中，主私钥一般由KGC通过随机数发生器产生，主公钥由主私钥结合系统参数产生。
签名系统的主密钥与加密系统的主密钥不同。数字签名算法属于签名系统，其主密钥为签名主密钥，密钥交换协议、密钥分装机制和公钥加密算法属于加密系统，其主密钥为加密主密钥。
密钥生成中心 key generation center;KGC
在SM9标识密码中，负责选择系统参数、生成主密钥并产生用户私钥的可信机构。
有限域和椭圆曲线
有限域
概述
域由一个非空集合F和两中运算共同组成，这两种运算分别为加法（用+表示）和乘法（用$\cdot$表示），并满足下列算数特性：
- a) (F, + )对于加法运算构成加法交换群，单位元用0表示。
- b) (F, $\cdot$ )对于乘法运算构成乘法交换群，单位元用1表示。
- c) 分配律成立：对于所有的$a,b,c \in F$,都有$(a+b) \cdot c = a \cdot c + b \cdot c$。
若集合F是有限集合，则称域为有限域。有限域的元素个数称为有限域的阶。
素域$F_p$
阶位素数的有限域是素域。
设p是一个素数，则整数模p的全体余数的集合${0,1,2, \cdots ,p-1}$关于模p的加法和乘法构成一个p阶素域，用符号 $F_p$ 表示。
$F_p$ 具有如下性质：
- a) 加法单位元是0
- b) 乘法单位元是1
- c) 域元素的加法是整数的模p加法，即若 $a,b\in F_p$ ,则 $a+b=(a+b) mod\ p $
- d) 域元素的乘法是整数的模p乘法，即若 $a,b\in F_p$ ,则 $a \cdot b=(a \cdot b) mod\ p $
有限域 $F_{q^m}$
设q是一个素数或者素数方幂，$f(x)$ 是多项式环 $F_q[x]$ 上的一个m(m>1)次不可约多项式（称为约化多项式或域多项式），商环 $F_q[x]/(f(x))$ 是含 $q^m$ 个元素的有限域（记为 $F_{q^m}$ ），称 $F_{q^m}$ 是有限域 $F_q$ 的扩域，域 $F_q$ 为域 $F_{q^m}$ 的子域，m为扩张次数。 $F_{q^m}$ 可以看成 $F_q$ 上的m维向量空间。 $F_{q^m}$ 的每一个元可以唯一地写成 $\alpha_0\beta_0+\alpha_1\beta_1+\cdots+\alpha_{m-1}\beta_{m-1}$，其中 $\alpha_i \in F_q$ ，而 $\beta_0,\beta_1,\cdots,\beta_{m-1}$ 是向量空间 $F_{q^m}$ 在 $F_q$ 上的一组基。
$F_{q^m}$ 中的元素可以用多项式基或正规基表示。在商密规范中，一般 $F_{q^m}$ 中的元素均采用多项式基表示。
不可约多项式 $f(x)$ 可取为首一的多项式 $f(x)=x^m+f_{m-1}x^{m-1}+\cdots+f_2x^2+f_1x+f_0$ （其中$f_i \in F_q,i=0,1,\cdots,m-1$）， $F_{q^m}$ 中的元素由多项式环 $F_q[x]$ 中所有次数低于m多项式构成。多项式集合 ${ x^{m-1},x^{m-2},\cdots,x,1}$ 是 $F_{q^m}$ 在 $F_q$ 上的一组基，称为多项式的基。域 $F_{q^m}$ 上的任意一个元素 $a(x)=a_{m-x}x^{m-1}+a_{m-2}x^{m-2}+\cdots +a_1x+a_0$ 在 $F_q$ 上的系数恰好构成了一个m维向量，用 $a=(a_{m-1},a_{m-2},\cdots,a_1,a_0)$ 表示，其中分量 $a_i \in F_q,i=0,1,\cdots,m-1$ 。 $F_{q^m}$ 具有如下性质：
- a) 零元0用m维向量 $(0,\cdots,0,0)$ 表示
- b) 乘法单位元1用m维向量 $(0,\cdots,0,1)$ 表示
- c) 两个域元素的加法为向量加法，各个分量用域 $F_q$ 的加法
- d) 域元素a和b的乘法定义如下：设a和b对应的 $F_q$上多项式为a(x)和b(x)，则 $a\cdot b$ 定义为多项式$(a(x)\cdot b(x) mod \ f(x))$ 对应的向量
- e) 逆元：设a对应的 $F_q$ 上的多项式为a(x),a的逆元 $a^{-1}$ 对应的 $F_q$ 上多项式为 $a^{-1}(x)$ ，那么有 $a(x)\cdot a^{-1}(x)\equiv 1 \ mod \ f(x)$ 。
有限域上的椭圆曲线
有限域 $F_{q^m}(m\ge 1)$ 上的椭圆曲线是由点组成的集合。在仿射坐标系下，椭圆曲线上点P（非无穷远点）用满足一定方程的两个域元素 $x_P$ 和 $y_P$ 表示， $x_P,y_P$分别称为点P的x坐标和y坐标，并记 $P=(x_P,y_P)$ 。
定义在 $F_{p^m}$ 上的椭圆曲线方程为：
$ y^2 = x^3+ax+b, a,b \in F_{p^m}, 且 4a^3+27b^2\ne 0 \ \cdots \ \cdots \ \cdots 1 $
椭圆曲线 $E(F_{p^m})$ 定义为：
| $ E(F_{p^m})={ (x,y) | x,y \in F_{p^m},且满足方程(1)}\cup {O} ,其中O是无穷远点$ |
椭圆曲线 $E(F_{p^m})$ 上的点的数目用 $# E(F_{p^m})$ 表示，称为椭圆曲线 $E(F_{p^m})$ 的阶。
商密SM9规范中规定素数 $p>2^{191}$
设E和E’是定义在 $F_q$ 上的椭圆曲线，如果存在一个同构映射 $\phi_d:E’(F_{q^d})\to E(F_{q^d})$ ，其中d是使映射存在的最小整数，则称E’为E的d次扭曲线。当 $p \ge 5$ 时，d的取值又3种情况：
- a) $若a=0,b\ne 0,那么d=6, E’:y^2 = x^3 + \beta b,\phi_6 : E’ \to E: (x,y)\mapsto(\beta^{-1/3}x,\beta^{-1/2}y);$
- b) $若b=0,a\ne 0, 那么d=4, E’:y^2=x^3+\beta ax,\phi_4:E’ \to E:(x,y) \mapsto (\beta^{-1/2}x,\beta^{-3/4}y); $
- c) $若a\ne 0,b\ne 0,那么d=2,E’:y^2=x^3+\beta^2 ax+ \beta^3 b,\phi_2:E’ \to E:(x,y) \mapsto(\beta^{-1}x,\beta^{-3/2}y). $
椭圆曲线群
椭圆曲线 $E(F_{p^m})(m\ge 1)$上的点按照下面的加法运算规则，构成一个交换群：
- a) $O+O=O $
- b) $\forall P=(x,y) \in E (F_{p^m}) \backslash { O }, P+O=O+P=P $
- c) $\forall P=(x,y) \in E (F_{p^m}) \backslash { O }, P的逆元素-P=(x,-y),P+(-P)=O $
-
d) $两个非互逆的不同点相加的规则： $
$设P_1=(x_1,y_1) \in E(F_{p^m}) \backslash { O}, P_2=(x_2,y_2) \in E(F_{p^m})\backslash {O},且x_1 \ne x_2, $
$设P_3=(x_3,y_3)=P_1+P_2,则$
\[\begin{cases} x_3 = \lambda^2 - x_1 - x_2, \\ y_3 = \lambda (x_1 - x_3) - y_1, \end{cases}\]其中
\[\lambda = \frac {y_2-y_1}{x_2-x_1};\] -
e) 倍点规则： $设P_1=(x_1,y_1) \in E(F_{p^m}) \backslash {O}, 且y_1 \ne 0,P_3=(x_3,y_3)=P_1+P_1$,
则
$ \begin{cases} x_3 = \lambda^2-2x_1,
y_3 = \lambda (x_1 - x_3) - y_1, \end{cases} $ 其中 $ \lambda = \frac {3x_1^2 + a}{2y_1}. $
椭圆曲线多倍点运算
椭圆曲线上同一个点的重复相加称为该点的多倍点运算。设u式一个正整数，P是椭圆曲线上的点，其u倍点 $ Q=[u]P= \begin{matrix} \underbrace{ P+P+\cdots+P } \ u个 \end{matrix} . $
多倍点运算可以扩展到0倍点运算和负数倍点运算：$[0]P=O,[-u]P=u$.
椭圆曲线子群上点的验证
输入：定义 $F_{q^m}$ 上（q为奇素数，$m \ge 1$）椭圆曲线方程的参数a、b，椭圆曲线$E(F_{q^m})$上的子群G的阶N，$F_{q^m}$ 上的一堆元素(X,y)。
输出：若(x,y)是群G中的元素，则输出有效，否则输出无效。
- a) 在 $F_{q^m}$ 上验证（x,y）是否满足椭圆曲线方程 $y^2 = x^3+ax+b$
- b) 令Q=(x,y)，验证[N]Q=O
若以上任何一项验证失败，则输出无效，否则输出有效