差分分析【附code】_D-A-X的博客-程序员秘密_差分分析

技术标签: 密码学  

算法步骤

  • 收集大量明密文对;
  • 选取一个固定的输入值 x ′ x' x
  • 遍历所有收集到的明密文对,寻找 x x x x ∗ x^* x,使得 x ⨁ x ∗ = x ′ x\bigoplus x^*=x' xx=x
  • 创建4元组 ( x , x ∗ , y , y ∗ ) (x,x^*,y,y^*) (x,x,y,y),其中, y = π ( x ) , y ∗ = π ( x ∗ ) y=\pi(x),y^*=\pi(x^*) y=π(x),y=π(x)
  • 通过4元组构建差分表;
  • 从输入 x ′ x' x开始,在差分表中选取差分值最大的作为输出,找到输出对应的s盒子并将该值作为输入,再在差分表中寻找差分值大的作为输入,以此类推,构建出差分链;
  • 计算该差分链中最后一轮输入对应位置的 u ′ = u ⨁ u ∗ u'=u\bigoplus u^* u=uu的值,记作 u 真 ′ u'_真 u
  • 遍历所有可能的密钥,遍历4元组,要求四元组中差分链最后一轮输入对应位置的 y = y ∗ y=y^* y=y;根据收集到的 y 、 y ∗ y、y^* yy值即当前测试密钥值计算最后一轮输入的 u u u u ∗ u^* u,再根据该值计算 u 测 ′ = u ⨁ u ∗ u'_测=u\bigoplus u^* u=uu;若 u 真 ′ = = u 测 ′ u'_真==u'_测 u==u,则该密钥对应count值加一;
  • 遍历结束后输出count值最大的密钥。

代码

在这里插入图片描述
  首先使用书中给出的差分链分析出第5轮第2、4部分的密钥。再选择新的差分链分析出第5轮第1、3部分密钥,然后穷举高16位密钥情况,并验证密钥正确性。
  与线性分析不同的是,由于差分分析中可以找到一条第5轮仅包含第1、3部分且偏差很大的差分链,因此不需要在已知第5轮第2、4部分的基础上进行差分分析,也因此减小了部分时间开销。
  与线性分析相同的是,差分分析也是基于概率的分析方法,因此仍需要对一定范围内的密钥情况进行遍历并验证是否正确。
  同时,由于对基于不同规模的明密文对进行分析得到的差分分析准确度也有所不同,但在超过阈值后将出现平台期,即当分析的明密文对达到MAX规模后,差分分析得到的结果的准确度几乎保持不变,因此为降低时间开销,MAX作为可调参数需要进行调参摸索。在本题中,该MAX值大约为8000。
  综上代码实现流程为:快速读入数据并存入数组中;根据已有的明密文对分别对第5轮第2、4部分和第1、3部分进行差分分析,记录每一种密钥对应的count值;在一定范围内遍历第5轮第2、4部分和第1、3部分密钥,穷举高16位密钥并验证正确性(一定范围指内循环和外循环的循环次数,该参数需要测试调整到最合适);得到正确密钥后快速输出密钥。
  需要注意的是,穷举验证过程中由于输入数据的随机程度不大(实际上检测的数据具有连续性),因此在一定检测数量下,相同明文在不同密钥下得到相同密文的个数将会有所提升,因此需要适度增加验证数量。

#include <stdio.h>
#include <string.h>
typedef unsigned short ushort;
typedef unsigned int uint;

int n;
ushort ciphertext[65540];
uint key, tail_key;
int cnt13[16][16], cnt24[16][16];
bool flag13[16][16];
ushort key51, key52, key53, key54;
//SPN statement
const unsigned short sBox_4[16] = {
    0xe, 0x4, 0xd, 0x1, 0x2, 0xf, 0xb, 0x8, 0x3, 0xa, 0x6, 0xc, 0x5, 0x9, 0x0, 0x7}; 
const unsigned short inverse_sBox[16] = {
    0xe, 0x3, 0x4, 0x8, 0x1, 0xc, 0xa, 0xf, 0x7, 0xd, 0x9, 0x6, 0xb, 0x2, 0x0, 0x5};
const unsigned short pos[17] = {
    0x0,
								0x8000, 0x4000, 0x2000, 0x1000,
                                0x0800, 0x0400, 0x0200, 0x0100,
                                0x0080, 0x0040, 0x0020, 0x0010,
                                0x0008, 0x0004, 0x0002, 0x0001};
