RSA 加密算法是怎么回事？难懂吗？
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 −1 (mod λ ( n )) ，即 e d ≡ 1 (mod λ ( n ))。
至此，第一阶段完成。 在这一阶段， Step1.2 生成的 n 和 S tep1.4 生成的 e 组成了公钥：（n，e）；而 S tep1.2 生成的 n 和 S tep1.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 17 , 3233) = 2790.
原文 65，通过公钥加密得到密文 2790。 将其交给有私钥的人。
4. 解密
计算m = mod (c d , n) 得到原文。
密文为2790，则m = mod（2790 413 , 3233） = 65
密文为2790，通过私钥解密得到原文65。
以上就是RSA的整个运作过程。
RSA算法原理推导
为什么这个加密解密过程能够有效？为什么当 c = mod (m e ,n) 时，就一定有m = mod(c d , n)呢？
首先， 根据 S tep 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
根据S tep1.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 加密的信息，就可以认为在事实上是不能被破解的。
没想到吧，小学数学课上就学过的质数、余数、质因数分解竟然这么有用，居然就在生活中时时处处保护着我们的信息安全。
“众智汇” 愿景
尽职尽才，允公允能 —— 本社群不定期举行线上分享，组织群友分享知识、经验、资源，以达到 让我们每个人的职业生涯得到最大程度的发展 的目的 。
欢迎扫面下列二维码关注“悦思悦读”公众微信号
About The Author
bjmayor
程序员，码农，php,python,ios,android,go，产品经理，创业。