撲克牌版「公鑰夾帶部分私鑰」 密碼破解術

PanSci泛科學網 作者：洪朝貴 ▲CC by kozumel@flickr 監聽，是很受統治者歡迎的技術。40年前美國總統尼克森頗好此道，也因此羞愧下臺。今天的美國政府掌握更先進的科技，並藉反恐、打擊犯罪之名，更全面地對國內外公民違法監聽。Edward Snowden因為在今年6月間揭發NSA（國安局）的監聽弊案而獲頒吹哨者獎，但後續記者及電腦專家仍在持續分析尚未爆完的資料。 最近又有好幾彈爆開，其中一彈嚇死人：美國國安局幾乎可以破解所有網路加密協定（中文）。這引發大家熱烈討論，連噗浪都很熱鬧。即使紐約時報跟華盛頓時報都報出來了，即使資安專家都因此而跳出來呼籲必須更改網安標準，很多人還是不相信NSA辦得到。NSA到底可能採取哪些神奇的方式破解密碼？有興趣的朋友可以幫忙摘譯register所推薦的資安教授Matthew Green分析文（我也大推！）。 本文只針對其中一種很明確可行的可能性，拿撲克牌當比喻，讓大家知道：當你所採用的加解密軟體來自一家「與NSA過從甚密的廠商」而你又看不到原始碼的時候，「NSA可以破解你的密碼」這完全是辦得到的事。 把網路上的加解密活動極度簡化，想像成是一桌撲克牌局。這個牌局的遊戲規則細節我們就省略了，只需要知道： 1. 有兩付撲克牌，一副是藍色，另一副是橘色。 2 .遊戲一開始，莊家會發給每個人一張藍牌、一張橘牌。 3. 每個人把手上的橘牌攤在牌桌上，但藍牌不給別人看。 如果你對於這兩張牌所代表的詳細意義有興趣，可以參考白話版的非對稱式加解密；但就本文而言，其實只需要知道：橘牌代表加解密演算法當中的公鑰（大家都看得見），而藍牌則代表私鑰（只有自己看得見）。 現在的問題是：莊家有沒有可能知道每個人手中的藍牌是哪張？若莊家照規矩來，雖然發牌的時候他一定會看見牌，但理論上他不應該記牌。但是如果他發牌的時候動一點手腳，自己加一點潛規則進去，把藍牌的資訊藏到橘牌裡面去，那他就比不知情的玩家要佔一些便宜了。例如他發牌的時候，可以先抽一張橘牌，然後根據橘牌的數字大小來決定要發什麼花色的藍牌給玩家。更具體地舉例，比方他自己暗中決定： 1. 如果橘牌是A或2或3，那麼他就不斷地重抽藍牌，直到抽到梅花，才把它跟橘牌一起發給玩家。 2. 如果橘牌是4／5／6，那就一定要抽到一張方塊的藍牌才發牌。 3. 如果橘牌是7／8／9，那就一定要抽到一張紅心的藍牌才發牌。 4. 如果橘牌是10或人頭，那就一定要抽到一張黑桃的藍牌才發牌。 因為橘牌攤在桌上，所以大家都看得見；但是因為只有莊家知道發牌的潛規則，所以只有他可以從攤在桌面上的橘牌推測出蓋著的藍牌的花色。 以上就是我對這篇論文“Simple Backdoors for RSA key generation"的「撲克牌比喻版」白話翻譯。當然，真實的狀況要複雜很多，理解上述比喻之後，還需要略微修正如下。 「莊家」在真實世界裡，就是密碼產生器／亂數產生器。拿「NSA要求微軟安裝在Windows裡的後門」來說，如果運作方式真的類似本文所述的話，它也不太可能記牌（記住每位Windows用戶所產生的所有公私鑰），因為「每當金鑰一產生就出現（回傳NSA的）網路活動」太容易被識破。所以採取本文的策略比較合理可行——一般人不會想到私鑰的部分訊息會被藏在公鑰裡、更不會想到只洩漏私鑰的部分訊息，密碼就會被完全破解。 從一副撲克牌當中抽一張，只能傳遞不到6個bits的資訊（52