2014年12月8日

改變世界的九大演算法 - John MacCormick

本書所介紹的九大演算法是:搜尋引擎的索引(search engine indexing)、網頁排序(page rank)、公鑰加密(public-key cryptography)、錯誤更正碼(error-correcting codes)、模式辨識(pattern recognition,如手寫辨識、聲音辨識、人臉辨識等等)、資料壓縮(data compression)、資料庫(databases)、數位簽章(digital signature)。

寫程式的人很多,做IT工作的也很多,但並不是每一個人都能了解這些常用演算法背後的精神與原理,我也跟一般 IT 工程師一樣,沒有專業到完全了解這些演算法的來歷,沒有辦法把每一個演算法講出來,還能讓 dummy user 聽得懂。

本書的推薦序也講得很明白,要撰寫甚至出版這本書,本身就有很高的風險,科普書的禁忌是:出現的算式越多,賣得越差,所以這本書的目標讀者該是給像我們這樣的 IT 工程師閱讀,但如果是剛畢業沒多久的工程師們,應該都還有印象,在演算法課程時鴨子聽雷的窘樣。

這似乎也多少註定了書本的命運,銷售量肯定不會很高。但我還是強烈建議,應該花時間去把這本書看一看,這可讓我們對關聯式資料庫、Google搜尋等等項目,有更深一層的認識。專業工作者的一項最重要的功能,就是在遇到一些技術上要實作的問題時,能提出一套解決方案,而這本書的知識,就是你備而不用的專業背景知識。

接下來,我只討論「公鑰加密」這個章節,其他的部份,就留待讀者自己去看書了。「公鑰加密」這章的副標題是:用明信片寄送祕密,這個比喻非常貼切,因為網路上的資料,對所有網路節點來說,都是明白且清楚的,把資料放在網路上傳送,也就等同於我們寫了一張明信片投遞出去,所有經手這張明信片的人都能看到,上面寫了什麼。

最直覺的解決方式,就是收送雙方預先協商出一個密碼,但這樣會有另一個問題,當面對另一個不認識的人,我們就沒辦法預先協商密碼了。

作者用顏料混色法,來解釋應該要怎麼處理

  1. A 與 B 各自選擇一個「個人色」
  2. A 與 B 其中一位,公開宣佈一個不同的新顏色為「公共色」
  3. A 與 B 各自將公共色與個人色混合,製造出一個「公共個人混色」
  4. A 取得 B 的「公共個人混色」,再加入自己的「個人色」。同時間 B 取得 A 的「公共個人混色」,再加入自己的「個人色」。結果兩個人製造出完全一樣的三色混色結果。

於是這最終的三色混漆,就成了 A 與 B 的共同祕密混漆。由於 C 不知道 A 與 B 的「個人色」,因此就無法破解「公共個人混色」

電腦不是混色,而是將顏色改為數字,混色改為乘法。最有明的公鑰加密方法是 RSA。了解這個章節搭配上第九章數位簽章的內容,就可以知道,我們怎麼在公開的 Internet 環境中,製作一個在任意的 A 與 B 兩地之間,安全地傳送資料的計算環境。

在我們學習網路程式設計時,通常會連帶學到,區域網路的廣播特性,還有網路監聽側錄 sniffer 程式的使用,因為撰寫網路程式就是在跟封包資料奮戰,我們常常得一個一個 byte 去觀察收送兩端傳送資料的正確性,才知道自己寫的程式到底對或錯。

sniffer 技巧如果用在 hacker 行為上,只要在網路上經過的節點上放置 sniffer 程式,就可以錄製到所有的封包資料,雖然一般使用者沒辦法想像網路的傳輸協定,但都能理解到,有個監聽者在監聽資料的狀況下,沒有資料加密機制,就等於拿一張明信片在上面寫字,告訴大家我在講什麼。

還記得以前的宿舍網路,當時還是用同軸電纜,網路一段一段加上 repeater,當時也是 BBS 流行的時代,所以只要在其中有一台電腦裝上 sniffer,就可以看到大家在 BBS 上跟妹妹 talk 的肉麻對話。

雖然現在的集線器已經都是 switch 而不是 hub,switch 不會將某個 port 的資料轉送到其他所有 port 上,但是 hacker 還是可以透過 ARP 的方式,製造出 man-in-the-middle 的環境,就能取得特定 IP (range) 的進出封包,資料加密機制在現今有缺陷的網路協定上,是不可或缺的技術。

博客來:改變世界的九大演算法:讓今日電腦無所不能的最強概念