李濱

（成都師范學(xué)院數(shù)學(xué)系，四川 成都611130）

0 引言

現(xiàn)代密碼體制的設(shè)計(jì)思想是使體制的安全性取決于密鑰，密鑰管理便成為網(wǎng)絡(luò)環(huán)境下信息安全的關(guān)鍵內(nèi)容，密鑰管理者尤其需要對(duì)主密鑰加強(qiáng)管理.但在現(xiàn)實(shí)的使用中卻存在幾種不確定的情況：第一種是出現(xiàn)管理者自己不經(jīng)意泄露主密鑰的情形，第二種是出現(xiàn)主密鑰被他人竊取的情形，第三種是出現(xiàn)管理者丟失了主密鑰的情形，第四種是出現(xiàn)主密鑰被他人惡意毀壞的情形.無(wú)論出現(xiàn)哪種情況都會(huì)導(dǎo)致整個(gè)系統(tǒng)處于不安全的狀態(tài)，系統(tǒng)中的信息要么受到攻擊，要么再也不能使用了.后來(lái)人們采取給可信的用戶發(fā)放密鑰副本的方式來(lái)解決這個(gè)問(wèn)題，但這些用戶又有多大的信用度呢？在出現(xiàn)背叛行為時(shí)系統(tǒng)同樣處于不安全的狀態(tài).目前真正能夠解決這個(gè)問(wèn)題的唯一辦法就是在密鑰管理中引入秘密共享的思想.所謂秘密共享，是指在多個(gè)參與者之間共享主密鑰k的思想，設(shè)參與者集合為P＝｛P1，P2，…，Pn｝，則根據(jù)一定的共享方案可計(jì)算出每個(gè)參與者得到的信息，記作｛k1，k2，…，kn｝，其中ki由參與方Pi秘密保存，稱為一個(gè)子密鑰，只有參與者集合P的某些特定的子集集合Ⅰ才能利用其各自掌握的子密鑰一起重構(gòu)主秘密，這些子集構(gòu)成的集合也被稱為訪問(wèn)結(jié)構(gòu).

秘密共享是密鑰管理的一種核心技術(shù)，和其他密碼技術(shù)一樣，它源自現(xiàn)實(shí)世界，是現(xiàn)實(shí)世界在數(shù)字領(lǐng)域的映像.以銀行為例，銀行的保險(xiǎn)庫(kù)是銀行的核心重地，由誰(shuí)來(lái)單獨(dú)掌管都是不合適的，所以，一般都是交給幾個(gè)人來(lái)共同掌管.例如，有5個(gè)出納，規(guī)定需要3個(gè)出納在一起才能打開(kāi)保險(xiǎn)庫(kù).這一措施有兩個(gè)優(yōu)點(diǎn)：一是杜絕了不足3個(gè)人開(kāi)庫(kù)作案的隱患；二是5個(gè)人一共有10種開(kāi)庫(kù)的方法，防止了一個(gè)人遺忘密鑰或缺席而打不開(kāi)保險(xiǎn)庫(kù)的可能.這一設(shè)想實(shí)現(xiàn)了3個(gè)人共享一個(gè)秘密的思想，密碼學(xué)把這種秘密共享方案稱為（3，5）門(mén)限方案.一般來(lái)說(shuō)，（t，n）門(mén)限方案是一類特殊的秘密共享方案.Shamir［1］和Blakley［2］于1979年先后各自獨(dú)立地提出了門(mén)限方案的思想，并分別采用代數(shù)法和幾何法將其實(shí)現(xiàn).在（t，n）門(mén)限方案中，n表示參與者個(gè)數(shù)，t表示為了重構(gòu)秘密需要的最少子密鑰數(shù)，其訪問(wèn)結(jié)構(gòu)是所有t元素子集構(gòu)成的集合.門(mén)限方案是理想的秘密共享方案.它的基本做法就是將一個(gè)主密鑰k拆成有限個(gè)子密鑰k1，k2，…，kn，這些子密鑰滿足由其中的t（1＜t＜n）個(gè)ki（1≤i≤n）可推出主密鑰的重構(gòu)性要求和少于t個(gè)的ki不能推出k的安全性要求，只有具備重構(gòu)性和安全性的秘密共享才是完備的秘密共享.接下來(lái)掌管主密鑰的莊家將這n個(gè)子密鑰k1，k2，…，kn分發(fā)給n個(gè)參與者，由于重構(gòu)密鑰至少需要t個(gè)子密鑰，所以暴露u（u≤t-1）個(gè)子密鑰不會(huì)危及主密鑰，從而少于t個(gè)參與者的共謀不能得到主密鑰；同時(shí)，如果一個(gè)子密鑰被丟失或毀壞仍可恢復(fù)主密鑰.

