# 组合公钥标识密钥管理算法

## 前言

本文描述基于椭圆曲线密码的组合公钥标识密钥管理算法 (Combined Public Key Identity-Based Key Management Algorithm based on Elliptic Curve Cryptogaphy, 以下简称CPK标识密钥管理算法)。CPK标识密钥管理算法是一种基于标识的非对称密钥管理算法，可以实现对椭圆曲线密码公私钥的基于身份标识的管理。CPK标识密钥管理算法可以和SM2椭圆曲线公钥密码算法^[1-5]^结合使用，实现基于标识的公钥加密 、数字签名和密钥交换。

## 1 术语和定义

* **主密钥 (Master Secret)** 是标识密钥管理分层体系中处于顶层的密钥。在CPK标识密钥管理算法中，主密钥用于导出系统的公开参数和用户身份标识对应的椭圆曲线密码私钥。
* **公开参数 (Public Parameters)** 是标识密钥管理体系中的系统公开参数，用户通过安全信道获取系统的公开参数。在CPK标识密钥管理算法中，公开参数用于导出用户的椭圆曲线密码公钥。
* **标识 (Identity)** 是可唯一确定一个实体身份的信息。标识应由实体无法否认的信息组成，如实体的可识别名称、电子邮箱、身份证号码、电话号码和所在地址。CPK标识密钥管理算法中标识的含义等同于SM2椭圆曲线公钥密码算法^[2]^对可辨别标识的定义和SM9标识密码算法^[9]^中对标识的定义。
* **密钥生成中心 (Key Generation Center, KGC)** 是负责生成主密钥、导出并发布公开参数和用户私钥的权威机构。

## 2 符号和缩略语

本规范沿用SM2椭圆曲线密码算法^[1]^第2章中对缩略语和符号的定义。

## 3 辅助函数

本部分介绍CPK标识密钥管理算法中的辅助函数。

### 3.1 密码杂凑函数$Hash()$

密码杂凑函数$Hash()$ 的输入是任意长度(或小于某个最大长度)的比特串，输出是固定比特长度的杂凑值。本规范使用获国家密码管理主管部门批准的密码杂凑函数，如SM3密码杂凑算法^[6]^。

### 3.2 $HMAC_K()$

HMAC是基于密码杂凑函数的消息认证码，其输入是密钥$K$和任意长度的比特串。HMAC算法的规范由RFC 2104^[10]^定义。本规范的HMAC要求使用获国家密码管理主管部门批准的密码杂凑函数，如SM3密码杂凑算法^[6]^。

### 3.3 随机数发生器

本部分规定使用国家密码管理主管部门批准的随机数发生器。

## 4 CPK标识密钥管理算法描述

本规范包括主密钥生成算法、公开参数导出算法、用户私钥导出算法和用户公钥导出算法共4个算法。

### 4.1 主密钥生成算法

主密钥是处于标识密钥管理分层结构顶层的密钥。主密钥由KGC生成并安全保存，KGC可以根据用户标识从主密钥导出用户私钥。CPK标识密钥管理算法的主密钥由多元组$\{ECParams, k, S\}$构成，其中包括：

* 椭圆曲线系统参数$ECParams$，椭圆曲线系统参数中基点表示为$G$，基点$G$的阶表示为$n$;
* 允许导出私钥的数量上限$k$，$k$是一个整数，用于限定该主密钥针对不同用户标识导出的用户私钥的最大数量；
* 种子密钥$S$是KGC通过安全的随机数生成器生成的随机比特串，$S$的比特长度应不低于椭圆曲线系统参数中基点阶$n$的比特长度。

主密钥生成算法包括以下步骤：

1. 选择椭圆曲线系统参数$ECParams$，本规范要求使用获国家密码管理部门批准的椭圆曲线系统参数，如SM2椭圆曲线公钥密码算法第5部分^[5]^中给出的256位素域椭圆曲线系统参数；
2. 根据预估的最大选择整数$k$作为生成私钥的数量上限；
3. 通过安全的随机数生成器生成512比特的种子密钥$S$，本规范要求使用符合国家密码管理部门批准的随机数生成器；
4. 输出多元组$\{ECParams, k, S\}$，为CPK标识密钥管理算法的主密钥。


