第3章幾類語(yǔ)義安全的公鑰密碼體制

       3.1語(yǔ)義安全的RSA加密方案3.1.1RSA加密算法 RSA算法是1978年由Rivest、Shamir和Adleman提出的一種用數(shù)論構(gòu)造的，也是迄今理論上*為成熟完善的公鑰密碼體制，該體制已得到廣泛的應(yīng)用。它作為陷門置換在1.3.1節(jié)中有過(guò)介紹，下面是算法的詳細(xì)描述。 設(shè)GenPrime是大素?cái)?shù)產(chǎn)生算法。 密鑰產(chǎn)生過(guò)程: GenRSA(): p,q←GenPrime(); n=pq,φ(n)=(p－1)(q－1); 選e,滿足1計(jì)算d,滿足d·e≡1 mod φ(n) pk=(n,e),sk=(n,d). 加密（其中Mpk(M): CT=Me mod n. 解密: sk(CT): M=CTd mod n. 下面證明RSA算法中解密過(guò)程的正確性。 證明: 由加密過(guò)程知CT≡Me mod n，所以 CTd mod n≡Med mod n≡Mkφ(n)+1 mod n 下面分兩種情況:

      （1） M與n互素。由歐拉定理: Mφ(n)≡1 mod n，Mkφ(n)≡1 mod n，Mkφ(n)+1≡M mod n 即CTd mod n≡M。密碼學(xué)中的可證明安全性第3章幾類語(yǔ)義安全的公鑰密碼體制

      （2） (M,n)≠1。先看(M,n)=1的含義，由于n=pq，所以(M,n)=1意味著M不是p的倍數(shù)也不是q的倍數(shù)。因此(M,n)≠1意味著M是p的倍數(shù)或q的倍數(shù)，不妨設(shè)M=tp，其中t為正整數(shù)。此時(shí)必有(M,q)=1，否則M也是q的倍數(shù)，從而是pq的倍數(shù)，與M由(M,q)=1及歐拉定理得Mφ(q)≡1 mod q，所以Mkφ(q)≡1 mod q，Mkφ(q)φ(p)≡1 mod q，Mkφ(n)≡1 mod q，因此存在一個(gè)整數(shù)r，使得Mkφ(n)=1+rq，兩邊同乘以M=tp得Mkφ(n)+1=M+rtpq=M+rtn，即Mkφ(n)+1≡M mod n，所以CTd mod n≡M。 （證畢） 如果消息M是Z*n中均勻隨機(jī)的，用公開(kāi)鑰(n,e)對(duì)M加密，則敵手不能恢復(fù)M。然而如果敵手發(fā)起選擇密文攻擊，以上性質(zhì)不再成立。比如敵手截獲密文CT≡Me mod n后，選擇隨機(jī)數(shù)r←RZ*n，計(jì)算密文CT′≡re·CT mod n，將CT′給挑戰(zhàn)者，獲得CT′的明文M′后，可由M≡M′r－1 mod n恢復(fù)M，這是因?yàn)?M′r－1≡CT′dr－1≡reMedr－1≡redMedr－1≡rMr－1≡M mod n 為使RSA加密方案可抵抗敵手的選擇明文攻擊和選擇密文攻擊，需對(duì)其加以修改。

        3.1.2RSA問(wèn)題和RSA假設(shè) RSA問(wèn)題: 已知大整數(shù)n,e,y∈Z�硁，滿足1RSA假定: 沒(méi)有概率多項(xiàng)式時(shí)間的算法解決RSA問(wèn)題。         3.1.3選擇明文安全的RSA加密 設(shè)GenRSA是RSA加密方案的密鑰產(chǎn)生算法，它的輸入為，輸出為模數(shù)n（為2個(gè)比特素?cái)?shù)的乘積）、整數(shù)e、d滿足ed≡1 mod φ(n)。又設(shè)H:0,12→0,1��()是一個(gè)哈希函數(shù)，其中��()是一個(gè)任意的多項(xiàng)式。 加密方案Π（稱為RSA�睠PA方案）如下: (1) 密鑰產(chǎn)生過(guò)程: KeyGen(): n,e,d←GenRSA(); pk=(n,e),sk=n,d. (2) 加密過(guò)程（其中M∈0,1��()）: pk(M): r←RZ*n; 輸出re mod n,H(r)�軲. (3) 解密過(guò)程: skC1,C2: r=Cd1 mod n; 輸出H(r)�軨2. 解密過(guò)程的正確性顯然。 在對(duì)方案進(jìn)行安全性分析時(shí)，將其中的哈希函數(shù)視為隨機(jī)諭言機(jī)。隨機(jī)諭言機(jī)（random oracle）是一個(gè)魔盒，對(duì)用戶（包括敵手）來(lái)說(shuō)，魔盒內(nèi)部的工作原理及狀態(tài)都是未知的。用戶能夠與這個(gè)魔盒交互，方式是向魔盒輸入一個(gè)比特串x，魔盒輸出比特串y（對(duì)用戶來(lái)說(shuō)y是均勻分布的）。

        這一過(guò)程稱為用戶向隨機(jī)諭言機(jī)的詢問(wèn)。 因?yàn)檫@種哈希函數(shù)工作原理及內(nèi)部狀態(tài)是未知的，因此不能用通常的公開(kāi)哈希函數(shù)。在安全性的歸約證明中（見(jiàn)圖1��7），敵手需要哈希函數(shù)值時(shí)，只能由敵手為他產(chǎn)生。之所以以這種方式使用哈希函數(shù)，是因?yàn)橐�把欲攻擊的困難問(wèn)題嵌入到哈希函數(shù)值中。這種安全性稱為隨機(jī)諭言機(jī)模型下的。如果不把哈希函數(shù)當(dāng)作隨機(jī)諭言機(jī)，則安全性稱為標(biāo)準(zhǔn)模型下的，如3.2節(jié)的Paillier公鑰密碼系統(tǒng)和3.3節(jié)的Cramer�睸houp密碼系統(tǒng)。 定理3��1設(shè)H是一個(gè)隨機(jī)諭言機(jī)，如果與GenRSA相關(guān)的RSA問(wèn)題是困難的，則RSA�睠PA方案Π是IND�睠PA安全的。 具體來(lái)說(shuō)，假設(shè)存在一個(gè)IND�睠PA敵手以()的優(yōu)勢(shì)攻破RSA�睠PA方案Π，那么一定存在一個(gè)敵手至少以 AdvRSA()≥2() 的優(yōu)勢(shì)解決RSA問(wèn)題。 證明: Π的IND�睠PA游戲如下。 ExpRSA�睠PAΠ,() n,e,d←GenRSA(); pk=(n,e),sk=n,d; H←RH:0,12→0,1��(); M0,M1←sk(·),H(·)(pk)，其中M0=M1=��(); β←R0,1,r←RZ*n,C��=re mod n,H(r)�軲β; β′←sk,≠C��(·),H(·)(pk,C��); 如果β′=β，則返回1；否則返回0. 其中H:0,12→0,1��()表示0,12到0,1��()的哈希函數(shù)族,sk,≠C��(·)表示敵手不能對(duì)C�吃L問(wèn)sk(·)。敵手的優(yōu)勢(shì)定義為安全參數(shù)的函數(shù): AdvRSA�睠PAΠ,()=PrExpRSA�睠PAΠ,()=1－12 下面證明RSA�睠PA方案可歸約到RSA假設(shè)。 敵手已知(n,e,c^1)，以（攻擊RSA�睠PA方案）作為子程序，進(jìn)行如下過(guò)程（圖3��1），目標(biāo)是計(jì)算r^≡(c^1)1/e mod n。 圖3��1RSA�睠PA方案到RSA的歸約

     （1） 選取一個(gè)隨機(jī)串h^←R{0,1}��()，作為對(duì)H(r^)的猜測(cè)值（但是實(shí)際上并不知道r^）。將公開(kāi)鑰(n,e)給。

     （2） H詢問(wèn): 建立一個(gè)表Hlist(初始為空)，元素類型xi,hi，在任何時(shí)候都能發(fā)出對(duì)Hlist的詢問(wèn)，做如下應(yīng)答（設(shè)詢問(wèn)為x）: �r 如果x已經(jīng)在Hlist，則以x,h中的h應(yīng)答。 �r 如果xe≡c^1 mod n，以h^應(yīng)答，將(x,h^)存入表中，并記下r^=x。 �r 否則隨機(jī)選擇h←R{0,1}��()，以h應(yīng)答，并將(x,h)存入表中。

     （3） 挑戰(zhàn)。輸出兩個(gè)要挑戰(zhàn)的消息M0和M1，隨機(jī)選擇β←R{0,1}，并令c^2=h^�軲β，將c^1,c^2給作為密文。

     （4） 在執(zhí)行結(jié)束后（在輸出其猜測(cè)β′之后），輸出第（2）步記下的r^=x。 設(shè)表示事件: 在模擬中發(fā)出H(r^)詢問(wèn)，即H(r^)出現(xiàn)在Hlist中。 斷言3��1在以上模擬過(guò)程中，的模擬是完備的。 證明： 在以上模擬中，的視圖與其在真實(shí)攻擊中的視圖是同分布的。這是因?yàn)?(1) 的H詢問(wèn)中的每一個(gè)都是用隨機(jī)值來(lái)回答的。而在對(duì)Π的真實(shí)攻擊中，得到的是H的函數(shù)值，由于假定H是隨機(jī)諭言機(jī)，所以得到的H的函數(shù)值是均勻的。 (2) 對(duì)來(lái)說(shuō)，h^�軲β為h^對(duì)Mβ做一次一密加密。由h^的隨機(jī)性，h^�軲β對(duì)來(lái)說(shuō)是隨機(jī)的。 所以兩種視圖不可區(qū)分。 （斷言3��1證畢） 斷言3��2在上述模擬攻擊中Pr≥2。 證明: 顯然有PrExpRSA�睠PAΠ,()=1=12。又由在真實(shí)攻擊中的定義知的優(yōu)勢(shì)大于等于，得在模擬攻擊中的優(yōu)勢(shì)也為 Pr［ExpRSA�睠PAΠ,()=1］－12≥ PrExpRSA�睠PAΠ,()=1=PrExpRSA�睠PAΠ,()=1|Pr +PrExpRSA�睠PAΠ,()=1|Pr ≤PrExpRSA�睠PAΠ,()=1|Pr+Pr =12Pr+Pr=12(1－Pr)+Pr =12+12Pr 又知: PrExpRSA�睠PAΠ,()=1≥PrExpRSA�睠PAΠ,()=1Pr =12(1－Pr) =12－12Pr 所以≤PrExpCPAΠ,()=1－12≤12Pr，即模擬攻擊中Pr≥2。 （斷言3��2證畢） 由以上兩個(gè)斷言，在上述模擬過(guò)程中r^以至少2的概率出現(xiàn)在Hlist。若發(fā)生，則在第（2）步可找到x滿足xe=c^1 mod n，即x≡r^≡(c^1)1/e mod n。所以成功的概率與發(fā)生的概率相同。 （定理3��1證畢） 定理3��1已證明Π是IND�睠PA安全的，然而它不是IND�睠CA安全的。敵手已知密文CT=C1,C2，構(gòu)造CT′=C1,C2�軲′，給解密諭言機(jī)，收到解密結(jié)果為M″=M�軲′，再由M″�軲′即獲得CT對(duì)應(yīng)的明文M。

      3.1.4選擇密文安全的RSA加密 因?yàn)檫x擇密文安全的單鑰加密方案的構(gòu)造較容易，本節(jié)利用選擇密文安全的單鑰加密方案構(gòu)造選擇密文安全的公鑰加密方案。 單鑰加密方案Π=(PrivGen,Enc,Dec)的選擇密文安全性由以下IND�睠CA游戲來(lái)刻畫。 ExpPriv�睠CAΠ,()： kpriv←PrivGen(); M0,M1←Enckpriv(·),Deckpriv(·),其中M0=M1=��(); β←R0,1,C��=Enckpriv(Mβ); β′←Enckpriv(·),Deckpriv,≠C��(·)(C��); 如果β′=β，則返回1；否則返回0. 其中Deckpriv,≠C��(·)表示敵手不能對(duì)C�吃L問(wèn)Deckpriv(·)。敵手的優(yōu)勢(shì)可定義為安全參數(shù)的函數(shù): AdvPriv�睠CAΠ,()=PrExpPriv�睠CAΠ,()=1－12 單鑰加密方案Π的安全性定義與定義2��2、定義2��6、定義2��7類似。 設(shè)GenRSA及H如前，Π=(PrivGen,Enc,Dec)是一個(gè)密鑰長(zhǎng)度為，消息長(zhǎng)度為��()的IND�睠CA安全的單鑰加密方案。 選擇密文安全的RSA加密方案Π′=(KeyGen,,)（稱為RSA�睠CA方案）構(gòu)造如下。

       (1) 密鑰產(chǎn)生過(guò)程: KeyGen(): n,e,d←GenRSA(); pk=(n,e),sk=n,d.

       (2) 加密過(guò)程（其中M∈0,1��()）: pk(M): r←RZ*n; h=H(r); 輸出re mod n,Ench(M).

       (3) 解密過(guò)程: skC1,C2: r=Cd1 mod n; h=H(r); 輸出Dech(C2). 定理3��2設(shè)H是隨機(jī)諭言機(jī)，如果與GenRSA相關(guān)的RSA問(wèn)題是困難的，且Π是IND�睠CA安全的，則RSA�睠CA方案Π′是IND�睠CA安全的。 具體來(lái)說(shuō)，假設(shè)存在一個(gè)IND�睠CA敵手以()的優(yōu)勢(shì)攻破RSA�睠CA方案Π′，那么一定存在一個(gè)敵手至少以 AdvRSA()≥2() ……