LFSR 的串流加密 (Stream Cipher)
線性回饋移位暫存器 (LFSR, Linear Feedback Shift Register) 及其在串流加密 (Stream Cipher) 算法中，特別是像 MFRC522 的 48 位元應用上的說明。
什麼是 LFSR？
線性回饋移位暫存器 (LFSR) 是一種硬體實現簡單、能高效產生偽隨機序列 (Pseudo-Random Sequence) 的數位電路。它是串流加密算法中最基礎、也是最重要的組成部分。
1. 核心結構
一個 LFSR 由兩部分組成：
移位暫存器 (Shift Register)： 一系列串聯的記憶單元（例如 D 觸發器），每一單元儲存一位元 (bit) 數據。在每個時鐘週期，數據會向一端移動一位。48 位元的 LFSR 就包含 48 個這樣的記憶單元。
線性回饋函數 (Linear Feedback Function)： 這是一個簡單的電路，它從暫存器的特定位置（稱為抽頭, Taps）取出位元，然後將這些位元進行異或 (XOR) 運算，將運算結果作為新的輸入位元送回暫存器的開頭。
2. 運作原理
初始狀態 (種子, Seed)： LFSR 從一個初始的非零狀態（稱為種子）開始，這個種子通常就是加密密鑰本身，或由密鑰派生而來。
時鐘週期： 每經過一個時鐘週期，發生兩件事：
暫存器中所有的位元向一端（通常是右邊）移動一位。
回饋函數計算出新的輸入位元，填補到騰空的最高位。
輸出： 暫存器中特定位置的位元（通常是最低位）被輸出，形成 密鑰串流 (Keystream)。
3. 48 位元 LFSR 在 CRYPTO1 中的角色
在 MIFARE Classic 和 MFRC522 所用的 CRYPTO1 算法中，48 位元 LFSR 扮演著核心狀態機的角色：
狀態： LFSR 的 48 個位元就是加密算法的內部狀態。
密鑰： 48 位元的 CRYPTO1 密鑰用於在認證階段初始化或更新 LFSR 的狀態。
密鑰串流生成： 在數據傳輸階段，LFSR 根據其內部狀態和特定的非線性過濾函數（這是 CRYPTO1 的專有部分）輸出密鑰串流。
🔑 LFSR 的串流加密 (Stream Cipher) 原理
串流加密的理念是，將明文數據的每一個位元（或每一個位元組）與一個等長的密鑰流位元（或位元組）進行 XOR 運算，從而產生密文。
加密與解密
串流加密最大的優點是加解密過程是完全對稱且相同的：
加密： $C = M \oplus K$
解密： $M = C \oplus K$
因為 $K \oplus K = 0$，所以 $(M \oplus K) \oplus K = M \oplus (K \oplus K) = M \oplus 0 = M$。
串流加密的安全性依賴於：
密鑰串流的週期長度：
一個 $n$ 級（位元）的 LFSR，如果其回饋函數（抽頭）選擇得當（即使用本原多項式），它可以產生長度為 $2^n - 1$ 的最大週期序列（稱為 m 序列）。
48 位元 LFSR 理論上最大週期可達 $2^{48} - 1$，這是一個極大的數字。週期越長，序列重複的可能性越小，安全性越高。
密鑰串流的隨機性：
雖然 LFSR 產生的序列是確定性的（只要知道初始種子和回饋函數就能重現），但它們在統計學上必須具有良好的偽隨機性，才能抵抗各種攻擊。
串流加密在 CRYPTO1 中的安全性挑戰
雖然 48 位元的 LFSR 週期很長，但 CRYPTO1 的安全性缺陷在於其線性特性：
線性分析： 由於 LFSR 本身是線性的，如果只是簡單地使用 LFSR 輸出進行加密，攻擊者很容易通過分析明文和密文的少量數據來還原 LFSR 的內部狀態，進而推導出整個密鑰。
CRYPTO1 的加強： 為了克服 LFSR 的線性弱點，CRYPTO1 在 LFSR 輸出前增加了非線性過濾函數 (Non-linear Filter)。然而，正如前面所說，這個專有的非線性函數最終也被逆向工程破解，導致整個 CRYPTO1 算法的密鑰在實際應用中可以被快速還原。
LFSR（線性回饋移位暫存器）是串流加密的核心，尤其在密碼學領域中，48 位元是一個特定的長度，例如在舊版的 RFID 協議（如 CRYPTO1）中出現。
由於 LFSR 的運作是位元級別 (bit-level) 的，並且需要指定抽頭 (Taps) 才能運行，這使得它很適合用來進行計算機科學原理的演示。
這個範例將建立一個 Tkinter 應用程式來模擬和視覺化一個 48 位元的 LFSR 的運行。
🚨 LFSR 核心原理提醒
位元長度 (N)： 48 位元。
抽頭 (Taps)： 決定了哪些位元被 XOR 運算後回饋到暫存器的開頭。抽頭的選擇決定了序列的週期。這裡我們使用一個產生最大週期 ($2^{48}-1$) 的本原多項式所對應的抽頭組合作為示範。
操作： 移位（右移）和 XOR 回饋。
💻 Python 程式碼 (48 位元 LFSR 模擬器)
import tkinter as tk
from tkinter import messagebox
import time
import random
# --- LFSR 核心邏輯 ---
class LFSR48:
# 48 位元 LFSR 的抽頭 (Taps)，基於本原多項式 x^48 + x^7 + x^4 + x^2 + 1
# 抽頭位置 (從 LSB (最右邊) 開始算，第 1 位元是 0，第 48 位元是 47)
# 我們需要的位置是 47 (最高位), 6, 3, 1, 0
# 這裡我們使用 48 (輸出位), 7, 4, 2 作為回饋位元，這是一種常見的表示法。
TAPS = [47, 6, 3, 1]
LENGTH = 48
def __init__(self, seed=None):
"""初始化 LFSR 狀態。"""
self.state = 0 # 使用整數來儲存 48 位元 LFSR 的狀態
self.output_bit = 0
self.initial_seed = 0
self.set_seed(seed)
self.count = 0
def set_seed(self, seed_val):
"""設置 LFSR 的初始狀態 (種子)。"""
if seed_val is None:
# 如果沒有提供種子，則使用隨機非零值
seed_val = random.getrandbits(self.LENGTH)
# 確保種子非零 (LFSR 狀態不能是全零，否則會鎖死)
if seed_val == 0:
seed_val = 1
self.state = seed_val & ((1 << self.LENGTH) - 1) # 確保只取 48 位元
self.initial_seed = self.state
self.count = 0
def step(self):
"""執行 LFSR 的單一步驟：計算回饋位元，移位，更新狀態。"""
# 1. 計算回饋位元 (Feedback Bit)
# 這是所有抽頭位置的位元進行 XOR 運算後的結果
feedback_bit = 0
for tap in self.TAPS:
# 提取 tap 位置的位元，並與 feedback_bit 進行 XOR
# (self.state >> tap) & 1 提取第 tap 位元的值
bit_at_tap = (self.state >> tap) & 1
feedback_bit ^= bit_at_tap
# 2. 獲取輸出位元 (Output Bit)
# 通常是最低位 (LSB)
self.output_bit = self.state & 1
# 3. 移位 (Shift)
# 將狀態右移一位
self.state >>= 1
# 4. 回饋 (Feedback)
# 將回饋位元 (feedback_bit) 放入最高位 (MSB，第 47 位)
if feedback_bit == 1:
self.state |= (1 << (self.LENGTH - 1))
self.count += 1
return self.output_bit
def get_state_binary(self):
"""以 48 位元的二進制字串形式返回當前狀態。"""
# 使用 f-string 格式化，將整數轉換為 48 位元的二進制字串
return f'{self.state:048b}'
def get_keystream_output(self, steps):
"""連續執行多個步驟，並返回密鑰串流。"""
output = ""
original_state = self.state
for _ in range(steps):
output += str(self.step())
# 為了不影響視覺化，這裡我們將狀態恢復到執行前 (實際應用中不這樣做)
self.state = original_state
return output
# --- Tkinter GUI 界面 ---
class LFSRApp:
def __init__(self, master):
self.master = master
master.title("48-bit LFSR 模擬與視覺化")
self.lfsr = LFSR48()
self.step_delay = 0.05 # 視覺化延遲（秒）
self.setup_ui()
self.update_display() # 初始化顯示
def setup_ui(self):
# --- 狀態顯示區 ---
tk.Label(self.master, text="LFSR 狀態 (48 位元):", font=('Arial', 10, 'bold')).grid(row=0, column=0, columnspan=2, pady=5)
self.state_label = tk.Label(self.master, text="0" * self.lfsr.LENGTH, font=('Consolas', 10), bg='lightgray', relief='sunken', padx=5, pady=5)
self.state_label.grid(row=1, column=0, columnspan=2, padx=10, pady=5)
tk.Label(self.master, text=f"抽頭 (Taps): {self.lfsr.TAPS}", fg='blue').grid(row=2, column=0, columnspan=2, pady=2)
# --- 輸出與計數 ---
self.output_label = tk.Label(self.master, text="輸出位元 (Output Bit): 0", font=('Arial', 10))
self.output_label.grid(row=3, column=0, columnspan=2, pady=2)
self.count_label = tk.Label(self.master, text="步驟計數 (Step Count): 0", font=('Arial', 10))
self.count_label.grid(row=4, column=0, columnspan=2, pady=2)
# --- 控制按鈕 ---
control_frame = tk.Frame(self.master)
control_frame.grid(row=5, column=0, columnspan=2, pady=10)
tk.Button(control_frame, text="執行單一步驟", command=self.step_and_visualize, bg='#90EE90').pack(side=tk.LEFT, padx=5)
tk.Button(control_frame, text="連續執行 10 步", command=lambda: self.run_steps(10), bg='#ADD8E6').pack(side=tk.LEFT, padx=5)
tk.Button(control_frame, text="重設 (隨機種子)", command=self.reset_lfsr, bg='#FFB6C1').pack(side=tk.LEFT, padx=5)
# --- 密鑰串流輸出區 ---
tk.Label(self.master, text="密鑰串流輸出 (Keystream):", font=('Arial', 10, 'bold')).grid(row=6, column=0, columnspan=2, pady=5)
self.output_stream_text = tk.Text(self.master, height=5, width=60)
self.output_stream_text.grid(row=7, column=0, columnspan=2, padx=10, pady=5)
def update_display(self, highlight_pos=None, new_bit=None):
"""更新 Tkinter 界面上的 LFSR 狀態顯示。"""
state_str = self.lfsr.get_state_binary()
# 創建帶有顏色標記的狀態字串
display_text = ""
for i, bit in enumerate(state_str):
# 標記抽頭位置 (Taps)
if i in [self.lfsr.LENGTH - 1 - t for t in self.lfsr.TAPS]: # 將抽頭位置轉換為字串索引
display_text += f"[{bit}]"
else:
display_text += bit
display_text += " "
self.state_label.config(text=display_text.strip())
self.output_label.config(text=f"輸出位元 (Output Bit): {self.lfsr.output_bit}")
self.count_label.config(text=f"步驟計數 (Step Count): {self.lfsr.count}")
# 標記輸出位元
self.output_stream_text.insert(tk.END, str(self.lfsr.output_bit))
self.output_stream_text.see(tk.END) # 自動捲動到最底部
self.master.update_idletasks()
def step_and_visualize(self):
"""執行單一步驟並更新視覺化。"""
# 1. 執行 LFSR 步驟
self.lfsr.step()
# 2. 更新顯示
self.update_display()
# 限制 Keystream 顯示長度
if len(self.output_stream_text.get("1.0", tk.END)) > 500:
self.output_stream_text.delete("1.0", "2.0") # 刪除第一行，保持顯示性能
def run_steps(self, num_steps):
"""連續執行多個步驟並顯示動畫效果。"""
self.master.config(cursor="wait")
self.master.update()
for _ in range(num_steps):
self.step_and_visualize()
time.sleep(self.step_delay) # 暫停以觀察移位
self.master.config(cursor="")
def reset_lfsr(self):
"""重設 LFSR 到一個新的隨機種子。"""
self.lfsr.set_seed(None)
self.output_stream_text.delete("1.0", tk.END)
self.update_display()
messagebox.showinfo("重設", f"LFSR 已重設。新的初始狀態：{self.lfsr.get_state_binary()}")
if __name__ == "__main__":
root = tk.Tk()
app = LFSRApp(root)
root.mainloop()
沒有留言:
張貼留言