基于二元多項式與中國剩余定理的多秘密分享方案

黃科華

(泉州幼兒師范高等專科學(xué)校初等教育系，福建泉州362000)

秘密分享方案的主要目的是用來解決在特定用戶(準(zhǔn)入結(jié)構(gòu))中分享一個秘密.一個秘密分享方案(SSS)主要包含以下幾個方面:秘鑰分發(fā)者D，參與用戶集合P，準(zhǔn)入結(jié)構(gòu)Γ，秘鑰空間S，分配算法和恢復(fù)算法.

Shamir［1］和 Blakley［2］與1979年分別獨立提出了(t，n)門限秘密分享方案，通過該方案，n用戶中只要有t個及以上的人合作就能合成秘鑰，而少于t個用戶就得不到秘鑰的任何信息.當(dāng)然，兩個方案都存在許多不足的地方，如1)秘密份額是一次性的，不能重復(fù)利用;2)秘鑰分發(fā)者的權(quán)利過大，有可能導(dǎo)致秘鑰分發(fā)者的欺騙，比如發(fā)送無效的份額;3)每次只能共享一個秘鑰，秘鑰的信息不夠大等.在兩個方案的基礎(chǔ)上，Asmuth和Bloom［3］在1983年提出的基于中國剩余定理的門限方案;Brlckell［4］等人在1991年提出了理想化的秘密共享方案;黃科華［5］結(jié)合單向函數(shù)和二元多項式的方案解決了秘鑰的一次性使用的問題，本文正是在此基礎(chǔ)上，利用中國剩余定理，提供了一個多秘密的分享方案，而且在這個方案中，引入可驗證的秘鑰機制，來避免秘鑰欺騙.

1 預(yù)備知識

1.1 陷門單向函數(shù)

陷門單項函數(shù)h(x)滿足以下兩個條件，(i)給定x，能夠容易地計算y=h(x);

(ii)給定y，計算x=h－1(y)是困難的，但是如果知道陷門，可以容易地計算出y.

陷門單向函數(shù)可以選擇離散對數(shù)函數(shù)或者RSA函數(shù)等.

1.2 中國剩余定理

設(shè)整數(shù) m1，m2，…mn兩兩互質(zhì)，對于任意整數(shù) s1，s2，…sn，方程組:

2 基于二元多項式與中國剩余定理的多秘密分享方案

2.1 秘鑰生成和分發(fā)階段

設(shè)有n個用戶為P1，P2，…Pn.每個Pj自己選取一個向量作為自己的私鑰(且yij≠ymn，i≠m 或者 j≠ n)，并計算 h(yij)，i=0，1，2，…t，j=1，2，…n.其中h(x)為無碰撞陷門單向函數(shù)，由秘鑰分發(fā)者D選取并公布，陷門信息由D掌握.

設(shè)s1，si，…sn是需要分享的多個秘鑰，秘鑰分發(fā)者D選擇n個互質(zhì)的整數(shù) m1，m2，…mn，通過中國剩余定理得到modM的唯一解S.

D構(gòu)造一個二元多項式f(x，y)，表達(dá)式如下:

并使得a00=S(常數(shù)項為秘鑰S)

D 計算 f(xi，yij)，i=0，1，2，…，t，j=1，2，3，…，n.并公布.

2.2 秘鑰的合成過程

不妨設(shè) f(xi，yij)=Aij，i=0，1，2，…，t，j=1，2，3，…，n

三個月前，他們瞞著所有的人，寫了一份分手協(xié)議，分配了財產(chǎn)。但他們彼此各退一步，商定等孩子三年后上了大學(xué)，再公布于眾。按照協(xié)議規(guī)定，他們互不打探干涉對方的私生活，仍在一個屋檐下或者另租居所，不過，每月孩子回來的那天必須琴瑟和鳴夫唱婦隨。

t+1個用戶合作可以通過以下方式恢復(fù)二元多項式，取得S.

從公告牌中的 xi，(i=0，1，2，…，t)可以得出下列方程組:

即

t+1 個用戶可以拿出 yij0，yij1，…，yijt，

其中 0 ≤ j0，j1，…，jt(均為正整數(shù))≤ n，i=0，1，2，…，t

代入(2)式可得:

(3)可以寫成方程組:

也即是以下的矩陣:

由(2)式可得下列方程組:

其中 j=0，1，2，…，t.

寫成矩陣即為:

由于xi≠xj，i≠j，所以系數(shù)矩陣為范德蒙矩陣，能夠解出唯一解:

因為能夠合成整個二元多項式，取得S.

取得S后，每個用戶可以再從公布的m1，m2，…mn中解出所有的秘鑰 s1，si，…sn.

3 分析

3.1 滿足門限性

從方案中可以看出，該方案為(t+1，n)門限方案，t+1個人合作可以順利恢復(fù)秘鑰，而少于t+1，就無法從方程組4(或者矩陣 5)中恢復(fù)出(Bi0，Bi1，…，Bit)，i=0，1，2，…，t，因而，也無法從方程組6(或者矩陣7)中恢復(fù)出系數(shù)(a0j，a1j，…，atj)，j=0，1，2，…，t，故不能得到密鑰 S.

3.2 多秘密分享

利用中國剩余定理，把多個秘密封裝成S進(jìn)行分發(fā)，合成用戶可以通過公布的m1，m2，…mn取得多個秘鑰.

3.3 不需要安全信道和秘鑰可以多次使用

由于使用了陷門單向函數(shù)，所有的交流都可以在公用信道上達(dá)成，整個秘密共享的過程不需要任何的安全信道.而且，公布在外面的只是h(yij)，用戶的份額沒有泄露，所以份額可以多次使用.

3.4 防止分發(fā)者的欺騙

由于秘密份額是用戶自己選擇并發(fā)布的，所以任何用戶都可以通過公布的h(x)驗證分發(fā)者提供的份額是不是正確的.這限制了分發(fā)者的權(quán)利.

3.5 方便系統(tǒng)更新

當(dāng)完成一次秘密分享以后，秘鑰分發(fā)者D只需要更新陷門單線函數(shù)h(x)即可.

4 結(jié)語

本文是文［5］的進(jìn)一步改進(jìn)，除了繼承文［5］的優(yōu)點之外，該系統(tǒng)不需要安全信道，并且防止了秘鑰分發(fā)者D的欺騙，是可驗證的秘密分享方案.

［1］Shamir A.How to share a secret［J］.Communications of the ACM，1979，(11):612－613.

［2］Blakley G R.Safeguarding cryptographic keys［A］.Managing Requirements Knowledge，International Workshop on［C］.IEEE Computer Society，1899.

［3］Asmuth C，Bloom J.A modular approach to key safeguarding［J］.IEEE Transactions on Information Theory，1983，(2):208－210.

［4］Brickell E F，Davenport D M.On the classification of ideal secret sharing schemes［J］.Journal of Cryptology，1991，(2):123－134.

［5］黃科華，熱娜·艾合買提，張瑛瑛.基于單向函數(shù)與二元多項式的秘密分享方案［J］魯東大學(xué)學(xué)報(自然科學(xué)版)，2014，(3):223－227.