破解換位與乘法密碼技術

密碼學是資訊安全的根本，理解密碼破解技術有助於提升系統安全性。本文首先介紹暴力破解換位密碼的方法，透過遍歷金鑰空間，並結合英文檢測函式，找到可讀的明文。接著，文章探討模組化算術，闡述其在乘法密碼中的應用，包含模運算元、最大公約數、歐幾裡得演算法以及多重指定技巧等概念，並提供 Python 程式碼範例與詳細解析，說明如何計算模反元素和最大公約數。最後，文章以 Cuisenaire Rods 作為視覺化工具，輔助理解因數和最大公約數的概念，強化讀者對模組化算術的理解。

破解換位密碼

本章涵蓋的主題：

• 使用三重引號的多行字串
• strip() 字串方法

破解換位密碼的方法

要破解換位密碼，我們將使用暴力破解的方法。在數千個金鑰中，正確的金鑰很可能是唯一一個能夠產生可讀英文的金鑰。我們在上一章中開發了英文檢測程式碼，以便程式可以在找到正確金鑰時識別出來。

換位密碼破解程式的原始碼

開啟一個新的檔案編輯器視窗，點選「檔案」>「新建視窗」。將以下程式碼輸入檔案編輯器，然後將其儲存為 transpositionHacker.py。按下 F5 執行程式。請注意，首先您需要下載 pyperclip.py 模組並將該檔案放在與 transpositionHacker.py 檔案相同的目錄中。您可以從 http://invpy.com/pyperclip.py 下載該檔案。

transpositionHacker.py 原始碼

# 換位密碼破解器
# http://inventwithpython.com/hacking (BSD 授權)

import pyperclip, detectEnglish, transpositionDecrypt

程式碼解析：

• 程式首先匯入必要的模組，包括 pyperclip、detectEnglish 和 transpositionDecrypt。
• pyperclip 模組用於存取剪貼簿內容。
• detectEnglish 模組包含用於檢測字串是否為英文的函式。
• transpositionDecrypt 模組包含用於解密換位密碼的函式。

建構換位密碼破解器

我們的目標是編寫一個程式，可以自動破解換位密碼。為此，我們將使用暴力破解的方法，嘗試所有可能的金鑰，直到找到一個產生可讀英文的金鑰。

實作細節：

1. 遍歷所有可能的金鑰：由於金鑰的範圍很大，我們需要編寫一個迴圈來遍歷所有可能的金鑰。
2. 解密訊息：對於每個金鑰，我們將使用 transpositionDecrypt 模組中的函式來解密訊息。
3. 檢查是否為英文：解密後，我們將使用 detectEnglish 模組中的函式來檢查解密後的訊息是否為英文。
4. 輸出結果：如果找到一個可讀的英文訊息，我們將輸出該訊息和對應的金鑰。

程式碼範例與解析

def hackTranspositionCipher(message):
    for key in range(1, len(message)):
        decryptedText = transpositionDecrypt.decryptMessage(key, message)
        if detectEnglish.isEnglish(decryptedText):
            print(f"可能的金鑰：{key}")
            print(decryptedText)
            # 可以在此新增確認是否為正確解密的邏輯

# 使用範例
message = "取得的加密訊息"
hackTranspositionCipher(message)

程式碼解析：

• hackTranspositionCipher 函式遍歷所有可能的金鑰，對每個金鑰使用 transpositionDecrypt.decryptMessage 函式解密訊息。
• 使用 detectEnglish.isEnglish 函式檢查解密後的訊息是否為英文。
• 如果解密後的訊息是英文，則輸出該訊息和對應的金鑰。

暴力破解移位密碼法

在密碼學的世界中，移位密碼法（Transposition Cipher）是一種常見的加密技術，它透過重新排列明文中的字母順序來達到加密的目的。然而，這種加密方法並非完全安全，可以透過暴力破解的方式來還原始資訊。

程式實作

以下是一個使用Python撰寫的移位密碼破解程式：

import pyperclip
import detectEnglish
import transpositionDecrypt

