RSA加密(二) 加密过程

上篇文章我们介绍了密码学的基础,相信你已经对密码学及相关的知识有所了解,如果还没有阅读过,可以点击这里查看👉 RSA加密(一) 密码学基础

这篇文章主要给大家讲解下RSA加密的过程,但在讲加密过程前我们需要了解几个数学公式。都很简单,相信大家看了就会明白,文中遇到有链接的地方,可先跳过不影响阅读。下面我们先来看看RSA加密的介绍。

RSA加密简介

本文开篇的这张图就是RSA加密的三位作者,RSA算法是由Rivest、Shamir和Adleman在1977年共同提出,他们当时正好都在麻省理工学院工作,RSA就是他们三人姓氏开头字母拼在一起组成的。

当年的照片,留心下他们的发际线对比😅

但其实在RSA算法提出的4年前的1973年,在英国政府通讯总部工作的数学家克利福德·柯克斯(Clifford Cocks)在一个内部文件中便提出了一个与之等效的算法,但该算法当时被列入机密,直到1997年才得到公开(稍微有一些些可惜了~)。

从上篇文章我们了解到,RSA加密算法是通过分解质因数的困难性来实现的。换言之,对一个极大整数做因数分解愈困难,RSA算法愈可靠。假如有人找到一种快速因数分解的算法的话,那么用RSA加密的信息的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA钥匙才可能被强力方式破解。到当前为止,世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长,用RSA加密的信息实际上是不能被破解的,正因为RSA加密的安全性,所以RSA加密算法在当今互联网信息传递中被广泛的使用。

可以毫不夸张的说:只要有计算机网络的地方就有RSA加密算法。

数学公式

前面说到要理解RSA加密需要先了解一些数论相关的知识,这里我总结了几个必要的公式,方便后面能够更好的理解加密过程。

1.互质关系

  1. 质数定义:除了1和它本身,不能被其它数整除的数。例如:2、3、5、7、11、13、17、19、23、29…
  2. 任意两个质数构成互质关系。例如5和7,除1之外没有其他数能够整除5和7。
  3. 质数A与不是它的倍数的数构成互质。例如5能和1、2、3、4、6、7、8、9、11构成互质关系。

2.欧拉函数

对于任意正整数n,欧拉函数就是计算比n小的数中与n互质的数有多少个,用φ(n)表示,例:

计算整数8的欧拉函数:与8形成互质关系的是1、3、5、7共四个数,所以 φ(8) = 4。

从上面互质关系中的第三条我们可以知道,当n是一个质数时,比n小的所有数都与n形成互质关系,所以有:

n是质数:φ(n) = n-1

根据中国剩余定理(又称孙子定理)我们可以得到:两个互质整数p、q乘积的欧拉函数为:

φ(pxq) = φ(p)φ(q) (即可分开计算再相乘)

所以当p、q都是质数的时候,根据上面的公式 φ(n)=n-1 我们可以得到:

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

我们知道上面这种情况的欧拉公式就够了,关于更多欧拉函数的相关知识我们可以查看👉这里

3.欧拉定理

介绍欧拉定理之前,先说下取余操作。大家都知道 5除4余1,在数学中表示为 5=1(mod4) ,因为在计算机中计算余数的符号为百分号%,所以下面公式统一用 5%4=1 这种既简洁又好理解的形式表示。

欧拉定理:若正整数a和n互质则有

$a^{φ(n)}$ % n=1

正如上面的式子,伟大的定理往往都相当简洁!关于欧拉定理如何证明,感兴趣的同学可以查看👉这里

另外与之相关的一个概念,若正整数a和n互质则存在整数b使得:

ab % n=1

b就叫做a的模反元素,那b就一定存在吗?欧拉定理我们可以写成:

a x $a^{φ(n)-1}$ % n=1

所以b=$a^{φ(n)-1}$时上式成立,故b必然存在。

对于后面的加解密过程,我们主要用到如下两个公式:

RSA加密、解密过程

生成公钥、私钥

1. 随机找出两个不相等的质数 p、q

这里方便起见我们取 p=5,q=11(实际应用中p和q越大越难破解)

2. 计算p、q的乘积 n = p x q

n = 5 x 11 = 55(n的二进制长度称为RSA加密的密钥长度,这里55表示成二进制是110111,长度只有6位,实际应用中为1024位或更高的2048位)

3. 计算n的欧拉函数φ(n),根据上面我们所推导的欧拉函数,得到:φ(n)=(p-1)(q-1)

φ(n) = 4 x 10 = 40

4. 随机选择一个整数e,条件是1< e < φ(n),且e与φ(n) 互质

e和40要互质,为了方便这里我们取 e = 3.( 实际应用中这里一般取65537 )

5. 计算e对于φ(n)的模反元素d

即 ed % φ(n)=1可以写成:3d = k40+1,当k=2时,我们得到d=27.

6. 将e和n封装作为公钥(e,n),d和n封装作为私钥(d,n),即:

公钥:(e=3,n=55)

私钥:(d=27,n=55)

加密

上面我们已经计算出了公钥和私钥,根据上篇文章中的非对称加密流程。发送发收到公钥后开始进行加密操作。

假设现在我们要发送一段消息m=4,公钥为 (e=3,n=55)

m必须是一个整数(可将发送的消息通过ASCII码转换成十进制),且m<n,这就导致RSA加密的内容长度受到了限制。

计算密文:c = $m^e$ % n

即密文c = $ 4^3$ % 55 = 64%55 = 9

发送方便将密文9,通过网络等途径发送给接收方。

解密

接收方收到密文c=9后,使用自己创建的私钥 (d=27,n=55) 进行解密操作。

计算原文:m = $c^d$ % n

即原文m = $9^{27}$ % 55 = 4 (简单推导见👉这里,也可通过编程验证)

于是接收方便得到了发送方想要发送的消息,整个加密和解密过程就结束了。

总结

可以看到RSA加密和解密的过程并不复杂,用到的公式也只有仅仅两个,但这里面还有一些问题等待着我们去探索,例如:

  • m<n,这就导致RSA加密的内容长度受到了限制,那如何加密发送一段很长的文本呢?
  • RSA在公钥和密文传输的过程中就真的很安全吗?
  • 为什么解密的时候原文:m 就等于 $c^d$ % n呢?

欢迎在留言区说出你的想法,我们将在下一篇文章中给大家带来解答。