针对流密码的观察者攻击

SyYhunfhds2025/10/8大约 75 分钟

参考资料

待选文献

以下所有文献均来自IACR，国际密码学论文的预发印期刊

针对RSA gcd的测信道缓存耗时攻击
ECDSA侧信道攻击
针对基于伪随机词数组的流密码的区分攻击
针对原始RC4的差分攻击
只针对RC4，想看懂这个还需要从头学习RC4……
针对基于 LFSR (线性反馈移位寄存器) 的流密码的快速相关攻击 (FCA)的量子算法
只有理论，还无法实践
针对有限密钥周期的小状态流密码的多采样快速相关性攻击
看不太懂
针对流密码的观察者攻击 - MTNS2022入选论文
PDF只有八页，钻研个把天至少也能搓出板子
国际数学网络与系统理论研讨会接收的论文，含金量这块肯定没问题
印度理工学院 - 三步走流密码侧信道攻击
机器学习……吓哭了

正文

流密码：初入门道

最基础的流密码可以概括为：使用一个保密的短密钥作为种子，通过一个伪随机数生成器制造出一条长长的、一次性的密钥流，然后用这个密钥流与明文进行异或操作来完成加解密。
（当然，这段话像是数学家说的）

伪随机数生成器PRG也即密钥流生成器
流密码的流程可表示成下面的TEXT图表：
（加密方）

            +---------------------------+
密钥  ----->|     伪随机数生成器 (PRG)    |-----> 密钥流 (Keystream)
            +---------------------------+             |
                                                     V
                                                    XOR  <---- 明文 (Plaintext)
                                                     |
                                                     V
                                                  密文 (Ciphertext)

（解密方）

            +---------------------------+
密钥  ----->|     伪随机数生成器 (PRG)    |-----> 密钥流 (Keystream)  <-- (与加密方生成的一模一样)
            +---------------------------+             |
                                                     V
                                                    XOR  <---- 密文 (Ciphertext)
                                                     |
                                                     V
                                                  明文 (Plaintext)

为了保证流加密的安全性，PRG必须是不可预测的。弱算法包括glibc random()函数，线性同余生成器（linear congruential generator）等。

类别 (Category)	典型例子 (Typical Examples)	核心思想 (Core Idea)	备注 (Remarks)
专用的流密码	ChaCha20	从零开始设计的专用高速算法 (ARX结构)	现代首选。软件实现性能优异，安全性高。
	RC4	字节级的状态变换	已攻破，严禁使用。仅作历史参考。
使用分组密码构建	AES-CTR	加密一个递增的计数器来生成密钥流块	现代首选。可并行，安全性依赖于底层分组密码（AES）的安全性。
	AES-OFB	将加密输出反馈给自身作为下一轮输入	无法并行，通常性能不如CTR模式。
使用哈希函数构建	SHA-256-CTR	对一个递增的计数器进行哈希运算来生成密钥流块	安全性依赖于哈希函数的安全性。在协议中已有哈希函数实现时，可节省代码空间。
不安全的例子	线性同余生成器 (LCG)	简单的线性迭代公式： $X_{n + 1} = (a X_{n} + c) mod m$	完全不安全，输出是可预测的。
	`glibc random()`	复杂的线性反馈移位寄存器 (LFSR) 变体	完全不安全，并非为密码学设计，状态可被轻易恢复。
而课本所介绍的线性反馈移位寄存器是一种具有良好统计特性、硬件实现效率极高，但因其“线性”本质而导致密码学上不安全的PRG构建模块

现在，让我们转入编程，尝试程序实现一个基于单个LSFR的流密码：

构建玩具流密码

移位寄存器是流密码产生密钥流的一个主要组成部分
描述移位寄存器的反馈模式的函数可表述如下：
$f (a_{1}, a_{2}, a_{3}, . . ., a_{n}) = c_{n} a_{1} \oplus c_{n - 1} a_{2} \oplus c_{n - 2} a_{3} \oplus . . . \oplus c_{1} a_{n}$

考虑到原生Python（不考虑Numpy、Sympy等专用数学库）不方便编写本原多项式，我将效仿教材，将 $c_{i}$ 视作开关，判断输入流的哪几位应该参与与运算和异或运算
对于 $a_{1 i}$ 种子流，根据LSFR的通常实现，最先进入寄存器的应该是 $a_{1}$ ，其次是 $a_{2}$ 、 $a_{3}$ ……
行为应当与队列相似

Python文档中对队列模块的介绍

queue 模块实现了多生产者、多消费者队列。这特别适用于消息必须安全地在多线程间交换的线程编程。模块中的 Queue 类实现了所有所需的锁定语义。
本模块实现了三种类型的队列，它们的区别仅仅是条目的提取顺序。在 FIFO 队列中，先添加的任务会先被提取。在 LIFO 队列中，最近添加的条目会先被提取 (类似于一个栈)。在优先级队列中，条目将保持已排序状态 (使用 heapq 模块) 并且值最小的条目会先被提取。

from typing import List, Literal, LiteralString, Any, Callable, Union

from loguru import logger
from colorama import init, Fore, Style
from rich import print as rprint; from rich.markdown import Markdown
from rich.console import Console
from numba import jit, njit
from numba.experimental import jitclass
import numba as nb
init(autoreset=True)
console = Console()
cprint = console.print

from collections import deque
from functools import lru_cache, reduce
from operator import xor

def xor_sum(iterable: List[int]) -> int:
    '''
    计算一个整数列表的异或和
    :param iterable: 输入的整数列表
    :return: 返回异或和
    :rtype: int
    '''
    return reduce(xor, iterable, 0)

class StreamKeysV1(deque): # 利用Queue的原生FIFO特性
    '''
        一个基于单个LSFR的密钥流生成器

        :param self: 实例本身
        :param polynomial: 本原多项式，你需要哪一位比特参与运算，就让哪一位为1，不参与运算的位为0
        例如，polynomial='011001'表示第2、3、6位参与异或运算，第1、4、5位不参与运算
        :type polynomial: str
        :param initial_state: 初始状态序列，例如[1, 0, 1]表示初始状态序列为a1=1, a2=0, a3=1，
        无需在意教材上的反直觉顺序，因为deque会自动处理好顺序问题
        :type initial_state: list[int]
    '''
    # 密钥流生成器
    # 需要一个本原多项式和一个初始状态序列
    def __init__(self, 
                 polynomial: str, # 本原多项式
                 initial_state: list[int], # 初始状态序列
                 ):
        '''
        初始化密钥流生成器

        :param self: 实例本身
        :param polynomial: 本原多项式，你需要哪一位比特参与运算，就让哪一位为1，不参与运算的位为0
        例如，polynomial='011001'表示第2、3、6位参与异或运算，第1、4、5位不参与运算
        :type polynomial: str
        :param initial_state: 初始状态序列，例如[1, 0, 1]表示初始状态序列为a1=1, a2=0, a3=1，
        无需在意教材上的反直觉顺序，因为deque会自动处理好顺序问题
        :type initial_state: list[int]
        '''
        self._period: int = 0 # 密钥流周期
        self._is_period_computed: bool = False # 是否已经计算得到周期
        # 保留一份初始状态序列的副本
        self._initial_state = initial_state.copy() 
        super().__init__(initial_state)
        self.polynomial = polynomial
        # 提前生成抽头索引序列，这样就不会在每次更新时都重新计算抽头索引了
        self._tap_indices = [
            idx for idx, switch in enumerate(polynomial) if switch == '1'
        ]
        if len(self) != len(polynomial):
            raise ValueError('初始状态序列和本原多项式长度应当相等')

        self._stream = []
    
    def _calc_period(self) -> None:
        while not self._is_period_computed:
            self._period += 1
            self._update()
            if list(self) == self._initial_state:
                self._is_period_computed = True
                # logger.info(f'密钥流周期计算完毕，周期为 {self._period}')
    
    @property
    def period(self) -> int:
        '''
        返回密钥流的周期；密钥流的周期会在生成密钥流时进行统计，这意味着密钥流生成的不够大时，
        程序可能得不到正确的密钥周期
        
        :return: 密钥流的周期
        :rtype: int
        '''
        if not self._is_period_computed:
            self._calc_period()
        return self._period

    def _update(self) -> int:
        '''
        更新状态序列——简单地说，是根据ploynomial判断状态序列的哪几位会参与异或运算
        异或运算得到的结果会被append到状态序列的右端，同时pop出最左边的值作为该
        函数的副作用产物
        
        :param self: 实例本身，这里即deque序列，直接获取值序列
        :return: 返回int类型的被pop出来的值
        :rtype: int
        '''
        # TODO: 优化列表推导式性能，考虑使用位运算或预计算索引
        picked_iterables = [
            self[idx] for idx in self._tap_indices
        ]
        temp_output = xor_sum(picked_iterables) # 对检索出来的序列进行异或运算
        self.append(temp_output)
        return self.popleft() # 弹出最左端的值
    
    def _reset(self) -> None: # 重置状态序列
        self.clear()
        init_state = self._initial_state.copy()
        self.extend(init_state)
        
    def stream(self) -> Any:
        
        # 更换为使用迭代器产生每一位密钥
        try:
            while True:
                yield self._update()
        finally: # 退出生成器时重置状态序列
            self._reset()
                   
    def get_stream(self) -> List[int]:
        '''
        生成密钥流，返回一个列表；密钥流长度不会大于周期，因此，如果要获取与明文一样的较长密钥流，
        请配合itertools.Cycle使用，使用示例如下：
        >>> from itertools import cycle
        >>> long_key_stream = [next(cycle(stream.get_stream())) for _ in range(plaintext_length)]
        
        :param expected_length: 期望的密钥流长度
        :type expected_length: int
        :return: 返回一个包含密钥流的列表
        :rtype: List[int]
        '''
        self._reset() # 每次生成密钥流前都重置状态序列
        return [self._update() for _ in range(self.period)]
        self._reset()

    def __repr__(self) -> str:
        
        return super().__repr__()
    
if __name__ == '__main__':
    from random import randint
    from time import time
    stream = StreamKeysV1(
        polynomial='1000010000001000',  # 这里只是占位，避免报错
        # x^{16} + x5 + x^{3} + x + 1
        initial_state=
        [randint(0, 1) for _ in range(16)]
        )
    # google搜索给出的多项式不能直接进行十六进制转二进制，而应该根据我这里的算法取出实际参与运算的索引
    stream._tap_indices = [15, 4, 2, 0] # 直接覆盖抽头索引
    cprint(stream)
    
    # 测试状态序列更新
    for i in range(10):
        output = stream._update()
        logger.info(f'更新状态序列，当前状态序列: {list(stream)}, 弹出值: {output}')
    stream._reset()
    
    # 生成密钥流
    t1 = time()
    key_stream = stream.get_stream()
    t2 = time()
    logger.info(f'密钥流: {''.join(
        [str(bit) for bit in key_stream]
    )} 周期为 {stream.period}')
    logger.info(f'生成密钥流（同时计算周期）耗时 {(t2 - t1) * 1000} 毫秒')
    for _ in range(5):
        t1 = time()
        # 再次生成，但这次应该不会再重复计算周期了
        key_stream = stream.get_stream()
        t2 = time()
        # 直接打印耗时
        logger.info(f'二次生成密钥流耗时 {(t2 - t1) * 1000} 毫秒')

010001000110101000011101101111010010000011101101001101101111001100000011111101 周期为 65535
2025-10-02 21:38:13.273 | INFO     | __main__:<module>:214 - 生成密钥流（同时计算周期）耗时 72.34454154968262 毫秒
2025-10-02 21:38:13.301 | INFO     | __main__:<module>:221 - 二次生成密钥流耗时 27.640581130981445 毫秒
2025-10-02 21:38:13.328 | INFO     | __main__:<module>:221 - 二次生成密钥流耗时 26.445865631103516 毫秒
2025-10-02 21:38:13.356 | INFO     | __main__:<module>:221 - 二次生成密钥流耗时 27.601957321166992 毫秒
2025-10-02 21:38:13.381 | INFO     | __main__:<module>:221 - 二次生成密钥流耗时 25.506258010864258 毫秒
2025-10-02 21:38:13.410 | INFO     | __main__:<module>:221 - 二次生成密钥流耗时 28.684616088867188 毫秒