const unsigned short pBox[17] = {
    0x0,
								 0x8000, 0x0800, 0x0080, 0x0008,
								 0x4000, 0x0400, 0x0040, 0x0004,
								 0x2000, 0x0200, 0x0020, 0x0002,
								 0x1000, 0x0100, 0x0010, 0x0001};
unsigned short sBox_16[65536], spBox[65536];

void get_spBox(){
      //获得spBox 
	for(int i = 0; i < 65536; ++i){
    
		sBox_16[i] = (sBox_4[i >> 12] << 12) | (sBox_4[(i >> 8) & 0xf] << 8) | (sBox_4[(i >> 4) & 0xf] << 4) | sBox_4[i & 0xf];
		spBox[i] = 0;
		for(int j = 1; j <= 16; ++j){
    
			if(sBox_16[i] & pos[j]) spBox[i] |= pBox[j];
		}
	} 
} 

inline ushort read(){
    
	char ch;
	ushort buf = 0;
	for(int i = 0; i < 4; ){
    
		ch = getchar();
		if(ch >= '0' && ch <= '9'){
    
			buf = (buf << 4) | (ch ^ 48);
			i++;
		}
		else if(ch >= 'a' && ch <= 'z'){
    
			buf = (buf << 4) | (ch - 'a' + 10);
			i++;
		}
	}
	return buf;
}

inline void input(){
    
	for(int i = 0; i < 65536; ++i){
    
		ciphertext[i] = read();
	}
}

inline void output(){
    
	char buf[8];  //输出缓冲区
	for(int i = 0; i < 8; ++i){
    
		buf[7 - i] = key & 0xf;
		if(buf[7 - i] < 10) buf[7 - i] += '0';
		else buf[7 - i] = buf[7 - i] - 10 + 'a'; 
		key >>= 4;
	}
	for(int i = 0; i < 8; ++i) putchar(buf[i]);
	putchar('\n');
}

inline void diff_analysis(){
    
	uint x, x_, y, y_, x_xor;
	ushort u1, u2, u3, u4, u1_, u2_, u3_, u4_;
	
	x_xor = 0x0b00;
	for(x = 12345; x < 20567; ++x){
    
		x_ = x ^ x_xor;
		y = ciphertext[x];
		y_ = ciphertext[x_];
		if((y & 0xf0f0) == (y_ & 0xf0f0)){
    
			for(int L1 = 0; L1 < 16; ++L1){
    
				for(int L2 = 0; L2 < 16; ++L2){
    
					//v2 = L1 ^ ((y >> 8) & 0xf);
					//v4 = L2 ^ (y & 0xf);
					u2 = inverse_sBox[L1 ^ ((y >> 8) & 0xf)];
					u4 = inverse_sBox[L2 ^ (y & 0xf)];
					
					//v2_ = L1 ^ ((y_ >> 8) & 0xf);
					//v4_ = L2 ^ (y_ & 0xf);
					u2_ = inverse_sBox[L1 ^ ((y_ >> 8) & 0xf)];
					u4_ = inverse_sBox[L2 ^ (y_ & 0xf)];
					
					//u2_xor = u2 ^ u2_;
					//u4_xor = u4 ^ u4_;
					if(((u2 ^ u2_) == 0x6) && ((u4 ^ u4_) == 0x6)) cnt24[L1][L2]++;
				} 
			}
		}
	}
	x_xor = 0x0020;
	for(x = 12345; x < 20567; ++x){
    
		x_ = x ^ x_xor;
		y = ciphertext[x];
		y_ = ciphertext[x_];
		if((y & 0x0f0f) == (y_ & 0x0f0f)){
    
			for(int L1 = 0; L1 < 16; ++L1){
    
				for(int L2 = 0; L2 < 16; ++L2){
    
					//v1 = L1 ^ ((y >> 12) & 0xf);
					//v3 = L2 ^ ((y >> 4) & 0xf);
					u1 = inverse_sBox[L1 ^ ((y >> 12) & 0xf)];
					u3 = inverse_sBox[L2 ^ ((y >> 4) & 0xf)];
					
					//v1_ = L1 ^ ((y_ >> 12) & 0xf);
					//v3_ = L2 ^ ((y_ >> 4) & 0xf);
					u1_ = inverse_sBox[L1 ^ ((y_ >> 12) & 0xf)];
					u3_ = inverse_sBox[L2 ^ ((y_ >> 4) & 0xf)];
					
					//u1_xor = u1 ^ u1_;
					//u3_xor = u3 ^ u3_;
					if(((u1 ^ u1_) == 0x5) && ((u3 ^ u3_) == 0x5)) cnt13[L1][L2]++;
				}
			} 
		}
	}
}

