URAL 1141. RSA Attack RSA加密演算法

意甲冠军：给你e n c 并有m^e = c(mod n) 求 m

过程大致是

1.发送的信息是m

2.随机选择两个质数 p和q, n = q*p, n的欧拉函数值φ(n）= (p-1)*(q-1)这个须要证明 

3.选择一个与φ(n)互质的而且小于φ(n)的数e, 计算c = m^e(mod n)

4.发送c

5解密 求e的逆元d 逆元就是2个数乘一下在mod一个数等于1 这里就是e*d = 1(mod φ(n))

求逆元用扩展欧几里德或者直接求高速幂

6.计算c^d(mod n) 就是m

版权声明：本文博客原创文章，博客，未经同意，不得转载。

本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/4663333.html，如需转载请自行联系原作者