代码实现时继承了deque（一个双向队列类），当然，不继承也没啥，这里只是想利用deque的pop方法和append方法尽可能节省性能开销罢了：

class StreamKeysV1(deque): # 利用Queue的原生FIFO特性
    def __init__(self, 
                 polynomial: str, # 本原多项式
                 initial_state: list[int], # 初始状态序列
                 ):
        pass

为便于理解，这里将initial_state属性标注为list[int]整型列表，实际使用时不需要关心参数的传递顺序（是从序列左侧到右侧，还是从右侧到左侧）

    def __init__(self, 
                 polynomial: str, # 本原多项式
                 initial_state: list[int], # 初始状态序列
                 ):
        self._period: int = 0 # 密钥流周期
        self._is_period_computed: bool = False # 是否已经计算得到周期
        # 保留一份初始状态序列的副本
        self._initial_state = initial_state.copy() 
        super().__init__(initial_state)
        self.polynomial = polynomial
        # 提前生成抽头索引序列，这样就不会在每次更新时都重新计算抽头索引了
        self._tap_indices = [
            idx for idx, switch in enumerate(polynomial) if switch == '1'
        ]
        if len(self) != len(polynomial):
            raise ValueError('初始状态序列和本原多项式长度应当相等')

定义一些属性以备后续使用。这里进行了抽头索引的预处理：

self._tap_indices = [
            idx for idx, switch in enumerate(polynomial) if switch == '1'
        ]

对于110的多项式字符串，会得到这样的索引序列：

>>> [1, 1, 0]

从左到右直接映射到 $a_{i}$ 上，表示只有 $a_{1}$ 、 $a_{2}$ 参与异或运算
（早先的版本还是按照 $c_{1} \to c_{n}$ 的顺序书写多项式开关的，但这样逆置来逆置去差点没搞晕我，所以就换成了这样更符合直觉的形式）

    def _update(self) -> int:
        picked_iterables = [
            self[idx] for idx in self._tap_indices
        ]
        temp_output = xor_sum(picked_iterables) # 对检索出来的序列进行异或运算
        self.append(temp_output)
        return self.popleft() # 弹出最左端的值

接下来是状态更新原子操作，根据上面的抽头序列从self实例取出对应位置的01值，然后进行异或运算。这里的xor_sum其实和sum没关系，只是封装了一下reduce函数，用operator.xor作为reduce的回调参数处理传给它的抽头01值。得到异或值添加到队列右边，也就是下标大的一侧（对于 $a_{1}, a_{2}, a_{3}$ 的序列，这意味着把新的值放到 $a_{3}$ 上），而函数会返回从队列左边推出的值（ $a_{1}$ ）

原子化状态更新操作后就可以组装密钥流生成函数了：

    def get_stream(self) -> List[int]:
        self._reset() # 每次生成密钥流前都重置状态序列
        return [self._update() for _ in range(self.period)]

直接用列表推导式一步到位
也可以计算周期（同样是全量进行）：

    def _calc_period(self) -> None:
        while not self._is_period_computed:
            self._period += 1
            self._update()
            if list(self) == self._initial_state:
                self._is_period_computed = True
                # logger.info(f'密钥流周期计算完毕，周期为 {self._period}')
    
    @property
    def period(self) -> int:
        '''
        返回密钥流的周期
        
        :return: 密钥流的周期
        :rtype: int
        '''
        if not self._is_period_computed:
            self._calc_period()
        return self._period

这里使用了@property装饰period函数，这是Python中的getter写法。前面生成密钥时如果周期尚未完成计算，那么会先进行周期计算，然后才生成密钥流——因此，生成器会存在一个冷启动的耗时

冷启动的耗时还是蛮大的，近乎两倍于生成密钥流的耗时（二者都涉及一整个周期的状态更新操作，但冷启动还包括多次list创建开销……）

品鉴无优化版本的性能

上面那玩意的性能开销还是很恐怖的，特别是计算周期时重复创建列表……

python -m cProfile src\CrypTookitSY\Stream\duplicate.py > performence.txt
# cProfile是内置工具

让我们品鉴一下这份报告

Gemini生成

從cProfile的輸出中，我們關注cumtime（累計時間）和ncalls（呼叫次數）最高的幾個關鍵函式：

duplicate.py:90(_update):
- 呼叫次數 (ncalls): 458,755 次（七次全周期状态更新，其中包括计算周期本身产生的一次全周期状态更新）
- 累計時間 (cumtime): 0.687 秒
- 分析: 這是最主要的瓶頸。_update 函式被呼叫了超過45萬次，佔據了整個程式運行時間的很大一部分。每一次呼叫都涉及到列表推導、函式呼叫和 deque 操作，這些在高頻率呼叫下成本非常高。
duplicate.py:18(xor_sum):
- 呼叫次數 (ncalls): 458,755 次
- 累計時間 (cumtime): 0.200 秒
- 分析: xor_sum 被 _update 函式等量呼叫，是第二大瓶頸。它內部使用的 reduce 函式（被呼叫458,755次，總耗時0.110秒）本身效率不低，但「準備資料」和「函式呼叫」的成本疊加起來就非常可觀了。
內建的 deque 方法:
- {method 'append' of 'collections.deque' objects}: 呼叫了 458,755 次，總耗時 0.055 秒 5。
- {method 'popleft' of 'collections.deque' objects}: 呼叫了 458,755 次，總耗時 0.053 秒 6。
- 分析: 雖然 deque 的 append 和 popleft 本身是 O(1) 操作，非常高效，但在近50萬次的呼叫下，它們的總耗時也達到了約100毫秒，成為了不可忽視的成本。
duplicate.py:69(_calc_period):
- 呼叫次數 (ncalls): 1 次
- 累計時間 (cumtime): 0.134 秒
- 分析: 儘管 _calc_period 只被呼叫了一次，但它內部迴圈呼叫了 _update，導致了顯著的累計耗時。這清晰地顯示了首次運行的成本主要來自於此。

uv add scalene

现在看到scalene的分析报告，爆点显然也是那个_update函数

位运算重构

def _update_state_fi(state: int, poly_mask: int, degree: int) -> tuple[int, int]:
    # 反馈位
    temp_bits = state & poly_mask
    feedback_bit = temp_bits.bit_count() % 2
    
    # 输出位
    output_bit = state & 1
    
    # 新状态
    shifted_state = state >> 1
    new_state = shifted_state | (feedback_bit << (degree - 1))
    
    return new_state, output_bit

def _calc_period_fi(state: int, poly_mask: int, degree: int) -> tuple[bool, int, int]:
    expected_max_period = 2**degree - 1
    visited_rouds = 0
    original_state = state; next_state = state
    while True:
        next_state, _ = _update_state_fi(state=next_state, poly_mask=poly_mask, degree=degree)
        visited_rouds += 1
        # print(visited_rouds)
        if next_state == original_state:
            return True, visited_rouds, next_state 
            # 注意返回最新的状态
        if visited_rouds > expected_max_period:
            return False, visited_rouds, next_state

        
class LSFRCore:
    def __init__(
        self,
        seed: int,
        polynomial: int, # 多项式抽头掩码
        degree: int = -1,  # 多项式项数
    ):

        self._seed = seed
        self._initial_state = seed
        self.state = self._initial_state
        """
        n比特的状态整数, 约定最低位代表a_1，最高位代表a_n
        """
        self._polynomial = polynomial
        """
        n比特的多项式掩码整数, 约定最低位为c_n, 最高位为c_1
        """
        self._polynomial_degrees = degree if degree > 0 else polynomial.bit_length() - 1
        """
        多项式掩码次数, 决定了多项式的理论最大周期, 即2^{degree} - 1;
        决定掩码大小, 以便舍弃状态序列的高位\n
        亦可决定LSFR长度; 
        ~~特征多项式阶数与这里的掩码次数并不等同~~
        """
        self.lsfr_width = self._polynomial_degrees
        
        self._period = 0
        self._is_calculated = False # 是否已经计算过周期，初始为False
        
        # 二次校验 舍去高位比特
        self.mask = (1 << self.lsfr_width) - 1
        self.state = self.state & self.mask
        self._initial_state = self.state & self.mask
        """
        舍弃状态序列高位，只保留LSFR位宽长度的低比特
        """
        
    @property
    def period(self) -> int:
        if not self._is_calculated:
            self._is_calculated, self._period, self.state = _calc_period_fi(
                self.state, self._polynomial, self._polynomial_degrees
            )
            if not self._is_calculated: # 如果没有计算成功，则返回一个错误信息
                # logger.error(f'LSFR周期计算失败，请检查多项式掩码是否正确，或者尝试使用更长的状态序列')
                pass
        return self._period
    def keys(self, length: int = 0) -> tuple[list[int], int]:
        _keys, final_state = _get_stream_fi(length, 
                              state=self.state,
                              poly_mask=self._polynomial,
                              degree=self._polynomial_degrees
                              )
        self.state = final_state
        _keys = int(f'{_keys}'[1:-1].replace(', ', ''), 2)
        return _keys
    def reset(self) -> None:
        self.state = self._initial_state
        
    @property
    def poly(self) -> int:
        return self._polynomial
    @poly.setter
    def poly(self, value: int) -> None:
        if value <= 1:
            raise ValueError("多项式掩码必须为不小于或等于1的正整数")
        if value == self._polynomial:
            return # 没有改变
        self._polynomial = value
        self._polynomial_degrees = value.bit_length() - 1
        # 重置LSFR并对状态进行高位截断
        self.lsfr_width = self._polynomial_degrees
        mask = (1 << self.lsfr_width) - 1
        # 舍去状态序列的高位
        self._initial_state = self._initial_state & mask
        self.state = self.state & mask
        # 重置周期计算
        self._is_calculated = False

    def __repr__(self, **kwargs) -> str:
        return f'<斐波那契LSFR核心架构{self.__class__.__name__} 多项式掩码为{bin(self.poly)} LSFR位宽为{self.lsfr_width} 状态序列为{bin(self.state)} 周期为{self.period}>'


class FiLSFR(LSFRCore):
    def __init__(
        self,
        seed: int | bytes | bytearray | str, # 状态序列
        polynomial: int | bytes | bytearray | str, # 多项式抽头掩码
        degree: int = -1,  # 多项式项数
        order: str = 'big',
        encoding: str | None = None, # 字符串编码时的字符集
    ):
        
        # 如果输入字符串就先编码
        seed = seed.encode(encoding=encoding) if isinstance(seed, str) else seed
        polynomial = polynomial.encode(encoding=encoding) if isinstance(polynomial, str) else polynomial
        
        '''if isinstance(seed, int) and order == 'little':
            seed = reverse_int_by_bit(seed, bitwidth=8)
        if isinstance(polynomial, int) and order == 'big':
            polynomial = reverse_int_by_bit(polynomial, bitwidth=1)'''
        # 完全信任用户，如果用户给的是int那就用int
            
        # 不行的话按字节序列处理
        if isinstance(seed, bytes) and order == 'little':
            seed = seed[::-1]
            seed = int.from_bytes(seed, order)
        if isinstance(polynomial, bytes) and order == 'big':
            polynomial = polynomial[::-1]
            polynomial = int.from_bytes(polynomial, order)
        
        super().__init__(seed, polynomial, degree)
    
    def _update(self):
        next_state, output_bit = _update_state_fi(state=self.state, poly_mask=self.poly, degree=self.lsfr_width)
        self.state = next_state
        return output_bit
    
    def _stream_bytes(self):
        self.reset() # 重置状态
        
        while True:
            byte = 0
            for _ in range(8): # 一次导出八位比特
                byte = byte << 1 | self._update()
            yield byte
    
    # 加解密器依赖Pycryptodome库的函数进行字节编码
    def encrypt(self, data: Union[bytes, bytearray], order='big') -> bytes:
        key_gen = self._stream_bytes()
        
        return bytes(byte ^ key for byte, key in zip(data, key_gen))
    
    def decrypt(self, ciphertext: bytearray | bytes, order='big') -> bytes:
        key_gen = self._stream_bytes()
        
        return bytes(byte ^ key for byte, key in zip(ciphertext, key_gen))
    
