不朽情缘小技巧

書名：功能型密碼算法設計與分析
作者名：黃欣沂賴建昌
本章字數： 1767字
更新時間： 2023-11-07 17:24:06

1.3 RSA公鑰加密方案

本節首先給出標準RSA加密方案，然后給出修改后的RSA加密方案，使其能夠抵抗選擇明文攻擊，記作RSA-CPA方案，并給出安全性分析。RSA加密算法由Ron Rivest、Adi Shamir和Leonard Adleman于1978年提出，方案的描述如下。

1.3.1 RSA加密方案

設GenPrime是大素數產生算法，λ為系統安全參數。

●SysGen：運行大素數產生算法得到兩個素數p,q←GenPrime(λ)，其中p和q秘密保存。

●KeyGen：輸入p，q，計算n=pq，φ(n)=(p-1)(q-1)，選取大整數1<e<φ(n)，使得gcd(φ(n),e)=1成立，其中φ(n)為n的歐拉函數。接著計算d，滿足d·e≡1modφ(n)，輸出公鑰(n,e)，私鑰(n,d)。

●Encrypt：輸入待加密的消息m，公鑰(n,e)，計算密文c≡memod n。

●Decrypt：輸入密文c，私鑰(n,d)，計算m≡cdmod n。

方案的正確性分析如下：由加密過程，可知c≡memod n，所以

cdmod n≡medmod n≡mkφ(n)+1mod n

分為下面兩種情況：

1）若m與n互素，則由歐拉定理：mφ(n)≡1mod n，mkφ(n)≡1mod n，mkφ(n)+1≡mmod n。即cdmod n≡m。

2）若gcd（m，n）≠1，注意到n=pq，則意味著m是p的倍數或q的倍數，不妨設m=tp，其中t為一正整數。此時必有gcd{m,q}=1，否則m也是q的倍數，從而是pq的倍數，與m＜n=pq矛盾。由gcd{m,q}=1及歐拉定理得mφ（q）≡1modq，所以mkφ（q）≡1modq，（mkφ（q））φ（p）≡1modq，mkφ（n）≡1modq，因此存在一個整數r，使得mkφ（n）=1+rq，兩邊同乘m=tp得，mkφ（n）+1=m+rtpq=m+rtn，即mkφ（n）+1≡mmod n，所以cdmod n≡m。

1.3.2 RSA-CPA方案描述

設GenPrime是大素數產生算法，λ為系統安全參數。

●SysGen：運行大素數產生算法得到兩個素數p,q←GenPrime(λ)，p,q秘密保存。

●KeyGen：輸入p，q，計算n=pq，φ(n)=(p-1)(q-1)，選取大整數1<e<φ(n)，使得(φ(n),e)=1成立。接著計算d，滿足d·e≡1modφ(n)，輸出公鑰(n,e)，私鑰(n,d)。

●Encrypt：輸入待加密的消息m，公鑰（n，e），選取隨機數，輸出密文CT=（C₁，C₂）≡（remod n，H（r）⊕m）。

●Decrypt：輸入密文CT，私鑰（n，d），計算r≡mod n，計算明文m=H（r）⊕C₂。

1.3.3 安全性分析

RSA-CPA方案的安全性基于RSA問題的難解性，我們首先給出RSA問題的定義。

RSA問題：已知大整數n，e，y∈，滿足q＜e＜φ（n）且gcd（φ（n），e）=1，計算mod n。

RSA困難性假設：沒有概率多項式時間的算法能夠解決RSA問題。

定理1.1 設H是一個隨機諭言機，如果RSA問題是難解的，那么RSA-CPA方案是IND-CPA安全的。

證明：假設在IND-CPA安全模型中，存在一個敵手A能以不可忽略的優勢（概率）ε攻破RSA-CPA方案，那么可以構造一個模擬算法B，通過與A交互以不可忽略的優勢（λ）≥2ε解決RSA問題。假設模擬算法B以一個RSA問題實例（n，e，y）為輸入，目標是計算mod n。為描述方便，不妨設加密消息的長度為?。