維吉尼亞密碼雖是經典的多字母替換加密法，但其安全性並非牢不可破。本文將探討三種破解維吉尼亞密碼的技術：字典攻擊、卡西斯基檢驗法和暴力破解。字典攻擊嘗試用字典檔中的詞彙作為金鑰解密；卡西斯基檢驗法分析密鑰中的重複序列，推匯出可能的金鑰長度；暴力破解則在已知或推測的金鑰長度下，嘗試所有可能的金鑰組合。這些方法各有優劣，適用於不同的場景，理解其原理和實作方式有助於提升密碼分析能力。
破解維吉尼亞密碼的技術深度解析
字典攻擊的技術原理與實作
維吉尼亞密碼（Vigenère Cipher）是一種歷史悠久的多字母替換加密技術，但其加密強度並非無懈可擊。字典攻擊（Dictionary Attack）是一種破解維吉尼亞密碼的有效方法，其核心思想是利用預先準備的字典檔對可能的金鑰進行暴力破解。
字典攻擊的實作程式碼解析
def hackVigenereDictionary(ciphertext, dictionaryFile):
with open(dictionaryFile, 'r') as file:
dictionary = file.readlines()
for word in dictionary:
word = word.strip()
decryptedText = decryptVigenere(ciphertext, word)
if isEnglish(decryptedText):
return word, decryptedText
return None, None
#### 程式碼解析：
此段程式碼實作了字典攻擊的核心邏輯。首先，它開啟指定的字典檔並讀取所有單詞。接著，它逐一使用這些單詞作為金鑰對密鑰進行解密。如果解密後的文字是有效的英文，則傳回該金鑰和解密結果。
### 卡西斯基檢驗法（Kasiski Examination）的技術深度解析
卡西斯基檢驗法是一種用於破解維吉尼亞密碼的密碼分析技術，其基本原理是透過尋找密鑰中重複的字母序列來推斷金鑰的長度。
#### 卡西斯基檢驗法的實作步驟
1. **尋找重複序列**：在密鑰中尋找重複出現的字母序列，並記錄它們之間的間距。
2. **計算間距的因數**：對每個間距進行因數分解，找出可能的金鑰長度。
3. **提取每N個字母**：根據推斷出的金鑰長度N，從密鑰中提取每N個字母，形成新的字串。
4. **頻率分析**：對這些字串進行頻率分析，以破解單字母替換密碼。
#### 卡西斯基檢驗法的實作程式碼解析
```python
def kasiskiExamination(ciphertext):
# 尋找重複序列及其間距
sequences = findRepeatedSequences(ciphertext)
spacings = calculateSpacings(sequences)
# 計算間距的因數
factors = getFactors(spacings)
# 移除重複的因數
uniqueFactors = removeDuplicates(factors)
return uniqueFactors
def getEveryNthLetters(ciphertext, n):
result = []
for i in range(n):
result.append(ciphertext[i::n])
return result
#### 程式碼解析：
此段程式碼實作了卡西斯基檢驗法的核心邏輯。首先，它尋找密鑰中的重複序列並計算間距。接著，它對這些間距進行因數分解，以找出可能的金鑰長度。最後，它根據推斷出的金鑰長度從密鑰中提取每N個字母。
### 暴力破解技術的深度解析
在獲得可能的金鑰長度後，可以透過暴力破解技術遍歷所有可能的金鑰組合，以找到正確的解密金鑰。
#### 暴力破解的實作程式碼解析
```python
def bruteForceVigenere(ciphertext, keyLength):
for key in generateAllKeys(keyLength):
decryptedText = decryptVigenere(ciphertext, key)
if isEnglish(decryptedText):
return key, decryptedText
return None, None
#### 程式碼解析：
此段程式碼實作了暴力破解的核心邏輯。它遍歷所有可能的金鑰組合，並使用每個金鑰對密鑰進行解密。如果解密後的文字是有效的英文，則傳回該金鑰和解密結果。
```python
# 維吉尼亞密碼破解完整程式碼
import re
from collections import Counter
def hackVigenereDictionary(ciphertext, dictionaryFile):
# 字典攻擊實作
with open(dictionaryFile, 'r') as file:
dictionary = file.readlines()
for word in dictionary:
word = word.strip()
decryptedText = decryptVigenere(ciphertext, word)
if isEnglish(decryptedText):
return word, decryptedText
return None, None
def kasiskiExamination(ciphertext):
# 卡西斯基檢驗法實作
sequences = findRepeatedSequences(ciphertext)
spacings = calculateSpacings(sequences)
factors = getFactors(spacings)
uniqueFactors = removeDuplicates(factors)
return uniqueFactors
def bruteForceVigenere(ciphertext, keyLength):
# 暴力破解實作
for key in generateAllKeys(keyLength):
decryptedText = decryptVigenere(ciphertext, key)
if isEnglish(decryptedText):
return key, decryptedText
return None, None
# 其他輔助函式實作
def findRepeatedSequences(ciphertext):
# 尋找重複序列
sequences = []
for i in range(len(ciphertext) - 3):
seq = ciphertext[i:i+3]
if ciphertext.count(seq) > 1:
sequences.append(seq)
return sequences
def calculateSpacings(sequences):
# 計算間距
spacings = []
for seq in sequences:
indices = [i for i, x in enumerate(ciphertext) if ciphertext.startswith(seq, i)]
spacing = indices[1] - indices[0]
spacings.append(spacing)
return spacings
def getFactors(spacings):
# 取得因數
factors = []
for spacing in spacings:
factors.extend([i for i in range(1, spacing + 1) if spacing % i == 0])
return factors
def removeDuplicates(factors):
# 移除重複因數
return list(set(factors))
def generateAllKeys(keyLength):
# 生成所有可能的金鑰
keys = []
for i in range(26 ** keyLength):
key = ''
for j in range(keyLength):
key += chr((i // (26 ** j)) % 26 + 65)
keys.append(key)
return keys
def decryptVigenere(ciphertext, key):
# 維吉尼亞密碼解密實作
plaintext = ''
keyIndex = 0
for char in ciphertext:
if char.isalpha():
shift = ord(key[keyIndex % len(key)].upper()) - 65
if char.isupper():
plaintext += chr((ord(char) - 65 - shift) % 26 + 65)
else:
plaintext += chr((ord(char) - 97 - shift) % 26 + 97)
keyIndex += 1
else:
plaintext += char
return plaintext
def isEnglish(text):
# 判斷是否為英文文字
commonWords = ['the', 'be', 'to', 'of', 'and', 'a', 'in', 'that', 'have', 'I']
text = text.lower()
for word in commonWords:
if word in text:
return True
return False
#### 程式碼解析：
此附錄提供了維吉尼亞密碼破解的完整程式碼實作，包括字典攻擊、卡西斯基檢驗法和暴力破解等技術。這些程式碼片段展示瞭如何透過不同的密碼分析技術來破解維吉尼亞密碼。
## 第21章至第24章內容整理與分析
本章節涵蓋了密碼學中的幾個重要主題，包括`itertools.product()`函式、斷點陳述式（`break` statement）、一次性密碼（One-Time Pad Cipher）、尋找質數（Finding Prime Numbers）以及公開金鑰密碼學（Public Key Cryptography）和RSA密碼（RSA Cipher）。
### itertools.product() 函式與斷點陳述式
`itertools.product()`是一個用於計算多個迭代器之間的笛卡爾積的函式，在密碼學中常用於生成所有可能的密碼組合。斷點陳述式（`break`）則是用於中斷迴圈的執行。
#### 程式碼範例：使用itertools.product()生成所有可能的二位數密碼
```python
import itertools
# 定義可能的數字
numbers = '0123456789'
# 生成所有可能的二位數密碼
for password in itertools.product(numbers, repeat=2):
print(''.join(password))
內容解密：
import itertools：匯入itertools模組，用於使用product()函式。numbers = '0123456789'：定義一個包含所有數字的字串。itertools.product(numbers, repeat=2)：生成所有可能的二位數密碼組合。''.join(password)：將生成的元組（tuple）轉換為字串。
一次性密碼（One-Time Pad Cipher）
一次性密碼是一種理論上不可破解的加密技術，條件是金鑰必須是隨機的、與明文等長、且永不重複使用。
為何一次性密碼不可破解
- 金鑰的隨機性確保了密鑰的不可預測性。
- 金鑰與明文等長避免了金鑰重複使用的問題。
- 永不重複使用金鑰確保了即使攻擊者獲得了部分明文，也無法推斷出金鑰或其它明文。
尋找質數
質數是指除了1和自身以外沒有其它正因數的正整數。尋找質數在密碼學中有重要應用，特別是在公開金鑰密碼學中。
篩法（Sieve of Eratosthenes）
篩法是一種用於找出一定範圍內所有質數的演算法。
def prime_sieve(n):
sieve = [True] * (n + 1)
sieve[0:2] = [False, False] # 0和1不是質數
for current_prime in range(2, int(n**0.5) + 1):
if sieve[current_prime]:
for multiple in range(current_prime*2, n + 1, current_prime):
sieve[multiple] = False
return [num for num, is_prime in enumerate(sieve) if is_prime]
print(prime_sieve(100))
內容解密：
sieve = [True] * (n + 1)：初始化一個布林列表，假設所有數字都是質數。sieve[0:2] = [False, False]：0和1不是質數。- 迴圈遍歷至$\sqrt{n}$，標記非質數。
- 傳回所有質數的列表。
公開金鑰密碼學與RSA
公開金鑰密碼學使用一對金鑰：公鑰用於加密，私鑰用於解密。RSA是一種廣泛使用的公開金鑰密碼學演算法。
RSA的安全性
RSA的安全性根據大數分解的難度。攻擊者需要分解一個很大的合數（兩個大質數的乘積）才能獲得私鑰。
中間人攻擊（Man-In-The-Middle Attack）
中間人攻擊是指攻擊者在通訊雙方之間攔截並篡改資訊，以達到竊取資訊或破壞通訊的目的。
密碼學基礎工具製作
本章涵蓋主題：
- 什麼是密碼學？
- 編碼與密碼
- 凱撒密碼
- 密碼輪
- 聖西爾投影片
- 使用紙和筆進行密碼學操作
- “雙重強度”加密
什麼是密碼學？
密碼學是一門研究如何安全地傳輸資訊的學科，主要涉及加密（encryption）和解密（decryption）技術，以確保資訊在傳輸過程中的機密性和完整性。
編碼與密碼
在深入密碼學的世界之前，我們需要了解兩個重要的概念：編碼（codes） 和 密碼（ciphers）。編碼是指用一種特定的方式來表示資訊，例如摩斯密碼；而密碼則是一種透過改變資訊的表現形式來隱藏其真實含義的方法，例如凱撒密碼。
凱撒密碼
凱撒密碼是一種簡單的替換式密碼，透過將明文中的每個字母按照固定的偏移量進行替換來實作加密。例如，當偏移量為3時，明文中的"A"會被替換成"D"，“B"會被替換成"E”，依此類別推。
程式碼實作凱撒密碼
def caesar_cipher(text, shift):
result = ""
for char in text:
if char.isalpha():
ascii_offset = ord('A') if char.isupper() else ord('a')
result += chr((ord(char) - ascii_offset + shift) % 26 + ascii_offset)
else:
result += char
return result
# 示例使用
text = "Hello, World!"
shift = 3
encrypted = caesar_cipher(text, shift)
print(f"加密後：{encrypted}")
#### 內容解密：
1. `caesar_cipher`函式接受兩個引數：`text`（待加密的文字）和`shift`（偏移量）。
2. 迴圈遍歷每個字元，檢查是否為字母。
3. 如果是字母，根據大小寫計算新的字元，並加入結果字串中。
4. 非字母字元保持不變。
5. 傳回加密後的字串。
### 密碼輪與聖西爾投影片
密碼輪和聖西爾投影片是兩種用於實作替換式密碼的工具。密碼輪通常由兩個同心圓盤組成，分別標有字母或數字，透過旋轉圓盤來實作加密和解密。聖西爾投影片則是一種更簡單的工具，透過在兩個條狀物上標記字母，並相對滑動來實作加密和解密。
### “雙重強度”加密
“雙重強度”加密是指對明文進行兩次加密操作，以增加破解的難度。例如，先使用凱撒密碼進行第一次加密，然後再使用另一種加密方法進行第二次加密。
## 密碼學簡介
密碼學是一門研究如何使用秘密程式碼的科學。密碼學家是指使用和研究這些秘密程式碼的人。隨著科技的發展，密碼學在現代社會中扮演著越來越重要的角色，從間諜、士兵到網路購物者，任何需要與他人分享秘密的人都依賴密碼學來保護他們的秘密。
### 密碼與加密法
在早期的電報系統中，為了將英文字母轉換成電脈衝，需要一套編碼系統（或稱密碼）來進行轉換。這套系統被稱為摩爾斯密碼，由Samuel Morse和Alfred Vail開發。摩爾斯密碼是一種公開且易於理解的編碼系統，任何人都可以使用它來解碼已編碼的訊息。
### 製作紙質加密輪
在學習如何使用電腦程式進行加密和解密之前，讓我們先了解如何使用簡單的紙質工具來實作這些功能。我們將學習一種稱為凱撒密碼的加密法，這種加密法在兩千年前由朱利葉斯·凱撒使用。要使用凱撒密碼將明文轉換成密鑰，我們需要製作一個稱為加密輪（或加密盤）的工具。你可以影印書中的加密輪，或從http://invpy.com/cipherwheel列印一個。
#### 加密輪的使用步驟：
1. 將內圓和外圓剪下，並將它們疊在一起。
2. 使用圖釘或釘書針將兩個圓固定在中心點，使它們可以旋轉。
3. 旋轉內圓以設定金鑰，然後你就可以使用凱撒密碼進行加密和解密。
### 虛擬加密輪
如果你沒有剪刀和影印機，也可以使用線上虛擬加密輪。存取http://invpy.com/cipherwheel即可使用軟體版本的加密輪。點選滑鼠並移動遊標來旋轉輪盤，直到你想要的金鑰就位。
### 程式碼範例：凱撒密碼實作
```python
def caesar_cipher(text, shift, direction):
result = ""
for char in text:
if char.isalpha():
ascii_offset = 65 if char.isupper() else 97
result += chr((ord(char) - ascii_offset + shift * direction) % 26 + ascii_offset)
else:
result += char
return result
def encrypt(text, shift):
return caesar_cipher(text, shift, 1)
def decrypt(text, shift):
return caesar_cipher(text, shift, -1)
#### 內容解密：
# 上述程式碼實作了凱撒密碼的加密和解密功能。
# `caesar_cipher` 函式根據提供的 `shift` 和 `direction` 對輸入的 `text` 進行轉換。
# `encrypt` 和 `decrypt` 函式分別呼叫 `caesar_cipher` 進行加密和解密。
# 使用 `ord` 和 `chr` 函式來取得和設定字元的 ASCII 值，以實作字母的位移。
# 對於非字母字元，保持原樣不變。
# 範例用法：
text = "Hello, World!"
shift = 3
encrypted = encrypt(text, shift)
print(f"Encrypted: {encrypted}")
decrypted = decrypt(encrypted, shift)
print(f"Decrypted: {decrypted}")