可驗(yàn)證的Asmuth-Bloom秘密共享方案

于 洋，劉煥平

(哈爾濱師范大學(xué))

0 引言

秘密共享方案是信息安全與數(shù)據(jù)保密的重要手段，在一個(gè)秘密共享方案中，只有授權(quán)的參與者集合才可以恢復(fù)秘密 ，而非授權(quán)集合中的成員則得不到關(guān)于秘密S的任何信息.1979年，Shamir和Blakley分別基于Lagrange插值法和多維點(diǎn)空間的性質(zhì)提出了(t，n)門限秘密共享概念.1983年Asmuth和Bloom基于中國(guó)剩余定理和模數(shù)運(yùn)算提出Asmuth-Bloom門限方案，其構(gòu)造新穎，設(shè)計(jì)簡(jiǎn)明.但是，在實(shí)際應(yīng)用之后，會(huì)帶來三個(gè)問題(1)能否通過公共信道傳輸，使其在應(yīng)用上更具有可行性，減少成本，提高使用價(jià)值(2)能否有效防止分發(fā)者的欺騙行為(3)能否有效檢測(cè)參與者之間的欺騙行為.

該文構(gòu)造了一種可驗(yàn)證的Asmuth-Bloom門限秘密共享方案，該方案中，秘密份額由秘密分發(fā)者和參與者協(xié)同產(chǎn)生，不僅能防止秘密分發(fā)者的欺騙，而且能夠檢測(cè)參與者之間的相互欺詐，并通過公共信道發(fā)送秘密數(shù)據(jù)和秘密份額.

1 Asmuth-Bloom秘密共享方案

1.1 準(zhǔn)備工作

設(shè)秘密分發(fā)者為D，n個(gè)參與者的集合P={P1，P2，…，Pn}門限值為 t，共享秘密為 S，D 選取大素?cái)?shù)p(p＞S)，n個(gè)正整數(shù)序列m=(m1，m2，…，mn)滿足如下條件:

1.2 秘密份額分發(fā)

D 計(jì)算 x=S+Ap，xi=x(mod mi)(i=1，2，…，n)，將(xi，mi)作為秘密份額秘密發(fā)給參與者 Pi(i=1，2，…，n)

1.3 秘密恢復(fù)

t個(gè)參與者交換各自秘密份額后，應(yīng)用中國(guó)剩余定理解得唯一的x，則S=x(modp).

2 可驗(yàn)證的Asmuth-Bloom秘密共享方案

2.1 方案初始化

設(shè)秘密分發(fā)者為D，n個(gè)參與者的集合P={P1，P2，…，Pn}，門限值為 t，共享秘密為 S，D 選取大素?cái)?shù)p(p＞S)，整數(shù)A，n個(gè)正整數(shù)序列m=(m1，m2，…，mn)，p，A，m滿足Asmuth-Bloom 秘密共享方案條件.在有限域Zp上選取一生成元g，使得Zp中計(jì)算以g為底的離散對(duì)數(shù)困難.D任選取一隨機(jī)數(shù)c∈Zp，計(jì)算y=gc(modp)，D以c作為私鑰.參與者Pi(i=1，2，…，n)分別為自己選取一個(gè)整數(shù) si∈ Zp(i=1，2，…，n)，滿足(si，p-1)=1(i=1，2，…，n)，Pi計(jì)算ai=gsi發(fā)給D(i=1，2，…，n)，D 將(p，g，y，m，ai)(i=1，2，…，n)公布在公告板上.

2.2 秘密份額及驗(yàn)證信息的產(chǎn)生

D計(jì)算秘密數(shù)據(jù)X=S+Ap，將X隨機(jī)分解為 n個(gè)不為0的正整數(shù) X1，X2，…，Xn之和，即X=X1+X2+…+Xn.

(1)D計(jì)算bi=Xi*(i=1，2，…，n)將其公布在公告板上，參與者Pi(i=1，2，…，n)在公告板上讀取 bi(i=1，2，…，n).

