本文转载自微信公众号《后端技术指南针》，作者指南针氪金入口。转载本文请联系后台技术指南针公众号。1.数学与密码学之美没事的时候看了一会《数学之美》。第17章描述了电视剧《暗算》开发的密码学背后的一些数学原理。从凯撒密码到二战盟军、日军，本书讲述了密码学中均匀分布&统计独立性的基本理论。我兴致勃勃地读了起来，但有些细节我没看懂，所以我决定写一篇文章。2、加密算法的一点历史我们知道常见的加密算法有：对称加密和非对称加密，而非对称加密就是我们今天的主角。非对称加密不是一蹴而就的。1976年后才出现。可以说非对称加密是对称加密的优化。2.1对称加密的缺点所谓对称加密是指：发送方使用一种规则对信息进行处理，接收方需要使用相同的规则对信息进行反向处理。对称加密要求通信双方使用相同的规则和密钥进行加密和解密，因此如何妥善保管密钥和规则非常重要。如果密钥泄露，再强大的对称加密算法也是徒劳，所以如何安全地交换对称加密的规则和密钥是一个短板。如何安全地交换密钥？真让人头疼。2.2密钥交换算法1976年，两位美国计算机科学家WhitfieldDiffie和MartinHellman提出了一种新的思路，无需传递密钥即可完成解密。听起来很厉害。这是世界吗？实际上，它被称为Diffie-HellmanDiffie-Hellman密钥交换算法。我们来看看维基百科上两位大神的简介：这两位大神都是密码学的先驱。为非对称加密算法指明了方向：双方不一定要直接交换密钥。在Diffie-Hellman密钥交换算法中，通信双方实际上并不交换密钥，而是通过计算生成一个相同的共享密钥。具体过程还是比较复杂的，这里就不展开了。非对称加密算法RSA借鉴了这个思想，使用公钥和私钥完成加密和解密，但是避免了密钥传输，RSA算法的公钥是公开的，用公钥加密的信息必须使用对应的私钥解密。3.RSA算法RSA算法可以说是地球上最重要的算法之一，是数据通信和网络安全的基石。3.1算法作者RSA是由罗纳德·里维斯特（RonRivest）、阿迪·沙米尔（AdiShamir）和伦纳德·阿德尔曼（LeonardAdleman）于1977年提出的。当时他们三人都在麻省理工学院工作，RSA就是由他们三个姓氏的首字母组成的。RSA算法密钥越长，越难破解。根据相关文献，目前破解的最长RSA密钥为768个二进制位。一般认为1024位的RSA密钥基本安全，2048位的密钥极其安全。RSA算法目前支持4096位长度。密钥长度与加解密时间成正比，所以我们需要根据自己的场景来选择密钥长度，不必盲目追求长密钥。3.2算法过程RSA算法的本质是数学。公钥和私钥在数学上是相关的，不需要直接传输。算法过程包括：密钥生成、密钥加解密。3.2.1密钥生成RSA算法的密钥是配对的，公钥加密，私钥解密。让我们看看这对密钥是如何计算的。1、随机选择两个素数P和Q，我们选择P=61，Q=53，计算PQ的乘积N=PQ=61*53=3233，将N转为二进制：110010100001。N的二进制长度为12，也就是密钥长度为12。本文只是讲解算法原理。实际中，密钥长度超过1024位才安全，12位基本就是演示了。2、求N的欧拉函数值。欧拉函数的定义：给定任意正整数n，在小于等于n的正整数中，有多少个与n互质？欧拉函数有一个通用的计算公式为：要证明欧拉函数需要分很多种情况，特别是当n为素数时会出现一些特殊情况。直接得出结论：a。如果k是素数，则φ(k)=k-1；b.如果n=P*Q，P和Q都是质数，则φ(n)=φ(P*Q)=φ(P)φ(Q)=(P-1)(Q-1)。P=61，Q=53，则N=3233，则N的欧拉函数记为M=(P-1)*(N-1)=60*52=31203.求一个整数EM是相对primetoM除了1和E之外，E和E之间没有公约数（互质）4.求一个整数D满足如下关系：(E*D)modM=1，即E和E的乘积D除以M的余数为1，这里有一项-模逆元，意思是有一个整数d可以使ed除以φ(n)的余数为1。等价于下面的计算过程：当E=17,M=3120,K=1,2,3...,17*D-K*M=1时，解这个方程求出一组满足关系的D和K即它可以证明其中一个群是(D,K)=(2753,15)。综上所述，我们找到了由随机选择的互质P和Q计算出的N、M、E、D，我们把这些数分成两组：(E,N)和(D,N)分别是公钥组和私钥组密钥组，E是公钥，D是私钥。本例中公钥组为(E,N)=(17,3233)，私钥组为(D,N)=(2753,3233)。接下来，我们将使用这对密钥进行加密和解密。3.2.1加密过程由于RSA算法本质上是数字运算，所以在对字符串进行加密时，需要先将字符串数字化。我们可以借助ascii码、unicode编码、utf-8编码等将字符串转换成数字。特别要注意转换后的数字X需要小于key组中的N。如果字符串转换后的个数大于N，则需要拆分。这可能是因为我们在数据量很大的时候使用了对称加密算法对内容进行加密。使用使用非对称加密算法加密密钥的原因。加密过程满足：X^EmodN=Y其中X为明文，E为公钥，N为大整数，Y为密文，mod取余。3.2.3解密过程得到密文Y后，我们开始解密。过程满足：Y^DmodN=X，其中Y为密文，D为私钥，N为大整数，X为明文，mod取余。上述加解密过程涉及到费马小定理。3.2.4欧拉定理和费马小定理这块有点晦涩难懂，但却是RSA算法的核心部分。来看看：费马小定理给出了素数检测性质，欧拉证明了。这就是费马-欧拉定理。3.3RSA算法可靠性分析经过上面的密钥生成、加解密过程，我们不免要问：RSA算法可靠吗？私钥D能否从公钥组(E,N)推导出来？整理一下：因为ed≡1(modφ(N))，只知道e和φ(N)就可以计算出d，而e是公钥，所以只需要知道φ(N)就可以了。根据欧拉函数φ(N)=(P-1)(Q-1)，只有知道P和Q才能计算出φ(N)。N=pq，P和Q只能通过分解N来计算。因此，如果能分解大数N，就可以计算出私钥D来破解密文。3.5大整数因式分解大整数因式分解难度极大，属于NPC问题。除了暴力破解，没有什么好的解决办法。目前，人类分解的二进制数最大长度为768位，1024位的长度尚未破解。所以长度为1024的二进制密钥是安全的。因此，RSA算法的安全性取决于分解大整数的难度。目前RSA算法可以支持的密钥长度为4096位。分解的难度超乎想象。即使有量子计算机的帮助，难度和时间也是非常非常大的。4.总结本文从对称加密算法的密钥传递安全性出发，讲述了Diffie-Hellman算法的密钥交换协商，为RSA算法的公钥和私钥提供了灵感。MIT的三位数学家根据欧拉定理&费马定理等数学定理，创造了伟大的RSA非对称加密算法。RSA算法的安全性取决于分解大量质因数的难度。目前，1024位的二进制密钥还没有被人类破解。出于安全原因，可以使用2048位RSA密钥进行加密。不愧是烧脑的硬核内容。不禁感叹素数真是个神奇的东西。段位有限，只能用来招揽点子，仅此而已！
