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

       3.1語義安全的RSA加密方案3.1.1RSA加密算法 RSA算法是1978年由Rivest、Shamir和Adleman提出的一種用數(shù)論構(gòu)造的，也是迄今理論上*為成熟完善的公鑰密碼體制，該體制已得到廣泛的應(yīng)用。它作為陷門置換在1.3.1節(jié)中有過介紹，下面是算法的詳細描述。 設(shè)GenPrime是大素數(shù)產(chǎn)生算法。 密鑰產(chǎn)生過程: GenRSA(): p,q←GenPrime(); n=pq,φ(n)=(p－1)(q－1); 選e,滿足1計算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算法中解密過程的正確性。 證明: 由加密過程知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章幾類語義安全的公鑰密碼體制

      （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ù)。此時必有(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，因此存在一個整數(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中均勻隨機的，用公開鑰(n,e)對M加密，則敵手不能恢復(fù)M。然而如果敵手發(fā)起選擇密文攻擊，以上性質(zhì)不再成立。比如敵手截獲密文CT≡Me mod n后，選擇隨機數(shù)r←RZ*n，計算密文CT′≡re·CT mod n，將CT′給挑戰(zhàn)者，獲得CT′的明文M′后，可由M≡M′r－1 mod n恢復(fù)M，這是因為 M′r－1≡CT′dr－1≡reMedr－1≡redMedr－1≡rMr－1≡M mod n 為使RSA加密方案可抵抗敵手的選擇明文攻擊和選擇密文攻擊，需對其加以修改。

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

        這一過程稱為用戶向隨機諭言機的詢問。 因為這種哈希函數(shù)工作原理及內(nèi)部狀態(tài)是未知的，因此不能用通常的公開哈希函數(shù)。在安全性的歸約證明中（見圖1��7），敵手需要哈希函數(shù)值時，只能由敵手為他產(chǎn)生。之所以以這種方式使用哈希函數(shù)，是因為要把欲攻擊的困難問題嵌入到哈希函數(shù)值中。這種安全性稱為隨機諭言機模型下的。如果不把哈希函數(shù)當(dāng)作隨機諭言機，則安全性稱為標準模型下的，如3.2節(jié)的Paillier公鑰密碼系統(tǒng)和3.3節(jié)的Cramer�睸houp密碼系統(tǒng)。 定理3��1設(shè)H是一個隨機諭言機，如果與GenRSA相關(guān)的RSA問題是困難的，則RSA�睠PA方案Π是IND�睠PA安全的。 具體來說，假設(shè)存在一個IND�睠PA敵手以()的優(yōu)勢攻破RSA�睠PA方案Π，那么一定存在一個敵手至少以 AdvRSA()≥2() 的優(yōu)勢解決RSA問題。 證明: Π的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��(·)表示敵手不能對C�吃L問sk(·)。敵手的優(yōu)勢定義為安全參數(shù)的函數(shù): AdvRSA�睠PAΠ,()=PrExpRSA�睠PAΠ,()=1－12 下面證明RSA�睠PA方案可歸約到RSA假設(shè)。 敵手已知(n,e,c^1)，以（攻擊RSA�睠PA方案）作為子程序，進行如下過程（圖3��1），目標是計算r^≡(c^1)1/e mod n。 圖3��1RSA�睠PA方案到RSA的歸約

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

     （2） H詢問: 建立一個表Hlist(初始為空)，元素類型xi,hi，在任何時候都能發(fā)出對Hlist的詢問，做如下應(yīng)答（設(shè)詢問為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 否則隨機選擇h←R{0,1}��()，以h應(yīng)答，并將(x,h)存入表中。

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

     （4） 在執(zhí)行結(jié)束后（在輸出其猜測β′之后），輸出第（2）步記下的r^=x。 設(shè)表示事件: 在模擬中發(fā)出H(r^)詢問，即H(r^)出現(xiàn)在Hlist中。 斷言3��1在以上模擬過程中，的模擬是完備的。 證明： 在以上模擬中，的視圖與其在真實攻擊中的視圖是同分布的。這是因為 (1) 的H詢問中的每一個都是用隨機值來回答的。而在對Π的真實攻擊中，得到的是H的函數(shù)值，由于假定H是隨機諭言機，所以得到的H的函數(shù)值是均勻的。 (2) 對來說，h^�軲β為h^對Mβ做一次一密加密。由h^的隨機性，h^�軲β對來說是隨機的。 所以兩種視圖不可區(qū)分。 （斷言3��1證畢） 斷言3��2在上述模擬攻擊中Pr≥2。 證明: 顯然有PrExpRSA�睠PAΠ,()=1=12。又由在真實攻擊中的定義知的優(yōu)勢大于等于，得在模擬攻擊中的優(yōu)勢也為 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證畢） 由以上兩個斷言，在上述模擬過程中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�軲′，給解密諭言機，收到解密結(jié)果為M″=M�軲′，再由M″�軲′即獲得CT對應(yīng)的明文M。

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

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

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

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