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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
#define N 900
using namespace std;
int a[N+12];
double G=0;
int culc(int x)
{
int k=x,s=0;
while(k)
{
s+=k%2;
k/=2;
}
return s;
}
int lfsr(int r,int m)
{
int t=(r<<1)&0xffffff;
int s=culc(r&m)&1;
return (t^s);
}
void solve(int B,int msk,double pos1,double pos2)
{
int r1,i,s1;
for (r1=(1<<(B-1));r1<(1<<(B));r1++)
{
s1=r1;
G=0;
for(i=1;i<=N;i++)
{
s1=lfsr(s1,msk);
if(a[i]==(s1&1)) ++G;
}
if((G/N>pos1)&&(G/N<pos2))
{
printf("%d:pos=%.4lf%\n",r1,G/N);
}
}
}
int main()
{
freopen("data.txt","r",stdin);
int i,j;
for(i=1;i<=N;i++)
{
char c;
scanf("%c",&c);
a[i]=(c=='1');
}
solve(18,0x3da61,0.595,0.655);
return 0;
}

最后剩下的$0.5$的概率数量如果只有$1$个或者$2$个,可以开暴力枚举($2$个的话请保证能够两重循环可行)

如果最后仍然剩下很难暴力枚举的$0.5$的概率,可以把未知的量跟已知的构造异或函数,使概率较大地偏离$0.5$(取$<0.4$或者$>0.6$的值为宜)。将已知的和未知的同步起来,也可以解出最后的答案。

所有的lfsr都解出来的时候,我们的题目也就解出来了,就可以得到flag了。