才宇飛，姜 偉，劉煥平

(1.哈爾濱師范大學(xué);2.天津市渤海石油第一中學(xué))

0 引言

在保密通信中，秘密共享是信息安全和數(shù)據(jù)保密的重要手段，針對(duì)密鑰管理中密鑰的泄漏問題和遺失問題，Blakley［1］和 Shamir［2］于 1979 年分別獨(dú)立提出了門限秘密共享體制，由于門限秘密共享體制簡(jiǎn)單有效和易于實(shí)現(xiàn)，因此得到了很多學(xué)者的關(guān)注并對(duì)其進(jìn)行了大量的研究.Asmuth和Bloom［3］提出了基于中國剩余定理的秘密共享方案，相對(duì)于Shamir［2］的方案降低了秘密重構(gòu)階段的計(jì)算復(fù)雜性，同時(shí)安全性也降低了.Angsuman Das 和 Avishek Adhikari［4］提出一般接入結(jié)構(gòu)上的秘密共享方案，使其具有更加廣泛的應(yīng)用空間.1989 年，Brickell［5］提出了向量空間秘密共享方案，并且指出Shamir門限方案是向量空間秘密共享方案的特殊情況.2002年，許春香［6］等人提出一個(gè)密鑰空間為有限域的安全矢量空間秘密共享方案，并對(duì)安全性和信息率做了定量分析.

由于現(xiàn)代密碼分析技術(shù)的不斷發(fā)展，攻擊者的計(jì)算能力增強(qiáng)，基于有限域的密碼體制已經(jīng)不能滿足安全性的需要，越來越多的學(xué)者投入到安全性更好的橢圓曲線密碼體制的研究，由于橢圓曲線公鑰密碼體制具有密鑰短，加密強(qiáng)度高，存儲(chǔ)空間小的優(yōu)點(diǎn)，學(xué)者構(gòu)造了許多的橢圓曲線秘密共享方案［7-9］.

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

1.1 向量空間訪問結(jié)構(gòu)及向量空間秘密共享方案

設(shè) P={p1，p2，…，pn}是n個(gè)分享者集合，K=GF(q)是一個(gè)有限域，分發(fā)者D?P，Kr是K上的r維向量空間.Γ是P上的一個(gè)單調(diào)訪問結(jié)構(gòu)，且r不小于所有最小授權(quán)子集的最大基數(shù).稱Γ是一個(gè)向量空間訪問結(jié)構(gòu)，如果存在函數(shù)

φ:P∪D→Kr，滿足性質(zhì)φ(D)=(1，0，…，0)∈〈φ(pi):pi∈B〉?B∈Γ.

向量空間秘密共享方案［10］構(gòu)造如下:首先D向全體參與者公布函數(shù)φ，對(duì)要共享的秘密S∈K，D定義v1=S，并隨機(jī)地選取vi∈K，i=2，3，…，r.K 中的一個(gè)向量 v=(S，v2，…，vr)，使得 S=v·φ(D).其中 φ(D)=(1，0，…，0)，把si=v·φ(pi)的值作為子秘密份額秘密發(fā)送給每個(gè)參與者pi，如果B={p1，p2，…，pl}是一個(gè)授權(quán)子集，則存在K中的一個(gè)向量λ =(λ1，λ2，…，λl)，滿足，其中“·”表示向量的數(shù)量積(內(nèi)積)，則有

從而對(duì)于B中的參與者來說，秘密S由他們所共享的子秘密si的線性組合來恢復(fù).

1.2 模素?cái)?shù)的橢圓曲線

定義1 有限域Zp上的橢圓曲線E(Zp)是定義在仿射平面上的三次方程y2≡(x3+ax+b)modp的所有解(x，y)∈Zp×Zp與無窮遠(yuǎn)點(diǎn)O構(gòu)成的并集，記為

其中:p為素?cái)?shù)，p ＞ 3，a，b∈Zp，且4a3+27b2≠0.

E上的點(diǎn)數(shù)記為#E，它滿足不等式E上的加法運(yùn)算定義如下:假設(shè)P=(x1，y1)，Q=(x2，y2)是 E 上的點(diǎn).如果 x1=x2且y2=-y1，則 P+Q=O;否則 P+Q=(x3，y3)，

其中

且

可以證明，橢圓曲線上的點(diǎn)關(guān)于點(diǎn)的加法構(gòu)成阿貝爾群.

如果P=(x，y)，k是一個(gè)整數(shù)，那么

點(diǎn)P的階是滿足nP=O的最小的正整數(shù)，記為l.

定義2 給定一個(gè)有限域Zp上的橢圓曲線E(Zp)，P∈E(Zp)，點(diǎn)P的階為大素?cái)?shù)l，對(duì)于給定點(diǎn) R ∈〈P〉，計(jì)算整數(shù)n∈［1，l］，滿足 nP=R.稱為橢圓曲線離散對(duì)數(shù)問題(ECDLP).

2 橢圓曲線上的向量空間秘密共享方案

