簡單替換密碼的破解利用字詞頻率分析和模式匹配,程式碼中以 hackSimpleSubstitution 函式實作核心破解流程,包含初始化字母對映、遍歷密鑰單詞、更新和交叉驗證對映等步驟。解密金鑰則由 decryptWithCipherletterMapping 函式產生,將字母對映轉換為金鑰,並處理無法確定的字母。維吉尼亞密碼則是一種多字母替換加密技術,使用多個子金鑰進行加密,其安全性取決於金鑰長度。程式碼中以 vigenere_cipher 函式示範加密過程,並說明如何將金鑰轉換為子金鑰列表以及如何處理非字母字元。文章也探討了維吉尼亞密碼的金鑰長度、金鑰選擇的重要性,並提供 Python 程式碼範例,詳細說明瞭加密和解密的核心邏輯,以及大小寫和非字母字元的處理方式。

簡單替換密碼破解技術深度解析

密碼破解核心邏輯

簡單替換密碼(Simple Substitution Cipher)的破解依賴於字詞模式匹配和字母對映的交叉驗證。程式碼實作中,hackSimpleSubstitution 函式負責核心破解邏輯,其運作流程如下:

  1. 初始化空白對映:首先建立一個空白的字母對映,用於儲存密鑰字母與明文字母的對應關係。
  2. 遍歷密鑰單詞:程式依序處理密鑰中的單詞,並利用字典檔案檢查單詞模式是否存在於已知英文單詞中。
  3. 更新字母對映:透過 addLettersToMapping 函式,將可能的明文字母加入對應的密鑰字母對映中。
  4. 交叉驗證對映:使用 intersectMappings 函式,將新的對映與現有的對映進行交叉驗證,以確保一致性。

程式碼解析

def hackSimpleSubstitution(ciphertext):
    # 初始化空白對映
    intersectedMap = blankLetterMapping()
    cipherwordList = nonLettersOrSpacePattern.sub('', ciphertext.upper()).split()
    
    for cipherword in cipherwordList:
        newMap = blankLetterMapping()
        wordPattern = getWordPattern(cipherword)
        
        if wordPattern not in wordPatterns.allPatterns:
            continue
        
        # 更新字母對映
        for candidate in wordPatterns.allPatterns[wordPattern]:
            newMap = addLettersToMapping(newMap, cipherword, candidate)
        
        # 交叉驗證對映
        intersectedMap = intersectMappings(intersectedMap, newMap)
    
    return removeSolvedLettersFromMapping(intersectedMap)

內容解密:

  • blankLetterMapping() 用於建立初始空白對映,確保每個密鑰字母都有對應的可能明文字母集合。
  • getWordPattern(cipherword) 取得密鑰單詞的模式,例如 “hello” 的模式為 “0.1.2.2.3”,用於匹配可能的明文單詞。
  • addLettersToMapping(newMap, cipherword, candidate) 更新字母對映,將候選明文單詞的字母對應到密鑰單詞的字母。
  • intersectMappings(intersectedMap, newMap) 進行交叉驗證,確保不同密鑰單詞推匯出的字母對映保持一致。

從字母對映建立解密金鑰

decryptWithCipherletterMapping 函式負責將字母對映轉換為簡單替換密碼的解密金鑰,並使用該金鑰解密密鑰。

程式碼解析

def decryptWithCipherletterMapping(ciphertext, letterMapping):
    key = ['x'] * len(LETTERS)
    
    for cipherletter in LETTERS:
        if len(letterMapping[cipherletter]) == 1:
            keyIndex = LETTERS.find(letterMapping[cipherletter][0])
            key[keyIndex] = cipherletter
        else:
            ciphertext = ciphertext.replace(cipherletter.lower(), '_')
            ciphertext = ciphertext.replace(cipherletter.upper(), '_')
    
    key = ''.join(key)
    return simpleSubCipher.decryptMessage(key, ciphertext)