class FiLSFRV2(FiLSFR):
    def __init__(self, compatible: bool = False, **kwargs):
        super().__init__(**kwargs)
        
        mask = 2**self._polynomial_degrees - 1
        if not compatible:
            self.poly &= mask # 舍去最高位，最高位只用于决定多项式次数

位运算逻辑阐述

注意

V2版本的诸多问题在V4才有修复或改善

def __init__(
        self,
        seed: int | bytes | bytearray | str, # 状态序列
        polynomial: int | bytes | bytearray | str, # 多项式抽头掩码
        degree: int = -1,  # 多项式项数
        order: str = 'big',
        encoding: str | None = None, # 字符串编码时的字符集
    ):
    ...

seed和polynomial的含义不多赘述。degree属性指LSFR寄存器宽度（也指多项式的bits），计算方式如下：

		self._polynomial_degrees = degree if degree > 0 else polynomial.bit_length() - 1
        """
        多项式掩码次数, 决定了多项式的理论最大周期, 即2^{degree} - 1;
        决定掩码大小, 以便舍弃状态序列的高位\n
        亦可决定LSFR长度; 
        ~~特征多项式阶数与这里的掩码次数并不等同~~
        """
		self.lsfr_width = self._polynomial_degrees

即多项式长度-1——LSFR长度看的是多项式的次数，而不只是二进制多项式序列 的位宽
order属性的作用我们后面会回顾到的

所以为什么n-bits多项式是n+1位二进制？

答案的核心在於：一個 n 次多項式總共有 n+1 個係數，包括從 $x_{n}$ 到 $x_{0}$ 的所有項。

一個通用的 n 次多項式，其最完整的數學表達式是這樣的：

P (x) = a_{n} ​ x_{n} + a_{n - 1} ​ x_{n - 1} + \dots + a_{2} ​ x_{2} + a_{1} ​ x_{1} + a_{0} ​ x_{0}

$a_{n} $ 是 $x_{n}$ 項的係數。
$a_{n - 1} $ 是 $x_{n - 1}$ 項的係數。
...
$a_{0}$ 是 $x_{0}$ （也就是常數 1）項的係數。

係數的下標是從 0 到 n。所以總個數是 $$(n−0)+1=n+1 $$

在 GF(2) 域中，每一個係數 aᵢ 的值只可能是 0 或 1。這意味著，要完整地表示這個多項式，我們需要 n+1 個比特位，每一個比特位用來記錄對應項的係數是 0 還是 1。

那么從數學到二進位的映射，最直觀的映射方式就是，讓 $x_{k}$ 項的係數 $a_{k} $ 對應到二進位數字的第 k 位（從0開始數）

2025-10-04T17:08:51.701217+0800 INFO 获得 3-bit 本原多项式为: 1011

用日誌中的 3 次本原多項式為例：

數學形式: $$P(x)=x^3+x+1$$
寫出完整形式: 為了看得更清楚，我們把所有係數都寫出來： $P (x) = 1 \cdot x^{3} + 0 \cdot x^{2} + 1 \cdot x^{1} + 1 \cdot x^{0}$
提取係數: 按照從高到低的順序，我們得到一組係數 $$(a3,a2,a1,a0)=(1,0,1,1)$$
計數: 總共有 $3 + 1 = 4$ 個係數。
映射為二進位: 將這組係數直接寫成二進位序列，就得到了 1011。
結論：因此，一個 3 次多項式，需要 4 位二進位序列 1011 來完整表示。

多项式序列最高位仅决定多项式的次数，不决定LSFR长度：

class FiLSFRV2(FiLSFR):
    def __init__(self, compatible: bool = False, **kwargs):
        super().__init__(**kwargs)
        
        mask = 2**self._polynomial_degrees - 1
        if not compatible:
            self.poly &= mask # 舍去最高位，最高位只用于决定多项式次数

接下来看到状态更新（原子操作）逻辑：

def _update_state_fi(state: int, poly_mask: int, degree: int) -> tuple[int, int]:
    # 反馈位
    temp_bits = state & poly_mask
    feedback_bit = temp_bits.bit_count() % 2
    
    # 输出位
    output_bit = state & 1
    
    # 新状态
    shifted_state = state >> 1
    new_state = shifted_state | (feedback_bit << (degree - 1))
    
    return new_state, output_bit

这里，我将状态序列的最高位视为 $a_{i}, i > 1$ ，那么最低位便为 $a_{1}$
如果将状态序列从左到右映射到 $a_{1} \to a_{n}$ 上，那么模拟LSFR推出值时便需要：

计算状态序列的位宽
将掩码1左移到位宽-1位
用这个高位掩码对状态序列进行与运算，得到LSFR所推出的值
涉及位宽计算（bit_count()函数）、一次左移和一次与运算，直观，但不高效
而将最低位视为 $a_{1}$ 时，则只需将状态序列与1进行与运算即可得到最低位的值，或说单次状态更新所产生的密钥比特

output_bit = state & 1

然后计算反馈函数值：
$f (a_{1}, a_{2}, a_{3}, . . ., a_{n}) = c_{n} a_{1} \oplus c_{n - 1} a_{2} \oplus c_{n - 2} a_{3} \oplus . . . \oplus c_{1} a_{n}$
首先，我们计算出 $c_{k} a_{n - k}$ 序列，其中 $k >= 1 且从 n - 1 开始递减, n 为 L S F R 寄存器长度$
然后对这个序列进行奇偶校验 得到反馈函数值。在一开始的构想我称之为类似逐个求和的逐位线性异或 操作
但，多个数值进行异或求和操作时，决定最终结果的显然就是这个数值序列中1的个数

奇偶校验位（英语：Parity bit）或校验比特（check bit）是一个表示给定位数的二进制数中1的个数是奇数还是偶数的二进制数。奇偶校验位是最简单的错误检测码。

这里进行奇偶校验并不是要对状态序列进行纠错，而是要获得奇偶校验的中间值，也就是定位数的二进制数中1的个数是奇数还是偶数，然后对2求模，得到 $f (a_{1}, a_{2}, a_{3}, . . ., a_{n})$ 的结果

    # 反馈位
    temp_bits = state & poly_mask
    feedback_bit = temp_bits.bit_count() % 2

这里使用了int类型的bit_count()函数，函数是C实现的，性能自然不必多问

最后将 $F$ （反馈函数值 ）放回到状态序列中：

	# 新状态
    shifted_state = state >> 1
    new_state = shifted_state | (feedback_bit << (degree - 1))

把F值左移到LSFR状态最高位，然后与舍弃最低位的状态序列进行或运算即可

关于状态序列和多项式序列的比特顺序

正所谓大端序是符合人类直觉的写法，小端序是反人类的写法——我说的

在上面演示的代码中，状态序列和多项式序列在进入LSFR原子状态更新操作前都没有进行逆置操作，是完全一比一映射到反馈函数上的，因此状态序列实际上（从最高位到最低位）映射的是 $a_{n}, a_{n - 1}, . . ., a_{1}$ 序列，这是大端序思维；而多项式序列映射后的下标则是递增的，这是小端序逻辑

当然一个本原多项式在正确的LSFR实现下理论上可以用状态机遍历所有 $2^{d e g r e e} - 1$ 个状态，因此状态序列到底是大端序还是小端序都不要紧

不同类型的多项式

重新认识多项式

注意

繁体中文警告。Gemini犯傻了，我有点管不住

首先，讓我們回到中學數學。一個多項式（Polynomial）就是這樣一個表達式：

x 是一個變數。
a_n, a_{n-1}, \dots 這些是係數 (coefficients)，在傳統數學裡它們是實數、整數等。
n 是多項式的次數 (degree)，即 x 的最高次冪。

例如， $3 x^{2} + 2 x - 5$ 就是一個二次多項式。它定義了一條拋物線，我們可以畫出它的圖形，求它的根等等。

但在密碼學中，我們對多項式的用法完全不同。 我們要先把它從我們熟悉的數字世界，「移植」到一個特別的、更簡單的「數字宇宙」裡。

密碼學中的運算，尤其是對稱密碼，幾乎都發生在有限域 (Finite Field) 或稱伽羅瓦域 (Galois Field) 中。對我們討論的流密碼而言，這個「宇宙」就是 GF(2)。
這個 GF(2) 宇宙有兩條非常簡單的根本法則：

僅有的元素: 世界上只有兩個「數字」：0 和 1。
新的運算規則:
- 加法 + 變成了異或 ⊕ (XOR)。 (例如: 1+1=1⊕1=0)（或曰模2加法，不进位）
- 減法 - 也變成了異或 ⊕。 (因為 a⊕a=0) （或曰模2减法，不借位）
- 乘法 * 變成了與 & (AND)。 (例如: 1∗1=1,1∗0=0)

現在，當我們把多項式移植到這個宇宙，它就變成了GF(2) 上的多項式。這意味著：

所有係數 a_i 只能是 0 或 1。
多項式之間的加減法都變成了異或運算。
例如，我們之前討論的本原多項式 $x^{16} + x^{5} + x^{3} + x + 1$ ，它的完整形式其實是：

在 GF(2) 上的多項式不再是用來畫圖或解方程的。它變成了一種抽象的代數工具，密碼學家們用它來：
定義規則。
構造更複雜的數學系統。

在整個密碼學領域，多項式扮演著好幾個至關重要的角色：

