非对称加密

非常有趣的思想。

对称加密

为什么要加密呢？因为有些羞羞的东西不想让他人看到。

比如甲给乙传小纸条，必须要经过捣蛋鬼的手中。如果不加密，捣蛋鬼就会知道其中的内容，然后发出嘿嘿嘿的猥琐笑声。BAD ENDING 1

甲和乙都很无语。所以他们决定以后发消息的时候要加密。

甲把信息加密后写在小纸条上，传给乙。

捣蛋鬼即使在途中看到了也没有办法知道里面的内容。HAPPY ENDING (DREAMING)

但是现实很残忍，甲和乙不能私下接触，所以只能通过传小纸条的方式来交换信息。

那么加解密用的密钥，甲该怎么传给乙呢？

假设甲把密钥加密后传给乙，乙不知道加密过后的密钥怎么解密。看不懂。BAD ENDING 2

假设甲把没加密的密钥传给乙，捣蛋鬼也知道了密钥，甲再发羞羞的内容给乙时，捣蛋鬼用已知的密钥解密，再次发出嘿嘿嘿的猥琐笑声。BAD ENDING 3

甲感到很绝望。不加密会被偷窥。加密了也会被偷窥。

甲在想如果加密和解密用的不是同一个密钥，那么这样就不怕被偷窥了。那要怎么做呢？

后来老师在密码学课上讲了方法。

甲准备两个密钥，这两个密钥有这样的特点，知道一个密钥不能推出另外一个密钥，但是两个密钥对于某些数学运算能得到相同的结果，也就是一个密钥加密的文本只能用另外一个密钥解密。

甲随机选择一个密钥，不加密，写在小纸条上传给乙。捣蛋鬼和乙一看这乱七八糟的数字一定是密钥，这个密钥已经公开了。所以称为公钥。剩下那个没公开的称为私钥。

乙心神领会后，也把公钥发给了甲。

这样两轮信息交换后

甲知道了乙的公钥、甲的公钥、甲的私钥。

乙知道了甲的公钥、乙的公钥、乙的私钥。

捣蛋鬼知道了甲的公钥和乙的公钥。

甲用乙的公钥加密羞羞的东西，发给乙。

捣蛋鬼看到莫名其妙的东西，知道是被加密了。但是乙的公钥不能解密，能解密的只有乙的私钥。捣蛋鬼并不知道乙的私钥。只好放行。传给乙。

乙收到密文后，用乙的私钥解密，看到了羞羞的东西，决定回复甲。

乙用甲的公钥加密回复，发给甲。

捣蛋鬼再次看到莫名其妙的东西，知道肯定又是加密了。而且肯定使用甲的公钥加密了。因为如果用乙的公钥加密，甲没有乙的私钥没有办法解密。捣蛋鬼没有甲的私钥，不能解密，只好放行。

甲收到密文后用甲的私钥解密。看到了回复。 HAPPY ENDING

在上述两个例子中，有两种加密方式。

加密和解密用的是同一个密钥，这叫对称加密。

相应地，加密和解密用的不是同一个密钥，这叫非对称加密。

对称加密很容易做到。那么非对称加密是怎么做到密钥不一样还能解密的呢？

有好几种方法，比如有一种方法是这样的。

在数学运算中，有些运算会产生信息丢失，也就是即便知道了运算结果也不一定能推出运算前的数。

比如对于取膜 $\bmod$

$3 \bmod 2 = 1$ 。如果只知道运算结果是 $1$ 是不能确定运算前是 $3$ 的，因为有可能是 $1, 3, 5, 7, 9\dots$ 中的任何一个。

虽然不知道原来的数，但是只要知道数学关系就能得到相同的结果。比如只要奇数模 2 都会等于 1 。

所以可以这么做。

甲先公开生成密钥的两个常数 $g = 5$ 和 $p = 23$ 。

甲随机选取一个数字 $a$ 比如 $a = 6$ ，算出公钥 $A = g^a \bmod p = 5^6 \bmod 23 = 8$

甲把公钥 $A = 23$ 发给乙，把私钥 $a = 6$ 偷偷藏起来。

捣蛋鬼知道了 $5^? \bmod 23 = 8$ ，但是推不出甲的私钥 $a$ 。

乙随机选取一个数字 $b$ 比如 $b = 15$ ，算出公钥 $B = g^b \bmod p = 5^{15} \bmod 23 = 19$

乙把公钥 $B = 19$ 发给甲，把私钥 $b = 15$ 偷偷藏起来。

捣蛋鬼知道了 $5^? \bmod 23 = 19$ ，但是推不出乙的私钥 $b$ 。

因为 $(g^a)b = (g^b)^a$ 所以 $(g^a)^b \bmod p = (g^b)^a \bmod p$

由于取模的性质有

$(g^a)^b \bmod p = A^b \bmod p$

$(g^b)^a \bmod p = B^a \bmod p$

所以

$A^b \bmod p = B^a \bmod p$

也就是甲可以通过甲的私钥和乙的公钥组合来解密，不能只通过乙的公钥来解密。

同样，乙可以通过乙的私钥和甲的公钥组合来解密，不能只通过甲的公钥来解密。

在实际应用中通常选择比较大的数防止暴力穷举。

因为非对称加密相比于对称加密较慢，所以通常使用非对称加密传递对称加密的密钥后使用对称加密通信。

中间人攻击

以上情况建立在捣蛋鬼没有好好听课的前提下。实际上捣蛋鬼刚好认真听了老师那节介绍非对称加密的课。

于是甲传递甲的公钥时，捣蛋鬼替换为捣蛋鬼的公钥。

乙收到捣蛋鬼的公钥后发出乙的公钥。

捣蛋鬼收到乙的公钥后替换为捣蛋鬼的公钥。

甲收到捣蛋鬼的公钥后，用捣蛋鬼的公钥加密羞羞的东西，发给乙。

捣蛋鬼收到加密的内容后，用捣蛋鬼的私钥解密后看到羞羞的内容。发出嘿嘿嘿的猥琐笑声。BAD ENDING 4

应对非对称加密

如果文件被非对称加密（如 RSA）加密了。有什么办法解密吗？

目前能想到的有以下几种方法。

暴力穷举，假设你有银河超级计算器的话。
获取私钥，假设你可以有资本色诱或威胁的话。
找到快速的大质数分解方式，顺便拿个炸药奖。

最后

在现实生活中，甲传纸条给乙，经过捣蛋鬼的手，捣蛋鬼噌地站起来指着甲说：“老师他上课传纸条！”。REAL ENDING

参考链接