$$ 05 $$

　　是的，当牛郎与织女想到的数字变大时，与监听者的计算量的差距也会变大。

　　当计算量差异超过王母一年的总算力，那么，就可以认为，这是一次安全的秘钥传递了。

　　牛郎已经发现了，计算量差值其实大致是自己与织女两个数字的和。

　　也就是说，要确保安全的话，两个人使用的数字，要与秘钥类似，都是十位的。

　　·

　　这里，其实有个“指数爆炸”问题，我们知道，假如以2为底数，那么2^10=1024，如果是2^30，就已经是上亿的数字了。

　　如果指数是一个十位的数字，那么，结果的大小可想而知，能绕地球好几圈了吧？

　　·

　　这改怎么办呢？其实也简单，求余数就是了。找一个十位数作为除数，那么不管前置的数字多大，最后得到的余数，至多是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更好。

　　那么，看起来偶数不如奇数。当然，这里为了效果更好，牛郎想选择：素数。

　　·

　　----

　　$$ 06 $$

　　确实，经过牛郎多次推算，素数（即质数，除了1和它本身以外不再有其他因数的自然数）确实是做除数最好的材料，因为它可以保证余数尽可能均衡分布。

　　问题总是环环相扣，解决了一个问题，又出现一个新的问题。

　　那就是：如何生成一个十位的素数呢？

　　牛郎想了很多办法，很可惜，这是不太可能的。

　　·

　　但是后来，牛郎天才地想到一种方式，可以判断一个数“大概率是素数”。

　　虽然不能完美得到素数，但是若是用作除数的话，应该会比大部分随机选择的数字要好，还是勉强可以用一下的。

　　具体是怎么样的呢？

　　·

　　加入一个数p是质数，随便找个比它小的数a，则a^p-a可以被p整除。

　　很简单是不是？只是由于p比较大，所以a^p这一步计算起来稍微耗时一些。

　　“这也太浪费时间浪费人力了吧？”牛郎吐槽道，“我是牛郎，这不是浪费人力，是浪费牛力。”

　　忽然，牛郎转念一想，不如就叫“费牛算法”吧。

　　“不过‘牛’可能不太合适，换做‘马’怎么样？而且数学上的东西用‘算法’也不太好，这事也不是很难，不如叫‘小定理’吧。”

　　于是，这个方式有了一个响亮的名字：“费马小定理”。

　　·

　　只是，这个定理是充分不必要的，也就是说，如果p是质数，那么一定满足该定理。

　　但如果p不是质数，那么也可能该定理。

　　也就是说，如果满足了该定理，那么p大概率是质数，当然也可能不是。

　　但如果不满足该定理，可以确定，p一定不是质数。

　　好吧，虽然不完美，但是，将就着用吧。

　　·

　　----

　　$$ 07 $$

　　接着探讨下一个问题：底数应该选择多少呢？

　　原则上，我们肯定是想让计算得到的结果，更具有随机性，这样才能保证攻击者反推的难度。

　　当然，因为指数是个十位的数字，所以底数越大，计算量也越大。

　　因此，要在自己的计算量与破解难度之间，进行一个权衡。

　　·

　　牛郎想到一个方法，既然素数选择了p，那么，可以在小于p的数中，找这样一个数a：

　　从a的1次方，a的2次方，一直到a的p-1次方，这所有的数字除以p得到的余数，都不相同。

　　·

　　是不是有点苛刻了？但是，这样的到的数字，确实可以保证乘方结果的均匀。

　　这个数字真的存在吗？理论上一定存在的，牛郎在一本“古书”上得知。

　　但是，要求出这个数，可能没有速算的方法，只能从2开始，一个一个验证，总会找到的。

　　看来，要得到它，计算量简直跟原始森林里的树根一样繁杂，就叫它“原根”吧。

　　·

　　没办法，计算量还是有些过大，牛郎知难而退，选择了放弃原根策略，“随便”选择一个底数。

　　选谁好呢？为了计算简便，就选个十以内的数字吧。

　　既然前面一直在说素数，那就选择十以内最大的素数吧。

　　就这样，底数“7”应运而生。

　　·

　　接着，牛郎开始寻找大素数p。有仙术的助力，这个也不难。

　　牛郎取出32枚硬币，他也不知道为什么要用32枚，总觉得这个数字比较吉利。

　　同时抛出，落地，按顺序收集，正面表示1，反面表示0，最后转换为十进制，就得到一个“随机数”了。

　　接着用“费马小定理”验证就好，不符合就重来，直到找出一个合适的数字p。

　　·

　　----

　　$$ 08 $$

　　有了底数7和合适的除数p，牛郎决定与织女进项首次秘钥交换。

　　牛郎先把自己的想法详细记录下来，告诉织女，同时也附带了底数7和除数p。

　　接着，牛郎和织女各自生成了一个十位的随机数，互相保密，假定牛郎的随机数是a，织女的随机数是b。

　　牛郎计算出A=(7^a%p)，织女计算出B=(7^b%p)，这里为了表示方便，%为求余操作，%p代表除以p得到的余数。

　　·

　　接着，牛郎和织女交换A和B这两个值。

　　然后，牛郎计算S=B^a%p，织女计算S=A^b%p，从而两人得到相关的秘钥S。

　　此时，网络上传递的有A B p和底数7，但是，监听者由于缺少a b，因此无法推算出秘钥S。

　　而需要破解的话，之前也论证过，时间至少需要一年，因此可以认为这是一个“别人都不知道”的秘钥。

　　·

　　虽然拿到了秘钥S，但是，牛郎与织女也发现了一个问题：整个交换过程，无法认证对方身份。

　　比如，站在牛郎视角，他并不知道对方是王母还是织女。

　　如果王母也想到了这一点，那么他就可以冒充织女身份，与牛郎产生秘钥。

　　这样，牛郎发的信息，王母就全能看到了。

　　·

　　那么，织女收不到消息，岂不是王母就暴露了？不会的，王母再冒充牛郎，与织女产生秘钥。

　　于是，牛郎发的消息，王母解密阅读后，在用织女的秘钥重新加密，转发给织女，神不知鬼不觉。

　　而王母，则悄悄成为了整个通信过程中的“中间人”，无需去破解秘钥，却可以拿到信息。

　　·

　　想到这里，这个看似完美的方案，终是不得不匆匆画上句号。

　　没事，提前发现了问题，就还有解决问题的机会，看来加密这块儿，还是要仔细想想了。