一次性密碼本與質數探討

一次性密碼本加密法，又稱 OTP，其核心概念在於使用與訊息等長的隨機金鑰，且該金鑰僅使用一次。由於金鑰的隨機性和唯一性，使得 OTP 在理論上是無法被破解的，即使攻擊者擁有無限的計算能力。然而，實際應用中，生成和安全分發與訊息等長的真隨機金鑰非常困難，限制了 OTP 的廣泛應用。文章接著探討了質數在密碼學中的重要性，特別是在 RSA 等公鑰加密演算法中的應用。質數的特性使其成為建構安全加密系統的根本。接著介紹了兩種常用的尋找質數的方法：簡單除法測試和埃拉託斯特尼篩法。簡單除法測試適用於判斷較小數字是否為質數，而埃拉託斯特尼篩法則能高效地找出一定範圍內的所有質數。最後，針對超大質數的判斷，文章詳細介紹了 Rabin-Miller 演算法，這是一種機率性演算法，能夠快速判斷一個大數字是否為質數，並提供了 Python 程式碼實作範例。

第22章 - 一次性密碼本（One-Time Pad）密碼法

一次性密碼本密碼法是一種無法破解的加密技術。即使擁有無限的計算能力，也無法攻破這種加密方法。我們已經擁有的維吉尼亞密碼程式無需任何修改即可實作一次性密碼本。

為何一次性密碼本無法破解

要了解為何一次性密碼本（OTP）無法破解，我們需要先了解為何一般的維吉尼亞密碼可以被破解。我們的維吉尼亞密碼破解程式是透過頻率分析來工作的。但是，如果金鑰的長度與訊息相同，那麼每個可能的密鑰字母對於同一個明文字母的出現機率是相同的。

假設我們要加密的訊息是「ifyouwanttosurviveouthereyouvegottoknowwhereyourtowelis」（去掉空格和標點符號後有55個字母）。為了使用一次性密碼本進行加密，我們需要一個同樣長度為55個字母的金鑰。假設我們使用的金鑰是「kcqyzhepxautiqekxejmoretzhztrwwqdylbttvejmedbsanybpxqik」。加密後的密鑰是「shomtdecqtilchzssixghyikdfnnmacewrzlghraqqvhzguerplbbqc」。

加密範例

Plaintext ifyouwanttosurviveouthereyouvegottoknowwhereyourtowelis Key kcqyzhepxautiqekxejmoretzhztrwwqdylbttvejmedbsanybpxqik Ciphertext shomtdecqtilchzssixghyikdfnnmacewrzlghraqqvhzguerplbbqc

現在，假設一名密碼分析者得到了密鑰「shomtdec…」。她如何攻擊這個密碼呢？暴力破解金鑰是不可行的，因為可能的金鑰數量太龐大了。對於一個55個字母的訊息，可能的金鑰數量是26^55，是一個天文數字。

為何一次性密碼本是牢不可破的

即使密碼分析者有足夠強大的計算能力來嘗試所有可能的金鑰，她仍然無法破解一次性密碼本。這是因為對於任意給定的密鑰，所有可能的明文訊息都是同等可能的。

例如，給定密鑰「shomtdec…」，我們可以輕易地宣稱原始明文是「themythofosiriswasofimportanceinancientegyptianreligion」，並使用金鑰「zakavkxolfqdlzhwsqjbzmtwmmnakwurwexdcuywksgorghnnedvtcp」進行加密。

Plaintext themythofosiriswasofimportanceinancientegyptianreligion Key zakavkxolfqdlzhwsqjbzmtwmmnakwurwexdcuywksgorghnnedvtcp Ciphertext shomtdecqtilchzssixghyikdfnnmacewrzlghraqqvhzguerplbbqc

我們能夠破解加密的通常原因是，因為通常只有一個金鑰能夠將密鑰解密成有意義的英文。但是，我們已經展示了相同的密鑰可以由兩個非常不同的明文訊息產生。對於一次性密碼本來說，密碼分析者無法判斷哪一個是原始訊息。事實上，任何一個長度為55個字母的可讀英文明文訊息都同樣有可能是原始明文。

