0

0
0

文字

分享

0
0
0

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

洪朝貴
・2013/09/11 ・2746字 ・閱讀時間約 5 分鐘 ・SR值 500 ・六年級

poker-nsa

監聽, 是很受統治者歡迎的技術。 40 年前美國總統 尼克森 頗好此道, 也因此羞愧下臺。 今天的美國政府掌握更先進的科技, 並藉反恐、 打擊犯罪之名, 更全面地對國內外公民違法監聽。 Edward Snowden 因為在今年六月間揭發 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 < 64 = 26), 雖然比 2.3 bits 的教學品保量化指標 更有意義一點, 但跟實際應用上幾十或幾百個 bits 的資訊還是差很多。 在上述的比喻中, 莊家很老千地把 (理應是私密的) 藍牌其中 2 個 bits 的資訊 (22 = 4 種花色) 暗藏到橘牌的 5.8 個 bits 裡面去。

在實際的 RSA 加解密演算法當中, 藍牌跟橘牌之間本來就不能任意組合、 莊家 (密碼產生器) 本來就合理地必須篩選出某些有意義組合的一雙 「藍牌/橘牌」。 也因此, 會浪費掉一些 bits。 RSA Security 公司表示: 1024 bits 的 RSA 密碼, 大約只有 80 bits (完全自由隨意亂碼的) 對稱加密密碼的強度; 3072 bits 的 RSA 密碼, 大約等同於 128 bits 完全亂碼的強度。

「玩了一陣子之後, 莊家的潛規則會不會被觀察力敏銳的玩家發現呢? 例如玩家可能發現: 為什麼每當我拿到點數小的橘牌時, 藍牌就一定是梅花?」 因為真實世界的 bits 數太多, 可以排列組合的方式太多, 所以莊家可以採用很複雜的潛規則把資訊打很亂地藏到橘牌裡, 讓玩家很難看出與正常隨機發牌有何不同。

「只知道藍牌的花色, 還是無法精確地指出藍牌是哪一張啊! (所以無法破解密碼)」 嗯, 到這裡, 就幾乎必須把比喻丟掉了。 Simple Backdoors 論文其實是建立在 An attack on RSA given a small fraction of the private key bits (及其他更數學、 我沒讀) 的結果之上。 如前所述, 藍牌與橘牌之間其實並不是完全隨意組合。 也就是說, 就算莊家不耍老千, 任何人從桌面上對手的橘牌還是可以稍微推算一下他手中可能有哪些藍牌、 不可能是哪些藍牌。 如果進一步知道藍牌更多一點資訊, 就更可以縮小範圍了。 這篇 attack 論文指出: 只要可以取得藍牌 (bits 數) 1/4 的資訊, 那麼要精確指出藍牌到底是哪一張, 就變得 「相對很簡單」。 (所需破解時間從 exponential time 大幅降到 polynomial time) 他們並且真的跑程式測試, 在 500MHz 的 Intel P3 機器上試著破解 1024 bits 的 RSA 密碼 (假設已知其中最高的 256 bits) 只需要 21 小時。 如果說原先破解 RSA 的困難度就像想要出大氣層旅遊一樣 — 不是不可能, 但你我做不到 — 那麼 「已知部分密碼」 版的破解困難度就像花個一兩千塊搭高鐵旅遊一樣輕鬆。

這裡雖然是舉 RSA 為例, 但我相信網路上一定還可以找得到更多破解其他 「非對稱式加解密」 的論文。 當然, 像是 RSA 這類歷經長時間驗證的加解密演算法, 都不太可能被徒手直接攻破 — 比較可能是在 「部分機密被偷偷巧妙洩漏」 的前提之下, 才會被破解。 而最簡單的 「偷偷巧妙洩漏」 方式, 就是如本文所說, 把私鑰的一部分資訊藏在公鑰裡面。 最有可能被惡意動手腳的地方, 就是密碼產生器與亂數產生器, 而美國 NSA 與 FBI 等等情治單位, 過去不斷在這方面出手惹議, 早為關心資安人士知悉。 小格先前提及的兩個案例 NSA 要求微軟在 Windows 裡暗藏後門 以及 OpenBSD 被懷疑遭 FBI 植後門 (但後來證實並沒有) 最終都追蹤到這個地方。 差別在於: OpenBSD 的原始碼攤在陽光下, 所以大家可以仔細檢查可疑的地方; 而 Windows 的程式碼看不見, 所以用戶就只好自求多福了。 我們一直強調: 為什麼社會應該要採用自由軟體/開放原始碼軟體? 除了免費跟好用之外, 還有其他更重要的原因 — 資訊安全也是其中之一。 採用開放原始碼軟體, 並不必然就 100% 安全; 但若採用看不見原始碼的軟體, 那根本就不必談什麼資訊安全了。