假設(shè) P={p1，p2，…，pn}是n個(gè)參與者的集合，E(Zp)是有限域Zp上的橢圓曲線，G是一個(gè)l(l是一個(gè)大素?cái)?shù))階的E(Zp)上的基點(diǎn)，且〈G〉上的橢圓曲線離散對(duì)數(shù)問題是難解的.所要共享的秘密S∈E(Zp)，Γ是P的一個(gè)向量空間訪問結(jié)構(gòu)，φ:P∪ D→是相應(yīng)的函數(shù)，公開參數(shù)φ(pi)=(ai1，ai2，…，air)，φ(D)={1，0，…，0}.首先每個(gè)參與者pi選取 ai∈［1，l］，計(jì)算βi=aiG，ai作為私鑰，βi公開.其次分發(fā)者D選取a∈［1，l］，計(jì)算 β =aG，a作為私鑰，β 作為公鑰，分發(fā)者要保證 βi≠ βj(i≠ j)，β ≠ βi，i，j=1，2，…n.

2.1 秘密份額的分發(fā)

(1)分發(fā)者D任意選取數(shù)x2，…，xr∈，令v=(S，x2G，…，xrG)∈ (Zp× Zp)r，所共享的秘密 S=v·φ(D).

(2)分發(fā)者計(jì)算 si=v·φ(pi)=ai1S+ai2x2G+ … +airxrG，i=1，2，…，n，si為參與者pi的子秘密共享.

公開 C1，C2i，i=1，2，…，n.

2.2 秘密的恢復(fù)

為了恢復(fù)秘密S，不妨假設(shè)B={p1，p2，…，pl}是授權(quán)子集，則存在Zp上的向量

又因?yàn)镃2i-aiC1=si(見后文可行性分析)，所以授權(quán)子集中的成員用自己的私鑰ai即可求得si，再由B中的所有參與者提供的子秘密si就可恢復(fù)秘密S，

3 方案分析

(1)可行性分析.

令 xiG=(mi，ni)，i=2，…，r則向量

參與者共享的秘密

恢復(fù)秘密時(shí)，設(shè)授權(quán)子集 B={p1，p2，…，pl}∈Γ，則，其中λ =(λ1，λ2，…，λl)，由于所以授權(quán)子集中的成員用自己的私鑰ai即可求得 si，秘密

(2)本方案的安全性是基于橢圓曲線離散對(duì)數(shù)問題難解性及橢圓曲線上的Elgamal密碼體制的安全性.采用橢圓曲線上的Elgamal密碼體制對(duì)子秘密si進(jìn)行加密，提高了安全性能，計(jì)算簡(jiǎn)單.已知C1，試圖從C1=kG中得到整數(shù)k是不可能的，同樣，已知 C2i，試圖從 C2i=si+kβi中得到si是不可能的，因?yàn)閗是未知的.

(3)當(dāng)要保存新的秘密S'時(shí)，只需分發(fā)者D重新選擇xi∈R(Zp)*，i=2，…，r再計(jì)算參與者的子秘密si'，按照以上的步驟進(jìn)行，公開C1'，C2i'.而不需要改變分發(fā)者和參與者的公鑰和私鑰.

4 結(jié)論

基于橢圓曲線提出了一個(gè)更具安全性，實(shí)用性的向量空間秘密共享方案.無需安全信道傳輸，也減少了通信代價(jià).橢圓曲線密碼體制使秘密共享建立在橢圓曲線離散對(duì)數(shù)難題上，提高了安全性能.再接下來的研究中，會(huì)考慮無可信中心的秘密共享方案.

［1］ Blakley G R.Safeguarding Cryptographic Keys［A］.Proc.AFIPS 1979 National Computer Conference，1979:313-317.

［2］ Shamir A.How to Share a Secret［J］.Communications of the ACM，1979，22(11):612-613.

［3］ Asmuth C.，Bloom J.A Modular Approach to Key Safeguarding［J］.IEEE Transactions on Information Theory，1983，29:208-210.

［4］ Das A.，Adhikari A.An Efficient Mult-use Multi-secret Sharing Scheme Based on Hash Function［J］.Applied Mathematics Letters，2010，23:993-996.

［5］ Brickell E F.，Some Ideal Secret Sharing Schemes［J］.Journal of Combinatorial Mathematics and Combinatorial Computing，1989，9:105-113.

［6］ 許春香，陳凱，肖國振.安全的矢量空間秘密共享方案［J］.電子學(xué)報(bào)，2002，30(5):715-718.

［7］ 殷春梅，汪彩梅.一種基于橢圓曲線的多密鑰共享方案［J］.合肥工業(yè)大學(xué)學(xué)報(bào)，2006，29(4):392-394.

［9］ 肖立國，鐘誠，陳國良.基于橢圓曲線密碼體制的動(dòng)態(tài)秘密共享方案［J］.微電子學(xué)與算機(jī)，2002(1):30-31.

［10］Stinson D R.密碼學(xué)原理與實(shí)踐［M］.馮登國等譯，3版.北京:電子工業(yè)出版社，2010.