謹防偽隨機數

Python中的random模組並不生成真正的隨機數。它們是透過演算法計算出來的，看起來像是隨機數（通常足夠好）。如果一次性密碼本的金鑰不是從真正的隨機源生成的，那麼它就失去了數學上完美的保密性。

使用`os.urandom()`生成真隨機數

os.urandom()函式可以提供真正的隨機數，但使用起來稍微複雜一些。更多關於此函式的資訊，請參閱http://invpy.com/random。

謹防兩次使用同一金鑰

如果您使用相同的一次性密碼本金鑰來加密兩條不同的訊息，那麼您就在加密中引入了弱點。以這種方式使用一次性密碼本密碼有時被稱為「兩次密碼本」。這是一個玩笑的名字，因為所謂的「兩次密碼本」其實只是錯誤地使用了一次性密碼本。

錯誤使用一次性密碼本的後果

僅僅因為某個金鑰能夠將一次性密碼本的密鑰解密成可讀的英文，並不意味著它是正確的金鑰。然而，如果您對兩條不同的訊息使用相同的金鑰，那麼駭客現在就可以利用這一點來破解您的加密。

內容解密：

此章節主要闡述了一次性密碼本（One-Time Pad）的原理及其不可破解性。一次性密碼本是一種特殊的維吉尼亞密碼，其特點是金鑰與訊息等長，且只使用一次。透過舉例說明瞭為何一次性密碼本是牢不可破的，以及在使用時需要注意的事項，如避免使用偽隨機數和避免重複使用同一金鑰。

一次性密碼本（One-Time Pad）的加密技術

一次性密碼本是一種理論上無法破解的加密技術，但其使用條件極為嚴格。一次性密碼本的關鍵在於使用與訊息長度相同、且只使用一次的金鑰進行加密。

為何一次性密碼本是無法破解的

根據夏農定理（Shannon’s Theorem），只要滿足兩個條件：金鑰長度等於訊息長度，且金鑰只使用一次，那麼一次性密碼本就是絕對安全的。這是因為攻擊者無法透過密鑰推斷出任何有關明文的資訊。

雙重使用一次性密碼本的風險

然而，如果將同一個一次性密碼本金鑰用於加密兩條不同的訊息，就會產生嚴重的問題。這種情況被稱為「兩次使用密碼本」（Two-Time Pad）。當攻擊者獲得兩條使用相同金鑰加密的密鑰時，他們可以透過將兩條密鑰進行 XOR 運算來還原出明文之間的差異，從而可能推斷出明文的內容。

def xor(a, b):
    return bytes([x ^ y for x, y in zip(a, b)])

# 假設有兩條使用相同金鑰加密的密鑰
ciphertext1 = b'PRFDQELRYW'
ciphertext2 = b'KMAYLZGMTR'

# 對兩條密鑰進行 XOR 運算
result = xor(ciphertext1, ciphertext2)
print(result)

內容解密：

上述程式碼展示瞭如何對兩條使用相同一次性密碼本金鑰加密的密鑰進行 XOR 運算。透過 xor 函式，我們將兩條密鑰 ciphertext1 和 ciphertext2 對應位元進行 XOR，得到結果 result。這裡的關鍵在於，XOR 運算具有還原明文之間差異的能力，因為相同的金鑰被用於加密兩條訊息，從而使得攻擊者可以利用這個特性來推斷明文內容。

與維吉尼亞密碼的關係

當一次性密碼本金鑰被重複使用時，其加密效果等同於維吉尼亞密碼（Vigenère Cipher）。維吉尼亞密碼是一種多字母替換加密技術，其安全性取決於金鑰的長度和隨機性。當金鑰長度等於訊息長度時，維吉尼亞密碼就變成了安全性極高的一次性密碼本。

一次性密碼本的實際應用挑戰

