閆鴻濱，沈建濤

（南通職業(yè)大學(xué) 電子工程系，南通 226007）

基于圓錐曲線密碼的密鑰恢復(fù)方案研究

閆鴻濱，沈建濤

（南通職業(yè)大學(xué) 電子工程系，南通 226007）

0 引言

隨著網(wǎng)絡(luò)的應(yīng)用與發(fā)展，網(wǎng)絡(luò)安全問題日益突出。數(shù)據(jù)加密是確保計(jì)算機(jī)網(wǎng)絡(luò)安全的一種重要的機(jī)制，其安全性取決于對(duì)密鑰的保護(hù)，加密過的密鑰以文件的形式保存在只有用戶有權(quán)訪問的地方。若用戶忘記口令、誤刪密鑰文件或者存放密鑰的磁盤發(fā)生介質(zhì)損壞等情況時(shí)，用戶可能無法再進(jìn)行正常的信息處理和交換，給用戶帶來了許多不便和損失。互聯(lián)網(wǎng)上許多服務(wù)提供了類似的密鑰(口令)恢復(fù)功能[1]，這些系統(tǒng)一般在用戶發(fā)出口令恢復(fù)請(qǐng)求后，先使用用戶注冊(cè)時(shí)設(shè)置的私密性問題對(duì)用戶進(jìn)行身份驗(yàn)證，再為用戶找回丟失的口令或重新為用戶分配新口令。這類系統(tǒng)存在的突出問題：一是系統(tǒng)完全掌握用戶的口令，用戶的口令對(duì)于系統(tǒng)而言不具任何私密性；二是有的系統(tǒng)將用戶口令經(jīng)過某種單向函數(shù)處理后保存，一旦用戶丟失口令，則只能重新分配口令，無法取得原有口令。

機(jī)遇以上問題，下文設(shè)計(jì)一種基于圓錐曲線公鑰密碼體制的安全性，結(jié)合門限的靈活性的密鑰恢復(fù)方案，克服了傳統(tǒng)密鑰恢復(fù)服務(wù)的缺點(diǎn)。

1 預(yù)備知識(shí)

在介紹新方案之前，先簡單介紹一下圓錐曲線密碼體制[2]。

設(shè)FP，為P元有限域，P為奇素?cái)?shù)，F(xiàn)P*為FP的乘群。不妨設(shè)：

考慮仿射平面A2(FP)上的圓錐曲線：

顯然，x=0時(shí)得原點(diǎn)0(0,0)。若x≠0，令y=xtmodp，將y帶入曲線方程得：

在FP中，若a≠t2，則由式(3)得：

其中，a,b∈FP*，()-1為FP*中元的乘法逆元，對(duì)t∈FP，t2≠a用p(t)表示C(FP)上有式(4)確定的點(diǎn)(x,y)，原點(diǎn)O記為P(∞)，令：

則P:H→C(FP)是一一對(duì)應(yīng)映射。C(FP)中點(diǎn)的⊕運(yùn)算定義為：

1）對(duì)任意p(t)∈C(FP)，其中t∈H，均有

2）設(shè)p(t1)，p(t2)∈C(FP)其中t1，t2∈H，且t1，t2≠∞，定義

易知t3∈H，且運(yùn)算⊕是可交換的

3）對(duì)p(t)∈C(FP)，有負(fù)元

對(duì)于p(t1)，p(t2)，p(t3)∈C(FP)，容易驗(yàn)證：

明文的嵌入：

所謂明文嵌入問題，是指將原始明文m變換為C(FP)中的點(diǎn)p(m)，這里m∈H*，H*=H{∞}，將p(m)稱為明碼，它由明文m編碼而得。

對(duì)于m∈H*，計(jì)算xm=b(a-m2)-1modp，ym=bm(a-m2)-1modp，a,b∈FP*，則有pm=(xm,ym)

譯碼算法：計(jì)算m=ymxm-1modp。由明文的嵌入過程容易證明譯碼算法的正確性。

