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

– 8 分鐘閱讀

簡單替代密碼是一種常見的加密方式，其安全性建立在金鑰的保密性上。然而，僅僅依靠龐大的金鑰空間並不足以確保安全，因為詞彙模式和正規表示式等技術可以有效地破解這類別密碼。透過分析密鑰單詞的詞彙模式，我們可以從字典中篩選出可能的明文單詞，並建立密碼字母與潛在解密字母之間的對映關係。藉由比對密鑰與候選明文單詞的模式，逐步推匯出金鑰，從而破解密鑰。本文提供的 Python 程式碼示範瞭如何計算詞彙模式、建立詞彙模式字典以及如何利用這些技術進行簡單替代密碼的破解。程式碼中使用 pprint 模組最佳化輸出格式，並採用高效的字串構建方法提升程式效能。

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

前言

在前一章中，我們探討了簡單替代密碼（Simple Substitution Cipher）的基本原理及其加密方法。簡單替代密碼由於其龐大的金鑰空間，使得暴力破解變得幾乎不可能。因此，我們需要更為智慧的破解演算法來攻破這種加密技術。本章將重點介紹如何利用詞彙模式（Word Patterns）和正規表示式（Regular Expressions）等技術來破解簡單替代密碼。

詞彙模式計算

詞彙模式是指一個單詞中字母的重複模式。例如，單詞 “cat” 的詞彙模式是 0.1.2，而 “catty” 的詞彙模式則是 0.1.2.2.3。無論使用何種簡單替代密碼，金鑰加密後的密鑰單詞（cipherword）與其對應的明文單詞（plaintext word）始終具有相同的詞彙模式。

程式碼範例：計算詞彙模式

def get_word_pattern(word):
    word = word.upper()
    next_num = 0
    letter_nums = {}
    word_pattern = []

    for letter in word:
        if letter not in letter_nums:
            letter_nums[letter] = str(next_num)
            next_num += 1
        word_pattern.append(letter_nums[letter])
    return '.'.join(word_pattern)

# 測試範例
print(get_word_pattern("cat"))  # 輸出：0.1.2
print(get_word_pattern("roofer"))  # 輸出：0.1.1.2.3.0

內容解密：

  1. get_word_pattern 函式接收一個單詞作為輸入，並將其轉換為大寫字母以確保大小寫不敏感。
  2. 使用字典 letter_nums 來記錄每個字母對應的數字，從 0 開始。
  3. 遍歷單詞中的每個字母，如果字母尚未出現在 letter_nums 中，則分配一個新的數字，並遞增 next_num。
  4. 將每個字母對應的數字加入 word_pattern 列表中。
  5. 最後，將 word_pattern 列表中的數字以點號（.）連線，形成最終的詞彙模式。

取得密鑰單詞的候選明文單詞

透過計算密鑰單詞的詞彙模式，我們可以從字典檔案中找出具有相同詞彙模式的明文單詞作為候選單詞。

程式碼範例：取得候選單詞

def get_candidates(cipherword, word_pattern_dict):
    pattern = get_word_pattern(cipherword)
    return word_pattern_dict.get(pattern, [])

# 假設 word_pattern_dict 是預先建立好的詞彙模式字典
word_pattern_dict = {...}  # 詞彙模式字典

# 測試範例
cipherword = "HGHHU"
candidates = get_candidates(cipherword, word_pattern_dict)
print(candidates)  # 輸出具有相同詞彙模式的明文單詞列表

內容解密：

  1. get_candidates 函式接收一個密鑰單詞和一個預先建立的詞彙模式字典作為輸入。
  2. 使用 get_word_pattern 函式計算密鑰單詞的詞彙模式。
  3. 從詞彙模式字典中查詢具有相同詞彙模式的明文單詞列表。
  4. 傳回候選明文單詞列表，如果沒有找到匹配的詞彙模式，則傳回空列表。

建立密碼字母對映

透過分析密鑰單詞及其候選明文單詞，可以建立密碼字母（cipherletter）與其潛在解密字母（potential decryption letters）之間的對映關係。

程式碼範例：建立密碼字母對映

def create_cipherletter_mapping(cipherword, candidates):
    mapping = {}
    for letter in cipherword.upper():
        mapping[letter] = set()

    for candidate in candidates:
        for i, letter in enumerate(cipherword.upper()):
            mapping[letter].add(candidate[i].upper())

    return mapping

# 測試範例
cipherword = "HGHHU"
candidates = ["PUPPY", "MOMMY", "BOBBY"]
mapping = create_cipherletter_mapping(cipherword, candidates)
print(mapping)  # 輸出密碼字母對映

內容解密：

  1. create_cipherletter_mapping 函式接收一個密鑰單詞和其候選明文單詞列表作為輸入。
  2. 初始化一個字典 mapping 來儲存密碼字母對映，鍵為密碼字母，值為一個集合用於儲存潛在解密字母。
  3. 遍歷每個候選明文單詞，將對應位置的明文字母加入到相應密碼字母的潛在解密字母集合中。
  4. 傳回密碼字母對映字典。

簡單替換密碼破解中的詞彙模式處理