儘管一次性密碼本理論上是無法破解的，但其在實際應用中面臨著巨大的挑戰。首先，金鑰的分發和管理極為困難，因為金鑰需要與訊息一樣長，並且只能使用一次。其次，生成真正隨機的金鑰也是一項挑戰。因此，一次性密碼本通常只在極為重要的場閤中使用，例如高階別的外交或軍事通訊。

尋找質數（Prime Numbers）

在討論完一次性密碼本之後，我們接著探討另一個重要的密碼學基礎：質數。質數是指除了 1 和自身之外沒有其他正因數的整數，例如 2、3、5、7 等。質數在密碼學中扮演著至關重要的角色，特別是在 RSA 等公鑰加密演算法中。

質數的定義和重要性

質數是指大於 1 的整數，它除了 1 和自身以外沒有其他正因數。質數在數論中佔有重要地位，它們是構成所有整數的基本元素。在密碼學中，質數被廣泛用於構建安全的加密演算法。

使用埃拉託斯特尼篩法尋找質數

埃拉託斯特尼篩法（Sieve of Eratosthenes）是一種古老且高效的演算法，用於找出一定範圍內的所有質數。其基本思想是逐步標記出每個質數的倍數，最終剩下的未被標記的數字就是質數。

def sieve_of_eratosthenes(n):
    primes = [True] * (n + 1)
    primes[0] = primes[1] = False
    for i in range(2, int(n**0.5) + 1):
        if primes[i]:
            for j in range(i*i, n + 1, i):
                primes[j] = False
    return [i for i in range(2, n + 1) if primes[i]]

# 找出 100 以內的質數
print(sieve_of_eratosthenes(100))

內容解密：

上述程式碼實作了埃拉託斯特尼篩法，用於找出指定範圍內的所有質數。首先，我們初始化一個布林陣列 primes，其中 primes[i] 表示數字 i 是否為質數。然後，我們從 2 開始，逐步標記每個質數的倍數為非質數。最終，陣列中仍被標記為 True 的索引即為質數。該演算法的時間複雜度為 O(n log log n)，是一種非常高效的尋找質數的方法。

質數在密碼學中的應用

質數在密碼學中的應用非常廣泛，尤其是在公鑰加密演算法中。例如，RSA 演算法的安全性根據大整數分解的困難性，而大整數分解又與質數密切相關。透過使用大質數，RSA 可以實作很高的安全性。

總之，質數不僅是數論中的基本元素，也是現代密碼學的根本。瞭解和尋找質數對於構建安全的加密系統至關重要。

尋找質數的技術探討

在數論的研究中，質數（Prime Numbers）扮演著基礎且重要的角色。質數是指除了1和自身之外沒有其他正因數的整數。本文將探討質數的基本特性、判斷方法以及相關演算法的實作。

質數的基本特性

質數具有以下四個重要特性：

定義特性：質數是大於1的整數，且僅有1和自身作為因數。
偶數特性：2是唯一的偶質數，這使得2在質數中具有特殊地位。
無窮特性：質數的數量是無窮的，不存在最大的質數。
乘積特性：兩個質數的乘積所得到的數字，其因數對僅包含1、自身以及這兩個質數。

合成數的組成

非質數的整數被稱為合成數（Composite Numbers），因為它們可以分解為多個質數的乘積。例如，1386可以表示為$2 \times 3 \times 3 \times 7 \times 11$，其中每個乘數都是質數。

判斷質數的方法

簡單除法測試

判斷一個數字是否為質數的基本方法是透過除法測試。以下為isPrime函式的實作範例：

import math

def isPrime(num):
    # 小於2的數字不是質數
    if num < 2:
        return False
    
    # 測試從2到sqrt(num)的整數是否能整除num
    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:
            return False
    return True

內容解密：

初始檢查：首先檢查數字是否小於2，若是則直接傳回False，因為小於2的數字不是質數。
迴圈測試：使用迴圈測試從2到$\sqrt{num}$的所有整數是否能整除num。若找到任何一個能整除的數字，則傳回False。
最佳化原理：只需測試到$\sqrt{num}$的原因在於，若num有大於$\sqrt{num}$的因數，則必定有對應的小於$\sqrt{num}$的因數。