int main(){
    
	
	get_spBox();
	scanf("%d", &n);
	bool flag;
	for(int group = 0; group < n; ++group){
    
		input();
		flag = false;
		
		//计算2、4位
		memset(cnt24, 0, 256 * sizeof(int));
		memset(cnt13, 0, 256 * sizeof(int));
		diff_analysis();  //差分分析 
				
		//外循环 
		for(int round24 = 0; round24 < 10; ++round24){
    
			int max24 = -1;
			for(int L1 = 0; L1 < 16; ++L1){
    
				for(int L2 = 0; L2 < 16; ++L2){
    
					if(cnt24[L1][L2] > max24){
    
						max24 = cnt24[L1][L2];
						key52 = L1;
						key54 = L2;
					}
				}
			}
			cnt24[key52][key54] = 0;
			
			//内循环
			memset(flag13, true, 256 * sizeof(bool));
			for(int round13 = 0; round13 < 10; ++round13){
    
				int max13 = -1;
				for(int L1 = 0; L1 < 16; ++L1){
    
					for(int L2 = 0; L2 < 16; ++L2){
    
						if(cnt13[L1][L2] > max13 && flag13[L1][L2]){
    
							max13 = cnt13[L1][L2];
							key51 = L1;
							key53 = L2;
						}
					}
				}
				flag13[key51][key53] = false;
				
				//开始穷举
				tail_key = (key51 << 12) | (key52 << 8) | (key53 << 4) | key54; 
				int plaintext, k1, k2, k3, k4, k5;
				for(int fore_key = 0; fore_key < 65536; ++fore_key){
    
					key = (fore_key << 16) | tail_key;
					k5 = tail_key;
					k4 = (key >> 4) & 0xffff;
					k3 = (key >> 8) & 0xffff;
					k2 = (key >> 12) & 0xffff;
					k1 = (key >> 16) & 0xffff;
					for(plaintext = 0; plaintext < 24; ++plaintext){
    
						if((sBox_16[spBox[spBox[spBox[plaintext ^ k1] ^ k2] ^ k3] ^ k4] ^ k5) != ciphertext[plaintext]) break;
					}
					if(plaintext == 24){
    
						flag = true;
						break;
					}
				}
				if(flag) break;
			}
			if(flag) break; 
		}
		output();
	}	
	
	return 0;
}

相关资料

SPN线性密码分析【附code】

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/m0_46161993/article/details/106797113

智能推荐

简单使用django框架_minhoag的博客-程序员秘密

首先,打开pycharm下的Terminal窗口,安装django框架输入pip install django如下图所示,即安装成功接着,创建一个Django项目(这里的项目名为pyshop),此项目可包含多个应用程序创建成功后,打开项目,可以看到一个package,里面有一些模块可供使用,内容如下:wsgi.py提供一个接口,用于django和web构建的应用程序中。还可以看到有一个manage.py,可管理django项目,可用于启动web服务器,可用于数据库操作

0619_如何成功安装Angular-Cli?踩坑记_Golden_soft的博客-程序员秘密

由于Angular4升级了,旧版的Angular-Cli支持性不是很好,所以Angular-Cli也需要升级更新,本质就是删除掉以前的,再重新安装就好了。Angular-Cli is more than tool,it is a platform!一、安装Angular-Cli经过n次的失败安装,终于在最后一次安装成功,为了使同学们少走弯路,现将经验写下来:1、查看...

️【保姆级安装教程】️使用VMware Workstation搭建Windows11系统上手体验,结尾有趣事_xybDIY的博客-程序员秘密

使用VMware Workstation搭建Windows11系统一、前提准备1、Windows11镜像下载2、虚拟机硬件资源分配3、虚拟机安装注意事项二、安装步骤1、打开VMware Workstation 16 pro软件2、选择“创建新的虚拟机”3、选择“自定义”类型的配置4、选择虚拟机硬件兼容性5、安装客户机操作系统6、选择客户机操作系统7、命名虚拟机8、固件类型选择9、处理器配置10、虚拟机内存大小11、网络类型12、选择I/O控制器类型13、选择磁盘类型14、选择磁盘15、指定磁盘容量16、指定

