非对称加密破解（非对称加密和对称加密）

非对称加密可以破解吗？？？？

非对称加密理论在1976年由两个老美提出，理论核心是一种算法求得的非对称密钥对当前很难相互推倒出来，只要推到不出来……理论上这种加密体系就是安全的。但算法在理论上并没有证明这个非对称密钥对绝对无法相互推倒，所以以后说不准的

密码学基础（三）：非对称加密（RSA算法原理）

加密和解密使用的是两个不同的秘钥，这种算法叫做非对称加密。非对称加密又称为公钥加密，RSA只是公钥加密的一种。

现实生活中有签名，互联网中也存在签名。签名的作用有两个，一个是身份验证，一个是数据完整性验证。数字签名通过摘要算法来确保接收到的数据没有被篡改，再通过签名者的私钥加密，只能使用对应的公钥解密，以此来保证身份的一致性。

数字证书是将个人信息和数字签名放到一起，经由CA机构的私钥加密之后生成。当然，不经过CA机构，由自己完成签名的证书称为自签名证书。CA机构作为互联网密码体系中的基础机构，拥有相当高级的安全防范能力，所有的证书体系中的基本假设或者前提就是CA机构的私钥不被窃取，一旦 CA J机构出事，整个信息链将不再安全。

CA证书的生成过程如下：

证书参与信息传递完成加密和解密的过程如下：

互质关系：互质是公约数只有1的两个整数，1和1互质，13和13就不互质了。

欧拉函数：表示任意给定正整数 n，在小于等于n的正整数之中，有多少个与 n 构成互质关系，其表达式为：

其中，若P为质数，则其表达式可以简写为：

情况一：φ(1)=1

1和任何数都互质，所以φ(1)=1；

情况二：n 是质数， φ(n)=n-1

因为 n 是质数，所以和小于自己的所有数都是互质关系，所以φ(n)=n-1；

情况三：如果 n 是质数的某一个次方，即 n = p^k ( p 为质数，k 为大于等于1的整数)，则φ(n)=(p-1)p^(k-1)

因为 p 为质数，所以除了 p 的倍数之外，小于 n 的所有数都是 n 的质数；

情况四：如果 n 可以分解成两个互质的整数之积，n = p1 × p2，则φ(n) = φ(p1p2) = φ(p1)φ(p2)

情况五：基于情况四，如果 p1 和 p2 都是质数，且 n=p1 × p2，则φ(n) = φ(p1p2) = φ(p1)φ(p2)=(p1-1)(p2-1)

而 RSA 算法的基本原理就是欧拉函数中的第五种情况，即： φ(n)=(p1-1)(p2-1);

如果两个正整数 a 和 n 互质，那么一定可以找到整数 b，使得 ab-1 被 n 整除，或者说ab被n除的余数是1。这时，b就叫做a的“模反元素”。欧拉定理可以用来证明模反元素必然存在。

可以看到，a的 φ(n)-1 次方，就是a对模数n的模反元素。

n=p x q = 3233，3233写成二进制是110010100001，一共有12位，所以这个密钥就是12位。

在实际使用中，一般场景下选择1024位长度的数字，更高安全要求的场景下，选择2048位的数字，这里作为演示，选取p=61和q=53；

因为n、p、q都为质数，所以φ(n) = (p-1)(q-1)=60×52= 3120

注意，这里是和φ(n) 互互质而不是n！假设选择的值是17，即 e=17；

模反元素就是指有一个整数 d，可以使得 ed 被 φ(n) 除的余数为1。表示为：(ed-1)=φ(n) y -- 17d=3120y+1，算出一组解为(2753,15)，即 d=2753，y=-15，也就是(17 2753-1)/3120=15。

注意，这里不能选择3119，否则公私钥相同？？

公钥：(n,e)=(3233,2753)

私钥：(n,d)=(3233,17)

公钥是公开的，也就是说m=p*q=3233是公开的，那么怎么求e被？e是通过模反函数求得，17d=3120y+1，e是公开的等于17，这时候想要求d就要知道3120，也就是φ(n)，也就是φ(3233)，说白了，3233是公开的，你能对3233进行因数分解，你就能知道d，也就能破解私钥。

