加密，究竟有幾秘密？｜星島教室

眾所周知，密碼與我們的日常生活息息相關，而數學在密碼學中扮演着一個非常重要的角色。「加密」（Encryption）是將原來的訊息（明文）改變為難以理解及讀取的密文。經過「解密」（Decryption）過程，密文才能還原為明文。加密法分為「對稱加密法」及「非對稱加密法」，本文將扼要介紹對稱加密法及非對稱加密法，並提供簡化例子予讀者研習，以加深各位對相關課題的認識及理解。

對稱加密法

Alice想給Bobby傳遞一個訊息 m （ m 稱為明文），為讓讀者更易理解，我們可假設m為一個整數，Alice將 m 加上一個整數 e （ e 為一個密鑰）後訊息變為 m＋e ，以上過程是為加密法。加密後訊息由 m 轉變為 m＋e ，我們稱 m＋e 為 c （ c 可稱為密文），在解密過程中，將 c 減去 e 後Bobby便可得到訊息 m 。由於在加密及解密的過程中我們使用相同的密鑰，故此以上的加密法稱為對稱加密法。

例子︰

訊息 m＝3，密鑰 e 為－100，由此密文 c＝m＋e＝3－100＝－97。

解密之後，訊息為 c－e＝－97－(－100)＝3，即Bobby可接收原來的訊息。

RSA加密演算法（非對稱加密法）

在對稱加密法中，由於加密及解密的密鑰相同，如在過程中被黑客發現密鑰，訊息便會被破解，為提高安全性，在1977年，3名在麻省理工學院工作的科學家，羅納德．李維斯特（Ronald Linn Rivest）、阿迪．薩莫爾（Adi Shamir）和倫納德．阿德曼（Leonard Adleman）共同提出了一種非對稱加密演算法，即RSA加密演算法，RSA加密演算法在電子商業中被廣泛使用。RSA加密演算法就是以他們3人姓氏開頭字母拼在一起組成的。RSA加密演算法是一種非對稱式密碼學，它需要兩個密鑰，一個是公開密鑰，其作用是為訊息加密；另一個是私有密鑰，用作解密。公開密鑰把明文（原本訊息）加密後所得的密文，只能用相對應的私有密鑰才能解密並得到原本的明文，最初用來加密的公開密鑰並不能用作解密。由於加密和解密需要使用兩個不同的密鑰，故此RSA加密演算法被稱為非對稱加密法。

RSA加密演算法原理及流程

1. 先隨機選擇兩個非常大的質數 p 及 q 。

2. 設 n＝pq。

3. 設 ＝(p－1)(q－1)。

4. 選定一個足夠大的整數 e 使得 1＜e＜ 及 e 與 互質（即 e 和 的最大公因數為 1）。

5. 求 d 唯一的值使得 1＜d＜ 及 e×d≡1(mod ) 。
[e×d≡1(mod ) 表示 e×d－1 可被 整除]

6. (e, n) 及 (d, n) 分別為公開密鑰及私有密鑰。

7. 假設Alice想給Bobby傳遞一個訊息 m (mn) ，使用公開密鑰加密後的密文 c 為 me 被 n 除後的餘數。

8. 使用私有密鑰 (d, n) 解密，Bobby可得到原本的明文 m ，其中 m 為 cd 被 n 除後的餘數。

RSA 加密演算法流程

為使讀者更易明白RSA加密演算法原理及流程，以下例子中使用了數值很小的質數示範RSA加密演算法的原理，在實際操作上， p 和 q 均為非常大的質數。選取大質數是基於保安理由，黑客在得到公開密鑰 (e, n) 後想設法得到私有密鑰 (d, n) ，他必須知道 的值（e×d≡1(mod ) ），而由於 ＝(p－1)(q－1)，他要計算 p 和 q 的值，換句話說，他須使用電腦因式分解一個非常大的整數 n (n＝pq)，n 愈大，破解私有密鑰的困難便會愈大，故此對於足夠大的 n 而言，RSA加密演算法頗為安全。

例子

我們選取兩個質數p及q，其中p＝7及q＝13 。

n＝pq＝91 及 ＝(7－1)(13－1)＝72 。

取 e＝29 使得 1＜e＜ 及 e 與 互質。

由此 d＝5 （因為 e×d－1＝29×5－1＝144＝72×2 ，即是 e×d≡1(mod )）

公開密鑰及私有密鑰分別為 (29, 91) 及 (5,91) 。

設 m＝2 (mn) ，c 為 me 被 n 除後的餘數，即 c 為 229 被 91 除後的餘數，得 c＝32 。

使用私有密鑰 (5, 91) 解密密文， m 為 cd 被 n 除後的餘數，即 m 為 325 被 91 除後的餘數，得 m＝2 。

練習

我們選取兩個質數p及q，其中 p＝3 及q＝11 。

設 m＝6 。

求 n, , d, e 及 c 的值，並證明使用私有密鑰可將密文還原為明文。

建議答案︰

n＝33, ＝20, d＝7, e＝3 及 c＝18

文：仁濟醫院羅陳楚思中學副校長譚在能、仁濟醫院羅陳楚思中學數學科老師曾韋怡及仁濟醫院羅陳楚思中學數學科老師鄧頌賢

本欄逢周四刊登，由教育評議會邀請資深中小學老師、校長及大學講師撰稿，旨在為學生提供多元化的STEAM學習材料，引發學生探求知識的興趣，將學習融入生活，培養學生的世界觀、敏銳的觸覺、積極學習的態度。

延伸閱讀：

〈天問〉｜星島教室

《星島頭條》APP經已推出最新版本，請立即更新，瀏覽更精彩內容：https://bit.ly/3yLrgYZ