python3+ selenium3开发环境搭建-手把手教你安装python(详细)_weixin_30797027的博客-程序员秘密

环境搭建基于python3和selenium3做自动化测试,俗话说:工欲善其事必先利其器;没有金刚钻就不揽那瓷器活,磨刀不误砍柴工,因此你必须会搭建基本的开发环境,掌握python基本的语法和一个IDE来进行开发,这里通过详细的讲解,介绍怎么搭建python3和selenium3开发环境,并提供一个基本入门的代码,后续逐步提供系列实践文章。安装包python笔者使...

Shell脚本调试技术_Augusdi的博客-程序员秘密

Shell脚本调试技术      本文全面系统地介绍了shell脚本调试技术,包括使用echo, tee, trap等命令输出关键信息,跟踪变量的值,在脚本中植入调试钩子,使用“-n”选项进行shell脚本的语法检查, 使用“-x”选项实现shell脚本逐条语句的跟踪,巧妙地利用shell的内置变量增强“-x”选项的输出信息等。一. 前言shell编程在unix/linux世界中使用得非常广泛,熟

《快学Scala》第三章习题解答_rongyongfeikai2的博客-程序员秘密

RT。package com.scalalearn.scala.main//java中的List转为scala buffer至关重要的引入import scala.collection.JavaConversions.asScalaBufferimport java.awt.datatransfer.{DataFlavor, SystemFlavorMap}import scala.c

随便推点

android scrollview源码分析,Android—ScrollView源码分析及简单实现_臭熊的哥哥的博客-程序员秘密

我的CSDN: ListerCi我的简书: 东方未曦一、ScrollView介绍及源码分析ScrollView是Android日常开发中比较常见的一个ViewGroup,它只能有一个子View。用户在滑动时子View在ScrollView内部滚动,显示不同的区域。在开发中如果需要将多个不同类型的视图垂直排列时,我们一般会使用ScrollView。但是永远不要将RecyclerView和ListVi...

flask-socketio:API 参考_Esun_nyy的博客-程序员秘密

flask-socketioAPI 参考类flask_socketio.SocketIO(app=None,**kwargs)创建一个 Flask-SocketIO 服务器。参数: app- flask应用程序实例。如果在实例化此类时不知道应用程序实例,则socketio.init_app(app)在应用程序实例可用时调用。 manage_session– 如果设置为True,此扩展管理 Socket.IO 事件的用户会话。如果设置为False,则使用 ...

Python 爬虫实战 3_UtopXExistential的博客-程序员秘密

目录抓包方法FiddlerFiddler 工作原理安装方法配置 Fiddler项目:使用抓包分析获取腾讯视频评论数据开始抓包分析抓包过程分析按照上面流程,每次触发一个页面,观察复制的 url 的规律代码部分第三讲:抓包分析技术精讲(课程笔记)抓包方法方法1:进入网页,F12 ---&gt;Network,访问某个网页,出现很多数据包,我们要获取和分析的就是这些数据包【如下图】。但是这样抓包的缺点:杂内容多,跳转快速,不太好做分析,因此...

C/C++中的段错误总结_biubiu_scut的博客-程序员秘密

Segment fault 之所以能够流行于世,是与Glibc库中基本所有的函数都默认型参指针为非空有着密切关系的。 来自:http://oss.lzu.edu.cn/blog/article.php?uid_7/tid_700.html#comment 背景    最近一段时间在linux下用C做一些学习和开发,但是由于经验不足,问题多多。而段错误就是让我

fork bomb 介绍 以及防范措施_weixin_33957648的博客-程序员秘密

文章来自 http://blog.csdn.net/gray13/article/details/7308771#comments下面就是一个最简单的 bash fork ×××:: () { : | : &amp; } ; :上面几个符号看上去很复杂,其实如果写成下面这个样子就好懂了,: 是函数名,执行一个调用自己的递归并且 pipe 到自己,&amp;...

JWT & HMAC-SHA256_weixin_30824599的博客-程序员秘密

JWTJSON Web Tokenshttps://jwt.io/https://en.wikipedia.org/wiki/JSON_Web_Token#StructureHMACSHA256https://en.wikipedia.org/wiki/HMACkeyed-hash message authentication code or hash-based ...

推荐文章

热门文章

相关标签