內容解密:

  • 初始化一個包含 26 個 ‘x’ 的列表作為金鑰範本,‘x’ 代表未知字母。
  • 遍歷 LETTERS 中的每個字母,如果該字母在 letterMapping 中只有一個可能的解密字母,則將其填入金鑰對應的位置。
  • 如果某個密鑰字母有多個可能的解密字母,則在密鑰中將該字母替換為底線,以標示無法確定的部分。
  • 最終將金鑰列表轉換為字串,並使用 simpleSubCipher.decryptMessage 函式解密密鑰。

為何不直接加密空格?

雖然加密空格可以增加破解難度,但由於空格通常是密鑰中出現頻率最高的符號,攻擊者仍可透過統計分析推斷出空格對應的密鑰符號。因此,加密空格並不能提供足夠的安全性提升。

維吉尼亞密碼:歷史與原理

維吉尼亞密碼是一種比簡單替換密碼更為強大的加密技術。它使用多個金鑰進行加密,因而被稱為多字母替換密碼。維吉尼亞密碼在歷史上曾經被認為是無法破解的,直到19世紀才被查爾斯·巴貝奇成功破解。

多重金鑰的概念

維吉尼亞密碼與凱撒密碼相似,但它使用了一系列字母作為金鑰,而不是單一的數字金鑰。每個字母對應一個數字,從A(0)到Z(25)。例如,金鑰「PIZZA」會被分解為多個子金鑰:P(15)、I(8)、Z(25)、Z(25)和A(0)。

加密過程範例

使用金鑰「PIZZA」對明文「Common sense is not so common.」進行加密的過程如下:

  1. 將明文的每個字母與對應的子金鑰進行凱撒密碼加密。
  2. 第一個字母「C」與子金鑰「P」(15)進行加密,得到密鑰「R」。
  3. 依此類別推,每個字母都使用對應的子金鑰進行加密。

加密過程如下表所示:

明文字母子金鑰密鑰字母
C (2)P (15)R (17)
O (14)I (8)W (22)
M (12)Z (25)L (11)
M (12)Z (25)L (11)
O (14)A (0)O (14)
N (13)P (15)C (2)
S (18)I (8)A (0)
E (4)Z (25)D (3)
N (13)Z (25)M (12)
S (18)A (0)S (18)
E (4)P (15)T (19)
I (8)I (8)Q (16)
S (18)Z (25)R (17)
N (13)Z (25)M (12)
O (14)A (0)O (14)
T (19)P (15)I (8)
S (18)I (8)A (0)
O (14)Z (25)N (13)
C (2)Z (25)B (1)
O (14)A (0)O (14)
M (12)P (15)B (1)
M (12)I (8)U (20)
O (14)Z (25)N (13)
N (13)Z (25)M (12)

程式碼實作

def vigenere_cipher(plaintext, key):
    # 將金鑰轉換為子金鑰列表
    subkeys = [ord(k.upper()) - ord('A') for k in key]
    
    # 初始化密鑰
    ciphertext = ""
    
    # 遍歷明文的每個字元
    for i, char in enumerate(plaintext):
        if char.isalpha():
            # 取得對應的子金鑰
            subkey = subkeys[i % len(subkeys)]
            
            # 進行凱撒密碼加密
            if char.isupper():
                ciphertext += chr((ord(char) - ord('A') + subkey) % 26 + ord('A'))
            else:
                ciphertext += chr((ord(char) - ord('a') + subkey) % 26 + ord('a'))
        else:
            ciphertext += char
    
    return ciphertext

# 範例使用
plaintext = "Common sense is not so common."
key = "PIZZA"
ciphertext = vigenere_cipher(plaintext, key)
print(ciphertext)

內容解密:

  1. vigenere_cipher 函式接受明文和金鑰作為輸入,並傳回加密後的密鑰。
  2. 將金鑰轉換為子金鑰列表,每個子金鑰對應一個數字(A=0, B=1, …, Z=25)。
  3. 遍歷明文的每個字元,如果是字母,則使用對應的子金鑰進行凱撒密碼加密。
  4. 使用模運算確保加密結果在字母表範圍內。
  5. 非字母字元保持不變,直接新增到密鑰中。

