|
|
|
3-3 公開鑰匙的同餘算術
『同餘算術』（Modular Arithmetic）是表示某一進位的運算，譬如有二進位運算、八進位運算、十六進位運算、或 n 進位運算（n 為任何數）。較常使用的同餘算術有加法、乘法和指數運算，其中同餘指數可說是同餘乘法一個特例（譬如 X3是 X × X × X），但它是公鑰系統的主要運算工具。在公鑰系統中有一個重要觀念，即是『反函數』（Inverse Function），表示某數經由演算之後，是否可以由另一個數值找出原來的值。譬如 X 經由計算後得到 Y，是否可以找到另一個數 Z，再由 Y 與 Z 計算出原來的值 X；如果可以的話，Z 便是 X 的反函數。我們試著利用各種同餘算術的推導，來找出是否具有反函數的功能（反向加法或反向乘法），再利用反函數來推論出公鑰系統的公開與私有鑰匙。反向函數又稱為『反向暗門』（Inverse Backdoor），理想狀態反向暗門必須是唯一的；因而，稱之為『單向暗門』。 3-3-1 模數 所謂『模數』（Modulo）是一種除法取餘數的運算，譬如某數modulo 16、modulo 10、modulo 8分別表示某數除以16、10、8的餘數，為了簡化，一般以mod表示。『模數』即是表示在某領域範圍內做運算，參與計算的運算元，以及計算後的結果都不會超過該領域範圍。譬如，modulo 8 運算，則運算元與結果都不會超過 8（0 ~ 7）範圍。如果運算結果超過 8，則取 8 的餘數。如此就非常接近 8 進位計算，但模數沒有進位，直接將進位部份捨棄。習慣上，我們常使用 10、2、8、16 進位的運算，但在密碼學上可能採用任何數（n）進位的運算，常以 modulo n 或 mod n 來表示。 令一個正整數 n 與整數 a，並 a 除以 n 得到商為 q，與餘數 b，之間的關係如下： a = qn + b 0 ≦ b < n；q =「a/n」 其中，q =「a/n」 表示 a/n 整除的數（0 或其它大於 1 的整數）；可能得到的餘數 b = {0, 1, 2, …, n-1}，稱之為『完全餘數系』（Complete of Residues）。上式成立的話，可定義模數運算如下： b ≡ a mod n 其中『≡』表示『相當於』的意思，而並非『相等』（Equal，” = “）；也就是說，b 的值是相當於 a 取模數 n（a mod n）的計算，但並非僅有 a 才可能得到 b，而可能存在其它數值。譬如，a mod 10 = 6，其中 a 可能出現的情況有：6、16、26、、、等等；但這些數存在有一個特性 a = qn + 6，q 為 0 或大於 1 的整數。瞭解模數運算（mod）之後，將其具有的特性歸類如下[1, 86, 121]：
(驗證： 5 ≡ 5 mod 10)
(驗證：5 ≡ 15 mod 10 則15 ≡ 5 mod 10 ≡ 5 = a )
(驗證：5 ≡ 15 mod 10 且15 ≡ 25 mod 10，則 5 ≡ 25 mod 10≡ 5 = a)
(驗證：(15 mod 10) = (25 mod 10)，則 15 ≡ 25 mod 10≡ 5 = a) 接下來，我們利用模數特性，來推論同餘算數。 3-3-2 同餘加法 『同餘加法』（Modular Addition）表示在某個領域（或稱模組，n）內執行加法運算。基本上，參與計算數值的大小應該不會超過該領域，計算後的結果也不會超過該領域（模組 n）。假設 a = 8、b = 7、n=13，則運算結果如下： (a + b ) mod n = (8 + 7) mod 13 = 2 上述表示在領域 13 的同餘加法運算，基本上，運算元（a 與 b）與計算後結果都不會超過 13（0 ~ 12），如果超過 13 的話，則取 13 的餘數。但許多情況下，參與計算數值的大小可能超過領域（模組 n），則取模組餘數後再計算的結果，與相加後再取模組餘數的結果相同，亦即： [(a mod n) + (b mod n)] mod n = (a + b) mod n 式子(4.1) 吾人以 a = 16、b=24、n=13，驗證上述式子(1) 是否成立： 式子(4.1) 左邊 = ((16 mod 13) + (24 mod 13)) mod 13 = (3 + 11) mod 13 = 1 式子(4.2) 右邊 = (16 + 24) mod 13 = 40 mod 13 = 1 則式子(1) 左邊運算結果與右邊相同，該式子成立。此特性對我們推演 RSA 演算法很有幫助。 我們將 modulo 10 的加法，由 0 到 9 之間數字相加的結果顯示於圖 4-3。
圖 4-3 Modulo 10 的加法 接著來探討同餘加法是否具有反向函數的功能。假設以 mod 10 為例，而明文、公開鑰匙、私有鑰匙、以及密文都介於 0 ~ 9 之間。由圖 4-3 可以明顯觀察出 mod 10 具有非對稱加/解密功能，其中公開鑰匙 KU與私有鑰匙 KR之間的關係是 KU + KR = 10，且加密與解密演算法都是同餘加法運算(mod 10)，下列是1 ~ 9 之間加密與解密鑰匙的配對關係：
譬如，KU = 4、KR = 6、明文 P=5，則利用公開鑰匙加密得密文 C = KU +5 = 4+5 ≡9 mod 10，再利用私有鑰匙解密，還原明文為 P = KR + 9 = 6+9≡5 mod 10。 由此可見，KU與 KR之間的關係是互為反向函數，亦即若以 KU加密的密文，便可以利用 KR解密回來，反之亦然。KU與 KR的關係如下(以 mod 10 為例)： KU + KR = 10 亦即： KU + KR≡0 mod 10 因此，我們可以做一個簡單的結論，同餘加法具有反向函數的能力，又稱之為『加法反向』（Addition Reverse）。假設同餘模數為 n，任何數值 y，與其反向元素為y-1，如果滿足『反向函數』，則兩數之間的關係為： y + y-1≡ 0 mod n 或 y + y-1 mod n≡ 0 也就是說，在任何模數（n）運算中，只要找出兩個數的和，可以整除 n 的話，則該兩數互為加法反向函數。 3-3-3 同餘乘法 『同餘乘法』（Modular Multiplication）的概念如同加法一樣，在某一領域內（模組 n）執行乘法運算。基本上，運算元（a、b）與運算結果都不會超過其領域，假設 a = 8、b = 7、n=13，則運算程序如下： (a × b) mod n = (8 × 7) mod 13 = 56 mod 13 = 4 在許多情況下，運算元還是可能超領域。同餘乘法還是滿足，運算元取模組餘數後相乘，與相乘後再取模組餘數，兩者結果相同，亦即： ((a mod n) × (b mod n)) mod n = (a × b) mod n (式子4.2) 吾人以 a = 16、b=24、n=13，驗證上述式子(1) 是否成立： 式子(4.2) 左邊 = ((16 mod 13) * (24 mod 13)) mod 13 = (3 * 11) mod 13 = 33 mod 13 = 7 式子(4.2) 右邊 = (16 * 24) mod 13 = 384 mod 13 = 7 上述左邊運算結果與右邊相同，則式子(4.2) 成立。吾人可觀察出一個重要的特性，式子(4.2) 左邊所計算處理的數值較小，相對的所需的運算量也較少。RSA 演算法大多利用此特性來減低計算量的（容後說明）。 我們也是希望由同餘乘法的特性中，尋找出有關公鑰系統的機能。首先，將 0 ~ 9 之間互相乘積的 mod 10 列於圖 4-4，再來觀察同餘乘法的特性。
圖 3-2 Modulo 10 的乘法 圖 3-2 中，只有 {1, 3, 7, 9} 可做加/解密演算法的鑰匙(原因後述)，至於公開與私有鑰匙之間的關係如下：
譬如，KU = 3、KR = 7、明文 P=4，則利用加密程序可計算密文： C = KU× P = 3 × 4 ≡ 2 mod 10；則密文為 2。 解密程序可還原明文： P = KR× C = 7 × 2 ≡ 4 mod 10；則明文為 4。 公開鑰匙又稱為私有鑰匙的同餘乘法反元素，因此，同餘乘法也具有公開鑰匙演算法的特性。兩者之間關係為 KU× KR≡1 mod 10。 利用同餘乘法所推演出來的反向函數，稱之為『乘法反向』（Multiplicative Reverse）。設同餘模數為 n，任何數值 y，與其反向元素為y-1，如果滿足『乘法反向』，則兩數之間的關係為： y × y-1≡ 1 mod n 0 < y < n；0 < y-1 < n （式子 4.3） 也就是說，在任何模數（n）運算中，只要找出兩個數的乘積，除以 n 得到餘數是 1 的話，則該兩數互為加法反向函數。 式子 4.3 必須當 y (或 y-1) 與 n 互質才會成立，有關證明方面請參考[1, 86, 92]，以下舉兩個例子分別說明之。 例1：若 a = 3, n = 10。因為 3 與 10 互質，所以存在一個 b (0 < b < 10)使得 a × b ≡ 1 mod n ( 3 × 7 ≡ 1 mod 10, b = 7) 例2：若 a = 5, n = 10。因為 5 與 10 不互質，所以找不到一個 b (0 < b < 10)滿足式子(4.1)。 因此利用同餘乘法依然存在公開鑰匙系統的鑰匙配對，只要找到一個 a ( < n ) 與 n 互質，必然存在一個 b ( < n ) 符合式子(4.1)，當然若 n 是質數，則每一個a ( < n ) 皆與 n 互質。 3-3-4 同餘指數 『同餘指數』（Modular Exponentiation）運算即是在某領域內（模組 n）執行指數運算。基本上，參與運算元與結果的大小都不會超過該領域，譬如 a =4、b=6、n=13，則運算程序如下： ab mod n = 46 mod 13 = 4096 mod 13 = 1 吾人可以發現，指數運算不需較大的數值參與運算，就可能產生非常大的運算量，沒經過特殊方法運算，幾乎很難完成指數運算（RSA 主要運算方法）。與同餘乘法相同，數值取模組餘數後再執行運算的結果，與執行指數運算後，再取模組餘數的結果相同，亦即： (a mod n)b mod n = ab mod n （式子 4.4） 吾人以 a = 16、b=4、n=13，驗證上述式子 (4.4) 是否成立： 式子 (4.4) 左邊 = (16 mod 13)4 mod 13 = 34 mod 13 = 81 mod 13 = 3 式子 (4.4) 右邊 = 164 mod 13 = 15536 mod 13 = 3 依照上述驗證，式子 (4.4) 左邊與右邊運算結果相同，式子成立。吾人也可以發現右邊的計算量非常大，如果能轉換成左邊計算方法，將可以減低許多運算量。吾人大都利用此特性來實現 RSA 演算法。 接著，必須推演同餘指數是否具有反向暗門特性，藉此觀察是否利用它來實現非對稱密碼系統。圖 4-5 為 0 ~ 9 之間 mod 10 的運算結果，表內數字為 xy的結果，其中 x 為列的數字；y 是行的數字。
圖 3-3 modulo 10 的指數運算 其實指數運算表示自我函數相乘的次數，如 X3表示 X 自我相乘 3 次。同餘指數是同餘乘法運算的延伸，它的反向函數也與同餘乘法相同，如下：（公式 4.3） y × y-1≡ 1 mod n 由圖 3-3 可以找出合乎反向暗門條件的鑰匙 KU（y）與 KR（y-1）如下：（n = 10）
譬如，明文 P = 8、公開鑰匙 KU = 3、私有鑰匙 KR = 7，則加密程序為： 加密：密文 C =
解密程序為： 解密：明文 P =
同樣的，將利用私有鑰匙加密，也可利用公開鑰匙還原。吾人可證明出同餘指數運算具有反向暗門（乘法反向），兩支鑰匙之間的關連為 KU× KR≡1 mod 10（與同餘乘法相同）。 3-3-5 Euler’s Totient 函數 Euler’s Totient 函數 ψ(n) 是公開鑰匙演算法中重要的參數，其意思是小於 n 但與 n 互質之正整數的數目，譬如ψ(10) = 4，因為小於 10 且與 10 互質的正整數共有 4 個 (1, 3, 7, 9)。圖 4-6是ψ(n), 0 < n < 31, 的函數值。
圖 3-4 Euler’s Totient 函數 由圖 3-4 可以觀察出來，如果 p 為質數的話（圖中有陰影的欄位），則： ψ(p) = p-1 譬如，p=3，則ψ(3) = 3-1=2；p=19，則 ψ(19) = 18；依此類推。現在假設有兩個質數 p 與 q，且 n = pq，則：（證明請參考 [1, 92]） ψ(n) =ψ(pq) =ψ(p) × ψ(q) = (p-1) × (q-1) （式子 4.7） 驗證，如果 p=3、q=7，所以n = 3 × 7 = 21，則： ψ(21) =ψ(3) × ψ(7) = (3-1) × (7-1) = 2 × 6 = 12（如同圖 4-6 所示） 我們來回顧一下ψ(n) 的特性，它代表著與 n 成為『互質』的數目。在同餘運算中，質數經由某一數運算之後，最有可能產生餘數，這也是推論公鑰演算法的最基本要素。因此，ψ(n) 的數值愈大，則可能選用的質數就愈多，以圖 4-5 為例（同餘指數運算），ψ(10) = 4，則可選用與 10 互質的數只有四個（1, 3, 5, 7），並且運算結果每 4 列便再重複。
|
翻轉工作室：粘添壽
資訊與網路安全技術
翻轉電子書系列：
|
