WriteUp

CTFSeason2

发布日期: 2021-02-14

Hgame Div 1,2题解

0.About

终于在接触CTF差不多大约5个月后，尝试打了一下杭州电子科大的CTF招新题（~~总体感觉只有4个字：我太菜了~~

只做了密码学，其他的题目不看，~~因为不是我研究的内容（~~

~~#define huangx607087 feiwu~~

Update 2.15

~~本以为21Feb2会先出的，结果发展到了瓶颈期~~，21Feb2原计划是2.12或者2.13发布，结果到了2.15都没能发布（因为只刷了4题，没刷满5题），我是fw（

1.组合密码

首先拿到的附件很简单，就一个txt文件，里面不出意外应该是写的摩尔斯电码。随便在网上找一个解密网站解密，得到了一串数字，看到所有的数字都在$40$到$128$之间，应该是ASCII码，转换成字符，发现最后是两个等于号，果断Base64解密。

Base64解密之后，我们得到了这样一串字符：Vigenere +Liki:}VkmvJb!1XtAxe!hpM1{M+9xqzrTM_Nj~cRg4x

看来应该是维吉尼亚密码，用密钥Liki进行解密，然后就得到了这样的内容：}KccnYt!1NlPpu!zeE1{C+9pfrhLB_Fz~uGy4n

感觉没什么思路，不过看到两个大括号的顺序是乱的，目测应该是栅栏密码，一个一个调，发现栅栏数量是$6$的时候，比较符合flag的格式：}!!Ch~K1z+LucNe9BGclEp_ynP1fF4Yp{rzntu。

不难发现最后$5$个字母对应的明文应该是emagh，符合凯撒密码的样式。因此直接找一个凯撒密码解密的网站即可得到最终的结果，最后倒过来提交以下就行了。

2.对称之美

PART 1 阅读题目

首先先来看一下题目

import random
import string
import itertools
from secret import FLAG
key = ''.join(random.choices(string.ascii_letters + string.digits, k=16))
cipher = bytes([ord(m)^ord(k) for m, k in zip(FLAG, itertools.cycle(key))])
print(cipher)
#cipher=*

题目给出了密钥的长度是$16$，然后最终结果就是将flag和密钥异或得出来的值。其中密钥里只含有A-Z,a-z和0-9，密文的长度是$1069$

PART 2 拆解密文，计算方差

发现密钥的长度是$16$，密文很长，不出意外应该是通过字母频率攻击得到的。所以我们可以编写C++程序，将密文中的第$1,17,33…$位，$2,18,34,…$位进行逐个拆解，然后每个文件都爆破一下，计算爆破时的方差即可。

拆解密文的代码

#include<bits/stdc++.h>
using namespace std;
int a[10000];
char s[40]="Cip00.txt";
int f[18]={1,2,3,4,5,6,7};
void generate(int x)
{
	s[3]='0'+x/10;
	s[4]='0'+x%10;
	FILE *gp=fopen(s,"w");
	int i,j;
	for(i=x;i<=1069;i+=16)
		fprintf(gp,"%d\n",a[i]);
	fclose(gp);
}
int main()
{
	FILE *fp;
	int i,j;
	fp=fopen("cipher.txt","r");
	for(i=1;i<=1069;i++) 
		fscanf(fp,"%d",&a[i]);
	fclose(fp);
	for(i=1;i<=16;i++)
		generate(i);
	return 0;
}

然后是爆破密钥的代码，其中loss是计算的方差，初始化函数里有每个字母出现的概率，比如A出现的概率是$8.15\text{percent}$(注：以后博客中百分号用percent单词表示，因为上传博客时有百分号的地方会出错)，那么pos[0]=8.15

我们把每次爆破出的概率放到cul数组中，最后的方差$ V=\sum_{i=0}^{25}(\mathrm{pos}[i]-\mathrm{cul}[i])^2 $。

这个方法也很巧妙，因为这个代码可以通过修改字符数组的方式，连续读取$16$个文件，并对应输出$16$个文件

#include<bits/stdc++.h>
using namespace std;
struct asdf{char chr;double loss;
}data[95];
double pos[26],cul[26],K=0;
char files[26]="Cip00.txt";
char outfiles[26]="Res00.txt";
char Table[90]="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
int a[45000],b[45000],n=0; 
bool cmp(asdf a,asdf b)
{
	return a.loss<b.loss;
} 
void init(int x)
{
	memset(cul,0,sizeof(cul));
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	n=0;K=0;
	files[3]='0'+x/10;
	files[4]='0'+x%10;
	outfiles[3]='0'+x/10;
	outfiles[4]='0'+x%10;
	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=fopen(files,"r");
	while(~fscanf(fp,"%d",&a[++n]));
	n--;
	fclose(fp);
}
double culcloss()
{
	memset(cul,0,sizeof(cul));
	int i,j;
	double V=0;
	for(i=1;i<=n;i++)
	{
		if(b[i]>='A'&&b[i]<='Z')
			cul[b[i]-65]++;
		if(b[i]>='a'&&b[i]<='z')
			cul[b[i]-97]++;
	}
	for(i=0;i<26;i++)
		V+=(pos[i]-cul[i])*(pos[i]-cul[i])*100/K;
	return V;
}
void solve(int x)
{
	K=0;
	memset(b,0,sizeof(b));
	int i,j;
	for(i=1;i<=n;i++)
		b[i]=a[i]^Table[x];
	for(i=1;i<=n;i++)
		if(b[i]>='a'&&b[i]<='z'||b[i]>='A'&&b[i]<='Z')
			++K;
	data[x].chr=Table[x];
	data[x].loss=culcloss();
}
int main()
{
	int i,j;
	for(i=1;i<=16;i++)
	{
		init(i);
		for(j=0;j<strlen(Table);j++)
			solve(j);
		sort(data,data+strlen(Table),cmp);
		FILE *gp=fopen(outfiles,"w");
		for(j=0;j<strlen(Table);j++)
			fprintf(gp,"chr=%c  loss=%.4lf\n",data[j].chr,data[j].loss);
		fclose(gp);
	}
}

PART 3 最后调整，得出答案

我们来看看第$1$组输出的前$6$行输出和第$4$组输出的前$6$行

Res01.txt                             _ [] X
____________________________________________
chr=8  loss=507.0642
chr=9  loss=748.7868
chr=2  loss=1161.6835
chr=3  loss=1385.8863
chr=4  loss=1426.1932
chr=5  loss=1430.1443

Res04.txt                             _ [] X
_____________________________________________
chr=e  loss=418.8335
chr=E  loss=418.8335
chr=c  loss=755.6027
chr=C  loss=755.6027
chr=d  loss=844.2964
chr=D  loss=844.2964

很显然，我们可以看出，第一组输出loss最小的是字符$8$，所以密钥应该是以$8$开头的，不过问题来了，每组输出对应的大小写字母都是一致的，也就是说，第$4$组输出我们无法判断E究竟是大写还是小写。

我们这边可以假设所有的字母都是大写字母，然后我们可以尝试解密。根据我解出的结果是key=b'89QEUTFDJAECOLTK'

然后带入密文进行异或解密，前40位是这样的：\nSYmmetry\x00In\x00ARt iS when THe\x00ELemeNts of

可以看到里面有\x00，对应的ASCII码是$0$，而如果我们将对应的部分改成小写字母，那么结果应该是\x20，也就是空格了。

修改之后，我们可以继续发现很多地方的大小写字母杂乱，看到输出实际上有英文句号的，那么可以推出只有一句话的开头才能用大写字母，所以不对的地方密钥前给成小写字母，最终我们可以得到正确的密钥是b'89qEUTFDJaeColtK'

最后我们就可以得出答案了。

from given import cipher
key=b'89qEUTFDJaeColtK'
s=""
for i in range(len(cipher)):
    s+=chr(key[i%len(key)]^cipher[i])
print(s)
'''
Symmetry in art is when the elements of 
a painting or drawing balance each other 
out. This could be the objects themselves, 
but it can also relate to colors and 
other compositional techniques.
You may not realize it, but your brain 
is busy working behind the scenes to seek 
out symmetry when you look at a painting. 
There are several reasons for this. The 
first is that we're hard-wired to look for 
it. Our ancient ancestors may not have had 
a name for it, but they knew that their 
own bodies were basically symmetrical, as 
were those of potential predators or prey. 
Therefore, this came in handy whether 
choosing a mate, catching dinner or 
avoiding being on the menu of a snarling, 
hungry pack of wolves or bears!
Take a look at your face in the mirror 
and imagine a line straight down the 
middle. You'll see both sides of your 
face are pretty symmetrical. This is 
known as bilateral symmetry and it's 
where both sides either side of this 
dividing line appear more or less the same.
So here is the flag: 
hgame{X0r_i5-a_uS3fU1+4nd$fUNny_C1pH3r}
'''

3.Transformer

题目意思很简单，一个替换密码，给出了$240$个片段和打乱的密文。不过虽然是打乱的，但是解压后我们只需要在文件夹中按大小排序，就可以做到基本对应了（因为替换密码加密后长度不变。，最短的是$25$字节的，一共有$7$个，所以我们只需要阅读$7$个即可。

看到flag文件中有疑似flag的内容，很明显，应该果断替换，盲猜最前面的内容是hgame，其他几个未知的字符也可以加进去，最后得到了这样的内容：hgame{ea5y_f0r_fun^3nd&he11o_}

不过最后提交之后一直不对，看来还少些什么，回顾密文，我们决定把给出的这段话破译掉

1	Tqh ufso mnfcyh eaikauh kdkoht qpk aiud zkhc xpkkranc uayfi kfieh 2003, oqh xpkkranc fk "qypth{hp5d_s0n_szi^3ic&qh11a_}",Dai'o sanyho oa pcc oqh dhpn po oqh hic.

果然，破译后有了大发现：最后的一句话内容是to add the year at the end，那么后面应该加个$2021$，最后提交内容是

hgame{ea5y_f0r_fun^3nd&he11o_2021}，果然对了。

先看一下题目

from libnum import *
from Crypto.Util import number
from secret import FLAG
m = s2n(FLAG)
a = number.getPrime(1024)
p = number.getPrime(1024)
c = a ** p * m % p
print("a = {}".format(a))
print("p = {}".format(p))
print("c = {}".format(c))

题目最后给出了$a,p,c$的值。其中$a^pm\equiv c\pmod p$。

根据费马小定理可知，$a^p\equiv a\pmod p$，因此原式就是$am\equiv c \pmod p$，故$a^{-1}c\equiv m \pmod p$，我们只需要用内置函数求个逆元就结束了。

5.WhitegiveRSA

1
2
3

N = 882564595536224140639625987659416029426239230804614613279163
e = 65537
c = 747831491353896780365654517748216624798517769637260742155527

题目描述得很简单。看到$N$并不是特别长，直接放Sagemath分解就得到
$$
N=857504083339712752489993810777 ×1029224947942998075080348647219
$$
然后就是正常的因式分解了。

6.gcd or more?

这道题是RSA，$e=2$的情景，首先想到的就是枚举$m=kn+c$，不过貌似不可行

$e=2$时，我们可以口算出$x^2\equiv 1 \pmod p$的解是$1$和$p-1$。然后Sagemath开根得出一个特解。

最后就是参考RSA Notes 3的内容，$e,\phi$不互素的情况的解法。

7.The Password

题目的具体要求说的很明白了，就是求最后的$x$。

首先，最容易想到的，就是异或运算的交换性和相同的数异或等于$0$的性质，因此我们可以把所有的$y$与$n$先进行异或更新下。

刚开始拿到题目的时候，以为是梅森旋转中的移位，不过最后发现移位是循环移位。

考虑到异或是二进制里的加，加上近期自己正在学格密码，因此想到了矩阵运算。

验证了一下，果然符合循环移位异或的结果。那么我们就可以构建矩阵来解决问题了，附上sagemath中的代码

def solve(y,n,l,r):
    y^^=n
    M,v=[],[]
    for i in range(64):
        M.append([0]*64)
        v.append([0])
    for i in range(64):
        M[i][i],M[i][(i-l)%64],M[i][(i+r)%64]=1,1,1
    M=matrix(GF(2),M)
    for i in range(64):
        v[i]=y&1
        y>>=1
    v=vector(GF(2),v)
    M=M^-1
    G=vector(ZZ,M*v)
    s=0
    for i in range(64):
        s+=(G[i]<<i)
    print(hex(s))
#------main-below------#
Y=[15789597796041222200,8279663441787235887,9666438290109535850,10529571502219113153,8020289479524135048,10914636017953100490,4622436850708129231]
N=[14750142427529922,2802568775308984,15697145971486341,9110411034859362,4092084344173014,2242282628961085,10750832281632461]
L=[3,9,5,13,64-16,7,5]
R=[7,4,2,6,8,5,2]
for i in range(7):
    solve(Y[i],N[i],L[i],R[i])
'''
0x6867616d657b6c
0x316e6530725f61
0x31676562723026
0x697340316d706f
0x7231306e315e31
0x6e246372797074
0x6f7d
'''