七夕缘起-第5.3章-非对称加密探索
经过了几次加密的尝试后，牛郎终于明白，加密很重要，同时，也需要一种认证机制。
如何才能将加密与认证融为一体呢？
牛郎想到了之前的“散列算法”，这个方式可以融入一些认证因素，但是，还不够强。
从原则上讲，能解密信息的人，一定就应该是我们指定的接收人才对。
但是，事实并非如此。前面尝试过的“AES加密方法”，是完全依赖与秘钥的。
整个过程只有一个秘钥，多人使用一个秘钥，一旦有人秘钥不慎将丢失，那么，拿到秘钥的人就能解密信息了。
而且，最让人头疼的时，让两个人都拿到这个相同的秘钥，本身就是个麻烦事。
好不容易想出来了“秘钥交换策略”，却因为无法认证身份，从而有“中间人攻击”的漏洞。
那么，怎样才能安全地加密呢？
按上面总结的几个点，可能还是要从“秘钥”上做文章。
既然两人或多人都知道秘钥，会增加泄露风险，那能否只有一人知道秘钥？
既然“交换秘钥”存在风险，那能否不要有秘钥交换过程？
牛郎怎么想，都觉得不可能呀，解密，必然要用到加密时的秘钥啊。
只有一个人知道秘钥，而且不与对方交换，那么，接收方就不知道秘钥，该怎么解密信息呢？
突然，牛郎灵机一动：
除非……加密和解密使用的秘钥不同！
试想一下，如果加密、解密使用的秘钥不同的话，那么，确实就不需要秘钥传递过程了。
比如说，牛郎要给织女传递信息，织女只要妥善保存好“解密秘钥”就足够了，这个根本也不需要告诉牛郎。
而“加密秘钥”则公开出去，牛郎可以用它加密，别人也可用用它加密，但大家都没有织女的“解密秘钥”，无法解密出原文。
由于自始至终，“解密秘钥”都是织女自己保管，从未进行过传递，因此理论上可以保证其安全性。
这好像是一个相对完美的方案。
当然，大家应该也想到了，既然“加密秘钥”被公开了出去，那么任何人都可以给织女发送加密信息。
怎么知道，发送者，一定是牛郎呢？
这里，还是要从秘钥方面入手，“加密秘钥”与“解密秘钥”要能够互换。怎么说呢？
我们把织女手中那个从未公开的秘钥，暂且成为“私钥”，而把她公之于众的秘钥称为“公钥”。
现在的情况是，用“公钥”加密，用“私钥”解密。
我们希望是，如果织女反过来用“私钥”加密的话，那么用“公钥”也能够成功解密。
也就是两把钥匙，用一把加密的话，就必须且只能用另一把解密。
这样能解决什么问题呢？
因为刚才提到了，“私钥”从未公开过，因此只有织女一人知道。
那么，如果出现了一段信息，可以用“公钥”解密，那么就可以断定，这段信息一定是织女发送的。
因为“公钥”可以解密意味着只能是“私钥”加密的，而拥有“私钥”的，只有织女一人。
不过大家都有“公钥”，因此这加密的信息相当于明文，但却足以发送者身份。
怎么样，综合一下，是不是就有一种集身份验证、密钥安全于一体的加密方式了呢？
先不说这个加密方法该怎么实现，单从理论上说，是的。
织女保存自己的“织女私钥”，对外公布“织女公钥”。
牛郎保存自己的“牛郎私钥”，对外公布“牛郎公钥”。
牛郎给织女发消息时，先用“织女公钥”加密，然后将加密后的信息，用自己的“牛郎私钥”再次加密。
接着就可以发送出去了。
织女和监听者们都会收到这个消息。
由于“牛郎公钥”是公开的，大家发现可以用这个公钥解密出内容，因此可以确认这一定是手中有“牛郎私钥”的牛郎发送的。
虽然所有人都知道这来自牛郎，也解密出了内容，但刚才说了，这内容是被“织女公钥”加密过的。
此时，只有织女手中的“织女私钥”，才能解密出最终的信息。而监听者们却无能为力。
同理，织女给牛郎发送信息时，也是一样的策略，经过两次加密，既确认了身份，又保证了信息安全。
当然，理论上可行的东西，真正实践起来，总是困难重重。
首先，该怎么去设计这种神奇的加密方法呢？
其次，既然“公钥”与“私钥”可以互相加解密，那么，它们之间必然存在着某种数学上的联系，
如何确保外界知道“公钥”前提下，无法猜测或者推算出“私钥”呢？
那么，接下来的问题，又是一个数学问题了。
牛郎再次翻遍数学典籍，在一本《数论》的典籍中，终于找到了一条重要思路：
寻找两个大素数比较简单，而将它们的乘积进行因式分解却极其困难。
接下来的过程，可能有点烧脑（这里“”表示乘法，“/”表示除法）：
1.选择两个不同的素数p和q，计算n=pq，m=(p-1)*(q-1)。
2.随便选择一个比p和q都大，但比n小的数e，这就是我们的“公钥”了。
是不是不难？接下来要用数学方法计算私钥：
私钥d=(km+1)/e，其中m、e就是上面1、2两步提到的数字。
既然是除法，则可能会有余数，而私钥d是个整数，这怎么办呢？
k的作用就发挥出来了，让k=1，2，3，……一直尝试，总会有一个k，可以得到整数私钥d的。
我们需要的，是公开信息n和e，而秘密保存d。其他的p、q、n、m、k，统统销毁掉，不要让任何人知道。
第一个问题，私钥d是安全的吗？
理论上，是的。因为d从未传递过，而且，通过公开的n和e，要推算出d，几乎是不可能的。
既然知道n是p*q的结果，那能通过n反推p和q吗？
基本不可能，因为目前没有快速的质数因数分解方法，而逐个尝试的话，计算量是可怕的。
当n足够大时，这其中的计算量，可能需要几年时间，这完全可以认为是安全的了。
这里为了描述方便，称上面公开的n为“公开信息”，称e为“公钥”，d为“私钥”。
我们设原文为m，加密后的密文为c，求余运算用%表示，那么：
加密过程c=(m^e)%n，
解密过程m=(c^d)%n。
可能你已经发现了，这个方法，只能用来加密数字，而且数字必须要比n小。
由于需要足够的加密强度，牛郎的p和q都取了十位数，那么n是个接近20位的数字，一般数字都会比它小。
这并不难，因为之前牛郎已经设计了字典，每个字在字典中的索引，都可以表示为数字。
一切准备就绪，是不是可以开始了呢？
是的。但是也要考虑，牛郎现在要将加密思路给织女讲一遍，这个是可能被王母窃听的。
所以，需要提前做一点准备。
牛郎先是个织女发了一封“公开的”私信，内容很简单：“静观其变”。
接着，
牛郎用之前的随机算法，加上“费马小定理”，得到了长度为一百位的素数p和q。
对，你没看错，牛郎想要绝对的安全，所以花了3天时间，真的找到了两个一百位长的素数。
接着，牛郎计算出了公开信息n和公钥e，将这两者通过喜鹊网络，广播了出去。
没错，就是广播，所有人都会收到的那种，包括王母：
牛郎
n
e
只有短短的三行，一行文字，两行数字。
最后，牛郎又给织女发了一封“公开的”私信：“静观其变”。
织女没有回复。三天以后，牛郎的两行数字到底代表什么，众说纷纭，整个天庭里传的沸沸扬扬。
而也有一些打探到小道消息的人，说牛郎给织女发过“静观其变”，很可能这个专门做给王母看的，想引诱王母出手。
但具体想要王母出手做什么呢？没人能猜得到。
其实，牛郎的目的，已经达到一半了。
虽然现在没有人知道自己的加密算法，但自己的公钥已经是众人皆知，无法被篡改的了。
换句话说，牛郎出其不意地让织女拿到了“绝对是来自牛郎的公钥”，规避了王母冒充自己的风险。
而且，织女只要用这个公钥加密，信息就只有牛郎能够解密，这就保证了安全。
但是很可惜，目前算法只有自己知道，所以自己才可以再众人毫不知情状态下发送广播。
一旦算法公开，很可能下一个人也会广播：织女 n e ，
只是，这个信息，真的是来自织女还是其他人伪造的，就不得而知了。
所以说，我们，算是成功了一半。
怎么才能在王母毫无反应的情况下，拿到织女的公钥呢？
这个已经超出数学领域了，可能需要一点心理学上的技巧。
于是牛郎修书一封：
织女：
我已找到了万全的加密方法，此法仅你能解。
全网广播就是为了气气王母，让她什么都知道却就是解不出来。
第一行是两个素数的积，而这两个素数都不大于第二行的数字。
这两个素数的最后两位，就是约定见面的日期。
盼十天之内回复。
可想而知，织女收到了信件，而王母自然也监听到了一份备份。
王母看了信件，明白牛郎织女的通信可能进入最后日期的沟通阶段了。
但这牛郎很嚣张呀，这么简单的事情，还能难得到我王母？
既然这样，这牛郎是不是有什么“话外之音”要传递？
万一牛郎明面上是说这个，实际上在偷偷暗示织女另一个时间，该怎么办？
于是王母赶紧找来语言分析师深入分析。
一群专家讨论了一天，并没发现什么特别之处，都是瞎猜。
这时，有人提出：
“最危险的地方就是最安全的地方，万一牛郎就是利用了王母您的多疑，然后真的就与织女定了这个时间呢？”
王母沉思，觉得也有可能。这样的话，先求出这两个素数，看看最后两位是什么。
很可能秘密就在其中。
王母赶紧召集自己的部下：“巴戈，解密这事就交个你了，明天告诉我结果。”
大将巴戈领旨后，觉得不难，随便派了几个部下计算。结果，第二天，竟然还没算出来。
巴戈急了，赶紧命令麾下所有将士一起计算，务必完成王母任务。
可惜，还是失败了。夜里，巴戈垂头丧气地向王母汇报：“属下无能，属下求不出来。”
王母这才意识到问题的严重性，看来，很可能牛郎真的用了这两个素数。
突然，王母一拍桌子：“坏了，牛郎大概利用了我的大意，想打时间差，十天可能是个幌子。”
接着，王母有镇定下来：
“牛郎啊牛郎”王母自言自语，“你这题目虽难，但天庭人才辈出，可不是吃素的。”
“传令，召集天庭数学专家，争取3天之内解决问题！”
“就算织女再快，也终究是一个人，不可能超过我这一群专家的。”
专家们整整想了3天，并无找到解决方案。
最终，专家们只得派代表想王母请罪：“王母息怒，臣等无法解答。”
这让王母怎么息怒：“一群废物！这都五天过去了，都让你们耽误了！”
数学专家说：“虽然我们解不出来，但是我们可以肯定，织女也解不出来。”
王母满是疑惑：“为什么？”
“因为，质因数分解只能逐个试商，就算集合整个天庭之力，也至少要计算百年。”
王母再次拍桌子：“既然是无解的问题，你们怎么不早说！”
“那您也没早问呀……”
忽然大殿之外传来喊声：“报——”
一名探子快步走入堂前，呈上文书：“下午织女发起了全网广播，怕是牛郎也已经收到了。”
王母打开文书，只见上面写着：
牛郎：
我思索3天自认为算不出来，你既来信，必有解答之法。
我按你的格式，将日期藏在质数后两位，并计算得到了2个数字 n e，
现在换你来求解日期了呢~
王母不甘心，同时也觉得牛郎不可能比自己的专家都厉害。
王母把新的文书扔给专家代表：“再给你们三天，解不出来就不用回来了。”
- 版权说明：
文章内容系作者原创，转载请注明出处。 - 封面图片：
印象笔记素材-密码锁
图片源自网络，如有侵权，可联系作者删除。 - 拓展资料：
百度百科-RSA
百度百科-公钥
百度百科-私钥
百度百科-非对称加密
网友评论