RSA非对称加密

最近在跟我厂安全组斗智斗勇的过程中，突然对ssh使用的RSA加密算法产生了兴趣，以前就一直好奇为啥一段报文用公钥加密过后只能用密钥解密，今天正好顺道解决了

设两个质数为P,Q
N=P*Q
M=(P-1)*(Q-1)
E与M互质,与N组成公钥(E,N)
存在一自然数n使得M*n+1=E*D，D与N组成私钥(D,N)

目的就是使得报文X用公钥加密得到的Y只能由私钥来解开

X^E mod N=Y//加密过程
Y^D mod N=X//解密过程

下面给出一组例子：

int P = 7;
int Q = 11;
int N = 77;
int M = 60;
int E = 43;
int D = 7;

下面是演示加密、解密过程：

System.out.println(Math.pow(4,43)%77);//输出53
System.out.println(Math.pow(53,7)%77);//输出

安全性：

由于只把(43,77)公布出去，要想得到私钥D=7,唯一的办法就是因式分解N=77,将得到的每一个M*n+1除以D，要求能整除且得到的结果为一质数(私钥D)，时间复杂度O(n*N^2),n为尝试获得D的次数，不保证大小...因此想破解RSA极为不靠谱