SM9 标识密码算法
第1 部分：总则
2
目 次
1 术语...............................................................................................................................................................3
2 符号和缩略语...............................................................................................................................................3
3 有限域和椭圆曲线.......................................................................................................................................4
3.1 有限域
...................................................................................................................................................
4
3.1.1 概述
...............................................................................................................................................
4
3.1.2 素域
F
p
...........................................................................................................................................
5
3.1.3
有限域
F
q
m
.....................................................................................................................................
5
3.2 有限域上的椭圆曲线
...........................................................................................................................
5
3.3 椭圆曲线群
...........................................................................................................................................
6
3.4 椭圆曲线多倍点运算
...........................................................................................................................
6
3.5 椭圆曲线子群上点的验证
...................................................................................................................
6
3.6 离散对数问题
.......................................................................................................................................
7
3.6.1 有限域上离散对数问题(
DLP
)
....................................................................................................
7
3.6.2 椭圆曲线离散对数问题(
ECDLP
)
................................................................................................
7
4 双线性对及安全曲线...................................................................................................................................7
4.1 双线性对
...............................................................................................................................................
7
4.2 安全性
...................................................................................................................................................
7
4.3 嵌入次数及安全曲线
...........................................................................................................................
8
5 数据类型及其转换.......................................................................................................................................8
5.1 数据类型
...............................................................................................................................................
8
5.2 数据类型转换
.......................................................................................................................................
8
5.2.1 数据类型转换关系
.......................................................................................................................
8
5.2.2 整数到字节串的转换
...................................................................................................................
9
5.2.3 字节串到整数的转换
...................................................................................................................
9
5.2.4 比特串到字节串的转换
...............................................................................................................
9
5.2.5 字节串到比特串的转换
...............................................................................................................
9
5.2.6 域元素到字节串的转换
...............................................................................................................
9
5.2.7 字节串到域元素的转换
.............................................................................................................
10
5.2.8 点到字节串的转换
.....................................................................................................................
10
5.2.9 字节串到点的转换
.....................................................................................................................
11
6 系统参数及其验证.....................................................................................................................................12
6.1 系统参数
.............................................................................................................................................
12
6.2 系统参数的验证
.................................................................................................................................
12
附 录 A 关于椭圆曲线的背景知识......................................................................................................14
附 录 B 椭圆曲线上双线性对的计算..................................................................................................21
附 录 C 数论算法.................................................................................................................................. 28
3
SM9 标识密码算法
第 1 部分：总则
本部分描述了必要的数学基础知识与相关密码技术，以帮助实现本文其它各部分所规定的密码机
制。
1 术语
1.1
标识 identity
可唯一确定一个实体身份的信息。标识应由实体无法否认的信息组成，如实体的可识别名称、电子
邮箱、身份证号、电话号码等。
1.2
主密钥 master key
处于标识密码密钥分层结构最顶层的密钥，包括主私钥和主公钥，其中主公钥公开，主私钥由KGC
秘密保存。KGC用主私钥和用户的标识生成用户的私钥。在标识密码中，主私钥一般由KGC通过随机数发
生器产生，主公钥由主私钥结合系统参数产生。
本文中，签名系统的主密钥与加密系统的主密钥不同。数字签名算法属于签名系统，其主密钥为签
名主密钥，密钥交换协议、密钥封装机制和公钥加密算法属于加密系统，其主密钥为加密主密钥。
1.3
密钥生成中心 key generation center；KGC
在SM9标识密码中，负责选择系统参数、生成主密钥并产生用户私钥的可信机构。
2 符号和缩略语
下列符号和缩略语适用于本部分。
cf ：椭圆曲线阶相对于 N 的余因子。
cid：用一个字节表示的曲线识别符，用以区分所用曲线的类型。
DLP：有限域上离散对数问题。
deg( f )：多项式 f(x)的次数。
d
1
、d
2
：k 的两个因子。
E：定义在有限域上的椭圆曲线。
ECDLP：椭圆曲线离散对数问题。
E(F
q
)：有限域 F
q
上椭圆曲线 E 的所有有理点(包括无穷远点 O)组成的集合。
E(F
q
)[r]：E(F
q
)上 r-扭点的集合(即曲线 E(F
q
)上的 r 阶扭子群)。
e：从 G
1
×G
2
到 G
T
的双线性对。
4
eid ：用一个字节表示的双线性对 e 的识别符，用以区分所用双线性对的类型。
F
p
：包含 p 个元素的素域。
F
q
：包含 q 个元素的有限域。
F
q
*
：由 F
q
中所有非零元构成的乘法群。
F
q
m
：有限域 F
q
的 m 次扩域。
G
T
：阶为素数 N 的乘法循环群。
G
1
：阶为素数 N 的加法循环群。
G
2
：阶为素数 N 的加法循环群。
gcd(x, y)：x 和 y 的最大公因子。
k：曲线 E(F
q
)相对于 N 的嵌入次数，其中 N 是#E(F
q
)的素因子。
m：有限域 F
q
m
关于 F
q
的扩张次数。
mod f(x)：模多项式 f(x)的运算。
mod n：模 n 运算。例如，23 mod 7=2。
N：循环群
1
、
2
和
T
的阶，为大于 2
191
的素数。
O：椭圆曲线上的一个特殊点，称为无穷远点或零点，是椭圆曲线加法群的单位元。
P：P = (x
P
, y
P
) 是椭圆曲线上除 O 之外的一个点，其坐标 x
P
，y
P
满足椭圆曲线方程。
P
1
：
1
的生成元。
P
2
：
2
的生成元。
P+Q：椭圆曲线 E 上两个点 P 与 Q 的和。
p：大于 2
191
的素数。
q：有限域 F
q
中元素的数目。
x
P
：点 P 的 x 坐标。
x||y：x 与 y 的拼接，其中 x 和 y 是比特串或字节串。
x y (mod q)：x 与 y 模 q 同余。亦即，x mod q = y mod q。
y
P
：点 P 的 y 坐标。
#E(K)：E(K)上点的数目，称为椭圆曲线群 E(K)的阶，其中 K 为有限域（包括 F
q
和 F
q
k
）。
<P>：由椭圆曲线上点 P 生成的循环群。
[u]P ：椭圆曲线上点
P
的 u 倍点。
[x, y]：不小于 x 且不大于 y 的整数的集合。
x
：顶函数，不小于 x 的最小整数。例如，
93.8,77
。
x
：底函数，不大于 x 的最大整数。例如,
83.8,77
。
：扭曲线参数。
：
2
到
1
的同态映射，满足 P
1
=
(P
2
)。
⊕：长度相等的两个比特串按比特的模2加运算。
3 有限域和椭圆曲线
3.1 有限域
3.1.1 概述
域由一个非空集合F和两种运算共同组成，这两种运算分别为加法(用“+”表示)和乘法(用“ ∙” 表
示)，并且满足下列算术特性：
a) (F, + )对于加法运算构成加法交换群，单位元用0表示。
b) (F\{0}, ∙ )对于乘法运算构成乘法交换群，单位元用1表示。
5
c) 分配律成立：对于所有的a,b,cF，都有(a+b) ∙ c=a ∙ c+b ∙ c。
若集合F是有限集合，则称域为有限域。有限域的元素个数称为有限域的阶。
3.1.2 素域 F
p
阶为素数的有限域是素域。
设 p 是一个素数，则整数模 p 的全体余数的集合{0,1,2,..., p-1}关于模 p 的加法和乘法构成一个 p
阶素域，用符号 F
p
表示。
F
p
具有如下性质：
a) 加法单位元是 0；
b) 乘法单位元是 1；
c) 域元素的加法是整数的模 p 加法，即若 a,b
F
p
，则 a + b = (a+b) mod p；
d) 域元素的乘法是整数的模 p 乘法，即若 a,b
F
p
，则 a ∙ b = (a ∙ b) mod p。
3.1.3
有限域 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
的每一个元可以唯一地写
成 a
0
0
+a
1
1
+… + a
m-1
m-1
的形式，其中 a
i
∈F
q
，而
0
,
1
,,
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
+…+f
2
x
2
+f
1
x+f
0
(其中 f
i
F
q
, i= 0,1, ...,m1)，F
q
m
中的元素由多项式环 F
q
[x]中所有次数低于 m 的多项式构成。多项式集合{x
m-1
,x
m-2
,...,x,1}是 F
q
m
在 F
q
上
的一组基，称为多项式基。域 F
q
m
上的任意一个元素 a(x) = a
m-1
x
m-1
+ a
m-2
x
m-2
+…+ a
1
x+ a
0
在 F
q
上的系数
恰好构成了一个 m 维向量，用 a = (a
m-1
, a
m-2
, ..., a
1
, a
0
)表示，其中分量 a
i
∈F
q
，i = 0,1, ...,m1。
F
q
m
具有如下性质：
a) 零元 0 用 m 维向量(0,...,0,0)表示；
b) 乘法单位元 1 用 m 维向量(0,...,0,1)表示；
c) 两个域元素的加法为向量加法，各个分量用域 F
q
的加法；
d) 域元素 a 和 b 的乘法定义如下：设 a 和 b 对应的 F
q
上多项式为 a(x)和 b(x)，则 a∙b 定义为多项
式(a(x)∙b(x)) mod f(x)对应的向量。
e) 逆元：设 a 对应的 F
q
上多项式为 a(x)，a 的逆元 a
1
对应的 F
q
上多项式为 a
-1
(x)，那么有 a(x)∙a
-1
(x)
≡1 mod f(x)。
关于有限域的扩域F
q
m
更多细节，参见附录A.1。
3.2 有限域上的椭圆曲线
有限域 F
q
m
(m≥1)上的椭圆曲线是由点组成的集合。在仿射坐标系下，椭圆曲线上点
P
(非无穷远点)
用满足一定方程的两个域元素 x
P
和 y
P
表示，x
P
, y
P
分别称为点
P
的 x 坐标和 y 坐标，并记 P=(x
P
, y
P
)。
本部分描述特征为大素数 p 的域上的曲线。
本部分如果不作特别说明，椭圆曲线上的点均采用仿射坐标表示。
定义在 F
p
m
上的椭圆曲线方程为：
y
2
= x
3
+ ax + b，a, bF
p
m
，且 4a
3
+ 27b
2
0。 (1)
椭圆曲线 E(F
p
m
)定义为：
E(F
p
m
) = {(x, y)| x, yF
p
m
，且满足方程(1)}∪{O}，其中 O 是无穷远点。
