ACTF新人赛密码学部分考察点与题解

关键词：密码学，CTF出题，题解。

具体的题目，考点，题解请见项目链接。

新生赛是我进入实验室以来参与出题的第一场比赛。为了这个比赛，我在平时还是做了一些积累，只有有灵感，我就着手开始写出题脚本和解题脚本，然后有一道自己完成不了的题目就麻烦DJ学长帮我写了一下，在这里感谢DJ学长啦！第二次在gitea上协作完成项目，无论是实验室的同学，学长，学弟还是河北师范的同学都给予了我很大的帮助。这次我吸取了之前密码学实验项目的教训，对于分支，调试，校对，发布的流程有了更多的了解。另外这次出题，在苏洋同学的帮助下我终于开始用git bash了，这也为我后面自学开博客打下了基础。最后，这次我也格外注重了文档的规范性，每一道题目都提前按格式把出题方向，题解，源代码，发布的题目，提示，题干，hint给写好了。
说起这次题目的遗憾，就是有两道稍微有难度而又很有意思的题目没有放上来。看了大家的做题情况，密码学的题目基本上都还是几位同学在做。所以对于更加复杂的两道题目，我认为没有必要这么早放上来了，等到校赛吧，等着你们成长。我看到同学们也努力了，比如某位同学，辛辛苦苦终于解出了一道维吉尼亚，当然他一开始对维吉尼亚有些误解，也问了我，最后独立的把题目解了出来。我觉得不管能不能解出题目，只要题目足够有意思，大家足够享受这个过程，就够了。还有一个比较悲剧的，就是没想到杂项出题的学长会和我出了同一个考点，面对着90%以上的题目相似度，我觉得学长题目内容的确更简洁一些，而我的题干更好一些，于是我就放弃了我的那道题目，把自己的题干放到了杂项的那道题目那里。杂项密码学也有千丝万缕的联系呢，少一道也不亏。以下是同学们的完成状况：

从同学们的完成状况来看，密码学的确没有杂项，逆向和web那么受欢迎，究其原因，应该是密码学的就业面没这么大，而且理论相对深奥，难度较大。但是我认为密码学一直都是挺有意思的存在，多了解一些密码学的知识点总是好的，如果的确有能力，可以做做密码学的研究；觉得自己能力不够的话，退而研究算法，或者在信息安全的其他方面引入密码学的知识，活学活用也很不错。好了，接下来就是这次的wp，我觉得自己这次的题目还是偏简单了一些，和CTF有比较大的差别，另外为了使一道题目有更多的考点，也更加有趣，我的确准备了很多的压缩包密码，所以遭到了一些吐槽。不过也没关系啦，继续完善一下自己，争取校赛能提供更好的题目！

classic0

题干

小Z用C语言编写了一个最简单的密码系统，里面都采用的是最简单的古典加密。但是他的源程序不幸泄露，聪明的你能否解读他采用的算法并进行解密？flag格式为actf{***}

考察点

凯撒，异或，编程能力，生日字典

hint

字典

writeup

题目给出了密文还有一个生日字典加密后的加密脚本压缩包。如果你够厉害，当然你可以直接根据密文来解啦，不过就是两种加密合在一起，不是简单凯撒，所以有一定难度。

不过如果你知道生日字典攻击的话，不妨拿个工具跑一下，那么很快就可以得到结果了，最后写出解题代码：

#include<stdio.h>

char flag[25] = {"Ygvdmq[lYate[elghqvakl}"};

int main()
{
	int i;
	for(i=0;i<25;i++)
	{
		flag[i] ^= 0x7;
        flag[i] += 3;
		printf("%c",flag[i]);
	}
}

注意，有个地方的字符不是空格也不是’.’！不过你是可以用winhex或者010editor看到它具体的值的，这个值是7f。

附：加密源代码

#include<stdio.h>

char flag[25] = {"actf{my_naive_encrytion}"};

int main()
{
	int i;
	for(i=0;i<25;i++)
	{
		flag[i] -= 3;
		flag[i] ^= 0x7;
		printf("%c",flag[i]);
	}
	return 0; 
}

