关于我们

1 引言

组合公钥密码体制(CPK-Cryptosystem)是在椭圆曲线密码(ECC)上构建的基于标识的密码体制。CPK的组合密钥主要由标识密钥和分割密钥构成。标识密钥和分割密钥复合成组合密钥(Combined-Key)，用(csk1, CPK1)标记。

标识密钥(Identity-Key)由实体的标识通过组合矩阵生成。组合矩阵(combining matrix)由密钥管理中心(KMC)定义，分私钥矩阵和公钥矩阵。私钥矩阵用于私钥的生产，需要保密；而公钥矩阵用于公钥的生成，需要公布。组合矩阵为标识和密钥的绑定关系提供证明。标识密钥对用(isk, IPK)标记。

分割密钥(Separating-Key)是KMC统一定义的有限的密钥序列，用(ssk, SPK)标记。

伴随密钥(Accompany-Key)是可选项，伴随密钥由各个体自行定义的无限的密钥序列，用(ask, APK)标记。伴随密钥与标识密钥复合的组合密钥用（csk2，CPK2）标记。

2 ECC复合特性

组合公钥体制采用有限域P上的椭圆曲线密码，以(a, b, G, n, p)定义。其中a, b定义三次方程y² ≡ ( x³ + ax + b ) mod p，G为加法群的基点，n是以G为基点的群的阶。令任意小于n的整数为私钥，则r G=R为对应公钥。

ECC复合特性如下：

在椭圆曲线密码ECC中，任意多对公、私钥，其私钥之和与公钥之和构成新的公、私钥对。

如果，私钥之和为：( r₁ + r₂ + … + r_m )mod n = r

则对应公钥之和为： R₁ + R₂ + … + R_m = R  (点加)

那么，r和R刚好形成新的公、私钥对。

因为，R = R₁ + R₂ + … + R_m = r₁G + r₂G +…+ r_mG = (r₁ + r₂ +…+ r_m) G

        = r G

3 标识密钥

 3.1组合矩阵

组合矩阵分为私钥矩阵和公钥矩阵。矩阵大小均为hx32。私钥矩阵由互不相同的小于n的随机数构成，由密钥管理中心(KMC)保有，用于私钥的生成。矩阵中的元素标记r_i,j，私钥矩阵用（r_i,j）标记。

公钥矩阵由私钥矩阵派生，即r_i,jG= (x_i,j,y_i,j) =R_i,j，公钥矩阵用（R_i,j）标记。

 3.2标识到矩阵坐标的映射

标识到组合矩阵坐标的映射是通过标识的HASH变换实现的。将HASH输出调整成长度为190比特的映射序列YS，以5比特构成w₀，w₁，…，w₃₄的字符串，决定列坐标与行坐标。

YS = Hash (ID)=w₀，w₁，w₂，…，w₃₄；

w₀的内容u指示列的起始坐标，以后的列坐标是在前列坐标加1实现。

w₁ - w₃₂依次指示行坐标。

w₃₃- w₃₇指示分割密钥坐标

 3.3标识密钥的组合计算

标识私钥(isk)的计算在KMC进行。设第i次行坐标用w_i表示，列坐标v_i=(u+i) mod 32表示，令标识私钥为isk，那么私钥计算以有限域域Fn上的倍数加法实现，实体Alice的私钥为：

isk_Alice＝ mod n

公钥计算以椭圆曲线Ep(a,b)上的倍点加法实现，按照复合定理，对应公钥为：

IPK_Alice＝  (点加)

4 复合密钥

 4.1 标识密钥与分割密钥的复合

KMC统一生成分割密钥集：ssk，SPK；

实体Alice的组合私钥cpk1_Alice由KMC计算：

Csk1_Alice = (isk_Alice +ssk_Alice) mod n

将组合私钥csk1_Alice记入CPK-card并删除分割私钥ssk_Alice。分割公钥集SPK，则以文件形式公布。

组合公钥将由依赖方计算：

CPK1_Alice=IPK_Alice+SPK_Alice;  (SPK_Alice的坐标由YS序列中的w₃₃..w₃₄指示)

 

 4.2 标识密钥与伴随密钥的复合（可选项）

实体Alice随机定义一对伴随密钥ask_Alice, APK_Alice，由KMC生成组合私钥：

Csk2_Alice = (isk_Alice +ask_Alice) mod n

KMC删除伴随私钥ask_Alice, 并用Alice的标识密钥对伴随公钥签名：

(APK_Alice)=sign₁

KMC将实体Alice的组合私钥csk2_Alice 伴随公钥APK_Alice以及sign₁记入CPK-card。

组合公钥将由依赖方计算：

CPK2_Alice=IPK_Alice+APK_Alice;  (由签名方Alice提供APK_Alice和sign₁)

5 数字签名

 5.1用分割密钥签名

签名：设:在Alice的ID卡中具有组合私钥csk1_Alice，

那么Alice的签名： (AliceID) = sign₁ 或

