RSA加密算法

RSA加密算法非常有名，在计算机领域的应用非常广泛，几乎是一般用户在信息加密时的首选。

它是一种非对称加密演算法，名字来源于它的三个发明人——罗纳德·李维斯特（RonRivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）——名字的首字母缩写。

这三人在1977年一起提出了RSA算法，当时他们都在麻省理工学院工作。

虽然已经被发明了四十多年，然而至今世界上没有可靠的攻击它的方法。在技术瞬息万变的今天，这样的稳定性尤其难能可贵。

RSA为什么这么保险呢？当然和它的实现原理有关系，我们要了解RSA，就需要掌握它的理论基础。

作为加密算法，RSA的原理实际上就是一系列非常严格的数学推导过程。一说到数学可能有人又要头疼了，数学啊，很难吧？

其实，并不难。

RSA算法背后的数学概念

最近笔者给一位小学生检查数学作业，由此得知他们们已经在学习下面这些概念：

余数：如果有两个整数a和b，a除以b不能除尽，那么a中不能除尽的部分就是。比如11除以5，商是2，余数是1。

 

MOD函数：求余数的函数，mod(11,5)就是对11除以5求余数。

约数：又称因数，如果有两个整数a和b，a除以b能除尽，那么b就是a的约数，比如，2÷1=2，2÷2=1，2的约数就是1和2。

 

因数分解：把一个正整数写成几个约数的乘积。

 

公约数：有几个整数，它们都有一个相同的约数，那么这个约数就是这几个整数的公约数，比如2的约数是1和2，4的约数是1、2和4，6的约数是1、2、3、6，2、4和6的公约数就是1和2。

 

质数：一个大于1的自然数，除了1和它本身，再没有别的约数了，那么这个数就是质数。比如2，它大于1，只有1和2两个约数，它就是质数。

 

互质：两个整数，只有1一个公约数，这两个整数就是互质整数。比如2和3，它们的公约数只有1，它们就是互质的。

有了这些概念做基础，其实就已经可以看懂RSA算法的推导过程了。现在我们一起来看一看吧——

RSA算法原理

RSA算法包括四个阶段：密钥生成，密钥发布，加密和解密。前两个阶段属于加密算法准备，后两个阶段则属于加密算法使用。

下面我们分别来看这四个阶段：

 

1. 密钥生成

 

这里说的密钥又分为公钥和私钥两个部分，各对应两个数字，公钥为 n 和 e，私钥为 n 和 d。

因为公钥和私钥的 n 是同一个 n，因此，其实RSA的密钥总共涉及三个数字：n，e 和 d，它们都是非常非常大的正整数。

它们是通过以下步骤生成的：

 

Step1.1：选择两个质数 p 和 q. 

 

Step1.2：计算出 p 和 q 的积 n：n = p·q。

 

Step1.3：计算n的卡迈克尔函数λ(n)。

卡迈克尔函数，n 的卡迈克尔函数计作 λ(n)，定义为：对任意正整数 n，它的卡迈克尔函数λ(n) 是满足如下条件的最小的正整数：这个正整数 m 使得 a^m ≡ 1 (mod n)，其中 a 是 1 到 m 之间任意一个与 m 互质的整数。

这里的 ≡ 是同余符号——同余是数论中的一种等价关系，当两个整数除以同一个正整数，若得相同余数，则二整数同余。

所以式子 a^m ≡ 1 (mod n) 表示：a的m次幂除以n之后的余数为1，又可以称作：a^m 和1对于模n同余。

在这里还需要了解另一个函数：

欧拉函数，n的欧拉函数计作φ(n)，定义为：对任意正整数n，它的欧拉函数就是在小于或等于n的正整数里与n互质的数字的个数。

φ(n) 分不同情况来看：

   a） 如果n=1，那么φ(1)=1

   b） 如果n是质数，那么φ(n)=n-1

   c）如果n是一个质数p的k次方，即n=p^k，那么φ(n)=φ(p^k)= p^k- p^k-1

   d）如果n是两个互质的数p和q的乘积，那么φ(n)=φ(p) ⋅φ(q)

