数论知识

  1. 互质：如果两个正整数，除了 1 以外没有其他的公因数，则他们互质。比如，14 和 15 互质。注意，两个数构成互质关系，他们不一定需要是质数，比如 7 和 9。

  2. 欧拉函数：用于计算任意正整数 n，在 <=n 的正整数中，与 n 互质的正整数个数。

  3. 欧拉定理：如果两个正整数 a 和 n 互质，则如下等式成立。

  4. 费马小定理：欧拉函数中的一个特殊情况，如果 n 是质数，而 a 不是 n 的倍数，此时 a 和 n 必然互质。因为n的欧拉函数值 = n-1

  5. 模反元素：如果两个正整数 a 和 n 互质，那么一定可以找到一个正整数 b，使得 ab - 1 被 n 整除。这个时候，b 就叫做 a 的 模反元素。

关键参数

(e,n)：公钥

(d,n)：私钥

p,q：n=p*q ，p和q都是两个大素数

c：密文

m：明文

n,e是公开的情况下，想要知道d的值，必须要将n分解计算出n的欧拉函数值，而n是两个大素数p，q的乘积，将其分解是困难的。

生成密钥

取两个大质数p,q，并计算他们的乘积n，一般要求n换算成二进制要大于2048位

则根据欧拉定理满足以下条件（欧拉函数）：

计算n的欧拉函数值

选择一个数e使得e与n的欧拉函数值互质，一般选择65537

计算e相对n的欧拉函数值的模反元素d，因为e与n的欧拉函数值互质，则根据模反元素的性质

根据扩展欧几里得算法，通过迭代求解即可解出d，随后即生成公钥(e,N)，私钥(d,N)

加解密的实现

加密：

m为要加密的信息，(e,n)组合起来为公钥，c和k分别为常数

解密：

m为要解密的信息，(d,n)组合起来为私钥，c和k分别为常数

两个公式可相互推导