返回文章列表
玄貓（BlackCat）

Python 頻率分析與排序技術

本文探討 Python 中頻率分析的排序技術與函式傳遞機制，並解析如何應用於破解維吉尼亞密碼。文章涵蓋 sort() 方法的 key 和 reverse 引數、函式作為值傳遞的應用、字典轉換為列表的方法、以及卡西斯基檢驗法和頻率分析的實踐步驟。

密碼學 Python
頻率分析 排序 Python 函式 維吉尼亞密碼 卡西斯基檢驗法 字典攻擊

Python 的排序與函式傳遞機制為頻率分析提供了強大的支援。sort() 函式的 key 引數允許我們根據自定義規則排序，例如利用 ETAOIN 字串進行字母頻率排序，而 reverse 引數則控制排序方向。更進一步，Python 支援將函式作為值傳遞，提升程式碼的靈活性和可重用性，這在 sort() 方法中得到充分體現。理解字典的 keys()、values() 和 items() 方法，可以有效地將字典轉換為列表，方便後續的排序和分析操作。這些技術為密碼分析，特別是針對維吉尼亞密碼的破解，提供了必要的工具。

頻率分析中的排序與函式傳遞

在進行頻率分析時，排序是一個非常重要的步驟。Python 的 sort() 函式提供了一個非常有用的功能，可以讓我們根據特定的規則來排序列表中的元素。

使用 sort() 方法的 key 和 reverse 引數

在 freqAnalysis.py 的第 47 行到第 49 行，我們可以看到如何使用 sort() 方法來排序字母列表。

for freq in freqToLetter:
    freqToLetter[freq].sort(key=ETAOIN.find, reverse=True)
    freqToLetter[freq] = ''.join(freqToLetter[freq])

內容解密：

  1. 迴圈遍歷 freqToLetter 字典：這裡的 freq 代表的是字母出現的頻率，而 freqToLetter[freq] 則是具有相同頻率的字母列表。
  2. sort() 方法的 key 引數：key=ETAOIN.find 表示根據字母在 ETAOIN 字串中的位置進行排序。ETAOIN 是一個按照英語字母出現頻率排序的字串。
  3. reverse=True：這個引數讓排序結果按照逆序排列，也就是頻率最高的字母排在最前面。
  4. ''.join(freqToLetter[freq])：將排序後的字母列表轉換成字串。

將函式作為值傳遞

在 Python 中，函式本身可以被當作值來傳遞。這在 sort() 方法中得到了體現。

def doMath(func):
    return func(10, 5)

def adding(a, b):
    return a + b

def subtracting(a, b):
    return a - b

print(doMath(adding))  # 輸出：15
print(doMath(subtracting))  # 輸出：5

內容解密：

  1. doMath() 函式接受另一個函式作為引數：這裡的 func 可以是任何一個接受兩個引數的函式。
  2. adding() 和 subtracting() 函式：這兩個函式分別執行加法和減法運算。
  3. 呼叫 doMath() 並傳遞函式：當我們傳遞 adding 或 subtracting 給 doMath() 時，它會根據傳入的函式執行相應的運算。

為什麼這樣做？

將函式作為引數傳遞給其他函式，可以增加程式的靈活性和可重用性。在 sort() 方法中，這種機制讓我們可以自定義排序規則，而不需要修改 sort() 方法本身的實作。

頻率分析技術解析與實踐

頻率分析是密碼學中的一個重要技術，用於分析文字中字母的出現頻率，以幫助破解密碼。在本章中，我們將探討頻率分析的原理和實作方法。

字典轉換為列表：keys()、values() 和 items() 方法

在 Python 中，字典是一種無序的資料結構，但我們可以透過 keys()、values() 和 items() 方法將其轉換為列表。

keys() 方法

keys() 方法傳回一個 dict_keys 物件，該物件包含了字典中的所有鍵。我們可以將其傳遞給 list() 函式，以取得一個包含所有鍵的列表。

spam = {'cats': 10, 'dogs': 3, 'mice': 3}
print(list(spam.keys()))  # 輸出：['cats', 'dogs', 'mice'] 或其他順序

values() 方法

values() 方法傳回一個 dict_values 物件，該物件包含了字典中的所有值。我們可以將其傳遞給 list() 函式，以取得一個包含所有值的列表。

spam = {'cats': 10, 'dogs': 3, 'mice': 3}
print(list(spam.values()))  # 輸出：[10, 3, 3] 或其他順序

items() 方法

