仿射密碼技術深度解析與Python實作

仿射密碼是一種根據模數運算和金鑰組的加密技術，結合了乘法和加法運算。其安全性建立在金鑰的選擇與符號集大小的設定。理解其核心概念、實作細節以及潛在風險，對於評估和應用仿射密碼至關重要。本文將詳細解析仿射密碼的各個環節，並提供 Python 程式碼範例。此程式碼包含加密、解密、金鑰處理、以及必要的安全檢查，以確保加密的完整性和可靠性。透過分析程式碼，讀者能更深入地理解仿射密碼的運作機制，並學習如何在實際應用中使用它。

歐幾裡得GCD演算法與乘法密碼

歐幾裡得GCD演算法是一種用於計算兩個整數的最大公約數（GCD）的有效方法。以下是一個實作歐幾裡得GCD演算法的Python函式：

def gcd(a, b):
    while a != 0:
        a, b = b % a, a
    return b

內容解密：

while a != 0：持續迴圈直到 a 等於 0。
a, b = b % a, a：更新 a 和 b 的值，a 變為 b % a，b 變為原來的 a。這是歐幾裡得演算法的核心步驟，用於逐步簡化問題。
return b：當 a 為 0 時，b 即為最大公約數。

互質數

在乘法密碼和仿射密碼中，我們需要使用互質數。如果兩個數字的最大公約數是1，則稱它們互質。換句話說，如果 gcd(a, b) == 1，則 a 和 b 互質。

乘法密碼

乘法密碼是一種使用乘法運算進行加密的密碼。對於一個給定的金鑰 k 和明文字母 m（對應的數字），加密後的密鑰 c 可以透過以下公式計算：

c = (m * k) % 26

其中，26是字母表的大小。

程式碼範例：

def multiplicative_cipher_encrypt(plaintext, key):
    ciphertext = ""
    for char in plaintext:
        if char.isalpha():
            num = ord(char.upper()) - ord('A')
            encrypted_num = (num * key) % 26
            ciphertext += chr(encrypted_num + ord('A'))
        else:
            ciphertext += char
    return ciphertext

# 使用金鑰7加密訊息 "HELLO"
print(multiplicative_cipher_encrypt("HELLO", 7))

內容解密：

for char in plaintext：遍歷明文中的每個字元。
if char.isalpha()：檢查字元是否為字母。
num = ord(char.upper()) - ord('A')：將字母轉換為對應的數字（A=0, B=1, …）。
encrypted_num = (num * key) % 26：進行乘法加密並取模26。
ciphertext += chr(encrypted_num + ord('A'))：將加密後的數字轉換回字母。

仿射密碼

仿射密碼結合了乘法密碼和凱撒密碼，使用兩個金鑰：Key A 用於乘法，Key B 用於加法。加密公式如下：

c = ((m * Key A) % 26 + Key B) % 26

程式碼範例：

def affine_cipher_encrypt(plaintext, key_a, key_b):
    ciphertext = ""
    for char in plaintext:
        if char.isalpha():
            num = ord(char.upper()) - ord('A')
            encrypted_num = ((num * key_a) % 26 + key_b) % 26
            ciphertext += chr(encrypted_num + ord('A'))
        else:
            ciphertext += char
    return ciphertext

# 使用 Key A = 5 和 Key B = 8 加密訊息 "HELLO"
print(affine_cipher_encrypt("HELLO", 5, 8))

內容解密：

結合乘法和加法運算進行加密。
使用兩個金鑰增加密碼的安全性。

金鑰選擇問題

在使用乘法密碼或仿射密碼時，必須小心選擇金鑰。例如，如果 Key A 不是與26互質的數字，則可能會導致多個明文字母對映到同一個密鑰字母，從而使得解密變得困難甚至不可能。

乘法密碼與仿射密碼流程圖

@startuml
skinparam backgroundColor #FEFEFE
skinparam componentStyle rectangle

title 仿射密碼技術深度解析與Python實作

package "安全架構" {
    package "網路安全" {
        component [防火牆] as firewall
        component [WAF] as waf
        component [DDoS 防護] as ddos
    }

    package "身份認證" {
        component [OAuth 2.0] as oauth
        component [JWT Token] as jwt
        component [MFA] as mfa
    }

    package "資料安全" {
        component [加密傳輸 TLS] as tls
        component [資料加密] as encrypt
        component [金鑰管理] as kms
    }

    package "監控審計" {
        component [日誌收集] as log
        component [威脅偵測] as threat
        component [合規審計] as audit
    }
}

firewall --> waf : 過濾流量
waf --> oauth : 驗證身份
oauth --> jwt : 簽發憑證
jwt --> tls : 加密傳輸
tls --> encrypt : 資料保護
log --> threat : 異常分析
threat --> audit : 報告生成

