关于非线性组合模型Geffe的分割攻击实现

admin • 2021-12-28 21:11 • 安全

密码学学完序列密码后要做关于Geffe的攻击。。。
看来看去就分割攻击比较好写~~但是这个LFSR2的级数太高了好像写的有点问题~~
~~不管了，快期未考试了~~

非线性组合模型

一、非线性组合模型

Geffe

$G e f f e$ 发生器是1973年

Geffe

$G e f f e$ 设计的一个密钥流生成器，具体描述如下:

如图所示，

Geffe

$G e f f e$ 发生器使用了3个

LFSR

$L F S R$ 移位寄存器他们以非线性方式组合，其中，

LFSR1

$L F S R 1$ 和

LFSR3

$L F S R 3$ 作为复合器的输入，

LFSR2

$L F S R 2$ 作为控制复合器。

其中，三个

LFSR

$L F S R$ 的反馈多项式分别为：

(

)

⊕

f_1(x)=x^{20}oplus x^3oplus 1

$f_{1} (x) = x^{20} \oplus x^{3} \oplus 1$

(

)

⊕

f_2(x)=x^{39}oplus x^4oplus 1

$f_{2} (x) = x^{39} \oplus x^{4} \oplus 1$

(

)

⊕

f_3(x)=x^{17}oplus x^3oplus 1

$f_{3} (x) = x^{17} \oplus x^{3} \oplus 1$

非线性组合函数

$F$ 为:

(

)

⊕

(

⊕

)

