当前位置:网站首页 > 网络安全培训 > 正文

CTF竞赛密码学之 LFSR

freebuffreebuf 2021-03-30 353 0

本文来源:蚁景科技

概述:

线性反馈移位寄存器(LFSR)归属于移位寄存器(FSR),除此之外还有非线性移位寄存器(NFSR)。移位寄存器是流密码产生密钥流的一个主要组成部分。

$GF(2)$上一个n级反馈移位寄存器由n个二元存储器与一个反馈函数$f(a_1,a_2,...,a_n)$组成,如下图所示。

FSR.png

移位寄存器的三要素:

  • 初始状态:由用户确定

  • 反馈函数:$f(a_1,a_2,...,a_n)$是n元布尔函数,即函数的自变量和因变量只取0和1这两个可能值

  • 输出序列

如果反馈函数是线性的,那么我们称其为 LFSR,如下图所示:

LFSR.png

LFSR的输出序列{ $a_n$ }满足:

$f(a_1,a_2,...,a_n) = c_1a_n⊕c_2a_{n-1}⊕...⊕c_na_1$

  • $a{n+1} = c_1a_n⊕c_2a{n-1}⊕...⊕c_na_1$

  • $a{n+2} = c_1a{n+1}⊕c_2a_n⊕...⊕c_na_2$

  • .....

  • $a{n+i} = c_1a{n+i-1}⊕c_2a_{n+i-2}⊕...⊕c_na_i$(i = 1,2,3,...)

举例:

下面是一个5级的线性反馈移位寄存器,其初始状态为$(a_1,a_2,...,a_n)= (1,0,0,1,1)$

例图.png

反馈函数为:$a{5+i} = a{3+i}⊕a_i$,(i = 1,2,...)可以得到输出序列为:

1001101001000010101110110001111 100110…

周期为31。

对于 n 级线性反馈移位寄存器,最长周期为$2^n-1$(排除全零)。达到最长周期的序列一般称为 m 序列

本文涉及相关实验:

转载请注明来自网盾网络安全培训,本文标题:《CTF竞赛密码学之 LFSR》

标签:CTF

关于我

欢迎关注微信公众号

关于我们

网络安全培训,黑客培训,渗透培训,ctf,攻防

标签列表