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

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

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

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

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

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

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

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

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

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