一種基于組合公鑰的密鑰派生方案

羅一帆， 張大偉， 常 亮， 劉曉東， 馬儒瀟

(1.北京交通大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院 北京 100044； 2. 桂林電子科技大學(xué) 廣西可信軟件重點(diǎn)實(shí)驗(yàn)室 廣西 桂林 541004； 3.山東大學(xué) 網(wǎng)絡(luò)信息安全研究所 山東 濟(jì)南 250100)

0 引言

在安全等級要求很高的系統(tǒng)中，單一密鑰的簽名方案存在風(fēng)險(xiǎn)，一旦密鑰泄露或是被攻破，整個(gè)系統(tǒng)的安全就不復(fù)存在了.為了提高系統(tǒng)的安全性，一般考慮采用密鑰派生方案.常用的密鑰派生都是采用多次迭代哈希的方案，將最后的哈希作為派生密鑰[1].但是這種方案在泄露其中一個(gè)密鑰后可以通過迭代算法推導(dǎo)出之后的派生密鑰，存在著安全隱患.

基于標(biāo)識的組合公鑰(combined public key，CPK)體制[2-5]是一種新的集中式公鑰管理模式，它可以通過公私鑰矩陣中的公私鑰因子經(jīng)線性組合派生出大量的公私鑰對，而公私鑰矩陣本身的存儲開銷并不大.目前CPK的主要用處是基于用戶身份的大規(guī)模密鑰分配，但CPK還有其他方面的應(yīng)用.例如文獻(xiàn)[6]提出了一種基于CPK的用戶身份認(rèn)證算法,文獻(xiàn)[7]提出了一種基于CPK的數(shù)字簽名方案,但是它們并沒有分析解決CPK本身存在的安全問題.由于公私鑰是通過公私鑰矩陣中的公私鑰因子經(jīng)過線性疊加得到的，因此存在針對公私鑰的3種共謀攻擊：線性共謀攻擊[8-9]、選擇共謀攻擊和隨機(jī)共謀攻擊[10].文獻(xiàn)[11-12]通過引入映射系數(shù)的方式提高了系統(tǒng)安全界限，解決了選擇共謀攻擊，但是經(jīng)過深入分析，發(fā)現(xiàn)其對模運(yùn)算理解有誤，導(dǎo)致對線性共謀攻擊的分析有誤.文獻(xiàn)[13]通過引入輔助矩陣和乘法關(guān)系改變了密鑰間的線性關(guān)系，但是沒有完全解決線性共謀攻擊，也增加了計(jì)算的復(fù)雜性.

本文設(shè)計(jì)了一種基于CPK的密鑰派生方案，對不同的消息采用不同的密鑰簽名.通過改變映射算法，讓私鑰由私鑰矩陣中每個(gè)元素乘上素?cái)?shù)映射系數(shù)后模加得到，使映射系數(shù)矩陣的秩達(dá)到列滿秩m×h.同時(shí)，任意小于其秩的數(shù)量的私鑰間均是線性無關(guān)的，無法通過合謀得到其他消息的簽名私鑰，使得系統(tǒng)在泄露私鑰的個(gè)數(shù)小于m×h時(shí)都是安全的.

1 CPK算法

系統(tǒng)參數(shù)記為T=(a,b,n,G,p)，其中(a,b)是定義在有限域上的橢圓曲線y2=(x3+ax+b)modp的非負(fù)整數(shù)；G是加法群的基點(diǎn)；n是以G為基點(diǎn)的群的階；p是有限域的階.

根據(jù)橢圓曲線參數(shù)生成公私鑰對，構(gòu)造規(guī)模為m×h的公鑰矩陣PKM和私鑰矩陣SKM：

(1)

根據(jù)用戶身份ID計(jì)算與ID對應(yīng)的矩陣元素坐標(biāo)(index1,1),(index2,2),…,(indexh,h)，其中(indexi,i)表示密鑰矩陣中行數(shù)為indexi、列數(shù)為i的元素.按照與ID對應(yīng)的矩陣元素坐標(biāo)，選取公鑰矩陣中的元素計(jì)算用戶公鑰PK=(rindex1,1+rindex2,2+…+rindexh,h)G，選取私鑰矩陣中的元素計(jì)算用戶私鑰sk=(rindex1,1+rindex2,2+…+rindexh,h)modn.由此可見用戶公鑰PK=sk×G，滿足橢圓曲線公私鑰對的對應(yīng)關(guān)系.

