设为首页收藏本站

开启辅助访问

基于LFSR的流密码的代数攻击

您所在的位置：网站首页 › lfsr是什么 › 基于LFSR的流密码的代数攻击

基于LFSR的流密码的代数攻击

2023-12-26 11:59| 来源: 网络整理| 查看: 265

目录

前言

一. 线性反馈移位寄存器

二.流密码

三. 非线性过滤函数

总结

前言

因为布尔多项式环不是一个整环，所以可以利用此性质来降低非线性多项式的次数。

一. 线性反馈移位寄存器

LFSR: Linear Feedback Shift Register 线性反馈移位寄存器。以一个12比特的线性反馈移位寄存器为例子，初始状态如下：

下一个clock,依据 $s_0^,=s_4+s_6+s_8+s_{11}=0, s^,_1=s_0, s_2^,=s_1,\ldots,s_1^,=s_{10}$ ，可得如下：

反馈函数的通式为： $f(x)=c_0x^{12}+c_1x^{11}+\ldots+c_{11}x+1$ ，在上图中反馈函数为 $f(x)=x^{12}+x^9+x^7+x^5+1$ 。

将LFSR的长度表示为L，当LFSR的输出序列的周期为 $2^L-1$ 时，反馈函数f(x)称为本原多项式。因为非零状态的个数为 $2^L-1$ ，所以LFSR的最大周期只能到达 $2^L-1$ ，这样的序列称为m-sequence。

二.流密码

模仿一次一密加密过程，利用有限的key，生成无限的keystream密钥流： $k_0,k_1,\ldots$ 。

已知明文攻击：攻击者已知明密文对 $(p_1,c_1), (p_2,c_2), \ldots,(p_m,c_m)$

所以可得 $k_1=p_1\bigoplus c_1, k_2=p_2\bigoplus c_2, \ldots, k_m=p_m\bigoplus c_m$

两种解密方法：方法一：从 $k_1,k_2,\ldots,k_m$ 中恢复初始密钥

方法二：从 $k_1,k_2,\ldots,k_m$ 中恢复某一时刻的中间状态 $(s_0,s_1,\ldots,s_{L-1})$ 。有了 $(s_0,s_1,\ldots,s_L-1)$ 可以得到同样的密钥流

结论：只通过LFSR生成密钥流是不安全的。Berlekamp-Massy 算法可以利用2L长的输出序列，以 $O(L^3)$ 的复杂度得到生成这个序列的线性反馈移位寄存器。

三. 非线性过滤函数

在线性反馈移位寄存器中加入非线性结构，如下图：

以 $f(x_1,x_2,x_3,x_4,x_5,x_6)$ 为例，每个clock，从当前状态 $s_0,s_1,\ldots,s_{L-1}$ 中抽取出6个 $(s_{k_1},s_{k_2},s_{k_3},s_{k_4},s_{k_5},s_{k_6})$ ,其中 $k_1,k_2,\ldots,k_6$ 为抽头数。由此可得密钥流：

$KS_i=f(s_{k_1},s_{k_2},s_{k_3},s_{k_4},s_{k_5},s_{k_6})$ 。

线性反馈移位寄存器的更新过程可以看成如下线性变换：

其中 $s_0^,=c_{L-1}s_0+c_{L-2}s_1+\ldots+c_0s_{L-1}$ ， $s_1^,=s_0,s^,_2=s_1,\ldots,s^,_{L-1}=s_{L-2}$ 。

假设 $x_1,x_2,\ldots,x_n$ 为n比特线性反馈移位寄存器某一时刻的中间状态，密钥流可以写成布尔多项式如下：

以下为探讨中间状态恢复问题：

此问题的本质相当于已知密钥流 $b_0,b_1,\ldots,b_{m-1}$ ,求解如下关于 $x_1,x_2,\ldots,x_n$ 的方程组：

在求解此方程中，由于L为线性函数，因此每个单独方程的次数都等于过滤函数f的次数。从此角度出发，要求f的次数足够高，f的非线性度要高。

总结

代数密码分析的本质就是从求解多变元多项式方程组的角度来分析密码算法。密码系统、代数系统、破解密码系统、求解代数系统之间的关系可以表示为如下：

【本文地址】

公司简介

联系我们

CopyRight 2018-2019 实验室设备网版权所有