def main():
    myMessage = """Cb b rssti aieih rooaopbrtnsceee er es no npfgcwu plri
ch nitaalr eiuengiteehb(e1 hilincegeoamn fubehgtarndcstudmd nM eu eacBoltaetee
oinebcdkyremdteghn.aa2r81a condari fmps" tad l t oisn sit u1rnd stara nvhn fs
edbh ee,n e necrg6 8nmisv l nc muiftegiitm tutmg cm shSs9fcie ebintcaets h a
ihda cctrhe ele 1O7 aaoem waoaatdahretnhechaopnooeapece9etfncdbgsoeb uuteitgna.
rteoh add e,D7c1Etnpneehtn beete" evecoal lsfmcrl iu1cifgo ai. sl1rchdnheev sh
meBd ies e9t)nh,htcnoecplrrh ,ide hmtlme. pheaLem,toeinfgn t e9yce da' eN eMp a
ffn Fc1o ge eohg dere.eec s nfap yox hla yon. lnrnsreaBoa t,e eitsw il ulpbdofg
BRe bwlmprraio po droB wtinue r Pieno nc ayieeto'lulcih sfnc ownaSserbereiaSm
-eaiah, nnrttgcC maciiritvledastinideI nn rms iehn tsigaBmuoetcetias rn"""

    hackedMessage = hackTransposition(myMessage)

    if hackedMessage is None:
        print('無法破解加密。')
    else:
        print('已將破解的訊息複製到剪貼簿：')
        print(hackedMessage)
        pyperclip.copy(hackedMessage)

def hackTransposition(message):
    print('正在破解...')
    print('(隨時可按下 Ctrl-C 或 Ctrl-D 離開。)')

    for key in range(1, len(message)):
        print('正在嘗試金鑰 #%s...' % (key))

        decryptedText = transpositionDecrypt.decryptMessage(key, message)

        if detectEnglish.isEnglish(decryptedText):
            print()
            print('可能的加密破解：')
            print('金鑰 %s: %s' % (key, decryptedText[:100]))
            print()
            print('輸入 D 表示完成，或直接按下 Enter 續繼破解：')
            response = input('> ')

            if response.strip().upper().startswith('D'):
                return decryptedText

    return None

if __name__ == '__main__':
    main()

內容解密：

1. main() 函式：程式的進入點，包含了一個預設的加密訊息，並呼叫 hackTransposition() 函式進行破解。
2. hackTransposition(message) 函式：負責暴力破解的核心邏輯。它會遍歷所有可能的金鑰（從1到訊息長度），並嘗試使用每個金鑰解密。
3. 解密與驗證：對於每個金鑰，程式呼叫 transpositionDecrypt.decryptMessage() 解密訊息，並使用 detectEnglish.isEnglish() 檢查解密後的文字是否為英文。如果是，則輸出可能的解密結果，並詢問使用者是否滿意該結果。
4. 使用者互動：若使用者對解密結果滿意，可輸入 ‘D’ 結束程式並傳回解密結果；否則，按下 Enter 繼續嘗試下一個金鑰。
5. pyperclip.copy(hackedMessage)：將最終的解密結果複製到剪貼簿，方便使用者進一步操作。

程式執行流程

當執行該程式時，它會逐一嘗試不同的金鑰來解密訊息，直到找到一個看似合理的英文文字為止。若找到合理的解密結果，程式會暫停並等待使用者確認；若使用者不滿意該結果，可繼續嘗試其他金鑰。最終，若無法找到正確的解密結果，程式會告知使用者無法破解該加密訊息。

技術深度探討

此程式展示了暴力破解移位密碼法的基本原理和實作方法。移位密碼法雖然簡單易用，但其安全性較低，容易被破解。該程式透過遍歷所有可能的金鑰，成功地還原了原始的加密訊息。這種方法對於理解密碼學的基本概念和實踐操作具有重要意義。

破解移位密碼技術解析

在密碼學領域中，移位密碼（Transposition Cipher）是一種常見的加密技術，其特點是透過重新排列明文的字母順序來達到加密的目的。要破解這種加密技術，需要採用特定的方法與技術。

程式實作：移位密碼破解

以下是一個 Python 程式範例，用於破解移位密碼：

