一種解決組合公鑰密鑰碰撞的方案

陳 莊 陳亞茹

(重慶理工大學計算機科學與工程學院 重慶 400054) (cz@cqut.edu.cn)

在信息化時代，終端設備的增加使物聯(lián)網(wǎng)安全面臨巨大挑戰(zhàn)，特別是在軍事、金融等安全性要求特別高的行業(yè)，身份認證是解決物聯(lián)網(wǎng)安全問題的核心,而身份認證有待于解決的2個核心問題是密鑰管理規(guī)模化和密鑰分發(fā).迄今為止，服務器在對終端身份認證主要存在下列3種方式:

1) 公鑰基礎設施(PKI).這是目前最廣泛的認證方式，需要認證中心CA和大量數(shù)據(jù)庫的支持，其中生成的密鑰是隨機產(chǎn)生的，用戶名和密鑰不存在線性關系，因此存在證書管理繁瑣、數(shù)據(jù)庫維護復雜、成本較高的問題，難以實現(xiàn)對密鑰的規(guī)?；芾?

2) 基于身份的密碼體制(IBE).主要的核心體制是用戶名和密鑰存在線性關系，通過身份標識直接進行認證，雖然在一定程度上解決了PKI認證過程中需要第三方的支持，但是需要保存用戶參數(shù)，在密鑰存儲上需要提供額外的空間，雖然有統(tǒng)一的密鑰管理系統(tǒng)，但是密鑰分發(fā)存在缺點,成本性也比較高.

3) 組合公鑰(CPK).是我國自主開發(fā)的算法認證過程中用戶標識經(jīng)過哈希函數(shù)、映射算法產(chǎn)生種子公私鑰對，種子公鑰經(jīng)過組合運算產(chǎn)生密鑰，認證時客戶端保存公共用戶參數(shù)，無需第三方CA的支持，實現(xiàn)了密鑰的規(guī)模化管理和分發(fā)，在成本和實用上得到認可.因此，CPK成為我國獨立進行技術研究的重點，并運用于大數(shù)據(jù)[1]、云計算[2-3]、身份認證[4-8]、防偽系統(tǒng)[9]等方面.

相比較PKI和IBE，CPK解決了PKI和IBE在認證過程中存在的問題，基于CPK本身的特性，認證過程在CPK芯片實現(xiàn)，客戶端通過存儲公鑰因子經(jīng)過組合運算生成大量的公鑰對，效率高、安全性強、占用資源少.通過不斷地改進，CPK的安全性得到不斷完善和增強.但是在改進過程中發(fā)現(xiàn)CPK在密鑰產(chǎn)生過程中會出現(xiàn)相同的身份，即密鑰碰撞.產(chǎn)生密鑰碰撞的原因是由下面2個環(huán)節(jié)引起的:1)用戶標識經(jīng)過哈希函數(shù)生成種子公私鑰對(簡稱環(huán)節(jié)1)；2)種子密鑰又經(jīng)過ECC算法等產(chǎn)生標識密鑰(簡稱環(huán)節(jié)2).因此發(fā)現(xiàn)一種有效解決密鑰碰撞的方案成為了CPK完善和發(fā)展的浪潮.

在文獻[12]中，為了解決?！皀”運算提出了約束橢圓曲線?！皀”方案，即在環(huán)節(jié)2的過程中進行研究.該方案解決了在模“n”下的碰撞問題，但是在產(chǎn)生種子密鑰對過程中無法解決經(jīng)過哈希函數(shù)運算引起的碰撞.

文獻[13]提出了一種新的方法來解決CPK的密鑰碰撞問題.該方法提高密鑰效率的原則是降低種子矩陣的規(guī)?；?，解決了文獻[12]中哈希運算可能產(chǎn)生的碰撞問題和文獻[11]中?！皀”運算出現(xiàn)的碰撞問題.但是映射識別過程中沒有考慮到av=0(1≤v≤n)系數(shù)的情況.

文獻[14]提出了映射方案去解決文獻[13]中av=0(1≤v≤n)的情況.該方案通過縮小種子矩陣的公共參數(shù)有效地解決了橢圓曲線規(guī)模膨脹等問題，進一步提高了計算效率.但是，在標識映射環(huán)節(jié)降低了整體系統(tǒng)的安全性.

本文從用戶標識經(jīng)過哈希生成種子密鑰矩陣和種子密鑰矩陣產(chǎn)生標識密鑰的環(huán)節(jié)出發(fā)，提出了一種雙線性對方法，不僅解決了文獻[11-12]提出的問題，而且通過離散對數(shù)降低橢圓曲線的規(guī)模，解決了文獻[14]中安全性和無碰撞的比特流兼容性問題.