2 密鑰派生算法

本算法的基本思想是利用CPK派生出大量公私鑰，對不同的消息使用不同的私鑰進(jìn)行簽名，使用對應(yīng)公鑰驗(yàn)證簽名.整個(gè)算法包括系統(tǒng)參數(shù)生成、密鑰派生、簽名與驗(yàn)簽3個(gè)部分.

2.1 系統(tǒng)參數(shù)生成

選取橢圓曲線密碼參數(shù)T=(a,b,n,G,p)，在Zn(Zn為模n的有限域)中隨機(jī)選取m×h個(gè)私鑰種子構(gòu)建私鑰矩陣SKM和公鑰矩陣PKM，如(1)式所示. 選取不同的素?cái)?shù)構(gòu)成映射系數(shù)序列MCS，MCS={m1,m2,…}，其中mi為素?cái)?shù).公開橢圓曲線密碼參數(shù)T、公鑰矩陣PKM和映射系數(shù)序列MCS.

2.2 密鑰派生

密鑰派生算法主要包括以下3個(gè)步驟：

1) 計(jì)算映射系數(shù).對消息M進(jìn)行哈希后按位分成m×h幀，即H(M)=w1,w2,…，wm×h，第i幀對應(yīng)映射系數(shù)序列MCS中的第i個(gè)素?cái)?shù)，故消息M的m×h個(gè)映射系數(shù)為MCS(w1),MCS(w2),…,MCS(wm×h).

2) 計(jì)算簽名私鑰.映射系數(shù)與私鑰矩陣SKM中私鑰種子相乘后模加得到簽名私鑰skM，skM=(MCS(w1)×r1,1+…+MCS(wm)×rm,1+…+MCS(wm×h)×rm×h)modn.

3) 計(jì)算驗(yàn)證公鑰.映射系數(shù)與公鑰矩陣PKM中公鑰種子相乘后相加得到驗(yàn)證公鑰PKM，PKM=MCS(w1)×R1,1+…+MCS(wm)×Rm,1+…+MCS(wm×h)×Rm×h.

其中簽名者需要執(zhí)行步驟1)和2)，驗(yàn)簽者需要執(zhí)行步驟1)和3).

2.3 簽名與驗(yàn)簽

簽名. 簽名者按照上述私鑰生成算法生成簽名私鑰skM，對消息M用標(biāo)準(zhǔn)橢圓曲線簽名算法(ECDSA、SM2)進(jìn)行簽名得到sigskM(M)：sigskM(M)←sig(skM,M).

驗(yàn)簽. 驗(yàn)簽者希望驗(yàn)證簽名sigskM(M)時(shí)，按照上述公鑰生成算法計(jì)算對應(yīng)公鑰PKM后進(jìn)行驗(yàn)證：0/1←Verify(PKM,sigskM(M),M).若結(jié)果是1，說明驗(yàn)證通過，否則驗(yàn)證不通過.

3 安全分析

在傳統(tǒng)CPK算法中，私鑰是由私鑰種子經(jīng)過映射選取后模加得到，因此存在一定的線性關(guān)系.針對這種線性關(guān)系，存在3種共謀攻擊的方法，即線性共謀攻擊、選擇共謀攻擊和隨機(jī)共謀攻擊.

3.1 線性共謀攻擊

線性共謀攻擊可以分為兩種：一種是通過聯(lián)立足夠的私鑰方程解出私鑰矩陣的通解；另一種是通過多個(gè)私鑰線性組合得到其他私鑰.在基本CPK方案中，私鑰是通過私鑰矩陣每列隨機(jī)選取一個(gè)值模加得到，即sk=(rindex1,1+rindex2,2+…+rindexh,h)modn.將所有的私鑰組合用矩陣形式表示為

