注：以下内容参考《新编密码学》范九伦 张雪锋 侯红霞 编著
第7章 公钥密码
7.1 公钥密码体制的基本原理
7.1.1 公钥密码的基本思想
传统对称密码系统面临密钥管理的难题：通信双方必须共享一个秘密密钥，而安全地分配这个密钥非常困难。1976年，W. Diffie和M. Hellman在论文《密码学的新方向》中提出了公钥密码体制的新思想，将密钥分为两部分：公开密钥（公钥）和私有密钥（私钥），分别用于加密和解密。公钥可以公开发布，私钥由持有者秘密保存。
公钥密码体制又称双钥密码体制或非对称密码体制；传统密码体制称为单钥密码体制或对称密码体制。
公钥密码体制的基本流程（图7-1）：
发送方Alice用接收方Bob的公钥pk加密消息，得到密文并发送
接收方Bob用自己的私钥sk解密，恢复明文
7.1.2 公钥密码算法满足的要求
一个实际可用的公钥密码体制(M,C,K,E,D)需满足：
对每个密钥对k=(pk,sk)，存在加密变换Epk:M→C和解密变换Dsk:C→M，使得Dsk[Epk[m]]=m。
Epk和Dsk都是多项式时间可计算的，但从pk推出sk在计算上不可行。
公钥密码体制的核心是陷门单向函数：一个可逆函数f(x)，正向计算容易，逆向计算困难（除非知道陷门信息）。
可行的公钥密码算法应满足：
产生密钥对容易
用公钥加密容易
用私钥解密容易
由密文和公钥恢复明文不可行，且由公钥推出私钥不可行
7.2 RSA算法
RSA算法由R. Rivest、A. Shamir和L. Adleman于1978年提出，基于大数分解问题：计算两个大素数的乘积容易，但分解该乘积非常困难。RSA是应用最广泛的公钥密码体制。
7.2.1 RSA算法的描述
密钥生成：
选取两个大素数p和q（长度相近，至少100位十进制数字）
计算n=p×q，φ(n)=(p−1)(q−1)
选取整数e（1<e<φ(n)，gcd(e,φ(n))=1）
计算d=e^(−1) mod φ(n)（用扩展欧几里得算法）
公钥：(n,e)，私钥：d（p,q可销毁但绝不能泄露）
加解密过程：
加密：将明文分成数值小于n的分组m，计算c=m^e mod n
解密：m=c^d mod n
正确性证明：基于欧拉定理a^φ(n)≡1(modn)（当gcd(a,n)=1），可证明m^(ed)≡m(modn)。
7.2.2 RSA算法的安全性分析
RSA的安全性基于大数分解的困难性。随着分解算法的进步，RSA模数长度需不断增加。目前1024~2048比特模数的RSA仍被认为是相对安全的。
常见攻击方法：
共用模数攻击：多个用户共用同一模数n但不同e是不安全的。若e1,e2互素，攻击者可由c₁1=m^e₁ mod n，c₂=m^e₂ mod n恢复m。存在r,s使re₁+se₂=1，则c₁^r×c₂^s≡m(mod n)。
低加密指数攻击：e太小时，若同一消息用多个不同模数加密（e=3，三个模数），可由中国剩余定理恢复m。若k>e(e+1)/2，可攻击线性相关的消息。对策：e足够大，并对短消息进行随机数填充。
中间相遇攻击：利用RSA的可乘性。若m=m₁×m₂，则c=m₁^e×m₂^e mod n。攻击者可预计算i^e并搜索，复杂度O(2^(l/2))。对短消息（如56位DES密钥）攻击可行。
7.2.3 RSA算法的参数选择
模数n的确定：
不能多用户共用模数
p,q应为强素数（p−1和p+1都有大素因子），防止p−1因子分解攻击
p与q之差不能太小（否则可通过n逼近分解），也不能太大（否则小素数试除可行）
p−1与q−1的最大公因子要小，防止迭代攻击
加密密钥e的选取：
gcd(e,φ(n))=1
e不能太小（防低加密指数攻击）
e在模φ(n)下的阶要足够大
解密密钥d的选取：
d不能太小（Wiener证明d<n⅓时可分解模数）
一般要求d不小于n½
7.3 ElGamal算法
ElGamal密码体制基于有限域上离散对数问题的困难性，由T. ElGamal于1985年提出。
7.3.1 离散对数问题
设p为素数，a是p的本原根，则对任意b∈{1,2,…,p−1}，存在唯一的x使b≡a^x(mod p)，称x=logab mod p为离散对数。正向计算容易，逆向计算（已知a,p,b求x）非常困难（当p足够大时）。
7.3.2 ElGamal算法的描述
密钥生成：
选择大素数p，Z*p的生成元g
选取随机数a（1≤a≤p−2），计算y=g^a mod p
公钥：(y,g,p)，私钥：a
加密：对明文m，随机选取k∈Zp−1，计算
c1=g^k mod p,c2=m⋅y^k mod p
密文c=(c1,c2)，长度是明文的两倍。
解密：
m=c2⋅(c₁^a)^(−1) mod p
特点：非确定性加密，同一明文多次加密可能得到不同密文。
7.3.3 ElGamal算法的安全性
安全性基于离散对数问题的困难性
要求p足够大（至少300位十进制），且p−1有大素因子
加密的不确定性增加了密码分析难度
若明文不属于g生成的子群，可能泄露信息。应确保所有明文都由g生成
注：以上内容的理解和计算，如果有任何错误，希望各位读者和大佬指出改正，非常感谢！！！