（t，n）門(mén)限方案可以利用不同領(lǐng)域的數(shù)學(xué)知識(shí)來(lái)構(gòu)造，目前比較著名的有基于有限域上的拉格朗日插值多項(xiàng)式的Shamir方案和利用有限域上的超平面構(gòu)造的Blakley方案，還有基于Reed Solomon（RS）碼的McEliece方案［3］，基于中國(guó)剩余定理的Asmuth Bloom方案［4］，以及基于有限域上的矩陣運(yùn)算的Karnin-Greene-Hellman方案［5］等.針對(duì)不同的應(yīng)用需求，人們對(duì)上述的各種門(mén)限方案進(jìn)行改進(jìn)，提出了多種門(mén)限方案的變體［6-10］.總之從數(shù)學(xué)的不同領(lǐng)域只要滿足其中一個(gè)目標(biāo)可由某個(gè)集合中的t個(gè)結(jié)果所確定，但任何一個(gè)附加結(jié)果都是多余的情況，都可以用來(lái)構(gòu)造門(mén)限方案.本文中正是通過(guò)冪乘的指數(shù)結(jié)構(gòu)形式，利用大數(shù)分解的困難性和不定方程整數(shù)解的存在性來(lái)構(gòu)造了一個(gè)（t，n）門(mén)限方案.

1 基于大數(shù)分解的（t，n）門(mén)限方案設(shè)計(jì)

在密碼學(xué)中，基于大整數(shù)分解的公開(kāi)密鑰密碼體制的安全性依賴于大整數(shù)分解問(wèn)題，大整數(shù)分解問(wèn)題是一個(gè)數(shù)學(xué)難題，它可以被描述為：給定兩個(gè)大素?cái)?shù)p，q計(jì)算乘積pq＝N很容易；反之，給定整數(shù)N，求N的素因數(shù)p，q使得N＝pq是一個(gè)計(jì)算上困難的問(wèn)題.

對(duì)于一個(gè)多元一次不定方程a1x1＋a2x2＋…＋amxm＝M，其中a1，a2，…，am，M 都是整數(shù)，m≥2，并且a1，a2，…，am都大于零.當(dāng) M 充分大時(shí)，此方程有正整數(shù)解的充要條件是gcd（a1，a2，…，am）｜M.

我們具體來(lái)看一下基于大數(shù)分解的（t，n）門(mén)限方案的實(shí)現(xiàn).設(shè)

基于大數(shù)分解（t，n）門(mén)限方案中的n個(gè)參與者為P1，P2，…Pn.莊家 D?｛P1，P2，…，Pn｝.D 想讓P1，P2，…，Pn分享主密鑰k，D秘密地分配給他們每人一個(gè)關(guān)于主密鑰k的子密鑰.當(dāng)P1，P2，…，Pn中的任意t個(gè)人給出他們的子密鑰后可以重建主密鑰k，而任意t-1個(gè)參與者給出他們的份額后不能重建主密鑰k.

基于大數(shù)分解的（t，n）門(mén)限方案可以描述如下：

1）莊家D 取兩個(gè)大素?cái)?shù)p 和q，計(jì)算N＝pq，φ（N）＝（p-1）（q-1），并將N 公開(kāi)，p，q，φ（N）保密.

2）莊家D選取兩兩互素的大整數(shù)序列e1，e2，…，en對(duì)于主密鑰k＜N，使得kei＞N（其中1≤i≤n），對(duì)1≤i≤n計(jì)算主密鑰冪ri＝keimodN，D將ri秘密地分配給參與者Pi，1≤i≤n.

3）對(duì)1≤i≤n，令集合Ai＝｛dσ（i）｜σ（i）表示下標(biāo)j1j2j3…jt，其中j1＝i，j2j3…jt是1到n中除去i的n-1個(gè)數(shù)中選取t-1個(gè)數(shù)的自然遞增排序｝，顯然，Ai中共有個(gè)元素.

例如：當(dāng)n＝5，t＝3時(shí)