(2)參與者Pi產(chǎn)生秘密份額，并通過公共信道向 Pj(j≠ i，j=1，2，…，n)發(fā)送秘密數(shù)據(jù)參與者 Pi在公告板上讀取 bi(i=1，2，…，n)，計(jì)算Xi=bi*(ysi)-1(i=1，2，…，n)，再計(jì)算 aij=Xi(mod mj)(j=1，2，…，n)，Pi將 aii保留，然后Pi計(jì)算 bij=aij*發(fā)給 Pj(j≠ i，j=1，2，…，n)，Pj收到 bij計(jì)算 aij=bij*()-1.

(3)防止參與者的欺騙，Pi(i=1，2，…，n)計(jì)算驗(yàn)證信息:

Pi(i=1，2，…，n)將αi、βij通過公共信道傳輸給分發(fā)者D，D在公告板上公開αi，βij.

(4)完成上述過程后，參與者Pi(i=1，2，…，n)的秘密份額為 Si={aji|j=1，2，…，n}.

2.3 秘密份額的驗(yàn)證

恢復(fù)秘密前，t個(gè)參與者集合在一起交換秘密份額，不失一般性，設(shè) t個(gè)參與者為{P1，P2，…，Pt}.為防止參與者之間的欺騙行為，參與者Pk收到參與者Pj的秘密份額Sj后，對(duì)其中n個(gè)分量aij進(jìn)行驗(yàn)證，驗(yàn)證公式如下:

若上式成立，則秘密份額Sj有效;否則Sj無效，即Pj提供了假的秘密份額.

2.4 秘密的恢復(fù)

t個(gè)參與者集合在一起交換并驗(yàn)證各自的秘密份額后，任意參與者Pi(i=1，2，…，n)擁有了t個(gè)秘密份額:

然后建立n個(gè)同余方程組如下:

(2)根據(jù)中國(guó)剩余定理求解這n個(gè)方程組可得唯一的 X1，X2，…，Xn，計(jì)算X=X1+X2+ … +Xn，再由式X=S+Ap即可解得共享秘密S=X(mod p).

3 方案分析

3.1 方案正確性分析

(1)驗(yàn)證式(2-1)的正確性

參與者 Pi(i=1，2，…，n)在把 aij發(fā)送給Pj(j≠i)的同時(shí)，Pi(i=1，2，…，n)通過公共信道將αi、βij傳輸給分發(fā)者D，D在公告板上公開αi、βij，Pj(j≠i)，根據(jù)式(1)可驗(yàn)證aij的真實(shí)性.

故驗(yàn)證式(1)是正確的.

(2)秘密恢復(fù)的正確性.

參與者集合P中前t個(gè)參與者{P1，P2，…，Pt}恢復(fù)秘密時(shí):由于S＜p，故X=S+Ap＜p+Ap=(A+1)p.

當(dāng)參與者集合P中任意t個(gè)參與者恢復(fù)秘密時(shí)，令N'表示m中任意t個(gè)數(shù)的乘積，可知:N ＜N'，所以Xi＜X ＜N ＜N'.

P中任意t個(gè)參與者交換各自的秘密份額后，建立形如式(2)的n個(gè)同余方程組，根據(jù)中國(guó)剩余定理也可解得唯一的Xi(i=1，2，…，n)，因此任意t個(gè)參與者能恢復(fù)共享秘密S.

3.2 方案安全性分析

(1)防止秘密分發(fā)者D的欺騙

該方案的秘密份額是由秘密分發(fā)者D和參與者集合 P={P1，P2，…，Pn}協(xié)同產(chǎn)生，能夠有效防止D的欺騙.

D將包含共享秘密S的秘密數(shù)據(jù)X分解為X=X1+X2+… +Xk+… +Xn，然后D計(jì)算將其公布在公告板上，參與者 Pi(i=1，2，…，n)在公告板上讀取bi(i=1，2，…，n).假設(shè)D偽造的秘密數(shù)據(jù)，然后計(jì)算=，將公布在公告板上.那么Pk在秘密份額的產(chǎn)生過程中首先在公告板讀取，然后計(jì)算:

(j=1，2，…，n)，Pk計(jì)算 bkj=akj*發(fā)送給Pj(j≠k)，Pj收到bkj計(jì)算akj=bkj*()-1.t個(gè)參與者{P1，P2，…，Pt}集合在一起交換各自的秘密份額后，建立形如式(2)的n個(gè)方程組，其中關(guān)于Xk的方程組變?yōu)?

