实验目的

通过C＋＋编程实现移位密码和单表置换密码算法，加深对经典密码体制的了解。并通过对这两种密码实施攻击，了解对古典密码体制的攻击方法。

实验内容

  1. 根据实验原理部分对移位密码算法的介绍，自己创建明文信息，并选择一个密钥，编写移位密码算法实现程序，实现加密和解密操作。

  2. 两个同学为一组，互相攻击对方用移位密码加密获得的密文，恢复出其明文和密钥。

  3. 自己创建明文信息，并选择一个密钥，构建置换表。编写置换密码的加解密实现程序，实现加密和解密操作。

  4. 用频率统计方法，试译下面用单表置换加密的一段密文： SIC GCBSPNA XPMHACQ JB GPYXSMEPNXIY JR SINS MF SPNBRQJSSJBE JBFMPQNSJMB FPMQ N XMJBS N SM N XMJBS H HY QCNBR MF N XMRRJHAY JBRCGZPC GINBBCA JB RZGI N VNY SINS SIC MPJEJBNA QCRRNEC GNB MBAY HC PCGMTCPCD HY SIC PJEISFZA PCGJXJCBSR SIC XNPSJGJXNBSR JB SIC SPNBRNGSJMB NPC NAJGC SIC MPJEJBNSMP MF SIC QCRRNEC HMH SIC PCGCJTCP NBD MRGNP N XMRRJHAC MXXMBCBS VIM VJRICR SM ENJB ZBNZSIMPJOCD GMBSPMA MF SIC QCRRNEC 写出获得的明文消息和置换表。

实验过程

移位密码

实验原理

移位密码：将英文字母向前或向后移动一个固定位置。例如向后移动3个位 置，即对字母表作置换（不分大小写）。  
ABCDEFGHIJKLMNOPQRSTUVW XYZ  
DEFGHIJKLMNOPQRSTUVWXYZABC

设明文为：public keys,则经过以上置换就变成了：sxeolf nhbv。 如果将26个英文字母进行编码：A→0，B→1，...，Z→25，则以上加密过程可简单地写成： 明文：m＝m1m2...mi..., 则有 密文：c=c1c2...ci..., 其中 ci=(mi+key mod26)，i＝1，2，...。

算法流程图

加密

移位密码加密算法流程图

解密

移位密码解密算法流程图

实验代码

加密代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
cout << "请输入要加密的内容：\t";
string a;
getline(cin, a);
getline(cin, a);
//cout<<typeid(a[0]).name()<<endl;
int len = a.length();
int n1;//左移n位
cout << "请输入移位位数：\t";
cin >> n1;
if (n1 >= 26) { n1 %= 26; }
string* key1 = new string[len];
cout << "加密结果：\t\t";
for (int i = 0; i < len; i++) {
	if (a[i] < 65 || (a[i] > 90 && a[i] < 97) || a[i]>122) { cout << a[i]; continue; }
	if (a[i] >= 65 && a[i] <= 90) { a[i] += 32; }
	if (a[i] + n1 > 122) { a[i] -= 26; }
	key1[i] = char(int(a[i]) + n1);
	cout << key1[i];
}
cout << endl;

解密代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
cout << "请输入要解密的内容：\t";
string a;
getline(cin, a);
getline(cin, a);
int len = a.length();
int n1;//右移n位
cout << "请输入移位位数：\t";
cin >> n1;
if (n1 >= 26) { n1 %= 26; }
string* key1 = new string[len];
cout << "解密结果：\t\t";
for (int i = 0; i < len; i++) {
	if (a[i] < 65 || (a[i] > 90 && a[i] < 97) || a[i]>122) { cout << a[i]; continue; }
	if (a[i] >= 65 && a[i] <= 90) { a[i] += 32; }
	if (a[i] - n1 < 97) { a[i] += 26; }
	key1[i] = char(int(a[i]) - n1);
	cout << key1[i];
}
cout << endl;

实验结果

加密： 输入明文为public keys，密钥为3（即凯撒密码），输出结果应为sxeolf nhbv。

明文加密结果

解密：将上述得到的结果进行解密，输出结果应为public keys:

密文解密结果

对移位密码的攻击

实验原理

移位密码是一种最简单的密码，其有效密钥空间大小为25。因此，很容易用 穷举的方法攻破。穷举密钥攻击是指攻击者对可能的密钥的穷举，也就是用所有可能的密钥解密密文，直到得到有意义的明文，由此确定出正确的密钥和明文的攻击方法。对移位密码进行穷举密钥攻击，最多只要试译25次就可以得到正确的密钥和明文。

