21Jan4

huangx607087寒假的切题4

0.简介

一个密码学fw的切题笔记，很菜，别看

今天BUUCTF上到了2000分，后面剩下的题目就都是那些90+分，做出来的人很少的那种了，难度也是非常大的。因此打算后面几天把理论看看，并且还要打杭电持续一个月的CTF，自己的人工智能项目也摸了3天了，哎

1.[GUET-CTF2019]Uncle Sam

我们还是先看一下加密代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *
def generkey(k):
	p, q = getPrime(k), getPrime(k)
	pubkey = p**2 * q
	n = pubkey
	l = (p-1)*(q-1) / gcd(p-1, q-1)
	privkey = inverse(n, l)
	return pubkey, privkey

def encrypt(m, pubkey):
	return pow(bytes_to_long(m), pubkey, pubkey)
# n =  *
# d = *
# c = * 给出部分略去

很显然，这与RSA不一样，因为这道题公钥$n=p^2q$，虽然貌似也出现过所谓的$p^2q$之类的分解因式法，不过这貌似也并不可分解。

注意到$l=\text{lcm}(p-1,q-1)$，并且还给出了私钥$d$值位$n$模$l$下的逆元。查阅了相关资料，可以得知这是Schmidt-Samoa 公钥密码体系。

这一加密体系中，加密过程是$c\equiv m^n \pmod n $，而解密函数则是$m\equiv c^d\pmod{pq} $

下面简单地证明一下：

已知
$$
\phi(n)=\phi(p^2q)=p(p-1)(q-1)
$$
由费马小定理，可以推出
$$
a^{p(p-1)(q-1)} \equiv 1 \pmod n
$$
又因为
$$
dn\equiv 1 \pmod {(p-1)(q-1)}
$$
所以
$$
a^{nd}\equiv a^{nd \mod ((p-1)(q-1))} \equiv a
$$
所以
$$
a^{nd}-a\equiv 0 \pmod{pq}
$$
因此
$$
pq=\gcd(a^{nd}-a,n)
$$
由于$a$是任意的数字，因此我们可以取$a=2,3,4…$均可，为方便起见这里取$2$

解密代码非常短，不过推出这个式子还是非常不容易的（，何况这个加密方法一开始自己也没怎么接触过，看到$pq$总是会想到RSA上去。根本原因还是自己太菜了

1
2
3
4
from Crypto.Util.number import *
from given import n,c,d
x=GCD(n,pow(2,n*d,n)-2)
print(long_to_bytes(pow(c,d,x)))

2.[XNUCA2018]baby_crypto

题目给出的内容非常简单

1
2
3
4
5
6
7
8
The 26 letters a, b, c, ..., y, z correspond to the integers 0, 1, 2, ..., 25
len(key_a) = m
len(key_k) = n
c[i] = (p[i] * key_a[i % m] + key_k[i % n]) % 26
p is plain text, only lowercase letters are refered to.
c is encrypted text
I have appended the flag at the end of plain text, the format of which is like 'flagis......'
Now you have the encrypted text, Good luck!

很显然这是一个线性的加密，应该跟Vigena密码相似，我们还是一样，每$3$个字母一组，求出周期。

PART 1 求周期部分

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
#include<bits/stdc++.h>
using namespace std;
string s;
map<string,int>lst,mil;
string f(int x)
{
	string c="";
	c+=(x/(26*26))+97;
	c+=(x%(26*26)/26)+97;
	c+=x%26+97;
	return c;
}
int main()
{
	freopen("enc.txt","r",stdin);
	freopen("detPro.txt","w",stdout);
	int i,j;
	cin>>s;
	s=" "+s;
	for(i=1;i<s.length()-1;i++)
	{
		if(lst[s.substr(i,3)]==0)
			lst[s.substr(i,3)]=i;
		else
		{
			int det=i-lst[s.substr(i,3)];
			if(mil[s.substr(i,3)]==0)
				mil[s.substr(i,3)]=det;
			else
				if(det>10)
					mil[s.substr(i,3)]=min(det,mil[s.substr(i,3)]);
			lst[s.substr(i,3)]=i;
		}
	} 
	for(i=0;i<=26*26*26;i++)
	{
		if(mil[f(i)]!=0)
			cout<<f(i)<<"   "<<mil[f(i)]<<endl; 
	}
	return 0;
}

打开最后的文件，我们可以看到，最后很多的间隔都是$6$的倍数，比如$6,12,18,24,30,…$之类的数字，因此可以猜测，周期应该是$6$。

PART 2 分割&求表达式

得到周期是$6$之后，我们可以把原来的密文拆分成$6$个文件，间隔$6$个字母一个文件进行输出，然后分别求表达式。

