RSA 加密算法是怎么回事？难懂吗？
source link: https://mp.weixin.qq.com/s/yl5NoVr6SMslc6U6cBlDAQ
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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 加密的信息，就可以认为在事实上是不能被破解的。
没想到吧，小学数学课上就学过的质数、余数、质因数分解竟然这么有用，居然就在生活中时时处处保护着我们的信息安全。
“众智汇” 愿景
尽职尽才，允公允能 —— 本社群不定期举行线上分享，组织群友分享知识、经验、资源，以达到 让我们每个人的职业生涯得到最大程度的发展 的目的 。
欢迎扫面下列二维码关注“悦思悦读”公众微信号
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK