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$为例，实际应用应当调参

#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了。