求表达式的时候，由于加密是一次函数，因此我们不需要考虑加密函数，直接枚举解密函数（也是一次函数，一共有$12×26$个），然后根据字母频率分析，计算方差即可，最后将方差排个序，每次选出最小的那个即可。

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
using namespace std;
double pos[26],cul[26];
struct asdf{int K,B;double loss;
}data[500];
int n,k[12],str[40000];
bool cmp(asdf a,asdf b)
{
	return a.loss<b.loss;
}
void init()
{
	int i,j;
	pos[0]=8.15,pos[1]=1.44,pos[2]=2.76,pos[3]=3.79;
	pos[4]=13.11,pos[5]=2.92,pos[6]=1.99,pos[7]=5.26;
	pos[8]=6.35,pos[9]=0.13,pos[10]=0.42,pos[11]=3.39;
	pos[12]=2.54,pos[13]=7.1,pos[14]=8,pos[15]=1.98;
	pos[16]=0.12,pos[17]=6.83,pos[18]=6.1,pos[19]=10.47;
	pos[20]=2.46,pos[21]=0.92,pos[22]=1.54,pos[23]=0.17;
	pos[24]=1.98,pos[25]=0.08; 
	FILE *fp;
	fp=fopen("enc6.txt","r");
	char c;
	str[0]=-1;
	for(i=1;i<=4771;i++)
	{
		fscanf(fp,"%c",&c);
		str[i]=c-97;
	}
	fclose(fp);
	k[0]=1,k[1]=3,k[2]=5,k[3]=7,k[4]=9,k[5]=11;
	k[6]=15,k[7]=17,k[8]=19,k[9]=21,k[10]=23,k[11]=25;
}
double culcvarp()
{
	int i,j;
	double P=0;
	for(i=0;i<26;i++)
		P+=(cul[i]-pos[i])*(cul[i]-pos[i]);
	return P;
}
void transform(int K,int B)
{
	int i,j;
	for(i=0;i<26;i++) cul[i]=0;
	for(i=1;i<=4771;i++)
		cul[(K*str[i]+B)%26]++;
	for(i=0;i<26;i++)
		cul[i]/=47.71;
	data[++n].K=K,data[n].B=B,data[n].loss=culcvarp();
}
int main()
{
	int i,j;
	init();
	for(i=0;i<12;i++)
		for(j=0;j<26;j++)
			transform(k[i],j);
	sort(data+1,data+n+1,cmp);s
	FILE *fp;
	fp=fopen("fnc&pso6.txt","w");
	for(i=1;i<=n;i++)
		fprintf(fp,"D(x)=%dx+%d:loss=%.9lf\n",data[i].K,data[i].B,data[i].loss);
	fclose(fp);
	return 0;
}

每次求出来后，我们可以发现，输出的第一个表达式的loss只有$12$左右，而第二个表达式的loss已经达到了$200+$，因此我们可以断定，第一个表达式就是我们想求的那个表达式。

求出所有解密表达式之后，我们就可以求出最后的flag了,到时候只需要直接在输出文件中找到flag is...的字样即可。

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
#include<bits/stdc++.h>
using namespace std;
int n,m;
char str[40000],ans[40000];
int main()
{
	int i,j;
	FILE *fp=fopen("enc.txt","r");
	fscanf(fp,"%s",str);
	n=strlen(str);
	fclose(fp);
	fp=fopen("dec.txt","w");
	for(i=0;i<n;i+=6)
		ans[i]=(11*(str[i]-97)+20)%26+97;
	for(i=1;i<n;i+=6)
		ans[i]=(15*(str[i]-97)+21)%26+97;
	for(i=2;i<n;i+=6)
		ans[i]=(17*(str[i]-97)+1)%26+97;
	for(i=3;i<n;i+=6)
		ans[i]=(11*(str[i]-97)+22)%26+97;
	for(i=4;i<n;i+=6)
		ans[i]=(15*(str[i]-97)+24)%26+97;
	for(i=5;i<n;i+=6)
		ans[i]=(17*(str[i]-97)+5)%26+97;
	fprintf(fp,"%s",ans);
	fclose(fp);
	return 0;
}

3.[AFCTF2018]MagicNum

题目给出了$6$个浮点数，会想到以前讲过，C++的float和int都是$4$个字节，也就是$8$位十六进制数。因此，我们肯定是要把float转化成与之对应的在内存中存储方式完全一致的int值。因此我们可以考虑强制转换指针类型，将float指针类型输出时强制转换成int指针类型，代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
int n,m;
int main()
{
	int i,j;
	float f;
	for(i=1;i<=6;i++)
	{
		scanf("%f",&f);
		float *p=&f;
		printf("%x\n",*(int*) p);
	}
	return 0;
}
//72065910510177138000000000000000.000000
//74636661

最后只需要把我们每次得到的八位十六进制数一个字节一个字节地倒过来重新组装，就变成了flag

4.LeftOrRight

题目给出了一个无法打开的图片，转换成txt，可以看到开始和解为都有$32$个十六进制数，转换成字符，貌似这两个字符都仅仅是打乱了顺序而已，根据题目提示，这种题目应该是给出了一棵二叉树的先序遍历和中序遍历，让你求后序遍历。

难度不大，随便在网上找一个脚本抄一下就可以得到最后的答案了（我只是一个当年用6个月速成NOIP然后拿了245的fw而已

5.[XNUCA2018]Warmup

这道题给出了$6$个人的RSA加密后的$e,n,c$，仔细观察的话可以看到第一个和第四个的$n$是相等的，因此可以直接上共模攻击的脚本解决最后的flag

6.总结

总之，寒假4篇刷题笔记，的确让自己学到了不少东西。明天又杭电的CTF，还是要看看题目的，继续学习一点CTF知识，争取4月进校队吧（趁自己大一上半年GPA 4.24，寒假还没什么事情，多学点肯定是很好的

CTFSeason2
#ExpLog
21Jan4
http://example.com/2021/01/29/21Jan4/
作者
huangx607087
发布于
2021年1月29日
许可协议