算法流程图

对移位密码的攻击算法流程图

实验代码

title
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
cout << "请输入要解密的内容：\t";
string b;
getline(cin, b);
getline(cin, b);
int len = b.length();
string* key1 = new string[len];
for (int j = 1; j <= 26; j++) {
	cout << "密钥为：" << j << "\t";
	for (int i = 0; i < len; i++) {
		string a = b;
		if (a[i] < 65 || (a[i] > 90 && a[i] < 97) || a[i]>122) { cout << a[i]; continue; }
		if (a[i] >= 65 && a[i] <= 90) { a[i] += 32; }
		if (a[i] - j < 97) { a[i] += 26; }
		key1[i] = char(int(a[i]) - j);
		cout << key1[i];
	}
	cout << endl;
}

实验结果

比如截获密文为：eq fsew ak osfosf!!

移位密码攻击

根据实验结果可以解出明文：my name is wanwan!! 密钥为18

单表置换密码

实验原理

单表置换密码就是根据字母表的置换对明文进行变换的方法，例如，给定置换 ABCDEFGHIJKLMNOPQRSTUVWXYZ HKWTXYSGBPQEJAZMLNOFCIDVUR

明文：public keys, 则有 密文：mckebw qxuo。 单表置换实现的一个关键问题是关于置换表的构造。置换表的构造可以有各种不同的途径，主要考虑的是记忆的方便。如使用一个短语或句子，删去其中的重复部分，作为置换表的前面的部分，然后把没有用到的字母按字母表的顺序依次放入置换表中。

算法流程图

单表置换密码算法流程图