(2)

映射系數(shù)矩陣中的元素，即ta(b,c)的含義是：a表示第幾個(gè)私鑰的組合方程，b表示在私鑰矩陣的第幾行，c表示在私鑰矩陣的第幾列.ta(b,c)的取值集合ξ={1,0}，1表示私鑰矩陣中對應(yīng)位置被取到，0則表示未被取到.對映射系數(shù)矩陣進(jìn)行初等變換，將第i+1,…,i+m(i=1,m+1,2m+1,…)列加到第i列，會得到h個(gè)全1的列，故映射系數(shù)矩陣的秩為m×h-h+1.

對于第1種線性共謀攻擊，要想解出私鑰矩陣的通解，至少需要m×h-h+1個(gè)線性無關(guān)的私鑰.因此，提高矩陣的規(guī)?？梢栽黾影踩?但是，對于第2種線性共謀攻擊，并不是小于映射系數(shù)矩陣秩的私鑰個(gè)數(shù)就一定線性無關(guān)，可能存在小于秩數(shù)量的私鑰經(jīng)過線性組合得到新的私鑰，而出現(xiàn)這種問題的根本原因是基本CPK方案中私鑰矩陣每列只取一個(gè)元素，導(dǎo)致映射系數(shù)矩陣中存在全零的列，映射系數(shù)矩陣達(dá)不到滿秩.

在本文提出的密鑰派生算法中，生成私鑰時(shí)不再是從私鑰矩陣中每列取一個(gè)元素，而是所有的元素均用到，而且在每個(gè)種子前乘上素?cái)?shù)的映射系數(shù)后模加得到.這樣ta(b,c)的取值就不再是0和1，而是完全隨機(jī)的素?cái)?shù).對于第1種線性共謀攻擊，由于經(jīng)過初等變換也無法得到相同的列，映射系數(shù)矩陣的秩達(dá)到滿秩m×h，因此提高了系統(tǒng)的抗攻擊能力.對于第2種線性共謀攻擊，由于映射系數(shù)矩陣中是完全隨機(jī)的素?cái)?shù)，故從中任取小于m×h行，均是線性無關(guān)的.只要共謀私鑰數(shù)量小于m×h，都不可能經(jīng)過線性組合得到其他私鑰.

3.2 選擇共謀攻擊

選擇共謀攻擊的描述是：設(shè)用戶A與用戶B是(j1,j2,…,jt1)層不同，用戶A與用戶C是(s1,s2,…,st2)層不同，且集合{j1,j2,…,jt1}和{s1,s2,…,st2}交集為空，則用戶A、B、C共謀可以得到與A是{j1,j2,…,jt1,s1,s2,…,st2}層不同的用戶私鑰.在本算法中，私鑰是由私鑰矩陣中每一個(gè)私鑰種子與素?cái)?shù)系數(shù)相乘后模加得到的，故不存在層不同與層互斥不同的關(guān)系，因此也不存在選擇共謀攻擊.此外，選擇共謀攻擊的本質(zhì)是私鑰之間存在線性關(guān)系，因此可以通過線性組合得到其他的私鑰.而在本文算法中，由于任意小于矩陣秩的私鑰均是線性無關(guān)的，故不可能通過線性組合得到其他的私鑰.

3.3 隨機(jī)共謀攻擊

隨機(jī)共謀攻擊的描述是：設(shè)兩個(gè)共謀用戶A、B的私鑰分別為skA、skB，公鑰分別為PKA、PKB.然后進(jìn)行如下步驟：① 計(jì)算兩者的私鑰差ΔskAB=skA-skB，ΔskBA=skB-skA；公鑰差ΔPKAB=PKA-PKB，ΔPKBA=PKB-PKA.② 在公鑰矩陣中選取公鑰因子組合出一個(gè)新的公鑰PKC，如果PKC-PKB=ΔPKBA或PKC-PKA=ΔPKAB，則該公鑰對應(yīng)的私鑰skC=2skB-skA或skC=2skA-skB，否則就繼續(xù)執(zhí)行②.

