基于二元多項(xiàng)式與中國(guó)剩余定理的多秘密分享方案

黃科華

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

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

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

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

1.1 陷門單向函數(shù)

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

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

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

1.2 中國(guó)剩余定理

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

2 基于二元多項(xiàng)式與中國(guó)剩余定理的多秘密分享方案

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

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

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

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

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

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

2.2 秘鑰的合成過(guò)程

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

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

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

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

即

t+1 個(gè)用戶可以拿出 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ù)矩陣為范德蒙矩陣，能夠解出唯一解:

因?yàn)槟軌蚝铣烧麄€(gè)二元多項(xiàng)式，取得S.

取得S后，每個(gè)用戶可以再?gòu)墓嫉膍1，m2，…mn中解出所有的秘鑰 s1，si，…sn.

3 分析

3.1 滿足門限性

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

3.2 多秘密分享

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

［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ù)與二元多項(xiàng)式的秘密分享方案［J］魯東大學(xué)學(xué)報(bào)(自然科學(xué)版)，2014，(3):223－227.