【代數】

張貼日期：Mar 07, 2017 2:21:4 PM

作者：張飛黃 副教授（國立臺灣師範大學）

Designed by D3images - Freepik.com

UniMath 去年刊出了兩篇發現超大質數的文章【發現超大質數！ 高達150000美金的超級質數任務】【［新發現］史上最大的孿生質數！】，文章裡面沒有講，但一般人可能會感到疑惑的問題：找到超級大的質數究竟有甚麼厲害的地方？本文目的就是要說明，超大的質數目前最重要的應用－密碼。

密碼學

說來諷刺，在歷史的長河裡，埋葬眾多英魂的戰場同時也是催生了許多現代重要科學的地方，密碼學正是其中之一。即使在今日，不論是個人機密、商業機密甚至於國防機密，也都仍然仰賴密碼學的應用；在第一次世界大戰(1914~1918)中，各國重要的戰略資訊都還是屬於人工加密階段，俄國因為找到多份德國的檔案及電碼本，而破解了德國在許多戰略上的資訊，包括德國建議盟國墨西哥與日本侵略美國，德國將提供軍事以及資金的援助。這些密文內容被英國所揭開後，促使美國在 1917 年 4 月向德國宣戰，進而改變了第一次世界大戰的局勢。而第二次世界大戰德國吸取了第一次大戰的失敗經驗，發展出以機械代替人工的加密方法。在電影「模仿遊戲」中，就講述英國數學家、邏輯學家、密碼分析學家和計算機科學家艾倫·圖靈在二戰中幫助盟軍破解德國軍事密碼的真實故事，因而縮短了第二次世界大戰的持續時間。從這些歷史事件看來，密碼學的發展無庸置疑對於現今地球的局勢影響是非常巨大的。

密碼學一般可分為兩個過程，其一是「加密」，意思是將我們想要傳遞的訊息（我們以下稱為明文）轉換成難以理解的資料（密文）的過程；第二是「解密」，將密文轉換回明文的過程。

為了方便說明，我們以同班同學小明與小華之間的一段對話為例，小明小華大概彼此累積了前幾世解不開的因緣吧，才會到現在還緊緊糾纏ＸＤ。「小華，請你在 01 給我 07」；很明顯地，我們聽到了一段密文，這是小明與小華之間不想讓其餘同學所知道的一段訊息。在此，可以理解小明有一個方法將想說的話編譯成密文，而小華也有方法能夠將密文還原為明文，一般的人除非撿到下列這張字條，

或者聽到小明或小華說出明文，否則光以「小華，請你在 01 給我 07」這句話來看，幾乎是不可能破解密文的。

但是，這樣的密碼學卻有著許多使用上的限制，我們可以假設一下，假設全班其他 40 位同學都用密文與小華說話(編按: 小華的人生也太辛苦了)：

１）如果全班都共用一套編碼規則，則等於每個人都聽得懂密文。這個時候傳遞密碼時就得小心避免被竊聽，否則後果不堪設想。筆者想起「聽風者」這部諜報電影中的橋段，周迅飾演的張學寧在片中擔任共產黨特務頭子，代號「老鬼」，在諜對諜的過程中，由於何兵（梁朝偉飾演）聽錯了從電台攔截到的摩斯密碼，把「老鬼曝光，速戰速決」聽成了「重慶曝光，速戰速決」，電影中設定敵軍首腦代號正好是重慶，意外害死了張學寧。

２）或者每個人獨立跟小華各有一套編碼規則，但這樣一來，小華自己就需要準備 40 套編碼規則。

是否有方法可以處理上述的限制呢？

答案是有的。這個方法就是現今在金融系統中被廣泛使用的「RSA 公開密碼系統」。

電影聽風者劇照

大的數難以快速的質因數分解

RSA 密碼系統所依賴的數學原理很簡單－質因數分解。請試著回答「1037」是否為質數？大家是否還記得一些判別方法呢？或者慢慢來檢查 1037 是否為 2、3、5、7、11、…的倍數。在我們國小高年級數學課，黑板上的因數、倍數與質因數分解，告訴我們在正整數的世界裡，一個正整數若不是質數，那麼就能唯一分解成質因數的乘積。

但是要判別一個正整數是否為質數，本身就不是太容易的事；而要對大的整數做質因數分解，更是連電腦都不易做到的工作。過去金融系統的保密安全性就可以說是建立在約 1,000,000 位數這樣的一個大整數不容易質因數分解的保護傘之下。

在本文裡，我們不會去證明或談論 RSA 公開密碼系統背後嚴謹的數學定理或其它細節，但我們希望能讓大家了解這樣的系統大致上是如何運作的。

RSA 公開密碼系統

RSA 公開密碼系統是 1977 年由 Ron Rivest、Adi Shamir 和 Leonard Adleman 所一起提出的，RSA 就是他們三位學者的姓氏開頭字母拼在一起而組成的。而為何稱做「公開」密碼系統呢？主要原因就是

編碼的規則可以讓所有人都知道！

在此，我們也把這個編碼規則稱為「公鑰」，讀者可以想像有一個很多位數的正整數(其實是兩個大質數的乘積)就是公鑰，而知道這個數字分解的方法就是所謂「私鑰」；在一開始講述的例子裡，如果小華要跟全班通訊，只要將用自己私鑰所產生的公鑰公開給大家來做編碼的規則即可，不是加密者要解譯已經編好碼的密文，幾乎是不可能的任務，只有像小華已經擁有私鑰（或者能夠質因數分解公鑰的人）才能將密文還原為明文。而安全性就是建立在超大質數的質因數分解是非常困難的任務，即使是用電腦計算！

在公開密碼系統的運作過程裡，其加密的方式與原理是所有人都知道的，並且也知道其解密的原理，但是仍然可以保證其安全性，這是不是很神奇呢！如果在當年的世界大戰中，德國應用的是公開密碼系統，最後很可能是完全不一樣的結果吧。

RSA 的運作流程

為了使有興趣讀者能更清楚 RSA 公開密碼系統的加解密過程，以下補充說明 RSA 的運作過程。

明文：M=314 (明文通常是很長串的數字，且須跟 N 互質)

公鑰：N=5767 (為兩個質數 73 與 79 之乘積，實際使用上是兩個超大質數) 與 e=55 (與 5616 互質的數字，這裡 5616 =(73-1)(79-1)，記作φ(N)。)

私鑰：d=919 (d 為滿足 e · d ≡ 1 (mod φ(N)) 的數字)

加密：314⁵⁵ ≡ 5485 (mod 5767) ＊ 此處 5485 = C 即為密文 ＊

解密：計算 C⁹¹⁹ (mod 5767) 即得到明文 M=314

這中間的原由正是鼎鼎大名的歐拉定理 [Euler’s Theorem]

M^φ(N) ≡1 (mod N)，其中 M 和 N 為互質的兩個正整數。

在上述的例子裡，可得到 314⁵⁶¹⁶ ≡1 (mod 5767)，這保證其解密的正確性

C⁹¹⁹ = 5485⁹¹⁹ = (314⁵⁵)⁹¹⁹ = 314^5616k+1 ≡ 314 (mod 5767)

延伸閱讀

1. 發現超大質數！ 高達150000美金的超級質數任務，陳宏賓，UniMath。

2. 繼張益唐縮小相鄰質數的間隔之後，天才數學家陶哲軒讓它變大了!，陳宏賓，UniMath。

3. ［新發現］史上最大的孿生質數！，陳宏賓，UniMath。