huangx607087寒假的切题4

0.简介

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

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

1.[GUET-CTF2019]Uncle Sam

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

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上去。根本原因还是自己~~太菜了~~

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

题目给出的内容非常简单

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 求周期部分

#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$个），然后根据字母频率分析，计算方差即可，最后将方差排个序，每次选出最小的那个即可。

#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...的字样即可。

#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指针类型，代码如下

#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