(本文轉載自 資訊人權貴ㄓ疑


數感宇宙探索課程,現正募資中!

文章難易度
洪朝貴
47 篇文章 ・ 0 位粉絲


0

0
0

文字

分享

0
0
0

今年夏天絕不能錯過——「搞笑諾貝爾獎世界展」首度登台!

鳥苷三磷酸 (PanSci Promo)_96
・2022/05/17 ・1966字 ・閱讀時間約 4 分鐘

你一定知道諾貝爾獎,但你知道世界上竟然還有搞笑諾貝爾獎(Ig Nobel Prize)嗎?搞笑諾貝爾獎是對諾貝爾獎的有趣模仿,甚至還會邀請真正的諾貝爾獎得主來參加!

搞笑諾貝爾獎由美國的科學雜誌《不可思議研究年報》的主編馬克·亞伯拉罕斯發起,每一屆都號稱「第一屆」,每次都會頒發十座獎盃給各領域中「無法被複製」或「荒唐到不應該再來一次」的研究者,頒獎要旨是希望讓大家能夠"先大笑,再思考"。臺灣也有多位學者共襄盛舉,並曾六度獲獎,臺灣立法院更曾拿下和平獎,其中原因竟然是因為他們以打架替代戰爭!典禮現場更是充滿歡笑,讓人佩服科學家怎麼一本搞笑做研究!

搞笑諾貝爾獎頒獎現場超搞怪!

  • 量身打造獎盃,每年都以當年獲獎的研究為靈感,製作不同主題的獎盃!
  • 不值錢獎金,得獎者會獲得比壁紙還不值錢的高額辛巴威幣作為獎金。
  • 甜便便小姐,得獎者只有 60 秒的時間能發表感言,只要一超時,年幼的「甜便便小姐」就會大叫:「請停下來吧!煩死人了!」直到得獎者下台。
  • 全場亂飛的紙飛機,頒獎典禮中會安排一名背著一個紅色靶心的人,讓台下觀眾將手中紙飛機射向台上的靶心。
2009 年的得獎者們。

今年夏天搞笑諾貝爾獎世界展將首次登台!廢到笑的研究與發人省思的成果,一次集結歷屆讓人目瞪口呆的得獎研究及五大互動體驗,讓你一本正經的捧腹大笑!展區內充滿更多腦洞無極限的幽默科學得獎,一定要揪朋友一起來漲知識。

5/2-5/26 早鳥 $260 限時搶購,購票請洽:https://kham.tw/t14cjEav

ㄎㄧㄤ到爆獎項搶先看

搞笑諾貝爾獎世界展將集結眾多搞笑諾貝爾獎的獲獎研究,其中有許多讓人會心一笑的內容,像是鴿子也懂藝術?日本學者就曾做過實驗,證明鴿子可以分得出畢卡索和莫內的畫;在野外遇到熊怎麼辦?只要穿上防熊裝就不用怕;指甲刮黑板的聲音經研究證實為世界上最讓人痛苦的聲音!

曾有科學家發明出可迅速變身防毒口罩的胸罩,並成功獲得搞笑諾貝爾獎的公共衛生獎,其發明聽起來很荒謬,但背後原因是胸罩是會隨身穿戴的物品,能夠在緊急時刻變成防毒口罩保護他人,符合了搞笑諾貝爾獎頒獎要旨「先大笑,再思考」,另外還曾有一年的「獸醫學獎」頒給發現幫乳牛取名字,就能夠增加產乳量的專家學者!以及最經典的貓貓是液體嗎?也都存在於搞笑諾貝爾獎的得獎研究裡!

  1. 鴿子也懂藝術?|連鴿子都分得出畢卡索和莫內的畫!
  2. 野外遇到熊了怎麼辦?|穿上防熊裝,再也不怕!
  3. 動物也吃重口味!?|綠頭鴨也有戀屍癖!?
  4. 用「屁」交流!|看看鲱魚怎麼用放「屁」溝通!
  5. 逃跑鬧鐘|還想賴床按鬧鐘嗎?鬧鐘本人跑起來給你追!
  6. 最討厭的聲音!|指甲刮黑板太邪惡了!
  7. 如何增加乳牛的產乳量?|不妨給牠取個名字吧!
  8. 胸罩變口罩|在突發的緊急狀況時胸罩變防護口罩!?  
  9. 恐龍走路長甚麼樣子?|在雞的屁股裝上一根棒子就知道!
  10. 貓是液體嗎?|喵星人的貓體力學大解密!

五大互動體驗,只有實驗了才知道

展區現場將規劃五種關於搞笑諾貝爾獎得獎研究的實際互動體驗,讓你能夠化身為小小研究學者,一起來實際試試看、探討世界上經典的搞笑研究!

  1. 吐司永遠是塗奶油的那面先落地嗎?
  2. 挑戰「說話干擾器」!你能夠堅持把話說完嗎?
  3. 極高速烤肉!液態氧+木炭可以燃起多大的火花?
  4. 活性碳內褲過濾屁味?沒有比較沒有傷害
  5. 旋轉吧!高速助產裝置,離心力有助生產?

2022年最寓教於「笑」的展覽,更多大開眼界的搞怪研究,就在國立臺灣科學教育館等你來刷新三觀! 5/2-5/26早鳥$260限時搶購,購票請洽:https://kham.tw/t14cjEav

 圖/歷屆得獎者授獎畫面
圖/日本展出現場照

展覽資訊

  • 展覽名稱:搞笑諾貝爾獎世界展
  • 展覽日期:2022 年 6 月 25 日(六)至 2022 年 9 月 11 日(日)
  • 展覽地點:國立臺灣科學教育館 七樓南側特展區(臺北市士林區士商路 189 號)
  • 展覽時間:平日9:00-17:00/週末、國定假日、暑假 9:00-18:00
    (閉展前 30 分鐘停止售票及入場)
  • 休展日:6/27(一)、9/5(一)
  • 主辦單位:寬宏藝術經紀股份有限公司、三貝多股份有限公司
  • 企劃單位:株式会社ドリームスタジオ(Dream Studio Company)
  • 授權單位:IMPROBABLE RESEARCH, INC.

購票請洽:https://kham.tw/t14cjEav


數感宇宙探索課程,現正募資中!

鳥苷三磷酸 (PanSci Promo)_96
9 篇文章 ・ 7 位粉絲
充滿能量的泛科學品牌合作帳號!相關行銷合作請洽:contact@pansci.asia