在破解簡單替換密碼的過程中，我們需要建立一個詞彙模式字典，以便快速查詢特定模式的單詞。這個過程涉及計算字典檔案中每個單詞的詞彙模式，並將這些模式儲存在一個檔案中，以便後續使用。

詞彙模式的計算

詞彙模式是指單詞中字母的重複模式。例如，單詞 “DUSTBUSTER” 的詞彙模式是 “0.1.2.3.4.1.2.3.5.6”。要計算詞彙模式，我們需要遍歷單詞中的每個字母，並為每個新的字母分配一個唯一的數字。

詞彙模式計算程式碼

def getWordPattern(word):
    # 將單詞轉換為大寫
    word = word.upper()
    nextNum = 0
    letterNums = {}
    wordPattern = []

    # 遍歷單詞中的每個字母
    for letter in word:
        if letter not in letterNums:
            # 為新的字母分配一個唯一的數字
            letterNums[letter] = str(nextNum)
            nextNum += 1
        # 將字母對應的數字新增到詞彙模式列表中
        wordPattern.append(letterNums[letter])
    # 將詞彙模式列表連線成一個字串
    return '.'.join(wordPattern)

詞彙模式字典的建立

為了建立詞彙模式字典，我們需要讀取字典檔案中的每個單詞，計算其詞彙模式，並將這些模式儲存在一個字典中。

def main():
    allPatterns = {}

    # 讀取字典檔案
    fo = open('dictionary.txt')
    wordList = fo.read().split('\n')
    fo.close()

    # 遍歷字典檔案中的每個單詞
    for word in wordList:
        # 計算單詞的詞彙模式
        pattern = getWordPattern(word)

        if pattern not in allPatterns:
            # 如果詞彙模式不在字典中，則新增它
            allPatterns[pattern] = [word]
        else:
            # 如果詞彙模式已經在字典中，則將單詞新增到對應的列表中
            allPatterns[pattern].append(word)

    # 將詞彙模式字典寫入檔案
    fo = open('wordPatterns.py', 'w')
    fo.write('allPatterns = ')
    fo.write(pprint.pformat(allPatterns))
    fo.close()

詞彙模式字典的使用

建立好詞彙模式字典後，我們可以在破解簡單替換密碼時使用它來查詢特定模式的單詞。

>>> import wordPatterns
>>> wordPatterns.allPatterns['0.1.2.1.1.3.4']
['BAZAARS', 'BESEECH', 'REDEEMS', 'STUTTER']
>>> wordPatterns.allPatterns['0.1.2.2.3.2.4.1.5.5']
['CANNONBALL']

#### 內容解密：

  1. 詞彙模式計算：getWordPattern 函式負責計算單詞的詞彙模式。它遍歷單詞中的每個字母，並為每個新的字母分配一個唯一的數字。
  2. 詞彙模式字典建立：main 函式讀取字典檔案，計算每個單詞的詞彙模式，並將這些模式儲存在一個字典中。
  3. 查詢特定模式的單詞：透過匯入 wordPatterns 模組，我們可以查詢特定模式的單詞列表。

這種方法可以有效地幫助我們破解簡單替換密碼。透過建立詞彙模式字典，我們可以快速查詢特定模式的單詞，從而推斷出密碼中的字母對應關係。

簡單替代密碼破解中的單詞模式分析

在簡單替代密碼的破解過程中，理解單詞的模式對於解密具有重要意義。單詞模式是指單詞中字母的出現順序及其重複情況的數字表示。

使用 pprint 模組最佳化輸出

在處理複雜的資料結構，如字典或列表時，Python 的 pprint 模組能夠提供更易讀的輸出格式。透過 pprint.pprint() 和 pprint.pformat() 函式，可以將資料以更清晰的方式呈現於螢幕或轉換為字串。

import pprint

someListOfListsVar = [['ant'], ['baboon', 'badger', 'bat', 'bear', 'beaver'], 
                      ['camel', 'cat', 'clam', 'cobra', 'cougar', 'coyote', 'crow'], 
                      ['deer', 'dog', 'donkey', 'duck'], ['eagle'], 
                      ['ferret', 'fox', 'frog'], ['goat']]

# 使用 pprint.pprint() 函式輸出
pprint.pprint(someListOfListsVar)

# 使用 pprint.pformat() 函式轉換為字串
prettifiedString = pprint.pformat(someListOfListsVar)
print(prettifiedString)

內容解密：

  1. pprint.pprint() 直接將資料以易讀格式輸出到螢幕。
  2. pprint.pformat() 將資料轉換為易讀格式的字串，可用於進一步處理或儲存。
  3. 這兩個函式對於除錯和展示複雜資料結構非常有用。

高效字串構建方法

在 Python 中，使用串聯（concatenation）構建字串是一種常見但效率較低的方法。更高效的方法是使用列表（list）儲存中間結果，然後透過 join() 方法合併成最終的字串。

# 低效的字串構建方法
building = ''
for c in 'Hello world!':
    building += c
print(building)

# 高效的字串構建方法
building = []
for c in 'Hello world!':
    building.append(c)
building = ''.join(building)
print(building)