classic1

题干

维吉尼亚加密是极其经典的古典密码，flag格式为actf{}，明文中的字母均为小写

考察点

键盘密码，维吉尼亚密码

hint

1.谜底就在谜面上

writeup

压缩包密码是一个键盘密码，稍微熟悉键盘的同学低下头看看，然后再看到密文里面“,.;”这一连串字符，应该会有些感觉。这些密文里面都是一个圈这样围在一起的，里面那个就是明文。key为circle。

这里的维吉尼亚密码，由于密文比较短，频率分析不管用，看一下题干，flag的格式已经给出，稍微尝试一下，得到加密密钥的值为sp，然后即可解决。

附：加密源代码

#include<stdio.h>
#include<iostream>

#define CYPHERLEN 31 
#define KEYLEN 2

using namespace std;

int main()
{
	char str[CYPHERLEN]={0};
	char key[3]="sp"; 
	int i; 
	for(i=0;i<CYPHERLEN;i++)
	{
		scanf("%c",&str[i]);
	}
	for(i=0;i<CYPHERLEN;i++)
	{
		if(isupper(str[i])||islower(str[i]))
		{
			str[i]=toupper(str[i]);
			str[i]-='A';
			str[i]+=(key[i%KEYLEN]-'a');
			str[i]%=26;
			str[i]+='A';
		}
	}
	for(i=0;i<CYPHERLEN;i++)
	{
			printf("%c",str[i]);
	}
	return 0;
 }

des-mailbox

题干

小Z自创了一套DES加密方法。他悄悄告诉你，这是你们传递秘密的信箱，所以想要获得他的秘密很简单，动动小脑袋瓜和小手指头就可以啦！flag格式为actf{***}

考察点

C语言强制转换，DES相关编程

hints

1.type casting
2.In fact, that is not completely how DES work. We divided the process into several steps.
3.the keys are just overthere.

writeup

首先要知道这个是一个强制转换，把字符转为浮点数，我们用puts即可把浮点数转换为字符，解出key。

#include<stdio.h>


int main()
{
	float f[]={
	72143238992041641000000.000000,
    77135357178006504000000000000000.000000,
    1125868345616435400000000.000000,
    67378029765916820000000.000000,
    75553486092184703000000000000.000000,
    4397611913739958700000.000000,
    76209378028621039000000000000000.000000
    };
	puts((char*)f);
 }

然后就可以看到des.py，里面子密钥都给出了，解密不就只是安装一个密码学包然后再用回密钥解密就行了嘛。

import pyDes
import base64
from FLAG import flag
deskey = "********"
DES = pyDes.des(deskey)
DES.setMode('ECB')
DES.Kn = [
			[1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0],
			[1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0], 
			[0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0],
			[1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1], 
			[0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1],
			[0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0],
			[0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0],
			[0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0],
			[1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0],
			[0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0],
			[0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1],
			[0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0],
			[1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0],
			[1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1],
			[1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1],
			[1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1]
		]
cipher_list = b'vrkgBqeK7+h7mPyWujP8r5FqH5yyVlqv0CXudqoNHVAVdNO8ML4lM4zgez7weQXo'
print(DES.decrypt(base64.b64decode(cipher_list)))

出题源代码

强制类型转换（这个思路要感谢DJ学长，最初的出处请见afctf第一届初赛，我在此基础上对代码做了一些调整）

#include <stdio.h> 
char flag[32]="Interestring Idea to encrypt";
 
int main() 
{    
	for(int i=0;i<7;++i)
	{        
		printf("%20f\n",*(float*)(flag+i*4));    
	} 
	printf("%20f\n",*(float*)(""))  ; 
	return 0; 
}

des加密代码（这个思路主要来自于湖湘杯2019）

import pyDes
import base64
from FLAG import flag
deskey = "********"
DES = pyDes.des(deskey)
DES.setMode('ECB')
DES.Kn = [
			[1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0],
			[1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0], 
			[0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0],
			[1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1], 
			[0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1],
			[0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0],
			[0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0],
			[0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0],
			[1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0],
			[0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0],
			[0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1],
			[0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0],
			[1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0],
			[1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1],
			[1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1],
			[1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1]
		]
