RSA算法与保密协议

RSA算法与保密协议章凌豪信息传输中的保密问题通信双方约定一个密码加密？（公共秘密）公开加密的算法，但只有我自己知道如何解密那么这个密码如何传输？从直觉上讲，知道加密的方法，反过来做不就能解密了吗？不对称的加密、解密算法？A任意想一个三位数A告诉B这个数乘以91的乘积的末三位B将这个数乘以11123123×91=11193193×11=2123构造解密算法并不容易上例的原理：91×11=10011001乘以任何三位数，末三位都不变可以更大500000001=42269×11829在知道加密算法的前提下，构造解密算法也是不容易的这就是不对称性为了提高安全性，需要进一步增强这种不对称性RSA算法利用了一种非常犀利的不对称性：大数分解1997年由MIT的RonRivest、AdiShamir、LeonardAdleman提出预备知识：Euler-Fermat定理𝑎𝜑(𝑝)=1(𝑚𝑜𝑑𝑝)p、a是任意整数φp=1~p−1中与p互质的数的个数（包括1）显然若p是质数，有φp=p−1可以证明对于𝑛=𝑝𝑞𝑝、𝑞是质数，有𝜑𝑛=(𝑝−1)(𝑞−1)RSA算法的具体实现找两个大质数p、𝑞n=pqm=p−1q−1找一个比𝑚小且与𝑚互质的e明文𝑎(𝑎𝑛)密文𝑐=𝑎𝑒𝑚𝑜𝑑𝑛计算𝑐𝑑𝑚𝑜𝑑𝑛即得到𝑎mod𝑛p=13，𝑞=17𝑛=221，𝑚=192𝑎𝑚=1(𝑚𝑜𝑑𝑛)𝑎、𝑎193、𝑎385、𝑎577除以221同余c=𝑎11𝑚𝑜𝑑221计算𝑐35𝑚𝑜𝑑221=𝑎385𝑚𝑜𝑑221=𝑎(𝑚𝑜𝑑221)关键的d和e怎么来？𝑎𝑑𝑒=𝑎𝑚𝑜𝑑𝑛𝑎𝑚=1𝑚𝑜𝑑𝑛𝑎𝑚+1=𝑎(𝑚𝑜𝑑𝑛)𝑎2𝑚+1=𝑎𝑚𝑜𝑑𝑛…𝑑𝑒=1(𝑚𝑜𝑑𝑚)𝑑在比𝑚小的质数中选通过解同余方程得到𝑒𝑒=1111𝑑=1𝑚𝑜𝑑192一个解为𝑑=35但是其他人并不知道m而𝑚=𝑝−1𝑞−1而p、𝑞是两个大质数𝑛=pq也是一个大数公钥与私钥公钥对(𝑒,𝑛)私钥对𝑑,𝑛（拓展欧几里得算法）我生成公钥与私钥发布公钥任何人可以将消息用公钥加密后发给我我用私钥解密其他人只知道就要根据𝑑𝑒=1(𝑚𝑜𝑑𝑚)解出𝑑但是𝑚的值未知必须将𝑛分解成两个质数𝑝、𝑞之积（无高效算法）