「公開金鑰密碼系統」是怎麼想出來的？

作者：股滿意足

撰寫日期：2024/7/23

  筆者在私立科技大學教授密碼學(cryptography)多年，想來談一下需要二支鑰匙的新一代「公開金鑰密碼系統(Public-key cryptosystem)」是如何被想出來的？也順便聊一下自己為何跨入密碼學領域的？

  筆者是在成大電機所博士班畢業後，到中山科學研究院服國防役，原先是做容錯電腦系統(Fault tolerant computing)研究的，沒接觸過密碼學，學校也沒有人開這方面的課，因為那時候網路才剛萌牙，還在把台灣的大學網在一起實驗的階段，所以以前常在戰場上使用的密碼學，也還沒有被大部分人看出在網路的重要價值。有一天，從中山科學研究院休假，跑去台北市逛重慶南路的書店，看到張真誠教授寫的「電腦密碼學與資訊安全」[1]這本書，因為之前有看過報紙報導年輕的張真誠教授擔任日本一知名學術研討會主席的事，知道張教授超會寫學術論文的，所以就買了這本書回去研究研究他為什麼這麼會寫論文。

  在看「電腦密碼學與資訊安全」這本書時，看到RSA密碼系統[2]時，發現加密(encryption)及解密(decryption)用了一個簡單的指數公式：(1) 加密：C=M^E mod N，(2) M=C^D mod N，「^」是指數運算，「mod」是求餘數的運算，M是原本的訊息，即明文(plaintext)，C是密文(ciphertext)，E是加密的鑰匙，D是解密的鑰匙。當傳送方將欲傳遞的明文M，利用加密的鑰匙E加密後變成另外一個訊息密文C，然後經過公開網路，傳遞給接收方。接收方收到密文C以後，利用解密鑰匙D將其還原成明文M。當時腦袋想到的是指數公式很簡單，但是計算卻很費時，如果能用博士班修過的平行處理(parallel processing)的方式，也許可以改善指數計算時間。後來找到辦法，將傳統指數演算法改成平行演算法，計算時間增快約33%，這個演算法有投稿到英國期刊International Journal of Computer Mathematics，接受並發表[3]。這是第一個用平行處理方法去加快RSA密碼系統的論文，後來這個演算法也被張真誠教授的另一本書「近代密碼學及其應用」[4]收錄。張真誠是台灣最早切入密碼學的學者之一，其卓越的貢獻，現被尊為「台灣密碼學之父」[5]。談點當初修孔令洋教授開的「平行處理」課的事，「平行處理」是開在博士班的課，孔教授第一次上課時講了2件事，第一件是開教科書，開了黃鎧教授的「Computer Architecture and Parallel Processing」[6]這本書，第二件是請一起修課的大學長蔡老師安排每周上課章節及負責講解的同學。由於要上台報告教科書的某一章節，黃鎧的「Computer Architecture and Parallel Processing」這本書又超級難，超級難的意思是黃鎧教授收集了相當多的論文，某一章節可能是某篇論文的精華，說精華就是沒頭沒尾，只放中間精華之處，所以非常難念，因為沒有來龍去脈，逼得非找原始論文不可。也因為不是老師講給學生聽，而是學生講給老師聽，當時覺得老師好混，現在回頭來看，是我修過的課裡面最有收獲的。李遠哲院士在獲得諾貝爾化學獎時，感謝他的指導教授用放牛吃草方式帶他，每次他問指導教授：「這怎麼做？」，他的指導教授總會回答：「我怎麼知道，會做的話我早就做了！」[7]，華人總喜歡用填鴉式想把所有知識教給學生，也許，什麽都不教，會是更好的選擇。

  「公開金鑰密碼系統」是怎麼想出來的？密碼系統原來都是加密鑰匙和解密鑰匙相同，是同一支鑰匙，也俗稱一支鑰匙密碼系統(one-key cryptosystem)或對稱密碼系統(symmetric cryptosystem)，常用的是美國政府制定的「資料加密標準(Data Encryption Standard, DES)」 [8]，即FIPS PUB 46。因為半導體技術的進步，使得電腦運算能力愈來愈快，也讓加解密快速的對稱密碼系統，常常需要換新鑰匙，但因為只有一支鑰匙，所以如何又方便又安全的將新鑰匙告知對方，變成一個重要的研究課題。在1976時，在史丹佛大學(Stanford University)電機系的Diffie 和 Hellman兩位學者在權威期刊IEEE Transactions on Information Theory發表了「New directions in cryptography」[9]論文，這篇論文有兩大貢獻，第一個貢獻是提出如何交換新鑰匙，即「迪菲-赫爾曼密鑰交換（Diffie–Hellman key exchange）協議」。第二個重要貢獻是提出新觀念：2支鑰匙的密碼系統，並稱之為Public-key cryptography，這是Public-key cryptography這個字眼第一次出現，雖然當時他們並沒有導出這樣的密碼系統。後來他們兩位也因此篇論文卓越的貢獻，獲得有資訊界諾貝爾獎之稱的圖靈獎(Turing Award)。

  在Diffie 和 Hellman提出Public-key cryptography概念後，麻省理工學院Rivest教授和當時同在他的電腦科學實驗室研究的Shamir和Adleman兩位學者於1978年共同導出第一個需要2支鑰匙的公開金鑰密碼系統[2]，後來大家習慣稱他們的方法為RSA密碼系統。RSA密碼系統就如前所述是用指數運算方法，那他們當初是怎麼想出來的？

  Rivest、Shamir、和Adleman三個人當初的靈感也是受到Diffie 和Hellman在「迪菲-赫爾曼密鑰交換協議」裡使用指數運算的啟發。在400多年前，一個業餘數學家的法國律師，Pierre de Fermat((皮耶·德·費馬)，提出費馬小定理(Fermat's Little Theorem， FLT)，即a^(p-1) mod p≡1，或是將等式左右兩邊各乘上a以後得a^p mod p≡a。經過100年後，瑞士數學家Leonhard Euler(李昂哈德·尤拉)，在提出尤拉統計函數(totient function) φ(n)，φ(n)是小於等於n的正整數中與n互質的數的數目，兩個正整數互質的意思是說它們的最大公約數為1，也就是說除了1以外，沒有更大的正整數可以同時除盡這兩個數。然後，他將費馬小定理用他的尤拉函數擴充成費馬-尤拉定理(Fermat–Euler theorem) 或 稱為尤拉統計定理(Euler's totient theorem)如下： a^(φ(n)) mod n≡ 1，a 和n互質。此式還可再擴展為a^(k*φ(n)) mod n≡ 1，k為任何大於等於1的正整數。如果等式左右邊各乘上a，公式就變成：a^(k*φ(n)+1) mod n≡ a。

  算術基本定理(Fundamental Theorem of Arithmetic)說明每個大於1的自然數，都可以分解成質數冪次方相乘。所以費馬-尤拉定理的指數部分k*φ(n)+1也可以分解成2個自然數的相乘，如k*φ(n)+1=e*d，所以

a^(e*d) mod n=a

  => (a^e)^d mod n=a

若c=a^e mod n是加密，明文a，透過加密鑰匙e，變成密文c。然後，解密的動作就是a=c^d mod n，就從密文c，利用解密鑰匙d，變成明文a。這就是RSA密碼系統的思考來源了，那這個容不容易被破解？當n值很大時，破解很困難，相當於解NP-complete的問題。

參考資料：

[1] 張真誠，「電腦密碼學與資訊安全」，ISBN:9572201239，松崗電腦圖書資料股份有限公司。

[2] R. L. Rivest, A. Shamir, and L. Adleman, “A Method for Obtaining Digital Signatures and Public- Key Cryptosystems,” Communications of the ACM, Vol.21, No.2, Feb. 1978, pp.120-126.

https://dl.acm.org/doi/pdf/10.1145/359340.359342

[3] C. W. Chiou, “Parallel implementation of the RSA public-key cryptosystem,” International Journal of Computer Mathematics, Vol.48, No.3–4, 1993, pp.153–155. https://doi.org/10.1080/00207169308804198

[4] 賴溪松、韓亮、張真誠，「近代密碼學及其應用」，ISBN：9789577179494，松崗出版社， 1995/9。

[5] 魯永明，「創校相陪16載「台灣密碼學之父」張真誠獲頒中正大學名譽博士」，聯合報，2023/03/14。

https://udn.com/news/story/6928/7031587

[6] K. Hwang and F. A.  Briggs, Computer Architecture and Parallel Processing, a graduate-level textbook by McGraw-Hill Book Co., New York, 1984, (846 pages). Chinese translation by Science Press, China, in 1987.  Spanish translation by A. B. Paloma and J. Ruz Ortiz, Univ. of Madrid, Libros McGraw-Hill De Mexico, Spain 1988.

[7] 李遠哲，「我的學思歷程～諾貝爾獎得主李遠哲院士獲邀中國醫藥大學〔博雅經典講座〕專題演講，激勵青年學子要和志同道合的人創造一個更美好的世界」，中國醫藥大學， 2024/03/12。

https://www.cna.com.tw/postwrite/chi/365236

[8] 「Data Encryption Standard」, Federal Information Processing Standards Publication 46, 1977/1/15.

https://csrc.nist.rip/files/pubs/fips/46/final/docs/nbs.fips.46.pdf

[9] W. Diffie and M. Hellman, "New directions in cryptography," IEEE Transactions on Information Theory, Vol. 22, No. 6, pp. 644-654, November 1976.

 doi: 10.1109/TIT.1976.1055638.