我們將上述Fp中的運(yùn)算改為Zn中的模N運(yùn)算[4～6]，這里N=pq，p，q是兩個(gè)大素?cái)?shù)。設(shè)?(N)=|C(FP)| |C(FP)|，則?(N)p(t)=p(∞)(modN)這里p(t)=(xt,yt)

其中( )-1表示模N的逆元（這在(a-t2,N)=1時(shí)存在）。任選e使得：

由Euclid算法求出d使得

于是圓錐曲線密碼體制的一種形式為：

公鑰：e，N以及a,b∈ZN，(ab,N)=1

密鑰：d，p，q。

明文：n∈ZN，(n,N)=1

密文：s∈ZN，加密算法為

1）計(jì)算ep(N)=p(s)(modN)，這里

注意，在假設(shè)大整數(shù)N不能分解時(shí)，模N的逆元存在（下同）。

知道密鑰時(shí)的解密算法為：

（1）計(jì)算dp(s)=dep(n)=p(n)(modN)

2 動(dòng)態(tài)密鑰恢復(fù)協(xié)議

本方案用到的系統(tǒng)參數(shù)：N=pq，p，q是兩個(gè)大素?cái)?shù)，Zn為相應(yīng)的有限域，h(x)為Zn上的單向函數(shù)。H={H1,H2,…,Hn}為系統(tǒng)中的n個(gè)密鑰托管者的集合，Г為H上的一個(gè)單調(diào)接入結(jié)構(gòu)，Г0={A1,A2,…,At}是Г的基。密鑰分發(fā)者D首先把H以及A1,A2,…,At依次向所有密鑰共享者公布[3,7]。

密鑰分配：1）分發(fā)者D任意選取n∈ZN，(n,N)=1 ，并計(jì)算ep(n)=p(s)(modN)，由p(s)=(xs,ys)計(jì)算ys=s(modN)，n作為D的主密鑰。

2）分發(fā)者D隨機(jī)地選取n個(gè)互不相同的元素s1,s2,…,sn∈Zn，且si≠1mod(N-1)(i=1,2,…,n)，并將si通過安全信道秘密地發(fā)送給Hi，作為Hi擁有的子密鑰。

3）分發(fā)者D隨機(jī)地選取Zn上的n-1次多項(xiàng)式F(x)=a0+a1x+…+an-1xn-1，使得F(0)=s，且F(x)保密。

4）分發(fā)者D隨機(jī)地選取α∈Zn，并計(jì)算xi=h(α+si)mod N

di=F(Ii)－h(huán)(α+si)mod N

yi=h(xi) mod p；i=1,2,…,n。

其中xi為Hi的屏蔽子密鑰，si為Hi的秘密子密鑰。Ii為Hi的身份表示符號(hào)（公開），然后D公開參數(shù)α以及有序數(shù)組(y1,y2,…,yn)與(d1,d2,…,dn)。

5）分發(fā)者D對(duì)每一個(gè)最小合格子集Ai=｛Hi1,Hi2,…,Hik｝，D由（Ii1,F(Ii1)），（Ii2,F(Ii2)）,…,（Iik，F(xiàn)(Iik)）及（0，s）共k+1個(gè)點(diǎn)用Lagrange插值公式確定出一個(gè)k次多項(xiàng)式：

并計(jì)算出Fi(α)，公開Fi(α)，i=1,2,…,t。

份額的驗(yàn)證算法在恢復(fù)密鑰時(shí)，可以用來檢測提供虛假份額的惡意參與者。

用戶D獲得s后，可以通過dp(s)=deP(n)=P(n))mod N)和P(n)=(xn,yn)，由式xn-1yn=n(mod N)就可以得到丟失的主密鑰。

3 性能分析

1）協(xié)議的安全性是以圓錐曲線密碼體制的安全性和單項(xiàng)函數(shù)的安全性為基礎(chǔ)的。

2）由于在恢復(fù)密鑰時(shí)，每個(gè)托管代理提交的是其屏蔽子密鑰，xi=h(α+si)mod p。根據(jù)單向函數(shù)不可求逆的特性，其他人無法通過xi求出Hi的子密鑰si，即每個(gè)托管代理的子密鑰并沒有因?yàn)橥ㄐ琶荑€的恢復(fù)而被公開，從而可以繼續(xù)使用。