实验代码

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
map<string, string>mp_str;
map<char, char>mp_ch;
string str1 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
string str2 ;
string key1="";
cout << "输入密钥：\t";
getline(cin, str2);
getline(cin, str2);
map<char, int>mp_is;
//将字母表所有字母出现标志位设置为0
for (int i = 0; i < 26; i++) {
	mp_is[str1[i]] = 0;
}
//如果在输入中出现过 标志位设置为1 在ley中添加
for (int i = 0; i < str2.length(); i++) {
	if (str2[i] >= 97 && str2[i] <= 122) { str2[i] -= 32; }
	else if (str2[i] < 65 || str2[i]>90) { continue; }
	if (mp_is[str2[i]] == 0) { key1 += str2[i]; }
	mp_is[str2[i]] = 1;
}
//没出现过的按顺序添入key中
for (int i = 0; i < 26; i++) {
	if (mp_is[str1[i]] == 0) { key1 += str1[i]; }
}
cout << "密钥为：\t" << key1 << endl;
str2 = key1;
//建立映射表
for (int i = 0; i < 26; i++) {
	mp_ch[str1[i]] = str2[i];
}
cout << "输入明文：\t";
string a;
getline(cin, a);
int len = a.length();
string b = "";
cout << "加密为：\t";
for (int i = 0; i < len; i++) {
	if (a[i] >= 97 && a[i] <= 122) { a[i] -= 32; cout << char((mp_ch[a[i]] + 32)); }
	else if (a[i] < 65 || a[i]>90) { cout << a[i]; }
	else { cout << mp_ch[a[i]]; }
}
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
map<string, string>mp_str;
map<char, char>mp_ch;
string str1 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
string str2;
string key1 = "";
cout << "输入密钥：\t";
getline(cin, str2);
getline(cin, str2);
map<char, int>mp_is;
for (int i = 0; i < 26; i++) {
	mp_is[str1[i]] = 0;
}
for (int i = 0; i < str2.length(); i++) {
	if (str2[i] >= 97 && str2[i] <= 122) { str2[i] -= 32; }
	else if (str2[i] < 65 || str2[i]>90) { continue; }
	if (mp_is[str2[i]] == 0) { key1 += str2[i]; }
	mp_is[str2[i]] = 1;

for (int i = 0; i < 26; i++) {
	if (mp_is[str1[i]] == 0) { key1 += str1[i]; }
}
cout << "密钥为：\t" << key1 << endl;
str2 = key
for (int i = 0; i < 26; i++) {
	mp_ch[str2[i]] = str1[i];
}
cout << "输入密文：\t";
string a;
getline(cin, a);
int len = a.length();
string b = "";
cout << "解密为：\t";
for (int i = 0; i < len; i++) {
	if (a[i] >= 97 && a[i] <= 122) { a[i] -= 32; cout << char((mp_ch[a[i]] + 32)); }
	else if (a[i] < 65 || a[i]>90) { cout << a[i]; }
	else { cout << mp_ch[a[i]]; }
}

在单表置换的加解密中，考虑了输入字符串的大小写、是否为字母问题，通过cout<< char((mp_ch[a[i]] +32));来实现小写字母的置换表替换，之后通过(a[i] < 65 || a[i]>90)cout << a[i]; 过滤非字母元素。

实验结果

加密：例如明文为Public keys!!，输入为"HK 1234 WT"，得到密钥为："HKWTABCDEFGIJLMNOPQRSUVXYZ"，那么密文应为Nskiew gayq!!；

加密实验结果

解密：同理，密文为Nskiew gayq !!时，输入为"HK 1234 WT"，得到密钥为："HKWTABCDEFGIJLMNOPQRSUVXYZ"，解密得到明文Public keys !!

解密实验结果

对单表置换密码的攻击

实验原理

在单表置换密码中，由于置换表字母组合方式有26！种，约为4.03×1026。 所以采用穷举密钥的方法不是一种最有效的方法。对单表置换密码最有效的攻击方法是利用自然语言的使用频率：单字母、双字母组/三字母组、短语、词头/词尾等，这里仅考虑英文的情况。 英文的一些显著特征如下[1]:

短单词(small words)：在英文中只有很少几个非常短的单词。因此，如果在一个加密的文本中可以确定单词的范围，那么就能得出明显的结果。一个字母的单词只有a和I。如果不计单词的缩写，在从电子邮件中选取500k字节的样本中，只有两个字母的单词仅出现35次，而两个字母的所有组合为26×26＝676种。而且，还是在那个样本中，只有三个字母的单词出现196次，而三个字母的所有组合为26×26×26＝17576种。

常用单词(common words):再次分析500k字节的样本，总共有5000多个不同的单词出现。在这里，9个最常用的单词出现的总次数占总单词数的21％，20个最常用的单词出现的总次数占总单词数的30％，104个最常用的单词占50％，247个最常用的单词占60％。样本中最常用的9个单词占总词数的百分比为： the 4.65 to 3.02 of 2.61 I 2.2 a 1.95 and 1.82 is 1.68 that 1.62 in 1.57

字母频率(character frequency):在1M字节旧的电子文本中，对字母"A"到"Z"（忽略大小写）分别进行统计。发现近似频率（以百分比表示）：

e 11.67 t 9.53 o 8.22 i 7.81 a 7.73 n 6.71 s 6.55
r 5.97 h 4.52 l 4.3 d 3.24 u 3.21 c 3.06 m 2.8
p 2.34 y 2.22 f 2.14 g 2.00 w 1.69 b 1.58 v 1.03
k 0.79 x 0.30 j 0.23 q 0.12 z 0.09

从该表中可以看出，最常用的单字母英文是e和t，其他字母使用频率相对来说就小得多。这样，攻击一个单表置换密码，首先统计密文中最常出现的字母，并据此猜出两个最常用的字母，并根据英文统计的其他特征（如字母组合等）进行试译。

算法流程图

对置换密码攻击的流程图

实验代码

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
cout << "输入明文：";
string a;
getline(cin, a);
getline(cin, a);
string a_copy = a;
int len = a.length();
int sum = len;
map<char, float>mp_cf;
string str = "abcdefghijklmnopqrstuvwxyz";
string str_c = str;
//初始化
for (int i = 0; i < 26; i++) {
	mp_cf[str[i]] = 0;
}
for (int i = 0; i < len; i++) {
	//cout << "a[i]" << a[i] << endl;
	if (a[i] == 32) { cout << " "; sum--; continue; }
	if (a[i] >= 65 && a[i] <= 90) { a[i] += 32; }
	mp_cf[a[i]] += 1;
}
cout << endl;
//统计出现频率
for (char i = 0; i < 26; i++) {
	mp_cf[str[i]] /= sum;
	cout << str[i] << ":" << mp_cf[str[i]] << endl;
}
//排序
for (int i = 0; i < 26 - 1; i++) {
	for (int j = 0; j < 26 - i -1; j++) {
		if (mp_cf[str[j]] < mp_cf[str[j + 1]]) {
			float temp_f= mp_cf[str[j]];
			char temp_c=str[j];
			str[j] = str[j + 1];
			mp_cf[str[j]] = mp_cf[str[j + 1]];
			
			str[j + 1] = temp_c;
			mp_cf[str[j + 1]] = temp_f;
		}
	}
}
cout << "----------------------------------"<<endl;
for (char i = 0; i < 26; i++) {
	cout << str[i] << ":" << mp_cf[str[i]] << endl;
}
//电子文本字母频率映射
map<char, char> map_stos;
string net_str = "etoiansrhlducmpyfgwbvkxjqz";
for (char i = 0; i < 26; i++) {
	map_stos[str[i]] = net_str[i];
}
cout << "置换表为：" << endl;
for (char i = 0; i < 26; i++) {
	cout << str_c[i] << " ";
}
cout << endl;
for (char i = 0; i < 26; i++) {
	cout << map_stos[str_c[i]] << " ";
}
cout << endl << "解密结果：" << endl;
//首次破译
a = a_copy;
for (int i = 0; i < len; i++) {
	if (a[i] == 32) { cout << " "; sum--; continue; }
	if (a[i] >= 65 && a[i] <= 90) { a[i] += 32; }
	cout << map_stos[a[i]];
}
//根据英文特征继续破译
while (1) {
	char old1;
	char new1;
	cout <<endl<<"---------------------------------------------------" << endl;
	cout << "the first letter:";
	cin >> old1;
	cout << "the second letter:";
	cin >> new1;
	cout << "--------------" << endl;
	for (int i = 0; i < 26; i++) {
		if (map_stos[str[i]] == old1) { map_stos[str[i]] = new1; continue; }
		if (map_stos[str[i]] == new1) { map_stos[str[i]] = old1; continue; }
	}
	cout << "置换表为：" << endl;
	for (char i = 0; i < 26; i++) {
		cout << str_c[i] << " ";
	}
	cout << endl;
	for (char i = 0; i < 26; i++) {
		cout << map_stos[str_c[i]] << " ";
	}
	cout << endl << "解密结果：" << endl;
	for (int i = 0; i < len; i++) {
		//cout << "a[i]" << a[i] << endl;
		if (a[i] == 32) { cout << " "; sum--; continue; }
		if (a[i] >= 65 && a[i] <= 90) { a[i] += 32; }
		cout << map_stos[a[i]];
	}
}

实验步骤与结果

1.输入明文，统计输入明文字母出现频率

明文字母出现频率

2.将字母出现频率排序，然后根据电子文本中的字母频率进行简单置换表构建，执行第一次解密：

明文字母出现频率

3.观察解密后的文本，根据英文特征修改置换表：

（1）在第一次解密后，发现文本中单个字母"o"的出现频率非常高，由此可以推测"o"实际应该为"a"：

o<->a

（2）"nr"跟在"that"前，推测"nr"实际为"is"：

n<->i,r<->s

（3）新解密出的明文中有"a doint a tn a doint m"，推测"tn"应该为"to"

n<->o

（4）存在"is that oy"推测"oy"应该为"of"：

y<->f

（5）继续分析在（3）中出现的语句"frop a doint a tn a doint m"，很明显这里是"from..to.."，所以将p与m对换：

p<->m

（6）文本结尾处有一个单词"messace"，推测应该为"message"，将c与g互换：

c<->g

（7）存在短语" py means of"，并且文本中也出现了"py"，推测应该是"by means of"和"by"，所以将p与b对换：

b<->p

（8）文本中第三个单词为"drobuem"，推测是problem，所以将p和d对换、u和l对换：

d<->p,u<->l

（9）文本中第二个单词为"uentral"，后面还出现了"uan"，推测是"central"和"can"，所以将u和c对换:

u<->c

（10）文本中出现了"recoverew"和"anw"，推测应该为"recovered"和"and"，所以将w与d对换:

w<->d

（11）在最后出现了单词"unauthoriked"，推测应该为"unauthorized"，所以将k和z对换：

k<->z

经过上述步骤之后，已经得到了通顺的语句，解密得到的明文为： the central problem in cryptography is that of transmitting information from a point a to a point b by means of a possibly insecure channel in such a way that the original message can only be recovered by the rightful recipients the participants in the transaction are alice the originator of the message bob the receiver and oscar a possible opponent who wishes to gain unauthorized control of the message