注以下内容参考《新编密码学》范九伦 张雪锋 侯红霞 编著第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位十进制数字计算np×qφ(n)(p−1)(q−1)选取整数e1eφ(n)gcd⁡(e,φ(n))1计算de^(−1) mod φ(n)用扩展欧几里得算法公钥(n,e)私钥dp,q可销毁但绝不能泄露加解密过程加密将明文分成数值小于n的分组m计算cm^e mod n解密mc^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₁1m^e₁ mod nc₂m^e₂ mod n恢复m。存在r,s使re₁se₂1则c₁^r×c₂^s≡m(mod n)。低加密指数攻击e太小时若同一消息用多个不同模数加密e3三个模数可由中国剩余定理恢复m。若ke(e1)/2可攻击线性相关的消息。对策e足够大并对短消息进行随机数填充。中间相遇攻击利用RSA的可乘性。若mm₁×m₂则cm₁^e×m₂^e mod n。攻击者可预计算i^e并搜索复杂度O(2^(l/2))。对短消息如56位DES密钥攻击可行。7.2.3 RSA算法的参数选择模数n的确定不能多用户共用模数p,q应为强素数p−1和p1都有大素因子防止p−1因子分解攻击p与q之差不能太小否则可通过n逼近分解也不能太大否则小素数试除可行p−1与q−1的最大公因子要小防止迭代攻击加密密钥e的选取gcd⁡(e,φ(n))1e不能太小防低加密指数攻击e在模φ(n)下的阶要足够大解密密钥d的选取d不能太小Wiener证明dn⅓时可分解模数一般要求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)称xlog⁡ab mod p为离散对数。正向计算容易逆向计算已知a,p,b求x非常困难当p足够大时。7.3.2 ElGamal算法的描述密钥生成选择大素数pZ*p​的生成元g选取随机数a1≤a≤p−2计算yg^a mod p公钥(y,g,p)私钥a加密对明文m随机选取k∈Zp−1​计算c1g^k mod p,c2m⋅y^k mod p密文c(c1,c2)长度是明文的两倍。解密mc2⋅(c₁^a)^(−1) mod p特点非确定性加密同一明文多次加密可能得到不同密文。7.3.3 ElGamal算法的安全性安全性基于离散对数问题的困难性要求p足够大至少300位十进制且p−1有大素因子加密的不确定性增加了密码分析难度若明文不属于g生成的子群可能泄露信息。应确保所有明文都由g生成注以上内容的理解和计算如果有任何错误希望各位读者和大佬指出改正非常感谢