Java软件中LFSR线性反馈移位寄存器的实际应用从随机数生成到硬件模拟解密完整教程
我最近花了一段时间研究LFSR，说实话，这东西初看挺让人头大，但当你真正理解它的运作机制后，会发现它在密码学、通信、游戏开发等领域都有很巧妙的应用。今天我就来把LFSR从理论到Java实现，再到实际的硬件模拟解密，完整给你讲清楚。
什么是LFSR？先从最简单的例子说起
想象你有4个灯泡排成一排，每个灯泡要么是亮（1）要么是灭（0）。现在我们要按照一套规则来更新这些灯泡的状态：
第1步：记录最右边灯泡的状态
第2步：根据某些灯泡的位置做异或（XOR）运算
第3步：把所有灯泡往右移动一位
第4步：把第一步记录的状态放到最左边
这就是LFSR的核心思想——线性反馈移位寄存器。它是一个寄存器（一组存储位），每次时钟脉冲到来时，数据向右移动一位，同时根据”抽头位置”（taps）计算新的输入位。
用代码直观理解
/**
* LFSR基础实现 - 用一个简单的4位寄存器演示
*/
public class LFSRBasic {
private int state; // 寄存器状态
private int width; // 寄存器宽度
private int[] taps; // 抽头位置（反馈点）
/**
* 初始化LFSR
* @param width 寄存器宽度（位）
* @param taps 抽头位置数组，例如 [4, 3, 3, 2] 表示多项式 x^4 + x^3 + x^2 + 1
*/
public LFSRBasic(int width, int[] taps) {
this.width = width;
this.taps = taps;
// 初始状态设为非零（全零会导致LFSR永远输出零）
this.state = 1;
}
/**
* 生成下一个输出位并更新状态
* @return 输出的位（0或1）
*/
public int nextBit() {
int feedback = 0;
// 根据抽头位置计算反馈位
for (int tap : taps) {
// 取寄存器第tap位（从右往左数，0-indexed）
int bit = (state >> tap) & 1;
feedback ^= bit; // XOR累积
}
// 保存输出位（最右边的位）
int output = state & 1;
// 右移一位
state >>>= 1;
// 将反馈位放到最左边
state |= (feedback << (width - 1));
return output;
}
/**
* 获取当前状态（二进制表示）
*/
public String getStateString() {
StringBuilder sb = new StringBuilder();
for (int i = width - 1; i >= 0; i--) {
sb.append((state >> i) & 1);
}
return sb.toString();
}
public static void main(String[] args) {
// 创建一个4位LFSR，抽头为[3, 2]
// 对应的多项式为 x^4 + x^3 + x^2 + 1（注意抽头是从高位算的）
LFSRBasic lfsr = new LFSRBasic(4, new int[]{3, 2});
System.out.println("LFSR输出序列：");
for (int i = 0; i < 16; i++) {
int bit = lfsr.nextBit();
System.out.print(bit);
if (i % 4 == 3) System.out.print(" ");
}
System.out.println();
}
}
运行上面的代码，你会看到类似这样的输出：
LFSR输出序列：
0000 1110 0111 1001 ...
这个序列看起来有点随机，对吧？这就是LFSR的魅力——用简单的规则产生看似随机的序列。
为什么LFSR很重要？它的数学原理
光看代码可能还是不太理解为什么这样设计。让我用数学的方式解释清楚。
多项式表示法
LFSR可以用一个特征多项式来表示：
\[P(x) = x^n + c_{n-1}x^{n-1} + c_{n-2}x^{n-2} + \cdots + c_1x + 1\]
其中系数 \(c_i\) 要么是0要么是1。如果 \(c_i = 1\)，表示第i位是抽头位置。
例如，多项式 \(x^4 + x^3 + 1\) 对应的抽头是 [3, 0]，状态转移如下：
初始状态: 0001
↓
输出: 1, 状态变为: 1000 (反馈位=0, 右移, 输入0)
↓
输出: 0, 状态变为: 0100
↓
输出: 0, 状态变为: 0010
↓
输出: 0, 状态变为: 1001 (反馈位=1⊕1=0... 等等，让我重新计算)
等一下，我刚才的计算有误，让我重新来：
对于多项式 \(x^4 + x^3 + 1\)，抽头位置是第3位和第0位：
状态: 0001 (初始)
第1步: 输出0, 反馈=bit3⊕bit0 = 0⊕1 = 1, 新状态=1000
第2步: 输出0, 反馈=bit3⊕bit0 = 0⊕0 = 0, 新状态=0100
第3步: 输出0, 反馈=bit3⊕bit0 = 0⊕0 = 0, 新状态=0010
第4步: 输出0, 反馈=bit3⊕bit0 = 0⊕0 = 0, 新状态=0001
等等，这样周期太短了。让我用一个更标准的本原多项式：
标准4位LFSR使用多项式：\(x^4 + x^3 + 1\)
/**
* 标准LFSR实现，使用本原多项式
*/
public class LFSRStandard {
private int state;
private int width;
private int mask; // 抽头掩码
public LFSRStandard(int width, int mask) {
this.width = width;
this.mask = mask;
this.state = 1; // 初始状态
}
public int nextBit() {
// 计算反馈位：将当前状态与抽头掩码做异或，然后取最低位
int feedback = Integer.bitCount(state & mask) % 2;
// 保存输出
int output = state & 1;
// 右移一位
state >>>= 1;
// 将反馈位放到最高位
state |= (feedback << (width - 1));
return output;
}
/**
* 生成指定长度的伪随机数
*/
public int nextInt(int bits) {
int result = 0;
for (int i = 0; i < bits; i++) {
result = (result << 1) | nextBit();
}
return result;
}
public static void main(String[] args) {
// 4位LFSR，本原多项式 x^4 + x^3 + 1
// 掩码二进制: 1101 (第3位和第0位)
LFSRStandard lfsr = new LFSRStandard(4, 0b1101);
System.out.println("完整周期（16个状态）：");
for (int i = 0; i < 16; i++) {
int bit = lfsr.nextBit();
System.out.printf("%d -> %s%n", bit, lfsr.getStateString());
}
}
public String getStateString() {
StringBuilder sb = new StringBuilder();
for (int i = width - 1; i >= 0; i--) {
sb.append((state >> i) & 1);
}
return sb.toString();
}
}
实际应用一：伪随机数生成
LFSR最常见的用途之一就是生成伪随机数。虽然它生成的序列是确定性的（给定初始状态，输出序列完全确定），但在很多场景下已经足够用了。
Java中的Random与LFSR
Java自带的 java.util.Random 使用的是线性同余生成器（LCG），而LFSR在某些情况下比LCG有更好的统计特性。让我给你展示如何构建一个基于LFSR的随机数生成器：
import java.util.concurrent.ThreadLocalRandom;
/**
* LFSR伪随机数生成器
* 使用Galois LFSR结构，提供更好的性能和均匀性
*/
public class LFSRRandom {
private long state;
private final int width;
private final long mask;
private final long initMask;
/**
* 构造Galois LFSR随机数生成器
* @param width 寄存器宽度（建议32或64）
* @param taps 抽头多项式（本原多项式）
*/
public LFSRRandom(int width, long taps) {
this.width = width;
this.mask = taps;
this.initMask = taps | 1L; // 确保最低位为1
// 用当前时间种子
this.state = System.nanoTime() ^ ThreadLocalRandom.current().nextLong();
this.state |= 1L; // 确保非零
}
/**
* 生成下一个伪随机整数
*/
public int nextInt() {
// Galois LFSR的高效实现
for (int i = 0; i < 32; i++) {
// 检查最低位
boolean lsb = (state & 1L) == 1L;
// 右移
state >>>= 1;
// 如果最低位是1，异或抽头多项式
if (lsb) {
state ^= mask;
}
}
return (int)(state & 0xFFFFFFFFL);
}
/**
* 生成[0, bound)范围内的随机整数
*/
public int nextInt(int bound) {
if (bound <= 0) throw new IllegalArgumentException("bound must be positive");
int bits, val;
do {
bits = (width <= 32) ? nextInt() : nextInt();
val = bits % bound;
} while (bits - val + (bound - 1) < 0);
return val;
}
/**
* 生成[0, 1)之间的随机双精度浮点数
*/
public double nextDouble() {
return nextInt() / (double)Integer.MAX_VALUE;
}
/**
* 测试随机数的均匀性
*/
public void testDistribution(int count, int bucketCount) {
int[] buckets = new int[bucketCount];
for (int i = 0; i < count; i++) {
int val = nextInt(bucketCount);
buckets[val]++;
}
double expected = (double)count / bucketCount;
System.out.println("分布测试（" + count + "次）：");
for (int i = 0; i < bucketCount; i++) {
double percent = (double)buckets[i] / count * 100;
double deviation = Math.abs(percent - (100.0 / bucketCount));
System.out.printf(" 桶%d: %5d (%6.2f%%) 偏差: %5.2f%%%n",
i, buckets[i], percent, deviation);
}
}
public static void main(String[] args) {
// 使用32位LFSR，本原多项式 x^32 + x^22 + x^2 + x + 1
// 这是标准的Galois LFSR抽头
LFSRRandom lfsr = new LFSRRandom(32, 0x00000405L);
// 测试
lfsr.testDistribution(10000, 10);
System.out.println("\n生成的随机数样本：");
for (int i = 0; i < 10; i++) {
System.out.println(" " + lfsr.nextInt(1000));
}
}
}
与Java内置Random的对比
/**
* 性能与质量对比测试
*/
public class LFSRRandomBenchmark {
public static void main(String[] args) {
int iterations = 1_000_000;
// 测试LFSR
long start = System.nanoTime();
LFSRRandom lfsr = new LFSRRandom(32, 0x00000405L);
for (int i = 0; i < iterations; i++) {
lfsr.nextInt();
}
long lfsrTime = System.nanoTime() - start;
// 测试Java Random
start = System.nanoTime();
java.util.Random random = new java.util.Random();
for (int i = 0; i < iterations; i++) {
random.nextInt();
}
long randomTime = System.nanoTime() - start;
System.out.printf("LFSR耗时: %d ms%n", lfsrTime / 1_000_000);
System.out.printf("Java Random耗时: %d ms%n", randomTime / 1_000_000);
System.out.printf("LFSR快%.2f倍%n", (double)randomTime / lfsrTime);
}
}
实际应用二：硬件模拟
LFSR在硬件设计中非常常见，因为它的实现非常简单——只需要几个异或门和一个寄存器。让我们模拟一个简单的硬件LFSR模块：
FPGA风格的LFSR模拟
/**
* 硬件风格的LFSR模块
* 模拟FPGA/CPLD中的LFSR设计模式
*/
public class HardwareLFSR {
// 寄存器（模拟硬件寄存器）
private byte[] register;
private int width;
// 抽头配置（模拟硬件连线）
private final boolean[] taps;
// 时钟边沿检测
private boolean previousClock = false;
/**
* 构造硬件LFSR
* @param width 寄存器宽度
* @param tapPositions 抽头位置（高位索引）
*/
public HardwareLFSR(int width, int... tapPositions) {
this.width = width;
this.register = new byte[width];
this.taps = new boolean[width];
// 设置抽头
for (int pos : tapPositions) {
if (pos >= 0 && pos < width) {
this.taps[pos] = true;
}
}
// 确保最高位始终有抽头（标准做法）
this.taps[width - 1] = true;
// 初始状态
reset();
}
/**
* 硬件复位
*/
public void reset() {
java.util.Arrays.fill(register, (byte)0);
register[width - 1] = 1; // 只设置最高位为1
}
/**
* 时钟上升沿触发
* @return 输出的位
*/
public byte clockEdge() {
// 检测上升沿
boolean currentClock = true;
byte output = register[0]; // 输出最低位
// 计算反馈值（组合逻辑）
byte feedback = 0;
for (int i = 0; i < width; i++) {
if (taps[i]) {
feedback ^= register[i];
}
}
// 移位（时序逻辑）
System.arraycopy(register, 1, register, 0, width - 1);
register[width - 1] = feedback;
previousClock = currentClock;
return output;
}
/**
* 并行加载初始状态（模拟硬件的preload功能）
*/
public void preload(long seed) {
for (int i = 0; i < width; i++) {
register[i] = (byte)((seed >> i) & 1);
}
// 确保非零
if (getState() == 0) {
register[0] = 1;
}
}
public long getState() {
long state = 0;
for (int i = 0; i < width; i++) {
state |= ((long)register[i] << i);
}
return state;
}
public String toBinaryString() {
StringBuilder sb = new StringBuilder();
for (int i = width - 1; i >= 0; i--) {
sb.append(register[i]);
if (i % 4 == 0 && i > 0) sb.append(" ");
}
return sb.toString();
}
public static void main(String[] args) {
// 模拟一个8位LFSR，使用多项式 x^8 + x^6 + x^5 + x^4 + 1
// 这是GPS和CDMA系统中常用的抽头
HardwareLFSR lfsr = new HardwareLFSR(8, 6, 5, 4);
System.out.println("硬件LFSR状态转换：");
System.out.println("初始状态: " + lfsr.toBinaryString());
for (int i = 0; i < 20; i++) {
byte out = lfsr.clockEdge();
System.out.printf("时钟%d: 输出=%d, 状态=%s%n",
i, out, lfsr.toBinaryString());
}
}
}
Verilog风格的LFSR实现
如果你熟悉硬件描述语言，下面的代码会让你感到非常亲切：
/**
* Verilog风格LFSR - 完全模拟硬件行为
*
* Verilog代码对应：
*
* module lfsr #(parameter WIDTH=8, parameter TAPS=8'h9D) (
* input wire clk,
* input wire reset,
* input wire [WIDTH-1:0] seed,
* input wire load,
* output reg out,
* output reg [WIDTH-1:0] state
* );
*
* always @(posedge clk) begin
* if (reset)
* state <= WIDTH'b1;
* else if (load)
* state <= seed;
* else begin
* out <= state[0];
* state <= {state[WIDTH-1:1],
* ^ (state & TAPS)};
* end
* end
*
* endmodule
*/
public class VerilogStyleLFSR {
private int state;
private final int width;
private final int tapMask;
private boolean load;
private boolean reset;
private int seed;
public VerilogStyleLFSR(int width, int tapMask) {
this.width = width;
this.tapMask = tapMask;
this.state = 1;
}
/**
* 模拟posedge clk边沿触发
*/
public int clockPosedge() {
int output;
if (reset) {
// 异步复位
state = 1;
output = 0;
} else if (load) {
// 并行加载种子
state = seed & ((1 << width) - 1);
output = state & 1;
} else {
// 正常LFSR操作
output = state & 1;
// 计算反馈：state & tapMask 的奇偶校验
int feedback = Integer.bitCount(state & tapMask) % 2;
// 移位并插入反馈
state = (state >>> 1) | (feedback << (width - 1));
}
return output;
}
/**
* 获取完整状态（用于调试/验证）
*/
public String stateBinary() {
StringBuilder sb = new StringBuilder();
for (int i = width - 1; i >= 0; i--) {
sb.append((state >> i) & 1);
}
return sb.toString();
}
public static void main(String[] args) {
// 32位LFSR，使用标准本原多项式 x^32 + x^22 + x^2 + x + 1
// 对应Verilog参数: TAPS = 32'h00400005
VerilogStyleLFSR lfsr = new VerilogStyleLFSR(32, 0x00400005);
System.out.println("32位LFSR状态序列：");
System.out.printf("初始: %s%n", lfsr.stateBinary());
for (int i = 0; i < 33; i++) {
int bit = lfsr.clockPosedge();
System.out.printf("时钟%d: out=%d, state=%s%n",
i, bit, lfsr.stateBinary());
}
}
}
实际应用三：解密与密码学攻击
这是最有趣的部分。LFSR因为结构简单、速度快，被广泛用于流密码中。但同时，它也有明显的弱点——线性性质使得它容易被攻击。
流密码中的LFSR
/**
* LFSR流密码加密/解密器
*
* 流密码原理：
* 1. 发送方和接收方使用相同的LFSR和初始状态（密钥）
* 2. LFSR生成伪随机密钥流
* 3. 密钥流与明文异或得到密文
*
* 解密时：
* 1. 使用相同的LFSR和初始状态生成密钥流
* 2. 密钥流与密文异或恢复明文
*/
public class LFSRCipher {
private int state;
private final int width;
private final int mask;
/**
* 初始化加密器
* @param width 寄存器宽度
* @param taps 抽头多项式
* @param key 初始密钥（作为种子）
*/
public LFSRCipher(int width, int taps, long key) {
this.width = width;
this.mask = taps;
this.state = (int)(key & ((1L << width) - 1));
if (this.state == 0) this.state = 1;
}
/**
* 生成下一个密钥位
*/
private int keyBit() {
int feedback = Integer.bitCount(state & mask) % 2;
int output = state & 1;
state = (state >>> 1) | (feedback << (width - 1));
return output;
}
/**
* 加密/解密消息（异或操作对称）
* @param input 输入字节数组
* @return 输出字节数组
*/
public byte[] encrypt(byte[] input) {
byte[] output = new byte[input.length];
for (int i = 0; i < input.length; i++) {
byte encryptedByte = 0;
for (int bit = 0; bit < 8; bit++) {
int keyBit = keyBit();
int dataBit = (input[i] >> bit) & 1;
encryptedByte |= ((byte)(dataBit ^ keyBit)) << bit;
}
output[i] = encryptedByte;
}
return output;
}
/**
* 将字节数组转换为十六进制字符串
*/
public static String toHex(byte[] data) {
StringBuilder sb = new StringBuilder();
for (byte b : data) {
sb.append(String.format("%02x", b));
}
return sb.toString();
}
public static void main(String[] args) {
// 使用一个简化的8位LFSR演示
// 多项式: x^8 + x^6 + x^5 + x^4 + 1 (GPS LFSR-G)
int width = 8;
int taps = 0b10111001; // x^8 + x^6 + x^5 + x^4 + 1
String message = "Hello, LFSR!";
long key = 0xAB; // 初始密钥
LFSRCipher cipher = new LFSRCipher(width, taps, key);
System.out.println("原始消息: " + message);
System.out.println("密钥: 0x" + String.format("%02X", key));
// 加密
byte[] encrypted = cipher.encrypt(message.getBytes());
System.out.println("加密后: " + toHex(encrypted));
// 解密（使用相同的密钥）
LFSRCipher decrypter = new LFSRCipher(width, taps, key);
byte[] decrypted = decrypter.encrypt(encrypted);
System.out.println("解密后: " + new String(decrypted));
}
}
攻击LFSR：已知明文攻击
现在，让我们来玩个游戏——假设你是一个密码分析师，截获了一段使用LFSR加密的密文，并且你知道部分内容（比如消息开头是”HTTP”或”PK”这样的文件头）。你能恢复密钥吗？
/**
* LFSR密码分析器 - 已知明文攻击
*
* 攻击原理：
* 1. 如果知道明文字节，可以通过密文异或得到密钥流
* 2. 使用Berlekamp-Massey算法从密钥流恢复LFSR抽头
* 3. 用恢复的LFSR和密钥流解密其余密文
*/
public class LFSRAnalyzer {
/**
* Berlekamp-Massey算法 - 核心密码分析工具
* 从已知序列恢复LFSR特征多项式
*
* @param sequence 已知序列（比特流）
* @param nBits 序列长度（建议至少2*寄存器宽度）
* @return 特征多项式系数（低位在前）
*/
public static int[] berlekampMassey(int[] sequence, int nBits) {
int[] C = new int[nBits + 1]; // 当前多项式
int[] B = new int[nBits + 1]; // 前一个多项式
C[0] = 1;
B[0] = 1;
int L = 0; // 当前LFSR长度
int m = 1; // 距离上次更新的步数
int b = 1; // 上次更新的偏差
for (int n = 0; n < nBits; n++) {
// 计算当前偏差
int d = sequence[n];
for (int i = 1; i <= L; i++) {
d ^= (C[i] & sequence[n - i]);
}
if (d == 0) {
m++;
} else if (2 * L <= n) {
// 需要增加LFSR长度
int[] T = C.clone();
// C(x) = C(x) - d/b * x^m * B(x)
// 在GF(2)中，减法就是异或，d/b = d*b (因为b只能是0或1)
for (int i = 0; i <= nBits - m; i++) {
if (B[i] == 1) {
C[i + m] ^= 1;
}
}
L = n + 1 - L;
B = T;
m = 1;
b = d;
} else {
// 不需要增加长度
int[] T = C.clone();
for (int i = 0; i <= nBits - m; i++) {
if (B[i] == 1) {
C[i + m] ^= 1;
}
}
m++;
b = d;
}
}
// 返回实际使用的多项式长度
int[] result = new int[L + 1];
System.arraycopy(C, 0, result, 0, L + 1);
return result;
}
/**
* 从序列中提取比特
*/
private static int[] extractBits(byte[] data, int startBit, int count) {
int[] bits = new int[count];
for (int i = 0; i < count; i++) {
int byteIndex = (startBit + i) / 8;
int bitIndex = 7 - (startBit + i) % 8;
bits[i] = (data[byteIndex] >> bitIndex) & 1;
}
return bits;
}
/**
* 攻击LFSR加密
* @param ciphertext 密文
* @param knownPlaintext 已知的明文部分
* @param lfsrWidth LFSR宽度估计（如果不知道可以试几个值）
* @return 恢复的密钥流
*/
public static byte[] attackLFSR(byte[] ciphertext, byte[] knownPlaintext, int lfsrWidth) {
// 步骤1：从已知明文和密文恢复密钥流
int keyStreamLength = knownPlaintext.length * 8;
int[] keyStream = new int[keyStreamLength];
for (int i = 0; i < keyStreamLength; i++) {
int plainBit = (knownPlaintext[i / 8] >> (7 - i % 8)) & 1;
int cipherBit = (ciphertext[i / 8] >> (7 - i % 8)) & 1;
keyStream[i] = plainBit ^ cipherBit;
}
// 步骤2：使用Berlekamp-Massey恢复LFSR特征多项式
int[] poly = berlekampMassey(keyStream, keyStreamLength);
// 步骤3：使用恢复的LFSR生成完整密钥流
int state = 1; // 初始状态需要尝试
byte[] recoveredKeyStream = new byte[ciphertext.length];
// 尝试所有可能的初始状态（小宽度时可以暴力破解）
for (int initState = 1; initState < (1 << lfsrWidth); initState++) {
int testState = initState;
boolean match = true;
// 验证恢复的LFSR是否能生成已知的密钥流
for (int i = 0; i < keyStreamLength; i++) {
int feedback = 0;
for (int j = 0; j <= lfsrWidth && j < poly.length; j++) {
if (poly[j] == 1 && j > 0) {
feedback ^= (testState >> (j - 1)) & 1;
}
}
int output = testState & 1;
if (output != keyStream[i]) {
match = false;
break;
}
testState = (testState >>> 1) | (feedback << (lfsrWidth - 1));
}
if (match) {
// 找到了正确的初始状态，生成完整密钥流
testState = initState;
for (int i = 0; i < ciphertext.length * 8; i++) {
int feedback = 0;
for (int j = 0; j <= lfsrWidth && j < poly.length; j++) {
if (poly[j] == 1 && j > 0) {
feedback ^= (testState >> (j - 1)) & 1;
}
}
int bit = testState & 1;
int byteIndex = i / 8;
int bitIndex = 7 - i % 8;
if (bit == 1) {
recoveredKeyStream[byteIndex] |= (1 << bitIndex);
}
testState = (testState >>> 1) | (feedback << (lfsrWidth - 1));
}
break;
}
}
return recoveredKeyStream;
}
/**
* 完整的攻击演示
*/
public static void main(String[] args) {
System.out.println("=== LFSR密码分析演示 ===");
System.out.println("攻击场景：已知明文攻击，恢复LFSR密钥");
System.out.println();
// 创建一个"攻击者"视角的LFSR
int width = 8;
int taps = 0b10111001; // x^8 + x^6 + x^5 + x^4 + 1
long key = 0x37;
// 攻击者知道密文和一部分明文
String knownPlaintext = "HTTP/1.1 200 OK";
String fullMessage = "HTTP/1.1 200 OK\r\nContent-Type: text/html\r\n\r\n<html>Hello</html>";
// 模拟加密（攻击者视角）
LFSRCipher cipher = new LFSRCipher(width, taps, key);
byte[] ciphertext = cipher.encrypt(fullMessage.getBytes());
System.out.println("攻击者已知的信息：");
System.out.println(" 密文: " + LFSRCipher.toHex(ciphertext));
System.out.println(" 已知明文: " + knownPlaintext);
System.out.println();
// 执行攻击
byte[] knownBytes = knownPlaintext.getBytes();
byte[] recoveredKeyStream = attackLFSR(ciphertext, knownBytes, width);
// 解密剩余部分
byte[] decrypted = new byte[ciphertext.length];
for (int i = 0; i < ciphertext.length; i++) {
decrypted[i] = (byte)(ciphertext[i] ^ recoveredKeyStream[i]);
}
System.out.println("攻击结果：");
System.out.println(" 恢复的明文: " + new String(decrypted));
System.out.println();
// 验证
String expected = fullMessage;
System.out.println("验证: " + (new String(decrypted).equals(expected) ? "✓ 成功破解!" : "✗ 失败"));
}
}
实际应用四：CRC校验
你可能不知道，CRC校验码其实就是LFSR的一种应用！CRC（循环冗余校验）广泛用于网络通信、存储系统等场景，用来检测数据传输中的错误。
”`java /**
LFSR实现CRC校验
CRC的本质是一个特殊配置的LFSR
发送方计算校验码附加到数据上
接收方用同样的LFSR验证数据完整性 */ public class CRCLFSR {
private int polynomial; private int remainder; private int width;
public CRCLFSR(int polynomial) {
this.polynomial = polynomial; this.width = Integer.SIZE - Integer.numberOfLeadingZeros(polynomial); this.remainder = 0;}
/**
更新CRC值（逐字节处理） */ public void update(byte[] data) { for (byte b : data) {
remainder ^= (b << (width - 8)); for (int i = 0; i < 8; i++) { if ((remainder & (1 << (width - 1))) != 0) { remainder = (remainder << 1) ^ polynomial; } else { remainder = remainder << 1; } }} }
/**
- 获取最终CRC值 */ public int getCRC() { return remainder & ((1 << (width - 1)) - 1); }
/**
CRC-32实现（使用标准多项式 0xEDB88320） */ public static class CRC32LFSR { private static final int POLYNOMIAL = 0xEDB88320; private int crc = 0xFFFFFFFF;
public void update(byte[] data) {
for (byte b : data) { crc ^= (b & 0xFF); for (int i = 0; i < 8; i++) { if ((crc & 1) != 0) { crc = (crc >>> 1) ^ POLYNOMIAL; } else { crc >>>= 1; } } }}
public int getValue() {
return crc ^ 0xFFFFFFFF;}
public static String compute(byte[] data) {
CRC32LFSR crc = new CRC32LFSR(); crc.update(data); return String.format("%08X", crc.getValue());} }
public static void main(String[] args) {
// CRC-8演示 CRCLFSR crc8 = new CRCLFSR(0x07); // CRC-8多项式 byte[] message = "123456789".getBytes(); crc8.update(message); System.out.println("CRC-8 of '123456789': " + String.format("%02X", crc8.getCRC())); System.out.println("期望值: 0xF4"); // CRC-32演示（与Java标准库对比） String testData = "Hello, LFSR World!"; String ourCRC32 = CRC32LFSR.compute(testData.getBytes()); java.util.zip.CRC32 stdCRC = new java.util.zip.CRC32(); stdCRC.update(testData.getBytes()); String stdCRC32 = String.format("%08X", stdCRC.getValue()); System.out.println("\nC[1] [2]