$$ 05 $$
是的，當(dāng)牛郎與織女想到的數(shù)字變大時(shí)，與監(jiān)聽者的計(jì)算量的差距也會(huì)變大。
當(dāng)計(jì)算量差異超過(guò)王母一年的總算力，那么，就可以認(rèn)為，這是一次安全的秘鑰傳遞了。
牛郎已經(jīng)發(fā)現(xiàn)了，計(jì)算量差值其實(shí)大致是自己與織女兩個(gè)數(shù)字的和。
也就是說(shuō)，要確保安全的話，兩個(gè)人使用的數(shù)字，要與秘鑰類似，都是十位的。
·
這里，其實(shí)有個(gè)“指數(shù)爆炸”問(wèn)題，我們知道，假如以2為底數(shù)，那么2^10=1024，如果是2^30，就已經(jīng)是上億的數(shù)字了。
如果指數(shù)是一個(gè)十位的數(shù)字，那么，結(jié)果的大小可想而知，能繞地球好幾圈了吧？
·
這改怎么辦呢？其實(shí)也簡(jiǎn)單，求余數(shù)就是了。找一個(gè)十位數(shù)作為除數(shù)，那么不管前置的數(shù)字多大，最后得到的余數(shù)，至多是10位數(shù)字。
那么，這個(gè)除數(shù)可以隨便找嗎？
我們當(dāng)然希望，余數(shù)能更均衡地分布。如果被除數(shù)能均勻分布的話，那么自然除數(shù)選擇什么都一樣了。
但有趣的是，偶數(shù)的平方都是偶數(shù)，奇數(shù)的平法也都是奇數(shù)。
·
也沒(méi)想太多，牛郎舉了個(gè)簡(jiǎn)單的例子：
先是偶數(shù)列：2 4 6 8 10 12，如果以8為除數(shù)，余數(shù)為：2 4 6 0 2 4，只有4種。若以7為除數(shù)，余數(shù)為：2 4 6 1 3 5，有6種，顯然7更好。
純奇數(shù)列的話：3 5 7 9 11 13，以8為除數(shù)，余數(shù)：3 5 7 1 3 5，還是4種。若以7為除數(shù)，余數(shù)為：3 5 0 2 4 6，共6種，還是7更好。
那么，看起來(lái)偶數(shù)不如奇數(shù)。當(dāng)然，這里為了效果更好，牛郎想選擇：素?cái)?shù)。
·
----
$$ 06 $$
確實(shí)，經(jīng)過(guò)牛郎多次推算，素?cái)?shù)（即質(zhì)數(shù)，除了1和它本身以外不再有其他因數(shù)的自然數(shù)）確實(shí)是做除數(shù)最好的材料，因?yàn)樗梢员ＷC余數(shù)盡可能均衡分布。
問(wèn)題總是環(huán)環(huán)相扣，解決了一個(gè)問(wèn)題，又出現(xiàn)一個(gè)新的問(wèn)題。
那就是：如何生成一個(gè)十位的素?cái)?shù)呢？
牛郎想了很多辦法，很可惜，這是不太可能的。
·
但是后來(lái)，牛郎天才地想到一種方式，可以判斷一個(gè)數(shù)“大概率是素?cái)?shù)”。
雖然不能完美得到素?cái)?shù)，但是若是用作除數(shù)的話，應(yīng)該會(huì)比大部分隨機(jī)選擇的數(shù)字要好，還是勉強(qiáng)可以用一下的。
具體是怎么樣的呢？
·
加入一個(gè)數(shù)p是質(zhì)數(shù)，隨便找個(gè)比它小的數(shù)a，則a^p-a可以被p整除。
很簡(jiǎn)單是不是？只是由于p比較大，所以a^p這一步計(jì)算起來(lái)稍微耗時(shí)一些。
“這也太浪費(fèi)時(shí)間浪費(fèi)人力了吧？”牛郎吐槽道，“我是牛郎，這不是浪費(fèi)人力，是浪費(fèi)牛力?！?p> 忽然，牛郎轉(zhuǎn)念一想，不如就叫“費(fèi)牛算法”吧。
“不過(guò)‘?！赡懿惶线m，換做‘馬’怎么樣？而且數(shù)學(xué)上的東西用‘算法’也不太好，這事也不是很難，不如叫‘小定理’吧?！?p> 于是，這個(gè)方式有了一個(gè)響亮的名字：“費(fèi)馬小定理”。
·
只是，這個(gè)定理是充分不必要的，也就是說(shuō)，如果p是質(zhì)數(shù)，那么一定滿足該定理。
但如果p不是質(zhì)數(shù)，那么也可能該定理。
也就是說(shuō)，如果滿足了該定理，那么p大概率是質(zhì)數(shù)，當(dāng)然也可能不是。
但如果不滿足該定理，可以確定，p一定不是質(zhì)數(shù)。
好吧，雖然不完美，但是，將就著用吧。
·
----
$$ 07 $$
接著探討下一個(gè)問(wèn)題：底數(shù)應(yīng)該選擇多少呢？
原則上，我們肯定是想讓計(jì)算得到的結(jié)果，更具有隨機(jī)性，這樣才能保證攻擊者反推的難度。
當(dāng)然，因?yàn)橹笖?shù)是個(gè)十位的數(shù)字，所以底數(shù)越大，計(jì)算量也越大。
因此，要在自己的計(jì)算量與破解難度之間，進(jìn)行一個(gè)權(quán)衡。
·
牛郎想到一個(gè)方法，既然素?cái)?shù)選擇了p，那么，可以在小于p的數(shù)中，找這樣一個(gè)數(shù)a：
從a的1次方，a的2次方，一直到a的p-1次方，這所有的數(shù)字除以p得到的余數(shù)，都不相同。
·
是不是有點(diǎn)苛刻了？但是，這樣的到的數(shù)字，確實(shí)可以保證乘方結(jié)果的均勻。
這個(gè)數(shù)字真的存在嗎？理論上一定存在的，牛郎在一本“古書”上得知。
但是，要求出這個(gè)數(shù)，可能沒(méi)有速算的方法，只能從2開始，一個(gè)一個(gè)驗(yàn)證，總會(huì)找到的。
看來(lái)，要得到它，計(jì)算量簡(jiǎn)直跟原始森林里的樹根一樣繁雜，就叫它“原根”吧。
·
沒(méi)辦法，計(jì)算量還是有些過(guò)大，牛郎知難而退，選擇了放棄原根策略，“隨便”選擇一個(gè)底數(shù)。
選誰(shuí)好呢？為了計(jì)算簡(jiǎn)便，就選個(gè)十以內(nèi)的數(shù)字吧。
既然前面一直在說(shuō)素?cái)?shù)，那就選擇十以內(nèi)最大的素?cái)?shù)吧。
就這樣，底數(shù)“7”應(yīng)運(yùn)而生。
·
接著，牛郎開始尋找大素?cái)?shù)p。有仙術(shù)的助力，這個(gè)也不難。
牛郎取出32枚硬幣，他也不知道為什么要用32枚，總覺得這個(gè)數(shù)字比較吉利。
同時(shí)拋出，落地，按順序收集，正面表示1，反面表示0，最后轉(zhuǎn)換為十進(jìn)制，就得到一個(gè)“隨機(jī)數(shù)”了。
接著用“費(fèi)馬小定理”驗(yàn)證就好，不符合就重來(lái)，直到找出一個(gè)合適的數(shù)字p。
·
----
$$ 08 $$
有了底數(shù)7和合適的除數(shù)p，牛郎決定與織女進(jìn)項(xiàng)首次秘鑰交換。
牛郎先把自己的想法詳細(xì)記錄下來(lái)，告訴織女，同時(shí)也附帶了底數(shù)7和除數(shù)p。
接著，牛郎和織女各自生成了一個(gè)十位的隨機(jī)數(shù)，互相保密，假定牛郎的隨機(jī)數(shù)是a，織女的隨機(jī)數(shù)是b。
牛郎計(jì)算出A=(7^a%p)，織女計(jì)算出B=(7^b%p)，這里為了表示方便，%為求余操作，%p代表除以p得到的余數(shù)。
·
接著，牛郎和織女交換A和B這兩個(gè)值。
然后，牛郎計(jì)算S=B^a%p，織女計(jì)算S=A^b%p，從而兩人得到相關(guān)的秘鑰S。
此時(shí)，網(wǎng)絡(luò)上傳遞的有A B p和底數(shù)7，但是，監(jiān)聽者由于缺少a b，因此無(wú)法推算出秘鑰S。
而需要破解的話，之前也論證過(guò)，時(shí)間至少需要一年，因此可以認(rèn)為這是一個(gè)“別人都不知道”的秘鑰。
·
雖然拿到了秘鑰S，但是，牛郎與織女也發(fā)現(xiàn)了一個(gè)問(wèn)題：整個(gè)交換過(guò)程，無(wú)法認(rèn)證對(duì)方身份。
比如，站在牛郎視角，他并不知道對(duì)方是王母還是織女。
如果王母也想到了這一點(diǎn)，那么他就可以冒充織女身份，與牛郎產(chǎn)生秘鑰。
這樣，牛郎發(fā)的信息，王母就全能看到了。
·
那么，織女收不到消息，豈不是王母就暴露了？不會(huì)的，王母再冒充牛郎，與織女產(chǎn)生秘鑰。
于是，牛郎發(fā)的消息，王母解密閱讀后，在用織女的秘鑰重新加密，轉(zhuǎn)發(fā)給織女，神不知鬼不覺。
而王母，則悄悄成為了整個(gè)通信過(guò)程中的“中間人”，無(wú)需去破解秘鑰，卻可以拿到信息。
·
想到這里，這個(gè)看似完美的方案，終是不得不匆匆畫上句號(hào)。
沒(méi)事，提前發(fā)現(xiàn)了問(wèn)題，就還有解決問(wèn)題的機(jī)會(huì)，看來(lái)加密這塊兒，還是要仔細(xì)想想了。