关于安全:RSA-算法基础之概念篇

一、RSA 算法

在加解密信息的过程中，应用的加密密钥（公钥）与解密密钥（私钥）不同，即：

1. 甲要传密信给乙，乙先依据某种算法得出本次与甲通信的公钥与私钥；
2. 乙将公钥传给甲（公钥能够让任何人晓得，即便泄露也没有任何关系）；
3. 甲应用乙给的公钥加密要发送的原文 m，将密文 c 发送给乙；
4. 乙应用本人的私钥解密密文 c，失去原文 m。

这种加密模式被称为“非对称加密算法”。从始至终，私钥始终都在信息接管方乙处，只有乙本人不泄露进来，私钥就没有泄露的可能。

二、质数与互质数

一个大于 1 的自然数，除了 1 和它自身外，不能被其余自然数整除（除 0 以外）的数称之为质数（素数）；否则称为合数 。

例如，15=3×5，所以 15 不是质数；13=13×1，以外不能为其它任何两个整数的乘积，所以 13 是一个质数；1 不是质数，也不是合数。

公约数只有 1 的两个数，叫做互质数 。判断或选取互质数的办法 / 定理有很多，如下所示：

1. 任意两个质数肯定形成互质数（如 3 与 11、53 与 61）；
2. 大数是质数的两个数肯定是互质数（如 97 与 88）；
3. 一个质数如果不能整除另一个合数，这两个数为互质数；即一个数是质数，另一个数只有不是前者的倍数，两者就形成互质关系（如 3 与 10、5 与 26）；
4. 1 和任何一个自然数在一起都是互质数；
5. 相邻的两个自然数是互质数（如 15 与 16）；
6. 相邻的两个奇数是互质数（如 49 与 51）

在 RSA 算法中，咱们通常应用以上第 1 条与第 2 条，即选取两个自身都是质数的数作为互质数，而以上第 2 条定理对于计算欧拉函数值有着踊跃作用。

三、模运算

模运算的定义如下： 让 m 去被 n 整除，用所得的余数作为后果，就叫做模运算 。

10 mod 3 = 1
26 mod 6 = 2
28 mod 2 = 0

四、同余

“≡”是数论中示意同余的符号，同余的定义如下：

给定一个正整数 m，如果两个整数 a 和 b 满足 a - b 能被 m 整除，即 (a-b) mod m = 0，那么就称整数 a 与 b 对模 m 同余，记作 a≡b(mod m)，同时可成立 a mod m=b。

同余与模运算是不同的：a≡b(mod m) 仅可推出 b=a mod m。

五、欧拉函数

欧拉函数自身须要一系列简单推导，本文仅介绍对意识 RSA 算法有帮忙的局部： 任意给定正整数 n，计算在小于等于 n 的正整数之中，有多少个与 n 形成互质关系？计算这个值的办法就叫做欧拉函数，以 φ(n) 示意 。

例如，在 1 到 8 之中，与 8 造成互质关系的是 1、3、5、7，所以 φ(n)=4。

在 RSA 算法中，须要明确欧拉函数对以下定理成立：

1. 如果 n 能够分解成两个互质的整数之积，即 n =p×q，则有：φ(n)=φ(pq)=φ(p)φ(q)；
2. 依据“大数是质数的两个数肯定是互质数”能够晓得：一个数如果是质数，则小于它的所有正整数与它都是互质数；所以如果一个数 p 是质数，则有：φ(p)=p-1

所以，如果咱们晓得一个数 n 能够合成为两个质数 p 和 q 的乘积，则有：

φ(n)=(p-1)(q-1)

六、欧拉定理与模反元素

欧拉函数的用途，在于欧拉定理。“欧拉定理”指的是：如果两个正整数 a 和 n 互质，则 n 的欧拉函数 φ(n) 能够让上面的等式成立：

a^φ(n) ≡ 1(mod n)

也就是说，a 的 φ(n) 次方被 n 除的余数为 1，模反元素的推导过程如下：

即， 如果两个正整数 a 和 n 互质，那么肯定能够找到整数 b，使得 ab- 1 被 n 整除，或者说 ab 被 n 除的余数是 1 。