埃拉託斯特尼篩法（Sieve of Eratosthenes）

埃拉託斯特尼篩法是一種高效生成一定範圍內所有質數的演算法。以下是primeSieve函式的實作：

def primeSieve(sieveSize):
    # 初始化篩子，所有值設為True，表示初始時所有數字都被視為質數
    sieve = [True] * sieveSize
    sieve[0] = sieve[1] = False  # 0和1不是質數
    
    # 篩選過程
    for i in range(2, int(math.sqrt(sieveSize)) + 1):
        pointer = i * 2
        while pointer < sieveSize:
            sieve[pointer] = False
            pointer += i
    
    # 編譯質數列表
    primes = [i for i in range(sieveSize) if sieve[i]]
    return primes

內容解密：

初始化：建立一個布林陣列sieve，大小為sieveSize，初始時所有值設為True，代表所有數字初始都被視為質數。
篩選過程：從2開始，對每個質數i，將其倍數在sieve中的對應值設為False，因為這些倍數不是質數。
結果編譯：最後遍歷sieve，將值仍為True的索引收集起來，這些索引即為質數。

尋找質數：埃拉託斯特尼篩法與其應用

在數論中，尋找質數是一項基本且重要的任務。質數是指除了1和自身之外沒有其他正因數的正整數。埃拉託斯特尼篩法是一種古老且高效的演算法，用於找出一定範圍內的所有質數。

埃拉託斯特尼篩法的工作原理

埃拉託斯特尼篩法的工作原理如下：首先，建立一個布林陣列（或列表），其中每個索引代表一個數字，初始值均設為True，表示所有數字都是質數。然後，從2開始，對於每個質數，將其所有倍數標記為False，因為它們不是質數。這個過程持續到陣列中的所有數字都被處理過一次。

def primeSieve(sieveSize):
    # 使用埃拉託斯特尼篩法傳回質數列表
    sieve = [True] * sieveSize
    sieve[0] = False  # 0和1不是質數
    sieve[1] = False
    
    # 建立篩子
    for i in range(2, int(math.sqrt(sieveSize)) + 1):
        pointer = i * 2
        while pointer < sieveSize:
            sieve[pointer] = False
            pointer += i
    
    # 編譯質數列表
    primes = []
    for i in range(sieveSize):
        if sieve[i] == True:
            primes.append(i)
    
    return primes

程式碼解析：

初始化篩子：建立一個大小為sieveSize的布林列表，所有值初始化為True，代表所有數字初始狀態下都被視為質數。
標記非質數：從2開始，對於每個遇到的質數，將其所有倍數標記為False。這是透過一個巢狀的while迴圈實作的，該迴圈從i * 2開始，以i為步長遞增，直到超出sieveSize。
收集質數：最後，遍歷整個篩子，將值仍為True的索引（即質數）加入到結果列表中。

為何埃拉託斯特尼篩法優於簡單的除法測試

對於較小的數字，簡單的除法測試（如檢查一個數字是否能被2到其平方根之間的任何數字整除）是可行的。然而，當處理非常大的數字時，這種方法變得極其緩慢。埃拉託斯特尼篩法則能夠在相對較短的時間內找出一定範圍內的所有質數，使其在需要大量質數的應用中（如密碼學）非常有用。

Rabin-Miller 質數測試：處理超大質數

對於極大的數字，如那些用於RSA加密演算法的數字，埃拉託斯特尼篩法同樣變得不切實際。這時，Rabin-Miller 質數測試就派上用場了。這是一種機率性的演算法，能夠快速判斷一個大數字是否為質數。

Rabin-Miller 演算法：高效的素數測試方法

Rabin-Miller 演算法是一種廣泛用於密碼學中的機率性素數測試方法。相較於其他素數測試演算法，Rabin-Miller 演算法在效率和準確性之間取得了良好的平衡。

Rabin-Miller 演算法的工作原理