cipher_list = base64.b64encode(DES.encrypt(flag))
#b'vrkgBqeK7+h7mPyWujP8r5FqH5yyVlqv0CXudqoNHVAVdNO8ML4lM4zgez7weQXo'

music

注：由于考察点重复，最后关头我把题目去掉了

题干

小Z喜欢听音乐，可是他不是VIP，也不想花钱下载音乐，可是你却在无意中发现了他拥有大量的音乐资源。试问，他是怎么做到的？flag格式为actf{***}

考察点

音频解密（接近于杂项）

灵感来源于学长分享的一片文章，我还对这篇文章提出了一些改进（即批量音频解密），然后把原文和改进后的文章一起发到了公众号“中南极光网安实验室”上。

hint

1.当你欣赏音乐的时候，记得打开文件看看哦

writeup

这道题其实是出自我的那篇推送文章的。自从XX音乐被爆只采用简单的异或加密以后，我就获得和很多首好听的歌曲。当然，这次的密钥不是0xa3，但分析方法一样。用010editor等十六进制编辑工具打开文件，看到文件里面大部分值为0x36，所以考虑到密钥的值为0x36，所以异或一下。

flag不在音频里面，为了表彰一下大家，只需要去文件里面搜一下字符串即可。然后在文章结尾找到的是一串base64，解密一下即可。

题目源代码

本次题目的编写没有用脚本，用的是010editor自带的异或功能。不过想要看批量解密的话，可以去公众号看，博客已经在路上了。

rsa0

题干

看看rsa的资料，学学python吧，这种简单题绝对不卡你！flag格式为actf{***}

考察点

压缩包伪加密，RSA基础知识与参数

hint

1.搞清楚各个参数的意义

writeup

都说了是压缩包伪加密，解决一下应该不难。

然后里面是最简单的rsa了，看一下资料应该能解决。

脚本

import gmpy2
from Cryptodome.Util.number import *
p = 9018588066434206377240277162476739271386240173088676526295315163990968347022922841299128274551482926490908399237153883494964743436193853978459947060210411
q = 7547005673877738257835729760037765213340036696350766324229143613179932145122130685778504062410137043635958208805698698169847293520149572605026492751740223
e = 65537
c = 50996206925961019415256003394743594106061473865032792073035954925875056079762626648452348856255575840166640519334862690063949316515750256545937498213476286637455803452890781264446030732369871044870359838568618176586206041055000297981733272816089806014400846392307742065559331874972274844992047849472203390350
phi = (p-1)*(q-1)
n = p*q
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print (long_to_bytes(m))

出题源代码

from Cryptodome.Util.number import *
import random

FLAG=#hidden, please solve it
flag=int.from_bytes(FLAG,byteorder = 'big')


p=getPrime(512)
q=getPrime(512)

print(p)
print(q)
N=p*q
e=65537
enc = pow(flag,e,N)
print (enc)

baby-aes

题干

AES是一种十分高效安全的对称加密方式，在现代密码学中有着举足轻重的地位。小Z对此很放心，于是就写了一个脚本用AES加密，你能获得他的明文嘛？flag格式为actf{***}

考察点

aes中的弱点（密钥），密钥、iv的作用，爆破

hint

1.现代密码的薄弱点在哪里

writeup

注意一下，这里的key和iv，虽说key是32字节，但是存在很多重复的现象。而且为了降低运算复杂度，我把key和iv的异或值给了处理。所以，我们只需要爆破即可，时间复杂度为256的二次方=65526次

脚本如下（时间不长，就懒得写break了）

from Cryptodome.Cipher import AES
import os
from Cryptodome.Util.number import *
import gmpy2

