自古以來，程式設計師就以三高聞名於相親市場，廣受丈母孃歡迎。
哪三高？收入高、截留率高、死亡率高。
此話怎講？
-
快二十年前程式設計師的月工資就可以過萬，這在當時是一個很了不起的數目。即便是遍地程式設計師的今天，在牛馬當中程式設計師的工資也是數一數二的，尤其是會做AI、懂ML的程式設計師。
-
大部分程式設計師沒有什麼奢侈的愛好，除了加班就是聯網打打 Dota，花不了幾個錢，剩下的都交給老婆。
-
因為精神壓力大，程式設計師中年禿頂是標配，過勞死屢見不鮮，方便老婆帶著存款開啟人生第二春。
要是《白鹿原》寫的是 IT 界，開篇應該是這樣的：
“田小娥後來引以為豪壯的是一生裡嫁過七個程式設計師。”
當然以上是程式設計師在自黑。程式設計師可能是歷史上最喜歡自黑的群體。比如他們有這麼一個段子：世界上有兩種科學，一種是科學，另一種是計算機科學。
大家嘿嘿一笑之餘，不要忘了這只是一個段子。計算機科學可不光可以幫你寫個搶票網站，堆個小遊戲。它也和其它自然科學一樣博大精深。
做為數學的一個分支，計算機科學凝聚了無數先賢的智慧，有很多精妙絕倫美輪美奐，讓人讚不絕口驚為天人的設計和思想。今天我就來講一講密碼學中讓我驚豔的一個演算法：迪菲-赫爾曼（Diffie-Hellman）金鑰交換演算法。
～～～～
大家可能注意到，有的網站網址是http開頭的，有的是https。有沒有這個 s 有什麼區別呢？
這裡的 s 是 secure（安全）的意思。有小s，表示你的機器跟這個伺服器之間的通訊是安全的，不怕旁人偷聽。比如說你在這個網站上填自己的身份資訊，用 https 方式傳送旁人就看不見你填的是啥。
你有沒有想過這是怎麼做到的？
還能怎樣？加密唄。
很好。那你有沒有想過是用什麼金鑰加密的呢？
你連上這個網站的時候，系統並沒有諮詢過你“尊敬的客戶，請問我們接下來的私密對話該用什麼金鑰？”所以這個金鑰肯定不是你選的。
也不是你的瀏覽器替你選的。要是瀏覽器選了一個金鑰 k 然後告訴網站“接下來咱倆的通訊用 k 加密吧”，壞人偷聽到這條訊息不就可以冒充你或者網站了嗎？
同樣，也不可能是網站選的。
更不可能是在瀏覽器和網站的程式碼裡事先固定的。這樣很多人都有機會知道這個金鑰，毫無安全可言。
所以，為了安全起見，https 協議要在每次建立一個新連線前，讓瀏覽器和網站透過不安全的通道商量出一個秘密，而這個秘密只有它們雙方知道，其他任何人都不知道 — 哪怕他們偷聽了全部商量過程。
等等！陽光之下沒有秘密。這怎麼可能？
迪菲-赫爾曼（Diffie-Hellman）演算法就可以完成這個貌似不可能的任務。
在計算機密碼學研究中，為了生動起見，經常把互動的雙方叫做愛麗絲（Alice）和鮑勃（Bob）。這種做法相當於在中文中把丫鬟甲和宋兵乙換成李嘉欣和周星馳，可以讓正在讀文的同學虎軀一震，走出半夢半醒。
據說，這一招是發明 RSA 加密演算法的三巨頭想出來的。
不得不說這些大佬是懂營銷的。擱在今天，絕對是百萬大V。
好了，我們就借用愛麗絲和鮑勃來講這個故事。因為待會兒要出現公式，為了預防讀者划走，我特地引入了三角戀和暴力，還在文末留了兩個八卦，請大家別走，堅持看完！
愛麗絲和鮑勃是一對高中生情侶，他們彼此愛你在心口難開。難開口是因為隔牆有耳，這個耳就是愛麗絲的情敵伊芙（Eve）。
順便講一句，在密碼學研究中，偷聽者這個角色通常是由伊芙扮演的，因為 Eve 和偷聽（eavesdropper）諧音。
想不到啊想不到，濃眉大眼的計算機科學家也喜歡諧音梗。
這個伊芙不但是個戀愛腦，而且天賦異稟，愛麗絲和鮑勃的任何對話她都有辦法聽到。要是這兩人的情話有啥地方刺激到了她，保不齊她一時衝動就讓愛麗絲血濺當場。
愛麗絲的高中計算機課的老師邁克爾看在眼裡，疼在心裡，於是給大家加了一堂計算機密碼學課程，讓愛麗絲鮑勃茅塞頓開，從此可以不懼伊芙，在光天化日之下聊騷。
這是怎麼做到的呢？
在下面的解說中，公開的訊息用藍字表示，未公開的秘密則用紅字。
首先愛麗絲和鮑勃選了一個很大的，有幾百位的素數 p，又隨便選了一個也很大的正整數 g。整個過程都廣而告之，所以我們可以假定伊芙對這兩個數也是心知肚明。
然後，愛麗絲選了一個秘密正整數 a，這秘密埋藏在她心裡，誰都不告訴。連鮑勃都不知道這個數，伊芙自然也不知道。
同樣，鮑勃也想了一個秘密正整數 b，這個秘密他也守口如瓶。
然後他們各自做了一個計算，然後公佈了計算結果。
愛麗絲算的是 p ^ a mod g（p 的 a 次方除以 g 的餘數）。我們把它叫 m。
鮑勃算的是 p ^ b mod g（p 的 b 次方除以 g 的餘數）。我們不妨叫它 n。
既然 m 和 n 是公開的，伊芙自然也知道咯。
愛麗絲和鮑勃看到對方的結果後，相視一笑，又做了第二步計算。
愛麗絲算的是 n ^ a mod g。我們把這個結果叫 s。
愛麗絲把 s 當成秘密，不告訴任何人。雖然伊芙知道 n 和 g，但她不知道 a，所以她算不出來 s 是多少。
鮑勃算的是 m ^ b mod g。結果也叫 s。鮑勃也把 s 當成秘密。
等等！咋能把兩個數都叫 s 呢？這不搞混了嗎？這不像正經科學家乾的事啊。
這就是迪菲-赫爾曼演算法的高光時刻。
原來，我們可以證明，愛麗絲算出來的 s 跟鮑勃算出來的 s 是一樣的，所以把它們叫一個名字沒有任何毛病。
證明過程用到了高等高中數學，我把它寫在下面，供學有餘力的朋友驗證。沒有興趣的讀者麼，現在就可以跳到結尾看八卦去了。
愛麗絲算的是 n ^ a mod g = (p ^ b mod g) ^ a mod g = (p ^ b) ^ a mod g = p ^ (b×a) mod g
也就是 p 的 b×a 次方除以 g 的餘數。
鮑勃算的是 m ^ b mod g = (p ^ a mod g) ^ b mod g = (p ^ a) ^ b mod g = p ^ (a×b) mod g
也就是 p 的 a×b 次方除以 g 的餘數。
咦，b×a 跟 a×b 不是一樣的麼？所以他們算出來的這兩個數原來是一樣的。
現在，愛麗絲和鮑勃有了共同的秘密 s，就可以用 s 做金鑰給他們的通訊加密解密了。伊芙就算是看到全部通訊內容，因為不知道金鑰，也只能乾瞪眼。
聰明的朋友會想到：伊芙雖然不知道 s 是多少，但她知道 p，g，m 和 n 啊！有了這四個數，她就不能推算出 s 來嗎？
比如，她知道 m = p ^ a mod g，難道不能從 m，p 和 g 反推出 a？有了 a，不就可以算出 s 了？
還真不能。從 p，g 和 a 算 m 容易，從 p，g 和 m 算 a 是一個很難很難的問題，叫離散對數。算這東西可就要了親命了，用最快的計算機也要 1000000…000 年，基本上那時候也不會有地球了。
這個精妙的演算法依靠的是一種計算機科學中叫做單向函式的東西。顧名思義，單向函式就是從輸入算輸出容易，但是反過來從輸出倒推輸入非常困難的函式。比如說很多我們常用的雜湊函式就是這樣。還有大家熟知的大素數乘積的因子分解問題：如果 p 和 q 是兩個很大的素數，k = p×q 很容易計算，但是反過來要把 k 拆成 p×q 可就難多了。這就是今天廣泛應用的 RSA 非對稱加密演算法的基石。
～～～～
感謝大家讀到這裡。現在履行承諾，開始八卦。
我在美國讀博的時候，選了一門密碼學和安全的課程。講課的教授在這個領域頗有些名氣，叫邁克爾·費舍爾（Michael Fischer）。費教授是個滿臉大鬍子的美國白人老頭，學問很好，但是講課嘛，稍微有欠生動。而且他鼻音很重，對剛到美國的我是一個巨大的聽力考驗，所以這門課很多時候我都是靠看書自學的，因為跟上他的講座對我來說非常困難。
從朋友那裡我瞭解到費教授的太太叫愛麗絲，在附近的另一所大學做計算機系的主任。他倆還有一個兒子叫鮑勃，跟我在哈佛的一個大學同學是朋友。這些背景知識給我理解費舍爾教授講課造成了很大的困擾。因為，我會自動腦補把費教授講的愛麗絲替換成“我老婆”，把他講的鮑勃換成“我兒子”。於是，在我聽來，他講的就是“我老婆給我兒子發了一條明文訊息，被一箇中間人截獲了”。很快我就因為關心他家人的安危走神了。
學完這門課之後有一年，系裡另一位博士生做開題報告，給大家介紹他接下來博士論文會做哪個方向。這位同學志向高遠，要設計一個全新的選舉制度。按照他的想法，這個制度有很多美好的特性，比如可以保障每個投票人不受人脅迫，也就是說如果有人拿著槍逼迫你投民主黨，你可以糊弄他，嘴上說好，手上悄悄投共和黨。
與此同時，在這位博士生同學的設想中，這個制度還能保證公正透明，就是說每個選民都可以去驗證系統確實尊重了他的選擇，不會出現他選的是民主黨而系統把票記到共和黨名下的情況。
聽到這裡，我感覺智力不夠用了，於是舉手提問：這兩點不會互相矛盾嗎？要是有辦法驗證系統記的票和我選的一致，那麼也可能有人拿槍逼我驗證我投的確實是民主黨，不是就崩了我。一想到這個，我在當初投票時不就不敢投共和黨了嗎？我不就還是受到了脅迫嗎？
那位同學聽了我的質疑，沉默了兩秒，然後講了一大通話，有很多我不懂的術語。
我不是專業搞密碼的，所以默默忍下了。
報告結束大家紛紛離場的時候，費舍爾教授向我走過來，對我說：剛才你說的那個問題，我認為你完全正確。
～～～～～～～～～～
老萬近期文章：
～～～～～～～～～～
關注老萬故事會公眾號：
碼字不易，嘔心瀝血只是希望更多人看到。如果喜歡這篇文章，請不吝三連。謝謝！🙏