莊家D秘密地隨機(jī)選取正整數(shù)δ，從序列ei（1≤i≤n）中任取t個(gè)數(shù)ei1，ei2，…，eit，組建下列結(jié)構(gòu)方程并計(jì)算dσ（i），

由于gcd（e1，e2，…，en）＝1，因此不定方程（＊）有一個(gè)正整數(shù)特解｛dσ（i1），dσ（i2），…，dσ（it）｝，能構(gòu)成（＊）的方程共有Ctn個(gè)，這樣的正整數(shù)解共有Ctn組，每一個(gè)方程的特解稱為一個(gè)同組組合.可以從所有的同組組合中各自找到Ai的一個(gè)元素.例如：當(dāng)n＝5，t＝3時(shí)，A2中的元素d215可以從同組組合｛d125，d215，d512｝中找到，而這一個(gè)同組組合是不定方程e1d125＋e2d215＋e5d512＝1＋δφ（N）的一個(gè)特解.接下來(lái)莊家D將集合Ai秘密地分配給參與者Pi，1≤i≤n.假設(shè)n個(gè)參與者中的任意t個(gè)成員Pi1，Pi2，…，Pit要計(jì)算主密鑰k，他們分別拿出自己的ri1，ri2，…，rit和Ai1，Ai2，…Ait中對(duì)應(yīng)選出的同組組合｛dσ（i1），dσ（i2），…，dσ（it）｝.

從2）、3）步可以看出子密鑰的構(gòu)成是ki＝｛ri｜Ai的元素｝，其中i＝1，2，…，n.值得注意的是必須要求kei＞N，否則，ri＝keimodN＝kei就是普通的指數(shù)，系統(tǒng)就會(huì)不安全.另一方面，莊家對(duì)兩個(gè)大素?cái)?shù)p和q以及歐拉函數(shù)φ（N）必須保密，否則，攻擊者可以從結(jié)構(gòu)方程（＊）解出一個(gè)正整數(shù)特解｛dσ（i1），dσ（i2），…，dσ（it）｝，從而得出主密鑰.由于N公開(kāi)，想要計(jì)算p和q是非常困難的，因此，該門(mén)限方案的安全性也依賴于大數(shù)分解的困難性.顯然，從主密鑰k的計(jì)算式來(lái)看，該方案需要t個(gè)參與者才能恢復(fù)主密鑰，多于t個(gè)參與者時(shí)，從中任選t個(gè)參與者也能恢復(fù)主密鑰，但低于t個(gè)參與者合謀卻因?yàn)閗的計(jì)算式中缺少足夠的乘積項(xiàng)而不能計(jì)算出主密鑰，甚至得不到主密鑰k的任何信息，所以該門(mén)限方案是無(wú)條件安全的.綜上所述，該門(mén)限方案滿足秘密共享的重構(gòu)性和安全性要求，是一個(gè)完備的秘密共享方案.

下面我們舉例來(lái)看看這個(gè)（t，n）門(mén)限方案的實(shí)現(xiàn)方式.

例：莊家D選定t＝3，n＝5，k＝13，p＝7，q＝11，δ＝2，

計(jì)算N＝77φ（N）＝60，將N 公開(kāi).

計(jì)算r1＝ke1modN＝137mod77＝62，r2＝ke2modN＝135mod77＝76，

r3＝ke3modN＝132mod77＝15，r4＝ke4modN＝1311mod77＝13，r5＝ke5modN＝133mod77＝41.

取d123＝8，d213＝9，d312＝10為一個(gè)同組組合.

取d124＝5，d214＝15，d412＝1為一個(gè)同組組合.

取d125＝9，d215＝5，d512＝11為一個(gè)同組組合.

取d134＝7，d314＝14，d413＝4為一個(gè)同組組合.

取d135＝9，d315＝14，d513＝10為一個(gè)同組組合.

取d145＝2，d415＝7，d514＝10為一個(gè)同組組合.

取d234＝7，d324＝10，d423＝6為一個(gè)同組組合.

取d235＝13，d325＝13，d523＝10為一個(gè)同組組合.

取d245＝8，d425＝3，d524＝16為一個(gè)同組組合.

取d345＝12，d435＝8，d534＝3為一個(gè)同組組合.

從上述同組組合中求出集合Ai，1≤i≤5.

這樣得到5個(gè)子密鑰：

莊家將ki秘密地分配給Pi，1≤i≤5.

假若P3，P4，P53個(gè)參與者在一起只要通過(guò)下面計(jì)算就可以恢復(fù)主密鑰k.