1 組合公鑰(CPK)算法

荊海龍[15]提出了CPK可以通過有線域離散對數(shù)和橢圓曲線這2種方法構建.在相同的資源下，與有限域離散對數(shù)相比較，橢圓曲線的構建所需要的密鑰矩陣在內(nèi)存上更少，但在效率性上更高.因此，本文構建基于雙線性對算法的橢圓曲線離散對解決CPK碰撞問題.

1.1 密鑰矩陣的生成

橢圓曲線的參數(shù)T=(a,b,G,n,p)，其中，p為階數(shù)，a,b∈Fp，G為基點，n為G上的階.Ri,j(0≤i≤m,0≤j≤n)為PSK的元素，ri,j為SSK的元素，矩陣規(guī)模為m×n.

1) 構建的種子公鑰矩陣PSK和種子私鑰矩陣SSK如下：

其中，ri,j是Ri,j=(xi,j,yi,j)對于G的離散對數(shù).顯然，PSK與SSK這2個矩陣中任一對應位置上的元素Ri,j=(xi,j,yi,j)與ri,j形成一個公私鑰對，故組合PSK中的倍點與SSK中的離散對數(shù)也可構成公私鑰對.

2) 基于種子矩陣的密鑰生成如下：

根據(jù)規(guī)則產(chǎn)生選取序列，在產(chǎn)生的序列之后，種子公鑰矩陣與私鑰矩陣根據(jù)該序列選取對應的位置上的元素來組合，這樣可以產(chǎn)生一個實體的CPK公私鑰對.

1.2 標識密鑰的生成

利用CPK算法生成標識密鑰的過程如圖1所示，通過對身份標識進行哈希函數(shù)運算和ECC算法產(chǎn)生標識密鑰.首先用戶標識經(jīng)過哈希函數(shù)運算和行映射算法生成種子矩陣，然后種子矩陣經(jīng)過組合運算生成標識密鑰.

圖1 標識密鑰生成圖

系數(shù)映射算法[14]通過從密鑰生成和種子矩陣構建的環(huán)節(jié)出發(fā),解決了文獻[13]中av=0(1≤v≤n)的情況，降低了種子矩陣存儲空間.但是在研究過程中發(fā)現(xiàn)存在比特流不兼容和安全隱患的問題，本文采用雙線性對用戶標識進行映射，解決了文獻[11-12]的哈希函數(shù)運算引起的碰撞問題，同時，經(jīng)過雙曲線選取合適的G的取值解決了文獻[14]中比特流產(chǎn)生過程中不安全性問題.

2 基于雙線性對方法選取G值

2.1 G值的選取規(guī)則

選取G值的具體步驟如下：

步驟1. 選取G1和G2，定義雙線性對:G1×G2→G3；

步驟2. 若len≤lenc，id先用比特0填充成lenc.設MP0=data1,MPi+1=E(MPi)(i≥0)，則計算行映射算法MP=E(id,key)；

步驟3. 若lenc≤lens則計算MPi+1=E(MPi,key)(0≤i≤lenc)；

步驟4. 通過行映射算法選取序列之后,選取一個合適的因子p(1≤p≤n)，根據(jù)y2G=(x3G+axG+b) modp和a+b=p2計算出合適G的取值；

步驟5. CPK密鑰生成中心通過計算O=(h1(Z)⊕h2(Q))和key是否相等進一步來驗證G取值的合理性.h1和h2是哈希函數(shù)運算，Z為橢圓曲線的主密鑰，用戶私鑰為Q.

步驟6. 輸出G值.

2.2 橢圓曲線的選取

在從上面G值的選取之中存在一個最大的因子p，其種子矩陣的長度為len+2p-3.滿足橢圓曲線的五元組T=(a,b,G,n,p)中n的長度最少為len+2p-3，這樣在任意的系數(shù)序列中可以避免模n運算而引起的碰撞.

3 無碰撞CPK方案的性能對比

至此，本文提出G值的取值方法上解決了安全性和比特流兼容性和安全問題.對本文提出的選取的方案與以前的方案進行對比，會發(fā)現(xiàn)在相同規(guī)模的需要下，種子矩陣密鑰占用更少的空間，成本更低，而且不會發(fā)生用戶標識相同情況下引起的碰撞問題.

假設矩陣的規(guī)模為m×n，每行av的長度為l，選取的G值的比特長度為Lr(av)=t.經(jīng)過實驗證明系統(tǒng)的安全性為1 024 b.

文獻[11]中產(chǎn)生的密鑰對數(shù)量為w=2n l，序列長度為nl(單位為b).種子矩陣的規(guī)模Nmax=nl(單位為kb)，橢圓曲線規(guī)模為256 b.矩陣的空間為M=nml.