{

g(x_1,x_2,x_3)=x_1x_2oplus(x_2oplus1)x_3= begin{cases} x_1,quad x_2=1\ x_3,quad x_2=0 end{cases}

$g (x_{1}, x_{2}, x_{3}) = x_{1} x_{2} \oplus (x_{2} \oplus 1) x_{3} = {x_{1}, x_{2} = 1 x_{3}, x_{2} = 0$

二、非线性组合模型

(1)密钥 $K=(k_{63},…,k_0) K=(k63,…,k0)按照如下方式填充：$

先将密钥重复链接，得到76比特密钥

’

K’

$K ’$

’

(

…

)

K’=(k_{11},…, k_1,k_0,k_{63},…,k_{0})

$K ’ = (k_{11}, \dots, k_{1}, k_{0}, k_{63}, \dots, k_{0})$

将

’

K’

$K ’$ 由低位到高位按照从右到左的顺序依次填入

LFSR1

$L F S R 1$ 、

LFSR2

$L F S R 2$ 和

LFSR3

$L F S R 3$ 。

2）按照密钥流生成方式空转100个时刻

将此时

LFSR

$L F S R$ 的内部状态做为密钥流生成的初态。

三、非线性组合模型

1.穷举

2.获得关于

3.解方程得到初态

4.根据前100个时刻的乱数，验证初态是否正确

四、分割攻击具体实现代码及注释

1.定义密钥流

	string K="1010010010000101010100101010110101101100100111001011010001110011";//K为初始密钥
	string s1,s2,s3;//s1,s2,s3中分别为LFSR1 2 3的初始填充
	s1="11001011010001110011";
	s2="100100001010101001010101101011011001001";
	s3="01000111001110100";

2.将

void LFSR_f1(int l_xunhuan,string chutai){//LFSR1的实现代码，其中l_xunhuan为循环轮数，chutai为LFSR的初态
	bitset<20>f1(chutai);//初态赋值 
	//cout<<f1.to_string();
	for(int i=1;i<=l_xunhuan;i++){//移位寄存
		int j=f1[0]^f1[17] ;
		len_f1++;
		//string s_out = f1.to_string();
		f1_out += '0'+j;
		f1.operator>>=(1);
		f1[19]=j;
	}
}

void LFSR_f2(int l_xunhuan,string chutai){//LFSR2的实现代码，其中l_xunhuan为循环轮数，chutai为LFSR的初态
	bitset<39>f2(chutai);//初态赋值 
	//cout<<f2.to_string();
	for(int i=1;i<=l_xunhuan;i++){//移位寄存
		int j=f2[0]^f2[35] ;
		len_f2++;
		//string s_out = f2.to_string();
		f2_out += '0'+j;
		f2.operator>>=(1);
		f2[38]=j;
	}
}

void LFSR_f3(int l_xunhuan,string chutai){//LFSR2的实现代码，其中l_xunhuan为循环轮数，chutai为LFSR的初态
	bitset<17>f3(chutai);//初态赋值 
	//cout<<f3.to_string();
	for(int i=1;i<=l_xunhuan;i++){//移位寄存
		int j=f3[0]^f3[14] ;
		len_f3++;
		//cout<<i<<endl;
		//cout<<"f3_out--->"<<f3_out<<endl;
		//string s_out = f3.to_string();
		f3_out += j+'0' ;
		f3.operator>>=(1);
		f3[16]=j;
	}
}

//此为主函数的调用语句
	LFSR_f1(100,s1);
	LFSR_f2(100,s2);
	LFSR_f3(100,s3);

3.根据

	string f0_out;//为最终输出密钥流
	for(int i=0;i<100;i++){
		if(f2_out[i]=='1') f0_out+=f1_out[i];
		else f0_out+=f3_out[i];
	}

4.枚举

	int cnt =0;
	int x_len = 1<<39; 
	for(int i=0;i<x_len;i++){
        //中间流程由后面具体解释
    }

5.根据

	int cnt =0;
	int x_len = 1<<39; 
	for(int i=0;i<x_len;i++){
		string  sheng_chu;       //生成枚举LFSR2的字符串
		for(int j=0;j<39;j++){
			int k=(i>>j) & 1;
			sheng_chu+=(k+'0');
		}
		f2_out="";
		f3_out="";
		f1_out="";
		LFSR_f2(100,sheng_chu);
		string sheng_f1(100,'2');//初始化LFSR1
		string sheng_f3(100,'2');//初始化LFSR2
		
		for(int j=0;j<100;j++){
			if(f2_out[j]=='0') sheng_f1[j]=f0_out[j];
			else sheng_f3[j]=f0_out[j];
		}
		string sheng(20,'2');
		sheng_f1=sheng+sheng_f1;
		bool flag =true;
		//不断的根据已有关系求解 f1
		while(flag){
			flag=false;
			for(int j=119;j>=20;j--){
				int x=sheng_f1[j-20]-'0',y=sheng_f1[j-3]-'0';
				if(sheng_f1[j]!='2' && (x==2) && (y!=2)){
					sheng_f1[j-20]= (y ^ (sheng_f1[j]-'0'))+'0';
					flag=true ;	
				} 
				else if(sheng_f1[j]!='2' && (x!=2) && (y==2)){
					sheng_f1[j-3]= (x ^ (sheng_f1[j]-'0'))+'0';
					flag=true ;
				}
				else if(sheng_f1[j]=='2' && (x!=2) && (y!=2)){
					sheng_f1[j]=(x^y)+'0';
					flag=true;
				}
			}
		}
		
//		for(int i=0;i<20;i++) cout<<sheng_f1[i];
//		cout<<endl;
		string sheng3(17,'2');
		sheng_f3=sheng3+sheng_f3;
		flag =true;
		//不断的根据已有关系求解 f3
		while(flag){
			flag=false;
			for(int j=116;j>=17;j--){
				int x=sheng_f3[j-17]-'0',y=sheng_f3[j-3]-'0';
				if(sheng_f3[j]!='2' && (x==2) && (y!=2)){
					sheng_f3[j-17]= (y ^ (sheng_f3[j]-'0'))+'0';
					flag=true ;	
				} 
				else if(sheng_f3[j]!='2' && (x!=2) && (y==2)){
					sheng_f3[j-3]= (x ^ (sheng_f3[j]-'0'))+'0';
					flag=true ;
				}
				else if(sheng_f3[j]=='2' && (x!=2) && (y!=2)){
					sheng_f3[j]=(x^y)+'0';
					flag=true;
				}
			}
		}
//		for(int i=0;i<17;i++) cout<<sheng_f3[i];
//		cout<<endl;
		}
	}

6.判断是否存在解不出来

		bool check_f1=true,check_f3=true;
		string temp_f1="",temp_f3="";
		for(int i=0;i<20;i++){
			if(sheng_f1[i]=='2') {
				check_f1=false;//判断是否存在有解不出来的情况
				break;
			}
			temp_f1+=sheng_f1[i];
		}
			
		for(int i=0;i<17;i++){
			if(sheng_f3[i]=='2') {
				check_f3=false;//判断是否存在有解不出来的情况
				break;
			}
			temp_f3+=sheng_f3[i];
		}

7.如果

	if(check_f1 && check_f3) {
			//cnt++;
			f1_out="";
			f3_out="";
			//cout<<"-1"<<endl;
			LFSR_f1(100,temp_f1);//根据f1初始值生成密钥流 
			//cout<<"-2"<<endl;
			//cout<<sheng_f3<<endl;
			LFSR_f3(100,temp_f3);//根据f3初始值生成密钥流 
			//cout<<sheng_f3<<endl;
			//cout<<"-3"<<endl;
			string f_sheng_out;
			//if() f_sheng_out=;
			for(int i=0;i<100;i++){ //根据枚举的f2,f1,f3的值, 生成密钥流 
				if(f2_out[i]=='1') f_sheng_out+=f1_out[i];
				else f_sheng_out+=f3_out[i];
			}
			if(f_sheng_out == f0_out) {//判断是否匹配成功 
				printf("YESn");
				cout<<temp_f1<<"n"<<temp_f3<<endl;
			}else{
				printf("NOn");
				cout<<temp_f1<<"n"<<temp_f3<<endl;//输出此时计算出的f1,f3 
			}
		}

五、完整代码及运行结果

#include <iostream>
#include <cstdlib>
#include <bitset>
using namespace std;

string f1_out,f2_out,f3_out;
int len_f1,len_f2,len_f3;

void LFSR_f1(int l_xunhuan,string chutai){
	
	bitset<20>f1(chutai);
	//cout<<f1.to_string();
	for(int i=1;i<=l_xunhuan;i++){
		int j=f1[0]^f1[17] ;
		len_f1++;
		//string s_out = f1.to_string();
		f1_out += '0'+j;
		f1.operator>>=(1);
		f1[19]=j;
	}
}

void LFSR_f2(int l_xunhuan,string chutai){
	
	bitset<39>f2(chutai);//初态赋值 
	//cout<<f2.to_string();
	for(int i=1;i<=l_xunhuan;i++){
		int j=f2[0]^f2[35] ;
		len_f2++;
		//string s_out = f2.to_string();
		f2_out += '0'+j;
		f2.operator>>=(1);
		f2[38]=j;
	}
	
}

void LFSR_f3(int l_xunhuan,string chutai){
	
	bitset<17>f3(chutai);//初态赋值 
	//cout<<f3.to_string();
	for(int i=1;i<=l_xunhuan;i++){
		
		int j=f3[0]^f3[14] ;
		len_f3++;
		//cout<<i<<endl;
		//cout<<"f3_out--->"<<f3_out<<endl;
		//string s_out = f3.to_string();
		f3_out += j+'0' ;
		f3.operator>>=(1);
		f3[16]=j;
	}
	
}

int main(){
//	string sy="01010101100010110111";
//			  // 01234567890123456789
//	LFSR_f1(100,sy);
//	cout<<f1_out;
	string K="1010010010000101010100101010110101101100100111001011010001110011";
	string s1,s2,s3;
	s1="11001011010001110011";
	s2="100100001010101001010101101011011001001";
	s3="01000111001110100";
{	
//	bitset<20> sy(s1);
//	for(int i=0;i<20;i++) cout<<sy[i]<<" ";
//	sy.operator<<=(1);
//	string ssyy=sy.to_string();
//	cout<<endl;
//	for(int i=0;i<20;i++) cout<<sy[i]<<" ";
//	cout<<endl;
}
	LFSR_f1(100,s1);
	LFSR_f2(100,s2);
	LFSR_f3(100,s3);
	
	string f0_out;
	for(int i=0;i<100;i++){
		if(f2_out[i]=='1') f0_out+=f1_out[i];
		else f0_out+=f3_out[i];
	}
	//
	cout<<"LFSR1--->"<<f1_out<<endl;
	cout<<"LFSR2--->"<<f2_out<<endl;
	cout<<"LFSR3--->"<<f3_out<<endl;
	cout<<"LFSR输出--->"<<f0_out<<endl;
	
	//long long ii=1<<39-1;
	
//	string 
//	for(int i=0;i<39;i++){
//		if((ii>>i & 1)==1) 
//	}

	int cnt =0;
	int x_len = 1<<30; 
	for(int i=0;i<x_len;i++){
		string  sheng_chu;
		for(int j=0;j<39;j++){
			int k=(i>>j) & 1;
			sheng_chu+=(k+'0');
		}
		//sheng_chu="100100001010101001010101101011011001001";
		f2_out="";
		f3_out="";
		f1_out="";
		LFSR_f2(100,sheng_chu);
		string sheng_f1(100,'2');
		string sheng_f3(100,'2');
		
		
		for(int j=0;j<100;j++){
			if(f2_out[j]=='0') sheng_f1[j]=f0_out[j];
			else sheng_f3[j]=f0_out[j];
		}
//		cout<<sheng_f1<<endl;
//		cout<<sheng_f3<<endl;
		string sheng(20,'2');
		sheng_f1=sheng+sheng_f1;
		bool flag =true;
		//不断的根据已有关系求解 f1
		while(flag){
			flag=false;
			for(int j=119;j>=20;j--){
				int x=sheng_f1[j-20]-'0',y=sheng_f1[j-3]-'0';
				if(sheng_f1[j]!='2' && (x==2) && (y!=2)){
					sheng_f1[j-20]= (y ^ (sheng_f1[j]-'0'))+'0';
					flag=true ;	
				} 
				else if(sheng_f1[j]!='2' && (x!=2) && (y==2)){
					sheng_f1[j-3]= (x ^ (sheng_f1[j]-'0'))+'0';
					flag=true ;
				}
				else if(sheng_f1[j]=='2' && (x!=2) && (y!=2)){
					sheng_f1[j]=(x^y)+'0';
					flag=true;
				}
			}
		}
		
//		for(int i=0;i<20;i++) cout<<sheng_f1[i];
//		cout<<endl;
		
		string sheng3(17,'2');
		sheng_f3=sheng3+sheng_f3;
		flag =true;
		//不断的根据已有关系求解 f3
		while(flag){
			flag=false;
			for(int j=116;j>=17;j--){
				int x=sheng_f3[j-17]-'0',y=sheng_f3[j-3]-'0';
				if(sheng_f3[j]!='2' && (x==2) && (y!=2)){
					sheng_f3[j-17]= (y ^ (sheng_f3[j]-'0'))+'0';
					flag=true ;	
				} 
				else if(sheng_f3[j]!='2' && (x!=2) && (y==2)){
					sheng_f3[j-3]= (x ^ (sheng_f3[j]-'0'))+'0';
					flag=true ;
				}
				else if(sheng_f3[j]=='2' && (x!=2) && (y!=2)){
					sheng_f3[j]=(x^y)+'0';
					flag=true;
				}
			}
		}
//		for(int i=0;i<17;i++) cout<<sheng_f3[i];
//		cout<<endl;
		bool check_f1=true,check_f3=true;
		string temp_f1="",temp_f3="";
		for(int i=0;i<20;i++){
			if(sheng_f1[i]=='2') {
				check_f1=false;//判断是否存在有解不出来的情况
				break;
			}
			temp_f1+=sheng_f1[i];
		}
			
		for(int i=0;i<17;i++){
			if(sheng_f3[i]=='2') {
				check_f3=false;//判断是否存在有解不出来的情况
				break;
			}
			temp_f3+=sheng_f3[i];
		}
			
		if(check_f1 && check_f3) {
			//cnt++;
			f1_out="";
			f3_out="";
			//cout<<"-1"<<endl;
			LFSR_f1(100,temp_f1);//根据f1初始值生成密钥流 
			//cout<<"-2"<<endl;
			//cout<<sheng_f3<<endl;
			LFSR_f3(100,temp_f3);//根据f3初始值生成密钥流 
			//cout<<sheng_f3<<endl;
			//cout<<"-3"<<endl;
			string f_sheng_out;
			//if() f_sheng_out=;
			for(int i=0;i<100;i++){ //根据枚举的f2,f1,f3的值, 生成密钥流 
				if(f2_out[i]=='1') f_sheng_out+=f1_out[i];
				else f_sheng_out+=f3_out[i];
			}
			if(f_sheng_out == f0_out) {//判断是否匹配成功 
				printf("YESn");
				cout<<temp_f1<<"n"<<temp_f3<<endl;
			}else{
				printf("NOn");
				cout<<"LFSR1="<<temp_f1<<"n"<<"LFSR3="<<temp_f3<<endl;//输出此时计算出的f1,f3 
			}
		}
	}
	//cout<<cnt;
}

程序运行展示:

因

LFSR2

$L F S R 2$ 级数太高，无法在短时间内结束

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。

THE END

c++lfsr 安全密码学

二维码

SpringSecurity CSRF引发的思考Cookie、Session、Token和JWT

< <上一篇

你下载国家反诈中心APP了吗

下一篇>>

搜索内容

关于非线性组合模型Geffe的分割攻击实现

非线性组合模型

一、非线性组合模型

二、非线性组合模型

(1)密钥 $K=(k_{63},…,k_0) K=(k63,…,k0)按照如下方式填充：$

2）按照密钥流生成方式空转100个时刻

三、非线性组合模型

1.穷举

2.获得关于

3.解方程得到初态

4.根据前100个时刻的乱数，验证初态是否正确

四、分割攻击具体实现代码及注释

1.定义密钥流

2.将

3.根据

4.枚举

5.根据

6.判断是否存在解不出来

7.如果

五、完整代码及运行结果

最新文章

分类

标签云

关于非线性组合模型Geffe的分割攻击实现

非线性组合模型 G e f f e Geffe Geffe分割攻击

一、非线性组合模型 G e f f e Geffe Geffe​​​发生器的基本介绍

二、非线性组合模型 G e f f e Geffe Geffe的初始化过程

(1)密钥 K = ( k 63 , … , k 0 ) K=(k_{63},…,k_0) K=(k63​,…,k0​)按照如下方式填充：

2）按照密钥流生成方式空转100个时刻

三、非线性组合模型 G e f f e Geffe Geffe​分割攻击流程

1.穷举 L F S R 2 LFSR2 LFSR2的初态

2.获得关于 L F S R 1 LFSR1 LFSR1和 L F S R 3 LFSR3 LFSR3初态的线性方程；

3.解方程得到初态

4.根据前100个时刻的乱数，验证初态是否正确

四、分割攻击具体实现代码及注释

1.定义密钥流 K K K​的值并将 K K K​填充到三个 L F S R LFSR LFSR​​的初态中

2.将 L F S R LFSR LFSR​空转100个时刻并记录下产生的密钥流

3.根据 L F S R 2 LFSR2 LFSR2​的值来决定最后输出密钥流的每一位取 L F S R 1 LFSR1 LFSR1还是取 L F S R 3 LFSR3 LFSR3​​的值

4.枚举 L F S R 2 LFSR2 LFSR2的初态

5.根据 L F S R 2 LFSR2 LFSR2​的初态，推算出 L F S R 1 LFSR1 LFSR1​和 L F S R 3 LFSR3 LFSR3​的初态

6.判断是否存在解不出来 L F S R 1 LFSR1 LFSR1或 L F S R 3 LFSR3 LFSR3​​的情况

7.如果 L F S R 1 LFSR1 LFSR1​和 L F S R 3 LFSR3 LFSR3​的初态均已解出，判断由此时 L F S R 1 LFSR1 LFSR1​​， L F S R 3 LFSR3 LFSR3​和 L F S R 2 LFSR2 LFSR2​所生成的​​密钥与真实值是否相等

五、完整代码及运行结果

最新文章

分类

标签云

非线性组合模型

一、非线性组合模型

二、非线性组合模型

(1)密钥 $K=(k_{63},…,k_0) K=(k63,…,k0)按照如下方式填充：$

三、非线性组合模型

1.穷举

2.获得关于

1.定义密钥流

2.将

3.根据

4.枚举

5.根据

6.判断是否存在解不出来

7.如果