乐趣区

关于安全: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

退出移动版