(MAC)=sign₂

将签名码sign发送给验证方。

验证：验证方计算Alice的公钥：CPK1_Alice = IPK _Alice + SPK _Alice

      其中，s(Hash(ID_A))®IPK_Alice,  SPK_Alice查表获得。

      验证Alice签名：  (AliceID)=sign₁’ 或

 (MAC)=sign₂’

    如果sign₁=sign₁’ 则证明AliceID为真，如果sign₂=sign₂’,则证明MAC为真。

 5.2用伴随密钥签名（可选项）

签名：设在Alice的ID卡中具有组合私钥csk2_Alice，伴随公钥APK_Alice，

那么Alice的签名： (TAG)＝sign; 

将(sign, APK_Alice,sign₁)提供给验证方。

其中TAG是标识域、时间域或字符串。

验证：设验证方收到签名码(sign, APK_Alice,sign₁)，

验证方计算Alice的标识公钥：σ(ID)→IPK _Alice，

验证方验证Alice的伴随公钥： (APK_Alice)=sign₁’

验证方计算Alice 的组合公钥：CPK2_Alice＝IPK _Alice +APK_Alice

验证方验证Alice 的签名： (TAG) =sign’

6 密钥交换

  6.1用分割密钥加密

加密：Alice通过Bob的标识求出w₃₃-w₃₇，查找Bob的系统公钥SPK_Bob；

Alice根据Bob的标识和公钥矩阵计算Bob的标识公钥IPK_Bob；

Alice计算Bob的公钥：CPK1_Bob=IPK_Bob+SPK_Bob；

Alice选择随机数r，计算：r·CPK1_Bob=β和r G=key；

(将密钥加密协议表示成ENC_BOB(key)=β)

Alice加密：E_key(data) = code；

Alice将code和β发送给Bob

脱密：Bob用自己的私钥计算出key：

csk2_Bob^-1 β= csk1_Bob^-1 (r CPK1_Bob )= csk1_Bob^-1 ( r csk1_Bob G )= r G = key

(将密钥脱密协议可表示成DEC_bob(β)=key)

Bob脱密：D_key(code) = data。

  6.2用伴随密钥加密（可选项）

在有些在线通信中，如C/S通信，需要证明双方的真实性，则通过认证获得对方的公钥。

请求：客户端发送认证信息，

 (ClientID) = sign，APK_client , (APK_Client)=sign₁

响应：服务器端发送认证信息，

 (ServerID) = sign，APK_server, sign₁

于是通信双方都具有了对方的公钥。

7 安全性分析

以公钥矩阵的大小为32x32，分割序列长度为1024为例。分割密钥对标识密钥的复合，是有限乱数对标识密钥的加密，可能产生重复。想要破解本体制，首先要消除分割密钥的影响，暴露标识密钥的线性关系。如果收集到足够数量的重复，获得1023个满秩的线性无关方程组，本体制就可以破解。因此，能否获取足够数量的重复条件，是保证安全的关键。

通过YS序列的地址码，可以找到相同的地址码，即相同的分割密钥，而相同的分割密钥可以互相抵消。当重复的平均出现数量不足1023时（不满秩），方程无唯一解，体制仍是安全的。假设用户数量为分割密钥数量的1024倍时，即1024x1024=100万，不同的用户平均使用相同的分割密钥1024次。在分割密钥的所有两两组合(1024)²中，重复占1/1024，这1024对重复对系统不够成任何威胁，这是因为：

a) 在这些重复中，只有参与共谋的起作用，而不参与共谋的就没有意义。假设用户群的一半参与共谋，那么在1024对重复中有一半是没有意义的，只有一半重复才有意义；

b) 在消除分割密钥影响以后的标识密钥的线性方程中，又只有线性无关方程才有意义，而线性相关方程就没有意义。

因此，当用户数量为分割密钥数量的1024倍时，可以不计共谋数量，本方案仍是安全的。设组合矩阵变量数为N1，分割密钥序列的变量数为N2，那么存储空间为N1+N2（加法），规模为N1*N2（乘法），因此，在相同的存储条件下，当标识密钥总量等于分割密钥总量时，可获得最大规模。规模是指无意义共谋的上限，如果本规模的共谋是不可能事件，那么，用户规模可以是无限的。部分存储空间和规模的关系见下表。

                         密钥存储与规模

N1	210 (40KB)	212 (160KB)	216 (2.6MB)	217 (5.2MB)
N2	210 (40KB)	212 (160KB)	216 (2.6MB)	217 (5.2MB)
存储	80KB	320KB	5.2MB	10.4MB
规模	220=1..0x106	224=1.6x107	232=4.2x109	234=1.7x1010

 

8 小结

组合矩阵和分割密钥由密钥管理中心（KMC）（信任根）统一定义，适应双向或单向认证模式下的数字签名和密钥交换。CPK适用于标识鉴别和实体鉴别，易于构建可信系统，可对超大规模的认证网络实施水平化管理。