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

閆鴻濱，沈建濤

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

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

閆鴻濱，沈建濤

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

0 引言

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

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

1 預備知識

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

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

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

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

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

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

則P:H→C(FP)是一一對應映射。C(FP)中點的⊕運算定義為：

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

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

易知t3∈H，且運算⊕是可交換的

3）對p(t)∈C(FP)，有負元

對于p(t1)，p(t2)，p(t3)∈C(FP)，容易驗證：

明文的嵌入：

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

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

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

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

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

由Euclid算法求出d使得

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

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

密鑰：d，p，q。

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

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

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

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

知道密鑰時的解密算法為：

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

2 動態(tài)密鑰恢復協(xié)議

本方案用到的系統(tǒng)參數(shù)：N=pq，p，q是兩個大素數(shù)，Zn為相應的有限域，h(x)為Zn上的單向函數(shù)。H={H1,H2,…,Hn}為系統(tǒng)中的n個密鑰托管者的集合，Г為H上的一個單調(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 ，并計算ep(n)=p(s)(modN)，由p(s)=(xs,ys)計算ys=s(modN)，n作為D的主密鑰。

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

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

4）分發(fā)者D隨機地選取α∈Zn，并計算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的身份表示符號（公開），然后D公開參數(shù)α以及有序數(shù)組(y1,y2,…,yn)與(d1,d2,…,dn)。

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

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

份額的驗證算法在恢復密鑰時，可以用來檢測提供虛假份額的惡意參與者。

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

3 性能分析

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

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

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

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

4 結(jié)束語

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

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

[2]王標.圓錐曲線及其在公鑰密碼體制中的應用[D].成都:四川大學,2006.

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

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

[5]孫琦,張起帆,彭國華.計算群元整數(shù)倍的一種算法及其在公鑰密碼體制中的應用[A].密碼學進展——ChinaCrypt'2002,第七屆中國密碼學學術會議論文集[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]焦學磊.基于環(huán)Zn上圓錐曲線的數(shù)字簽名方案[D].成都:成都理工大學,2008.

Research on the key recovery system based on conic curve cryptography

YAN Hong-bin, SHEN Jian-tao

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

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

閆鴻濱（1969 -），男，山東濟寧人，副教授，碩士研究生，研究方向為信息安全、密碼學。

TN918

A

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

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

2010-11-17

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