Rabin-Miller 演算法的核心思想根據費馬小定理的擴充套件。給定一個奇數 $n$，演算法首先將 $n-1$ 表示為 $2^t \cdot s$ 的形式，其中 $s$ 是奇數。然後，演算法進行多次測試，每次測試隨機選擇一個整數 $a$，並計算 $a^s \mod n$。如果 $a^s \equiv 1 \mod n$ 或存在某個 $0 \leq i < t$ 使得 $a^{2^i \cdot s} \equiv -1 \mod n$，則 $n$ 透過一次測試。若 $n$ 多次測試後仍然未被證明是合數，則可以認為 $n$ 是素數的機率很高。

程式碼實作

以下是 Rabin-Miller 演算法的 Python 實作範例：

import random

def rabinMiller(num):
    s = num - 1
    t = 0
    while s % 2 == 0:
        s = s // 2
        t += 1

    for trials in range(5): 
        a = random.randrange(2, num - 1)
        v = pow(a, s, num)
        if v != 1: 
            i = 0
            while v != (num - 1):
                if i == t - 1:
                    return False
                else:
                    i = i + 1
                    v = (v ** 2) % num
    return True

def isPrime(num):
    if (num < 2):
        return False 

    lowPrimes = [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, 101, 103, 107, 109, 
                 # ... 省略其他低位素數
                 ]

    if num in lowPrimes:
        return True

    for prime in lowPrimes:
        if (num % prime == 0):
            return False

    return rabinMiller(num)

def generateLargePrime(keysize=1024):
    while True:
        num = random.randrange(2**(keysize-1), 2**(keysize))
        if isPrime(num):
            return num

程式碼解析：

rabinMiller函式：
- 將輸入數字 num-1 表示為 2^t * s 的形式。
- 多次隨機測試以檢查 num 是否為素數。
isPrime函式：
- 首先檢查 num 是否為小於2的數字或是否在預先定義的低位素數列表中。
- 若不在列表中，則進一步使用 rabinMiller函式進行測試。
generateLargePrime函式：
- 生成指定位數的隨機大素數。

使用範例

你可以透過以下方式呼叫上述函式：

print(generateLargePrime(1024))
print(isPrime(45943208739848451))
print(isPrime(13))

輸出結果解析：

generateLargePrime(1024) 生成一個1024位元的大素數。
isPrime(45943208739848451) 傳回 False，表示該數字不是素數。
isPrime(13) 傳回 True，表示13是素數。

玄貓 BlackCat

技術愛好者，專注於分享程式開發、雲端技術與 AI 應用的心得體會。

一次性密碼本與質數探討

第22章 - 一次性密碼本（One-Time Pad）密碼法

為何一次性密碼本無法破解

加密範例

為何一次性密碼本是牢不可破的

謹防偽隨機數

使用os.urandom()生成真隨機數

謹防兩次使用同一金鑰

錯誤使用一次性密碼本的後果

內容解密：

一次性密碼本（One-Time Pad）的加密技術

為何一次性密碼本是無法破解的

雙重使用一次性密碼本的風險

內容解密：

與維吉尼亞密碼的關係

一次性密碼本的實際應用挑戰

尋找質數（Prime Numbers）

質數的定義和重要性

使用埃拉託斯特尼篩法尋找質數

內容解密：

質數在密碼學中的應用

尋找質數的技術探討

質數的基本特性

合成數的組成

判斷質數的方法

簡單除法測試

內容解密：

埃拉託斯特尼篩法（Sieve of Eratosthenes）

內容解密：

尋找質數：埃拉託斯特尼篩法與其應用

埃拉託斯特尼篩法的工作原理

程式碼解析：

為何埃拉託斯特尼篩法優於簡單的除法測試

Rabin-Miller 質數測試：處理超大質數

Rabin-Miller 演算法：高效的素數測試方法

Rabin-Miller 演算法的工作原理

程式碼實作

程式碼解析：

使用範例

輸出結果解析：

玄貓 BlackCat

使用`os.urandom()`生成真隨機數