crypto3

发表于 | 阅读次数:

仿射密码，题目来源：BITSCTF 2017

fanfie

题目密文：

1
MZYVMIWLGBL7CIJOGJQVOA3IN5BLYC3NHI

base解密、rot解码均失败，猜测为仿射密码或是替换密码。
BITSCTF进行base32加密得到：

1
IJEVIU2DKRDA====

对字母编码：

1
2
A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z  2  3  4  5  6  7
0  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

与密文对比发现 I->M 匹配, D->L 匹配(离谱orz)
相应字母的编码比对可得：

1
3  -> 11	4  -> 24	8  -> 12	20 ->  8	21 -> 21	25 ->  9	26 -> 22

仿射密码

编码表： A-Z 对应数字 0-25 (通常情况)
明文：hot(编码：7,14,19)
加密：设密钥 K = (7,3),编码表总数 n = 26，
(7 × 7 + 3) mod 26 = 52 mod 26 =0
(7 × 14 + 3) mod 26 = 101 mod 26 =23
(7 × 19 + 3) mod 26 =136 mod 26 =6
对应密文：AXG
模逆：若a,b两数的乘积对正整数n取模的结果为1. 则称a,b互为另外一个的模逆.
　　3×7 = 21; 21 % 20 = 1 ; 所以3,7 互为 20 的 模逆
　　9×3 = 27; 27 % 26 = 1 ; 所以9,3 互为 26 的 模逆
求模逆代码(C++):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
using namespace std;
int main()
{
	int a,b,n;
	int tump=0;
	cout<<"请输入a：";
	cin>>a;
	cout<<"请输入n：";
	cin>>n;
	for(int i=1;i<1000000;i++)
	{
		if((a*i)%n==1)
		{
			cout<<a<<"对"<<n<<"的模逆为"<<i;
			tump=1;
			break; 
		}
	}
	if(tump==0)cout<<a<<"对"<<n<<"没有模逆"; 
}

密钥求解代码(C++):

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
#include<iostream>
using namespace std;
int main()
{
	int miwen1,miwen2,miwen3,ming1,ming2,ming3,n;
	cout<<"请输入编码总数n：";
	cin>>n;
	cout<<"请输入第一组密文、明文对应编码：";
	cin>>miwen1>>ming1;
	cout<<"请输入第二组密文、明文对应编码：";
	cin>>miwen2>>ming2;
	cout<<"请输入第三组密文、明文对应编码：";
	cin>>miwen3>>ming3;
	int a,b,a_;//密钥 K(a,b) 
	for(int i=1;i<n;i++)
	{
		//a从1到n枚举
		int tump=0; 
		for(int j=1;j<n;j++)
		{
			if((i*j)%n==1)
			{
				a_=i;//a对n的逆为j 
				tump=1;
				break; 
			}
		}
		if(tump==0)continue;//a对n无逆
		int b1,b2,b3;
		for(int k=1;k<n;k++)//枚举b1 
		{
			if((a_*ming1 + k)%n==miwen1)
			{
			b1=k;
			break;
			}
		}
		for(int k=1;k<n;k++)//枚举b2 
		{
			if((a_*ming2 + k)%n==miwen2)
			{
			b2=k;
			break;
			}
		}
		for(int k=1;k<n;k++)//枚举b3 
		{
			if((a_*ming3 + k)%n==miwen3)
			{
			b3=k;
			break;
			}
		}
		
		if(b1==b2&&b1==b3)
		{
			b=b1;
			a=i;
			break;
		}
	}
	cout<<"密钥 K("<<a<<","<<b<<")";
}

求得密钥 K(13,4),可以得到密码表如下：

1
2
3
A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z  2  3  4  5  6  7

E  R  6  L  Y  F  S  7  M  Z  G  T  A  N  2  H  U  B  O  3  I  V  C  P  4  J  W  D  Q  5  K  X

密文仿射，得到明文：IJEVIU2DKRDHWUZSKZ4VSMTUN5RDEWTNPU
base32解密得：BITSCTF{S2VyY2tob2Zm}