RSA加密原理：非对称加密的鼻祖

加密算法，RSA是一个绕不开的话题，因为RSA算法是目前最流行的公钥算法，既可以用于加密，也可以用于用户数字签名。 不仅应用于加密货币领域，在传统互联网领域也得到广泛应用。 它自提出以来已经经历了20多年的各种考验，被普遍认为是目前最好的公钥方案之一。 比特币使用的Sha256算法也是基于它。 了解RSA算法，相信你会对区块链有更深入的了解。

非对称加密

直到 20 世纪 70 年代，密码学都是基于对称密钥，即发送方使用特定密钥加密消息，接收方使用相同密钥解密。 加密是从消息到使用特定密钥加密消息的映射。 , 要解密密文，需要使用相同的密钥反转映射。

假设 Alice 想与 Bob 通信，他们必须共享相同的密钥，但如果 Alice 和 Bob 无法物理相遇，通常无法建立共享密钥，或者需要额外的通信开销，例如使用 Diffie-Hellman 密钥交换。

此外，如果爱丽丝要和很多人交流，比如她开了一家银行，那么她需要和每个人交换不同的密钥，她必须管理所有这些密钥并发送数千条消息。 那么，密码学家们不禁要问，有没有更简单的方法呢？

1970 年，英国工程师和数学家詹姆斯·爱丽丝尝试了公钥加密，这是基于锁定和解锁是相互操作的简单而巧妙的概念

为了理解这些，我们用颜色的比喻来说明 Bob 如何在不让听者截获信息的情况下向 Alice 发送特定的颜色。

每种颜色都有一个补色，与补色叠加会得到白光，可以去除第一种颜色的影响，这里我们假设混色是单向函数，很容易混色输出第三种颜色，但相反的过程是困难的。 Alice首先生成自己的私钥，即可以随意选择一种颜色，比如红色。 接下来，假设爱丽丝有一台神秘的颜色机器，可以找到红色的互补色。 没有其他人知道这一点，它变成了蓝绿色，他将它作为公钥发送给 Bob，假设 Bob 想给 Alice 发送一个神秘的黄色阴影。

他将黄色与公共颜色混合比特币的计算原理，并将混合后的颜色发送给爱丽丝。 这时，爱丽丝可以在鲍勃的混合色中加入自己的私有色，这样会取消公开色的作用，留下鲍勃的秘密色，窃听者不能简单地破译鲍勃的黄色，除非他有爱丽丝的红色。

我们还需要一种数学方法来使这项工作在实践中发挥作用。

模幂

解决方案是由另一位数学家克利福德考克斯发现的。 Cox需要构造一种特殊的单向函数，trapdoor one-way function，从一个方向很容易计算，反之很难走到这里，除非你有关于trapdoor的特殊信息。 为此，他考虑了模幂运算。

之前讲过的Fiddy-Hellman密钥交换，我有介绍过，这里简单介绍一下，具体方法如下：取一个数的某一次次方，除以模数，输出余数，可以以这种方式用于加密信息，假设Bob有一条信息转换成一个数m，他可以将这个数乘以e次，其中e是公开指数，然后他可以将结果除以一个随机数N，并输出除法的余数，得到数c，这个计算很容易做，但是给定ce N，很难找到m是多少，因为我们需要某种试错过程，这是可用于 m 的单向函数。

正向执行容易，反向执行难。 也就是说，我们是一把数字锁，钥匙是活板门。 这是某种使加密的逆向过程变得容易的信息。 我们需要取c的其他次方，比如d的次方， Undo原来对m进行的操作，得到初始信息m。 两个运算的组合是 m 的 e 次幂。 然后整个d次方，即m的e乘以d次方，e表示加密，d表示解密。

因此，Alice 需要一种构造 e 和 d 的方法，让其他人很难找到 d 的值。 这需要第二个单向函数，用户生成 d，为此他想到了 Euclid。

欧几里德的证明

2000多年前，欧几里德就证明了每个数只有一个质因数分解，可以认为是一把钥匙。 我们知道质因数分解是一个非常困难的问题。 我先澄清一下这里的“难”是什么意思？ 我将通过介绍所谓的事件复杂度来解释它。 我们都执行过乘法运算。 每个人都有自己的计算加速方法。 如果你给计算机编程来计算乘法，它的计算速度比任何人都快得多。 .

对比一下这个齐次因子分解，如果有人让你分解589个素因子，你可能会觉得这道题比较难。 在任何情况下，这都需要反复试验，直到找到可以平分 589 的特定数字。 一系列错了之后，你会发现它的质因数分解是19*31。 如果有人让你分解 437231 个素因子，你可能会放弃并求助于计算机。 较小的数字会起作用，但随着数字变得越来越大数字越大，越多的计算机将开始不堪重负。 随着数字变大和计算步骤的增加，所需时间将急剧增加。 拥有更大数字的计算机可能需要几分钟，然后更大的数字可能需要数小时，最终可能需要数千。 分解非常大的数字需要数百年的时间。

