第二章 可驗證秘密分享的基礎(chǔ)理論

1、第二章 可驗證秘密分享的基礎(chǔ)理論本章將介紹一些必要的秘密分享基礎(chǔ)知識，并對幾個典型的分享方案進行了描述和分析2.1 公鑰密碼密碼系統(tǒng)根據(jù)密鑰的特點，可分為兩類，即私鑰密碼系統(tǒng)和公鑰密碼系統(tǒng)在私鑰密碼系統(tǒng)中，解密密鑰與加密密鑰相同或容易從加密密鑰導出因此，加密密鑰的暴露會使系統(tǒng)變得不安全；私鑰密碼系統(tǒng)的一個嚴重缺陷是通信雙方必須使用一個安全信道預(yù)先約定密鑰，但現(xiàn)實中這一點是很難實現(xiàn)的在公鑰密碼系統(tǒng)中，解密密鑰和加密密鑰不同，從一個難以推出另一個，解密和加密是可分離的；從而，通信雙方無需事先交換密鑰就可以建立起保密通信公鑰密碼的思想是由Diffie和Hellman在1976年首次提出的，給密碼學的

2、發(fā)展帶來了劃時代的變革自從那時起，人們基于不同的計算問題，提出了大量的公鑰密碼系統(tǒng)當然最重要的有RSA體制、ElGamal體制、Williams體制、Merkle-Hellman背包體制和基于身份的公鑰密碼系統(tǒng)等；其中RSA體制是1977年由Rivest，Shamir和Adleman提出的第一個比較完善的公鑰密碼系統(tǒng) 公鑰密碼的研究中經(jīng)常涉及到一個很重要的概念陷門單向函數(shù)一個函數(shù)，如果對它的定義域上的任意都易于計算，而對于的值域中的幾乎所有的，即使當已知時要計算也是不可行的，就稱是單向函數(shù)若當給定某些輔助信息下易于計算單向函數(shù)的逆，就稱是一個陷門單向函數(shù)這一輔助信息就是解密密鑰這就是設(shè)計公鑰密

3、碼體制的基本原理這類密碼的強度取決于求的計算復雜性2.1.1 主要的基本概念這里，介紹公鑰密碼學中的一些重要的基本概念u 公鑰密碼體制由上面的敘述可知，使用傳統(tǒng)的密碼體制進行秘密通信，顯然要求不同用戶間應(yīng)約定不同的密鑰這樣，如果個用戶都能夠秘密地交換信息，則每個用戶將需要個密鑰；這樣巨大的密鑰量給密鑰的分配與管理帶來極大的困難由Diffie和Hellman提出的公鑰密碼體制解決了這個問題，他們提出：加密密鑰與解密密鑰分開，并將加密密鑰公開、解密密鑰保密這樣，每個用戶擁有兩個密鑰：公開鑰（公鑰）和秘密鑰（私鑰）,并且所有公鑰均被記錄在類似電話號碼薄的密鑰本中這種密碼體制的安全性是從已知的公鑰、加

4、密算法與在信道上截獲的秘文不能求出明文或私鑰若用、分別表示加、解密變換，則它們應(yīng)滿足如下三個條件：（1）是的逆變換，即（明文空間），均有（2）在已知的公鑰與私鑰的條件下，與均是多項式時間的確定性算法（3），找到算法，使得是非常困難的這里所謂的非常困難是指在現(xiàn)有的資源與算法下，找到是不現(xiàn)實的 滿足上述三條的定義在正整數(shù)集上的數(shù)論函數(shù)稱為陷門單向函數(shù)于是設(shè)計公鑰密碼體制就變成尋找陷門單向函數(shù)通常選擇NP問題或NPC問題作為構(gòu)造公鑰密碼體制的數(shù)學基礎(chǔ)u 門限方案不論哪種密碼體制，解密密鑰都是需要嚴格保密的；所以，研究密鑰的管理就成為一個重要課題以往，通常是將要管理的密鑰放在特殊警衛(wèi)的保險柜內(nèi)，或按照

5、某種方式記在某個人的頭腦里；但這些都是不安全的為了可靠起見，人們想到將密鑰復制成多個副本，存放在不同的保險柜內(nèi)或計算機中，或者增加掌握密鑰的人數(shù)，但這樣做顯然又增加了泄密的可能性為了解決這一問題，Shamir和Blakley在1979年分別給出了門限密鑰分散管理方案（簡稱門限方案）；簡單地說，設(shè)密鑰通過分配算法被分發(fā)給個成員保管，如果滿足：（1）任何不少于個的合格成員通過所持有的正確的信息都可以重構(gòu)；（2）任何個以下的成員集都無法重構(gòu)；稱這種方案為門限方案，其中為方案的門限值u 數(shù)字簽名在進行秘密通信中，怎樣才能鑒別收方收到的信息確定是發(fā)方所發(fā)的，且發(fā)方可以確認內(nèi)容沒有被收方竄改？這是一個十分