隨機(jī)共謀攻擊的本質(zhì)是公鑰與私鑰之間存在關(guān)系:PK=sk×G.雖然本算法中添加映射系數(shù)后仍然存在這種關(guān)系，但是由于需要簽名的消息事先是未知的，所以無法確定消息的映射系數(shù)，也無法得到消息對應(yīng)的公鑰，因此隨機(jī)共謀攻擊在實(shí)施上是不可行的.

4 實(shí)驗(yàn)方案

4.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)主機(jī)配置為2.40 GHz、i5-2 430 M CPU，8 GB RAM,系統(tǒng)為Ubuntu16.10.整個(gè)實(shí)驗(yàn)選擇在Python語言下實(shí)現(xiàn)，曲線選擇ecdsa庫中提供的標(biāo)準(zhǔn)曲線NIST256p,哈希函數(shù)選取hashlib庫中提供的sha256.私鑰矩陣和公鑰矩陣選取sympy庫中提供的Matrix類構(gòu)建，大小設(shè)為4×4，其中私鑰矩陣中的元素為小于曲線階的隨機(jī)數(shù)私鑰.公鑰矩陣中的元素為對應(yīng)公鑰，以Point類型存儲.映射系數(shù)序列MCS選取前4 096個(gè)素?cái)?shù).

4.2 實(shí)驗(yàn)過程

具體實(shí)驗(yàn)過程如下.

1) 驗(yàn)證映射系數(shù)矩陣是否列滿秩. 構(gòu)建一個(gè)行數(shù)為44=256，列數(shù)為4×4=16的映射系數(shù)矩陣，所有元素從映射系數(shù)序列MCS中隨機(jī)選取.由于行數(shù)太大，截取其中部分映射系數(shù)矩陣，如圖1所示.

使用求秩函數(shù)計(jì)算映射系數(shù)矩陣的秩，結(jié)果是16，證實(shí)了該算法確實(shí)能夠使映射系數(shù)矩陣達(dá)到滿秩，提高系統(tǒng)的安全界限.

2) 驗(yàn)證映射系數(shù)矩陣任意16行是否滿秩. 任意選取映射系數(shù)矩陣中的16行構(gòu)成一個(gè)新的矩陣，再次使用求秩函數(shù)計(jì)算其秩，結(jié)果仍然是16，證實(shí)了該算法確實(shí)能使小于映射系數(shù)矩陣秩的任意數(shù)量私鑰均線性無關(guān)，無法共謀得到其他私鑰，系統(tǒng)的安全界限達(dá)到m×h.

3) 簽名與驗(yàn)簽. 需要驗(yàn)證采用CPK的密鑰派生算法的簽名和驗(yàn)簽是否通過.生成一條消息m=“helloworld”，計(jì)算其sha256哈希值h,根據(jù)哈希在映射系數(shù)序列中取出對應(yīng)位置素?cái)?shù)，與私鑰矩陣中的種子相乘后模加得到消息的簽名私鑰sk.然后調(diào)用簽名函數(shù)用該私鑰對消息m進(jìn)行簽名得到sig.同樣地，根據(jù)消息的哈希在映射系數(shù)序列中取出對應(yīng)位置素?cái)?shù)，與公鑰矩陣中的種子相乘后相加得到消息的驗(yàn)簽公鑰PK.調(diào)用驗(yàn)簽函數(shù)，用公鑰PK驗(yàn)證消息m的簽名sig，結(jié)果驗(yàn)簽通過.

圖1 部分映射系數(shù)矩陣Fig.1 Partial mapping coefficient matrix

4.3 性能比較

由于私鑰矩陣、公鑰矩陣、映射系數(shù)序列是事先生成好的，故不考慮其生成時(shí)間.表1為傳統(tǒng)ECDSA與密鑰派生算法的性能比較.從表中可以看出，采用密鑰派生算法后的簽名時(shí)間接近ECDSA的4倍，驗(yàn)簽時(shí)間接近2倍，性能損耗在可以接受的范圍內(nèi).

表1 ECDSA與密鑰派生算法的性能比較

