GM/T 0044.2-2016: SM9标识密码算法 第2部分:数字签名算法
GM/T 0044.2-2016 英文名称: Identity-based cryptographic algorithms SM9 - Part 2: Digital signature algorithm
中 华 人 民 共 和 国 密 码 行 业 标 准
GM/T 0044.2—2016
SM9 标识密码算法
国家密码管理局 发 布
前 言
GM/T 0044《SM9标识密码算法》分为5个部分：
——第1部分：总则；
——第2部分：数字签名算法；
——第3部分：密钥交换协议；
——第4部分：密钥封装机制和公钥加密算法；
——第5部分：参数定义。
本部分为GM/T 0044的第2部分。
本部分按照 GB/T 1.1—2009 给出的规则起草。
请注意本文件的某些内容可能涉及专利。本文件的发布机构不承担识别这些专利的责任。
本部分由密码行业标准化技术委员会提出并归口。
本部分起草单位：国家信息安全工程技术研究中心、深圳奥联信息安全技术有限公司、武汉大学、上 海交通大学、中科院信息工程研究所、北方信息技术研究所。
本部分主要起草人：陈晓、程朝辉、叶顶峰、胡磊、陈建华、路贝可、季庆光、曹珍富、袁文恭、刘平、 马宁、袁峰、李增欣、王学进、杨恒亮、张青坡、马艳丽、浦雨三、唐英、孙移盛、安萱。
引 言
A.Shamir 在1984年提出了标识密码(Identity-Based Cryptography)的概念，在标识密码系统中， 用户的私钥由密钥生成中心(KGC) 根据主密钥和用户标识计算得出，用户的公钥由用户标识唯一确 定，从而用户不需要通过第三方保证其公钥的真实性。与基于证书的公钥密码系统相比，标识密码系统 中的密钥管理环节可以得到适当简化。
1999年，K.Ohgishi、R.Sakai和 M.Kasahara 在日本提出了用椭圆曲线对(pairing)构造基于标识的 密钥共享方案；2001年，D.Boneh 和 M.Franklin,以及 R.Sakai、K.Ohgishi 和 M.Kasahara 等人独立提 出了用椭圆曲线对构造标识公钥加密算法。这些工作引发了标识密码的新发展，出现了一批用椭圆曲 线对实现的标识密码算法，其中包括数字签名算法、密钥交换协议、密钥封装机制和公钥加密算法等。
椭圆曲线对具有双线性的性质，它在椭圆曲线的循环子群与扩域的乘法循环子群之间建立联系，构 成了双线性DH、 双线性逆DH、 判定性双线性逆 DH、c 双线性逆DH 和 tGap- 双线性逆DH 等难题， 当椭圆曲线离散对数问题和扩域离散对数问题的求解难度相当时，可用椭圆曲线对构造出安全性和实 现效率兼顾的标识密码。
本部分描述了用椭圆曲线对实现的基于标识的数字签名算法。
1 范围
GM/T 0044 的本部分规定了用椭圆曲线对实现的基于标识的数字签名算法，包括数字签名生成算 法和验证算法，并给出了数字签名与验证算法及其相应的流程。
本部分适用于接收者通过签名者的标识验证数据的完整性和数据发送者的身份，也适用于第三方 确定签名及所签数据的真实性。
2 规范性引用文件
下列文件对于本文件的应用是必不可少的。凡是注日期的引用文件，仅注日期的版本适用于本文 件。凡是不注日期的引用文件，其最新版本(包括所有的修改单)适用于本文件。
GM/T 0004—2012 SM3 密码杂凑算法
GM/T 0044.1一2016 SM9 标识密码算法 第1部分：总则
3 术语和定义
下列术语和定义适用于本文件。
3.1
消息 message
任意有限长度的比特串。
3.2
签名消息 signed message
由消息以及该消息的数字签名部分所组成的一组数据元素。
3.3
签名密钥 signature key
在数字签名生成过程中由签名者专用的秘密数据元素，即签名者的私钥。
3.4
签名主密钥 signature master key
处于标识密码密钥分层结构最顶层的密钥，包括签名主私钥和签名主公钥，其中签名主公钥公开， 签名主私钥由 KGC 秘密保存。 KGC 用签名主私钥和用户的标识生成用户的签名私钥。在标识密码 中，签名主私钥一般由KGC 通过随机数发生器产生，签名主公钥由签名主私钥结合系统参数产生。
3.5
标 识 identity
可唯一确定一个实体身份的信息。标识应由实体无法否认的信息组成，如实体的可识别名称、电子 邮箱、身份证号、电话号码、街道地址等。
3.6
密钥生成中心 key generation center;KGC
在本部分中，负责选择系统参数、生成签名主密钥并产生用户签名私钥的可信机构。
4 符号
下列符号适用于本文件。
A,B: 使用标识密码系统的两个用户。
cf: 椭圆曲线阶相对于 N 的余因子。
cid: 用一个字节表示的曲线的识别符，其中0x10 表示F, (素数 p>2¹91)上常曲线(即非超奇异曲线),0x11 表 示 Fp 上超奇异曲线，0x12 表示 Fp 上常曲线及其扭曲线。
dsʌ : 用户A 的签名私钥。
e: 从 G₁XG₂ 到 G₁ 的双线性对。
eid: 用一个字节表示的双线性对e 的识别符，其中0x01 表示 Tate 对，0x02 表示 Weil 对，0x03 表
示 Ate 对，0x04 表示 R-Ate 对。
Gr: 阶为素数N 的乘法循环群。
G₁: 阶为素数N 的加法循环群。
G₂: 阶为素数N 的加法循环群。
gm: 乘法群GT 中元素g 的 u 次幂。
Hv(): 密码杂凑函数。
H₁(),H₂(): 由密码杂凑函数派生的密码函数。
hid: 在本部分中，用一个字节表示的签名私钥生成函数识别符，由KGC 选择并公开。
(h,S): 发送的签名。
(h',S'): 收到的签名。
IDa: 用户 A 的标识，可以唯一确定用户A 的公钥。
M: 待签名消息。
M': 待验证消息。
mod n:模 n 运算。例如，23 mod7=2。
P₁: 群 G₁ 的生成元。
P₂ : 群 G₂ 的生成元。
ks: 签名主私钥。
: 由元素P 生成的循环群。
[u]P: 加法群G₁ 、G₂ 中元素 P 的 u 倍 。
[x]: 顶函数，不小于x 的最小整数。例如，[71=7,[8 . 3]=9。
Lx」: 底函数，不大于x 的最大整数。例如，[7」=7,[8.3」=8。
xlly:x 与 y 的拼接，x 和 y 是比特串或字节串。
[x,y]: 不小于x 且不大于y 的整数的集合。
β:扭曲线参数。
5 算法参数与辅助函数
5.1 总则
本部分规定了一个用椭圆曲线对实现的基于标识的数字签名算法。该算法的签名者持有一个标识 和一个相应的签名私钥，该签名私钥由密钥生成中心通过签名主私钥和签名者的标识结合产生。签名 者用自身签名私钥对数据产生数字签名，验证者用签名者的标识验证签名的可靠性。
在签名的生成和验证过程之前，都要用密码杂凑函数对待签消息M 和待验证消息M '进行压缩。
5.2 系统参数组
系统参数组包括曲线识别符cid; 椭圆曲线基域Fq 的参数；椭圆曲线方程参数a 和b; 扭曲线参数β(若cid 的低4位为2);曲线阶的素因子N 和相对于N 的余因子cf; 曲线E(Fq)相对于N的嵌入次数 k;E(Fqd1)(d₁ 整除k) 的 N 阶循环子群G1 的生成元P₁ ;E(Fqd2)(d₂ 整除k) 的 N 阶循环子群G₂ 的生 成元 P₂; 双线性对e 的识别符eid; (选项)G₂ 到 G; 的同态映射ψ。
双线性对e 的值域为N 阶乘法循环群Gr。
系统参数的详细描述及其验证参见GM/T0044.1—2016 的第7章。
5.3 系统签名主密钥和用户签名密钥的产生
KGC 选择并公开用一个字节表示的签名私钥生成函数识别符 hid。
5.4 辅助函数
5.4.1 概述
在本部分规定的基于标识的数字签名算法中，涉及两类辅助函数：密码杂凑函数与随机数发生器。
5.4.2 密码杂凑函数
5.4.2.1 密码杂凑函数 Hv()
密码杂凑函数Hv() 的输出是长度恰为u比特的杂凑值。本部分规定使用国家密码管理主管部门 批准的密码杂凑函数，如 SM3 密码杂凑算法。
5.4.2.2 密码函数H₁()
密码函数 H₁(Z,n):
输入：比特串Z, 整数n。
输出：整数h₁ ∈[1,n- 1]。
步骤1:初始化一个32比特构成的计数器ct=0x00000001;
步骤2:计算hlen=8×[(5×(log₂n))/32];
步骤3:对i......