RSA 加密的原理——为什么被公钥加密的可以被私钥解密

RSA 加密的原理——为什么被公钥加密的可以被私钥解密？
目录
一，RSA 数学理论基础

二，RSA 实现原理

三，RSA 加密的过程

四，参考文献

引言
在密码学最开始，都是使用的普通加密模式

A 用加密规则加密了字符串 m 然后发给 B

B 用 A 的加密规则来解密，得到原始信息 m

在这个过程中 A 必须把自己的加密规则告诉 B，否则 B 无法解密这段密文，但是如果把加密规则也告诉 B，在传递密钥的过程中，可能就会被拦截获取，这就是最大的问题。

所以，后来又 3 位数学家提供了一种算法，实现非对称加密，后来算法也以他们三个的首字母命名，R（Rivest）S（Shamir ）A（Adleman ）算法。

最开始，我一直理解不了为什么公钥加密的可以被私钥解密，一直停留在使用层面，直到今天看到一篇博客，才解决了心中的疑惑。

一，RSA 必备数学理论基础
要理解整个 rsa 的流程，需要以下数学基础

1，互质关系
两个正整数，除 1 以外，再没有别的公因子。 比如 2 和 3， 2 和 9。

2，欧拉函数
任意给定正整数 n，请问在小于等于 n 的正整数之中，有多少个与 n 构成互质关系？（比如，在 1 到 8 之中，有多少个数与 8 构成互质关系？）

计算上面这个多少个的函数就被成为欧拉函数，以 φ(n)表示。在 1 到 8 之中，与 8 形成互质关系的是 1、3、5、7，所以 φ(n) = 4。

3，欧拉定理
由上面的欧拉函数可以经过一系列的推导，得到欧拉定理

如果两个正整数 a 和 n 互质，则 n 的欧拉函数 φ(n) 可以让下面的等式成立：

4，特殊情况——费马小定理
欧拉定理的特殊情况，当第二个数 n 为质数的情况。

假设正整数 a 与质数 p 互质，因为质数 p 的 φ(p)等于 p-1，

5，模反元素
如果两个正整数 a 和 n 互质，那么一定可以找到整数 b，使得 ab-1 被 n 整除，或者说 ab 被 n 除的余数是 1。

比如 a = 3 ,n = 5,则一定有（a*b）%n =1 ,即 3b -1 = 5y,即一定存在一个数 2，可以满足上式。

6,快速幂取模计算
如果有两个大数 a,b，a^b 可能是一个计算机无法表示的大数，则(a^b)%c 的值如何计算？

这里可以使用快速幂取模算法。

java 代码如下：

/**

• 快速幂取模 计算 (a^b) %c
• @param a
• @param b
• @param c
• @return 计算结果
  */
  private static int quick(int a,int b,int c) {
  int ans=1; //记录结果
  a=a%c; //预处理，使得 a 处于 c 的数据范围之下
  while(b!=0)
  {
  if((b&1)==1){ //1 即是 0000000000000001，判断个位是否是 1.如果 b 的二进制位是 1，那么我们的结果是要参与运算的
  ans=(ans*a)%c;
  }
  b>>=1; //二进制的移位操作，相当于每次除以 2，用二进制看，就是我们不断的遍历 b 的二进制位
  a=(a*a)%c; //不断的加倍
  }
  return ans;
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  参考了文章

https://blog.csdn.net/ltyqljhwcm/article/details/53043646

二，RSA 实现原理
第一步，选择两个不等质数 p,q（实际密钥一般为 1024 位或 2048 位）
这里我们选择 61 和 53。

第二步，计算乘积 n ####
n = p*q = 3233 (二进制 110010100001，只有 12 位)

第三步，计算 n 的欧拉函数 φ(n)
φ(n) = φ(p)*φ(q)= (p-1)(q-1) = 3120 。一个质数 p 的欧拉函数等于 p-1

第四步，随机选择一个整数 e，条件是 1< e < φ(n)，且 e 与 φ(n) 互质。
取 e = 17 (实际应用中，常常选择 65537)。

第五步，计算 e 对于 φ(n)的模反元素 d。
即找出一个 d 满足 ed 互质，且对于 φ(n) 取模为 1 ，即 ed = 1 (mod φ(n))。

即 ed -1 = kφ(n) ，带入上面已知条件：

17d -1 = k3120 即 17x +3120y = 1 (据说可以使用 扩展欧几里得算法求解)

这里直接给出答案 d = 2753。

第六步，将 n 和 e 封装成公钥，n 和 d 封装成私钥。
代入本次的推导过程中的数字，n = 3233,e = 17, d=2753。公钥为（3233，17），私钥为（3233，2723）。

加密使用 （3233，17），解密使用（3233，2723）。

第七步，分析，私钥的获取
由六可以看出来，公钥和私钥的区别其实只是 d，也就是说 d 的推导是否可以在已知 n，e 的情况下推导出来。

由第五步，要得出 d,已知 n,e。需要 φ(n)。

由第三部，要得出 φ(n)，需要 p，q。

而已知 n=p*q。而 n 已知，只需要分解 n 因子即可。

结论：只要 n 可以被分解，公私玥加密即可被破解。

第八步，n 可以被分解吗？
在本例中，3233 可以很快被破解，但是实际应用中，两个大质数的积是不容易被分解出来的

例如：

1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413

是以下两个质数的乘积：

a:

33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489

b:

36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917

人类已经分解的最大整数（232 个十进制位，768 个二进制位）。比它更大的因数分解，还没有被报道过，因此目前被破解的最长 RSA 密钥就是 768 位。而 RSA 加密一般使用 1024 位或者 2048 位，基本可以理解为不可破解

三，RSA 加密的过程
1，公钥（n,e）加密
所有字符串都可以使用 ascil 码/unicode 值来表示，假设一个字符 m = a，ascii 码为 65,需要满足 m < n 对他进行加密。

m^e ≡ c (mod n),c 为加密字符串

n = 3233,e = 17。 上式可以表示为： (65^17)%3233 = c ,c = 2790。

2,私钥（n,d）解密
(n,d) = (3233,2723) 。在拿到 c = 2790 之后，进行以下操作：

c^d ≡ m (mod n) 即可得到 m 。

推导,m = (2790^2723) %3233 ，在这里使用 必备知识六中的快速幂取模，可以轻松得到答案，m = 65。

3，证明，
略略略略略略略略略略略略略略略略略略略略略略略略略略略略略略略略略略略略略略略。

四，参考文献
1，http://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html

2，http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html

3，https://blog.csdn.net/ltyqljhwcm/article/details/53043646

作者：不会汪汪的猫咪
来源：CSDN
原文：https://blog.csdn.net/doujinlong1/article/details/82051986
版权声明：本文为博主原创文章，转载请附上博文链接！