RSA 学习笔记

2019-04-13 15:24发布

首先要知道名词 费马小定理 同余理论 模反元素(inverse of modules)
费马小定理 同余理论 网上都有解释,我解释一下 模反元素
模反元素:一个与模数n互质的整数a,如果一个整数x满足ax≡1(mod n) 则可称为x为a对模数n之模反元素。
在java里 用这个modInverse函数就可以得到x为a对模数n之模反元素。


首先, 找出三个数, p, q, r,
其中 p, q 是两个相异的质数, r 是与 (p-1)(q-1) 互质的数......
p, q, r 这三个数便是 private key

接著, 找出 m, 使得 rm == 1 mod (p-1)(q-1).....
这个 m 一定存在, 因为 r 与 (p-1)(q-1) 互质, 用辗转相除法就可以得到了.....
再来, 计算 n = pq.......
m, n 这两个数便是 public key

正常的做法是先找出 p q 这样 n 就知道了。
然后自己设置一个publickey m。
这样 p q m n都知道了,求r。

// rm == 1 mod (p-1)(q-1),求r。
用 privateKey = publicKey.modInverse((p-1)×(q-1));

这样p, q, r,m, n都求出来了,我就可以对数据进行加密解密了