### 4.2 公开参数导出算法

公开参数导出算法的输入为主密钥，输出为公开参数。KGC通过公开参数导出算法从主密钥中导出公开参数，并将公开参数通过安全信道发布给用户。设主密钥为多元组$\{ECParams, k, S\}$，$G$为椭圆曲线系统参数的基点，$n$ 为基点$G$的阶。公开参数导出算法包括以下步骤：

1. 步骤1：初始化一个32比特的计数器 $ct = 0x00000001$
2. 步骤2：对 $i$ 从$1$到$k$ 执行：
  1. 步骤 2.1：计算 $h \leftarrow HMAC_{S}(ct)$，其中HMAC的输入密钥为主密钥多元组中的种子密钥$S$，输入数据为计数器$ct$以高位优先编码的32比特长的比特串，输出的$x$为MAC值，长度等同于HMAC中密码杂凑函数的输出杂凑值长度；
  2. 步骤 2.2：将比特串$x$视为以高位优先编码的整数，计算 $x \leftarrow x \mod{n}$;
  3. 步骤 2.3：通过椭圆曲线多倍点运算计算 $P_i \leftarrow [x]G$；步骤 2.4：计算 $ct \leftarrow ct + 1$;
3. 步骤3：输出多元组 $\{ECParams, k, \{P_i\}_{i=1 .. k}\}$作为公开参数。

### 4.3 用户私钥导出算法

用户私钥导出算法的输入为主密钥和用户标识，输出为用户私钥。KGC通过用户私钥导出算法，根据用户标识从主密钥中导出用户私钥。设主密钥为多元组$\{ECParams, k, S\}$，用户标识$ID$为非0长度的比特串。用户标识私钥导出算法使用的辅助函数包括$Hash$和$HMAC$，$Hash$为密码杂凑算法，$HMAC$为基于$Hash$构造的HMAC算法。用户私钥导出算法步骤如下：

* 步骤1：计算 $Z \leftarrow Hash(ID)$;

* 步骤2：初始化整数 $d \leftarrow 0$；
* 步骤3：初始化一个32比特的计数器 $ct = 0x00000001$;
* 步骤4：对 $i$ 从$1$到$k$ 执行：
  * 步骤4.1：计算 $a \leftarrow HMAC_Z(ct)$
  * 步骤4.2：计算 $x \leftarrow HMAC_{S}(ct)$
  * 步骤4.3：计算 $d \leftarrow (d + a \cdot x) \mod{n}$;
  * 步骤5：输出$d$为用户私钥。

### 4.4 用户公钥导出算法

用户公钥导出算法的输入为公开参数多元组$\{ECparams, k, H\}$、用户标识$ID$，输出为用户公钥$Q$。系统中的任意用户都可以通过用户公钥导出算法，根据某个用户A的标识$ID_A$，从公开参数中导出该用户的公钥$Q_A$，用户公钥导出算法步骤如下：

* 步骤1：计算 $Z \leftarrow Hash(ID)$;
* 步骤2：初始化椭圆曲线点 $Q \leftarrow \infty$为椭圆曲线上的无穷远点；
* 步骤3：初始化一个32比特的计数器 $ct = 0x00000001$;
* 步骤4：对 $i$ 从$1$到$k$ 执行：
  * 步骤4.1：计算 $a \leftarrow HMAC_Z(ct)$
  * 步骤4.3：计算 $Q \leftarrow Q + [a]P_i$;
* 步骤5：输出$Q$为用户公钥。

## 5 KGC的工作流程

由于主密钥中包含导出私钥的数量上限$k$，因此KGC应维护一个已经导出私钥数量的计数器$ck$，在运行私钥导出算法时应检查计数器$ck$的值，如果$ck \ge k$，那么当前主密钥已经导出的私钥数量达到上限$k$，KGC应终止用户私钥导出算法的执行。如果KGC需要增加可以导出的用户私钥数量，那么KGC需要选择更大的$k$值并重新生成主密钥，KGC还需要用新生成的主密钥为所有用户重新导出用户私钥 。