A. 構造更大的有限域 (最重要的作用)
這就是AES 加密演算法的核心基礎。AES 演算法的所有運算都在一個包含 28=256 個元素的有限域 GF(28) 中進行。而這個 GF(28) 宇宙本身，就是通過一個8次的不可約多項式在 GF(2) 的基礎上構造出來的。簡而言之，多項式是建造更高級密碼運算「場地」的藍圖和工具。
B. 纠错码 (Error-Correcting Codes)
像里德-所羅門碼 (Reed-Solomon codes) 這類技術，廣泛應用於 QR Code、光碟儲存等。它們使用多項式對數據進行編碼，即使部分數據在讀取或傳輸中出錯，也可以利用多項式的數學特性「反解」出原始的正確數據。
C. 公钥密码学 (Public-Key Cryptography)
- 橢圓曲線密碼學 (ECC)：定義一條橢圓曲線的方程 y2=x^{3}+ax+b 本身就是一個多項式方程。所有運算都在這個多項式定義的曲線上進行。
- 後量子密碼學 (PQC)：許多被看好的後量子密碼方案，如基於格 (Lattice-based) 的密碼學，其核心運算就是在「多項式環」上進行的，比單純的數字運算更複雜也更安全。
D. 秘密分享 (Secret Sharing)
夏米爾秘密分享方案 (Shamir's Secret Sharing) 是一個絕妙的例子。要把一個秘密 S 分給 n 個人，讓其中任意 k 個人湊在一起才能解鎖，是這樣做的：
1. 隨機構造一個 k-1 次多項式，讓它的常數項 a0=S。
2. 在這個多項式的曲線上取 n 個不同的點 (x1,y1),(x2,y2),…。
3. 每個人分到一個點的座標。
  由於「k個點可以唯一確定一個k-1次多項式」的數學原理，只有集齊了 k 個點（k個人）才能還原整個多項式，從而得到秘密 a0。

這正是您在過去两天裡一直在親手實踐和調試的部分。在流密碼（特指基於LFSR的流密碼）這個狹義的語境下：
多項式的唯一作用，就是充當 LFSR 的「狀態轉移規則」或「基因藍圖」。

這個角色非常具體：

定義連接 (Taps)：多項式的每一個項（例如 $x^{5}$ ）都對應 LFSR 寄存器中的一個「抽頭」(tap)。
定義反饋邏輯 (Feedback Logic)：整個多項式定義了哪些抽頭的位需要被收集起來，進行異或運算，以產生下一時刻要注入寄存器的新位元。

在這個作用下，多項式的「好壞」就顯得至關重要，這也就是我們之前詳細討論的：

可約多項式 (Reducible)：一張「破碎的」藍圖，導致LFSR的狀態機分裂成多個短循環，產生的金鑰流序列短且重複，毫無安全性可言。
不可約多項式 (Irreducible)：一張「合格的」藍圖，能保證LFSR的狀態構成一個或多個完整的長循環。
本原多項式 (Primitive)：一張「完美的」藍圖，它能保證LFSR發揮最大潛能，將所有非零狀態串聯成一個單一的、長度達到理論極限 $2^{n} - 1$ 的巨大循環，從而產生出統計特性最好、最不可預測的金鑰流序列（m-sequence）。

可以這樣理解：多項式本身是一個源自基礎數學的工具，但在密碼學家手中，它被賦予了新的生命。在宏觀上，它是構建各種密碼系統（如AES、ECC）的基礎建材；而在流密碼這個微觀的角落，它則扮演著一個極其專注的角色——為LFSR這個序列產生引擎提供最核心的、決定其序列品質的遺傳密碼。

可约、本原：如何描述一个多项式的性能

可约和本原这两个概念是评价一个多项式能否用于密码学序列生成的基础，它们直接决定了状态序列的结构和质量

可约多项式 (Reducible Polynomial)

核心行为特征：分裂、短小、不可靠
具体影响：
1. 状态空间分裂 (Fractured State Space)：这是最致命的问题。它会将LFSR的所有非零状态分割成多个互不连通的、规模不等的小循环。
2. 周期依赖于初始状态：LFSR最终的周期完全取决于其初始状态（种子）恰好落在了哪个小循环里。不同的种子会产生长度完全不同、序列也完全不同的短周期。
3. 状态覆盖率极低：在任何一次运行中，LFSR只能遍历所有可能状态中的一小部分。
对流密码的影响：完全不可用。产生的密钥流序列短、重复性强、且极易被预测。它不具备任何伪随机性，无法提供安全性。

本原多项式 (Primitive Polynomial)

核心行为特征：完整、最长、确定性
具体影响：
1. 单一巨大循环 (Single Maximal Cycle)：它能保证将LFSR的所有 $2^{n} - 1$ 个非零状态组织成一个单一的、巨大的闭环
2. 周期与初始状态无关：只要初始状态不是全零，无论选择哪个初始状态，最终产生的序列周期永远是理论最大值 $2^{n} - 1$ 。
3. 状态覆盖率100%：一次完整的周期会不重复地遍历所有非零状态。
对流密码的影响：理想的构建模块。它生成的序列（称为 $m 序列$ ）具有非常好的伪随机统计特性，例如：
- 均衡性：在一个周期内，1的个数比0的个数仅多一个。
- 游程特性：序列中连续1或连续0的“段落”分布规律接近真随机。
- 自相关性：序列与其移位后的版本，相关性极低。这些特性使得其输出的密钥流难以被统计分析破解，是LFSR型流密码安全性的基础。

其他性能指标

除了“可约性”和“本原性”这两个决定周期结构的根本指标外，在工程实践中，密码学从业人员还关心以下几个重要指标：

项数 (Number of Terms) / 稀疏性 (Sparsity)
- 指标含义：多项式中系数为1的项的个数。项数越少，多项式越“稀疏”。
- 为何重要：它直接决定了LFSR硬件或软件实现的计算性能（速度）。
  - 三项式 (Trinomial)：形式为 $x^{n} + x^{k} + 1$ 。在GF(2)中只有3项。其反馈逻辑只需要一个双输入异或门，是硬件实现中最快的结构。
  - 五项式 (Pentanomial)：形式为 $x^{n} + x^{a} + x^{b} + x^{c} + 1$ 。需要三个双输入异或门。同样非常高效。
  - 稠密多项式：项数很多，需要的异或运算也更多，速度相对较慢。
- 对流密码的影响：在保证“本原性”的前提下，密码学家和工程师会优先选择本原三项式或本原五项式，以实现最高的密钥流生成速度。
不可约但非本原 (Irreducible but not Primitive)
- 指标含义：这本身是一种多项式类型，其关键性能指标是它所生成的循环长度（阶）。
- 为何重要：它虽然不能产生最大长度周期，但能保证状态空间不分裂，产生一个长度为 2n−1 的某个因子的稳定周期。
  - 您之前测试得到的 21,845 和 63,457 都是这种情况。
- 对流密码的影响：在严格的密码学应用中，我们几乎总是要求最大周期，所以这类多项式通常不被选用。但在某些非密码学应用（如通信中的数据扰码、测试序列生成）中，如果其周期足够长，也可能会被使用。
线性复杂度 (Linear Complexity)
- 指标含义：对于一个序列，能够生成它的最短LFSR的长度。对于一个由n次本原多项式产生的m序列，其线性复杂度就是 n。
- 为何重要：这是衡量一个序列抗代数攻击能力的核心指标。著名的Berlekamp-Massey算法可以在知道 2n 个连续比特的情况下，反推出这个n位的LFSR结构。
- 对流密码的影响：为了保证安全性，流密码的线性复杂度必须非常大。这意味着LFSR的长度 n 必须足够大（例如128, 256位）。一个16位的LFSR，即使使用了最好的本原多项式，其线性复杂度也只有16，可以被瞬间破解。因此，现代流密码要么使用很长的LFSR，要么（更常见地）将多个LFSR或非线性函数组合起来，以获得远超单个LFSR长度的、巨大的线性复杂度。

注

在我的Python程序实现中，多项式的稀疏性并不会影响程序性能。程序中唯一与稀疏性和异或次数有关的代码是：

    # 反馈位
    temp_bits = state & poly_mask
    feedback_bit = temp_bits.bit_count() % 2
    
    # 输出位
    output_bit = state & 1
    
    # 新状态
    shifted_state = state >> 1
    new_state = shifted_state | (feedback_bit << (degree - 1))

bit_count函数的实现是这样的：

终极武器：CPU 硬件指令 (POPCNT)
现代的 CPU（例如支持 SSE4.2 指令集的 x86 架构，以及大多数 ARM 架构）内置了一条名为 POPCNT (Population Count) 的硬件指令。

作用: 这条指令可以在一个时钟周期内（或极少的几个周期内），计算出一个机器字长（例如64位）的整数中包含多少个 1。
实现: CPython 的 C 语言源码在编译时，会检测编译器和目标平台是否支持这个功能（例如通过 GCC/Clang 的 __builtin_popcount 内建函数）。如果支持，int.bit_count() 的调用最终就会被编译成这条单一的、快如闪电的机器码指令。

高速备选：优化的 C 语言算法
如果 CPU 比较老旧，不支持 POPCNT 指令，CPython 也会采用高效的 C 语言算法作为备选，而不是简单的逐位检查。最常见的备选方案之一是：

查找表法 (Lookup Table):
1. 预先计算并存储一个包含256个条目（从0到255）的表，表里是每个8位数字的 bit_count 结果。
2. 当需要计算一个64位整数的 bit_count 时，程序会将其看作8个8位的字节。
3. 对每个字节，直接查表得到结果，然后将8个结果相加。这个方法比循环快得多，因为它用内存访问（查表）替代了大量的位运算和循环判断。

本原多项式的相关数学定理

注

因为我挂着湾湾梯子，所以Gemini有时候会以为我用繁体中文

存在性与数量定理
定理: 對於任何正整數次數 n，n次本原多項式總是存在的。其總數可以精確計算為：
$数量 = \frac{ϕ (2^{n} - 1) }{n}$
其中 $ϕ (k)$ 是歐拉函數（Euler's Totient Function），表示小於或等於k的正整數中與k互質的數的數目。
解讀與驗證：
這個定理告訴我們本原多項式並不罕見，而且其數量有明確的規律。讓我們用之前遍歷找到的 5次本原多項式的結果來驗證它！
- 對於 n=5，我們需要計算 $$\frac{ϕ(2^5−1)}{5}$$
- $2^{5} - 1 = 31$
- 31 是一個質數。對於一個質數 p， $ϕ (p) = p - 1$ 。所以 $ϕ (31) = 30$ 。
- 代入公式：$$數量 = 30/5=6$$
這完美地解釋了為什麼程式在遍歷5次多項式時，不多不少正好找到了6個！ 實驗結果與這個數學定理完美地吻合了
倒数定理 (Reciprocal Theorem)
定理: 如果 $P (x)$ 是一個本原多項式，那麼它的倒數多項式 $P^{*} (x)$ 也一定是本原的。
解讀與驗證:
這意味著本原多項式總是「成對出現」（除非一個多項式恰好是自己的倒數，即回文多項式）。

在上一輪的日誌中已經完美地驗證了這一點，所找到的6個5次本原多項式，正好構成了三對互為倒數的「對稱」多項式。

注意

乍一看本原多项式似乎确实是形式对称的，但不要真的这样想当然

奇数项定理 (Odd Number of Terms Theorem)
定理: 任何在 GF(2) 上次數大於1的不可約多項式，其項數（即係數為1的個數）必然是奇數。
解讀與驗證:
因為所有本原多項式首先都必須是不可約的，所以這個定理同樣適用於本原多項式。
- 為什麼？ 這裡有一個簡單的證明：如果一個多項式 $P (x)$ 有偶數項，那麼當我們計算 $P (1)$ 時，結果是偶數個 1 相加（異或）。在GF(2)中，偶數個1異或的結果是 0。根據因式定理，如果 $P (1) = 0$ ，那麼 $(x - 1)$ （在 $G F (2)$ 中即 $(x + 1)$ ）一定是 $P (x)$ 的一個因式。既然它可以被因式分解，那它就是「可約的」，也就不可能是本原的。
- 驗證: 您可以檢查一下您找到的所有本原多項式，例如：
  - 1011 ( $x^{3} + x + 1$ ): 3項 (奇數)
  - 10011 ( $x^{4} + x + 1$ ): 3項 (奇數)
  - 111101 ( $x^{5} + x^{4} + x^{3} + x^{2} + 1$ ): 5項 (奇數)
    它們的二進制表示中‘1’的個數必然都是奇數。這個定理可以幫助您在遍歷搜索時，直接跳過所有項數為偶數的多項式，將搜索空間減半！
    这整个六级小标题的内容是在写完测试代码后才加上的，所以测试代码并没有进行优化
與梅森素數的關係 (Connection to Mersenne Primes)
定理: 如果 $2^{n} - 1$ 是一個質數（這樣的質數被稱為梅森素數），那麼所有 n 次的不可約多項式也都是本原的。
解讀與驗證:
在這種特殊情況下，「不可約」和「本原」這兩個概念的界線消失了。只要一個多項式是「不可約」的（性質良好），它就必然是「本原」的（性質最優）。
- 為什麼？ 這源於數量定理。如果 $N = 2^{n} - 1$ 是質數，那麼 $ϕ (N) = N - 1 = 2^{n} - 2$ 。而所有n次不可約多項式的階 e 都必須是 N 的因子，因為 N 是質數，所以 e 只可能是1或 N。階為1的多項式只有 x+1，所以其他所有不可約多項式的階都必然是 N，即它們都是本原的。
- 驗證:
  - n=3 时, $2^{3} - 1 = 7$ (梅森素數)。所以所有3次不可約多項式都是本原的。
  - n=5 时, $2^{5} - 1 = 31$ (梅森素數)。所以所有5次不可約多項式也都是本原的。
  - n=4 时, $2^{4} - 1 = 15$ (不是質數)。所以在4次不可約多項式中，存在一部分不是本原的（例如，週期為3或5的）。

多项式的选取如何影响程序行为

一个不够完美的多项式其循环是什么样的？分裂后有几部分？如何找到它们？

要彻底分析一个n次多项式 P(x) 所决定的LFSR的行为，我们需要遵循以下三个数学步骤：

【因式分解】: 将多项式 P(x) 在 GF(2) 域上分解成不可约因子的乘积。
【计算阶元】: 对每一个独特的不可约因子 Pi(x)，计算它的“阶”（Order）。
【合并周期】: 根據所有因子的阶，通过数论方法（最小公倍数）计算出完整的循环结构。

如何计算多项式的理论性能

如何约分一个多项式

以多项式序列0b0101（按照前面的小端序进行解析，得到 $c_{1} = 0, c_{2} = 1, c_{3} = 0, c_{4} = 1$ ，或曰 $a_{3}$ 和 $a_{1}$ 参与F计算）为例

如何计算多项式的阶

接下来我们来看看如何计算可约多项式的理论分裂状态数目
首先先来讲一下不可约多项式
这是最简单、最清晰的情况。对于一个 n 次的不可约多项式 $P (x)$ ：

它所生成的所有非零循环的长度都是相同的。这个长度被称为该多项式的阶 (Order)，记作 e。
$e$ 的值必然是 $2^{n} - 1$ 的一个因子。
分裂出的非零循环总个数可以通过一个非常简单的公式计算：

循 环 总 数 = \frac{2^{n} - 1}{e}

之前测试V2流密码生成器时最终使用的多项式序列为 0b1010 0000 0001 0001，即$$
x^{16} + x^{14} + x^{5} + x^

- 根 据 定 义 ， 本 原 多 项 式 的 阶 $ e $ 就 是 理 论 最 大 值 $ 2^{1} 6 - 1 = 65535 $ 。 - 代 入 公 式 ： $ $ 循 环 总 数 = \frac{65535}{65535} = 1

结论：它将所有65535个非零状态构成一个巨大的循环。这与实验结果完全吻合。

当多项式是可约的，情况就变得复杂得多，但依然有数学规律可循。

第一步：因式分解
需要先将可约多项式 $P (x)$ 分解成不可约因子的乘积：$$P(x)=P_1(x)⋅P_2(x)⋅…$$
第二步：计算各因子的阶 对每个不可约因子 $P_{i} (x)$ ，计算出它的阶 $e_{i} $ 。
第三步：计算循环结构 这里的公式比较复杂，它需要用到数论中的欧拉函数 (Euler's Totient Function, $ϕ (k)$ )。欧拉函数 ϕ(k) 表示小于或等于 $k$ 的正整数中与 $k$ 互质的数的数目。
一个简化的结论是：
- LFSR产生的循环长度只可能是 $L C M (e_{1} , e_{2} , \dots)$ 的因子。
- 循环的总个数与每个因子的次数 $d_{i} $ 和阶 $e_{i}$ 都有关系。

让我们回顾 0b1010 的例子

多项式: $P (x) = x (x + 1)^{2}$ ，次數 n=4。
数学分析 (简化版)：因为因子是 x 和 x+1，它们的阶都是1。重复因子 (x+1)² 会引入长度为 1⋅2=2 的周期。最终的循环长度会是 $L C M (1, 2) = 2$ 的倍数，但具体结构非常复杂。
程序化系统搜索结果：
- 1 个长度为 1 的循环 (零状态) （程序运行时懒得处理全零状态了，于是直接忽略了）
- 2 个长度为 6 的循环
- 1 个长度为 3 的循环
- 总循环个数 = 1 + 2 + 1 = 4 个
  总结如下：

LCM是什么

LCM即Least Common Multiple，最小公倍数
LCM 在分析由可约多项式驱动的LFSR行为时，是计算其最终周期的核心数学工具

把LFSR看作一个由多个“小齿轮”组成的复杂钟表：

因式分解 = 拆解钟表 当我们对一个可约多项式 $P (x)$ 进行因式分解，得到 $P (x) = P_{1} (x) \cdot P_{2} (x) \cdot \dots$ 时，我们实际上是在将一个复杂的LFSR系统“拆解”成多个更小的、由不可约多项式 $P_{i} (x)$ 驱动的虚拟“子系统”。
阶 (Order) = 小齿轮的齿数 我们已经知道，每一个不可约的“零件” $P_{i} (x)$ 都有其自身的循环周期，我们称之为“阶”，记作 $e_{i} $ 。您可以把 $e_{i} $ 想象成第 $i$ 个小齿轮的齿数。例如， $齿轮 1$ 有 $e_{1} $ 个齿，转 $e_{1} $ 圈回到原位； $齿轮 2$ 有 $e_{2} $ 个齿，转 $e_{2} $ 圈回到原位。
LCM = 所有齿轮同时归位的时间 整个LFSR的完整状态，是由所有这些虚拟“子系统”的状态组合而成的。整个系统的状态要回到初始状态，就必须满足一个条件：所有的小齿轮必须同时回到它们的初始位置。
这个“同时归位”的最短时间点，正是所有齿轮齿数（即所有阶 $e_{i} $ ）的最小公倍数。

所以，LCM 在流密码分析中的作用就是：

通过计算LFSR各个“子系统”周期的最小公倍数，来确定整个系统状态回归原点所需的最大周期长度。

假设我们有一个7位的LFSR，其多项式 P(x) 是可约的，分解后得到两个不可约因子：

$P_{1} (x)$ ：一个3次不可约多项式，我们算出它的阶 $e_{1} = 7$ 。
$P_{2} (x)$ ：一个4次不可约多项式，我们算出它的阶 $e_{2} = 15$ 。

那么，由这个7位LFSR产生的密钥流，其周期 T 是多少？
$T = L C M (e_{1} , e_{2} ) = L C M (7, 15)$
因为 7 和 15 互质，所以它们的最小公倍数是 7×15=105。
结论：这个7位LFSR产生的密钥流会每隔 105 位重复一次。

程序测试 && 代码展示

4位LSFR程序测试结果如下

7位可约LSFR测试如下

测试代码如下：

from CrypTookitSY.Stream.lsfr import StreamCipherV2 as StreamCipher

from colorama import init, Fore, Style
init(autoreset=True)
from loguru import logger
from collections import defaultdict

from rich import console
console = console.Console()
cprint = console.print
rprint = console.rule
from rich.rule import Rule

def padding(text, length, padding: str = " "):
    return padding * (length - len(text)) + text
def padding_zero(text, length):
    return padding(text, length, "0")
def bin_then_padding_zero(num, length):
    binstr = bin(num)[2:]
    return padding_zero(binstr, length)

def universal_text_nbitwidth_lsfr(polynomal: int, bits: int):
    rprint(f"{bits}位LSFR测试, 多项式为{bin_then_padding_zero(polynomal, bits)}, 遍历所有状态")
    
    sc = StreamCipher(0, polynomal, bits)
    # 0只是占位的
    visited_states = set()
    expected_max_rounds = 2 ** bits - 1 # 单次遍历最大轮数
    num_of_succeeded_round = 0 # 成功的循环的数目
    num_of_failed_round = 0 # 失败的循环的数目
    all_succeeded_round = defaultdict(int)
    for state in range(0, expected_max_rounds + 1, 1):
        if state == 0: 
            rprint(f"[bold red]忽略全零的初始状态！[/bold red]")
            continue
        if state in visited_states: 
            continue
        
        rounds = 0
        sc.seeds = state # 修正状态
        all_succeeded_round[state] = [state] # 创建一个空的列表用于存储成功循环的状态
        # rprint(f"设置初始状态为: {bin_then_padding_zero(state, 4)}")
        while True: # 开始更新状态
            sc._update()
            # print(f"更新状态为: {bin_then_padding_zero(sc.seeds, 4)}")
            visited_states.add(sc.seeds)
            all_succeeded_round[state].append(sc.seeds)
            rounds += 1
            if sc.seeds == state: # 状态回到初始状态，说明已经遍历完所有状态
                # print(f"{Fore.BLUE}已经遍历完所有状态，共{rounds}轮")
                num_of_succeeded_round += 1
                all_succeeded_round[state].append(state) # 把初始状态也放进去
                break
            if rounds > expected_max_rounds: # 状态序列已经超过理论值，说明已经无法计算出周期长度了
                # print(f"{Fore.RED}已经超过理论值，无法计算出周期长度，请检查参数")
                num_of_failed_round += 1
                del all_succeeded_round[state] # 删除失败的循环
                break
        rounds = 0 # 重置轮数
        sc._reset()
                
    print(f"成功循环的次数为: {num_of_succeeded_round}", end=' ')
    print(f"失败的循环的次数为: {num_of_failed_round}")
    for state, rounds in all_succeeded_round.items():
        rprint(f"初始状态序列为: {bin_then_padding_zero(state, 4)}，多项式实际阶为: {len(rounds) - 2}")
        # 循环长度不包括初态和末态
        print(f"循环序列为: ")
        all_round_join = " -> ".join([bin_then_padding_zero(round, 4) for round in rounds])
        print(all_round_join)

if __name__ == '__main__':
    rprint("开始测试LSFR")
    
    universal_text_nbitwidth_lsfr(0b0101, 4)

遍历2到7位本原多项式如下

2025-10-04T17:08:51.699296+0800 INFO 获得 2-bit 本原多项式为: 111
2025-10-04T17:08:51.701217+0800 INFO 获得 3-bit 本原多项式为: 1011
2025-10-04T17:08:51.702442+0800 INFO 获得 3-bit 本原多项式为: 1101
2025-10-04T17:08:51.704147+0800 INFO 获得 4-bit 本原多项式为: 10011
2025-10-04T17:08:51.705116+0800 INFO 获得 4-bit 本原多项式为: 11001
2025-10-04T17:08:51.707062+0800 INFO 获得 5-bit 本原多项式为: 100101
2025-10-04T17:08:51.708122+0800 INFO 获得 5-bit 本原多项式为: 101001
2025-10-04T17:08:51.709238+0800 INFO 获得 5-bit 本原多项式为: 101111
2025-10-04T17:08:51.711680+0800 INFO 获得 5-bit 本原多项式为: 110111
2025-10-04T17:08:51.713770+0800 INFO 获得 5-bit 本原多项式为: 111011
2025-10-04T17:08:51.720664+0800 INFO 获得 5-bit 本原多项式为: 111101
2025-10-04T17:08:51.722909+0800 INFO 获得 6-bit 本原多项式为: 1000011
2025-10-04T17:08:51.723984+0800 INFO 获得 6-bit 本原多项式为: 1011011
2025-10-04T17:08:51.725066+0800 INFO 获得 6-bit 本原多项式为: 1100001
2025-10-04T17:08:51.726570+0800 INFO 获得 6-bit 本原多项式为: 1100111
2025-10-04T17:08:51.728203+0800 INFO 获得 6-bit 本原多项式为: 1101101
2025-10-04T17:08:51.729300+0800 INFO 获得 6-bit 本原多项式为: 1110011
2025-10-04T17:08:51.731207+0800 INFO 获得 7-bit 本原多项式为: 10000011
2025-10-04T17:08:51.732716+0800 INFO 获得 7-bit 本原多项式为: 10001001
2025-10-04T17:08:51.734247+0800 INFO 获得 7-bit 本原多项式为: 10001111
2025-10-04T17:08:51.735597+0800 INFO 获得 7-bit 本原多项式为: 10010001
2025-10-04T17:08:51.737122+0800 INFO 获得 7-bit 本原多项式为: 10011101
2025-10-04T17:08:51.738626+0800 INFO 获得 7-bit 本原多项式为: 10100111
2025-10-04T17:08:51.740145+0800 INFO 获得 7-bit 本原多项式为: 10101011
2025-10-04T17:08:51.741231+0800 INFO 获得 7-bit 本原多项式为: 10111001
2025-10-04T17:08:51.742379+0800 INFO 获得 7-bit 本原多项式为: 10111111
2025-10-04T17:08:51.743664+0800 INFO 获得 7-bit 本原多项式为: 11000001
2025-10-04T17:08:51.745501+0800 INFO 获得 7-bit 本原多项式为: 11001011
2025-10-04T17:08:51.746655+0800 INFO 获得 7-bit 本原多项式为: 11010011
2025-10-04T17:08:51.747580+0800 INFO 获得 7-bit 本原多项式为: 11010101
2025-10-04T17:08:51.748895+0800 INFO 获得 7-bit 本原多项式为: 11100101
2025-10-04T17:08:51.750112+0800 INFO 获得 7-bit 本原多项式为: 11101111
2025-10-04T17:08:51.751550+0800 INFO 获得 7-bit 本原多项式为: 11110001
2025-10-04T17:08:51.752558+0800 INFO 获得 7-bit 本原多项式为: 11110111
2025-10-04T17:08:51.753852+0800 INFO 获得 7-bit 本原多项式为: 11111101

爆破代码如下：

def bppv2(start: int = 2, stop: int = 8, step: int = 1):
    # ...
    for bits_width in range(start, stop, step): # bits_width 仍然代表 LFSR 的长度 n
        expected_max_rounds = 2 ** bits_width - 1
        rprint(f"爆破 {bits_width} 位的本原多项式, 期待周期为 {expected_max_rounds}")
        
        # 搜索 n 次多项式，其表示需要 n+1 位
        # 范围是从 2**n 到 2**(n+1) - 1
        for polynomial in range(2**bits_width, 2**(bits_width + 1)):
            
            # 优化：一个 n 次多项式，x^n 项必须存在（我们的范围保证了这一点）
            # 同时 x^0 (+1) 项也必须存在，否则可被x整除。
            # 这意味着多项式整数必须是奇数。
            if polynomial % 2 == 0:
                continue

            sc = StreamCipher( # 使用您最新的 V2 类
                seeds=1,
                polynomial=polynomial,
                length=bits_width
            )
            
            # 您已经确认 period 会被正确计算
            if sc.period == expected_max_rounds:
                # n 次多项式用 n+1 位二进制表示
                poly_bin_str = bin(polynomial)[2:]
                rprint(f"[bold green]获得 {bits_width} 次本原多项式为: {poly_bin_str}[/bold green]")
                logger.info(f"获得 {bits_width}-bit 本原多项式为: {poly_bin_str}")

思考程序实现的逻辑问题

注意

上面的分析不代表具体的程序实现

看起来搞错的话只影响文档表述，不影响程序行为……但真的是这样吗？
大的要来了！

注

这涉及多项式掩码与数学上的特征多项式的联系，具体请跳转到下下个六级标题LSFR位宽与多项式次数的联系

写稿的时候直到这个小标题，流密码生成器的LSFR长度自动计算逻辑都没能完全确定下来

我选用了两个多项式
前者是第二版（区分LSFR长度与多项式长度）爆破出来的多项式：

后者用的是第一版（也就是搞错LSFR长度与多项式长度）爆破出来的多项式：

两者都在LSFR长度为7时（其中，前者在LSFR长度为6时正常工作，并得到周期为63）下进行状态遍历，前者错误地产生了多个小状态，后者则运行良好
也就是说，我第一版遍历出来的多项式只能给V2用（而且要重新设计周期计算逻辑），而第二版遍历出来的标准本原多项式在使用时必须对输入的比特位进行减一操作

让我们看看V2实现发生了什么……好吧，我把多项式长度当成寄存器长度了
虽然我手动给__init__加了length参数，但毕竟防呆不防傻……

（所使用的本原多项式是6 bits的0b1100111）

临时打一下补丁

重新审视位运算逻辑

打了补丁但没有手动指定LSFR长度的V2会得到1785周期，基于V2完全重构的V4无论是否指定LSFR长度都会得到错误的数据（还会带着V2一起错），而且V4得到的周期还是1785的两倍

为什么周期恰好是两倍关系？
我猜可能是V4用了和V2一样的LSFR长度计算逻辑，但V4同时还更新了字节序，并且错误地在字节序更新前就已经计算好LSFR长度

但V3就没有出现这样的问题，因为V3是Qwen写的，不是我写的……
所以，LSFR长度不能只看多项式位宽或只看状态位宽……
修改之后复现伽瓦罗bug：

等会，我用了大端序，这将反转多项式产生一个……额，也是不可约多项式（确切地说是伽瓦罗）

bits_15_pri_ploy = 0b1010000000010001
# 反转之后得到1000100000000101
sc4 = SCV4(1, bits_15_pri_ploy, order="big")

（V2还没修，所以V2还是错的）

那么为什么0b1010000000010001的字符串倒转版本不是本原多项式呢？

倒数定理该如何理解？

“倒数定理”是成立的，但它的应用比“把字符串倒过来”要微妙一些。

当我们为16位的LFSR选择一个多项式时，实际上是在定义一个16次的特征多项式 (Characteristic Polynomial)。

代码中 length=16 显式指定了LFSR的长度，也隐含了特征多项式的最高次项是 $x^{1} 6$ 。
程序所传入的 polynomial 整数（掩码）0b1010000000010001 代表了多项式的其余部分。这个掩码对应的是：
$P_{m a s k } (x) = x^{15} + x^{13} + x^{4} + 1$
因此那个能产生65535周期的、完整的本原多项式实际上是：
$C (x) = x^{16} + P_{m a s k} (x) = x^{16} + x^{15} + x^{13} + x^{4} + 1$

倒数定理说的是，上面这个 16次的 C(x) 的倒数多项式 $C^{*} (x)$ 也一定是本原的。

一个 $n 次多项式 P (x)$ 的倒数 $P^{*} (x)$ 的数学定义是 $x^{n} \times P (\frac{1}{x})$ 。我们来计算一下：

C^{*} (x) = x^{16} \cdot C (\frac{1}{x})

C^{*} (x) = x^{16} \cdot ((\frac{1}{x})^{16} + (\frac{1}{x})^{15} + (\frac{1}{x})^{13} + (\frac{1}{x})^{4} + 1)

C^{*} (x) = (x^{16} \cdot x^{16} \cdot 1 ​) + (x^{16} \cdot x 15 \cdot 1 ​) + (x^{16} \cdot x^{13} \cdot 1 ​) + (x^{16} \cdot x^{4} \cdot 1 ​) + (x^{16} \cdot 1)

C^{*} (x) = 1 + x + x^{3} + x^{12} + x^{16}

重新排列一下：

C * (x) = x^{16} + x^{12} + x^{3} + x + 1

倒数定理保证了上面这个 C∗(x) 也是一个16次的本原多项式。

而前面大端序对多项式的字符串形式反转，实际上并不是计算数学上的倒数多项式，

我们拿来的是代表 $P_{m a s k} (x)$ 的16位掩码 1010000000010001。
将这个字符串反转，得到了 1000100000000101。
这个新的掩码对应的多项式是 $$P_{mask}′(x)=x^{15}+x+x^{2}+1$$
当我们用这个新掩码去测试时，我们实际上是在测试一个新的特征多项式： $C' (x) = x^{16} + P_{m a s k}' (x) = x^{16} + x 15 + x 11 + x 2 + 1$

现在对比一下：

数学上真正的倒数: $C^{*} (x) = x^{16} + x^{12} + x^{3} + x + 1$
我们通过反转掩码得到的: $C^{'} (x) = x^{16} + x^{15} + x^{11} + x^{2} + 1$

这两个多项式完全不同！

倒数定理保证了 C∗(x) 是本原的，但它并不保证我们通过反转掩码字符串得到的那个新多项式 C′(x) 也是本原的。 实验结果（它不是本原的）是正确的，恰好证明了“反转掩码字符串”这个操作与“求倒数多项式”在数学上是两回事。
这有点像在说“一个数字的倒数”。数字12的倒数是1/12。但如果我们只看它的个位数2，然后把2这个字符翻转过来（比如镜面翻转成5），得到的新数字5与1/12毫无关系。
我们反转的是“零件”（掩码），而定理说的是“整体”（完整的特征多项式）的属性。

LSFR位宽与多项式次数的联系

所以，为什么不减一呢？

这便是接下来需要辨析的程序中的“多项式掩码”和数学上的“特征多项式”之间的关系。

在整个LFSR的模拟中，我们实际上在和两个不同层面的“多项式”打交道：

数学上的“特征多项式” (Characteristic Polynomial)
- 这是我们在论文或教科书中看到的完整形式，例如 $$C(x)=x^{16}+x+x^{13}+x+1$$
- 它的次数是 16次。
- 它的二进制表示需要 17位 (0b11010000000100011，如果完整表示的话)。（在已经删除的文案中，用于演示的代码所使用的多项式正是掩码，而非特征多项式）
- 对于这个特征多项式，我们此前的结论（给StreamCipherV2打补丁时；StreamCipherV2不是FiLSFRV2） LFSR长度 = 它的位宽 - 1 是完全正确的。
程序中的“反馈掩码” (Feedback Mask)
- 这是我们代码中的 self.polynomial 变量。
- 它的作用是什么？是与一个与之等位宽（在这里是16位）的状态 self.seeds 进行 & 运算。
- 因此，这个掩码本身有意义的部分也只有 16位。它实际上只代表了特征多项式中，除了最高次项 $x^{16}$ 之外的所有部分。
- 对于上面的例子，它在代码中对应的polynomial掩码就是 0b1010000000010001。
- 这个掩码的 bit_length() 是 16。

注意

写到这里的时候，在程序实现中，LSFR长度就是多项式长度——这个实现是错误的，但是我当时没写单元测试，所以没发现这个问题

所以……下面的分析其实是错误的……

现在，关键点来了：
（最新的）程序推断LFSR长度时，使用的依据是程序中的“反馈掩码”，而不是数学上的“特征多项式”。

对于一个 n 位的LFSR，其反馈掩码的位宽最大就是 n
因此，没有指定 length 时，通过 polynomial.bit_length() 来获取掩码的位宽，并以此作为LFSR的长度 n，是一个非常合理且正确的工程推断

现在我们就能解释为什么V4正确而V2错误了：

V4 的逻辑 (正确):
```
self.lsfr_bitwidth = ... else max(self.seeds.bit_length(), self.polynomial.bit_length())
```
- 当传入 polynomial=0b1010000000010001 时，polynomial.bit_length() 是 16。
- max(...) 正确地将 lsfr_bitwidth 设置为 16。
- 结果：一个16位的LFSR配上一个16位的有效掩码，完美匹配，周期为65535。
V2 的逻辑 (错误):
```
# 打的补丁就是这个多项式长度-1
self.lsfr_bitwidth = ... else (polynomial.bit_length() - 1)
```
- 当传入同一个polynomial时，polynomial.bit_length() 是 16。
- 16 - 1 导致 lsfr_bitwidth 被错误地设置为了 15。
- 结果：一个15位的LFSR配上一个16位的掩码，尺寸错配，数学结构被破坏，周期为 1785。

因此“为什么不是多项式长度减1”的答案是：

因为我们在代码中用来推断的“多项式长度”，是“反馈掩码”的位宽，而不是“特征多项式”的位宽。对于一个n位的LFSR，其掩码的合理位宽就是n，因此直接使用 polynomial.bit_length() 是正确的。

而之前的V2补丁之所以出错，是因为它错误地将适用于“特征多项式”的 位宽-1 规则，用在了“反馈掩码”上。而V4（以及AI给的V3）所采用的多项式位宽等同于LSFR长度 逻辑，则正确地处理了程序实现层面的变量关系。

别急，还有反转！

LSFR位宽之谜（二）

改回多项式长度-1时单元测试符合预期，但是标准周期计算又炸了

我真是服了呀

def _update_state_v4(sc_inst: StreamCipher) -> int:
    self = sc_inst  # 改一下变量命名，以兼容提取出的代码
    output_key_bit = self.seeds & 1  # 取出最低位作为输出
    # 计算新的状态比特
    temp_bits = self.polynomial & self.seeds
    # 然后进行奇偶校验
    next_state_single_bit = temp_bits.bit_count() % 2  # 用于构成下一个状态的新比特
    next_state_bits = (self.seeds >> 1) | (
        next_state_single_bit << (self.lsfr_bitwidth - 1)
    )
    # 更新状态比特
    self.seeds = next_state_bits
    return output_key_bit

妈的可算是改完了

不同类型的LSFR

線性反饋移位暫存器（LFSR）主要有兩種經典的架構或「類型」：

斐波那契LFSR (Fibonacci LFSR)
伽羅瓦LFSR (Galois LFSR)

教材上主要是前者

斐波那契LSFR的核心思想是外部反馈，可以將其工作模式理解為「先計算，再注入」
工作流程比喻 (傳送帶模型):

檢查 (Inspect)：在傳送帶（暫存器）移動前，幾個預設的感測器（抽頭）會讀取對應位置上物品的狀態（0或1）。
計算 (Calculate)：所有感測器的讀數被送到一個外部的中央計算器（XOR邏輯），計算出一個新的物品狀態。
移位 (Shift)：傳送帶整體移動一格，最末端的物品掉出（成為輸出位）。
注入 (Inject)：剛剛計算出的新物品被放到傳送帶空出來的最前端。

伽罗瓦LFSR也能產生完全相同的最大長度序列，但它的工作方式非常不同

核心思想: 內部反饋 (Internal Feedback)。
- 可以將其工作模式理解為「先移位，再（有條件地）異或」。
工作流程比喻 (內部聯動模型):
1. 移位和輸出 (Shift & Output)：傳送帶首先整體移動一格，最末端的物品掉出（成為輸出位）。最前端空出一個位置，並總是先放上一個0。
2. 內部聯動 (Internal Feedback)：檢查剛剛掉出去的那個物品。
  - 如果掉出去的是 1：那麼傳送帶上所有“抽頭”位置的物品，會就地與1進行一次異或（即狀態翻轉，0變1，1變0）。
  - 如果掉出去的是 0：則什麼也不發生。

一些重要结论如下：

數學等價性: 對於同一個n次本原多項式，斐波那契LFSR和伽羅瓦LFSR（使用其倒數多項式）產生的序列內容是完全相同的（都是m序列），僅僅是相位不同（即序列的起始點錯開了幾位）。
性能差異: 在硬體和軟體實現中，伽羅瓦結構通常被認為具有輕微的性能優勢。

LSFR与多项式类型不匹配时会发生什么

根据维基百科所述，LSFR基础核心结构只有斐波那契LSFR和伽罗瓦LSFR两种，其他更复杂的LSFR都是由这两种结构组合而来的
相对的，基础的本原多项式也有两种，分别对应斐波那契LSFR（以下简称F）和伽罗瓦LSFR（以下简称GF）。两者在密码学上是等价的，对于同一个 $n 次本原多项式$ ，F和GF都能产生 $m 序列$ ，二者仅仅是相位不同

若把一個n位的LFSR看作一個向量，则每一次的 _update 操作，都可以用一個 $n \times n$ 的狀態轉移矩陣 (State Transition Matrix) T 來表示

S t a t e_{k + 1} = T \cdot S t a t e_{k}

這意味著，LFSR產生的整個狀態序列，就是初始狀態向量在矩陣 T 的不斷乘以作用下的結果：

S_{0}, T \cdot S_{0}, T^{2} \cdot S_{0}, T^{3} \cdot S_{0}, . . .

多項式 $P (x)$ 實際上是這個狀態轉移矩陣 T 的特征多项式 (Characteristic Polynomial)。多項式的數學屬性（如是否本原）直接決定了矩陣 T 的屬性（如其循環長度）
现在，對於同一個數學多項式 $P (x)$ ：

斐波那契LFSR：我們可以構建出一個與之對應的狀態轉移矩陣，稱之為 $T_{f}$ 。這個 $T_{f}$ 是一個標準的友矩陣 (Companion Matrix)。
伽羅瓦LFSR：我們也可以構建出它的狀態轉移矩陣 $T_{g}$ 。易证得，這個 $T_{g}$ 恰好是斐波那契矩陣 Tf 的轉置矩陣 (Transpose Matrix)。
在線性代數中有一個基本定理：一個矩陣和它的轉置矩陣，擁有完全相同的特徵多項式。
這便是兩者的數學聯繫！

因為 $T_{f}$ 和 $T_{g}$ 擁有共同的特徵多項式 $P (x)$ 。
如果 $P (x)$ 是本原的，它所定義的循環長度是 $2^{n} - 1$ 。
那麼，由 $T_{f}$ 和 $T_{g}$ 驅動的兩個系統，它們的最大週期必然是完全相同的！
本原多项式的循环长度决定了理想情况下，F和GF型LSFR都能遍历全部状态，只是遍历路径可能不完全一致罢了：
狀態序列 (State Sequence): 兩種LFSR遍歷所有狀態的順序不同。
輸出序列 (Output Sequence): 由於輸出位是從每個狀態中提取的，狀態的順序不同，導致輸出位的序列也不同。
相位差異 (Phase Difference): 易证得 ，這兩條不同的輸出序列，其中一條必定是另一條的循環移位 (cyclic shift)。也就是說，伽羅瓦產生的序列 ...c, d, e, f...，一定可以在斐波那契產生的無限序列 ...a, b, c, d, e, f, g, h... 中找到完全一樣的片段。它們本質上是同一首歌，只是從不同的小節開始唱而已。

说完了理论，那么如何实操呢？

之前的小节中已经演示过如何计算倒数多项式，公式是$$P^*(x) =x^n P (\frac{1}{x})$$
而F与GF型LSFR的本原多项式正好互为倒数
那么，应该如何将这一过程变成程序代码呢？

如何程序化多项式倒数计算

我们的目标是证明：“求倒数多项式”在数学上的操作，等价于“将多项式的整数表示进行比特反转”

首先选择一个具体的例子，比如一个4次本原多项式—— $P (x) = x^{4} + x + 1$ 作为演示
之前已经（左脑反驳右脑地写代码）推导过n次本原多项式需要n+1比特位宽来表示，那么这里的 $P (x)$ 的比特位宽便是 $5$ ，表示成我们的代码可以识别的版本就是0b10011

P (x) = 1 \cdot x^{4} + 0 \cdot x^{3} + 0 \cdot x^{2} + 1 \cdot x^{1} + 1 \cdot x^{0}

接下来计算 $P (\frac{1}{x})$ ：

P (\frac{1}{x}) = \frac{1}{x^{4}} + \frac{1}{x} + 1

然后乘上 $x^{4}$ ：

P^{*} (x) = x^{4} \cdot \frac{1}{x^{4}} + x^{4} \cdot \frac{1}{x^{1}} + x^{4} \cdot 1

P^{*} (x) = x^{4} + x^{3} + 1

转回二进制表示为：0b11001
现在我们来比较原始多项式和倒数多项式的二进制表示：

原始多项式 $P (x) = x^{4} + x + 1$
- 完整形式: $$P(x) = 1 \cdot x^4 + 0 \cdot x^3 + 0 \cdot x^2 + 1 \cdot x^1 + 1 \cdot x^0$$
- 系数序列: (1, 0, 0, 1, 1)
- 二进制表示: 10011
倒数多项式 P∗(x)=x4+x3+1
- 完整形式: $$P(x) = 1 \cdot x^4 + 1 \cdot x^3 + 0 \cdot x^2 + 0 \cdot x^1 + 1 \cdot x^0$$
- 系数序列: (1, 1, 0, 0, 1)
- 二进制表示: 11001
  显然，11001 正是 10011 的完全反转！

这个规律并非巧合。让我们看看一个通用的项 $a_{k} x^{k}$ 在求倒数的过程中发生了什么：

在 $P (x)$ 中，它贡献了系数 $a_{k}$ 在第 $k$ 次幂的位置上。
代入 $\frac{1}{x}$ 后，它变成 $a_{k} (\frac{1}{x})^{k} = \frac{a_{k}}{x^{k}}$ 。
乘以 $x^{n}$ 后，它变成 $x^{n} \cdot \frac{a_{k}}{x^{k}} = a_{k} x^{n - k}$ 。
这意味着，原始多项式中 $x^{k}$ 项的系数 $a_{k}$ ，在倒数多项式中跑到了 $x^{n - k}$ 项的位置。系数的位置从 k 变成了 n-k。
对于一个长度为 n+1 的比特序列（索引从0到n），将索引 k 的比特移动到索引 n-k 的位置，这正是比特反转操作的定义！

流密码：薄弱在哪里

主要弱点：线性
这是单个或多个的LFSR线性组合的最根本、最致命的缺陷，也是所有其他问题的根源。
- 薄弱點描述:
  LFSR的整个行为可以用一组简单的线性方程来描述。具体来说，输出密钥流的每一位，都是其内部状态各位元的线性组合（即异或和）。
- 后果:
  这种线性关系使得整个序列变得可预测。攻击者不需要猜测您的初始种子，他们可以通过代数方法直接“解方程”，反推出LFSR的结构。
- 对应的攻击技术: Berlekamp-Massey 算法
  - 这是针对所有线性序列的“银色子弹”。
  - 攻击原理: 只要攻击者能截获一小段连续的密钥流（对于一个n位的LFSR，理论上只需要 2n 位的密钥流），这个算法就能在极短的时间内，高效地计算出这个LFSR的反馈多项式
  - 攻击效果: 一旦多项式被反推出来，攻击者就拥有了和您完全一样的密钥流生成器。他可以同步地生成过去和未来的所有密钥流，您的加密瞬间被完全破解。
使用模式弱点：密钥流复用 (Keystream Reuse)
这个弱点是所有（不带认证的）流密码的通病，但在简单的LFSR上体现得尤为直接。
- 薄弱點描述:
  使用完全相同的密钥流（即相同的种子和多项式）去加密两条或多条不同的明文。这种情况被称为“两次使用一密 (Two-Time Pad)”。
- 后果:
  攻击者可以将两段密文进行异或，从而完全消除密钥流，直接得到两段明文的异或结果。 $C_{1} = P_{1} \oplus K$ $C_{2} = P_{2} \oplus K$ $C_{1} \oplus C_{2} = (P_{1} \oplus K) \oplus (P_{2} \oplus K) = P_{1} \oplus P_{2} $
- 对应的攻击技术: 统计分析与密文对比攻击 (Crib-Dragging)
  - 攻击原理: 攻击者拿到了 P1⊕P2。如果他们能猜到其中一段明文的一部分（例如，文件头"HTTP/"、英文常用词" the "），他们就可以通过这个已知的“小抄 (crib)”去滑动比对，逐步还原出另一段明文的内容。
  - 攻击效果: 即使不知道密钥，攻击者也能在很大程度上恢复出两条明文的内容。
结构性弱点：延展性 (Malleability)
您的LFSR流密码只提供了保密性，完全没有提供完整性 (Integrity) 保护。
- 薄弱點描述:
  由于加密就是简单的逐位异或，攻击者可以在不知道明文内容的情况下，对密文进行可预测的篡改。
- 后果:
  攻击者可以精确地翻转密文中的某个位元，从而导致解密后的明文中对应的位元也被翻转。
  Pdecr′=Cenc′⊕K=(Cenc⊕1)⊕K=(Penc⊕K⊕1)⊕K=Penc⊕1
- 对应的攻击技术: 比特翻转攻击 (Bit-Flipping Attack)
  - 攻击原理: 攻击者拦截了一段密文，虽然他看不懂，但他知道其中某几位可能对应着关键信息（例如，转账金额、指令代码）。他只需将密文中的这几位进行翻转（C_i = C_i \oplus 1），接收方在解密后，对应的明文位也会被翻转。
  - 攻击效果: 攻击者可以随心所欲地篡改传输的消息内容，造成严重后果（例如，将“转账给Alice 100元”改成“转账给Eve 900元”）。
配置性弱点：周期过短 (Short Period)

你猜猜为什么文案里的代码演示从V2、V3到V4，一直到现在的FiLSFR，始终在重构

薄弱點描述:
错误地选用了一个非本原或可约的多项式。
后果:
密钥流会在很短的时间内开始重复。一旦重复，其后续所有序列都变得完全可知。
对应的攻击技术: 频率分析 / 统计攻击
- 攻击原理: 攻击者收集足够长的密文，通过分析其统计规律，可以发现密钥流的周期。一旦周期被确定，破解难度就大大降低。
- 攻击效果: 相当于将一个长密钥问题，降级成了一个短密钥问题。

针对线性LSFR的 $B e r l e k a m p - M a s s e y 算法$

代码实现

def simple_bm_attack():
    # --- 1. 生成目标密钥流序列 ---
    # 使用一个已知的3次本原多项式 x³ + x + 1 (0b1011)
    sc = FibornacciLSFRCore(seed=0b1, polynomial=0b1011)
    
    # 根据Berlekamp-Massey算法，需要 2*L 的序列长度
    # L 是LFSR的真实长度，这里是 sc._degree = 3
    max_length = sc._degree * 2 
    
    sc_key_gen = sc.keys(max_length) # 假设 keys() 返回生成器
    keys = list(sc_key_gen)
    
    print(f"目标LFSR长度 L=3, 多项式 C(x)=x³+x+1")
    print(f"截获的 2L={max_length} 位密钥流: {keys}")
    
    # --- 2. Berlekamp-Massey 算法初始化 ---
    # 跳过开头的0 (在这个例子中没有)
    key_idx = 0
    while key_idx < len(keys) and keys[key_idx] == 0:
        key_idx += 1
    
    if key_idx == len(keys):
        print("序列全为0，无法分析。")
        return

    # C(x) - 当前的连接多项式
    Cx = {key_idx + 1, 0}
    # L - 当前的LFSR长度
    curr_length = key_idx + 1
    
    # B(x) - “仓库”里上一个版本的连接多项式
    Bx = {0}
    # m - 上一次“大修正”时的时间点
    m = key_idx
    # b - 辅助变量，记录“延时”
    b = 0

    # --- 3. 主循环：迭代处理序列 ---
    for n in range(key_idx + 1, max_length):
        # n 是当前正在处理的位元的索引
        
        # --- 步骤 1: 做出预测 ---
        # 预测 s[n] 的值
        prediction = 0
        # 根据 C(x) = 1 + c₁x + c₂x²...
        # 预测公式是: s[n] = c₁s[n-1] + c₂s[n-2] + ...
        for i in Cx:
            if i != 0: # x⁰=1 项不参与抽头
                prediction ^= keys[n - i]
        
        # --- 步骤 2: 计算差异 (Discrepancy) ---
        # 差异 d = 真实值 ⊕ 预测值
        discrepancy = keys[n] ^ prediction
        
        # --- 步骤 3: 根据差异决定是否修正 ---
        if discrepancy == 1: # 预测错误！需要修正
            # 拷贝一份 C(x) 以备后用
            Cx_old = Cx.copy()
            
            # --- 核心修正公式 ---
            # C_new(x) = C(x) + B(x) * x^(n-m)
            # 集合表示: Cx_new = Cx ^ {item + n - m for item in Bx}
            delay = n - m
            correction_term = {item + delay for item in Bx}
            Cx ^= correction_term # 利用set的对称差集运算模拟GF2上的加法
            
            # --- 步骤 4: 判断是否需要增加LFSR长度 L ---
            if curr_length <= n / 2:
                # 是时候进行“大修正”了
                # 更新 L
                curr_length = n + 1 - curr_length
                # 更新“仓库”和“时间点”
                m = n
                Bx = Cx_old
    
    # --- 4. 攻击结束，输出结果 ---
    # 为了与您的LFSR实现约定一致，我们找到的多项式是P(x)
    # 特征多项式 C(x) = 1 + P(x)
    # 所以 P(x) = C(x) - 1，即从集合中去掉0
    # Cx.discard(0)
    # 不要去掉, 这一项可以用于判断多项式次数 
    
    # 将集合 {2, 3} 转换为整数 0b1011
    reconstructed_poly = 0
    for i in Cx:
        reconstructed_poly |= (1 << i)
    reconstructed_poly |= (1 << curr_length) # 加上最高位的 x^L 项

    print(f"\n攻击完成:")
    print(f'反推得到的连接多项式 C(x) (次幂集合): {Cx}')
    print(f'反推得到的LFSR长度 L: {curr_length}')
    print(f'重构出的特征多项式 (整数): {bin(reconstructed_poly)}')
    
    rev_reconstructed_poly = reverse_polynomial(reconstructed_poly, curr_length)
    print(f'重构出的特征多项式倒数 (整数): {bin(rev_reconstructed_poly)}')

提示

Gemini写的，我反正没看懂

算法原理 && 算法步骤

BM演算法要解决的核心是：
给定一个（时序敏感）二进制序列 $s_{0}, s_{1}, s_{2}, . . ., s_{n - 1}$ ，找到一个能够生成这个序列的最短的线性反馈移位寄存器
「找到最短的LFSR」等價於找到兩樣東西：

最短的長度 L: 我們稱之為序列的线性复杂度 (Linear Complexity)。
對應的特征多项式 C(x): 這個多項式定義了LFSR的反馈逻辑。

演算法維護幾個關鍵變數，並在讀取序列的第 k 個位元時進行更新：

C(x): 當前猜測的連接多項式。
L: 當前猜測的LFSR長度。

对于一个长度为 L 的 LFSR，其特征多项式为 $C (x) = 1 + c_{1} x + c_{2} x^{2} + . . . + c_{L} x^{L}$ ，序列 $s_{0}, s_{1}, s_{2}, . . .$ 中的每一项 $s_{n} (当 n \geq L 时)$ 都满足以下关系：$$s_n = c_1s_{n-1} + c_2s_{n-2} + ... + c_L*s_{n-L}$$
在 GF(2)（二进制域）中，加法就是异或（XOR），所以上式变为：$$s_n = s_{n-1} & c_1 ⊕ s_{n-2} & c_2 ⊕ ... ⊕ s_{n-L} & c_L$$
（这里 & 是逻辑与，⊕ 是异或。 $c_{i}$ 是 0 或 1，代表对应位置是否有反馈抽头）
m: 上一次更新L時，我們讀到了第幾個位元。
B(x): 上一次更新L時，舊的C(x)是什麼樣的。

在處理第 k 個位元 sk 時，演算法執行以下四步：

第一步：計算“差異” (Discrepancy) 演算法用當前的LFSR模型（由 L 和 C(x) 定義）來計算一個“預測值”。然後，計算這個預測值與真實值 sk 之間的差異 d。在GF(2)域中，這個差異就是異或：
$d = s_{k} \oplus (p r e d i c t i o n)$
- 如果 d = 0，預測正確。
- 如果 d = 1，預測錯誤。
而在最开始，我们什么都不知道，就做一个最简单的猜测：这个序列是全零序列，由一个长度为0的LFSR生成。此时 $L = 0, C (x) = 1$ ;
接下来算法逐个读取序列中的比特 $s_{0}, s_{1}, s_{2}, . . .$ 。在每一步 n，它用当前的 $(L, C (x))$ 来预测 $s_{n}$ 的值。
第二步：如果預測正確 (d = 0) 什麼都不用做。當前的LFSR模型仍然可以解釋到目前為止的所有序列。繼續處理下一個位元。
第三步：如果預測錯誤 (d = 1) 這一步是演算法的精髓。我們需要更新我們的多項式 C(x) 來修正這個錯誤。BM演算法的絕妙之處在於，它使用上一次犯錯時的狀態來幫助修正這一次的錯誤。
新的多項式 $C_{n e w } (x)$ 這樣計算：
$C_{n e w} (x) = C_{o l d} (x) \oplus x_{k - m} \cdot B (x)$
- 直觀解釋:
  - C(x) 是我們當前這個“不完美”的模型。
  - B(x) 是我們“倉庫”裡存著的、上一個被證明不夠用的舊模型。
  - x^{k-m} 是一個“延遲”項，它將舊模型 B(x) 的影響“平移”到當前這個出錯的時間點 k 上。
  - 通過將當前模型與這個“經過延遲修正的舊模型”進行異或，我們神奇地得到了一個既能解釋過去所有序列、又能修正當前這個錯誤的新模型。
第四步：是否需要增加LFSR的長度 (L)？ 在修正了多項式之後，演算法還需要決定是否要增加LFSR的長度 L。規則是：
如果當前模型的“好日子”（即連續預測正確的步數）已經過得太久，具體來說是超過了其自身長度的一半，那麼這次的修正就需要一個更長的LFSR才能容納。
數學上的判斷條件是 $2 L <= k$ 。
- 如果需要增加長度:
  1. 更新長度： $L_{n e w} = k + 1 - L_{o l d}$ 。
  2. 更新“記憶”: 由於我們剛剛進行了一次“重大升級”（增加了L），我們需要更新我們的“倉庫”，為下一次可能的重大升級做準備。
    - 將當前這個不完美的 C(x) 存入 B(x)。
    - 記錄下當前的時間點 k 到 m。
- 如果不需要增加長度: 則保持 L 和“倉庫”裡的 B(x), m 不變。

演算法不斷重複這四步，直到讀完所有給定的序列位元。最終得到的 L 和 C(x)，就是能夠生成該序列的最短LFSR的長度和連接多項式。

算法推导

101 -> 110 | 1
110 -> 111 | 0
111 -> 011 | 1
011 -> 001 | 1
001 -> 100 | 1
100 -> 010 | 0
010 -> 101 | 0
FiLSFRDebug: 当前状态[101] 状态转移多项式[1 + x] 特征多项式[1011] 掩码多项式[011] 理论周期[2^3-1=7] 计算周期[7]

对于一个长度为 $L$ 的LSFR，其产生的序列 $s_{0}, s_{1}, s_{2}, . . ., s_{n - 1}$ ，从第 $L$ 位开始的每一位 $S_{n} (n >= L)$ 均可由它前面的 $L$ 位通过一个固定的线性公式计算出来，该公式便是：

S_{n} = \sum_{i = 1}^{L} c_{i} S_{n - i}, 在 G F (2) 域 中

展开后得到

$s_{n}$ : 我们想要预测的序列的第 n 位。
$s_{n - 1 }, s_{n - 2} , \dots$ : 序列中紧挨着它的前 L 位。
$c_{1} , c_{2} , \dots, c_{L} $ : 一组固定的系数（0或1），它们就是LFSR的“基因”，定义了反馈逻辑。
这组系数正是连接多项式(或称状态转移多项式) $P (x)$ 的另一种表现形式。

BM算法并非要 建立一个巨大的方程组然后去求解，而是采用一种迭代的、动态的方式来“逼近”正确的系数 cᵢ

小总结

线性 (可被代数方法破解)
⬇️
Berlekamp-Massey算法 (核心攻击)

流式异或 (无状态、无认证)
⬇️
金鑰流重用 (使用模式漏洞)
比特翻转攻击 (篡改漏洞)

多项式选择 (配置问题)
⬇️
週期过短 (可被统计分析破解)

花絮

stream2 = StreamCipherV2(
            seeds=randint(1, 2 ** 16 - 1),
            polynomial=0b1000010000001000,
            # 末位不可以为0，这会导致多项式可被x整除
            length=16
        )