Nfsr
关于NFSR学习的一些笔记
0x01解题背景
10月6日刚把0xCTF上的所有密码学题目AK,这道题卡了我一周,得到了学长的帮助,查了CTFWIKI和学长的博客才勉强做出来,太难了
0x02简介
NFSR,又称非线性移位寄存器,在模$2$的意义下,异或可以视作加法,按位与可以视作乘法。所以LFSR一般都是只有异或,而NFSR有与运算。并且与运算的性质可以知道,这是一个不可逆的运算 。
一般情况下,NFSR是多个LFSR通过一个函数$F(r_1,r_2,…,r_n)$,其中$F$函数中与运算和异或运算均存在,根据与运算的不可逆性,可知$F$函数的不可逆性,所以显然,我们写不出$F$函数的逆函数$F^{-1}$。
0x03 解题方法
我们可以一开始枚举每一个lfsr及其输出结果,看看$F(r_1,r_2,…,r_n)=r_i,i∈${$1,2,3,…,n$}的概率$P_i$。找出所有不为概率不为$0.5$的$P_i$,然后用以下的C++脚本暴力枚举$r_i$的初始值。
一般先定义$N=30$,区间筛选邻域$U(P,0.05)$判断存在性,然后不断调大$N$为$100,200,400,600,900,1200,2700$,直到最后运行只剩下一个结果即可,逐步调大主要是为了判断结果的存在性和检验参数的正确性。
如果$N$超过$600$算出来的数值仍然比较多的话,我们可以把区间筛选邻域由$U(P,0.05)$为$U(P,0.03)$或者$U(P,0.02)$增大筛选要求。
本代码以$18$位,概率$0.625$为例,实际应用应当调参
1 |
|
最后剩下的$0.5$的概率数量如果只有$1$个或者$2$个,可以开暴力枚举($2$个的话请保证能够两重循环可行)
如果最后仍然剩下很难暴力枚举的$0.5$的概率,可以把未知的量跟已知的构造异或函数,使概率较大地偏离$0.5$(取$<0.4$或者$>0.6$的值为宜)。将已知的和未知的同步起来,也可以解出最后的答案。
所有的lfsr都解出来的时候,我们的题目也就解出来了,就可以得到flag了。