当 n 为1、2、4、奇质数的次幂、奇质数的次幂的两倍时，λ(n) 为 φ(n)，当 n 为2、4以外的2的次幂时，λ(n) 为 φ(n) 的一半： 

因为：

（i） 欧拉函数的情况 c）；

（ii）正整数 n 可写作它的质因数的积。

因此对于任意正整数n，它的卡迈克尔函数 λ(n )是 n 的质因数的卡迈克尔函数的最小公倍数，记作： 其中：p1 < p2 <... < pk 是质数，而 r1, r2,..., rk 是正整数。

还有，因为 n 为两个质数 p 和 q 的积，所以 n 的卡迈克尔函数等于 p 和 q 的卡迈克尔函数的最小公倍数，计作 λ(n) = lcm(λ(p), λ(q)) 。

又因为根据 欧拉函数的情况 c）可得：λ(p) = φ(p) = p – 1且 λ(q) = φ(q) = q − 1。因此，λ(n) = lcm(p − 1, q − 1)。

 

也就是说，这一步要计算 p-1 和 q-1 的最小公倍数。

 

Step1.4：选择一个正整数e，满足：1 < e < λ(n) ，并且 e 和 λ(n) 互质。

 

Step1.5：确定 e 的模反元素 d。

模反元素：如果有两个互质的正整数a和n，那一定可以找到一个整数b，能让 ab - 1 能被 n 整除，也就是说ab除以n的余数是1，记作 ab ≡ 1(mod n)。数学家们已经利用欧拉定理也能证明模反元素的存在。

也就是说 d 满足：d ≡ e⁻¹ (mod λ(n)) ，即 ed ≡ 1 (mod λ(n))。

 

至此，第一阶段完成。在这一阶段，Step1.2 生成的 n 和 Step1.4 生成的 e 组成了公钥：（n，e）；而 Step1.2 生成的 n 和 Step1.5 生成的 d 组成了私钥：（n，d）。

 

2. 密钥发布

 

密钥生成之后，公钥被公之于众，任何人都可以获取并使用，而私钥则被保留在特定的，被允许解读加密信息的人手中。

 

3. 加密

 

加密只需要用到公钥（n，e），当人们想要用RSA算法加密一段信息时，需要按以下步骤进行：

 

Step 3.1：将信息按照约定的方法转化为一个正整数m，满足 0 ≤ m < n 。

此处的将信息转化为数字的方法也是公开的，如果信息实在太多也可以考虑分段，每段分别转化为一个大于等于0，小于n的正整数。

 

Step 3.2：计算c = mod（m^e， n），c就是加密后的密文。

 

加密完成，将生成的密文传递给要送达的人。

 

4. 解密

 

收到密文的人，如果手中有私钥（n，d），就可以开始解密了，方法如下：

 

Step 4.1：计算 m = mod（c^d， n），m就是原本的原文。

RSA加密全过程实例 

下面我们来看一个例子：

 

1.  密钥生成

1.1：我们选择 p = 61 和 q = 53.

 

1.2：计算n = 61 × 53 =3233.

 

1.3：计算λ(n) = λ(3233) = Icm(60, 52) = 780.

 

1.4： 选择 e，需满足 1 < e <780，且 e 和780互质。

我们选择 e = 17.

 

1.5：求e的模反元素d，使得 ed ≡ 1 mod λ(n)，也就是17d ≡  1 mod 780.

求 17d = 780 h + 1 ，其中h为正整数。

求得d = 413，验算：413 ×17  =  780 × 9 + 1，d成立。

 

我们生成了公钥 (n = 3233, e =17)，和私钥 (n = 3233, d =413).

 

2.    密钥发布

公布公钥，将密钥交给我们要通信的朋友。

 

3.    加密

 

原文为m（正整数），计算：c = mod(m^e, n). 

 

假设m = 65， 则c = mod(65¹⁷, 3233) = 2790.

 

原文 65，通过公钥加密得到密文 2790。将其交给有私钥的人。

 

4.    解密

 

