黃科華

泉州兒童發(fā)展職業(yè)學院 福建 362000

0 前言

秘密分享是密碼學的重要方向之一，自從Shamir在1979年提出了秘密共享體制以來，有關(guān)秘密共享體制的研究受到了廣泛關(guān)注。Shamir的基于Lagrange插值法構(gòu)造的秘密分享方案和后來的許多相關(guān)的方案都是一次性的方案，即各參與者的秘密份額只能使用一次，在每次共享過程后，秘密分發(fā)者都要重新分配各參與者的秘密份額。

1 陷門單向函數(shù)

定理1： Tp在 m odp2的乘法運算下構(gòu)成一個群 Tp

定理2定義函數(shù)

則有對于任意的

即對于任意的

證明：

命題得證。

已知y，求(a, β)可以通過以下式子得到：

則

以上為陷門單向函數(shù)的構(gòu)造，由上述可知，設(shè)單向函數(shù)為G，則由已知α, β求y =G(α, β)很容易，但在不知道n分解的前提下求G1?(y)=(α, β)是不可能的，不過知道了n的分解則為容易，即n的分解為陷門。

2 改進的門限秘密共享方案

該方案是對 Shamir(,)tn門限方案的改進。Shamir的方案是一次性的方案，也就是說當密鑰合成之后，下一次如果還需要新的密鑰的話，管理者就必須再通過安全信道重新分配一次份額，而在現(xiàn)實中，安全信道是不容易得到的，而且重新分配份額也需要一定的時間。本方案利用了第一部分所提出的函數(shù)的單向性構(gòu)造了一個秘密分享方案，解決了Shamir方案的一次性問題，而且本方案便于成員的加入和刪除。

設(shè)要分配的密鑰為K，以下為方案的內(nèi)容。

2.1 份額的分配過程

（1）D選擇一個大素數(shù)，以及n個單項函數(shù)Gi(α,β)=,ni=qi,其中ni＜P，i= 1 ,2,… n。D選擇n個份額(si;bi)(保密的參數(shù))， si, bi∈GF(P)。D通過安全信道將單向函數(shù)與份額分別發(fā)給n個用戶 Pi,i = 1 ,2,… n 。

（2）D隨機選擇一個有序?qū)?c,a)(公共的參數(shù))∈GF(P),計算 Gi(csi,a + bi), i = 1 ,2,… n ,并保證當 i≠j, Gi(csi,a+bi)= Gj(c sj,a + bj)。

（3）D通過 n + 1 個有序?qū)?0,K ) ,(i,Gi(csi,a+bi))(i=1,2, · · · ,n)構(gòu)造 n 次多項式 f (x) 。

（4）D公布(c,a)以及 f (n + i),i = 1,2,… n ? t+1。

2.2 密鑰的重構(gòu)過程

t個或者以上用戶聯(lián)合起來就可以恢復多項式 ()fx，從而恢復密鑰K：

（1）每個用戶 Pi下載(c,a)生成 Gi( c si, a + bi)；

（2）需要合成密鑰的 t個用戶提供 Gij(c sij,a + bij),j = 1 ,2… t給合成者；

（3）合成者下載 f (n + i ),i = 1 ,2,… n ? t +1；

（4）合成者通過掌握的 n + 1 個數(shù)值對(ij, Gij(c sij,a + bij))( j = 1,2… ,t ),

(r,f(n + r ) ,(r = 1 ,2… ,n ? t +1)來合成密鑰：

其中用(Xi, Xj)i = 1,2,… n+1來表示所得到的n+1個數(shù)值對。

3 對方案的分析

3.1 可行性

n+1個不同的數(shù)值對(ij, Gij(c sij,a + bij))( j = 1,2… ,t ),(r,f(n + r )),(r = 1 ,2… ,n ? t +1)可恢復n次的多項式 f (x)，而 K = f(0)，可以順利恢復密鑰。

3.2 安全性

（1）由 shamir的(,)tn門限秘密共享方案可知，少于或等于 1t? 個用戶聯(lián)合起來無法恢復多項式 ()fx，得不到密鑰的任何信息。

（2）由于iG 的單向性，公布ix=iG(cis,a +ib)與(c,a)并不能求得用戶的份額(is,ib)，即便K為系統(tǒng)所恢復也無法得到用戶份額的任何信息，因而用戶的份額可以重復使用。

3.3 關(guān)于系統(tǒng)的更新

（1）當密鑰K更新后，管理者只需更新(c,a)(設(shè)為(c′,a′)),計算, a ′+bi)，并生成多項式f(x)(設(shè)為f′(x))，然后D公布(c′,a′)以及f′(n+i),i = 1,2,…n ? t+1，即可按上述方案實行。因而用戶手中的份額可以無限次使用，無需管理者再使用安全信道來發(fā)送份額。

（2）當有成員加入時，D只需為 pn+1用戶隨機生成單向函數(shù)Gn+1和(sn+1,bn+1)，并通過全信道傳輸給新用戶即可。刪除成員時只需更新 f (x)并更新公布 f (n + i ), i = 1,2,… n ? t+1。不需要更改用戶手中的份額。

（3）某成員份額泄露時，管理者只需要重新發(fā)送新份額(s’,b’)，以及更新 f (x) 和更新 f (n + i ),i = 1,2,… n ? t+1即可，而無需更換其他成員的份額。

4 結(jié)束語

本文在文[2]基礎(chǔ)上構(gòu)了一個單向函數(shù)，并結(jié)合文[3]SHAMIR的(t,n)門限設(shè)計了一個秘密分享方案，在這個方案中，每次合成密鑰的時候用戶只是提供了部分的份額，攻擊者和其他的用戶無法通過提供的份額求出用戶的份額，所以在該秘密共享方案中用戶的份額可以無限次使用，而且方案便于成員的加入和刪除，當某成員份額泄露時只需改變他的份額即可，無需修改其他成員的份額。層次的學生學習效率都會大大提高。

[1]ascal aillier.A Tradoor ermutation Equivalent to Factoring[J].LNCS 1560.ublic Key Crytograhy: Second International Worksho on ractice and Theory in ublic Key Crytograhy, KC’99, Kamakura,Jaan, March 1999. roceedings. Sringer-Verlag.1999.

[2]T.Okamoto and S.Uchiyama.A New ublic-Key Crytosystem as secure as Factoring[J].LNCS 1403.Advances in Crytology. roceedings of Eurocryt’98.Sringer-Verlag.1998.

[3]Shamir A. How to share a secret. Comm. ACM 1979.

[4]譚凱軍,諸鴻文.基于單向函數(shù)的動態(tài)秘密分享機制[J].通訊學報.1999.

[5]劉煥平,胡銘曾,方濱興,楊義先.基于單向函數(shù)的動態(tài)密鑰分存方案[J].軟件學報.2002.

[6]He J,Daw son E.M ultistage secret sharing based on one2way function[J]. Electron Lett.1994.

[7]呂繼強,許衛(wèi)東,張鴻燕,王新梅.基于離散對數(shù)的環(huán)簽名方案.第一屆信息與網(wǎng)絡(luò)安全會議論文集[J].2003.

[8]Douglas R.Stinson著,馮登國譯.密碼學原理與實踐[M].電子工業(yè)出版社.2003.

[9]R.L.Rivest,A.Shamir and Y.Tauman,How to leak a secret [J].In Asiacryt.2001.