def hackTransposition(message):
    print('開始破解...')
    print('(隨時可按下 Ctrl-C 或 Ctrl-D 離開程式)')

    for key in range(1, len(message)):
        print('嘗試金鑰 #%s...' % (key))
        decryptedText = transpositionDecrypt.decryptMessage(key, message)
        
        if detectEnglish.isEnglish(decryptedText):
            print()
            print('可能的解密結果：')
            print('金鑰 %s: %s' % (key, decryptedText[:100]))
            print()
            print('輸入 D 表示完成，或直接按下 Enter 續繼破解：')
            response = input('> ').strip().upper()
            
            if response == 'D':
                return decryptedText

    return None

程式碼解析：

1. hackTransposition 函式：此函式負責執行移位密碼的破解工作，接受一個引數 message，即待破解的密鑰。
2. 迴圈嘗試不同金鑰：透過 for 迴圈，程式會逐一嘗試從 1 到 message 長度之間的每個金鑰。
3. 解密處理：使用 transpositionDecrypt.decryptMessage 函式對密鑰進行解密，得到 decryptedText。
4. 判斷解密結果：利用 detectEnglish.isEnglish 函式檢查解密後的文字是否為英文。如果是，則輸出可能的解密結果，並提示使用者輸入指令。
5. 使用者互動：程式會等待使用者輸入，如果輸入 D，則傳回解密結果；否則，繼續嘗試下一個金鑰。

多行字串的使用