3）同樣，任何人也無法通過公開信息α及有序數(shù)組（y1,y2,…,yn）與（d1,d2,…,dn）來獲取托管代理的屏蔽子密鑰及秘密子密鑰。

另外，當(dāng)某個(gè)成員提供他的屏蔽子密鑰后，可以通過驗(yàn)證等式y(tǒng)i=h(xi) mod p是否成立，來判斷該成員提供的份額是否有效，從而可以檢驗(yàn)惡意參與者。

4 結(jié)束語

文中綜合應(yīng)用單向函數(shù)，圓錐曲線密碼算法，門限原理，提出了一種密鑰恢復(fù)方案，較好地解決了密鑰管理中的密鑰共享和恢復(fù)的難題，該方案不僅適用于對(duì)用戶密鑰、口令進(jìn)行保存以及恢復(fù)，還可用以對(duì)其他私密信息進(jìn)行類似處理，具有一定的通用性。

[1]魏家好,侯整風(fēng).基于(r,n)門限的密鑰恢復(fù)方案[J].計(jì)算機(jī)技術(shù)與發(fā)展,2006,16(10):134-136.

[2]王標(biāo).圓錐曲線及其在公鑰密碼體制中的應(yīng)用[D].成都:四川大學(xué),2006.

[3]閆鴻濱,袁丁,等.一種新的廣義動(dòng)態(tài)密鑰托管方案[J].鐵道學(xué)報(bào),2006,28(5):104-107.

[4]孫琦,張起帆,彭國華.Dickson多項(xiàng)式ge(x,l)/公鑰密碼體制的新算法[J].四川大學(xué)學(xué)報(bào)(自然科學(xué)版),2002,1:18-23.

[5]孫琦,張起帆,彭國華.計(jì)算群元整數(shù)倍的一種算法及其在公鑰密碼體制中的應(yīng)用[A].密碼學(xué)進(jìn)展——ChinaCrypt'2002,第七屆中國密碼學(xué)學(xué)術(shù)會(huì)議論文集[c],電子工業(yè)出版社.

[6]K.Koyama,U.Maurer,T.Okamoto,and S.A.Vanstone,"New Public-Key Schemes Based on Elliptic Curves over the Ring Zn",Advances in Cryptology-CRYPTO'91,Lecture Notes in Computer Science1992(576):252-266.

[7]焦學(xué)磊.基于環(huán)Zn上圓錐曲線的數(shù)字簽名方案[D].成都:成都理工大學(xué),2008.

Research on the key recovery system based on conic curve cryptography

YAN Hong-bin, SHEN Jian-tao

密鑰管理是網(wǎng)絡(luò)安全中的關(guān)鍵問題，從技術(shù)上看，密鑰管理包括密鑰的產(chǎn)生、存儲(chǔ)、分配、使用和銷毀等一系列技術(shù)問題，密鑰共享和恢復(fù)是其中最重要的問題。文中介紹了一種基于圓錐曲線公鑰密碼體系進(jìn)行密鑰恢復(fù)的新方案，該方案應(yīng)用門限技術(shù)來恢復(fù)丟失的密鑰或口令。與傳統(tǒng)密鑰的恢復(fù)方案相比，具有較好的易用性和安全性。

密鑰管理；密鑰共享；密鑰恢復(fù)；協(xié)議

閆鴻濱（1969 -），男，山東濟(jì)寧人，副教授，碩士研究生，研究方向?yàn)樾畔踩?、密碼學(xué)。

TN918

A

1009-0134(2011)5(上)-0065-03

10.3969/j.issn.1009-0134.2011.5(上).23

2010-11-17

國家自然科學(xué)基金項(xiàng)目（60773035）；四川省學(xué)術(shù)和技術(shù)帶頭人資助項(xiàng)目（08226056）；國家教育部留學(xué)回國人員擇優(yōu)項(xiàng)目