一、数学原理
密文 = 明文^E mod N
明文 = 密文^D mod N
给定两个质数p q
计算方法如下：
1、求N
N = p * q
2、求中间数L， 是p-1和q-1的最小公倍数
L= （p-1， q-1）
3、选定一个正整数E （E是小于L，且E和L的最大公约数是1）
4、求正整数D, D满足 D*E mod L =1， 且D小于L
求D的方法
ed + ml =1 (e，l是已知变量 )
1、举例说明
设 p=13, q=17, 则N=13 * 17=221，L = 48，选定E=13，则 根据 13 * D mod 48 =1,求D。
13 * d + 48* m = 1
13 * d1 + 9 *m = 1, 其中 d1=d + 3m;
4 * d1 + 9 * m1 =1, 其中 m1 = d1 + m;
4 * d2 + m1 =1, 其中d2 = d1 +2m1;
得： m1 =1,d2 =0, 反推得到d=-11,m=3, 由于d是正整数，于是加上48，得到d的一个满足要求的解：37
假设明文是3
3^13 mod 221 =29
29^37 mod 221 = 3
2、公式及代码实现
e * d + l * m= 1
设d可以由函数f表示，d = f(e,l)
e * d + (l/e * e + l %e ) *m =1
e * d1 + (l % e) *m =1 ,其中 d1 = d + l/e * m
m = (1- e * d1)/(l%e) ,d = d1 - l/e * m
f(e, l ) = f(e % l, l % e) - l/e * (1- e * f(e%l , l%e))/ (l % e)
public static long cal(long l , long e) {
if(l ==1 || e ==1) return 1;
long d1 = cal(l %e, e%l);
return d1- l / e * ((1 - e * d1) / (l%e));
}