在上述程式中，我們使用了多行字串來儲存密鑰。這種字串以三個引號（""" 或 '''）開始和結束，可以包含多行文字，非常適合用於儲存大段的文字內容。

myMessage = """This is a very long ciphertext that needs to be hacked."""

多行字串的優點：

• 可以直接在程式碼中包含多行文字，無需使用 \n 進行換行。
• 方便閱讀和編輯大段文字。

程式執行流程

1. 程式首先輸出提示資訊，告知使用者已開始破解，並可隨時離開。
2. 進入迴圈，逐一嘗試不同的金鑰進行解密。
3. 對每一次解密結果進行判斷，若結果為英文，則輸出並請求使用者確認。
4. 根據使用者的輸入決定是否傳回解密結果或繼續嘗試下一個金鑰。

模組算術與乘法密碼

本章節將介紹模組算術的概念以及其在密碼學中的應用，特別是在乘法密碼和仿射密碼中的使用。

模組算術（又稱鐘表算術）

模組算術是一種特殊的算術系統，它類別似於鐘表的運作方式。在鐘表上，時間是以12或24小時為迴圈的，當時間超過這個迴圈時，就會重新開始。

例子

• 如果現在是3點鐘，那麼5小時後將是8點鐘。這是因為3 + 5 = 8。
• 如果現在是10點鐘，那麼5小時後將是3點鐘。這是因為10 + 5 = 15，而15超過了12，所以我們需要減去12，得到15 - 12 = 3。
• 如果現在是10點鐘，那麼200小時後將是6點鐘。這是因為10 + 200 = 210，210超過了12，所以我們不斷減去12，直到得到一個小於12的數字，最終結果是6。

最大公約數（GCD）

在模組算術中，最大公約數（GCD）是一個重要的概念。GCD是指兩個數字的最大共同因數。

歐幾裡得演算法

歐幾裡得演算法是一種用於計算兩個數字的GCD的演算法。它的工作原理是反覆應用除法演算法，直到餘數為0。

乘法密碼

乘法密碼是一種使用模組算術的密碼。它透過將明文的每個字元與一個金鑰相乘來加密資料。

程式碼範例

def multiplicative_cipher(plaintext, key):
    ciphertext = ""
    for char in plaintext:
        if char.isalpha():
            # 將字元轉換為對應的數字（A=0, B=1, ..., Z=25）
            num = ord(char.upper()) - ord('A')
            # 使用金鑰進行加密
            encrypted_num = (num * key) % 26
            # 將加密後的數字轉換回字符
            encrypted_char = chr(encrypted_num + ord('A'))
            ciphertext += encrypted_char
        else:
            ciphertext += char
    return ciphertext

# 使用金鑰5加密明文"HELLO"
print(multiplicative_cipher("HELLO", 5))

內容解密：

1. multiplicative_cipher函式接受明文和金鑰作為輸入，並傳回加密後的密鑰。
2. 對於明文中的每個字元，如果它是字母，則將其轉換為對應的數字（A=0, B=1, …, Z=25）。
3. 使用金鑰對數字進行加密，加密公式為(num * key) % 26，其中num是字元對應的數字，key是金鑰。
4. 將加密後的數字轉換回字符，並新增到密鑰中。
5. 如果字元不是字母，則直接新增到密鑰中，不進行加密。

相對質數

在模組算術中，如果兩個數字的GCD為1，則稱它們為相對質數。這在密碼學中非常重要，因為它確保了加密函式的可逆性。

模逆元

模逆元是指對於一個數字a，存在另一個數字b，使得(a * b) % n = 1。在模組算術中，模逆元的存在性取決於a和n是否相對質數。

程式碼範例

def mod_inverse(a, n):
    for x in range(1, n):
        if (a * x) % n == 1:
            return x
    return None

# 計算5在模26下的模逆元
print(mod_inverse(5, 26))

內容解密：

1. mod_inverse函式接受一個數字a和一個模數n作為輸入，並傳回a在模n下的模逆元。
2. 函式遍歷從1到n-1的所有數字，檢查是否存在一個數字x，使得(a * x) % n == 1。
3. 如果找到這樣的x，則傳回它作為模逆元。
4. 如果沒有找到，則傳回None，表示模逆元不存在。

模組化算術與乘法密碼

在密碼學的世界中，模組化算術（Modular Arithmetic）扮演著重要的角色。它是一種特殊的算術運算系統，能夠在特定的數值範圍內進行加、減、乘、除等運算。本章將探討模組化算術的基本概念及其在乘法密碼中的應用。

模運算元（The % Mod Operator）

模運算元是一種特殊的運算子號，用於計算兩個數相除後的餘數。在 Python 程式語言中，模運算元以 % 表示。舉例來說，15 % 12 的結果為 3，因為 15 除以 12 的餘數是 3。

>>> 15 % 12
3
>>> 210 % 12
6
>>> 10 % 10
0
>>> 20 % 10
0

內容解密：

1. 15 % 12：計算 15 除以 12 的餘數，結果為 3。
2. 210 % 12：計算 210 除以 12 的餘數，結果為 6。
3. 10 % 10：計算 10 除以 10 的餘數，結果為 0。
4. 20 % 10：計算 20 除以 10 的餘數，結果為 0。

最大公約數（GCD: Greatest Common Divisor）

最大公約數是指兩個或多個整數共有的最大正因數。例如，24 和 30 的最大公約數是 6，因為 6 是能整除 24 和 30 的最大正整數。

如何計算 GCD

要計算兩個數的最大公約數，我們可以使用 歐幾裡得演算法（Euclid’s Algorithm）。這個演算法根據一個簡單的事實：兩個數的最大公約數等於其中一個數與另一個數除以第一個數的餘數之間的最大公約數。

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

內容解密：

1. while b != 0：當 b 不等於 0 時，繼續執行迴圈。
2. a, b = b, a % b：使用多重指定技巧，將 a 和 b 的值進行交換，並將 b 更新為 a 除以 b 的餘數。
3. return a：當 b 等於 0 時，傳回 a 的值，即為兩個數的最大公約數。

多重指定技巧（Multiple Assignment）

Python 提供了一個非常有用的功能，稱為多重指定（Multiple Assignment），允許我們在一行程式碼中指定多個變數。這在交換兩個變數的值時尤其方便。

>>> spam, eggs = 'hello', 'goodbye'
>>> spam, eggs = eggs, spam
>>> spam
'goodbye'
>>> eggs
'hello'

內容解密：

1. spam, eggs = 'hello', 'goodbye'：同時指定 spam 為 'hello' 和 eggs 為 'goodbye'。
2. spam, eggs = eggs, spam：交換 spam 和 eggs 的值。

Cuisenaire Rods 與因數視覺化

Cuisenaire Rods 是一種用於視覺化數學運算的工具，可以幫助我們理解因數和最大公約數的概念。透過使用不同長度的方塊，我們可以輕鬆地看出哪些數字是另一個數字的因數，以及如何找到兩個數字之間的最大公約數。