簡單替換密碼的破解利用字詞頻率分析和模式匹配,程式碼中以 hackSimpleSubstitution 函式實作核心破解流程,包含初始化字母對映、遍歷密鑰單詞、更新和交叉驗證對映等步驟。解密金鑰則由 decryptWithCipherletterMapping 函式產生,將字母對映轉換為金鑰,並處理無法確定的字母。維吉尼亞密碼則是一種多字母替換加密技術,使用多個子金鑰進行加密,其安全性取決於金鑰長度。程式碼中以 vigenere_cipher 函式示範加密過程,並說明如何將金鑰轉換為子金鑰列表以及如何處理非字母字元。文章也探討了維吉尼亞密碼的金鑰長度、金鑰選擇的重要性,並提供 Python 程式碼範例,詳細說明瞭加密和解密的核心邏輯,以及大小寫和非字母字元的處理方式。
簡單替換密碼破解技術深度解析
密碼破解核心邏輯
簡單替換密碼(Simple Substitution Cipher)的破解依賴於字詞模式匹配和字母對映的交叉驗證。程式碼實作中,hackSimpleSubstitution 函式負責核心破解邏輯,其運作流程如下:
- 初始化空白對映:首先建立一個空白的字母對映,用於儲存密鑰字母與明文字母的對應關係。
- 遍歷密鑰單詞:程式依序處理密鑰中的單詞,並利用字典檔案檢查單詞模式是否存在於已知英文單詞中。
- 更新字母對映:透過
addLettersToMapping函式,將可能的明文字母加入對應的密鑰字母對映中。 - 交叉驗證對映:使用
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.」進行加密的過程如下:
- 將明文的每個字母與對應的子金鑰進行凱撒密碼加密。
- 第一個字母「C」與子金鑰「P」(15)進行加密,得到密鑰「R」。
- 依此類別推,每個字母都使用對應的子金鑰進行加密。
加密過程如下表所示:
| 明文字母 | 子金鑰 | 密鑰字母 |
|---|---|---|
| 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)
內容解密:
vigenere_cipher函式接受明文和金鑰作為輸入,並傳回加密後的密鑰。- 將金鑰轉換為子金鑰列表,每個子金鑰對應一個數字(A=0, B=1, …, Z=25)。
- 遍歷明文的每個字元,如果是字母,則使用對應的子金鑰進行凱撒密碼加密。
- 使用模運算確保加密結果在字母表範圍內。
- 非字母字元保持不變,直接新增到密鑰中。
金鑰長度與安全性
維吉尼亞密碼的安全性取決於金鑰的長度。較長的金鑰提供了更高的安全性,因為它增加了暴力破解的難度。例如,金鑰「PIZZA」有5個字母,對應$26^5 = 11,881,376$種可能的組合。雖然這個數量對於人工破解來說仍然過大,但對於電腦來說,只需幾個小時就能嘗試所有可能的金鑰。
維吉尼亞密碼技術深度解析
維吉尼亞密碼(Vigenère Cipher)是一種多字母替換加密技術,因其複雜性和歷史重要性而聞名。本章將探討維吉尼亞密碼的工作原理、其安全性,以及如何使用程式碼實作加密和解密。
金鑰長度與安全性
維吉尼亞密碼的安全性在很大程度上取決於其金鑰的長度。金鑰越長,可能的金鑰組合就越多,從而使暴力破解變得更加困難。下表展示了不同金鑰長度下的可能金鑰數量:
| 金鑰長度 | 方程式 | 可能的金鑰數量 |
|---|---|---|
| 1 | 26 = 26 | 26 |
| 2 | 26 × 26 = 676 | 676 |
| 3 | 676 × 26 = 17,576 | 17,576 |
| 4 | 17,576 × 26 = 456,976 | 456,976 |
| 5 | 456,976 × 26 = 11,881,376 | 11,881,376 |
| 6 | 11,881,376 × 26 = 308,915,776 | 308,915,776 |
| 7 | 308,915,776 × 26 = 8,031,810,176 | 8,031,810,176 |
| 8 | 8,031,810,176 × 26 = 208,827,064,576 | 208,827,064,576 |
| 9 | 208,827,064,576 × 26 = 5,429,503,678,976 | 5,429,503,678,976 |
| 10 | 5,429,503,678,976 × 26 = 141,167,095,653,376 | 141,167,095,653,376 |
| … | … | … |
| 12 | … × 26 = 95,428,956,661,682,176 | 95,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()
程式碼解密:
LETTERS變數定義了所有大寫字母,用於索引和操作字母。main函式設定了要加密或解密的訊息、金鑰和模式,並呼叫相應的函式進行處理。encryptMessage和decryptMessage函式分別呼叫translateMessage函式,並傳入不同的模式引數('encrypt'或'decrypt')。translateMessage函式是核心加密/解密邏輯所在。它遍歷輸入訊息中的每個字元,並根據金鑰和模式進行相應的操作。- **金鑰索引
keyIndex**用於跟蹤當前使用的金鑰字母,並在到達金鑰末尾時迴圈回第一個字母。 - **模運算
**num %= len(LETTERS)確保結果始終在字母表範圍內,避免索引越界。 - 大小寫處理確保輸出訊息中的字母大小寫與輸入訊息保持一致。
- 非字母字元直接新增到輸出中,不進行任何修改。
維吉尼亞密碼(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)
內容解密:
translated列表初始化:用於儲存加密或解密後的字元,最終透過''.join(translated)組合成完整字串。keyIndex與金鑰管理:keyIndex用於追蹤目前使用的金鑰字元,下標自動迴圈以確保金鑰重複使用。- 字元轉換邏輯:
- 使用
LETTERS.find(symbol.upper())將字元轉換為對應的索引數字。 - 根據
mode引數決定是加密(累加)還是解密(累減)。 - 使用模運算
num %= len(LETTERS)處理索引溢位問題。
- 使用
- 大小寫處理:保留原始字元的大小寫狀態。
- 非字母字元處理:直接附加至輸出結果,不進行任何加密或解密操作。
技術特點與應用考量
- 多字母替換機制:相較於單一替換密碼(如凱撒密碼),維吉尼亞密碼使用動態金鑰提升了破解難度。
- 金鑰管理:金鑰長度與複雜度直接影響加密安全性。較長的金鑰可有效抵禦頻率分析攻擊。
- 實務應用限制:在現代密碼學中,維吉尼亞密碼已不再被視為安全加密手段,主要用於教育與歷史研究。
未來發展趨勢
隨著計算能力的提升與密碼分析技術的進步,傳統的多字母替換密碼已無法滿足現代資安需求。然而,其設計理念仍對現代加密演算法具有參考價值,特別是在動態金鑰管理與複雜性設計方面。