非對稱式密碼學 - 番外 - Miller-Rabin

其實在RSA裡面藏了很多很多的困難，一般來說AES、DES、RC5其實寫程式都沒說很困難。

但RSA中有些東西就真的很困難了。

上一次我們提到幾個點：

1. 要怎麼讓電腦高速計算次方取模。
2. 怎麼求出 4096 位的質數，並確定它是質數。
3. 必需要使用擴展歐幾里得算法。

當 RSA 的位元數 1024、2048、4096，這樣的級別的時候，一般的質數掃描法，幾乎就沒有用了。

因此用一般的方式幾乎沒有辦法處理，必需要使用特定的算法。

而這些算法上我希望能大大家完成自己的RSA系統。

畢竟我們都是工程師，工程師除了用之外，有的時候還要知道一下內部的處理方式。

有些東西就能在必要的時後拆出來用。

好，廢話不多說，接下來將會分幾天提到：

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

那我們先從質數類開始吧～～

質數類

Miller-Rabin

我們簡單地來說明一下數學上的原理好了，這樣才能把程式寫出來。

數學定理

得先知道一個數學上的定理：

1. 如果 (1)^2 mod p 和 (-1)^2 mod p，1 和-1 都為 1 mod p 的『平凡平方根』。
2. 當 p 是質數且 p>2 的時候，不存在 1 mod p 的『平凡平方根』。
3. 我們假設 n 為質數且 n>2，於是 n-1 是偶數，因此可以寫成 2^s*d，s 跟 d 為正整數，d 為奇數。

n=7
7-1 = 6 = 2^1*3
s = 1
d = 3

4. 在 2 到 n-1 取任意數為 a 跟 0<=r<=s-1 來說，必定符合下面兩個公式的一種：
   1. a^d === 1 (mod n)
   2. a^((2^r)*d) === -1 (mod n)
5. 接著拿出『費馬小定理』的：假如 a 是一個整數，p 是一個質數，那麼 a^(p-1)＝ a mod p。
6. 接下來，我們用逆否的方式來證明他是質數，要是上述兩個都『不符合』，那就代表他不是質數。
7. 但在 1 到 n-1 之間我們不知道會不會有符合定理，只能做隨機抽樣 a 於 1 到 n-1 之間，來做檢測。

更詳細的數學我會放在補充資料。

數學計算測試

我們簡單地來算一下：

n = 601
n-1 = 600 = 2^3 * 75
可得 s = 3 , d = 75

取任意數為 a 跟 0<=r<=s-1。
a = 212

1. 212^75 mod 601 = 163 != 1 （不滿足）
2. 212^((2^1)*75) mod 601 = 125 （不滿足）
3. 212^((2^2)*75) mod 601 = 600 = -1 (滿足)

這邊大家可能要知道一下模算數的運算法則。

兩者之間，有一則滿足，要就是 601 是質數，要不然就是 212 是「強偽證」。

手算完之後，我們將這東西寫成程式。

程式碼撰寫（使用 Python）

想必大家應該心裡有底了。

那我們在判斷質數之前，我們先做幾個加速的程式：

1. 先排除 2、3、5、7、13...等小質數（這邊可自由選配看要多少個）。
2. n-1 轉換成 2^s*d。
3. 然後設定要做幾回 Miller-Rabin 測試。
   1. 測試第一先排除條件 1 的『a^d !== 1 (mod n)』。
   2. 測試第二排除條件 2 的『a^((2^r)*d) !== -1 (mod n)』。

判斷小質數

def test_prime_in_100(n: int) -> bool:
    prime_list = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
                  41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
    for i in prime_list:
        if n % i == 0:
            return True
    else:
        return False

n-1 轉換成 2^s*d

def convert_n_to_sd(n: int) -> Tuple[int, int]:
    # n-1 convert to (2^s)*d
    s = 0
    d = n - 1
    while True:
        quotient, remainder = divmod(d, 2)
        if remainder == 1:
            return s, d
        s += 1
        d = quotient

Miller Rabin 測試

def test_prime_in_miller_rabin(a: int, d: int, n: int, s: int):
    if pow(a, d, n) == 1:
        return False
    for i in range(s):
        if pow(a, 2**i*d, n) == n-1:
            return False
    return True

其餘流程

def is_prime_of_miller_rabin_test(n: int, trials_time: int = 5) -> bool:
    if test_prime_in_100(n):
        return False
    s, d = convert_n_to_sd(n)
    for _ in range(trials_time):
        a = random.randint(100, n)
        if test_prime_in_miller_rabin(a, d, n, s):
            return False
    return True

def get_prime(lens: int = 30):
    while True:
        prime = random.randint(10**(lens-1), 10**lens-1)
        if len(str(prime)) != lens:
            continue
        elif prime&1 == 0:
            prime += 1
        if is_prime_of_miller_rabin_test(prime):
            return prime

def main():
    print(get_prime(100))

Miller Rabin 結論

從這邊看來，Miller Rabin速度很快，正確率也很高。

但！Miller Rabin的測試最終還是有機率的問題，因此接下來要介紹一個跟機率沒關係的。

並非使用猜想的方法：AKS質數測試。

最後，其實Miller Rabin也十分好用了。

附上程式碼

作者的話

沒想到寫個已經很麻煩的文章還要看數學，還要寫程式。

好累阿～～～

我明明看到好多人參加比賽，但為什麼大家都還沒開賽？

難道是！存稿！說實話，寫這個好累，好懶得寫阿～

參考資料

米勒-拉賓質數判定法

模算數

費馬小定理 WiKi

RSA 周边——大素数是怎样生成的？

補充資料

The Legendre Symbol