@enduml

此圖示說明瞭仿射密碼的加密過程，包括數字轉換、乘法、取模、加法和最終的字母轉換。

仿射密碼（Affine Cipher）的金鑰選擇與解密機制

在密碼學中，仿射密碼是一種根據數學運算的加密技術，涉及金鑰選擇、加密及解密過程。本文將探討仿射密碼的金鑰選擇條件、解密原理及其實作方法。

仿射密碼的金鑰選擇條件

仿射密碼的加密金鑰由兩個數字組成：$Key A$ 和 $Key B$。其中，$Key A$ 必須與符號集的大小（本例中為 26）互質，即它們的最大公約數（GCD）為 1。這一條件至關重要，因為它確保了加密函式的可逆性，從而能夠正確解密。

def gcd(a, b):
    while a != 0:
        a, b = b % a, a
    return b

內容解密：

此函式用於計算兩個數字的最大公約數（GCD）。透過使用歐幾裡得演算法，它反覆更新 $a$ 和 $b$ 的值，直到 $a$ 為 0，此時 $b$ 即為兩者的 GCD。該函式對於檢查 $Key A$ 是否與符號集大小互質至關重要。

仿射密碼的解密機制

仿射密碼使用乘法進行加密，因此解密需要使用加密金鑰的模逆元。模逆元 $i$ 的定義是對於給定的 $a$ 和 $m$，滿足 $(a * i) % m == 1$。