正常情况下，3233我们可以因数分解为61*53，但是对于很大的数字，人类只能通过枚举的方法来因数分解，所以RSA安全性的本质就是：对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。

人类已经分解的最大整数是：

这个人类已经分解的最大整数为232个十进制位，768个二进制位，比它更大的因数分解，还没有被报道过，因此目前被破解的最长RSA密钥就是768位。所以实际使用中的1024位秘钥基本安全，2048位秘钥绝对安全。

网上有个段子：

已经得出公私钥的组成：

公钥：(n,e)=(3233,2753)

私钥：(n,d)=(3233,17)

加密的过程就是

解密过程如下：

其中 m 是要被加密的数字，c 是加密之后输出的结果，且 m n ，其中解密过程一定成立可以证明的，这里省略证明过程。

总而言之，RSA的加密就是使用模反函数对数字进行加密和求解过程，在实际使用中因为 m n必须成立，所以就有两种加密方法：

对称加密存在虽然快速，但是存在致命的缺点就是秘钥需要传递。非对称加密虽然不需要传递秘钥就可以完成加密和解密，但是其致命缺点是速度不够快，不能用于高频率，高容量的加密场景。所以才有了两者的互补关系，在传递对称加密的秘钥时采用非对称加密，完成秘钥传送之后采用对称加密，如此就可以完美互补。

非对称加密算法

如果要给世界上所有算法按重要程度排个序，那我觉得“公钥加密算法”一定是排在最前边的，因为它是现代计算机通信安全的基石，保证了加密数据的安全。

01 对称加密算法

在非对称加密出现以前，普遍使用的是对称加密算法。所谓对称加密，就是加密和解密是相反的操作，对数据进行解密，只要按加密的方式反向操作一遍就可以获得对应的原始数据了，举一个简单的例子，如果要对字符串"abc"进行加密，先获取它们的ANSCII码为：97 98 99；密钥为+2，加密后的数据就是：99 100 101，将密文数据发送出去。接收方收到数据后对数据进行解密，每个数据减2，就得到了原文。当然这只是一个非常简单的例子，真实的对称加密算法会做得非常复杂，但这已经能够说明问题了。

这样的加密方法有什么缺点呢？首先缺点一：密钥传递困难；想想看如果两个人，分别是Bob和Alice，Bob要给Alice发消息，那Bob就要把密钥通过某种方式告诉Alice，有什么可靠的途径呢？打电话、发邮件、写信...等等方式好像都不靠谱，都有被窃取的风险，也只有两人见面后当面交流这一种方式了；缺点二：密钥数量会随着通信人数的增加而急剧增加，密钥管理将会是一个非常困难的事情。

02 非对称加密算法

1976年，两位美国计算机学家，提出了Diffie-Hellman密钥交换算法。这个算法的提出了一种崭新的构思，可以在不直接传递密钥的情况下，完成解密。这个算法启发了其他科学家，让人们认识到，加密和解密可以使用不同的规则，只要这两种规则之间存在某种对应的关系即可，这样就避免了直接传递密钥。这种新的加密模式就是“非对称加密算法”。

算法大致过程是这样的：

（1）乙方 生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。

（2）甲方获取乙方的公钥，然后用它对信息加密。

（3）乙方得到加密后的信息，用私钥解密。

如果公钥加密的信息只有私钥解得开，那么只要私钥不泄漏，通信就是安全的。

03 RSA非对称加密算法

1977年，三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法。

从那时直到现在，RSA算法一直是最广为使用的"非对称加密算法"。毫不夸张地说，只要有计算机网络的地方，就有RSA算法。这种算法非常可靠，密钥越长，它就越难破解。根据已经披露的文献，目前被破解的最长RSA密钥是768个二进制位。也就是说，长度超过768位的密钥，还无法破解（至少没人公开宣布）。因此可以认为，1024位的RSA密钥基本安全，2048位的密钥极其安全。

公钥加密 - 私钥解密

只有私钥持有方可以正确解密，保证通信安全

私钥加密 - 公钥解密

所有人都可以正确解密，信息一定是公钥所对应的私钥持有者发出的，可以做签名

04 质数的前置知识

RSA的安全性是由大数的质因数分解保证的。下面是一些质数的性质：

1、任意两个质数构成素质关系，比如：11和17；