由于該方程組無法計(jì)算出Xk，因此無法計(jì)算出X和共享秘密S，所以任何參與者無法恢復(fù)出S.由以上分析可知，若D向任意一個(gè)參與者發(fā)送假的秘密數(shù)據(jù)，則導(dǎo)致其他所有參與者無法恢復(fù)共享秘密，因此，D的欺騙行為沒有任何意義，從而保證了本方案的公正性.

(2)識(shí)別參與者之間的相互欺騙

任意t個(gè)參與者在恢復(fù)秘密之前集合在一起交換各自的秘密份額.參與者Pk收到其他參與者Pj的秘密份額Sj后，通過式(1)驗(yàn)證Sj中n個(gè)分量的正確性，若Pj提供假的秘密份額，將被檢測(cè)出來.因此，本方案能夠識(shí)別參與者之間的欺騙行為.

(3)驗(yàn)證過程是安全的

首先本方案在由分發(fā)者D公布秘密數(shù)據(jù)時(shí)，Pi發(fā)送ai給D，根據(jù)ai求得si屬于離散對(duì)數(shù)求解困難問題，因此ai是安全的.D將bi公布在公告板上，根據(jù)bi求得Xi屬于離散對(duì)數(shù)求解困難問題，因此bi是安全的.故秘密數(shù)據(jù) Xi(i=1，2，…，n)是安全的.其次本方案在參與者之間互相交換時(shí)，同理，發(fā)送秘密份額也是安全的.最后在驗(yàn)證參與者交換的秘密份額是否正確時(shí)，每個(gè)參與者Pi發(fā)送給D驗(yàn)證信息αi=gXi(mod p)和βij=gkij(modp)，根據(jù)αi求得Xi屬于離散對(duì)數(shù)求解困難問題，因此αi是安全的，同理，kij也是安全的.所以驗(yàn)證過程式安全的.

(4)若再次分發(fā)秘密S'，分發(fā)者的私鑰c以及每個(gè)參與者Pi的秘密數(shù)據(jù)si(i=1，2，…，n)皆可重復(fù)使用，提高了秘密共享的實(shí)用性及價(jià)值.

4 結(jié)束語

基于中國(guó)剩余定理，結(jié)合模運(yùn)算性質(zhì)提出了一種可驗(yàn)證的門限秘密共享方案，該方案能夠不僅可以通過公共信道傳輸秘密數(shù)據(jù)和秘密份額，并且還有效地防止秘密分發(fā)者的欺騙并識(shí)別參與者之間的欺詐行為，其驗(yàn)證過程的安全性基于離散對(duì)數(shù)的難解性.本方案中，秘密分發(fā)者D的欺騙行為將導(dǎo)致任何參與者均無法恢復(fù)秘密，因此，D的欺騙行為沒有任何意義.在恢復(fù)秘密時(shí)，t個(gè)參與者集合在一起交換各自的秘密份額后，能夠通過驗(yàn)證式(1)識(shí)別任一參與者的欺詐行為.方案利用模運(yùn)算的相關(guān)性質(zhì)驗(yàn)證秘密份額的有效性，驗(yàn)證過程簡(jiǎn)單、高效，并且再次分發(fā)秘密時(shí)，參與者與分發(fā)者的私鑰也可重復(fù)使用，更加提高了該秘密共享方案的實(shí)用價(jià)值.

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

［2］ Blakley G R.Safeguarding cryptographic key［A］.Proceedings of AFIPS，1979 National Computer Conference［C］.New York:AFIPS，1979，48:313-317.

［3］ Asmuth C A ，Bloom J.A modular approach to key safeguarding［J］.IEEE Transactions on Information Theory IT-29，1983，208–210.

［4］ Ore O.The general Chinese remainder theorem［J］.American Mathematical Monthly，1952:9:365–370.

［5］ 唐春明，劉卓軍，王明生.一種實(shí)用的可驗(yàn)證秘密共享方案.計(jì)算機(jī)工程與應(yīng)用2006，15:129-133.

［6］ 龐遼軍，李慧賢，王育民.可驗(yàn)證的(t，n)門限秘密共享方案及其安全性.華南理工大學(xué)學(xué)報(bào):自然科學(xué)版，2007，35(1):102-105.

［7］ Mignotte M.How to share a secret?［J］In:Proc.of the Workshop on Cryptography，Springer.Heidelberg，1983:371–375.