2010年9月11日 星期六

白話 「非對稱式加密/解密」 Asymmetric Cryptography

[2013/12/21 整個重新改寫][ sozi 簡報版]

古代的 symmetric encryption (對稱式加密/解密)
及現代的 asymmetric cryptography (非對稱式加密/解密) 什麼是 非對稱式密碼學 Asymmetric Cryptography非對稱式加(解)密 Asymmetric Encryption(Decryption)? 不必讀英文文章, 看 圖片搜尋結果 就可略知一二了。 右圖改編自 微軟官網。 先介紹一下術語。 如果甲(左側 sender)想寄私密訊息給乙(右側 recipient), 他可以用一把金鑰 (key) 對明文 (plaintext, 就是未加密的原始訊息) 進行 加密 (encrypt), 產生 密文 (cyphertext)。 如果他們所採用的加解密演算法 夠好的話, 密文根本就是一堆亂碼, 就算貼在網頁上昭告天下也沒關係, 因為沒有人看得懂。 乙收到密文之後, 再用金鑰對密文進行 解密 (decrypt), 又得到明文。

比較古老的方法, 加密跟解密用的是同一支金鑰, 稱為 「對稱式加解密 symmetric encryption/decryption」, 如圖上半所示。 今日的通訊軟體, 加密跟解密時, 用的則是成對產生的兩支不同金鑰, 這類演算法稱為 「非對稱式加解密 asymmetric encryption/decryption」, 如圖下半所示。 這兩枝金鑰一枝稱為公鑰 (public key), 通常會在網站上昭告天下; 另一枝稱為私鑰 (private key), 是持有人自己小心保護、 不讓任何人看到的秘密。 右圖特別值得注意的是: 加密時, 採用 收件人的公鑰; 解密時, 採用 收件人的私鑰

[本段可略過] 加密演算法所運用的概念其實很簡單: 找一個很困難、 連全世界最聰明的數學家都解不開的問題, 把它反轉過來, 就變成了保護秘密的工具。 例如非對稱式加解密領域裡, 最受歡迎的 「困難」 問題, 就是因數分解。 沒錯, 國中生就懂的這個題目, 就算丟給頂尖的數學家去解, 他們的解法也比窮舉法好不到哪裡去。 所以如果你能把加密演算法設計成 「破解它跟做因數分解一樣曠日費時」, 那麼它就是一個基本的非對稱式加解密演算法了。 如果說丟出來挑戰竊聽者的問題等同於 「分解 r = p*q 」, 那麼你可以想像: 收件人的公鑰裡面就含有等同於 r 的資訊; 而收件人的私鑰裡面則含有等同於 p 跟 q 的資訊。 這幾個數字越大 (bit 數越大), 窮舉法所需要花的時間也就越多。 因為這些數字超大, 不可能用人工方式產生、 記憶, 所以產生時, 需要用到 亂數產生器 random number generator; 而保護私鑰的方式, 通常是用一個用戶自選的 passphrase 把它上鎖。

比方說你 (sender 甲) 有重大的內幕消息要爆料給貴哥知道, 但是擔心貴哥 (recipient 乙) 的 e-mail 被黃世銘檢查總長監看。 於是你在 MIT 的 PGP Key Server 搜尋到幾年前貴哥自己貼上去的公鑰。 你把 [貴哥的公鑰] 跟 [內幕消息] 餵給加密軟體 gpg 吃, 於是產生一堆亂碼 (密文)。 你可以很放心地把這堆亂碼 e-mail 給貴哥, 甚至就算直接把這堆亂碼以匿名的方式貼在貴哥的部落格也沒問題, 因為只有貴哥的私鑰能夠解密 (把 cipher text 轉成 plain text), 所以只有貴哥可以解讀你的內幕消息; 其他人 -- 就算是無法無天無所不能的黃世銘 -- 即使看見留言內容也完全不知道你在說些什麼。

asymmetric cryptography 右圖出自 ScienceBlogs, 作者 Mark C. Chu-Carroll。 上一段的解釋, 對應到這張圖的右下 (加密過程) 與左下 (解密過程)。 事實上, 非對稱式加解密演算法所產生出來的公鑰私鑰還有另一個用途: 它可以拿來做 數位簽章 (digital signature), 也就是圖的上半部所描述的狀況。

[2016/12/12 重寫數位簽章的說明] 假設你有更驚人的內幕消息及更多證據要爆料給貴哥, 但是希望貴哥承諾不可向媒體揭露消息來源。 貴哥當然沒辦法寫一張切結書簽名蓋章寄給你, 因為你不想留下實體通訊地址。 這時貴哥可以把切結書 (plain text) 跟我自己的 private key 餵給加密軟體 gpg 吃(變成 cipher text) 然後 e-mail 給你 (圖的左上)。 你收到 e-mail 之後, 就可以用貴哥的 public key 解密, 把看似亂碼的 cipher text 解碼成為原來承諾文的明文 plain text。 (圖的右上) 這裡的重點其實並不是要保護那一段文字, 而是要向世界證明寫切結書的是貴哥本人無誤。 因為除了貴哥本人之外, 沒有人能用那把獨一無二的 private key 寫出這種 「跟貴哥的 public key 匹配的 亂碼文章」。 以上就是 「數位簽章」 的核心原理。

嗯, 最早, 寫這帖的原因是為了要寫 螢幕廣播工具 iTALC 教學; 最近重新改寫, 則是因為今年六月以來, 從 美國 NSA 無所不在的監聽 到臺灣行政院的 「行動裝置安全謊言」 以及 蘋果電腦 iOS7 的 MDM 監聽陰謀 讓大眾感受到保護自身隱私的重要性, 所以打算寫更多加密相關的教學文, 又把這篇翻出來修改。 員工如果擔心自己的電腦/平板/手機被公司監聽, 固然可以根據 個人資料保護法 主張自己的隱私; 但與其事後靠法律彌補, 不如事前用技術預防。 而加密就是最好的自保方式, 所以加解密的基本原理, 應該是現代公民必備的基本常識。

沒有留言:

張貼留言