2011 第4期 獨家發行 數 數學與密碼系列之一 從傳統到現代 瞰 鳥 東海大學 沈淵源教授 數 學並不只是一門研究 數 的學問 真正研究 數 的學問的稱為 數論 英國大數學家戈德 福瑞 哈洛德 哈地 G. H. Hardy 在上一世紀的四十年代曾提到 數論乃純數中的純數 是遠離 一般人類活動的學科 所謂的 純 在某些人的觀念裡 跟 無用 是畫上等號的 但 純 真的就 無用 嗎 純 與 用 可能交會嗎 這跟我們今天要聊的重點 密碼學息息相關唷 自古以來 人總是喜歡保守一些不為人知的秘密 不管是私事 還是國家大事 我們似乎對 於保守秘密這件事樂此不疲 小至個人隱私 大至國家政治 經濟 或是軍事等機密 從歷史的記 載 我們不難發現 許多君王 將軍總是將機密信息埋藏在密碼中來與部屬 聯繫 目的是為了防止被敵方竊知而造成國家損失 這是早期密碼 學的源起 而隨著社會的進步 私人 企業與國家的權益變 得更為敏感 再加上 e 世代的來臨 讓人們對於資訊 電子服務等依賴與日俱增 透過網際網路來交換資訊 如 信用卡號碼 愈來愈頻繁 於是對於保護這些 資訊與電子系統安全的需求愈來愈高 密碼學技 術的發展也愈來愈精巧 細膩
本系列文章將依據加密函數的難易程度 對密碼系統做一簡單的分類 並針對各個系 統作深入淺出的介紹 如果加密函數是單向函數 註1 則我們可以將加密的相關資訊全部公 開 這就是所謂的公鑰密碼系統 也是現代密碼學與傳統密碼學分道揚鑣的地方 在這個 指導方針之下 我們預計探討的主題有 鳥瞰 從傳統到現代 私鑰密碼與模數魔術 私鑰密碼與公鑰密碼 公鑰密碼與離散對數 公鑰密碼與因數分解 公鑰密碼與橢圓曲線 公鑰密碼與編碼理論 公鑰密碼的相關應用 現在 就讓我們正式展開這趟數學與密碼的探索之旅吧 1. 憶兒時 我們小時候 或多或少都玩過一些關於密語的遊戲 就是將原本要說的話用一種很頑皮 的方式傳達給我們要傳達的那個人 只有那個人會懂我們在說什麼 別人就算聽見了 也就 像是鴨子聽雷般 不知其意 比如 我們要說 即刻寄錢來 但講的時候 把每個字注 音的最後一個音省略 只有一個音的字則維持那一個音 於是原本的話變成 ㄐ ㄎ ㄐ ㄑ ㄌ 請問 如果你收到這樣的訊息 你知道是什麼意思嗎 ݰ រ 2
這個例子當然還不夠格稱得上是密碼 只是一個有趣的開場白而已 不過卻可以讓我 們約略的感受如何把看得懂的信息 稱之為 明文 plaintext 轉換成看不懂的密碼 稱 之為 密文 ciphertext 事實上 這個轉換不僅僅是一個函數關係 f 它還得是一對 一函數才行 否則就會發生同一個密文卻對應到兩個明文的情況 如上述的 ㄐ 對應到 即 與 寄 一般 這也是為什麼我們剛剛說這個例子還不夠格稱得上密碼的原因 將明文轉換為密文之間的函數關係 f 我們將之稱為 加密函數 而其反函數 f-1 則 稱為解密函數 底下我們將介紹一個簡單的真正密碼的例子 這個例子雖然簡單 但卻能充 分 顯 現 數 論 在 密 碼 術 中 的 分 量 也 難 怪 乎 國 際 知 名 的 資 訊 安 全 專 家 布 魯 斯 施 奈 爾 Schneier 註2 在其 應用密碼術 一書中說到...almost all cryptologists are also theoretical mathematicians...... 幾乎所有的密碼學家同時也是理論數學家... 並在其第二本暢銷書 秘密與謊言 的序言中進一步說 Cryptography is a branch of mathematics. 密碼術是數學的一個分支 2. 簡單的例子 現在 我們用英文的 26 個字母來傳達信息 SEND MONEY 首 先 我 們 用 當 成 所 謂 的 加 密 鑰 匙 將 重 複 的 字 母 去 掉 剩 下 MATHEICS 然後將這些字母放在依序排列的 26 個字母下方 再把剩下的其餘字母接續 在後 如 A B C D E F G H I J K L M M A T H E I C S B D F G J N O P Q R S T U V W X Y Z K L N O P Q R U V W X Y Z 顯然的 這是個一一對應 我們把上一行的字母用下一行相對應的字母來代換 如此 一來 所要傳達的信息變為 QEKH JLKEY 換句話說 QEKH JLKEY 是 SEND MONEY 的密文 3
3. 安全性可慮 代換法對長一點的信息來說並不是一個妥當保持信息安全的好方法 但誰又能識破其 真相呢 值得懷疑 試著觀察密文 QEKH JLKEY 重複的字母提供了唯一的線索 由此 線索推論出來與原信息同形式的信息可能是 LIST MUSIC MINE TUNIC 或 DRAW CHART 當然 如果我們知道加密的鑰匙及整個方法 我們可以輕易的製作上表並將過程逆推 而得到原信息 這意味著 解密鑰匙很容易就可以從加密鑰匙中得到 此乃古典密碼術的 特性 我們將這種特性稱為 對稱式密碼系統 而也因為基於這樣的特性 所以整個信 息的安全性可說是完全掌控在那把加密的鑰匙上 如能保守住加密的鑰匙 安全性大抵如 虞 但要守住一把鑰匙卻有著以下的多重困難需要考量 鑰匙是傳遞信息的雙方都要知道的 只要一方沒守住 安全性就會被破壞 有時候 傳遞信息的對象是多方的 人多口雜 安全性更是可慮 從另一方面來說 如果鑰匙很複雜 複雜到必須寫下來 那麼被發現的機會更是有增無 減了 利用此法互通信息時 必須事先安排好 如何讓祕密通信的雙方 或多方 同意或知道 這把鑰匙 這整個 事先安排 的過程還得要極機密進行才可以 否則將功虧一匱 由於以上種種原因 刺激人們進一步的去思索 去探究更高竿或更深入的密碼術 我 們希望信息的安全性不要只受制於鑰匙的秘密性 亦即我們希望信息的安全性可以獨立於 鑰匙的秘密性之外 即便鑰匙不小心洩漏了 我們的信息內容還能被守住 換句話說 我 們想要達到的目的是 得到鑰匙 只能將擷取到的信息轉變為密碼文 卻無法將密碼 文破解 回歸其廬山真面目 這點對於古典密碼系統來說是不可能的 因為解密鑰匙與加密鑰匙是對稱的 公開了 加密鑰匙就等於是公開了解密鑰匙 所以我們必須將加 解密鑰匙之間的對稱性打破 這 是突破僵局的唯一之道 如何打破呢 很自然的 想到鑰匙就讓我們聯想到門 許多公共 建築物的大門 當我們從建築物的內部往外走時 只要輕輕將門一推即可 但若是從外部 往內走時 卻必須有鑰匙才行 其實 從門內將門一推的動作 表面上看來好像不需要鑰 匙 但實際上那個 推 的動作就是一把人人都知道的公開鑰匙 處在門內 門外 是全然 不同的兩個世界 4
數學 4. 來自於數論的靈感 如何打破加 解密鑰匙之間的對稱性呢 剛剛門的比喻給了我們些許的啟發與暗示 出去 簡單 容易 快速 進來 複雜 困難 緩慢 出門時 進門時 也就是說 一個方向是 簡 易 快 另一個方向是 雜 難 慢 具有這樣性質的 東西究竟是什麼呢 是一個運算嗎 是一個函數嗎 還是一個演算法 這整個探索過程的 歷史其實是相當耐人尋味的 不過我們得等到介紹公鑰密碼系統時再來分曉 所以現在我們的想法是 在數學裡面尋找一種運算 函數或演算法 它的計算速度 要非常快速 但其逆過程的計算速度卻要非常慢 這樣極其強烈對比的東西 看似遠在天邊 卻是近在咫尺 讓我們試著回想一下小 學時學過的四則運算 這最簡單的東西卻蘊含著最深奧的道理 以前 我們或許從不認為 兩個數相乘 會是一件大不了的事 即使這兩個數非常大 我們也不曾把它放在眼裡 同 樣的 我們也不覺得把 一個數分解成比原本小的兩個數的乘積 會是一件多偉大的事 我們之所以不覺得是因為當年我們的老師對我們太仁慈了 他給我們分解的數還不至於太 大 頂多四 五位數 要是再大一點 恐怕就不是那麼容易了 5
現在 我們把這件看似沒什麼了不起的事用明確的數學語言寫下來 找出兩相異質數 p 與 q 然後將其相乘得到積 n pq 這整個過程比起其逆過程 給一個整數 n 將之分解成兩質數 p 與 q 的乘積 來得簡單快速許多 為方便起見 下面的例子中 我們取比較小的兩質數 p 與 q 如 p 23 q 47 然後將其相乘得到 n pq 1081 這個步驟很快 反之 如果是要把 1081 分解成兩質 數的乘積 那麼我們至少得試 2 3 5 7 11 13 17 19 等共 8 個除法之後 才找到 23 可以整除 1081 即 1081 23 47 在這裡 其實 1081 算是很小的數 我們尚感覺不出找到 23 有何困難 但當 n 是一 個 200 位的整數時 其困難度就非比尋常了 關於這部分的計算複雜度問題會在稍後的文 章中說明 現在 我們正式介紹這個加 解密鑰匙不對稱的密碼術 首先 我們先取一整數 e 令其與 ψ(n) (p 1)(q 1) 互質 在我們的例子中 ψ(n) (p 1)(q 1) 22 46 22 11 23 我們不妨取 e 3 此處 n 1081 e 3 是公開的鑰匙 而 p 與 q 則保持秘密 這次 我們將英文的 26 個 字母以數字來表示 如下 6 空白 A B C D E F G H I J K L M 00 01 02 03 04 05 06 07 08 09 10 11 12 13 N O P Q R S T U V W X Y Z 14 15 16 17 18 19 20 21 22 23 24 25 26
數學 假設我們要傳遞的訊息是 SEND MONEY 則先將其化為對應的數字 如下 19 05 14 04 00 13 15 14 05 25 因為 1081 是四位數 所以我們將信息數串以三位數分為一組 即 190 514 040 013 151 405 250 最後一組的 25 因為只有二位數 故在尾巴補上 0 我們用 m1,m2,m3,... 來表示這些三位數 然後按照下面的法則轉換為密碼 ci mie mod 1081 i 1, 2, 3,... 此處 ci 為介於 0 與 n 1 之間的整數 亦即被 n 1081 除所得的餘數 這裡 我們需要 用到 同餘 的概念 後續的系列期刊會再詳細討論 轉換後的 ci 值如下 c1 1903 6859000 55 mod 1081 c2 5143 135796744 443 mod 1081 c3 0403 64000 221 mod 1081 c4 0133 2197 35 mod 1081 c5 1513 3442951 1047 mod 1081 c6 4053 66430125 513 mod 1081 c7 2503 15625000 226 mod 1081 所以收到的密文為 55 443 221 35 1047 513 226 如何把這串密文 {ci} 破解回歸其廬山真面目 {mi} 呢 我們令 b [p 1, q 1] 為 p 1 與 q 1 的最小公倍數 注意 若不知 p 與 q 則 無從知道 b 且 d 為同餘方程式 ex 1 mod b 的最小正整數解 此處 b 2 11 23 506 則 d 為 ex 1 mod506 的最小正整數解 e 3 即 3d 1 mod 506 得 d 169 計算 cid mod 1081 即得 mi, i 1, 2, 3,... 7
為什麼這麼神奇呢 轉眼間好像魔術般的又回到了原點 我們先暫且把這個問題擺一邊 先來驗證看看 cid mod 1081 的確就是 mi 第一個碰 到的是 55169 mod 1081 就是把 55 自乘 169 次後 再被 1081 除所得的餘數 將 55 自乘 169 次 表面上看來得執行 168 次的乘法 這可相當耗費時間了 但如果只是平方 速度就會快上許多 重複執行平方的動作 我們可以得到 4 次方 8 次方 16 次方 32 次方 64 次方 128 次方等 這提供了我們一個解決 55169 mod 1081 計算問題的方 法 先將 169 寫成 27 25 23 20 128 32 8 1 然後依次計算 55 的 2a 次 方如下 552 3025-218 mod 1081 在此 我們引入負數 為 554 (-218)2-40 mod 1081 558 (-40)2 519 mod 1081 5516 5192 192 mod 1081 5532 1922 110 mod 1081 5564 1102 209 mod 1081 的是將每個數的大小調整成比 n 小 如此一來可以稍稍減少 2 所要執行的計算量 特別是當你 用手算的時候 這是一大幫助 55128 2092 441 mod 1081 因此我們得到 55169 441 110 519 55 190 mod 1081 這裡要特別注意的是 原來需要執行 168 次的乘法工作 現在只要 10 次就了結 這 個演算法稱為連續平方法 此觀念非常重要 值得推廣 8
數學 利用同樣的方法 我們可以算出其他項 {ci169 mod 1081 } 的值 現在 我們回 到剛剛被我們暫且擺在一邊的問題 為何 cid mod 1081 的確就是 mi 呢 為簡便之故 下面的論證中 我們將下標的符號 i 省略 從上面的過程 我們知道從 m 到 c 的運算為 c me mod n 而破解 c 時計算的是 m' cd mod n 所以我們 必須要證明的是 m' m 還記得嗎 m 與 m' 都是小於 n 的正整數 所以我們只需證明 m' m mod n 首先 由定義我們知道 m' cd (me)d=mde mod n 因為 d 是同餘方程式 ex 1 mod b 的解 故 de 1 mod b 即 de 1 kb k n 若 m 與 p 互質 則由費馬小定理告訴我們 mp-1 1 mod p 又 p 1 b b a(p 1) a n 故可得 mkb (mp 1)ka 1 mod p 所以我們有 m' mde m1+kb m mkb m mod p 若 p m 則上面的同餘式顯然成立 同理可證 m' mde m mod q 但 n pq 且 p 與 q 互質 故得證 m' mde m mod n 9
5. 計算之複雜度分析 經過上面這一番勞苦的計算之後 讓人深深覺得像是這樣的計算最好還是交由電腦來 承擔 我們同時也注意到分解 n 1081 的困難度是整個方法安全與否的關鍵所在 然而 在上面的例子中 有一些計算似乎比分解 1081 還複雜 例如 將 55 自乘 169 次 這好像 有點奇怪 我們說困難度是在分解 1081 但卻有些計算比分解 1081 還複雜 這不是很 怪異嗎 其實 在實際的應用當中 質數 p 與 q 都是 100 位數之大 相乘之後就變成 200 多 位數 所以在加密或解密的過程中 雖然我們不可嗤之以鼻的輕看計算高次冪之數的計算 量 但比起分解一個 200 多位數 就目前已知的演算法 的計算量 單純的計算高次冪之 數的計算量是來得少 而且少得很多很多 要分析這其中的奧秘 我們得將所涉及的運算分解成一些最基本的運算 如 加法 減法 乘法 除法及其相互比較 當然 數字的大小會影響到電腦去執行這些運算的時 間 所以為了簡單起見 我們假設所有這些運算所需的時間都是一樣的 比如一秒一百萬 次 在解密的過程中 最困難的地方似乎是將一個數自乘 d 次 此處 d 為同餘方程式 ex 1 mod b 中的最小正整數解 因為 b [p 1,q 1] 所以我們可以假設 d (p 1)(q 1) gcd(p 1 q 1) pq 2 n 2 n 2 接著 我們把 d 連續除以 2 將之化為二進數 這需要幾次的除法呢 很明顯的 這 個數目就是 d 的二進制表示法的位數 先說是 k 吧 因此 2k 1 d k 1 log2d log2( n ) log2n 1 k log2n 2 這讓我們知道 k 的上界為 log2n 此數隨著 n 的增加而增加 但增加的速度非常慢 如 n 為 200 位數 則 log2n 卻比 700 還小 10
數學 我們利用連續平方法處理上面的次冪計算 則需要執行 k 次 先平方 再除以 n 得其餘數 的計算 這將少於 700 次的乘法及少於 700 次的除法 再連同前面將 d 化成二位數的計算合 起來 不會超過 2100 次的基本運算 若要我們動手去算 那當然還是曠日費時 但對電腦來 說 卻是輕而易舉之事 不吭半聲便結束了 再來是將上述步驟所得到的平方數 依據 d 的二進數之有無 兩兩相乘再除以 n 得其餘 數 這個步驟的乘法 除法都不會超過 k 次 所以全部合起來不會超過 3500 次的基本運算 最後是估計解同餘方程式 ex 1 mod b 所需的基本運算次數 這個步驟需要將 b 與 e 輾轉相除 不難證明其次數不會超過 2 log2n 恕在此不贅述 即 1400 次的除法 逆推回去 將 1 寫成 b 與 e 的線性組合 所需的基本運算跟前面輾轉相除法合起來不會超過 2800 次 所以 整個加密 解密過程合起來所需的基本運算最多不會超過 10000 次 以 一 秒一百萬次 的速度來執行這些基本運算的電腦 在一秒鐘內就可以完成一百件這樣的工 作 也許一秒執行一百萬次基本運算的電腦是快過現在任何一部電腦的速度 但是資訊科 技的發展日新月異 也許很快的 我們就可以目睹這樣的電腦速度誕生 再者 駭客的能 力常常是無遠弗屆 做最壞的打算才是上上之策啊 6. 誰還管生生世世 夜夜朝朝 話說回來 試圖破解密文的人必須先分解那巨大無比的 200 位數 n 為 p q 由此算 出 b 後再執行上述的計算來解密 如果此人所用來分解 n 的方法是除以從 1 開始到 n 的所 有整數的話 那麼光這一項工作就得執行 10100 次的除法 如果我們用 一秒一百萬次 速 度的電腦來處理 需要約 1094 秒鐘的時間 也就是約 3 1086 年才能算完 當然 實際上 只需要除以其中的質數 但問題是 判斷 100 位以內的數 哪些是質數 又是一件相當 頭痛的事了 所以 即便是用超越現今的電腦配備 最有效率的演算法 要分解一個 200 位數尚需 40 億年的光陰才能完成 而 40 億年後 誰還管誰看到這則信息呢 11
數學 [ 註 ] 1. 單向函數 one-way function 如果一個函數是單向函數 則其函數值 f(x) 可在短時間內計算出來 但給予 y 要找滿足 f(x) y 的 x 在計算上是不可行的 2. 施奈爾 Bruce Schneier 是一位國際知名的資訊安全專家及作家 經濟學家譽之為安全宗師 他的第一本暢銷書 應用密碼術 Applied Cryptography 被譽為密碼術之經典著作 他是 Counterpane Internet Security, Inc. 的創辦人 同時也是這個公司的 CTO 其著作翻譯為中文 者有 秘密與謊言 Secrets and Lies, 由商周出版社於 2001 年 9 月 16 日初版發行 施氏的 詳細介紹可至 http://www.schneier.com/ [ 參考文獻 ] 1. 沈淵源 數論輕鬆遊 數學傳播第二十九卷第四期 116 94 年 12 月 第 45 71 頁 全文見網頁 http://www.math.sinica.edu.tw/math_media/d294/29408.pdf 讀者好康 意猶未盡嗎 我們將於後續的期刊中 請沈教授一步 一步地帶領我 們一窺密碼術的奧妙 但礙於期刊篇幅有限 如您想更深入的了解完整的 內容 歡迎購買沈教授在全華圖書的出版品 書號 09062 書名 密碼學之旅 與 MATHEMATICA 同行 作者 沈淵源 誠摯邀請老師分享您精闢的見解及投稿 投稿請寄 we04@chwa.com.tw 您的稿件企劃部將視情況刪修 修改後會寄給您過目 您同意後才會刊登 投稿作品 視同授權本刊書面及電子版刊載 作品一經刊登將依字數致贈 稿酬 來稿請勿侵害他人著作權 如有引文 請註明參考資料來源 來稿請附作者資料 姓名 任教學校 聯絡電話 地址 電子郵件信箱 如有任何疑問 歡迎您 E-mail 或來電詢問 02-2262-5666 213 楊先生 本公司已盡力處理刊物中圖文的著作權事宜 倘有疏漏 惠請著作權人能與 本公司聯繫 僅此致謝 總公司 北區高中營業處 中區高中營業處 南區高中營業處 地址 新北市土城區忠義路 21 號 地址 臺中市南區樹義一巷 26 號 2 樓 地址 高雄市三民區應安街 12 號 電話 02 2262-5666 電話 04 2261-8485 電話 07 381-1377 傳真 02 2262-0565 傳真 04 3601-8600 傳真 07 960-2868 12