金鑰長度與安全性

維吉尼亞密碼的安全性取決於金鑰的長度。較長的金鑰提供了更高的安全性,因為它增加了暴力破解的難度。例如,金鑰「PIZZA」有5個字母,對應$26^5 = 11,881,376$種可能的組合。雖然這個數量對於人工破解來說仍然過大,但對於電腦來說,只需幾個小時就能嘗試所有可能的金鑰。

維吉尼亞密碼技術深度解析

維吉尼亞密碼(Vigenère Cipher)是一種多字母替換加密技術,因其複雜性和歷史重要性而聞名。本章將探討維吉尼亞密碼的工作原理、其安全性,以及如何使用程式碼實作加密和解密。

金鑰長度與安全性

維吉尼亞密碼的安全性在很大程度上取決於其金鑰的長度。金鑰越長,可能的金鑰組合就越多,從而使暴力破解變得更加困難。下表展示了不同金鑰長度下的可能金鑰數量:

金鑰長度方程式可能的金鑰數量
126 = 2626
226 × 26 = 676676
3676 × 26 = 17,57617,576
417,576 × 26 = 456,976456,976
5456,976 × 26 = 11,881,37611,881,376
611,881,376 × 26 = 308,915,776308,915,776
7308,915,776 × 26 = 8,031,810,1768,031,810,176
88,031,810,176 × 26 = 208,827,064,576208,827,064,576
9208,827,064,576 × 26 = 5,429,503,678,9765,429,503,678,976
105,429,503,678,976 × 26 = 141,167,095,653,376141,167,095,653,376
12… × 26 = 95,428,956,661,682,17695,428,956,661,682,176

當金鑰長度達到12個字母或以上時,對大多數消費級筆記型電腦來說,在合理時間內破解變得極為困難。

金鑰選擇的重要性

金鑰不一定要是一個單詞,如「PIZZA」。它可以是任何字母的組合,例如「DURIWKNMFICK」。實際上,最好不要使用字典中的單詞,因為密碼分析者可能會預期密碼學家會使用字典單詞作為金鑰。使用一個難以猜測的金鑰,如隨機生成的字母組合,可以顯著提高安全性。

程式碼實作

以下是使用Python實作維吉尼亞密碼的程式碼範例:

# Vigenere Cipher (Polyalphabetic Substitution Cipher)

import pyperclip

LETTERS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

def main():
    myMessage = """Alan Mathison Turing was a British mathematician..."""
    myKey = 'ASIMOV'
    myMode = 'encrypt' # 設定為 'encrypt' 或 'decrypt'

    if myMode == 'encrypt':
        translated = encryptMessage(myKey, myMessage)
    elif myMode == 'decrypt':
        translated = decryptMessage(myKey, myMessage)

    print('%sed message:' % (myMode.title()))
    print(translated)
    pyperclip.copy(translated)
    print()
    print('訊息已複製到剪貼簿。')

def encryptMessage(key, message):
    return translateMessage(key, message, 'encrypt')

def decryptMessage(key, message):
    return translateMessage(key, message, 'decrypt')

def translateMessage(key, message, mode):
    translated = [] # 儲存加密/解密後的訊息字串

    keyIndex = 0
    key = key.upper()

    for symbol in message: # 對訊息中的每個字元進行迴圈
        num = LETTERS.find(symbol.upper())
        if num != -1: # -1 表示 symbol.upper() 不在 LETTERS 中
            if mode == 'encrypt':
                num += LETTERS.find(key[keyIndex]) # 如果是加密則加上金鑰
            elif mode == 'decrypt':
                num -= LETTERS.find(key[keyIndex]) # 如果是解密則減去金鑰

            num %= len(LETTERS) # 處理可能的環繞

            # 將加密/解密後的符號新增到 translated 的末尾
            if symbol.isupper():
                translated.append(LETTERS[num])
            elif symbol.islower():
                translated.append(LETTERS[num].lower())

            keyIndex += 1 # 移至金鑰中的下一個字母
            if keyIndex == len(key):
                keyIndex = 0
        else:
            # 如果符號不在 LETTERS 中,則按原樣新增到 translated
            translated.append(symbol)

    return ''.join(translated)