def main():
    enc_flag=b'\x8c-\xcd\xde\xa7\xe9\x7f.b\x8aKs\xf1\xba\xc75\xc4d\x13\x07\xac\xa4&\xd6\x91\xfe\xf3\x14\x10|\xf8p'
    xornum=91144196586662942563895769614300232343026691029427747065707381728622849079757
    for i in range(0,256):      
        for j in range(0,256):
             num=i*256+j
             subkey=long_to_bytes(num).ljust(2,b'\x00')
             key=subkey*16
             iv=long_to_bytes(bytes_to_long(key)^xornum)[-16:].ljust(16,b'\x00')
             aes=AES.new(key,AES.MODE_CBC,iv)
             flag = aes.decrypt(enc_flag)
             if(flag[:4]==b'actf'):
                 print(flag)

if __name__=="__main__":
    main()

出题源代码

from Cryptodome.Cipher import AES
import os
import gmpy2
from flag import FLAG
from Cryptodome.Util.number import *

def main():
    key=os.urandom(2)*16
    iv=os.urandom(16)
    print(bytes_to_long(key)^bytes_to_long(iv))
    aes=AES.new(key,AES.MODE_CBC,iv)
    enc_flag = aes.encrypt(FLAG)
    print(key)
    print(iv)
    print(enc_flag)
#91144196586662942563895769614300232343026691029427747065707381728622849079757
#b'\xc9\x81\xc9\x81\xc9\x81\xc9\x81\xc9\x81\xc9\x81\xc9\x81\xc9\x81\xc9\x81\xc9\x81\xc9\x81\xc9\x81\xc9\x81\xc9\x81\xc9\x81\xc9\x81'
#b'\x87lQbI0\xfc\xe6\xaa\x05P\xb1\x01\xd1pL'
#b'\x8c-\xcd\xde\xa7\xe9\x7f.b\x8aKs\xf1\xba\xc75\xc4d\x13\x07\xac\xa4&\xd6\x91\xfe\xf3\x14\x10|\xf8p'
if __name__=="__main__":
    main()

rsa3

题干

安全的密码算法，往往找不到任何的规律和联系。小Z由于学艺不精，无意中设计了一套极其危险的密码算法，你能帮忙破解一下这个密码算法中的秘密嘛？flag格式为actf{***}

考察点

经典费马分解

hint

1.RSA常见的攻击方式

writeup

其实这道题和省赛拿到没做出来的题目考点是一样的，所以那次省赛我已经有脚本了，但是省赛题目不应该这么出，怎么到了最后变成了电脑性能的较量。。

我觉得要考费马分解应该这样出：大家可以看到，题目中的两个素数之间相隔很近，这就给费马分解提供了机会（虽然我不知道网上有没有像我一样用这个next_prime这个函数的，但是意思应该也会相近），大家可以上网查查相关资料，省赛的时候一个学弟的脚本挺不错的，还多线程。但是我当时候的脚本和他写得不一样，当然也能解出来，不过哪时间复杂度可能稍慢一些，现在给出我的脚本：

import gmpy2
from Cryptodome.Util.number import *
n=177606504836499246970959030226871608885969321778211051080524634084516973331441644993898029573612290095853069264036530459253652875586267946877831055147546910227100566496658148381834683037366134553848011903251252726474047661274223137727688689535823533046778793131902143444408735610821167838717488859902242863683
c=1457390378511382354771000540945361168984775052693073641682375071407490851289703070905749525830483035988737117653971428424612332020925926617395558868160380601912498299922825914229510166957910451841730028919883807634489834128830801407228447221775264711349928156290102782374379406719292116047581560530382210049
e=65537

for b in range(0,10000):
    a=gmpy2.iroot(n+b*b,2)[0]
    if(a*a-b*b==n):
        p=a+b
        q=a-b
        break;
assert(p*q==n)
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print (long_to_bytes(m))

我通过修改学弟的脚本也可以解决这道题。

import threading