內容解密：

  1. 第一個範例使用傳統的串聯方式逐一新增字元到 building 字串中。
  2. 第二個範例則是先將字元新增到列表 building 中，最後透過 ''.join(building) 合併成一個完整的字串。
  3. 後者對於大量字串操作更為高效，因為它避免了頻繁的字串重新分配和複製。

計算單詞模式

單詞模式的計算是簡單替代密碼破解中的一個關鍵步驟。getWordPattern() 函式負責將給定的單詞轉換為其對應的模式。

def getWordPattern(word):
    word = word.upper()
    nextNum = 0
    letterNums = {}
    wordPattern = []
    
    for letter in word:
        if letter not in letterNums:
            letterNums[letter] = str(nextNum)
            nextNum += 1
        wordPattern.append(letterNums[letter])
    
    return '.'.join(wordPattern)

# 範例用法
print(getWordPattern('Buffoon'))  # 輸出：0.1.2.2.3.3.4

內容解密：

  1. 將輸入的單詞轉換為大寫，以確保大小寫不敏感。
  2. 使用字典 letterNums 記錄每個字母對應的數字，首次出現的字母被賦予一個新的數字。
  3. 將每個字母對應的數字新增到 wordPattern 列表中。
  4. 最後，透過 '.'.join(wordPattern) 將數字列表合併成一個以點分隔的字串，代表單詞的模式。

簡單替換密碼破解中的單詞模式程式解析

程式功能概述

此程式用於產生一個包含單詞模式的字典，並將其儲存至檔案中，以輔助簡單替換密碼的破解。單詞模式是指單詞中字母的相對順序，而非其實際字母。

getWordPattern 函式詳解

函式目的

將輸入的單詞轉換為其對應的單詞模式。

程式碼解析

def getWordPattern(word):
    word = word.upper()
    nextNum = 0
    letterNums = {}
    wordPattern = []

    for letter in word:
        if letter not in letterNums:
            letterNums[letter] = str(nextNum)
            nextNum += 1
        wordPattern.append(letterNums[letter])
    return '.'.join(wordPattern)

內容解密：

  1. 單詞預處理：將輸入的 word 轉換為大寫，以確保處理的一致性。
  2. 初始化變數：
    • nextNum：用於為新出現的字母分配一個唯一的數字，從0開始。
    • letterNums：一個字典，用於儲存字母及其對應的數字。
    • wordPattern：一個列表，用於儲存單詞模式的數字序列。
  3. 遍歷單詞中的每個字母：
    • 若字母尚未出現在 letterNums 中，則為其分配一個新的數字，並遞增 nextNum。
    • 將字母對應的數字追加到 wordPattern 中。
  4. 傳回單詞模式：使用 ‘.’ 將 wordPattern 中的數字連線成字串後傳回。

main 函式詳解

函式目的

讀取字典檔案，計算每個單詞的單詞模式，並將結果儲存至 wordPatterns.py 檔案中。

程式碼解析

def main():
    allPatterns = {}

    fo = open('dictionary.txt')
    wordList = fo.read().split('\n')
    fo.close()

    for word in wordList:
        pattern = getWordPattern(word)
        if pattern not in allPatterns:
            allPatterns[pattern] = [word]
        else:
            allPatterns[pattern].append(word)

    fo = open('wordPatterns.py', 'w')
    fo.write('allPatterns = ')
    fo.write(pprint.pformat(allPatterns))
    fo.close()

內容解密：

  1. 初始化：建立一個空字典 allPatterns 用於儲存單詞模式及其對應的單詞列表。
  2. 讀取字典檔案：將 dictionary.txt 中的單詞讀入 wordList 列表中。
  3. 計算單詞模式：
    • 遍歷 wordList 中的每個單詞，計算其單詞模式。
    • 將單詞模式作為鍵，單詞作為值，存入 allPatterns 中。若鍵已存在，則將單詞追加至對應的值列表中。
  4. 寫入結果檔案：
    • 開啟 wordPatterns.py 檔案，將 allPatterns 字典以 Python 程式碼的形式寫入其中。
    • 使用 pprint.pformat 美化字典的輸出格式。

程式執行流程圖示

@startuml
skinparam backgroundColor #FEFEFE
skinparam componentStyle rectangle

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

package "資料庫架構" {
    package "應用層" {
        component [連線池] as pool
        component [ORM 框架] as orm
    }

    package "資料庫引擎" {
        component [查詢解析器] as parser
        component [優化器] as optimizer
        component [執行引擎] as executor
    }

    package "儲存層" {
        database [主資料庫] as master
        database [讀取副本] as replica
        database [快取層] as cache
    }
}

pool --> orm : 管理連線
orm --> parser : SQL 查詢
parser --> optimizer : 解析樹
optimizer --> executor : 執行計畫
executor --> master : 寫入操作
executor --> replica : 讀取操作
cache --> executor : 快取命中

master --> replica : 資料同步

note right of cache
  Redis/Memcached
  減少資料庫負載
end note

@enduml

此圖示展示了程式的主要執行流程，包括讀取字典檔案、計算單詞模式、儲存結果等步驟。

玄貓 BlackCat

玄貓 BlackCat

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