七夕缘起-第5.2章-秘钥交换的策略
目前虽然有了不错的加密方法，但这秘钥，确实还是个难题。
而且，同一个秘钥，使用的时间也不能太长，否则一旦被破解出来，那么通信就会变得很不安全。
现在，牛郎需要想一种能够快速安全交换秘钥的方式。
这个的难点在于，目前要尽量避免使用隐私信息。
现在牛郎织女不能见面，两人共同知晓的隐秘信息终是有限的，用一个少一个，所以，这些最好先留着，作为以后的“王牌”。
那么，如果使用现有的秘钥，进行加密传递呢？
也不行，那跟明文没什么区别。
试想，一旦哪一天，这个旧的秘钥泄露了或者被破解了出来，那么，王母就能顺藤摸瓜，得到新的秘钥值。
尤其是现在加密方法刚刚是初级阶段，目前只有一个“见面日期”的秘钥，破解难度自然没有那么高，简直就是明文。
所以说，这个新的秘钥，还不能依赖现有的秘钥，也就是“绝对独立”的。
而且，加密和解密需要相同的秘钥，这就是牛郎目前最大的挑战了：
如何在全程明文传输的情况下，（刚才说了，加密没有意义），
让双方得到相同的秘钥，但其他人却不知道该秘钥。
很显然，由一方传递给另一方，显然是行不通的了，这样途中所有的监听者都会知道秘钥。
是不是觉得“比登天还难”了？既然都全程明文了，还怎么让别人“不知道”？
不过，仔细想一想，好像还真是有可能的。
毕竟，我们并不需要像写加密信件一样传递太多信息。
要做的，仅仅是需要双方拿到一个秘钥而已，再直白一点，那就是个长度为十位的自然数罢了。
像个办法，让双方得到一个相同的十位数，很难么？不难。
那如何在不使用隐秘信息的情况下，让别人不知道呢？
这个么，其实也是有可能做到的。
想想之前加密时，提到的“加密强度”：
“按目前王母的实力，只要加密算法在3亿次尝试之内无法被解密，那么，就可以认为它是安全的。”
也就是说，如果能有一种方式，将运算差异化，让双方能够快速计算出结果，
但是其他人则需要超过3亿以上次运算，那么，就可以实现安全的秘钥交换。
当然，这样，就不是简单的加密领域了，而是，需要去想一些数学方法。
牛郎在喜鹊仙子的帮助下，翻阅了古往今来数学领域的各种著作，突然发现了一种相对单向的运算：
计算一个数的乘方，是有速算方法的，但是，反过来求其逆运算，基本没有速算方式。
举个例子，计算2的4次方，正常是4次乘法，2x2x2x2=16，
但其实它等价与2的平方的平方，2x2=4，4x4=16，只要2次乘法就能算出来。
但如果想计算2的几次方等于16，那么要16不断除以2直到值为1，然后看除了几次，
即16/2=8，8/2=4，4/2=2，2/2=1，需要4次除法运算，是基本没有优化空间的。
看来，这应该就是本次秘钥交换的核心了。
只要能找到一种数学方法，形成算法上的隔离，
让自己和织女能通过乘方速算法计算秘钥，而监听者们只能通过乘方逆运算或者枚举求解，
当两者的计算量的差距足够大时，那么就可以认为拿到了一个相对安全的秘钥。
唉，这个乘方的逆运算，叫起来太不顺口了，反正都是对数字的运算，要不就简称“对数”计算吧。
现在，算法的思想有了，接下来又出现了另一个难点：怎么去形成这种算法生的隔离呢？
如果所有人拿到的信息都一样，那么所有人肯定可以用相同的算法去计算，所以，必然要创造信息上的差异。
让自己和织女的信息，能够用乘方速算，但其他监听者，却只能用较慢的对数计算。
只是，要引入信息差异，但还不能引入双方都知道的隐私信息，这改怎么办？
哈哈，既然“双方都知道的信息”很有限，不能随便用，那“仅有单方知道的信息”，应该是近乎无限的吧？
比如说，引入“只有牛郎知道的信息”，让织女不知道该信息也能算出秘钥，但其他人却不行。
但是，这可能吗？
这确实有可能，因为织女有“只有织女知道的信息”，也就是牛郎织女比其他监听者知道的多。
只要像个办法，让“只有单方面知道的信息”，即参与了运算，又能互相湮灭，就足够了。
而中间的监听者，因为不知道双方信息湮灭后的产物，要计算秘钥，或者反推双方的信息，还是很有难度的。
那么，这就是个数学上要处理的问题了。
具体要怎么处理呢？该回到刚才我们说的“乘方运算”了。
比如牛郎想到一个数3，织女想到一个数4，互不告诉对方。
约定以2位底数算乘方，牛郎得到23=8，织女得到24=16，把这个数告诉对方。
此时，织女无需知道牛郎想到的是几，只要计算84=4096，而牛郎也只需要计算163=4096。
由此，双方不需要知道对方的数字，却可以拿到相同的秘钥：4096。
让我们看看，王母安排的监听者们，会得到哪些信息：双方约定的底数2，牛郎发送的8，织女发送的16。
因为只有这3个数在途中传递了，其他信息没有被传递，监听者是不知道的。
那么，这些监听者们，能通过已知的这3个数，得到秘钥4096吗？
答案是“能”。
因为，知道底数2，知道牛郎发送的数字8，那么，2的几次方是8呢？
这个很容易计算，因此他们完全可以反推出，牛郎想到的数字，是3。
同理，他们也能反推出，织女想到的数字是4。
那这个方法有什么用？
重点来了，刚才监听者们反推牛郎织女的数字，是需要时间计算的。
我们提供，对数运算基本没有优化空间，所以要得到3和4，他们至少需要3+4=7次计算。
这就是监听者比牛郎织女多做的事情，怎么样，有思路了吧？
是的，当牛郎与织女想到的数字变大时，与监听者的计算量的差距也会变大。
当计算量差异超过王母一年的总算力，那么，就可以认为，这是一次安全的秘钥传递了。
牛郎已经发现了，计算量差值其实大致是自己与织女两个数字的和。
也就是说，要确保安全的话，两个人使用的数字，要与秘钥类似，都是十位的。
这里，其实有个“指数爆炸”问题，我们知道，假如以2为底数，那么210=1024，如果是230，就已经是上亿的数字了。
如果指数是一个十位的数字，那么，结果的大小可想而知，能绕地球好几圈了吧？
这改怎么办呢？其实也简单，求余数就是了。找一个十位数作为除数，那么不管前置的数字多大，最后得到的余数，至多是10位数字。
那么，这个除数可以随便找吗？
我们当然希望，余数能更均衡地分布。如果被除数能均匀分布的话，那么自然除数选择什么都一样了。
但有趣的是，偶数的平方都是偶数，奇数的平法也都是奇数。
也没想太多，牛郎举了个简单的例子：
先是偶数列：2 4 6 8 10 12，如果以8为除数，余数为：2 4 6 0 2 4，只有4种。若以7为除数，余数为：2 4 6 1 3 5，有6种，显然7更好。
纯奇数列的话：3 5 7 9 11 13，以8为除数，余数：3 5 7 1 3 5，还是4种。若以7为除数，余数为：3 5 0 2 4 6，共6种，还是7更好。
那么，看起来偶数不如奇数。当然，这里为了效果更好，牛郎想选择：素数。
确实，经过牛郎多次推算，素数（即质数，除了1和它本身以外不再有其他因数的自然数）确实是做除数最好的材料，因为它可以保证余数尽可能均衡分布。
问题总是环环相扣，解决了一个问题，又出现一个新的问题。
那就是：如何生成一个十位的素数呢？
牛郎想了很多办法，很可惜，这是不太可能的。
但是后来，牛郎天才地想到一种方式，可以判断一个数“大概率是素数”。
虽然不能完美得到素数，但是若是用作除数的话，应该会比大部分随机选择的数字要好，还是勉强可以用一下的。
具体是怎么样的呢？
加入一个数p是质数，随便找个比它小的数a，则a^p-a可以被p整除。
很简单是不是？只是由于p比较大，所以a^p这一步计算起来稍微耗时一些。
“这也太浪费时间浪费人力了吧？”牛郎吐槽道，“我是牛郎，这不是浪费人力，是浪费牛力。”
忽然，牛郎转念一想，不如就叫“费牛算法”吧。
“不过‘牛’可能不太合适，换做‘马’怎么样？而且数学上的东西用‘算法’也不太好，这事也不是很难，不如叫‘小定理’吧。”
于是，这个方式有了一个响亮的名字：“费马小定理”。
只是，这个定理是充分不必要的，也就是说，如果p是质数，那么一定满足该定理。
但如果p不是质数，那么也可能该定理。
也就是说，如果满足了该定理，那么p大概率是质数，当然也可能不是。
但如果不满足该定理，可以确定，p一定不是质数。
好吧，虽然不完美，但是，将就着用吧。
接着探讨下一个问题：底数应该选择多少呢？
原则上，我们肯定是想让计算得到的结果，更具有随机性，这样才能保证攻击者反推的难度。
当然，因为指数是个十位的数字，所以底数越大，计算量也越大。
因此，要在自己的计算量与破解难度之间，进行一个权衡。
牛郎想到一个方法，既然素数选择了p，那么，可以在小于p的数中，找这样一个数a：
从a的1次方，a的2次方，一直到a的p-1次方，这所有的数字除以p得到的余数，都不相同。
是不是有点苛刻了？但是，这样的到的数字，确实可以保证乘方结果的均匀。
这个数字真的存在吗？理论上一定存在的，牛郎在一本“古书”上得知。
但是，要求出这个数，可能没有速算的方法，只能从2开始，一个一个验证，总会找到的。
看来，要得到它，计算量简直跟原始森林里的树根一样繁杂，就叫它“原根”吧。
没办法，计算量还是有些过大，牛郎知难而退，选择了放弃原根策略，“随便”选择一个底数。
选谁好呢？为了计算简便，就选个十以内的数字吧。
既然前面一直在说素数，那就选择十以内最大的素数吧。
就这样，底数“7”应运而生。
接着，牛郎开始寻找大素数p。有仙术的助力，这个也不难。
牛郎取出32枚硬币，他也不知道为什么要用32枚，总觉得这个数字比较吉利。
同时抛出，落地，按顺序收集，正面表示1，反面表示0，最后转换为十进制，就得到一个“随机数”了。
接着用“费马小定理”验证就好，不符合就重来，直到找出一个合适的数字p。
有了底数7和合适的除数p，牛郎决定与织女进项首次秘钥交换。
牛郎先把自己的想法详细记录下来，告诉织女，同时也附带了底数7和除数p。
接着，牛郎和织女各自生成了一个十位的随机数，互相保密，假定牛郎的随机数是a，织女的随机数是b。
牛郎计算出A=(7a%p)，织女计算出B=(7b%p)，这里为了表示方便，%为求余操作，%p代表除以p得到的余数。
接着，牛郎和织女交换A和B这两个值。
然后，牛郎计算S=Ba%p，织女计算S=Ab%p，从而两人得到相关的秘钥S。
此时，网络上传递的有A B p和底数7，但是，监听者由于缺少a b，因此无法推算出秘钥S。
而需要破解的话，之前也论证过，时间至少需要一年，因此可以认为这是一个“别人都不知道”的秘钥。
虽然拿到了秘钥S，但是，牛郎与织女也发现了一个问题：整个交换过程，无法认证对方身份。
比如，站在牛郎视角，他并不知道对方是王母还是织女。
如果王母也想到了这一点，那么他就可以冒充织女身份，与牛郎产生秘钥。
这样，牛郎发的信息，王母就全能看到了。
那么，织女收不到消息，岂不是王母就暴露了？不会的，王母再冒充牛郎，与织女产生秘钥。
于是，牛郎发的消息，王母解密阅读后，在用织女的秘钥重新加密，转发给织女，神不知鬼不觉。
而王母，则悄悄成为了整个通信过程中的“中间人”，无需去破解秘钥，却可以拿到信息。
想到这里，这个看似完美的方案，终是不得不匆匆画上句号。
没事，提前发现了问题，就还有解决问题的机会，看来加密这块儿，还是要仔细想想了。
- 版权说明：
文章内容系作者原创，转载请注明出处。 - 封面图片：
印象笔记素材-黑洞
图片源自网络，如有侵权，可联系作者删除。 - 拓展资料：
百度百科-DH秘钥交换算法
博客园-DH算法理解
MyWord-大数模幂算法
知乎-离散对数难题
百度百科-费马小定理
百度百科-中间人攻击
网友评论