items() 方法傳回一個 dict_items 物件，該物件包含了字典中的所有鍵值對。我們可以將其傳遞給 list() 函式，以取得一個包含所有鍵值對的列表。

spam = {'cats': 10, 'dogs': 3, 'mice': 3}
print(list(spam.items()))  
# 輸出：[('cats', 10), ('dogs', 3), ('mice', 3)] 或其他順序

內容解密：

  1. keys()、values() 和 items() 方法分別傳回字典的鍵、值和鍵值對。
  2. 將這些方法傳回的物件傳遞給 list() 函式，可以取得相應的列表。
  3. 這些列表的順序是隨機的，因為字典是無序的資料結構。

對字典專案進行排序

在頻率分析中，我們需要對字母的出現頻率進行排序。為此，我們可以使用 items() 方法將字典轉換為列表，然後使用 sort() 方法進行排序。

freqToLetter = {196: ['E'], 140: ['T'], 139: ['I']}
freqPairs = list(freqToLetter.items())
freqPairs.sort(key=lambda x: x[0], reverse=True)
print(freqPairs)  
# 輸出：[(196, ['E']), (140, ['T']), (139, ['I'])]

內容解密：

  1. 將字典轉換為列表，使用 items() 方法。
  2. 使用 sort() 方法對列表進行排序，key 引數指定排序的依據。
  3. reverse=True 表示按降序排序。

取得頻率順序

透過對字母的出現頻率進行排序，我們可以取得頻率順序。

freqOrder = []
for freqPair in freqPairs:
    freqOrder.append(freqPair[1])
print(''.join(freqOrder))  
# 輸出：'ETI'

內容解密：

  1. 將排序後的列表中的值提取出來，儲存在 freqOrder 列表中。
  2. 使用 join() 方法將 freqOrder 列表中的元素連線成一個字串。

英文頻率匹配評分

透過比較文字的字母頻率與英文的字母頻率，我們可以評估文字的可讀性。

def englishFreqMatchScore(message):
    freqOrder = getFrequencyOrder(message)
    matchScore = 0
    for commonLetter in ETAOIN[:6]:
        if commonLetter in freqOrder[:6]:
            matchScore += 1
    return matchScore

內容解密：

  1. 取得文字的頻率順序，使用 getFrequencyOrder() 函式。
  2. 初始化匹配評分 matchScore 為 0。
  3. 將文字的前 6 個最常見字母與英文的前 6 個最常見字母進行比較，如果匹配，則增加 matchScore。
  4. 傳回匹配評分 matchScore。

頻率分析與維吉尼亞密碼破解技術深度解析

在前一章中，我們探討了頻率分析的技術細節，並實作了一個簡單的頻率分析模組，用於評估文字的加密品質。本章將進一步延伸這個主題，重點介紹如何利用頻率分析和其他技術手段來破解歷史上著名的維吉尼亞密碼。

維吉尼亞密碼簡介及其安全性挑戰

維吉尼亞密碼是一種多字母替換加密技術，曾經被認為是不可破解的。其主要特點是使用一個關鍵字來決定每個字母的加密方式，這使得頻率分析變得更加複雜。然而，這種密碼仍然存在可被利用的弱點，特別是在關鍵字相對簡單或可被猜測的情況下。

字典攻擊：破解維吉尼亞密碼的第一步

字典攻擊是一種暴力破解方法，透過嘗試使用字典中的單字作為關鍵字來解密密鑰。這種方法在關鍵字是常見英文單字的情況下尤其有效。我們實作了一個名為vigenereDictionaryHacker.py的程式，利用dictionary.txt檔案中的約45,000個英文單字進行嘗試解密。

程式碼解析

def hackVigenere(ciphertext):
    fo = open('dictionary.txt')
    words = fo.readlines()
    fo.close()

    for word in words:
        word = word.strip() 
        decryptedText = vigenereCipher.decryptMessage(word, ciphertext)
        if detectEnglish.isEnglish(decryptedText, wordPercentage=40):
            # 檢查使用者是否確認已找到正確的解密金鑰
            print('Possible encryption break:')
            print('Key ' + str(word) + ': ' + decryptedText[:100])
            print('Enter D for done, or just press Enter to continue breaking:')
            response = input('> ')
            if response.upper().startswith('D'):
                return decryptedText

