符号
A,B：使用标识密码系统的两个用户。
\(cf\)：椭圆曲线阶相对于\(N\)的余因子。
\(cid\)：用一个字节表示的曲线的标识符，其中\(\mbox{0x10}\)表示\(F_p\)（素数\(P>2^{191}\)）上常曲线（即非超奇异曲线），\(\mbox{0x11}\)表示\(F_p\)表示超奇异曲线，\(\mbox{0x12}\)表示\(F_p\)上常曲线及其扭曲线。
\(ds_A\)：用户A的签名私钥。
\(e\)：从\(G_1×G_2\)到\(G_T\)的双线性对。
\(eid\)：用一个字节表示的双线性对\(e\)的标识符，其中\(\mbox{0x01}\)表示Tate对，\(\mbox{0x02}\)表示Weil对，\(\mbox{0x03}\)表示Ate对，\(\mbox{0x04}\)表示R-ate对。
\(G_T\)：阶为素数\(N\)的乘法循环群。
\(G_1\)：阶为素数\(N\)的加法循环群。
\(G_2\)：阶为素数\(N\)的加法循环群。
\(g^u\)：乘法群\(G_T\)中元素\(g\)的\(u\)次幂，\(g^{u} = \underset{u\text{个}}{\underbrace{g \cdot g \cdot \ldots \cdot g}}\)，\(u\)是正整数。
\(H_v()\)，\(Hash()\)：密码杂凑函数。
\(H_1()\)、\(H_2()\)：由密码杂凑函数派生的密码函数。
\(hid\)：本部分中，用一个字节表示的加密私钥生成函数识别符，由KGC选择并公开。
\((h,S)\)：发送的签名。
\((h',S')\)：收到的签名。
\(ID_A\)：用户A的表示，可以唯一确定用户A的公钥。
\(M\)：待签名消息。
\(M'\)：待验证消息。
\(\mod{n}\)：模n运算。例如，\(23\mod{7}=2。
\)N\(：循环群\)G_1\(、\)G_2\(和\)G_T$的阶，为大于\(2^{191}\)的素数。
\(P_{pub-s}\)：签名主公钥。
\(P_1\)：群\(G_1\)的生成元。
\(P_2\)：群\(G_2\)的生成元。
\(ks\)：签名主私钥。
\(〈P〉\)：由元素\(P\)生成的循环群。
\([u]P\)：加法群\(G_1\)、\(G_2\)中元素\(P\)的\(u\)倍。
\(⌈x⌉\)：顶函数，大于或等于\(x\)的最小整数。例如，\(⌈7⌉=7\)，\(⌈8.3⌉=9\)。
\(⌊x⌋\)：底函数，小于或等于\(y\)的最大整数。例如，\(⌊7⌋=7\)，\(⌊8.3⌋=8\)。
\(x‖y\)：\(x\)与\(y\)的拼接，其中\(x\)和\(y\)是比特串或字节串。
\([x,y]\)：大于或等于\(x\)且小于或等于\(y\)的整数的集合。
\(β\)：扭曲线参数。
系统签名主密钥和用户签名密钥的产生
KGC产生随机数\(ks∈[1,N-1]\)作为签名主私钥，计算\(G_1\)中的元素\(P_{pub-s}=[ks] P_1\)作为签名主公钥，则签名主密钥对为\((ks,P_{pub-s} )\)。KGC秘密保存\(ks\)，公开\(P_{pub-s}\)。
KGC选择并公开用一个字节表示的签名私钥生成函数识别符\(hid\)。
用户A的标识为\(ID_A\)，为产生用户A的签名私钥\(ds_A\)，KGC首先在有限域\(F_N\)上计算\(t_1=H_1(ID_A ‖hid,N)+ks\)，若\(t_1=0\)则需重新产生签名主私钥，计算和公开签名主公钥，并更新已有用户的签名私钥；否则计算\(t_2=ks⋅t_1^{-1}\)，然后计算\(ds_A=[t_2 ] P_2\)。
密码杂凑函数\(H_v()\)
密码杂凑函数\(H_v ()\)的输出是长度恰为\(v\)比特的杂凑值。本部分规定使用国家密码管理主管部门批准的密码杂凑函数，如SM3密码杂凑算法。
密码函数\(H_1 ()\)
密码函数\(H_1(Z,n)\)的输入为比特串\(Z\)和整数\(n\)，输出为一个整数\(h_1∈[1,n-1]\)。\(H_1(Z,n)\)需要调用密码杂凑函数\(H_v ()\)。
密码函数\(H_1(Z,n)\)：
输入：比特串\(Z\)，整数\(n\)。
输出：整数\(h_1∈[1,n-1]\)。
- 初始化一个32比特构成的计数器\(ct=\mbox{0x00000001}\)；
- 计算\(hlen=8×⌈(5×(\log{2}{n}))⁄32⌉\)；
- 对\(i\)从\(1\)到\(⌈hlen⁄v⌉\)执行：
3.1. 计算\(Ha_i=H_v(\mbox{0x01}‖Z‖ct)\)；
3.2. \(ct++\)； - 若\(hlen⁄v\)是整数，令\(Ha!_{⌈hlen⁄v⌉} =Ha_{⌈hlen⁄v⌉}\) ，否则令\(Ha!_{⌈hlen⁄v⌉}\) 为\(Ha_{⌈hlen⁄v⌉}\) 最左边的\((hlen-(v×⌊hlen⁄v⌋))\)比特；
- 令\(Ha=Ha_1 ‖Ha_2 ‖⋯‖Ha_{⌈hlen⁄v⌉-1} ‖Ha!_{⌈hlen⁄v⌉}\) ；
- 计算\(h_1=(Ha\mod{(n-1)})+1\)。
密码函数\(H_2 ()\)
密码函数\(H_2(Z,n)\)的输入为比特串\(Z\)和整数\(n\)，输出为一个整数\(h_2∈[1,n-1]\)。\(H_2(Z,n)\)需要调用密码杂凑函数\(H_v ()\)。
密码函数\(H_2(Z,n)\)：
输入：比特串\(Z\)，整数\(n\)。
输出：整数\(h_2∈[1,n-1]\)。
- 初始化一个32比特构成的计数器\(ct=\mbox{0x00000001}\)；
- 计算\(hlen=8×⌈(5×(\log{2}{n}))⁄32⌉\)；
- 对\(i\)从\(1\)到\(⌈hlen⁄v⌉\)执行：
3.1. 计算\(Ha_i=H_v(\mbox{0x01}‖Z‖ct)\)；
3.2. \(ct++\)； - 若\(hlen⁄v\)是整数，令\(Ha!_{⌈hlen⁄v⌉} =Ha_{⌈hlen⁄v⌉}\) ，否则令\(Ha!_{⌈hlen⁄v⌉}\) 为\(Ha_{⌈hlen⁄v⌉}\) 最左边的\((hlen-(v×⌊hlen⁄v⌋))\)比特；
- 令\(Ha=Ha_1 ‖Ha_2 ‖⋯‖Ha_{⌈hlen⁄v⌉-1} ‖Ha!_{⌈hlen⁄v⌉}\) ；
- 计算\(h_2=(Ha\mod{(n-1)})+1\)。
数字签名生成算法
设待签名的消息为比特串\(M\)，为了获取信息M的数字签名\((h,S)\)，作为签名者的用户A应实现以下运算步骤：
A1.计算群\(G_T\)中的元素\(g=e(P_1,P_{pub-s} )\)；
A2.产生随机数\(r∈[1,N-1]\)；
A3.计算群\(G_T\)中的元素\(w=g^r\)；
A4.计算整数\(h=H_2(M‖w,N)\)；
A5.计算整数\(l=(r-h) \mod{N}\)，若\(l=0\)则返回A2；
A6.计算群\(G_1\)中的元素\(S=[l] ds_A\)；
A7.消息\(M\)的签名为\((h,S)\)。
数字签名验证算法
为了检验收到的消息\(M'\)及其数字签名\((h',S')\)，作为验证者的用户B应实现以下运算步骤：
B1.验证\(h'∈[1,N-1]\)是否成立，若不成立则验证不通过；
B2.验证\(S'∈G_1\)是否成立，若不成立则验证不通过；
B3.计算群\(G_T\)中的元素\(g=e(P_1,P_{pub-s} )\)；
B4.计算群\(G_T\)中的元素\(t=g^{h'}\)；
B5.计算整数\(h_1=H_1(ID_A ‖hid,N)\)；
B6.计算群\(G_2\)中的元素\(P=[h_1 ] P_2+P_{pub-s}\)；
B7.计算群\(G_T\)中的元素\(u=e(S',P)\)；
B8.计算群\(G_T\)中的元素\(w'=u⋅t\)；
B9.计算整数\(h_2=H_2(M'‖w',N)\)，检验\(h_2=h'\)是否成立，若成立则验证通过；否则验证不通过。
注1：注意到签名主公钥为\(P_{pub-s}=[ks] P_1\)，且用户A的签名私钥为
注2：双线性对
设\((G_1,+)\)、\((G_2,+)\)和\((G_T,⋅)\)是3个循环群，\(G_1\)、\(G_2\)和\(G_T\)的阶均为素数\(N\)，\(P_1\)是\(G_1\)的生成元，\(P_2\)是\(G_2\)的生成元，存在\(G_2\)到\(G_1\)的同态映射\(ψ\)使得\(ψ(P_2 )=P_1\)。
双线性对\(e\)是\(G_1×G_2→G_T\)的映射，满足如下条件：
a) 双线性性：对任意的\(P∈G_1\)，\(Q∈G_2\)，\(a,b∈Z_N\)，有\(e([a]P,[b]Q)={e(P,Q)}^{ab}\)；
b) 非退化性：\(e(P_1,P_2 )≠1_{G_T }\)；
c) 可计算性：对任意的\(P∈G_1\)，\(Q∈G_2\)，存在有效的算法计算\(e(P,Q)\)。
标准GM/T 0044.1—2016中7.1节、GM/T 0044.5—2016中3.1节规定了，SM9算法使用R-ate对（\(eid\)：\(\mbox{0x04}\)）。
参考
GM/T 0044.1—2016
GM/T 0044.2—2016
GM/T 0044.5—2016