[Day 12] 012 - 非對稱式密碼學 - Asymmetric cryptography （番外）（二） - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天

第 12 屆 iThome 鐵人賽

DAY 12

Security

無趣的密碼學，有趣的加密！系列第 12 篇

[Day 12] 012 - 非對稱式密碼學 - Asymmetric cryptography （番外）（二）

12th鐵人賽

dennysora

2020-09-14 00:46:54

3427 瀏覽

分享至

非對稱式密碼學 - 番外 - AKS、擴展歐幾里得

一樣回顧一下，我們已經處理完了質數類的『Miller-Rabin』。

接下來一口氣把其他兩個介紹完吧～

最後一個我放別人的文章連結……（我自己沒時間讀，然後難度也有……請體諒。）

接下來將會提到：

質數類：
1. AKS 質數測試
模反元素：
1. 擴展歐幾里得算法
大整數冪取模演算法：
1. 蒙哥馬利演算法（大約瞭解就好，python 的 pow 更快更強大。）

質數類

AKS 質數測試

這個可就厲害了，由印度的三個大神尋找出來的方法。

一般在判斷質數的其中幾個重點：

一般的。
多項式的。
確定性的。
無仰賴質數判定演算法的。

在目前來說，很多質數判定，很快速的、確定的，必需要有特定條件的質數。
要不然就是，很快、無特殊條件、無仰賴其他的判定，但就是利用猜想。

一直都沒有三者都達到的算法，而我接下來要介紹的就是那麼厲害的算法，4項條件都符合，速度也夠快。

上一次我們介紹的Miller-Rabin能在多項式時間內給出確定性的結果，但因為廣義黎曼猜想未被證明，因此也不能說是確定性的。

而AKS演算法並無仰賴任何為證明的猜想。

數學定理

一樣的我們必須要補完一些數學上的定理。

先設定n是大於等於2的質數，a是隨機數。
那麼(x + a)^n === (x^n + a) (mod n)就會成立。
我們把這個公式變成能用的形式。
(x - 1)^n - (x^n - 1) 只要係數能被n整除，那就是質數了。

這邊其實使用了同餘多項式來處理，但為了方便我們程式處理，加上我腦袋已經不想看數學了，就大家看一下論文吧～

好沒了，那我們動手算一下。

證明？喔～那東西我放在附錄了，我找了4篇的論文，希望大家很舒服的看。

記得看完再來我下面留言教教我這樣的學渣阿～

數學計算測試

我們設n=3

(x-1)^3 - (x^3 - 1)
= (x^3 - 3x^2 + 3x - 1) - (x^3 - 1)
= -3x^2 + 3x
嗯啊，可以被n=3整除，是質數。

(x-1)^n
這邊要使用二項式定理來處理。

程式碼撰寫（使用 Python）

def aks (n: int):
    if n == 2:
        return True
    c = 1
    for i in range(n//2+1):
        c = c*(n-i)//(i+1)
        if c % n:
            return False
    return True

結束～

等等！先別打我！
Rosetta Code AKS_test_for_primes
其實他有幫你寫好了。

AKS 質數測試結論

雖然看起來程式寫好了……

但其實不能用，不信的話你自己拿去跑10位數質數就知道。

因此我們必須再參考一些其他的處理方法。

我有找到一份別人的寫的AKS_PrimeTest。

但我這邊實際測試50位數就都會錯誤。

我不知道為什麼，但目前開源出來的程式沒找到。

我個人是很推薦『Miller-Rabin』的算法，至少我們在處理公式跟撰寫時，能很簡單地處理。

而且速度很快之外，佔用量也小。
AKS並不是最快的，它只是能在方程時間內，判斷確切的質數。
但目前我找的程式碼，卻沒有辦法體現它的優勢。

我這邊也只是寫文章介紹，如果要花時間開發AKS的算法，這篇文章可能要再花好一段時間了。

所以目前就先到這邊，看看各位大神有沒有什麼話說。

或者有什麼資料可以分享的。

模反元素：

我們接著把這模反元素的，擴展歐幾里得算法快速地講完。

擴展歐幾里得算法：

聽過歐幾里得算法嗎？沒聽過？去重讀國高中。

好我知道，我講另一個名字『輾轉相除法』知道嗎？

如果知道，那就簡單了。

而『擴展歐幾里得算法』其實就是在做『輾轉相除法』，但順便將模反元素算出來。

我們看個圖一：

圖片來自擴展歐幾里得算法 WiKi

這原理其實也不難懂，互質兩者的最大公因數就是1。

那我們RSA的求d也不就是e*d === 1 (mod r)，然後r跟e互質。

而擴展歐幾里得算法的等效公式：ax+by = gcd(a,b)。

然後因為是輾轉相除法，因此會不斷地重複，直到餘數等於0。

假設我們設b為0，其 ax = gcd(a,b) = 1（如果a跟b互質）。

不就是 e*d === 1 (mod r) 嗎。

證明的部分我就不做了，大家有興趣自己去看文件。

接下來寫程式。

程式碼撰寫（使用 Python）

我想大家可能會有點不知道怎麼寫。

首先先把互質的e跟r選好後，兩邊取最大公因數。

並紀錄x，然後不斷地讓b歸零，做遞回。

當b等於0時，回傳x=1跟y=0，這時滿足 ax = gcd(a,b) = 1（如果a跟b互質）。

然後開始堆疊計算出來的數據，最後輸出x跟y。

使用y-a//b*x來堆疊計算結果，也就是等效於擴展算法，這邊補充一個等效的解釋：gcd和egcd算法。

def ext_gcd(a: int, b: int) -> Tuple[int, int]:
    if b == 0:
        return 1, 0
    else:
        y, x = ext_gcd(b, a % b)
        y = y-a//b * x
        return x, y

在程式中你能看到，做輾轉相除法，並堆疊數值還有交換。

但如果x為『負』，則直接捨棄這組r。