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

閆鴻濱，沈建濤

（南通職業大學 電子工程系，南通 226007）

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

閆鴻濱，沈建濤

（南通職業大學 電子工程系，南通 226007）

0 引言

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

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

1 預備知識

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

設FP，為P元有限域，P為奇素數，FP*為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是兩個大素數。設?(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)，這里

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

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

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

2 動態密鑰恢復協議

本方案用到的系統參數：N=pq，p，q是兩個大素數，Zn為相應的有限域，h(x)為Zn上的單向函數。H={H1,H2,…,Hn}為系統中的n個密鑰托管者的集合，Г為H上的一個單調接入結構，Г0={A1,A2,…,At}是Г的基。密鑰分發者D首先把H以及A1,A2,…,At依次向所有密鑰共享者公布[3,7]。

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

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

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

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

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

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

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

5）分發者D對每一個最小合格子集Ai=｛Hi1,Hi2,…,Hik｝，D由（Ii1,F(Ii1)），（Ii2,F(Ii2)）,…,（Iik，F(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）協議的安全性是以圓錐曲線密碼體制的安全性和單項函數的安全性為基礎的。

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

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

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

4 結束語

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

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

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

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

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

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

[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]焦學磊.基于環Zn上圓錐曲線的數字簽名方案[D].成都:成都理工大學,2008.

Research on the key recovery system based on conic curve cryptography

YAN Hong-bin, SHEN Jian-tao

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

密鑰管理；密鑰共享；密鑰恢復；協議

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

TN918

A

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

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

2010-11-17

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