if __name__ == '__main__':
    main()

程式碼解密:

  1. LETTERS變數定義了所有大寫字母,用於索引和操作字母。
  2. main函式設定了要加密或解密的訊息、金鑰和模式,並呼叫相應的函式進行處理。
  3. encryptMessagedecryptMessage函式分別呼叫translateMessage函式,並傳入不同的模式引數('encrypt''decrypt')。
  4. translateMessage函式是核心加密/解密邏輯所在。它遍歷輸入訊息中的每個字元,並根據金鑰和模式進行相應的操作。
  5. **金鑰索引keyIndex**用於跟蹤當前使用的金鑰字母,並在到達金鑰末尾時迴圈回第一個字母。
  6. **模運算**num %= len(LETTERS)確保結果始終在字母表範圍內,避免索引越界。
  7. 大小寫處理確保輸出訊息中的字母大小寫與輸入訊息保持一致。
  8. 非字母字元直接新增到輸出中,不進行任何修改。

維吉尼亞密碼(Vigenère Cipher)技術深度解析

維吉尼亞密碼是一種複雜的替換加密技術,屬於多字母替換密碼(Polyalphabetic Substitution Cipher)範疇。它透過使用不同的金鑰對明文的不同部分進行加密,顯著提升了密碼的安全性。

程式實作核心邏輯

以下程式碼片段展示了維吉尼亞密碼的加密與解密核心實作:

def translateMessage(key, message, mode):
    translated = []
    keyIndex = 0
    key = key.upper()

    for symbol in message:
        num = LETTERS.find(symbol.upper())
        if num != -1:
            if mode == 'encrypt':
                num += LETTERS.find(key[keyIndex])
            elif mode == 'decrypt':
                num -= LETTERS.find(key[keyIndex])
            num %= len(LETTERS)
            # 取得加密/解密後的字母
            if symbol.isupper():
                translated.append(LETTERS[num])
            else:
                translated.append(LETTERS[num].lower())
            keyIndex = (keyIndex + 1) % len(key)
        else:
            translated.append(symbol)
    return ''.join(translated)

內容解密:

  1. translated 列表初始化:用於儲存加密或解密後的字元,最終透過 ''.join(translated) 組合成完整字串。
  2. keyIndex 與金鑰管理keyIndex 用於追蹤目前使用的金鑰字元,下標自動迴圈以確保金鑰重複使用。
  3. 字元轉換邏輯
    • 使用 LETTERS.find(symbol.upper()) 將字元轉換為對應的索引數字。
    • 根據 mode 引數決定是加密(累加)還是解密(累減)。
    • 使用模運算 num %= len(LETTERS) 處理索引溢位問題。
  4. 大小寫處理:保留原始字元的大小寫狀態。
  5. 非字母字元處理:直接附加至輸出結果,不進行任何加密或解密操作。

技術特點與應用考量

  1. 多字母替換機制:相較於單一替換密碼(如凱撒密碼),維吉尼亞密碼使用動態金鑰提升了破解難度。
  2. 金鑰管理:金鑰長度與複雜度直接影響加密安全性。較長的金鑰可有效抵禦頻率分析攻擊。
  3. 實務應用限制:在現代密碼學中,維吉尼亞密碼已不再被視為安全加密手段,主要用於教育與歷史研究。

未來發展趨勢

隨著計算能力的提升與密碼分析技術的進步,傳統的多字母替換密碼已無法滿足現代資安需求。然而,其設計理念仍對現代加密演算法具有參考價值,特別是在動態金鑰管理與複雜性設計方面。