1.3 RSA公钥加密方案_功能型密码算法设计与分析-QQ阅读男生玄幻网

书名：功能型密码算法设计与分析
作者名：黄欣沂赖建昌
本章字数：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。为描述方便，不妨设加密消息的长度为ℓ。