內容解密：

  1. hackVigenere函式：該函式負責執行字典攻擊，嘗試使用dictionary.txt中的每個單字來解密密鑰。
  2. detectEnglish.isEnglish：用於判斷解密後的文字是否為英文，若超過40%的單字是英文，則視為可能的解密結果。
  3. 使用者互動：程式會提示使用者確認解密結果是否正確，若使用者輸入D，則傳回解密後的文字。

進階破解技術

除了字典攻擊外，還有一種更為複雜的方法可以破解維吉尼亞密碼，即使關鍵字是隨機產生的。這種方法涉及更深入的密碼分析技術，包括卡西斯基檢驗和重合索引分析等。

破解維吉尼亞密碼（Vigenère Cipher）的高階技術

檔案讀取方法：readlines()

在處理檔案時，我們可以使用 readlines() 方法來讀取檔案內容。此方法會將檔案內容以列表形式傳回，每個列表元素代表檔案中的一行。需要注意的是，每個字串結尾都包含換行符號 \n，除了可能位於檔案結尾的字串。

巴貝奇攻擊與卡西斯基檢驗法

卡西斯基檢驗法是一種用於判斷維吉尼亞密碼金鑰長度的方法。該方法透過找出密鑰中重複出現的字母序列及其間距，進而推斷金鑰的可能長度。

卡西斯基檢驗法步驟一：找出重複序列的間距

首先，我們需要在密鑰中找出至少三個字母的重複序列。這些序列可能對應於明文中相同的字母被相同的子金鑰加密後的結果。例如，給定密鑰 “Ppqca xqvekg ybnkmazu ybngbal jon i tszm jyim. Vrag voht vrau c tksg. Ddwuo xitlazu vavv raz c vkb qp iwpou."，移除非字母字元後，我們發現序列 “VRA”、“AZU” 和 “YBN” 重複出現。

計算這些序列之間的間距：

  • “VRA” 第一次和第二次出現之間有 8 個字母。
  • “VRA” 第二次和第三次出現之間有 24 個字母。
  • “VRA” 第一次和第三次出現之間有 32 個字母。
  • “AZU” 第一次和第二次出現之間有 48 個字母。
  • “YBN” 第一次和第二次出現之間有 8 個字母。

卡西斯基檢驗法步驟二：計算間距的因數

接下來，我們計算這些間距的因數（不包括 1）：

  • 8 的因數是 2、4 和 8。
  • 24 的因數是 2、4、6、8、12 和 24。
  • 32 的因數是 2、4、8 和 16。
  • 48 的因數是 2、4、6、8、12、24 和 48。

統計這些因數的出現次數：

因數出現次數
24
44
62
84
122
161
242
481

出現次數最多的因數（2、4 和 8）很可能是維吉尼亞密碼金鑰的長度。

從字串中提取每 N 個字母

假設金鑰長度為 4，我們需要將密鑰分成四組，每組包含每第四個字母。對應到給定的密鑰，我們可以得到四個字串：

  1. 每第四個字母（從第一個字母開始）：PAEBABANZIAHAKDXAAAKIU
  2. 每第四個字母（從第二個字母開始）：PXKNZNLIMMGTUSWIZVZBW
  3. 每第四個字母（從第三個字母開始）：QQGKUGJTJVVVCGUTUVCQP
  4. 每第四個字母（從第四個字母開始）：CVYMYBOSYRORTDOLVRVPO

如果我們的猜測正確，這些字串分別對應於使用金鑰中不同子金鑰加密的結果。

頻率分析

維吉尼亞密碼本質上是多個凱撒密碼的組合。透過卡西斯基檢驗法，我們可以確定金鑰的長度，接下來只需依次破解每個子金鑰。以第一個字串 “PAEBABANZIAHAKDXAAAKIU” 為例，我們可以使用頻率分析法來破解。

#### 內容解密：

此處我們需要對每個字串進行頻率分析。首先，將每個字串使用所有可能的子金鑰（26 個）進行解密，然後計算解密後文字的英語頻率匹配分數。透過比較這些分數，我們可以找出最可能的正確解密鑰字和對應的子金鑰。

def frequency_analysis(ciphertext):
    # 對每個可能的 subkey（0-25）進行解密並計算頻率匹配分數
    for subkey in range(26):
        decrypted_text = vigenereCipher.decryptMessage(subkey, ciphertext)
        score = english_freq_match_score(decrypted_text)
        print(f'Subkey: {subkey}, Score: {score}, Decrypted Text: {decrypted_text[:20]}...')

