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 是无穷远点。