《改變世界的九大演算法》:公鑰加密——用明信片寄祕密,用共同祕密來加密

《改變世界的九大演算法》:公鑰加密——用明信片寄祕密,用共同祕密來加密
Photo Credit: iStock

我們想讓你知道的是

作者將我們日常生活會用到的電腦功能背後的道理,以淺顯易懂的方式介紹,不具備資訊科學的背景也可以了解。而且令人驚喜的是,每一種演算法,都是一個解決問題的創意與線索,也讓我們得以一窺近代數學家、資訊科學家的努力探索成果。

文:約翰・麥考米克(John MacCormick)

第4章 公鑰加密:用明信片寄送祕密

人喜歡八卦,喜歡祕密。加密的目的是為了傳遞祕密,因此每個人都是天生的加密高手──人能夠比電腦更輕易地祕密溝通,如果你想告訴朋友一個祕密,只要在對方的耳朵旁講悄悄話就行了,電腦可就沒那麼容易辦到,電腦沒辦法把信用卡卡號「輕聲」說給另一台電腦聽,如果電腦和網際網路連線,就更加無從控制信用卡卡號會被傳到哪裏、被哪幾台電腦窺知。

本章將探索電腦如何利用公鑰加密(public key cryptography)來克服這個問題,而這也是電腦科學至今最聰明且最具影響力的概念。

現在你或許想問,本章的副標題為何是「用明信片寄送祕密」,答案就在圖4-1。我們把公鑰加密比喻成用明信片溝通,現實生活中如果你想寄機密文件給某人,你當然會把文件妥善密封在信封裏寄出,雖無法保證天衣無縫,但畢竟不失為穩妥的做法。把機密訊息寫在明信片上寄出顯然無法保密,因為凡是接觸得到明信片的人(例如郵務員)都會看到明信片上的訊息。

4-1
Photo Credit: 經濟新潮社出版

以上正是電腦在網際網路上進行祕密溝通時遇到的問題。由於網路上的任何訊息通常都會經過許多「路由器」(routers),凡是能進入路由器的人(包括惡意竊聽者)都能一窺訊息內容,因此從你的電腦出去的每一筆資料進入網路後,就如同寫在明信片上一樣!

或許你已經替明信片問題想到快速的解決之道。何不用密碼在訊息上加密後,再寫在明信片上?如果你認識收件人,這麼做是可行的,因為你們過去可能已經針對密碼達成共識,但真正的問題在於你寄明信片給不認識的人時,如果你在這張明信片上使用密碼,那麼郵務員將無從知道你的訊息,但收件人也看不懂!公鑰加密真正厲害的地方是,你使用只有收件人能破解的密碼,儘管你們根本沒機會針對使用的密碼暗中達成共識。

電腦在面對不認識的收件人時也面臨同樣的溝通問題。例如你第一次用信用卡在亞馬遜網站買東西,於是電腦必須將你的信用卡卡號傳給亞馬遜的伺服器,但是你的電腦從沒和亞馬遜的伺服器傳輸過訊息,因此這兩台電腦過去沒有機會針對密碼達成共識,而它們試圖達成的任何共識,都可以被網路上它們之間所有的路由器觀察到。

現在回到明信片的比喻。我承認這狀況聽起來有點矛盾,收件者看到的資訊與郵務員看到的資訊一模一樣,但收件者能夠將訊息解密,郵務員卻不能。公鑰加密將為這個矛盾的情況提供解答,接下來進一步說明。

用共同的祕密來加密

首先是個簡單的例子,也就是在一間房間裏進行口語溝通。你跟你的朋友阿諾和你的死對頭伊芙在同一個房間裏,你想偷偷傳訊息給阿諾,又不希望讓伊芙知道訊息的內容,或許這訊息是信用卡卡號,但為了簡化起見,就假設是1到9之間的一個數字吧。此外你只可以用大聲說出來的方式跟阿諾溝通,而這麼一來又會被伊芙聽到,輕聲細語或遞紙條等小聰明的舉動一律不准。

假設你想傳的信用卡卡號是7,其中一種傳遞方式,就是先試著想一個阿諾知道但伊芙不知道的數字,例如你和阿諾小時候住在同一條街上,你們經常在你家的前院玩耍,地址是快樂街322號。又假設伊芙小時候並不認識你,特別是她不知道你和阿諾以前玩耍的這個地方的地址,於是你可以跟阿諾說:「嘿阿諾,我們小時候在我快樂街的家玩,你還記得那裏的門牌號碼嗎?如果你把門牌號碼加上信用卡卡號,結果是329。」