這里需要說(shuō)明的是在該門(mén)限秘密共享方案的實(shí)際應(yīng)用中一般要求大素?cái)?shù)p和q都要是12位以上的數(shù).但上面這個(gè)例子我們只需要呈現(xiàn)本方案是怎樣實(shí)現(xiàn)的，為了便于計(jì)算，把其中的p和q取成了兩個(gè)小素?cái)?shù).

2 結(jié)束語(yǔ)

隨著人們對(duì)信息安全研究的逐漸深入，秘密共享已成為密碼學(xué)中的一個(gè)重要分支，它的理論日臻完善，應(yīng)用范圍也從起初的密鑰管理擴(kuò)展到了數(shù)字簽名、電子選舉、電子拍賣(mài)、糾錯(cuò)碼等諸多方面.利用數(shù)學(xué)領(lǐng)域各研究方向的成熟知識(shí)設(shè)計(jì)新的秘密共享方案是目前國(guó)際密碼界的研究趨勢(shì).對(duì)于一個(gè)大的正整數(shù)N，如何判斷N是否為素?cái)?shù)和如何把N 分解成素?cái)?shù)之積，是一個(gè)計(jì)算上困難的問(wèn)題.人們對(duì)這兩個(gè)問(wèn)題已經(jīng)研究了上千年，而且算法在不斷地改進(jìn)，對(duì)于素?cái)?shù)的判斷問(wèn)題是相對(duì)容易的.但對(duì)于大數(shù)分解問(wèn)題，1988年用400臺(tái)計(jì)算機(jī)聯(lián)網(wǎng)運(yùn)行326天，對(duì)100位十進(jìn)制數(shù)分解成功.最新的記錄已提到129位十進(jìn)制數(shù).至今還不存在對(duì)一個(gè)大整數(shù)分解的一般性的有效解決算法.目前最好的分解算法是數(shù)域篩選法，按照它的漸近時(shí)間估計(jì)值，對(duì)于一個(gè)200位十進(jìn)制數(shù)，即使以每秒107次運(yùn)算的超高速電子計(jì)算機(jī)進(jìn)行因子分解，也要花費(fèi)108年.著名的RSA公鑰密碼體制是1978年由Rivest、Shamir和Adleman提出，并以它的3個(gè)發(fā)明者的名字命名的，它的安全性依賴于大數(shù)的因數(shù)分解的困難性.本文中提出的（t，n）門(mén)限秘密共享方案的安全性，同樣依賴于大因數(shù)分解的困難性，但針對(duì)的內(nèi)容不同，結(jié)構(gòu)不同，作用不同.該方案設(shè)計(jì)的思路和方法是一種創(chuàng)新，結(jié)果顯示該門(mén)限方案是一種安全完備并且易于實(shí)現(xiàn)的秘密共享方案.

致謝 作者衷心感謝審稿人對(duì)本文所提出的十分寶貴的修改意見(jiàn)和給予的幫助.

［1］Shamir A.How to share a secret［J］.Communications of the ACM，1979，22（11）：612-613.

［2］Blakley G R.Safeguarding cryptographic keys［C］／／AFIPS Conference Proceedings.New Jersy：AFIPS Press，1979：313-317.

［3］McEliece R J，Sarwate D V.On sharing secrets and Reed-Solomon codes［J］.Communications of the ACM，1981，24（3）：583-584.

［4］Asmuth C，Bloom J.A modular approach to key safeguarding［J］.IEEE Transactions on Information Theory，1983，29（2）：208-210.

［5］Karnin E D，Green J W，Hellman M E.On sharing secret systems［J］.IEEE Transactions on Information Theory，1983，29（1）：35-41.

［6］Xiao L，Liu M.Threshold schemes with weights［J］.Journal of Systems Science and Complexity，2004，17（4）：578-581.

［7］Li B.Difference secret sharing scheme based on special access right［J］.Journal of Sichuan University（NSE），2006，43（1）：78-83.

［8］Dehkordi M H，Mashhadi S.New efficient and practical verifiable multi-secret sharing schemes［J］.Information Science，2008，9（178）：2262-2274.

［9］Nojoumian M，Stinson D H，Grainger M.Unconditionally secure social secret sharing scheme［J］.IET Information Security，2010，4（2）：202-211.

［10］Nojoumian M，Stinson D R.On dealer-free dynamic threshold schemes［J］.Advances in Mathematics of Communications，2013，7（1）：39-56.