文獻[12]中產(chǎn)生的密鑰對數(shù)量為w=2(t+l)n，序列長度為(t+l)n(單位為b).種子矩陣的規(guī)模Nmin=256 kb和Nmax=253+mn(t+2)(單位為kb)，橢圓曲線規(guī)模為255+mn(t+2)(單位為b).矩陣的空間為M=mnNmax.

本方案可產(chǎn)生的密鑰對數(shù)量為w=2n(t+l)，序列長度為n(t+l)(單位為b).種子矩陣的規(guī)模Nmax=256 kb，橢圓曲線規(guī)模為1 024 b.矩陣的空間為M=mnNmax.

假設t=4,系統(tǒng)的安全需求為1 024 b,各種方案的性能對比如表1所示：

表1 各種方案的性能對比

4 安全性對比

本文在密鑰產(chǎn)生過程中在橢圓曲線上選擇合適的G點，然后根據(jù)G點進行相應的映射，與以前的CPK算法[14]相比較，沒有在環(huán)節(jié)1過程中通過減少哈希函數(shù)運算來避免密鑰的碰撞，也沒有文獻[13]在環(huán)節(jié)2過程中僅僅通過公鑰進行對比來避免ECC算法.本方案通過選取合適的G值可以避免窮盡等一系列攻擊.

5 結 語

本文提出了一種基于雙線性對方法建立的CPK方案，通過選取合適的G點不僅解決了系統(tǒng)的安全性和產(chǎn)生標識密鑰過程中的碰撞問題，而且提高了CPK服務器對終端的認證效率，保密性極強，適用于政府和銀行等保密性要求較高的行業(yè).總體來說，公司的實驗結果一致證明了本方案的安全性、通信性都具有優(yōu)勢，可以用于政府藍牙耳機、保密箱的應用等.但是，由于本方案具有極強的加密性，導致在破解上可能無從下手，基于CPK的芯片是否能通過國家密碼局的認可是下一步需要研究的重點.

[1]Chris V. A spatial distribution measure and collision analysis technique for distributed space systems[J]. Electronic Commerce Research, 2016, 32(8): 45-56

[2]田秀明. 基于CPK的Web服務認證系統(tǒng)的研究[D]. 天津: 天津大學, 2014

[3]李鵬程. 基于改進CPK的移動互聯(lián)網(wǎng)身份認證方案研究與實現(xiàn)[D]. 南京: 南京郵電大學, 2016

[4]李濤. 基于CPK技術的無碰撞的多作用域身份認證算法的研究[D]. 北京: 中國科學院大學, 2015

[5]Feng Yu. Secure authentication scheme based on CPK[J]. Journal of Networks, 2010, 5(9): 1106-1113

[6]常曉林, 馮登國, 卿斯?jié)h. 一次身份認證可訪問多個應用服務器[J]. 軟件學報, 2002, 13(6): 1111-1116

[7]馬宇馳, 趙遠, 鄧依群, 等. 基于CPK的可信平臺用戶登錄認證方案[J]. 計算機工程與應用, 2010, 46(1): 90-94

[8]孫偉達, 游向東. 一種基于CPK的移動終端加密系統(tǒng)[J]. 信息安全與通信保密, 2015, 37(12): 124-126

[9]Chen Y, Chou J S. ECC-based untraceable authentication for large-scale active-tag RFID systems[J]. Electronic Commerce Research, 2015, 15(1): 97-120

[10]王公浩, 王玟, 吳鐸, 等. CPK隨機碰撞概率分析[J]. 信息安全與通信保密, 2008, 30(11): 87-88

[11]榮昆, 李益發(fā). CPK種子矩陣的優(yōu)化設計方案[J]. 計算機工程與應用, 2006, 42(24): 120-121

[12]馬芯宇, 龍翔, 范修斌. 無碰撞CPK的種子庫構建和選取方案[J]. 計算機工程與應用, 2012, 48(27): 99-104, 113

[13]馬安君, 李方偉, 朱江. 組合公鑰體制的線性共謀攻擊分析[J]. 計算機應用, 2013, 33(8): 2225-2227

[14]李濤, 張海英, 楊駿, 等. 無碰撞組合公鑰的種子密鑰矩陣的優(yōu)化設計方案[J]. 計算機應用, 2015, 35(1): 83-87

[15]邢海龍. 組合公鑰CPK關鍵技術研究與應用[D]. 長沙: 國防科學技術大學, 2009

陳莊

教授，碩士生導師，主要研究方向為企業(yè)信息化管理、網(wǎng)絡與信息安全.

cz@cqut.edu.cn

陳亞茹

碩士研究生,主要研究方向為信息安全.

642200814@qq.com