組合公鑰體制(v50)

1、組合公鑰(CPK)體制(v50)(2010.08)1引言組合公鑰體制(Combined Public Key Cryptosystem，簡稱CPK)，是在橢圓曲線密 碼(ECC)上，由組合矩陣和分割密鑰序列構(gòu)成。ECC遵從IEEE標準。組合矩陣(Combining-matrix)分為私鑰矩陣和公鑰矩陣，分割密鑰序列 (Separating-key sequence )由一定數(shù)量的分割密鑰(Separating-key)構(gòu)成，密鑰對用(ssk, SPK)標記。標識密鑰(Identity-key)由標識產(chǎn)生，用(isk, IPK)標記。組合密鑰(Combined-key)由標識密鑰和分割密鑰復(fù)合而

2、成，用(csk, CPK)標記。2 ECC復(fù)合特性組合公鑰體制采用有限域Fp上的橢圓曲線E: y2三(x3 + ax + b ) mod p，以參數(shù) (a, b, G, n, p)定義。其中a, b是系數(shù)，a,b,x,yp G為加法群的基點，n是以G為基 點的群的階。令任意小于n的整數(shù)為私鑰，則r G=R為對應(yīng)公鑰。ECC復(fù)合特性如下：在橢圓曲線密碼ECC中，任意多對公、私鑰，其私鑰之和與公鑰之和構(gòu)成 新的公、私鑰對。如果，私鑰之和為：(r1 + r2+rm)mod n = r則對應(yīng)公鑰之和為：R1 + R2 + R, = R (點加)那么，和R剛好形成新的公、私鑰對。因為，R 一 R+ R2

3、 + + Rm一iG + 板，+. +mG - (r1 + 版 +. +m) G 一 r G3標識密鑰3.1組合矩陣組合矩陣分為私鑰矩陣和公鑰矩陣。矩陣大小均為hx32，用（）或（%） 表示，i=1.h，j=1.32。r是小于n的隨機數(shù)。私鑰矩陣（用于私鑰的生成，是 秘密變量。公鑰矩陣由私鑰矩陣派生，即jjG=（x.j）yij）二%，是公開變量。3.2標識到矩陣坐標的映射標識到組合矩陣坐標的映射通過將標識ID經(jīng)Hash變換變成YS序列實現(xiàn)：YS = Hash （ID）= w1，w2，w34；w的字長為k比特，k由矩陣的行數(shù)h決定，即h=2k，w1- w32依次指示行坐標。w33- w34指示分

4、割密鑰坐標。列坐標從1到32順序 啟用。3.3標識密鑰的計算標識私鑰（isk）的計算在KMC進行。設(shè)第i列所用行坐標用w表示，令標識 私鑰為isk，那么私鑰以有限域域Fp上的倍數(shù)加法實現(xiàn)，實體Alice的私鑰為：iskm= Y、何 ni i 二1公鑰計算以橢圓曲線E上的倍點加法實現(xiàn)，對應(yīng)公鑰為：叫尸Y氣,（點加）ii 二14分割密鑰分割密鑰由YS序列中的w33,w34指示，從分割密鑰序列中選取，并只以公 鑰形式存在，分割公鑰序列SPKi可以文件形式公布，或記入CPK-card。5組合密鑰標識密鑰和分割密鑰復(fù)合形成組合密鑰。設(shè)分割私鑰為ssk，實體Alice的 組合私鑰cskAlice由KMC計

5、算：cskAlice = (iskAlce +sskAlce)mod n將組合私鑰cskAice記入Alice的CPK-card并刪除分割私鑰sskAlice。組合公鑰由各依賴方計算:CPKAlice=IPKAlice+SPKAlice；5數(shù)字簽名簽名函數(shù)用SIG標記，驗證函數(shù)用SIG-1標記。簽名：Alice的ID卡提供復(fù)合私鑰cskAli，ecskAliceAlice的簽名： SIG (AliceID)=sign1 cskAlicesig . (MAC) = sign2A lice驗證：驗證方計算 Alice 的公鑰：CPKAlice = IPK Alice + SPK Alice其中，(

6、Hash(AliceID)LIIPKAlice, SPKA底則由 YS 的 w33,w34指示。驗證 Alice 簽名：sig，Ka(AlicelD)=signi或SIG i (MAC)=sign2CPK Al”。2如果signsign；，則證明AlicelD為真，如果sign2=sign2，則證明MAC為真。6密鑰交換CPK密鑰交換遵從Diffie-Helman協(xié)議。加密：Alice通過Bob的標識求出YS序列中的w33-w34,在分割公鑰序列中查找出 Bob的分割公鑰SPKBob；Alice根據(jù)Bob的標識和公鑰矩陣計算Bob的標識公鑰IPKBob；Alice 計算 Bob 的組合公鑰：C

7、PKB妒IPKBob+SPKBob；Alice選擇隨機數(shù)r,計算：CPK邛和r G=key ；(密鑰加密協(xié)議可簡單表示成ENCBOB(key)邛)Alice 加密：Ekey(data) = code；Alice將code和P發(fā)送給Bob脫密：Bob用自己的組合私鑰計算出key:cskBob-1 阡 CSk Bob-1 (r CPKBob )= cskBob-1 (r cskBob G )= r G = key(密鑰脫密協(xié)議可簡單表示成DECbob(p)=key)Bob 用對稱密鑰 key 脫密：Dkey(code) = data。7安全界限CPK組合私鑰csk是標識私鑰isk和分割私鑰ssk相

8、加而成，分割私鑰序列 是亂數(shù)序列，用于對標識私鑰的加密。因為標識私鑰是組合矩陣變量的線性組 合，只有消除分割私鑰的影響，才能暴露標識密鑰的線性方程。消除分割私鑰 的辦法是尋找分割私鑰的重復(fù)。設(shè)組合矩陣變量的總量為N1，分割私鑰變量的總量為N2。因為標識密鑰方 程組的秩為N1-1，要列N1個聯(lián)立方程，至少要獲得N1個重復(fù)。假設(shè)用戶量為 N1*N2,分割私鑰重復(fù)的概率為N1次，那么可以找到N1個重復(fù)，但是：在這些重復(fù)中，只有參與共謀的才有私鑰，可以列出方程，而沒有參與 共謀的，即使找到了重復(fù)，也因為沒有私鑰，所以列不出方程，因而沒有意義。在消除分割私鑰影響以后的組合私鑰的線性方程中，又只有線性無關(guān)

9、方 程才有意義，而線性相關(guān)方程沒有意義。當(dāng)N1*N2個用戶全體參與共謀的情況下，N1個方程恰好滿秩的可能性幾乎 等于零，顯然方程不可能有唯一解，私鑰的組合矩陣仍然是安全的。8存儲量與密鑰規(guī)模當(dāng)組合矩陣變量總量為N1，分割密鑰變量總量為N2時，公布所需要的空間 是兩個總量之和(N1+N2)，而密鑰規(guī)模則是兩個總量的乘積(N1*N2)，因此當(dāng)N1=N2時，其密鑰規(guī)模最大。密鑰規(guī)模是指無意義共謀規(guī)模的上限（實際上，離 真正得上限還差很遠），如果本規(guī)模的共謀是不可能事件，那么用戶規(guī)?？梢允?無限的。假設(shè)ECC密鑰長度為160比特（20B），其公鑰長度為40B，那么密鑰 的存儲量和密鑰規(guī)模的關(guān)系如下表。N12i0 (40KB)212 (160KB