基于大數(shù)分解的門限秘密共享方案

李濱

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

0 引言

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

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

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

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

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

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

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

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

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

1）莊家D 取兩個大素數(shù)p 和q，計算N＝pq，φ（N）＝（p-1）（q-1），并將N 公開，p，q，φ（N）保密.

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

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

例如：當n＝5，t＝3時

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

由于gcd（e1，e2，…，en）＝1，因此不定方程（＊）有一個正整數(shù)特解｛dσ（i1），dσ（i2），…，dσ（it）｝，能構(gòu)成（＊）的方程共有Ctn個，這樣的正整數(shù)解共有Ctn組，每一個方程的特解稱為一個同組組合.可以從所有的同組組合中各自找到Ai的一個元素.例如：當n＝5，t＝3時，A2中的元素d215可以從同組組合｛d125，d215，d512｝中找到，而這一個同組組合是不定方程e1d125＋e2d215＋e5d512＝1＋δφ（N）的一個特解.接下來莊家D將集合Ai秘密地分配給參與者Pi，1≤i≤n.假設(shè)n個參與者中的任意t個成員Pi1，Pi2，…，Pit要計算主密鑰k，他們分別拿出自己的ri1，ri2，…，rit和Ai1，Ai2，…Ait中對應(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)就會不安全.另一方面，莊家對兩個大素數(shù)p和q以及歐拉函數(shù)φ（N）必須保密，否則，攻擊者可以從結(jié)構(gòu)方程（＊）解出一個正整數(shù)特解｛dσ（i1），dσ（i2），…，dσ（it）｝，從而得出主密鑰.由于N公開，想要計算p和q是非常困難的，因此，該門限方案的安全性也依賴于大數(shù)分解的困難性.顯然，從主密鑰k的計算式來看，該方案需要t個參與者才能恢復(fù)主密鑰，多于t個參與者時，從中任選t個參與者也能恢復(fù)主密鑰，但低于t個參與者合謀卻因為k的計算式中缺少足夠的乘積項而不能計算出主密鑰，甚至得不到主密鑰k的任何信息，所以該門限方案是無條件安全的.綜上所述，該門限方案滿足秘密共享的重構(gòu)性和安全性要求，是一個完備的秘密共享方案.

下面我們舉例來看看這個（t，n）門限方案的實現(xiàn)方式.

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

計算N＝77φ（N）＝60，將N 公開.

計算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為一個同組組合.

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

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

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

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

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

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

取d235＝13，d325＝13，d523＝10為一個同組組合.

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

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

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

這樣得到5個子密鑰：

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

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

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

2 結(jié)束語

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