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

2018-04-02 03:04:41陳亞茹

信息安全研究 2018年3期

陳莊陳亞茹

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

在信息化時代，終端設備的增加使物聯網安全面臨巨大挑戰，特別是在軍事、金融等安全性要求特別高的行業，身份認證是解決物聯網安全問題的核心,而身份認證有待于解決的2個核心問題是密鑰管理規?；兔荑€分發.迄今為止，服務器在對終端身份認證主要存在下列3種方式:

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

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

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

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

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

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

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

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

1 組合公鑰(CPK)算法

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

1.1 密鑰矩陣的生成

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

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

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

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

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

1.2 標識密鑰的生成

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

圖1 標識密鑰生成圖

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

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

2.1 G值的選取規則

選取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)，根據y2G=(x3G+axG+b) modp和a+b=p2計算出合適G的取值；

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

步驟6. 輸出G值.

2.2 橢圓曲線的選取

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

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

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

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

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

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

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

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

表1 各種方案的性能對比

4 安全性對比

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

5 結語

本文提出了一種基于雙線性對方法建立的CPK方案，通過選取合適的G點不僅解決了系統的安全性和產生標識密鑰過程中的碰撞問題，而且提高了CPK服務器對終端的認證效率，保密性極強，適用于政府和銀行等保密性要求較高的行業.總體來說，公司的實驗結果一致證明了本方案的安全性、通信性都具有優勢，可以用于政府藍牙耳機、保密箱的應用等.但是，由于本方案具有極強的加密性，導致在破解上可能無從下手，基于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服務認證系統的研究[D]. 天津: 天津大學, 2014

[3]李鵬程. 基于改進CPK的移動互聯網身份認證方案研究與實現[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]常曉林, 馮登國, 卿斯漢. 一次身份認證可訪問多個應用服務器[J]. 軟件學報, 2002, 13(6): 1111-1116

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

[8]孫偉達, 游向東. 一種基于CPK的移動終端加密系統[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]榮昆, 李益發. CPK種子矩陣的優化設計方案[J]. 計算機工程與應用, 2006, 42(24): 120-121

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

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

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

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