# 對四個字串分別進行頻率分析
frequency_analysis('PAEBABANZIAHAKDXAAAKIU')
frequency_analysis('PXKNZNLIMMGTUSWIZVZBW')
frequency_analysis('QQGKUGJTJVVVCGUTUVCQP')
frequency_analysis('CVYMYBOSYRORTDOLVRVPO')

#### 內容解密：

上述程式碼展示瞭如何對四個字串進行頻率分析。我們遍歷所有可能的子金鑰，對每個子金鑰解密對應的字串，並計算解密後文字的英語頻率匹配分數。輸出結果將幫助我們識別最可能的正確子金鑰和解密鑰字。

結合所有子金鑰破解維吉尼亞密碼

一旦我們破解了所有子金鑰，就可以組合它們來得到完整的金鑰。然後，使用這個金鑰來解密原始密鑰，從而獲得明文。

#### 內容解密：

透過上述步驟，我們成功地破解了維吉尼亞密碼。卡西斯基檢驗法幫助我們確定了金鑰的長度，頻率分析使我們能夠破解每個子金鑰。最終，結合所有子金鑰，我們可以還原出完整的金鑰並解密密鑰。

@startuml
skinparam backgroundColor #FEFEFE
skinparam componentStyle rectangle

title Python 頻率分析與排序技術

package "Python 應用架構" {
    package "應用層" {
        component [主程式] as main
        component [模組/套件] as modules
        component [設定檔] as config
    }

    package "框架層" {
        component [Web 框架] as web
        component [ORM] as orm
        component [非同步處理] as async
    }

    package "資料層" {
        database [資料庫] as db
        component [快取] as cache
        component [檔案系統] as fs
    }
}

main --> modules : 匯入模組
main --> config : 載入設定
modules --> web : HTTP 處理
web --> orm : 資料操作
orm --> db : 持久化
web --> cache : 快取查詢
web --> async : 背景任務
async --> fs : 檔案處理

note right of web
  Flask / FastAPI / Django
end note

@enduml

此圖示說明瞭破解維吉尼亞密碼的流程，包括使用卡西斯基檢驗法確定金鑰長度、分割密鑰、進行頻率分析以破解子金鑰，以及最終組合子金鑰來解密原始密鑰。

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

維吉尼亞密碼簡介及其弱點分析

維吉尼亞密碼是一種歷史悠久的多字母替換加密技術，但其核心弱點在於金鑰的重複使用。透過精確的頻率分析與機率推斷，可以逐步破解該密碼。

關鍵技術：重複金鑰長度的推斷

重複金鑰長度的推斷是破解的第一步，透過計算不同間隔的重合指數（Index of Coincidence），可以找出最可能的金鑰長度。

頻率分析在維吉尼亞密碼破解中的應用

頻率分析的核心在於比對解密結果與英語文字的字母頻率分佈的接近程度。使用freqAnalysis.englishFreqMatchScore函式可以量化這種接近程度。

def freqAnalysis(text):
    # 計算文字的字母頻率並與標準英語頻率進行比對
    letter_count = {}
    for letter in text:
        if letter.isalpha():
            letter_count[letter] = letter_count.get(letter, 0) + 1
    # 計算頻率匹配分數
    score = englishFreqMatchScore(letter_count)
    return score

內容解密：

  1. letter_count字典用於儲存每個字母的出現次數，透過遍歷輸入文字實作統計。
  2. englishFreqMatchScore函式比對統計結果與標準英語字母頻率，傳回匹配度分數。
  3. 分數越高，表示該文字越接近自然英語。

金鑰推斷與暴力破解的結合

在獲得可能的金鑰片段後，透過組合不同的片段進行暴力破解，縮小候選金鑰的範圍。

程式碼範例：暴力破解金鑰組合

def bruteForceKeys(subkeys):
    possible_keys = []
    for subkey_combination in itertools.product(*subkeys):
        key = ''.join(subkey_combination)
        possible_keys.append(key)
    return possible_keys

內容解密：

  1. 使用itertools.product函式生成所有可能的金鑰組合。
  2. 將每個子金鑰的候選值組合成完整的金鑰，並儲存於possible_keys列表中。
  3. 透過遍歷possible_keys進行解密嘗試，直至找到正確的金鑰。

實戰演練：破解維吉尼亞密碼

步驟一：確定金鑰長度

透過重合指數法或其他統計方法推斷金鑰長度。

步驟二：頻率分析確定子金鑰

對每個子字串進行頻率分析，找出最可能的子金鑰。

步驟三：暴力破解確定最終金鑰

組合子金鑰並進行暴力破解，從而確定最終的正確金鑰。