5 計(jì)算量與存儲量

在計(jì)算量方面，本文算法對于不同的消息采用不同的私鑰簽名.在簽名階段，簽名者需要執(zhí)行1次消息的哈希運(yùn)算，m×h次映射系數(shù)與私鑰種子的數(shù)乘運(yùn)算，m×h-1次Zn域上的模加運(yùn)算.在驗(yàn)簽階段，驗(yàn)簽者需要執(zhí)行1次消息的哈希運(yùn)算，m×h次映射系數(shù)與公鑰種子在橢圓曲線上的點(diǎn)乘運(yùn)算，m×h-1次橢圓曲線上的模加運(yùn)算.由于Hash運(yùn)算速度很快，橢圓曲線上的加法運(yùn)算也很高效，點(diǎn)乘運(yùn)算可以用硬件實(shí)現(xiàn)加速，故整體的計(jì)算開銷不大.

在存儲量方面，相比于普通CPK，存儲開銷僅多了映射系數(shù)序列MCS，私鑰矩陣、公鑰矩陣的存儲都完全一樣，故整體的存儲開銷也不大.

6 結(jié)束語

為了提高單密鑰簽名的安全性，設(shè)計(jì)了一種基于組合公鑰的密鑰派生算法.同時(shí)，針對CPK現(xiàn)有的安全問題，引入映射系數(shù)，改變了私鑰的生成方式，使得映射系數(shù)矩陣達(dá)到滿秩m×h.由此，任意小于映射系數(shù)矩陣秩數(shù)量的私鑰均線性無關(guān)，無法共謀得到其他私鑰，使系統(tǒng)的安全界限提高到m×h.但是本文算法無法解決共謀私鑰數(shù)量大于m×h的情況，如何徹底地解決CPK的共謀攻擊問題，還需要進(jìn)一步的研究.

參考文獻(xiàn)：

[1] 聶文霞, 孫貴芳, 張形形. TD_LTE系統(tǒng)中密鑰派生函數(shù)(KDF)研究[J]. 廣東通信技術(shù),2015，35(4): 40-43.

[2] 唐文, 南相浩, 陳鐘. 基于橢圓曲線密碼系統(tǒng)的組合公鑰技術(shù)[J]. 計(jì)算機(jī)工程與應(yīng)用, 2003，39(21): 1-3.

[3] 南湘浩. CPK五種版本要點(diǎn)[J]. 計(jì)算機(jī)安全, 2010(10): 1.

[4] 南湘浩. CPK組合公鑰體制(v8.0)[J]. 信息安全與通信保密, 2013(3): 39-41.

[5] 南湘浩. CPK組合公鑰體制(v7.0)[J]. 計(jì)算機(jī)安全, 2012(5): 2-4.

[6] 邵春雨, 蘇錦海. 基于組合公鑰的用戶公鑰認(rèn)證算法[J]. 計(jì)算機(jī)工程,2011，37(4): 145-146.

[7] 張鋒, 王明華, 楊欣. 基于CPK的數(shù)字簽名系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J]. 信息通信, 2016(5): 104-106.

[8] 熊榮華, 李增欣, 楊恒亮,等. 組合公鑰(CPK)體制密鑰間的線性關(guān)系[J]. 計(jì)算機(jī)安全, 2012(1): 30-33.

[9] 熊榮華, 李增欣, 楊恒亮,等. 組合公鑰(CPK)體制的安全性分析[J]. 中國信息安全, 2011(12): 75-77.

[10] 趙美玲, 張少武. 基于ECC的組合公鑰技術(shù)的安全性分析[J]. 計(jì)算機(jī)工程, 2008，34(1): 156-157.

[11] 李方偉, 馬安君, 朱江,等. 解決組合公鑰共謀攻擊和密鑰碰撞的新方法[J]. 計(jì)算機(jī)應(yīng)用研究, 2014，31(4): 1176-1179.

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

[13] 邵春雨, 蘇錦海, 魏有國,等. 一種雙矩陣組合公鑰算法 [J]. 電子學(xué)報(bào), 2011, 39(3): 671-674.