def findModInverse(a, m):
    if gcd(a, m) != 1:
        return None  # 如果 a 和 m 不互質，則不存在模逆元
    u1, u2, u3 = 1, 0, a
    v1, v2, v3 = 0, 1, m
    while v3 != 0:
        q = u3 // v3
        v1, v2, v3, u1, u2, u3 = (u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3
    return u1 % m

內容解密：

此函式使用擴充套件歐幾裡得演算法來計算 $a$ 模 $m$ 的模逆元。首先檢查 $a$ 和 $m$ 是否互質，如果不是，則傳回 None。接著，透過迭代更新變數，最終傳回模逆元。該函式對於計算仿射密碼的解密金鑰至關重要。

整數除法運算子 `//`

在 findModInverse 函式中，使用了整數除法運算子 //。該運算子執行除法並向下取整，結果始終為整數。

>>> 41 // 7
5
>>> 41 / 7
5.857142857142857

內容解密：

此段程式碼展示了整數除法運算子 // 與普通除法運算子 / 的區別。使用 // 可確保結果為整數，這在需要進行整數運算的密碼學計算中非常重要。

cryptomath 模組的實作

為了方便在多個密碼程式中重用，gcd 和 findModInverse 函式被封裝在一個名為 cryptomath.py 的模組中。

# cryptomath.py

def gcd(a, b):
    # 傳回 a 和 b 的 GCD
    while a != 0:
        a, b = b % a, a
    return b

def findModInverse(a, m):
    # 傳回 a 模 m 的模逆元
    if gcd(a, m) != 1:
        return None
    u1, u2, u3 = 1, 0, a
    v1, v2, v3 = 0, 1, m
    while v3 != 0:
        q = u3 // v3
        v1, v2, v3, u1, u2, u3 = (u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3
    return u1 % m

內容解密：

此模組包含了計算 GCD 和模逆元的函式。透過將這些通用功能封裝在單獨的模組中，可以在不同的密碼學程式中方便地呼叫，提高程式碼的可重用性和可維護性。

##仿射密碼實作與解析仿射密碼是一種結合乘法與加法運算的加密技術，根據模數運算實作。本章將探討仿射密碼的原理、實作方法及其安全性分析。

仿射密碼的核心概念

仿射密碼結合了乘法密碼與凱撒密碼的特性，需要兩個金鑰：$Key A$用於乘法運算，$Key B$用於加法運算。加密過程可表示為：

$$C = (P \times Key A + Key B) \mod M$$

其中$C$為密鑰，$P$為明文，$M$為符號集大小。

程式碼解析

以下為仿射密碼實作的主要程式碼片段：

def encryptMessage(key, message):
    keyA, keyB = getKeyParts(key)
    checkKeys(keyA, keyB, 'encrypt')
    ciphertext = ''
    for symbol in message:
        if symbol in SYMBOLS:
            symIndex = SYMBOLS.find(symbol)
            ciphertext += SYMBOLS[(symIndex * keyA + keyB) % len(SYMBOLS)]
        else:
            ciphertext += symbol
    return ciphertext

內容解密：

金鑰分解：函式getKeyParts(key)將單一金鑰分解為$Key A$和$Key B$。
- $Key A = key // len(SYMBOLS)$
- $Key B = key \mod len(SYMBOLS)$
安全性檢查：checkKeys(keyA, keyB, 'encrypt')確保金鑰的有效性。
- 檢查$Key A$是否為1（弱加密）
- 檢查$Key B$是否為0（弱加密）
- 驗證$Key A$與符號集大小是否互質
加密邏輯：
- 對每個符號在SYMBOLS中的索引進行仿射變換
- 使用模數運算確保結果在符號集範圍內

解密實作

解密過程需要計算$Key A$的模逆元，使用cryptomath.findModInverse函式實作：

def decryptMessage(key, message):
    keyA, keyB = getKeyParts(key)
    checkKeys(keyA, keyB, 'decrypt')
    plaintext = ''
    modInverseOfKeyA = cryptomath.findModInverse(keyA, len(SYMBOLS))
    
    for symbol in message:
        if symbol in SYMBOLS:
            symIndex = SYMBOLS.find(symbol)
            plaintext += SYMBOLS[(symIndex - keyB) * modInverseOfKeyA % len(SYMBOLS)]
        else:
            plaintext += symbol
    return plaintext

內容解密：

模逆元計算：使用cryptomath.findModInverse(keyA, len(SYMBOLS))計算$Key A$的模逆元。
解密邏輯：
- 對密鑰進行逆運算：$(C - Key B) \times Key A^{-1} \mod M$
- 確保結果正確映射回明文符號

安全性分析

金鑰空間限制：$Key A$必須與符號集大小互質，限制了有效金鑰數量。
弱金鑰問題：當$Key A = 1$或$Key B = 0$時，加密變得非常弱。
暴力破解風險：相較於其他加密演算法，仿射密碼的金鑰空間較小，容易遭受暴力破解攻擊。

最佳實踐建議

使用足夠大的符號集，增加金鑰空間。
定期更換金鑰，降低被破解的風險。
結合其他加密技術，增強整體安全性。

仿射密碼程式詳解

仿射密碼是一種結合了乘法和加法的加密技術，透過兩個整數金鑰（Key A 和 Key B）來實作加密和解密。本篇文章將探討仿射密碼的實作細節及其在程式中的應用。

程式結構與主要功能

程式 affineCipher.py 主要包含以下幾個部分：

模組匯入
- 程式一開始匯入了必要的模組，包括 sys、pyperclip、cryptomath 和 random。這些模組分別用於提供離開程式的功能、操作剪貼簿、數學運算以及隨機數生成。
符號集定義
- SYMBOLS 變數定義了可以被加密的字元集，包括空格、標點符號、數字和字母等。
主函式
- main() 函式是程式的入口，負責設定要加密或解密的訊息、金鑰以及操作模式（加密或解密）。

程式碼解析

def main():
    myMessage = """"A computer would deserve to be called intelligent if it could deceive a human into believing that it was human." -Alan Turing"""
    myKey = 2023
    myMode = 'encrypt'  # 設定為 'encrypt' 或 'decrypt'
    if myMode == 'encrypt':
        translated = encryptMessage(myKey, myMessage)
    elif myMode == 'decrypt':
        translated = decryptMessage(myKey, myMessage)
    print('Key: %s' % (myKey))
    print('%sed text:' % (myMode.title()))
    print(translated)
    pyperclip.copy(translated)
    print('Full %sed text copied to clipboard.' % (myMode))

內容解密：

此段程式碼首先定義了要加密的訊息 myMessage、金鑰 myKey 和操作模式 myMode。接著根據 myMode 的值呼叫 encryptMessage() 或 decryptMessage() 函式進行加密或解密，並將結果輸出到螢幕和剪貼簿中。

金鑰處理

仿射密碼使用兩個金鑰（Key A 和 Key B）進行加密和解密，但為了方便記憶，通常只儲存一個金鑰。程式中使用 getKeyParts() 函式將單一金鑰分解為兩個金鑰。

程式碼解析

def getKeyParts(key):
    keyA = key // len(SYMBOLS)
    keyB = key % len(SYMBOLS)
    return (keyA, keyB)

內容解密：

此函式將金鑰 key 分解為 keyA 和 keyB。keyA 是 key 除以符號集大小的商，而 keyB 是餘數。這種方法允許從單一金鑰中還原出兩個金鑰。

元組資料型別

在 Python 中，元組是一種不可變的序列型別，用於儲存多個值。getKeyParts() 函式傳回一個包含 keyA 和 keyB 的元組。

程式碼解析

return (keyA, keyB)

內容解密：

元組使用圓括號來定義，其內容不可修改。使用元組可以提高程式的執行效率，因為 Python 直譯器對元組的操作比對串列的操作更快。

##仿射密碼（Affine Cipher）技術深度解析

金鑰驗證機制

在實作仿射密碼加密與解密過程中，金鑰驗證是確保加密安全性的關鍵步驟。程式碼中checkKeys函式負責檢查金鑰的有效性，具體實作如下：

def checkKeys(keyA, keyB, mode):
    if keyA == 1 and mode == 'encrypt':
        sys.exit('當金鑰A設為1時，仿射密碼變得極度弱。請選擇不同的金鑰。')
    if keyB == 0 and mode == 'encrypt':
        sys.exit('當金鑰B設為0時，仿射密碼變得極度弱。請選擇不同的金鑰。')
    if keyA < 0 or keyB < 0 or keyB > len(SYMBOLS) - 1:
        sys.exit('金鑰A必須大於0，金鑰B必須在0和%s之間。' % (len(SYMBOLS) - 1))
    if cryptomath.gcd(keyA, len(SYMBOLS)) != 1:
        sys.exit('金鑰A (%s) 和符號集大小 (%s) 不是互質數。請選擇不同的金鑰。' % (keyA, len(SYMBOLS)))

內容解密：

弱金鑰檢查：當keyA為1或keyB為0時，加密過程會變得脆弱，因為這兩種情況下加密運算無法有效改變原始訊息的索引值。
金鑰範圍檢查：keyA必須為正數，keyB必須在符號集大小範圍內，確保加密運算的有效性。
互品檢查：keyA與符號集大小必須互質，這是仿射密碼能夠正確解密的必要條件。

加密函式實作

加密函式encryptMessage負責將明文訊息轉換為密鑰，其核心邏輯如下：

def encryptMessage(key, message):
    keyA, keyB = getKeyParts(key)
    checkKeys(keyA, keyB, 'encrypt')
    ciphertext = ''
    for symbol in message:
        if symbol in SYMBOLS:
            symIndex = SYMBOLS.find(symbol)
            ciphertext += SYMBOLS[(symIndex * keyA + keyB) % len(SYMBOLS)]
        else:
            ciphertext += symbol
    return ciphertext

內容解密：

金鑰分解：透過getKeyParts函式將組合金鑰分解為keyA和keyB。
加密運算：對符號集中的每個字元進行加密，計算公式為(symIndex * keyA + keyB) % len(SYMBOLS)，確保結果在符號集範圍內。
非符號字元處理：對於不在符號集中的字元，直接附加到密鑰後面，保持原樣。

解密函式實作

解密函式decryptMessage負責將密鑰還原為明文，其核心邏輯如下：

def decryptMessage(key, message):
    keyA, keyB = getKeyParts(key)
    checkKeys(keyA, keyB, 'decrypt')
    plaintext = ''
    modInverseOfKeyA = cryptomath.findModInverse(keyA, len(SYMBOLS))
    for symbol in message:
        if symbol in SYMBOLS:
            symIndex = SYMBOLS.find(symbol)
            plaintext += SYMBOLS[(symIndex - keyB) * modInverseOfKeyA % len(SYMBOLS)]
        else:
            plaintext += symbol
    return plaintext

內容解密：

模逆運算：透過cryptomath.findModInverse計算keyA的模逆，用於解密過程中的乘法運算。
解密公式：使用公式(symIndex - keyB) * modInverseOfKeyA % len(SYMBOLS)還原始索引值，實作解密。

技術深度分析

仿射密碼的安全性取決於金鑰選擇的合理性以及符號集的大小。正確選擇互質的keyA和適當範圍的keyB是確保加密安全的關鍵。此外，程式碼中對弱金鑰的檢查和處理機制進一步增強了加密的可靠性。

玄貓 BlackCat

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

仿射密碼技術深度解析與Python實作

歐幾裡得GCD演算法與乘法密碼

內容解密：

互質數

乘法密碼

程式碼範例：

內容解密：

仿射密碼

程式碼範例：

內容解密：

金鑰選擇問題

乘法密碼與仿射密碼流程圖

仿射密碼（Affine Cipher）的金鑰選擇與解密機制

仿射密碼的金鑰選擇條件

內容解密：

仿射密碼的解密機制

內容解密：

整數除法運算子 //

內容解密：

cryptomath 模組的實作

內容解密：

仿射密碼的核心概念

程式碼解析

內容解密：

解密實作

內容解密：

安全性分析

最佳實踐建議

仿射密碼程式詳解

程式結構與主要功能

程式碼解析

內容解密：

金鑰處理

程式碼解析

內容解密：

元組資料型別

程式碼解析

內容解密：

金鑰驗證機制

內容解密：

加密函式實作

內容解密：

解密函式實作

內容解密：

技術深度分析

玄貓 BlackCat

整數除法運算子 `//`