2、一个数是质数，另一个数只要不是前者的倍数，两者就构成素质关系，比如3和10；

3、如果两个数之中，较大的那个是质数，则两者构成互质关系，比如97和57；

4、1和任意一个自然数都是互质关系，比如1和99；

5、p是大于1的整数，则p和p-1构成互质关系，比如57和56；

6、p是大于1的奇数，则p和p-2构成互质关系，比如17和15

05 RSA密钥生成步骤

举个“栗子“，假如通信双方为Alice和Bob，Alice要怎么生成公钥和私钥呢？

St ep 1：随机选择两个不相等的质数p和q；

Alice选择了3和11。（实际情况中，选择的越大，就越难破解）

S tep 2 ：计算p和q的乘积n；

n = 3*11 = 33，将33转化为二进制：100001，这个时候密钥长度就是6位。

Step 3 ：计算n的欧拉函数φ(n)；

因为n可以写为两个质数相乘的形式，欧拉函数对于可以写成两个质数形式有简单计算方式

φ(n) = (p-1)(q-1)

Step 4 ：随机选择一个整数e，条件是1 e φ(n)，且e与φ(n) 互质；

爱丽丝就在1到20之间，随机选择了3

Step 5 ：计算e对于φ(n)的模反元素d

所谓模反元素，就是指有一个整数d，可以使得ed被φ(n)除的余数为1

Step 6 ：将n和e封装成公钥，n和d封装成私钥；

在上面的例子中，n=33，e=3，d=7，所以公钥就是 (33,3)，私钥就是（33, 7）。

密钥生成步骤中，一共出现了六个数字，分别为：

素质的两个数p和q，乘积n，欧拉函数φ(n)，随机质数e，模反元素d

这六个数字之中，公钥用到了两个（n和e），其余四个数字都是不公开的,可以删除。其中最关键的是d，因为n和d组成了私钥，一旦d泄漏，就等于私钥泄漏。

那么，有无可能在已知n和e的情况下，推导出d？

（1）ed 1 (mod φ(n))。只有知道e和φ(n)，才能算出d。

（2）φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。

（3）n=pq。只有将n因数分解，才能算出p和q。

结论是如果n可以被因数分解，d就可以算出，也就意味着私钥被破解。

BUT！

大整数的因数分解，是一件非常困难的事情。目前，除了暴力破解，还没有发现别的有效方法。

维基百科这样写道：

"对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。

假如有人找到一种快速因数分解的算法，那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有较短的RSA密钥才可能被暴力破解。到现在为止，世界上还没有任何可靠的攻击RSA算法的方式。

只要密钥长度足够长，用RSA加密的信息实际上是不能被解破的。"

06 RSA加密和解密过程

1、加密要用公钥(n,e)

假设鲍勃要向爱丽丝发送加密信息m，他就要用爱丽丝的公钥 (n,e) 对m进行加密。

所谓"加密"，就是算出下式的c：

爱丽丝的公钥是 (33, 3)，鲍勃的m假设是5，那么可以算出下面的等式：

于是，c等于26，鲍勃就把26发给了爱丽丝。

2、解密要用私钥(n,d)

爱丽丝拿到鲍勃发来的26以后，就用自己的私钥(33, 7) 进行解密。下面的等式一定成立(至于为什么一定成立，证明过程比较复杂，略)：

也就是说，c的d次方除以n的余数为m。现在，c等于26，私钥是(33, 7)，那么，爱丽丝算出：

因此，爱丽丝知道了鲍勃加密前的原文就是5。

至此，加密和解密的整个过程全部完成。整个过程可以看到，加密和解密使用不用的密钥，且不用担心密钥传递过程中的泄密问题，这一点上与对称加密有很大的不同。由于非对称加密要进行的计算步骤复杂，所以通常情况下，是两种算法混合使用的。

07 一些其它的

在Part 5的第五步，要求一定要解出二元一次方程的一对正整数解，如果不存在正整数解，这该怎么办？

扩展欧几里得算法给出了解答：

对于不完全为 0 的非负整数 a，b，gcd（a,b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a,b）=ax+by;

第五步其实等价于：ed - kφ(n) = 1, e与φ(n)又互质，形式上完全与扩展欧几里得算法的一致，所以一定有整数解存在。

Reference: