易中守恒、信达天下 | 热线:010-68873631 |
组合公钥密码体制(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定义三次方程y2 ≡ ( x3 + ax + b ) mod p,G为加法群的基点,n是以G为基点的群的阶。令任意小于n的整数为私钥,则r G=R为对应公钥。
ECC复合特性如下:
在椭圆曲线密码ECC中,任意多对公、私钥,其私钥之和与公钥之和构成新的公、私钥对。
如果,私钥之和为:( r1 + r2 + … + rm )mod n = r
则对应公钥之和为: R1 + R2 + … + Rm = R (点加)
那么,r和R刚好形成新的公、私钥对。
因为,R = R1 + R2 + … + Rm = r1G + r2G +…+ rmG = (r1 + r2 +…+ rm) G
= r G
3 标识密钥
3.1组合矩阵
组合矩阵分为私钥矩阵和公钥矩阵。矩阵大小均为hx32。私钥矩阵由互不相同的小于n的随机数构成,由密钥管理中心(KMC)保有,用于私钥的生成。矩阵中的元素标记ri,j,私钥矩阵用(ri,j)标记。
公钥矩阵由私钥矩阵派生,即ri,jG= (xi,j,yi,j) =Ri,j,公钥矩阵用(Ri,j)标记。
3.2标识到矩阵坐标的映射标识到组合矩阵坐标的映射是通过标识的HASH变换实现的。将HASH输出调整成长度为190比特的映射序列YS,以5比特构成w0,w1,…,w34的字符串,决定列坐标与行坐标。
YS = Hash (ID)=w0,w1,w2,…,w34;
w0的内容u指示列的起始坐标,以后的列坐标是在前列坐标加1实现。
w1 - w32依次指示行坐标。
w33- w37指示分割密钥坐标
3.3标识密钥的组合计算标识私钥(isk)的计算在KMC进行。设第i次行坐标用wi表示,列坐标vi=(u+i) mod 32表示,令标识私钥为isk,那么私钥计算以有限域域Fn上的倍数加法实现,实体Alice的私钥为:
iskAlice= mod n
公钥计算以椭圆曲线Ep(a,b)上的倍点加法实现,按照复合定理,对应公钥为:
IPKAlice= (点加)
4 复合密钥
4.1 标识密钥与分割密钥的复合
KMC统一生成分割密钥集:ssk,SPK;
实体Alice的组合私钥cpk1Alice由KMC计算:
Csk1Alice = (iskAlice +sskAlice) mod n
将组合私钥csk1Alice记入CPK-card并删除分割私钥sskAlice。分割公钥集SPK,则以文件形式公布。
组合公钥将由依赖方计算:
CPK1Alice=IPKAlice+SPKAlice; (SPKAlice的坐标由YS序列中的w33..w34指示)
4.2 标识密钥与伴随密钥的复合(可选项)
实体Alice随机定义一对伴随密钥askAlice, APKAlice,由KMC生成组合私钥:
Csk2Alice = (iskAlice +askAlice) mod n
KMC删除伴随私钥askAlice, 并用Alice的标识密钥对伴随公钥签名:
(APKAlice)=sign1
KMC将实体Alice的组合私钥csk2Alice 伴随公钥APKAlice以及sign1记入CPK-card。
组合公钥将由依赖方计算:
CPK2Alice=IPKAlice+APKAlice; (由签名方Alice提供APKAlice和sign1)
5 数字签名
5.1用分割密钥签名
签名:设:在Alice的ID卡中具有组合私钥csk1Alice,
那么Alice的签名: (AliceID) = sign1 或
(MAC)=sign2
将签名码sign发送给验证方。
验证:验证方计算Alice的公钥:CPK1Alice = IPK Alice + SPK Alice
其中,s(Hash(IDA))®IPKAlice, SPKAlice查表获得。
验证Alice签名: (AliceID)=sign1’ 或
(MAC)=sign2’
如果sign1=sign1’ 则证明AliceID为真,如果sign2=sign2’,则证明MAC为真。
5.2用伴随密钥签名(可选项)签名:设在Alice的ID卡中具有组合私钥csk2Alice,伴随公钥APKAlice,
那么Alice的签名: (TAG)=sign;
将(sign, APKAlice,sign1)提供给验证方。
其中TAG是标识域、时间域或字符串。
验证:设验证方收到签名码(sign, APKAlice,sign1),
验证方计算Alice的标识公钥:σ(ID)→IPK Alice,
验证方验证Alice的伴随公钥: (APKAlice)=sign1’
验证方计算Alice 的组合公钥:CPK2Alice=IPK Alice +APKAlice
验证方验证Alice 的签名: (TAG) =sign’
6 密钥交换
6.1用分割密钥加密
加密:Alice通过Bob的标识求出w33-w37,查找Bob的系统公钥SPKBob;
Alice根据Bob的标识和公钥矩阵计算Bob的标识公钥IPKBob;
Alice计算Bob的公钥:CPK1Bob=IPKBob+SPKBob;
Alice选择随机数r,计算:r·CPK1Bob=β和r G=key;
(将密钥加密协议表示成ENCBOB(key)=β)
Alice加密:Ekey(data) = code;
Alice将code和β发送给Bob
脱密:Bob用自己的私钥计算出key:
csk2Bob-1 β= csk1Bob-1 (r CPK1Bob )= csk1Bob-1 ( r csk1Bob G )= r G = key
(将密钥脱密协议可表示成DECbob(β)=key)
Bob脱密:Dkey(code) = data。
6.2用伴随密钥加密(可选项)在有些在线通信中,如C/S通信,需要证明双方的真实性,则通过认证获得对方的公钥。
请求:客户端发送认证信息,
(ClientID) = sign,APKclient , (APKClient)=sign1
响应:服务器端发送认证信息,
(ServerID) = sign,APKserver, sign1
于是通信双方都具有了对方的公钥。
7 安全性分析以公钥矩阵的大小为32x32,分割序列长度为1024为例。分割密钥对标识密钥的复合,是有限乱数对标识密钥的加密,可能产生重复。想要破解本体制,首先要消除分割密钥的影响,暴露标识密钥的线性关系。如果收集到足够数量的重复,获得1023个满秩的线性无关方程组,本体制就可以破解。因此,能否获取足够数量的重复条件,是保证安全的关键。
通过YS序列的地址码,可以找到相同的地址码,即相同的分割密钥,而相同的分割密钥可以互相抵消。当重复的平均出现数量不足1023时(不满秩),方程无唯一解,体制仍是安全的。假设用户数量为分割密钥数量的1024倍时,即1024x1024=100万,不同的用户平均使用相同的分割密钥1024次。在分割密钥的所有两两组合(1024)2中,重复占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适用于标识鉴别和实体鉴别,易于构建可信系统,可对超大规模的认证网络实施水平化管理。