def isqrt(n):
    x = n
    y = (x + n // x) // 2
    while y < x:
      x = y
      y = (x + n // x) // 2
    return x

def Fermat(num, x):
    y2 = x*x - num;
    y = isqrt(y2);
    if y*y == y2:
        print([x+y, x-y]);

if __name__ == "__main__":
    num = int(input('n='))
    x = isqrt(num)
    if x*x < num:
        x += 1
    i = 1
    while(i < 1e20):
        threads = []
        for j in range(40):
            t = threading.Thread(target = Fermat, args = (num, x))
            i += 1
            x += 1
            threads.append(t)
        for t in threads:
            t.start()
        for t in threads:
            t.join()

用这段代码可以在短时间内解出p,q。

出题源代码

from flag import FLAG
from Cryptodome.Util.number import *
import gmpy2
import random

e=65537
p = getPrime(512)
q = int(gmpy2.next_prime(p))
n = p*q
m = bytes_to_long(FLAG)
c = pow(m,e,n)
print(n)
print(c)

TinySPN(by )

注：出题方向是我提出的，但是这里面的题干，源代码和解题脚本都是DJ学长 写的，我只负责把它放到服务器上，并且写出交互代码。

题干

SPN is a classical design patter in cryptography.

nc 47.103.117.169 10003

flag格式为flag{***}

考察点

线性/差分密码分析，交互

hint

1. what is SBOX?
2. why can’t we replace SBOX in cipher?

writeup

TL;DR

attack simple SPN by chosen-plaintext attack, use linear cryptanalysis or differential cryptanalysis will break it. exp use linear cryptanalysis.

Detail

because this SPN cipher is so simple, so we just need following steps.

1. get LAT, like example(Linear Approximation Table).
2. find one path with high bias.
3. collecting enough plaintext-cipher pairs.
4. extracting key from pairs.(check exp for more details).(linear_cryptanalysis.py is a example of this step, but code is like a shit so you’d better forget it.)
5. decrypt flag.

test.py is my test data, ignore it.

if SBOX is so good that can’t break it, record it and replay exp~

send me this SBOX so that I can post it~

exp

#!/usr/bin/python3

from typing import List, Tuple
from tqdm import tqdm
# import test
# import pysnooper
from util import doxor, doin, trans_inv, SZ
from binascii import unhexlify
from codecs import encode
import random
import pwn

def maskeq(a: int, b: int) -> bool:
    c: int = 0
    while b > 0:
        if b&1:
            c ^= (a&1)
        b //= 2
        a //= 2
    return c==0

def LAT(sbox: List[int]) -> List[List[int]]:
    count = []
    for row in tqdm(range(256), desc="compute LAT"):
        count.append([])
        for col in range(256):
            cnt = -128
            bitmask = (row << 8) | col
            for i in range(256):
                if maskeq((i << 8) | sbox[i],  bitmask):
                    cnt += 1
            count[row].append(abs(cnt))
        count[row].append(row)
    return count

def check(num: int, bitmask: int) -> bool:
    a = 0
    while bitmask > 0:
        if bitmask & 1 == 1:
            a ^= num & 1
        bitmask //= 2
        num //= 2
    return a == 0

def check_key(text_pairs: List[Tuple[int, int]], sbox: List[int], key: int, mask: int) -> int:
    cnt = 0
    for text_pair in text_pairs:
        (plain, cipher) = text_pair
        mid = cipher ^ key
        mid = sbox[mid] 
        if check((plain << 8) | mid, mask):
            cnt += 1
    return cnt

# @pysnooper.snoop()
def decrypt(sbox, sboxi, ct, k):
    pt = ''
    for i in range(0, len(ct), SZ):
        res = decrypt_block(sbox, sboxi, ct[i:i+SZ], k)
        pt += ''.join(map(chr, res))
    return pt

def decrypt_block(sbox, sboxi, pt, ks):
    cur = doxor(pt, ks[SZ:])
    cur = list(map(lambda x:sbox[x], cur))
    cur = trans_inv(cur)
    cur = list(map(lambda x:sboxi[x], cur))
    cur = doxor(cur, ks[:SZ])
    return cur

def compute_frontkey(sbox, sboxi, pt: List[int], ct: List[int], lastkey: List[int]) -> List[int]:
    cur = doxor(ct, lastkey)
    cur = list(map(lambda x:sbox[x], cur))
    cur = trans_inv(cur)
    cur = list(map(lambda x:sboxi[x], cur))
    return doxor(cur, pt)

def doin(x):
    return list(unhexlify(x))

def doout(x):
    tmp = ''.join(map(chr, x))
    return (encode(tmp.encode(), 'hex')).decode()

def main():
    # pwn.context.log_level = "DEBUG"
    # io = pwn.remote("192.168.16.128", 9999)
    io = pwn.process("../src/server.py")
    sbox_str = io.readline()
    sbox: List[int] = list(map(int, sbox_str[1:-2].split(b",")))
    sboxi: List[int] = []
    for i in range(256):
        sboxi.append(sbox.index(i))
    # print(sbox)
    flag_ct = doin(io.readline().strip())
    # print(flag_ct)
    pts: List[str] = []#test.pt
    cts: List[str] = []#test.ct
    for i in tqdm(range(2048), desc="collect plaintext-cipher paits"):
        pt = random.randint(0, (1<<64)-1)
        pt = "{:016x}".format(pt)
        io.sendline(pt)
        ct = io.readline().strip()
        pts.append(pt)
        cts.append(ct)
    # print("pt0: {}".format(pts[0]))
    # print("ct0: {}".format(cts[0]))
    lat = LAT(sbox)
    ptx = list(map(lambda x:(int(x[0:2], 16)), pts))
    key = []
    for i in range(8):
        ctx = list(map(lambda x:(int(x[i*2:i*2+2], 16)), cts))
        lat.sort(key=lambda x:x[(1<<(7-i))], reverse=True)
        # print("{}th byte is for LT{}".format(i, lat[0][256]))
        res = []
        for k in tqdm(range(256), desc="compute {}th byte of key".format(i+9)):
            res.append((k, abs(check_key(zip(ptx, ctx), sbox, k, (lat[0][256]<<8) |0b10000000)-(len(pts)//2))))
        res.sort(key=lambda x: x[1], reverse=True)
        key.append(res[0][0])
        # print(res)
        # print("{}th key is {:02x}".format(i+9, res[0][0]))
    pt1 = doin(pts[0])
    ct1 = doin(cts[0])
    key = compute_frontkey(sbox, sboxi, pt1, ct1, key) + key
    print("computed key: {}".format(doout(key)))
    # print(key)
    ans = decrypt(sbox, sboxi, flag_ct, key)
    if ord(ans[-1]) < 9:
        ans = ans[:-ord(ans[-1])]
    print(ans)

if __name__ == "__main__":
    main()

题目源代码

#!/usr/bin/python3

import os
from binascii import hexlify, unhexlify
import Crypto.Random.random as random
from secret import flag

SZ = 8

sbox = list(range(256))
random.shuffle(sbox)
sboxi = []
for i in range(256):
    sboxi.append(sbox.index(i))

def doxor(l1,l2):
    return [x[0]^x[1] for x in zip(l1,l2)]

def trans(blk):
    res = []
    for k in range(0, SZ, 8):
        bits = [bin(x)[2:].rjust(8,'0') for x in blk[k:k+8]]
        for i in range(8):
            res.append(int(''.join([x[i] for x in bits]),2))
    return res

def encrypt_block(pt, ks):
    cur = doxor(pt, ks[:SZ])
    cur = [sbox[x] for x in cur]
    cur = trans(cur)
    cur = [sboxi[x] for x in cur]
    cur = doxor(cur, ks[SZ:])
    return cur

def encrypt(pt, k):
    x = 0 if len(pt)%SZ==0 else (SZ-len(pt)%SZ)
    pt += [x]*x
    ct = ''
    for i in range(0, len(pt), SZ):
        res = encrypt_block([x for x in pt[i:i+SZ]], k)
        ct += ''.join(["{:02x}".format(xx) for xx in res])
    return ct

def doout(x):
    if len(x) % 16:
        x = (16 - len(x) % 16) * "0" + x
    return x

def doin(x):
    return list(unhexlify(x))

def genkeys():
    return list(os.urandom(2*SZ))

if __name__ == "__main__":
    print(sbox)
    key = genkeys()
    ct = encrypt(flag, key)
    print(ct)
    while True:
        pt = doin(input())
        print(doout(encrypt(pt, key)))

• 作者： 痛并快乐着
• 文章链接: https://life-extension.github.io/2020/02/16/ACTF新人赛密码学部分wp/
• 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-ND 4.0 许可协议。转载请注明出处!

Related post

Comment

Share

To Top «Pre post Next post»

• 极光实验室战队考核密码学部分考察点与题解

  四月 1日, 2020

  关键词：DH密钥交换协议，Coppersmith攻击，混合密码通信，rsa及aes编程。 题目 出题思路由于是战队考核，这次的题目应出得相对综合，也更考验同学们的知识面和对各方面加密的理解和把握能力。同时，题目应当结合密码学的实际应用...

  
• Coppersmith攻击方式小结

  三月 29日, 2020

  关键词：rsa，coppersmith攻击。 CopperSmith攻击的种类真的很多，以下是我归纳的几种常见形式： 一道新的例题——p的高位和地位泄露摘自：Securinets CTF Quals 2020 - Destructio...

  
• ACTF2020密码学部分writeup

  六月 5日, 2020

  编写的项目文件请参考项目链接。同时欢迎大家访问ACTF2020的所有赛题。喜欢的话请多多资瓷一下，给我们实验室的项目加个Star或者Fork，谢谢。 为了保护服务器的同时不给选手带来更多困难，密码学部分的交互题开了pow算力检测，我也...

  
• 通过python脚本自动插入汇编反调试代码

  五月 20日, 2020

  研究背景在之前OLLVM项目的研究过程中，我们发现反调试技术对反混淆脚本有一定的干扰作用，如果可以在OLLVM的中间代码中自动化插入反调试代码，那么就可以给OLLVM的代码混淆增加一层保障。 方案分析探讨多种方案以后，我认为最适合在汇...

  
• 答辩顺序抽签小程序

  五月 14日, 2020

  最近比较喜欢动手编写小程序和脚本。晚上有同学和我讨论对答辩队伍进行公平抽签的方案，所以打算编写一个很简单的小脚本，并做到尽量减少计算量。 脚本思路按照一定根据给各个队伍排序，然后初始化抽签序号池，每次随机获取池内的一个值，交给其中一支...

  
• 课堂记录小助手

  五月 7日, 2020

  作为一名课代表，我需要每天记录同学在QQ群的签到和回答问题情况。开始我是直接把记录复制到word里面手动提取有用的消息，最后我决定解放双手编写一个自动化处理脚本。 这个脚本需要一些什么功能呢？1.最基础的，就是从漫长的聊天记录中提取专...

  
• 基于门限方案的条形码保密及容错技术

  四月 30日, 2020

  关键词：门限方案，条形码保密，条形码容错，条形码认证与防伪造。 经历过初期两个小项目的探索，我们项目团队积累了一定的项目研究经验，在老师和16级学长的帮助下，我们把研究方向转到了门限方案的实际应用上。结合市面上用9张合并的条形码提高条...

  
• 2020新年原创脚本-其中的小把戏你清楚吗

  四月 26日, 2020

  关键词：随机数素数生成，新年祝福小程序。 脚本创作这是我在大年三十写的一个程序，当时我正准备去伯克利交流，但由于疫情的缘故，出国变数增大，所以我就打算通过随机数“未卜先知”。以下就是我的脚本： 12345678910111213141...

  
• 基于CRT的物流信息安全处理方案

  四月 15日, 2020

  关键词：中国剩余定理，密钥分发技术，隐私保护。 引言在2018年11月份的时候，段老师在密码学课上讲到了密钥分发协议，我当时就觉得这个协议很有意思也很有应用前景。后来老师还很主动地分享了一下它的idea，其中一部分就是有关物流单上的信...

  
• 基于CRT的新型群文件共享系统

  四月 13日, 2020

  关键词：隐私保护，权限管理，身份认证，中国剩余定理，密钥分发，密钥更新。 这个项目的是在2019年寒假期间进行的，4月份在中南大学信息安全作品赛答辩，但是由于功能只实现了主体部分，加之我在台上比较胆怯紧张，所以只获得团队三等奖，但是当...

  

Please check the parameter of comment in config.yml of hexo-theme-Annie!