（計(jì)算機(jī)軟件與理論專業(yè)論文）先應(yīng)秘密共享方案的研究與實(shí)現(xiàn).pdf

先應(yīng)秘密共享方案的研究與實(shí)現(xiàn) 摘要 隨著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的迅速發(fā)展和普及，信息成為社會(huì)發(fā)展的重要戰(zhàn)略資源，信 息安全問題己成為世人關(guān)注的社會(huì)問題。門限秘密共享是實(shí)現(xiàn)信息安全和數(shù)據(jù)保密的 重要手段，先應(yīng)秘密共享在不改變共享秘密的情況下，通過周期性更新秘密份額來保 證門限秘密共享系統(tǒng)的安全性和魯棒性。 本文闡述了密碼學(xué)的相關(guān)知識，介紹了門限秘密共享的基本原理，重點(diǎn)分析了可 驗(yàn)證秘密共享方案、無可信中心方案、先應(yīng)秘密共享等幾種典型方案。針對這些方 案中存在的問題和不足，提出了一種新的先應(yīng)秘密共享方案。該方案具有以下特點(diǎn)： 1 采用無可信中心的秘密共享形式，避免了可信中心的權(quán)威欺騙。同時(shí)能 夠驗(yàn)證成員的秘密份額，發(fā)現(xiàn)攻擊者和不誠實(shí)的成員，提高了系統(tǒng)的安全性； 2 為了防止移動(dòng)攻擊造成的秘密份額的泄漏或損壞，方案定期更新所有成員的 秘密份額，使得攻擊者在前一個(gè)周期獲得的秘密份額完全失效，提高了系統(tǒng)的 魯棒性； 3 通過部分更新秘密份額刪除被腐蝕的成員和增加新的成員，提高了系統(tǒng) 的可用性。 最后在w i n d o w s x p 系統(tǒng)下，利用v c + + 6 0 實(shí)現(xiàn)了該方案的原型系統(tǒng)。實(shí)驗(yàn)結(jié)果表 明：該方案是正確和可行的，且具有良好的安全性和魯棒性。 關(guān)鍵詞：l a g r a n g e 插值；秘密共享；先應(yīng)秘密共享 t h er e s e a r c ha n dr e a l i z a t i o no fp r o a c t i v es e c r e t s h a r i n g a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fc o m p u t e rn e t w o r k s ，t h ei n f o r m a t i o nh a sb e c o m ea l l i m p o r t a n ts t r a t e g yr e s o u r c eo fs o c i a ld e v e l o p m e n t ，a n di n f o r m a t i o ns e c u r i t yh a sb e c o m ea s o c i a lp r o b l e mt h a tt h ew o r l dp a y st h ea t t e n t i o nt o t h r e s h o l ds e c r e ts h a r i n gi so n eo ft h e i m p o r t a n tw a yt os a v es e c u r e l yi m p o r t a n ti n f o r m a t i o na n dd a t a ，p r o a c t i v es e c r e ts h a r i n g r e n e w se v e r ys h a r ep e r i o d i c a l l yw i t h o u tc h a n g i n gt h es e c r e t t h i sd i s s e r t a t i o np r e s e n t ss o m ek n o w l e d g et h a tr e f e r st ot h ec r y p t o g r a p h y t h e ni t i n t r o d u c e st h em a i ni d e ao ft h r e s h o l ds e c r e ts h a r i n g ，a n dd e t a i l e d l ya n a l y s e sv e r i f i a b l e s e c r e ts h a r i n gs h c e m e ，s e c r e ts h a r i n gw i t h o u tt h et r u s ta n dp r o a c t i v es e c r e ts h a r i n g t od e a l w i t ht h ep r o b l e m sa n dd e f i c i e n c yo ft h e s es c h e m e s ，w ep r o p o s ean e ws c h e m eo f p r o a c t i v es e c r e ts h a r i n gw h i c hh a st h ef o l l o w i n gf e a t u r e s ： 1 t h es c h e m eh a sn o tt h et r u s t e dc e n t e rw h i c hc a np r e v e n tt h ea u t h o r i t yc h e a t a tt h e s a m et i m e ，t h es c h e m ec a nv 耐母e v e r ys h a r e h o l d e r ss h a r ea n df i n dt h ea t t a c k e r sa n d m i s b e h a v i n gs h a r e h o l d e r s s ot h es c h e m ei m p r o v e ss y s t e m ss e c u r i t y 2 i no r d e rt op r e v e n tt h em o b i l ea d v e r s a r yf r o ml e a r n i n go rd e s t r o y i n gt h es h a r e s ，t h e s c h e m er e n e w st h e mp e r i o d i c a l l y , a n di ns u c haw a yt h a ta n yi n f o r m a t i o nl e a r n e db yt h e a d v e r s a r ya b o u ti n d i v i d u a l s h a r e sb e c o m e so b s o l e t e h e n c et h es c h e m ee n h a n c e s s y s t e m sr o b u s t n e s s 3 s o m eo ft h es h a r e sm u s tb er e n e w e ds oa st od e l e t et h ec o r r u p t e ds h a r e h o l d e ra n d a d dan e ws h a r e h o l d e r , t h e r e f o r et h es c h e m er a i s e ss y s t e m su s a b i l i t y a tl a s t ，w eu s ev c + + 6 0a n ds q ls e r v e r 2 0 0 0t od e s i g nap r o t o t y p es y s t e mi n w i n d o w sx p t h er e s u l ts h o w st h a tt h i ss c h e m ew h i c hh a sg o o ds e c u r i t ya n d r o b u s t n e s s ，i sr i g h ta n df e a s i b l e k e y w o r d s ：l a g r a n g ei n t e r p o l a t i o n ；s e c r e ts h a r i n g ；p r o a c t i v es e c r e ts h a r i n g 插圖目錄 系統(tǒng)模型3 3 原型系統(tǒng)的運(yùn)行流程圖一3 3 新成員獲取秘密份額的過程3 4 獲取的公共參數(shù)3 5 產(chǎn)生秘密份額的過程3 6 恢復(fù)的共享秘密3 8 定期更新秘密份額的過程3 9 添加成員的過程一4 0 刪除成員的過程4 2 恢復(fù)的共享秘密4 4 1 2 3 4 5 6 7 8 9 1 5 5 5 5 5 5 5 5 5 5 圖圖圖圖圖圖圖圖圖圖 獨(dú)創(chuàng)性聲明 本人聲明所呈交的學(xué)位論文是本人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研究成果。據(jù) 我所知，除了文中特別加以標(biāo)注和致謝的地方外，論文中不包含其他人已經(jīng)發(fā)表或撰寫過的 研究成果，也不包含為獲得 金目墾王些太堂 或其他教育機(jī)構(gòu)的學(xué)位或證書而使用過的 材料。與我一同工作的同志對本研究所做的任何貢獻(xiàn)均已在論文中作了明確的說明并表示謝 意。 學(xué)位論文作者簽名： 履履梅簽字日期：d 窘年石月，弓日 學(xué)位論文版權(quán)使用授權(quán)書 本學(xué)位論文作者完全了解金理王些盔堂有關(guān)保留、使用學(xué)位論文的規(guī)定，有權(quán)保留并 向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和磁盤，允許論文被查閱和借閱。本人授權(quán)金膽 王些盔堂可以將學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮 印或掃描等復(fù)制手段保存、匯編學(xué)位論文。 ( 保密的學(xué)位論文在解密后適用本授權(quán)書) 學(xué)位論文作者簽名： 再尖f 虱爿辱 導(dǎo)師簽名： 彳膨億 簽字日期：d 8 年6 月妒 簽字日期：蘇石月f 卻 學(xué)位論文作者畢業(yè)后去向： 工作單位： 通訊地址： 電話： 郵編： 致謝 本人在碩士研究生學(xué)習(xí)和撰寫學(xué)位論文期間，自始至終得到了我的導(dǎo)師侯整風(fēng)教 授的悉心指導(dǎo)，無論從課程學(xué)習(xí)，論文選題，還是收集資料，論文成稿，都傾注了侯 老師的心血，由衷地感謝侯老師在學(xué)業(yè)指導(dǎo)及其他各方面所給予的關(guān)心。侯老師兢兢 業(yè)業(yè)的敬業(yè)精神、一絲不茍的治學(xué)態(tài)度和誨人不倦的高尚師德給我留下了深刻的印 象，讓我受益匪淺，所有這一切必將在我今后的工作、學(xué)習(xí)和生活中激勵(lì)我繼續(xù)努力， 鞭策我不斷上進(jìn)。 同時(shí)，在此感謝計(jì)算機(jī)學(xué)院的各位老師，他們的教誨為本文的研究提供了理論基 礎(chǔ)；感謝實(shí)驗(yàn)室的其他同學(xué)，在本課題的研究和撰寫中，他們在許多問題上都給我提 出了寶貴的意見，感謝他們對我的無私幫助。 感謝所有愛我、關(guān)心和幫助過我的人。 作者：殷鳳梅 2 0 0 8 年3 月 第一章緒論 隨著計(jì)算機(jī)網(wǎng)絡(luò)及通信技術(shù)的迅猛發(fā)展，人類進(jìn)入了信息社會(huì)，利用互聯(lián) 網(wǎng)獲取和交換信息己成為當(dāng)今信息社會(huì)的一個(gè)重要特征。在信息社會(huì)的發(fā)展過 程中，人類必須面對和解決幾個(gè)關(guān)鍵問題：( 1 ) 如何進(jìn)行保密的通信；( 2 ) 如何 保證信息不被非法修改；( 3 ) 如何保障計(jì)算機(jī)及網(wǎng)絡(luò)系統(tǒng)不被非法訪問和攻擊。 密碼學(xué)是研究信息安全的重要學(xué)科，主要針對數(shù)據(jù)加密、數(shù)字簽名、身份認(rèn)證、 密鑰交換等安全理論和協(xié)議進(jìn)行研究，保障計(jì)算機(jī)尤其是網(wǎng)絡(luò)系統(tǒng)中的數(shù)據(jù)安 全性。 密碼體制的設(shè)計(jì)和研究都是在k e r c k h o f f 的假設(shè)前提下進(jìn)行的。一般情況 下，密碼體制由密碼算法和密鑰組成，k e r c k h o f f 假設(shè)要求密碼體制的安全性僅 依賴于密鑰的保密而不依賴加密和解密算法。因此，密鑰的安全是整個(gè)密碼體 制安全的前提，密鑰一旦泄露將直接破壞密碼體制的安全性，因此必須解決密 鑰管理問題。秘密共享為解決密鑰管理問題提供了嶄新的思路，在密鑰的安全 保存、傳輸及合法利用中起著非常關(guān)鍵的作用。 1 1 研究目的和意義 門限秘密共享的概念最早是由s h a m i r 1 l 并i i b l a k l e y t 2 】于1 9 7 9 年分別提出的， 其基本思想是將秘密分成行個(gè)秘密份額( 也稱為份額) ，并安全地分發(fā)給以個(gè)成員 ( 參與者) ，使得其中t 個(gè)或更多的成員聯(lián)合就可以恢復(fù)秘密，而少于t 個(gè)成員 就無法恢復(fù)。秘密共享具有如下優(yōu)點(diǎn)： ( 1 ) 有利于防止權(quán)力過于集中； ( 2 ) 確保秘密的安全性和完整性； ( 3 ) 提高系統(tǒng)的可靠性。 然而，傳統(tǒng)的秘密共享方案對于保護(hù)生命周期較長的秘密并不十分有效， 因?yàn)槿肭终呖梢岳谜麄€(gè)生命周期進(jìn)行長時(shí)間的攻擊。當(dāng)然，我們可以周期性 地更新秘密本身來解決這個(gè)問題。但是，對有些周期比較長、機(jī)密性比較強(qiáng)的 秘密( 例如各種密鑰、企業(yè)機(jī)密文件、高機(jī)密數(shù)據(jù)等) 來說，更新秘密是不現(xiàn)實(shí) 的。先應(yīng)秘密共享方案( p r o a c t i v es e c r e ts h a r i n g ，簡稱p s s ) t 3 】為解決這個(gè)問題提 供了個(gè)嶄新的途徑。 先應(yīng)秘密共享方案的基本思想就是“分布+ 更新”，即在秘密共享的基礎(chǔ)上 引入秘密共享份額周期更新機(jī)制。系統(tǒng)周期性地用新份額替換當(dāng)前使用的舊份 額，由于新份額與舊份額間無相關(guān)性，攻擊者在前期獲得的秘密份額變得毫無 用處。攻擊者欲獲得完整的秘密信息，必須在一個(gè)周期內(nèi)獲得足夠多的秘密份 額。先應(yīng)秘密共享使得攻擊者的有效可利用時(shí)間大大縮短，從而保證了秘密的 長期安全性。先應(yīng)秘密共享已經(jīng)在認(rèn)證中心的密鑰管理，電子商務(wù)中銀行電子 貨幣的簽名密鑰管理，安全數(shù)據(jù)庫的密鑰管理等眾多場合有著廣泛的應(yīng)用。 在大多數(shù)秘密共享方案中，成員的秘密份額都是由可信中心分發(fā)的。實(shí)際 應(yīng)用中，這不僅增加了可信中心的計(jì)算、傳輸和存儲復(fù)雜度，而且會(huì)使得可信 中心成為攻擊者的首選目標(biāo)，影響系統(tǒng)的安全性。此外，被絕對信任的可信中 心并不存在，因此需要探索無可信中心的秘密共享方案。 為了提高秘密共享的安全性，本文提出了一種新的先應(yīng)秘密共享方案，該 方案無需可信中心。為了提高系統(tǒng)的魯棒性，共享秘密保持不變的情況下，所 有成員如何定期更新秘密份額是本方案研究的主要目的。另外，沒有可信中心 的情況下，如何完成成員變更( 包括成員的添加和刪除) 引起的部分秘密份額 的更新是本方案研究的另一目的。 1 2 國內(nèi)外研究現(xiàn)狀 秘密共享最早由s h a m i r 和b l a k l e y 提出。隨后，出現(xiàn)許多秘密共享的其它算 法，如基于中國剩余定理的a s m u t h b l o o m 法【4 j 、使用矩陣乘法的 k a m i n g r e e n e h e l l m a n 方法【5 】以及b r i c k e l l 的矢量空間方法【6 】等。 s h a m i r 方案需要一個(gè)可信中心，然而出于某種目的，可信中心可能分發(fā)給 某個(gè)成員假的秘密份額，這樣該成員與其他成員合作將不能恢復(fù)秘密。為了防 止可信中心的權(quán)威欺騙，1 9 8 5 年c h o r 7 】等人首先提出了可驗(yàn)證秘密共享的思想。 隨后，f e l d m a n 提出了一種可驗(yàn)證的秘密共享方案【8 】，該方案基于離散對數(shù)問題。 為了保留s h a m i r 方案的完備性，p e d e r s o n 提出了一種新的可驗(yàn)證方案 9 】 4 6 1 。1 9 9 4 年h a r n 提出了一種基于e 1 g a m a l 簽名的門限群簽名方案【l ，該方案不需要可信 中心。然而，在h a m 的方案中，超過門限值的小組成員聯(lián)合起來，能夠恢復(fù)某 個(gè)成員的私鑰。r g e n n a r o 給出了分布式環(huán)境下的聯(lián)合秘密共享協(xié)議【1 1 j o i n t s h a m i rr s s 協(xié)議) ，分布式密碼系統(tǒng)是一個(gè)公鑰密碼系統(tǒng)，其私鑰分布在多個(gè) 用戶中，并且一定數(shù)量的用戶可以恢復(fù)私鑰。這樣，部分私鑰信息的丟失不會(huì) 影響整個(gè)系統(tǒng)的安全性。 在秘密共享方案中，部分秘密份額可能會(huì)泄漏或者損壞。泄漏或損壞的秘 密份額達(dá)到門限數(shù)目，秘密就會(huì)暴露或者丟失。因此在保證共享秘密保持不變 的情況下，成員需要周期性地更新自己的秘密份額，使以前暴露或損壞的秘密 份額不會(huì)對秘密的安全產(chǎn)生威脅，這樣就出現(xiàn)了先應(yīng)秘密共享方案( p r o a c t i v e s e c r e ts h a r i n g ，簡稱p s s ) 。 ro s t r o v s k y 和my u n g 屹】于1 9 9 1 年最早提出先應(yīng)秘密共享的概念， h e r z b e r g 將先應(yīng)秘密共享與門限密碼學(xué)結(jié)合，提出了動(dòng)態(tài)r s a 的先應(yīng)秘密共享 算法【3 】。在h e r z b e r g 方案的基礎(chǔ)上，隨后出現(xiàn)了多種不同形式的先應(yīng)式秘密共 享方案 1 孓2 0 1 。為了保證其他成員在不泄漏秘密份額的情況下，新成員可以正確 地獲得秘密份額，李琥提出了一個(gè)新成員加入?yún)f(xié)議【2 引。 2 先應(yīng)秘密共享的思想已經(jīng)應(yīng)用到數(shù)字簽名中，并且出現(xiàn)了各種前向安全簽 名方案。其中，a n d e r s o n 2 l 】最先提出前向安全特性的概念，b e l l a r e 和m i n e r 率 先實(shí)現(xiàn)了前向安全簽名方案【22 1 ，之后出現(xiàn)了各種前向安全簽名方案 2 3 2 7 1 。 現(xiàn)有的先應(yīng)秘密共享方案中都存在可信中心，系統(tǒng)的安全性受到很大的影 響；并且這些方案都主要集中在所有成員定期更新問題的研究上，而對于由于 添加刪除成員引起的部分秘密份額的更新問題很少研究。 1 3 研究內(nèi)容和內(nèi)容安排 本文主要對先應(yīng)秘密共享進(jìn)行研究，通過分析前人的成果與不足，提出一 種新的先應(yīng)秘密共享方案。研究的主要內(nèi)容包括： ( 1 ) 深入研究門限秘密共享理論及其典型方案； ( 2 ) 提出了新的先應(yīng)秘密共享方案； ( 3 ) 實(shí)現(xiàn)原型系統(tǒng)，驗(yàn)證了該方案的可行性和安全性。 本論文的組織結(jié)構(gòu)如下： 第一章緒論。闡述了課題的研究的目的和意義、國內(nèi)外研究現(xiàn)狀和研究的 主要內(nèi)容及內(nèi)容安排。 第二章密碼學(xué)概述。介紹了經(jīng)典密碼學(xué)和公鑰密碼學(xué)的主要內(nèi)容以及數(shù)字 簽名技術(shù)。 第三掌門限秘密共享。介紹了門限秘密共享的基本思想和主要類型，重點(diǎn) 分析了門限秘密共享的幾種典型方案。 第四章先應(yīng)秘密共享方案。詳細(xì)介紹了方案的主要內(nèi)容，并分析該方案的 可行性、安全性以及方案的特點(diǎn)。 第五章先應(yīng)秘密共享原型系統(tǒng)的實(shí)現(xiàn)。闡述了大數(shù)運(yùn)算的實(shí)現(xiàn)，重點(diǎn)介紹 了原型系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)過程。 第六章總結(jié)與展望?？偨Y(jié)本文所做的工作，并對先應(yīng)秘密共享的研究及應(yīng) 用前景做出展望。 第二章密碼學(xué)概述 密碼學(xué)作為一種保護(hù)信息安全的方法，是一門古老又年青的學(xué)科，它最早 應(yīng)用于軍事、外交和情報(bào)等少數(shù)領(lǐng)域，后來隨著科技的不斷發(fā)展而逐漸進(jìn)入到 人們的生活中，其商用價(jià)值和社會(huì)價(jià)值已經(jīng)得到充分的認(rèn)可。 密碼學(xué)包含兩個(gè)分支：密碼編碼學(xué)和密碼分析學(xué)。密碼編碼學(xué)是對信息進(jìn) 行編碼實(shí)現(xiàn)信息保密的學(xué)科；密碼分析學(xué)是研究、分析、破譯密碼的學(xué)科。 兩者相互對立，又互相促進(jìn)地共同向前發(fā)展。 密碼學(xué)的發(fā)展可以分為經(jīng)典密碼學(xué)和公鑰密碼學(xué)。 2 1 經(jīng)典密碼學(xué) 經(jīng)典密碼學(xué)是基于消息的發(fā)送者和接收者運(yùn)用相同的密鑰來達(dá)到消 息加密的目的，其具體實(shí)現(xiàn)過程是：首先消息的發(fā)送者用共享密鑰加密消 息，然后消息的接收者用相同的密鑰解密消息并獲取消息。采用這種方法 的密碼學(xué)我們又將它稱之為單鑰密碼學(xué)或?qū)ΨQ密鑰密碼學(xué)。這種密碼體制 大體上可分為兩類：代替密碼和換位密碼。 代替密碼：基本思想是將明文中的字符替換成密文中的另外一個(gè)字 符。在經(jīng)典密碼學(xué)中，有四種類型的代替密碼：簡單代替密碼、多名碼代 替密碼、多字母代替密碼和多表代替密碼。 換位密碼：基本思想是根據(jù)某種算法不改變明文的字符形式僅僅改變 字符的位置，將重新排列的信息作為密文。 如果將代替密碼和換位密碼相結(jié)合便形成乘積式密碼，它是一種混合 式密碼。使用最廣泛的混合式密碼就是d e s 算法。 對稱密鑰系統(tǒng)中，消息的發(fā)送者和接受者必須在沒有第三方知道的情況 一下獲取雙方都同意的密鑰，如果他們處于不同的地理位置，特別是不可能當(dāng)面 交流的情況下，他們就必須借助一個(gè)可靠的第三方或是一個(gè)可靠的通信系統(tǒng)來 確定密鑰。然而人和通信系統(tǒng)都未必是可靠的，所以密鑰的傳輸和保管是對稱 密碼學(xué)中一個(gè)棘手的問題。 2 2 公鑰密碼學(xué) 在對稱密鑰算法中，算法的安全性很大程度上取決于密鑰的安全性， 一旦密鑰泄漏出去，那就意味著任何獲得密鑰的人都可以進(jìn)行加密和解 密。為了更好地解決密鑰的安全性問題，研究人員做了大量新的嘗試。19 7 6 年，w h i t f i e l dd i f f i e 和m a r t i nh e l l m a n 2 9 】發(fā)表了開創(chuàng)性的論文“密碼學(xué)的 新方向 ，提出了公鑰密碼體制的思想，給密碼學(xué)的發(fā)展帶來了劃時(shí)代的 變革。 4 公鑰密碼體制用到兩個(gè)不同的密鑰：一個(gè)是公開的( 公鑰) ，另一個(gè)是秘密 的( 私鑰) 。從公鑰很難推導(dǎo)出私鑰。公鑰用來加密消息，但無法解密，只有私 鑰能夠解密消息。公鑰密碼體制對于保密通訊、密鑰分配和鑒別等領(lǐng)域都有著 深遠(yuǎn)的影響。公鑰密碼體制將加密密鑰和解密密鑰分開的特點(diǎn)，可以實(shí)現(xiàn)多個(gè) 用戶加密的消息只能由一個(gè)用戶解密；或者由一個(gè)用戶加密的消息能由多個(gè)用 戶解密。前者應(yīng)用在網(wǎng)絡(luò)中，實(shí)現(xiàn)了保密通信；后者應(yīng)用在認(rèn)證系統(tǒng)中，實(shí)現(xiàn) 了數(shù)字簽名。 公開密鑰的第一個(gè)算法是由r a l p hm e r k l e 和m a r t i nh e l l m a n 聯(lián)合開 發(fā)的背包算法【3 1 】 32 1 。這個(gè)算法是基于組合數(shù)學(xué)中的背包問題而提出的， 該系統(tǒng)又被稱為m h 背包公鑰密碼系統(tǒng)。由于m e r k l e h e l l m a n 變換無法 將超遞增序列的特性完全隱藏起來，m h 背包算法已經(jīng)被破譯而失去了實(shí) 用價(jià)值。 繼m e r k e l 和h e l l m a n 之后，r i v e s t ，s h a m i r 和a d l e m a n 又聯(lián)合提出 了r s a 公鑰密碼算法【”】，它的安全性是依賴于大數(shù)的素因子分解困難性。 此后，又出現(xiàn)了r s a 的變形：r a b i n 密碼。 此外，還有基于離散對數(shù)問題( d l p 問題) 的e 1 g a m a l 算法【3 4j 和基于 橢圓曲線離散對數(shù)問題的橢圓曲線密碼算法e c c 3 5 1 【36 1 。美國政府的官方 數(shù)字簽名標(biāo)準(zhǔn)d s a 算法【37 】就是在e 1 g a m a l 的成果基礎(chǔ)上稍作修改而成。 盡管還有許多其他公開密鑰算法，但是隨著計(jì)算機(jī)硬件的發(fā)展和數(shù)學(xué) 理論上的突破可以在實(shí)際中使用的算法所剩無幾。經(jīng)過大量研究和實(shí)踐， r s a ，e 1 g a m a l 和e c c 等公開密鑰系統(tǒng)已經(jīng)被證明是符合要求的，并且日 漸趨于完善。 2 2 1r s a 算法 r s a 是由r i v e s t ，s h a m i r 和a d l e m a n 聯(lián)合提出的公鑰系統(tǒng)，它的基礎(chǔ) 是數(shù)論的歐拉定理，其安全性依賴于大數(shù)的素因子分解的困難性。 r s a 算法的具體描述如下： ( 1 ) 取兩個(gè)素?cái)?shù)p ，q ( 保密) ； ( 2 ) 計(jì)算n = p q ( 公開) ，矽( 以) = ( p - 1 ) ( q - 1 ) ( 保密) ； ( 3 ) 隨機(jī)選擇整數(shù)e ( 公開) ，滿足g c d ( e ，妒( ，z ) ) = 1 ； ( 4 ) 計(jì)算d ( 保密) ，滿足d e 毫l ( m o d 0 ( n ) ) 。 加密算法：c = e ( m ) = m 。m o dn 解密算法：m = d ( c ) = c dm o dn 如果n = p q 被因子分解，r s a 算法就被攻破。因?yàn)槿绻@得p , q ，便 可計(jì)算出( ，1 ) = ( p 一1 ) ( g - 1 ) ，并從等式d e 蘭l ( m o d ( n ) ) 最終能求出解密密鑰d 。 因此，r s a 算法的安全性依賴于因子分解的困難性。 隨著因子分解算法不斷的進(jìn)步以及計(jì)算機(jī)硬件技術(shù)的飛速發(fā)展，為了 保證r s a 算法的安全性，采用了如下措施： ( 1 ) 產(chǎn)生位數(shù)更大的大素?cái)?shù)。現(xiàn)今r s a 的密鑰長度一般采取1 0 2 4 比特，這 能夠保證在現(xiàn)有的數(shù)學(xué)知識基礎(chǔ)上，r s a 加密體制是安全的； ( 2 ) 選取恰當(dāng)?shù)膒 ，q 。s i m m o n s 和n o r r i s 曾證明，如果p ，q 選取不當(dāng)，破譯 者可以利用公開密鑰反復(fù)對密文進(jìn)行多次加密就能還原出明文。r i v e s t 提出， 若選擇的p ，q 使p 1 ，q 1 各能被一個(gè)大素?cái)?shù)p ，q 整除，并使得p 1 ，q 1 分別含 有大素?cái)?shù)因子，則上述破譯成功的概率很小。 ( 3 ) 選擇安全素?cái)?shù)因子作為p ，q 。b l a k l a y 提出了安全素?cái)?shù)的概念，即若素 數(shù)p 形如p = 2 p + l ( p 為另一大素?cái)?shù)) ，則稱p 為安全的。若p 和q 兩個(gè)素?cái)?shù)因 子均為安全素?cái)?shù)，那么將大大提高r s a 體制的安全性。 r s a 算法的優(yōu)點(diǎn)是密鑰空間大，安全性能高，但是加密速度比d e s 算法慢很多。如果通過硬件實(shí)現(xiàn)，r s a 比d e s 慢大約10 0 0 倍，即使通過 軟件實(shí)現(xiàn)也要慢上10 0 倍左右。在實(shí)際應(yīng)用中，r s a 算法常常和d e s 算 法結(jié)合使用：d e s 加密明文，r s a 加密d e s 的密鑰，這樣既解決了長報(bào) 文加密的效率問題，又解決了d e s 密鑰分配的問題。 2 2 2e l g a m a l 算法 e 1 g a m a l 算法既可用于數(shù)字簽名又可用于加密，其安全性依賴于有限 域上的離散對數(shù)分解的難度?，F(xiàn)階段有限域上離散對數(shù)問題仍然無法被破 解，因此用e 1 g a m a l 算法加密后的信息在沒有密鑰的情況下是無法被恢復(fù) 的。 e 1 g a m a l 算法如下： ( 1 ) 隨機(jī)選擇g 、x 和大素?cái)?shù)p ，其中g(shù) 和x 小于p ； ( 2 ) 計(jì)算y = 9 1m o dp ，x 是私鑰，y 是公鑰，公開g 和p ； ( 3 ) 加密消息m ，選擇隨機(jī)數(shù)k ( k 和p 1 互素) ，計(jì)算：a = g km o dp 和b = y k m m o d p ( 4 ) 解密時(shí)計(jì)算：m = b a 1m o dp 因?yàn)閍 1 = g k x m o dp 以及b a 1 = y k m a 1 = g k x m g h = mr o o dp 都成立，除了y 是 密鑰的一部分以及加密是和y l c 相乘而來，它和d i f f e h e l l m a n 密鑰交換幾乎一 樣。每個(gè)e 1 g a m a l 簽名和加密都需要一個(gè)新的k 值，該值必須隨機(jī)選取。 2 2 3 橢圓曲線( e c c ) 密鑰系統(tǒng) 橢圓曲線密碼體制3 8 】 3 9 1 來源于對橢圓曲線的研究。橢圓曲線指的是 由韋爾斯特拉斯( w e i e r s t r a s s ) 方程： y 2 + 口l x y + a 3 y = 石3 + 口2 x 2 + 口4 x + a 6 6 所確定的平面曲線，它是由方程的全體解( 毛) ，) 再加上一個(gè)無窮遠(yuǎn)點(diǎn)曰構(gòu)成 的集合。其中系數(shù)a i o = 1 , 2 ，6 ) 定義在某個(gè)域上，可以是有理數(shù)域、實(shí)數(shù) 域、復(fù)數(shù)域、也可以是有限域g f ( p 7 ) 。橢圓曲線密碼體制中的橢圓曲線定 義在有限域上。給定橢圓曲線e 上的一個(gè)點(diǎn)尸，對任意的點(diǎn)q ，如果存在 整數(shù)m 使q = m p ，如何求解m 為橢圓曲線上的離散對數(shù)問題，而橢圓曲線 密碼體制的安全性就是基于該問題的困難性。將橢圓曲線應(yīng)用到密碼學(xué) 上，最初是由n e a lk o b l i t z 3 9 】和v i c t o rm i l l e r t 3 8 】在19 8 5 年分別獨(dú)立提出的。 橢圓曲線密碼體制是目前公鑰密碼體制中，對每比特提供的加密強(qiáng)度 最高的一種體制。目前求解橢圓曲線上的離散對數(shù)問題的最好算法是 p o l l a r d r h o 4o j 方法，其時(shí)間復(fù)雜度是完全指數(shù)時(shí)間的。而目前最好的大整 數(shù)分解算法的時(shí)間復(fù)雜度是亞指數(shù)時(shí)間的。因此，當(dāng)r s a 的密鑰使用2 0 4 8 位時(shí)，僅使用2 3 4 位e c c 密鑰，就可以獲得相同的安全強(qiáng)度，此時(shí)它們之 間的密鑰長度相差6 倍，且此差距會(huì)隨著e c c 密鑰的增長而變得更大。 2 3 數(shù)字簽名 從社會(huì)的發(fā)展來看，隨著電子信息時(shí)代的來臨，人們越來越希望通過 數(shù)字通信網(wǎng)進(jìn)行迅速的、遠(yuǎn)距離的交易。在這種數(shù)字化的信息世界里，傳 統(tǒng)的手寫簽名和印簽已經(jīng)難以發(fā)揮作用，因此，人們迫切需要一種具有手 寫簽名和印簽功能的數(shù)字化簽名方法。這正是數(shù)字簽名技術(shù)產(chǎn)生的背景。 數(shù)字簽名有助于實(shí)現(xiàn)大型網(wǎng)絡(luò)安全通信中的密鑰分配，同時(shí)也是實(shí)現(xiàn)認(rèn)證 的重要工具。 數(shù)字簽名的作用與手寫簽名類似，應(yīng)滿足如下條件： ( 1 ) 可驗(yàn)證性。接收方能夠驗(yàn)證發(fā)送方所宣稱的身份； ( 2 ) 不可否認(rèn)性。發(fā)送方不能否認(rèn)已發(fā)送的報(bào)文； ( 3 ) 不可偽造性。接收方不能偽造報(bào)文： ( 4 ) 第三方可以確認(rèn)收發(fā)雙方的消息傳遞，但不能偽造這一過程。 目前已經(jīng)提出了許多數(shù)字簽名體制，但大致可以分為兩種：一種是對 整體消息的簽字，它是消息經(jīng)過密碼變換的被簽字消息整體；另一種是對 壓縮消息的簽字，它是附加在被簽字消息之后或某一特定位置上的一段簽 字圖樣。如果按照明密文的對應(yīng)關(guān)系劃分，每一種又可分為兩種類型：一 類是確定性數(shù)字簽名，其明文與密文一一對應(yīng)，它對一特定消息的簽字不 變化，如r s a 簽名；另一類是隨機(jī)化的或概率式的數(shù)字簽名，它對同一消 息的簽字是隨機(jī)變化的，取決于簽字算法中的隨機(jī)參數(shù)取值，這時(shí)一個(gè)明 文可能有多個(gè)合法的數(shù)字簽名，如e l g a m a l 簽名。下面分別介紹基于r s a 和e l g a m a l 的數(shù)字簽名。 7 2 3 1r s a 簽名 r s a 簽名與r s a 加密不同之處在于r s a 加密是用公開密鑰e 進(jìn)行加 密，用解密密鑰d 進(jìn)行解密，而r s a 簽名正好相反，它是用解密密鑰d 進(jìn)行簽名，用公開密鑰e 進(jìn)行驗(yàn)證。具體過程描述如下： 假設(shè)明文為m 和簽名為s z n 。 參數(shù)選擇：p l 和p 2 是大素?cái)?shù)，計(jì)算甩= p 。木p ：，隨機(jī)選擇e 并根據(jù) d e 三1 m o d ( p l - 1 ) ( p 2 1 ) 計(jì)算d ，公開n 和e ，將p l ，p 2 銷毀，秘密保存d 。 簽名：對消息m ，計(jì)算散列碼h ( m ) ，定義s = s i g ( h ( m ) ) = h ( m ) om o d 1 1 驗(yàn)證：對給定消息m ，簽名s 可以按以下等式進(jìn)行驗(yàn)證： v e r k ( h ( m ) ，s ) = 1 h ( m ) = s 。r o o dn 在r s a 實(shí)現(xiàn)數(shù)字簽名的方案中，將要簽名的消息作為一個(gè)散列函數(shù) 的輸入，產(chǎn)生一個(gè)定長的安全散列碼。使用數(shù)字簽名者的解密密鑰對這個(gè) 散列碼進(jìn)行加密就形成了簽名，然后將簽名附在消息后。驗(yàn)證者根據(jù)消息 產(chǎn)生一個(gè)散列碼，同時(shí)使用簽名者的公開密鑰對簽名進(jìn)行解密。 r s a 簽名的安全性依賴于分解甩= p ，木p ：的困難性。 2 3 2e 1 g a m a l 簽名 e 1 g a m a l 簽名的基本過程為：m 為需要簽名的消息，選擇大素?cái)?shù)p 、 隨機(jī)數(shù)x 、g z p ，其中g(shù) 是z p 乘法群的一個(gè)本原元，x 是用戶的私人密 鑰。計(jì)算y = g xm o dp 得到公開密鑰( p ，g ，y ) 。 簽名：給定消息m ，發(fā)送方進(jìn)行簽名： ( 1 ) 發(fā)送方在z 口乘法群中選擇隨機(jī)數(shù)k ； ( 2 ) 計(jì)算m 的散列碼h ( m ) ； ( 3 ) 計(jì)算r = g 。m o dp 和s = ( h ( m ) 一x r ) k “m o d ( p 一1 ) ； ( 4 ) 將s i g k ( m ，k ) = ( r l l s ) 作為簽名，將m ，( r l i s ) 發(fā)送給接收方。 驗(yàn)證：接收方收到m ，( r | | s ) ，計(jì)算出h ( m ) ，并按下式進(jìn)行驗(yàn)證： v e r k ( h ( m ) r ，s ) = 1 錚y r = g h 【m r o o dp 這是因?yàn)椋簓 r r 8 = g x r + k s = g h ( m m o dp 在此方案中，對同一個(gè)消息m ，由于隨機(jī)數(shù)k 不同會(huì)產(chǎn)生不同的簽名值。 該體制的安全性依賴于求解離散對數(shù)問題的困難性。 2 4 本章小結(jié) 本章首先概述了密碼學(xué)的發(fā)展，探討了幾種重要的公鑰密碼算法，如 r s a 算法、e l g a m a 算法和橢圓曲線( e c c ) 密鑰系統(tǒng)等，最后介紹了數(shù)字簽 名的相關(guān)內(nèi)容。 第三章門限秘密共享 門限秘密共享是信息安全和數(shù)據(jù)保密中的重要手段，在多方環(huán)境中，它 是一個(gè)基本協(xié)議和工具。其概念最早由s h 鋤i r 【1 】和b l a k l e y 2 j 于1 9 7 9 年分別提出 的。這一思想的最初動(dòng)機(jī)在于解決密鑰管理的安全性問題。通常，一個(gè)密鑰 可能決定著多個(gè)重要文件的安全性，一旦密鑰丟失或者損壞，都可能造成 多個(gè)重要文件不能打開，在密鑰失竊的情況下，還可能造成多個(gè)文件被竊取( 一 個(gè)密鑰可能加密多個(gè)文件) 。為了解決這個(gè)問題，一種方法是創(chuàng)建密鑰的多 個(gè)備份并且將這些備份分發(fā)給不同的人保管。但是這種方法并不理想，因 為創(chuàng)建的備份數(shù)目多或者少都會(huì)影響系統(tǒng)的安全性和魯棒性。門限秘密共 享在不增加風(fēng)險(xiǎn)的前提下能夠很好地解決上述問題。 3 1 門限秘密共享的基本思想 門限秘密共享的基本思想是將所需共享的秘密s 分成n 個(gè)份額s f ，分 發(fā)給以個(gè)成員，并且滿足： ( 1 ) 任何f 個(gè)以上的s f ，能夠重構(gòu)s ； ( 2 ) 少于t 個(gè)s f ，無法重構(gòu)s 。 下面給出門限秘密共享的正式定義【4 l 】：設(shè)p = ，最，只) 為成員集合， s ，s ，s ：，s 。為n + 1 個(gè)有限集。一個(gè)( t ，n ) 門限方案由兩個(gè)算法組成，一個(gè)是秘 密分配算法，另一個(gè)是秘密恢復(fù)算法。對于秘密s ，分配中心通過秘密分 配算法生成秘密份額= b ，是，j 。) e s , x s 2 x 最和對應(yīng)于成員集的公開目錄 局= 缸。，x ：，工。 ，一般簡單地記2 p = 1 ，2 ，z ) 。對每個(gè)a = e ，p , 2 ，氣) c p ， i ， k ) 個(gè)人能阻止秘密的恢復(fù)。 b e u t e l s p a c h e r 給出了實(shí)現(xiàn)這一特殊安全要求的秘密共享方案【42 | ，即可阻 止恢復(fù)秘密的秘密共享( s e c r e ts h a r i n gw i t hp r e v e n t i o n ) 方案。其基本思想： 每個(gè)參與者都有兩個(gè)分享的秘密份額，一個(gè)為“是 ，一個(gè)為“否 ，當(dāng)決定是 否能恢復(fù)秘密時(shí)，參與者選擇并提交自己的秘密份額，如果多于k 個(gè)“是而 少于m 個(gè)“否”，就可重構(gòu)秘密，否則就不能重構(gòu)秘密。 ( b ) 基于多分辨濾波的秘密共享 l o 在現(xiàn)有大多數(shù)門限秘密共享方案中，各參與者的權(quán)限相同，不適用于 社會(huì)中廣泛存在的等級關(guān)系；另外，任意t 個(gè)擁有份額的參與者都可以組 成授權(quán)子集，不利于分組控制。為此，s a n t i s 等人【43 提出了多分辨濾波秘 密共享的概念。其基本思想是借用現(xiàn)代信號中經(jīng)常用到的雙通道濾波器 組。一個(gè)信號序列經(jīng)過雙通道濾波器組濾波，可以分解成兩組序號序列。 將分解后的兩組信號繼續(xù)通過雙通道濾波器，由此得到多種“分辨率 層 次的信號表示，用這些信號即可精確恢復(fù)原有信號( 秘密) 。 ( c ) 可視秘密共享 在19 9 4 年歐洲密碼學(xué)會(huì)議上，n a o r 和s h a m i r 4 4 】首次提出了可視密碼 學(xué)( v i s u a lc r y p t o g r a p h y ) 來實(shí)現(xiàn)圖像的共享。其目標(biāo)是對二進(jìn)制黑白圖像 進(jìn)行( t ，n ) f - j 限視覺式處理：將原圖像中的每個(gè)像素5 。分成m 個(gè)子像素j ， 其中m 為一個(gè)完全平方數(shù)，這些子像素非黑即白地緊鄰在一起。在( t , n ) 門限可視秘密共享方案中，將原圖像分成n 張投影片，若將數(shù)量大于門限 值t 的投影片重疊在一起( 即m 個(gè)子像素作或運(yùn)算) ，則重疊后的圖像每一 點(diǎn)色彩均相同，反之，則會(huì)表現(xiàn)出各點(diǎn)不同的差異，造成視覺上的區(qū)別。 ( d ) 量子秘密共享 近年來，基于物理現(xiàn)象的密碼學(xué)也得到了研究界的重視。量子密碼可 能成為光通信網(wǎng)絡(luò)中數(shù)據(jù)保護(hù)的有力工具。量子秘密共享是量子密碼理論 的重要組成部分，其基本原理是量子糾纏( q u a n t u me n t a n g l e m e n t ) 。量子 秘密共享主要受到量子的“無性( n o c l o n i n g ) 特性 的物理限制。 ( e ) 基于廣義自縮序列的秘密共享 基于廣義自縮序列的秘密共享【45 】是l a g r a n g e 內(nèi)插多項(xiàng)式體制的一種 延伸，其基本思想是構(gòu)造兩個(gè)l a g r a n g e 多項(xiàng)式，一個(gè)用于恢復(fù)秘密，一 個(gè)則用于檢驗(yàn)份額和秘密的有效性。后者的系數(shù)來自廣義自縮序列，由于 其良好的偽隨機(jī)性，所以該類秘密共享方案是安全可靠的，并且能簡捷地 更新秘密份額。 3 3 門限秘密共享的典型方案研究 3 3 1 經(jīng)典的門限秘密共享 ( 1 ) s h a m i r 的門限方案 s h a m i r 提出的門限秘密共享方案可以描述如下： 系統(tǒng)參數(shù)：1 1 是參與者的數(shù)目，t 是門限值，p 是一個(gè)大素?cái)?shù)，p 挖t 。 同時(shí)，要求p 大于秘密的最大值，秘密空間與份額空間相等，均為有限域 g f ( p ) 。x i ，x 2 ，x n 為g f ( p ) 上n 個(gè)互不相同的元素。以上這些參數(shù)都是公 開的。 秘密分配算法： ( a ) 分發(fā)者d 首先隨機(jī)選擇g f ( p ) 上的一個(gè)t 一1 次的多項(xiàng)式 f ( x ) = a o + 口1 工+ + a t _ 1 3 c - 1m o d q 其中s = a o 。 ( b ) 分發(fā)者d 對于x 1 ，x 2 ，x n 分別計(jì)算s i = f ( x i ) ，其中1 f ，z 。 ( c ) 分發(fā)者d 將( x i ，s i ) 分配給成員p i ，s i 作為p i 擁有的秘密份額。 秘密恢復(fù)算法： 任意t 個(gè)秘密份額的持有者都可以將秘密份額放在一起，通過 l a g r a n g e 插值公式恢復(fù)出秘密信息s ： tt ， m ) = j 。兀蘭m o d p 乍t s = 口。= 們) 1 = 1 j = l ，f “f “ 而少于t 個(gè)成員的集合無法計(jì)算出秘密s 。 ( 2 ) b l a k l e y 的矢量方案 b l a k l e y 利用多維空間中的點(diǎn)構(gòu)造門限方案l 2 1 秘密被看成m 維空間 中的一個(gè)點(diǎn)，每一個(gè)影子是包含該點(diǎn)的( m 1 ) 維超平面的方程，任何m 個(gè) 超平面的交點(diǎn)就可以確定該點(diǎn)。 b l a k l e y 的方案比s h a m i r 的方案效率要低，但是它有一個(gè)特性：任何兩 個(gè)影子之間是無關(guān)的。而s h a m i r 的方案中足夠多的影子是可以計(jì)算出其他 影子的。 ( 3 ) a s m u t h b l o o m 的門限方案 a s m u t h b l o o m 的( f ，1 ) 門限方案 4 】是通過素?cái)?shù)實(shí)現(xiàn)的：選擇大素?cái)?shù)p ， 使得p 大于消息m ，選擇行個(gè)小于p 的數(shù)d 。，d ：，d 。使得： ( a ) d ，的值按遞增順序排列，即d ， p x d 。一。+ 2x d 。一。+ 3 x d 。 分配秘密份額時(shí)，選擇一個(gè)隨機(jī)數(shù)，計(jì)算： m = t + 巾 計(jì)算份額k i ： k f = m m o d d f 由中國剩余定理可知：由任意f 個(gè)或t 個(gè)以上的份額能夠恢復(fù)m ，少于f 個(gè) 份額則不能恢復(fù)。 ( 4 ) k a m i n g r e e n e h e l l m a n 的門限方案 k a m i n g r e e n e h e l l m a