计算m = mod (c^d, n) 得到原文。

 

密文为2790，则m = mod（2790⁴¹³, 3233） = 65

密文为2790，通过私钥解密得到原文65。 

以上就是RSA的整个运作过程。

RSA算法原理推导

为什么这个加密解密过程能够有效？为什么当 c = mod (m^e,n) 时，就一定有m = mod(c^d, n)呢？

首先， 根据 Step 3.2 可知：m^e  ≡ c (mod n)，根据同余关系保持基本运算的性质，有 c^d  ≡ (m^e)^d  = m^ed  (mod n)，也就是 c^d  ≡ m^ed  (mod n)

 

其次，因为 ed ≡ 1 (mod λ(n))，即 ed  - 1 ≡ 0 (mod λ(n))，也就是说ed  - 1 可以被λ(n) 整除。

又因为 λ(n) = lcm(p − 1, q − 1) ，也就是 λ(n) 可以被 p -1 和 q-1 整除，因此有 ed - 1 = h(p -1) = k(q-1)， h和k都是非负整数。

 

于是有：m^ed = m⋅m ^(ed-1)= m (m ^(p-1) ) ^h  

 

根据Step1.3 中 φ(p) = p – 1，m^ed = m (m ^(p-1) ) ^h  = m (m^φ (p) ) ^h

因为 p 是质数，所以如果 m 要么是 p 的倍数，要么与 p 互质——

 

i）若 m 是 p 的倍数，则 m^ed 也是 p 的倍数， m^ed ≡ 0 ≡ m (mod p) ；

ii）若 m 与 p 互质，根据欧拉定理则有 m^φ(p) ≡ 1 (mod p)

欧拉定理：两个互质的正整数 a 和 b， a^φ(b) ≡1 (mod b)。

于是，有 m^ed = m · m^φ (p) ≡ m (mod p)，即 m^ed  ≡ m  (mod p)

综合i）和ii）有：m^ed  ≡ m  (mod p) .

 

同理，可证明 m^ed  ≡ m  (mod q).

 

根据中国剩余定理，m^ed  ≡ m  (mod p) 和 m^ed  ≡ m  (mod q) 同时成立，等同于 m^ed  ≡ m  (mod pq)  成立，又因为 pq = n，因此，我们得以证明：m^ed  ≡ m  (mod n)

 

然后，根据同余的传递性，有 c^d  ≡ m^ed ≡ m (mod n)。且已知 m < n，所以mod（c^d ， n）= m，这也就是为什么 Step 4.1 能够求出m的原因。

为什么RSA难于破解？

这件事我们不妨反过来想，如果我们要破解RSA加密文件，我们需要什么？

我们需要私钥，私钥包括两个部分：n 和 d，n 就是公钥中的 n，所以我们唯一需要知道的就是 d。

那么我们能不能自己把 d 求出来呢？理论上是可行的。

因为 ed ≡ 1 mod λ(n)，e 是已知的，且 λ(n) = lcm(p − 1, q − 1)，因此，我们只需要知道 p - 1 和 q - 1 就好了。

n = p·q，那么我们只要对 n 进行质因数分解，找到它的最大质因数就可以了。 

可是，实际操作起来，却不那么容易。

如果 p 和 q 很大，n 就会更大。而大整数的因数分解，是一件非常困难的事情。目前，除了暴力破解，还没有发现别的有效方法。

只有短的 RSA 钥匙才可能被暴力方式破解。迄今为止，世界上还没有任何可靠的攻击RSA算法的方式。

只要其钥匙的长度足够长，用 RSA 加密的信息，就可以认为在事实上是不能被破解的。

没想到吧，小学数学课上就学过的质数、余数、质因数分解竟然这么有用，居然就在生活中时时处处保护着我们的信息安全。

“众智汇”愿景

尽职尽才，允公允能 —— 本社群不定期举行线上分享，组织群友分享知识、经验、资源，以达到让我们每个人的职业生涯得到最大程度的发展的目的。

欢迎扫面下列二维码关注“悦思悦读”公众微信号