只要阿諾記得正確的門牌號碼,就可以將你告訴他的329減去門牌號碼,得出信用卡卡號。他將329減去322得出7,也就是你想傳給他的信用卡卡號。另一方面,儘管伊芙聽見你和阿諾說的每一個字,但還是無法知道信用卡卡號。圖4-2說明整個過程。

4-2
Photo Credit: 經濟新潮社出版

這個方法有用,是因為你和阿諾之間存在著電腦科學家所說的「共同祕密」(shared secret),也就是322。因為你們知道這個數字但伊芙不知道,於是就可以利用這個共同祕密來傳遞任何想傳遞的數字,只要加上這個數字再把總數說出來,讓對方減去共同的祕密即可。伊芙聽到總數卻不能怎麼樣,因為她不知道該減去什麼數字。

信不信由你,只要懂得簡單的「加法技法」,將共同的祕密數字加在像信用卡卡號這種私人訊息上,你就知道網際網路上絕大多數的加密是怎麼運作的!電腦一直在使用這種技法,但是為了確保萬無一失,還有幾個細節要注意。

首先,電腦使用的共同祕密必須比門牌號碼322長很多,否則偷聽到對話的人就可以試遍所有可能性。例如,假設我們用加法技法將三位數的門牌號碼與16碼的信用卡卡號相加,由於三位數的門牌號碼共有999種可能性,因此偷聽到我們對話的伊芙就可以列出相對的999個信用卡卡號,而其中一個必定是你的信用卡卡號。至於電腦幾乎在瞬間就可以試遍999個信用卡卡號,所以共同祕密必須要比三位數再多很多位數才有用。

事實上,當你聽到某個位元數的加密法,如128位元加密(128-bit encryption),其實指的就是共同祕密的長度。共同祕密通常被稱為「公鑰」,因為它可以被用來解鎖或解密訊息。如果你算出公鑰中30%的位元數,就會知道公鑰大約有幾位數字。由於128的30%約為38,所以128位元加密的公鑰是一個38位數的數字。

一個38位數的數字比十億的4次方還大,一般電腦要花幾十億年才能試遍所有的可能性,因此38位數的共同祕密被認為非常安全。(作者注:如果你了解電腦的數字系統,此處的38位數是十進位數字而非二進位數字〔位元〕。若是你懂得對數,從位元轉成十進位數字的30%的轉換比率,是來自log102 ≈ 0.3。)

書籍介紹

本文摘錄自《改變世界的九大演算法:讓今日電腦無所不能的最強概念(暢銷經典版)》,經濟新潮社出版

作者:約翰・麥考米克(John MacCormick)
譯者:陳正芬

  • momo網路書店
  • Pubu電子書城結帳時輸入TNL83,可享全站83折優惠(部分商品除外,如實體、成人及指定優惠商品,不得與其他優惠併用)
  • 透過以上連結購書,《關鍵評論網》將由此獲得分潤收益。

榮獲美國出版人協會(Association of American Publishers)電腦資訊科學最佳書籍獎

電腦網路技術無所不在:每天,我們從海量的資訊中搜尋到所要的資訊、我們上傳照片到臉書上、我們運用公鑰加密來傳送私人資訊例如信用卡號碼等等、我們使用數位簽章來確認所造訪的網站的真偽……

這本書介紹了讓電腦網路世界得以運作,塑造今日人類生活的九種最重要的演算法(algorithm)。作者挑選這九大演算法的標準是:

  1. 每天會被一般電腦使用者用到的演算法。
  2. 必須能解決現實世界的具體問題。
  3. 主要是與資訊科學理論有關的演算法。
  4. 4美、簡潔、優雅。

本書所介紹的九大演算法是:搜尋引擎的索引(search engine indexing)、網頁排序(page rank)、公鑰加密(public-key cryptography)、錯誤更正碼(error-correcting codes)、模式辨識(pattern recognition,如手寫辨識、聲音辨識、人臉辨識等等)、資料壓縮(data compression)、資料庫(databases)、數位簽章(digital signature),以及一種如果存在的話將會很了不起的偉大演算法,並探討電腦能力的極限。

作者將我們日常生活會用到的電腦功能背後的道理,以淺顯易懂的方式介紹,不具備資訊科學的背景也可以了解。而且令人驚喜的是,每一種演算法,都是一個解決問題的創意與線索,也讓我們得以一窺近代數學家、資訊科學家的努力探索成果。面對越來越科技化的現代生活與職場挑戰,這些基本原理和概念值得我們去了解、吸收,為未來世界做好準備。

立體書封
Photo Credit: 經濟新潮社出版

責任編輯:翁世航
核稿編輯:丁肇九

關鍵會員推廣

Tags: