组合公钥(cpk)体制(v5.0)
组合公钥（CPK）体制(v5.0) （2010.08）1 引言组合公钥体制(Combined Public Key Cryptosystem，简称CPK)，是在椭圆曲线密码(ECC)上，由组合矩阵和分割密钥序列构成。ECC遵从IEEE标准。组合矩阵(Combining-matrix)分为私钥矩阵和公钥矩阵，分割密钥序列(Separating-key sequence )由一定数量的分割密钥(Separating-key)构成，密钥对用(ssk, SPK)标记。标识密钥(Identity-key)由标识产生，用(isk, IPK)标记。 组合密钥(Combined-key)由标识密钥和分割密钥复合而成，用(csk, CPK)标记。2 ECC复合特性组合公钥体制采用有限域Fp上的椭圆曲线E: y2 ( x3 + ax + b ) mod p，以参数(a, b, G, n, p)定义。其中a, b是系数，a,b,x,yp，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，用（ri,j）或（Ri,j）表示，i=1.h，j=1.32。r是小于n的随机数。私钥矩阵（ri,j）用于私钥的生成，是秘密变量。公钥矩阵由私钥矩阵派生，即 ri,j G= (xi,j,yi,j) =Ri,j，是公开变量。 3.2标识到矩阵坐标的映射标识到组合矩阵坐标的映射通过将标识ID经Hash变换变成YS序列实现：YS = Hash (ID)= w1，w2，w34；w的字长为k比特，k由矩阵的行数h决定，即h=2k，w1 - w32依次指示行坐标。w33- w34指示分割密钥坐标。列坐标从1到32顺序启用。3.3标识密钥的计算标识私钥(isk)的计算在KMC进行。设第i列所用行坐标用wi表示，令标识私钥为isk，那么私钥以有限域域Fp上的倍数加法实现，实体Alice的私钥为：iskAlicemod n 公钥计算以椭圆曲线E上的倍点加法实现，对应公钥为：IPKAlice (点加)4分割密钥分割密钥由YS序列中的w33,w34指示，从分割密钥序列中选取，并只以公钥形式存在，分割公钥序列SPKi可以文件形式公布，或记入CPK-card。5组合密钥标识密钥和分割密钥复合形成组合密钥。设分割私钥为ssk，实体Alice的组合私钥cskAlice由KMC计算：cskAlice = (iskAlice +sskAlice) mod n将组合私钥cskAlice记入Alice的CPK-card并删除分割私钥sskAlice。组合公钥由各依赖方计算：CPKAlice=IPKAlice+SPKAlice； 5数字签名签名函数用SIG标记，验证函数用SIG-1标记。签名：Alice的ID卡提供复合私钥cskAlice，Alice的签名：(AliceID)=sign1 或(MAC) = sign2验证：验证方计算Alice的公钥：CPKAlice = IPK Alice + SPK Alice 其中，s(Hash(AliceID)®IPKAlice, SPKAlice则由YS的w33,w34指示。 验证Alice签名：(AliceID)=sign1 或(MAC)=sign2 如果sign1=sign1, 则证明AliceID为真，如果sign2=sign2,则证明MAC为真。6密钥交换 CPK密钥交换遵从Diffie-Helman协议。加密：Alice通过Bob的标识求出YS序列中的w33-w34，在分割公钥序列中查找出Bob的分割公钥SPKBob；Alice根据Bob的标识和公钥矩阵计算Bob的标识公钥IPKBob；Alice计算Bob的组合公钥：CPKBob=IPKBob+SPKBob；Alice选择随机数r，计算：r·CPKBob=和r G=key；(密钥加密协议可简单表示成ENCBOB(key)=)Alice加密：Ekey(data) = code；Alice将code和发送给Bob脱密：Bob用自己的组合私钥计算出key：cskBob-1 = cskBob-1 (r CPKBob )= cskBob-1 ( r cskBob G )= r G = key(密钥脱密协议可简单表示成DECbob()=key)Bob用对称密钥key脱密：Dkey(code) = data。 7安全界限CPK组合私钥csk是标识私钥isk和分割私钥ssk相加而成，分割私钥序列是乱数序列，用于对标识私钥的加密。因为标识私钥是组合矩阵变量的线性组合，只有消除分割私钥的影响，才能暴露标识密钥的线性方程。消除分割私钥的办法是寻找分割私钥的重复。设组合矩阵变量的总量为N1，分割私钥变量的总量为N2。因为标识密钥方程组的秩为N1-1，要列N1个联立方程，至少要获得N1个重复。假设用户量为N1*N2，分割私钥重复的概率为N1次，那么可以找到N1个重复，但是：a) 在这些重复中，只有参与共谋的才有私钥，可以列出方程，而没有参与共谋的，即使找到了重复，也因为没有私钥，所以列不出方程，因而没有意义。b) 在消除分割私钥影响以后的组合私钥的线性方程中，又只有线性无关方程才有意义，而线性相关方程没有意义。当N1*N2个用户全体参与共谋的情况下，N1个方程恰好满秩的可能性几乎等于零，显然方程不可能有唯一解，私钥的组合矩阵仍然是安全的。8存储量与密钥规模当组合矩阵变量总量为N1，分割密钥变量总量为N2时，公布所需要的空间是两个总量之和（N1+N2），而密钥规模则是两个总量的乘积（N1*N2），因此当N1=N2时，其密钥规模最大。密钥规模是指无意义共谋规模的上限（实际上，离真正得上限还差很远），如果本规模的共谋是不可能事件，那么用户规模可以是无限的。假设ECC密钥长度为160比特（20B），其公钥长度为40B，那么密钥的存储量和密钥规模的关系如下表。N1210 (40KB)212 (160KB)N2210 (40KB)212 (160KB)规模220=1.0x106224=1.6x107小结CPK是基于组合的公钥体制，将密钥生产和密钥管理结合起来，能够实现数字签名和密钥交换，可以满足超大规模信息网络与非信息网络（包括物联）中的标识鉴别、实体鉴别、数据保密需求。