KGC的工作流程如下图所示：

```flow
​```flow
st=>start: 初始化
genmsk=>operation: 通过算法4.1生成主密钥
genmpk=>operation: 通过算法4.2导出公开参数
initck=>operation: 将计数器ck初始化为0
genkey1=>operation: 接收用户密钥生成请求
checkck=>condition: ck是否小于k?
genkey2=>operation: 通过算法4.3导出用户私钥并发布给用户
e=>end

st->genmsk->genmpk->initck->genkey1->checkck
checkck(no)->genmsk
checkck(yes)->genkey2->initck
​```
```

## 6 基于标识的SM2椭圆曲线公钥密码算法

CPK标识密钥管理算法可以和SM2椭圆曲线公钥密码的公钥加密算法^[2]^、数字签名算法^[3]^和密钥交换协议^[4]^结合使用，实现基于标识的SM2椭圆曲线公钥加密 、数字签名和密钥交换协议。

### 6.1 基于标识的公钥加密

### 6.1.1 加密流程

给定CPK标识密钥管理算法公开参数、待加密的消息$M$和接收方的标识$ID_A$，加密过程如下：

1. 调用算法4.4，根据接收方标识$ID_A$，从公开参数中导出接收方的公钥$Q_A$；
2. 调用SM2椭圆曲线公钥加密算法^[4]^中第6章定义的加密算法，用接收方公钥$Q_A$对消息$M$加密，得到密文$C$。

加密方可以根据已知的接收方标识预计算接收方的公钥，并缓存已经计算得到的接收方公钥。

### 6.1.2 解密流程

给定CPK标识密钥管理算法公开参数、给定密文$C$，接收方的解密过程如下：

1. 根据接收方的标识$ID_A$向KGC申请并获得用户私钥$d_A$；
2. 调用SM2椭圆曲线公钥加密算法^[4]^中第7章定义的解密算法，用接收方私钥$d_A$对密文$C$解密，得到明文$M$。

### 6.2 基于标识的数字签名流程

### 6.2.1 签名流程

给定CPK标识密钥管理算法公开参数、消息$M$，签名方的签名过程如下：

1. 根据签名方的标识$ID_A$向KGC申请并获得用户私钥$d_A$；
2. 调用SM2椭圆曲线公钥数字签名算法^[2]^中第6章定义的签名算法，用私钥$d_A$对消息$M$签名，得到签名值$\sigma$。

给定CPK标识密钥管理算法公开参数、消息$M$、签名值$\sigma$和签名方的标识$ID_A$，验证方的验证过程如下：

1. 调用算法4.4，根据接收方标识$ID_A$，从公开参数中导出接收方的公钥$Q_A$；
2. 调用SM2椭圆曲线公钥数字签名算法^[2]^中第7章定义的验证算法，用签名方公钥$Q_A$对消息$M$和签名值$\sigma$进行验证，得到验证结果。


### 6.3 基于标识的密钥交换协议

SM2椭圆曲线公钥密码密钥交换协议[3]要求密钥交换双方需预先获取对方的标识$Z$和公钥$P$，给定CPK标识密钥管理算法公开参数，密钥交换双方可以预先根据对方的标识从公开参数中导出对方的公钥，因此无需传递双方的公钥。

## 参考文献

1. GM/T 0003.1-2012 SM2椭圆曲线公钥密码算法第1部分：总则
2. GM/T 0003.2-2012 SM2椭圆曲线公钥密码算法第2部分：数字签名算法
3. GM/T 0003.3-2012 SM2椭圆曲线公钥密码算法第3部分：密钥交换协议
4. GM/T 0003.4-2012 SM2椭圆曲线公钥密码算法第4部分：公钥加密算法
5. GM/T 0003.5-2012 SM2椭圆曲线公钥密码算法第5部分：参数定义
6. GM/T 0004-2012 SM3密码杂凑算法
7. GM/T 0009-2012 SM2密码算法使用规范
8. GM/T 0010-2012 SM2密码算法加密签名消息语法规范
9. GM/T 0044-2016 SM9标识密码算法
10. RFC 2104. HMAC: Keyed-Hashing for Message Authentication.