因此，我们说这是一个hard problem，解决这个问题需要的事件数会快速增长，而factorization就是Cox用来构建trapdoor的方法。

第一步，假设爱丽丝随机生成一个位数超过150位的质数，记为p1，然后随机生成第二个位数相同的质数，记为p2，然后将两个质数相乘得到合数数字N。乘法要求事件小于一秒，可以很容易地用浏览器计算。 然后，她把N由P1分解由P2隐藏起来，告诉大家N。别人要电脑计算，可能要几年比特币的计算原理，

在第二步中，考克斯需要找到一个依赖于知道 N 的因式分解的函数，为此他回顾了瑞士数学家莱昂哈德欧拉 1765 年的函数。

欧拉函数

欧拉继续研究素数分布的性质。 他定义了一个重要的函数，称为 phi 函数，它平衡数字的整除性。 对于给定的数N，函数的输出是，有多少个小于等于N的整数，不同的N有公因数，我以phi(8)为例来说明。

我们考虑从 1 到 8 的整数，然后统计有多少个整数。 和8没有大于1的公因数，比如6不算，因为6和8的公因数是2，1357算在内。 它们只有 8 1 的公因数，所以 (8)=4。

对于任意素数P，(P)=P-1，如素数7，(7)，需要计入所有小于7的整数，这些数与7没有公因数，所以(7)=6 ，如果求素数21377的phi函数值只需要减1就可以得到答案，21376，任意素数的phi函数值很容易计算，由此得出一个有趣的结果，根据乘法phi的性质 phi(A·B)= phi(A)·phi(B)，如果已知数N，则为两个素数P1和P2的乘积。 那么phi(N)等于两个素数的phi值的乘积。 即（P1-1）·（P2-1）。

RSA加密

我们现在有了解决 phi 的陷门。 如果您知道 N 是如何因式分解的，那么求解 phi(N) 就很容易了。 例如77的质因数分解为7×11，则phi(77)=6×10=60。

第三步，如果phi函数和模幂运算联系起来，为此，他想到了欧拉定理，即phi函数和模幂运算的关系，m的phi(n)次方= 1mod n，意思是可以任意选择2个数，使它们没有公因数，假设m和n，这里令m=5，n=8，取m的phi(n)次方，即4次power , 除以 n 的总和为 1，我们只需要用两个简单的规则来处理这个方程。

首先，1的任意次方，记录为1的k次方，永远等于1。同样，我们可以将指数phi(n)乘以任意数k，结果仍然为1，然后将1乘以任意数计数m的结果总是m。 同样，左边可以乘以m，右边也可以得到m。 这可以简化为m的k·phi(n)+1次方，突破口就在这里。

现在我们有了 e 乘以 d 的方程式，它取决于 phi(n)，所以只有当 n 的因式分解已知时，计算 d 才容易，其中 d 可以用作 Alice 的密钥，这是一个 A 陷门，因此她可以释放e的效果，我举个例子简单说明一下：

假设 Bob 有一条信息，他使用一些填充方案将其转换为一个数字，这里假设 m，然后 Alice 通过以下方式生成她的公钥和私钥，首先，她生成 2 个大小相似的随机素数, 把这两个相乘得到n, 假设n是3127, 那么计算phi(n)就很容易了, 因为她知道n是如何因式分解的, 这里phi(n) = 3016, 那么她选择一个小的公共指数e,前天这个e一定是奇数，不同的phi(n)有公因数，这里选择e=3，最后她求出私有指数d的值，这里是(2·phi(n )+1)/3，即2011年。

他把这些隐藏起来，只留下n和e的值，因为n和e组成了她的公钥，可以认为是一把开锁，她把这些发给Bob，让Bob锁定自己的信息，Bob locks通过计算m的e吃mod n，记为c 这是他的加密信息，他把这个信息发回给Alice，最后，Alice用她的私钥d解密这个信息，通过trapdoor访问，c的d次方mod n，等于 Bob 的原始信息 m，任何知道 cne 的人都想知道如何计算指数 d，智能地计算 phi(n)，这需要他们知道 n 的质因数分解。

当n足够大的时候，爱丽丝可以保证即使是最先进的计算机网络也需要数百年的时间来计算这个。 该技术发布后，立即被视为国家机密，但在1977年，该技术于1977年被独立发现。作者是Ronald Rivester、Adi Samor和Leonard Aardman，加密以他们名字的首字母命名RSA . RSA是使用最广泛的公钥算法，也是历史上使用最多的加密算法。

目前世界上几乎所有的互联网用户都在使用RSA，或者相关的版本，不管他们是否意识到，RSA加密的强度来自于素因子分解的难度，这是深层次问题的结果的素数分布。 这个问题存在了几千年，人类至今也没能解决。