6、重要的問題；而解決這個問題的辦法就是實施數(shù)字簽名在公鑰密碼體制中，如果加、解密變換、是可交換的互逆變換，即對，有；則可以用這樣的PKC來實現(xiàn)數(shù)字簽名這時的公鑰密碼體制就可用于數(shù)字簽名設(shè)用戶發(fā)送一個簽了名的明文給用戶，則操作過程如下：（1）先用自己的私鑰變換得到；（2）再用用戶的公鑰對進行變換得到，并將發(fā)送給用戶；（3） 收到后，用他的私鑰進行變換得 ；（4）再用用戶的公鑰對進行變換得到這樣，用戶就收到了由用戶簽了名的明文因為除外，任何人均無法由明文產(chǎn)生，所以這樣做的結(jié)果是：用戶確信收到的明文是用戶所發(fā)送的，而用戶也無法否認發(fā)送過明文2.1.2 重要的公鑰密碼體制這里，主要描述幾個最重要的公鑰密

7、碼體制u RSA密碼體制RSA體制的安全性是基于分解大整數(shù)的困難性 設(shè)其中和為素數(shù)設(shè)，且定義對于，定義加密變換為 ，；解密變換為，；值是公鑰，是私鑰使用RSA體制時必須注意幾點：（1）不能泄露解密指數(shù)，否則必須重新選擇模數(shù)；（2）為了使分解算法（分解算法是一種分解大整數(shù)的方法）失敗，選擇和時應(yīng)使和含有大的素因子一般的方法是選擇兩個大素數(shù)和，使得和也是素數(shù)（形如的素數(shù)通常稱為安全素數(shù)）；（3）不同用戶不可以共用模數(shù)這是因為，假定用戶與共用模數(shù)，他們的加密指數(shù)分別為和，且如果用戶想加密同一明文送給與，那么用戶計算，；然后將發(fā)送給 假定截取到了和，那么就可以按照歐幾里德算法求出和,使得，則這表明，無

8、論密碼系統(tǒng)多么“安全”，解密發(fā)送的明文都是可能的； （4）不同用戶選用的素數(shù)不能相重不然的話，若與共用素數(shù)，設(shè)與分別是他們的模數(shù)，那么任何人可用歐幾里德算法求出，從而得到與的分解式u ElGamal密碼體制ElGamal體制是在密碼協(xié)議中有著大量應(yīng)用的一類公鑰密碼體制，它的安全性是基于離散對數(shù)問題的困難性在一個有限域（為素數(shù)）上的離散對數(shù)問題可敘述為：給定一個素數(shù)和的一個本原元，對，找唯一的一個整數(shù)，使得通常用來表示一般地，如果仔細選擇，那么認為該問題是困難的特別地，目前還沒有找到計算離散對數(shù)的多項式時間算法為了抵抗已知的攻擊，應(yīng)該至少為150位十進制整數(shù)，并且至少有一個大的素因子ElGama

9、l密碼體制是非確定性的，同一明文的秘文取決于每次加密者選擇的隨機值上的ElGamal公鑰密碼體制描述如下：設(shè)是一個素數(shù)，使得在上的離散對數(shù)問題是難處理的，令是一個本原元令，,定義 ，是公鑰，是私鑰對于，以及一個秘密的隨機數(shù)，定義 ，其中 ，對、，定義u Williams密碼體制密鑰的產(chǎn)生：與RSA系統(tǒng)相同，接收者任選兩個大素數(shù)，并求出；公開密鑰：加 密：若欲傳送明文給，則首先取得的公鑰，并求出密文；將密文傳送給解 密：收到密文后，將求出密文在模數(shù)下的四個平方根、及其，則必為此四個根之一若明文滿足某種格式（如后面加時間或許多0），則由此格式可以判定此四個根何者為真正的明文Williams體制由于在解密時有四個平方根，由此此系統(tǒng)并非如RSA般一明文對應(yīng)一密文的一對一系統(tǒng)利用格式法會造成傳輸效率較低（明文長度減少）為了使Williams體制為一對一的系統(tǒng)，有些學者提出利用額外兩個位使接收者能唯一確定四個平方根中何者為明文Harn及Kiesler提出一種消除此額外二位的方法，他們的方法基于下列定理：定理 若，是大素數(shù)且同余3模4，則對于任一整數(shù)，若不知道，那么的四個平方根可依下面的情況加以分辨：(1) ；(2) ；(3) ；(4) u Merkle-Hellman背包體制Merkle-Hellman背包體制