|
|
|
3-2 公開鑰匙的數學基礎
『數論』（Number Theory）是公開鑰匙密碼學的理論基礎，本節就相關部份做簡單介紹，讀者若有興趣可參考。 3-2-1 質數 『質數』（Prime）是密碼系統主要計算數值，因為密碼系統大多採用『模數』（Modulo）算術推論出來的。質數在『模數』運算裡出現的重複性最低，計算結果最能接近『唯一性』。 『質數』（Prime）：一個只能被 1 或自己整除的數值，稱之為質數。質數是除了 1 和自己之外，除以小於本身的任何數都會有餘數，下列是1 到 100 之間的質數：
一般在加密演算法裡常出現尋找質數的問題，並且為了不讓他人猜測出所找的數為何，都會選擇一個較大的數值範圍。就實際觀點而言，欲尋找一個很大的質數並非易事，一般可能利用亂數函數隨機取一個數，再測試這個數是否為質數(有關測試質數演算法可參考 [1, 7, 136])。接下來，簡單介紹質數的特性。 對任意 a >1的數，可以被分解成：
其中，p1, p2, …, pi都是質數，且 p1 < p2 < p3 < …< pi，每個 αpi > 0。也就是說，任何一個數都可分解成質因數的乘積。譬如： 3600 = 24× 32× 52 其中： p1 = 2、α2 =4（因 p1 = 2，則αp1 =α2）； p2 = 3、α3 =2（因 p2 = 3，則αp2 =α3）； p3 = 5、α5 =2（因 p3 = 5，則αp3 =α5）。 如果想要計算兩個數的乘積，可由相關質因數的指數（αpi）來計算（指數的和），譬如，216 = 12 × 18，可由下列計算得到： 12 = 22× 31，則α2 =2、α3 =1。 18 = 21× 32，則α2 =1、α3 =2。 216 = 23× 33，因為α2 =2 + 1= 3、α3 =1 + 2 =3。 3-2-2 互質數 若 gcd(a, b) 表示 a 和 b 的最大公因數，則 gcd(a, b) = 1表示 a 與 b 互質；也就是說，a 與 b 之間除了 1 之外，沒有其他公因數。現在我們來觀察如何計算出兩數之間的最大公因數。首先將任意兩數分解出其對應的質因數冪次方的乘積，接著選取較低冪次方的因子，將這些因子相乘便是兩數的最大公因數。譬如，欲找出 18 與 300 兩數的最大公因數 gcd(18, 300)，可由下列計算式得到： 300 = 22× 31× 52； 18 = 21× 32× 50，則： gcd(300, 18) = 21× 31× 50 = 6 上述尋找最大公因數的例子，看似簡單，其實對一個很大的數做質因數分解並非易事，目前雖有一些相關演算法，但其複雜度仍然偏高，這方面尚有研究空間。話說回來，找出兩個質數且具有互質條件，可說是公開密碼演算法精髓所在。至於如何尋找兩個互質的質數？這方面就留給讀者慢慢去探討。
|
翻轉工作室：粘添壽
資訊與網路安全技術
翻轉電子書系列：
|
