何谓密码学

虽然密码学中充满了如RSA、AES、PKA等高端现代缩写，但事实上，这已经是门有千年之久历史的古老学科了。自文字出现以来，密码一般也会同步地出现在了人们的生活中。这些是古典密码学，形式古雅而简单，富于趣味性。与之对应的是现代密码学，更“科学”（因为它和数学间的联系较古典密码学更紧密些），更安全，更符合现代文明的需求，但入门难度也更高一些。

密码学相关的模型有enigma加密机，它背后有一段惊险刺激的故事。还有斯巴达密码棒，虽然常会被作为高中大学的编程水题，但不要因为题目水就瞧不起古人的创意，没准告白的时候就能用上呢（然而这与我有什么关系呢）。

密码学，cryptology，是个涵盖较广的词，包括cryptography和所谓cryptanalysis。前者包括加密解密的艺术还有一些协议，而后者则强调对密码的安全性进行理论化的分析。而这本书名为Understanding Cryptography，主要是在讲述前者。

Cryptography主要能分成以下三块内容：对称算法，非对称算法（或公钥算法），密码协议。其实这三者并不并列，只是这三个词出现的频率比较高而已。真要说起来，前两者都是加密的大类，而后者是对加密算法在实际场景下的应用。

对称算法与非对称算法分别有何优点有何缺陷呢？这是后文所将详述的。在此，我们只需知道前者是双方共享一个密钥，而后者是用户有一个公钥也有一个私钥。看上去后者不太好理解？没事，搜一搜“数字签名”就知道为什么要这样设钥了，而且它的用处远不止用作签名。

一般来说，对称算法更容易入门些，那我们就来学学吧。

对称密码学

首先是概念，先举个例子吧。

Alice和Bob在通过QQ交流他们对某个题目的想法，然后Bob的手机很容易被黑所以他们的聊天记录可能会被监听。为了让交流的内容不被外人所知，Alice和Bob决定加密他们对话的内容。他们很有古典情怀，所以选择了凯撒加密，双方约定一个密钥，一方在发送时将原文通过密钥加密，另一方也通过这个密钥解密即可。

上面的例子模拟了一个典型的通信场景，信息源分别为Alice和Bob，他们使用的信道有两个：一个是不安全的QQ，还有一个是相对安全的用于约定密钥的食堂餐桌。然后在前一个信道上可能有非法用户监听。为了在不安全的信道上使通信相对安全，内容不外泄，他们用到了cryptography中的对称密码，其特点是双方共用一个密钥。

然后他们所用的凯撒加密是一种非常经典（也非常vulnerable）的替换密码。所谓替换密码，顾名思义，就是把一个字母替换为另一个字母。考虑英文字母表中的小写字母，一个字母可能被替换为二十六个字母中的任意一个，而为消歧义性，一个字母的原像应只有一个。（当然，你也可以搞个非单射，一个字母的原像有贼多可能，然后出个题，交代一下原文的hash值，来恶心人）这样的替换有多少类，也就是密钥空间有多大呢？$26! \approx 2^{88}$，很大了。看上去这种加密方式非常不错。

真的不错么？可以看得出来，bruteforce对于这样的加密一般是相当无力的。假设一台2019年的标准个人计算机每秒能够检查1e8个密钥，那么要遍历完大至1e26的密钥空间要多久呢？1e18秒，1e13年。就算搬来一千台计算机分工也得算到宇宙的寿命翻一倍，很安全。然而，这样的替换没有把原文的统计属性予以一丝一毫的改变。当样本足够大时，英语中各个字母的出现频率会有显著的改变，词频也会趋于稳定。于是，我们便可通过分析统计数据进行解密了。除字母和单词外，还可以通过字母元组的统计规律（如，q后面一般总是跟着u）来进行分析。当然，还需要一些语感和灵感……这是解密的有趣所在。随着所谓人工智能的发展，我们也可通过计算机对此进行分析。

密码的安全性

为了知晓密码是否足够安全，我们需要对密码进行攻击尝试。攻击的方式有哪些呢？首先是经典的密码分析，比较登大雅之堂，可以暴力枚举密钥，也可在获悉加密方法的内部结构后进行分析攻击。然后就是比较离谱的攻击方式了：implementation attack，物理玩法，比如测量处理私钥的处理器的功耗搞到密钥；社工，利用人性的弱点，比如冒充公安局说对方涉嫌违法犯罪需要提供密码。

后两个方法比较玄，不是很数学，所以书后面就不怎么讲了，不过这两个方法还是非常好用的，虽然随着时代的进步人们的防范还有设备的防范都加深了。

可靠的密码体制需要遵守Kerckhoffs原理，即即便公开密钥以外系统的一切，包括加密解密算法，系统也应足够安全。

这个原理看上去不太符合常理，因为隐藏细节不是也扩大了“加密/解密算法空间”吗？这样的方案被称为隐蔽式安全性，security by obscurity。但历史经验（书上的例子似乎不够多）告诉我们这样是有风险的。

遵守Kerckhoffs原理的话，安全传输信息的问题便可以归结到安全地传输、存储密钥的问题上了。所以密钥是否足够robust呢？首先我们得让bruteforce无效化。即密钥空间开得多大能够使密钥保证计算安全？简单计算一下可知，64位虽然不能马上破解但是耗费数小时数天还是能够做到的。而128位要让电子计算机算个几十年。（以上为口胡）这些估算是把计算机性能的提升（摩尔定律）算在内了的。

两类替换密码

了解了一下密码分析相关知识，我们来拿简单可爱的古典密码开刀吧！首先是凯撒密码，接着是仿射密码。在分析之前，我们先得用现代化的语言表述这两种（其实是一种）加密算法的内容，而这，涉及到了编码和模运算。

模运算，相信学过一点初等数论或是基础的计算机课程就不会陌生，此处就略去不表了。书中也便是引入模运算的定义，同余的概念，同余等价类的概念，整数环的定义和若干性质（封闭、可结合、可交换、加法乘法存在不变元、加法存在逆元而乘法不一定存在逆元），如此而已。利用同余等价类可简化计算。对于乘法逆元的存在与否介绍了基于两数是否互素的判别方法。这是两个要点。

所谓凯撒密码，便是把字母（广义）编码到整数环上，再在环上进行加法运算，仅此而已。这种方式非常的vulnerable，因为它的密钥空间只有26，52，或是其他（总归不会大，即便是用字母表是所有汉字的集合……但这个样子也太为凯撒而凯撒了吧？），计算机秒秒钟就能算出来，甚至都不用进行频率分析。唯一的麻烦就是要判定可能的plaintext是不是readable的，不过浏览26个字符串对人类而言还是容易的，尤其很多扫一眼就能退出check了。（当然，也能用计算机分析readable指数，训练个模型什么的，可是咱也不会呀\cry）

然后是仿射加密，affine。凯撒的加密是$e_k (x) = y \equiv (x + k) mod 26$，则仿射加密便是$e_k (x) = y \equiv (ax + b) mod 26$。解密找反函数就好了。需要注意的是，此处密钥需满足$gcd(a, 26) = 1$，不然没有乘法逆元解密不总是能进行。仿射加密看上去比凯撒牛逼了很多，真的如此？并不是。由乘法原则，密钥空间=（a的可能取值数）×（b的可能取值数）=12×26=312，还是小的可怜呀，不过对入门级CTFer来说可能要难一丢丢（笑）。

要点回顾

1.不要乱开发自己的加密算法。（这主要是在实际应用中，瞎搞很容易出问题；不过在学习生活中瞎搞还是好玩的，比如把告白用的text加个自己瞎搞的密然后把代码给妹子让她分析得出原文，然而这与我有什么关系呢）

2.不要使用未经证明的加密算法或未经证明的协议，基本同上。这也是对Kerckhoffs原理的强调。

3.攻击者总是试图寻找密码体制的最薄弱之处，大的密钥空间并不保证密钥的安全性因为它不一定能抵抗分析攻击。

4.用于防御bruteforce的对称算法的密钥长度为128位或以上为宜，64位存在危险。

5.模运算是一种以严格数学方式表示古典密码方案的工具。

习题

替换密码解密题

以下密文是使用替换密码加密得到的，请在不知道密钥的情况下解出原文。

1
lrvmnir bpr sumvbwvr jx bpr lmiwv yjeryrkbi jx qmbm wibpr xjvni mkd ymibrutjx irhx wi bpr riirkvr jx ymbinlmtmipw utn qmumbr dj w ipmhh but bj rhnvwdmbr bpr yjeryrkbi jx bpr qmbm mvvjudwko bj yt wkbrusurbmbwjk lmird jk xjubt trmui jx ibndt
1
wb wi kjb mk rmit bmiq bj rashmwk rmvp yjeryrkb mkd wbi iwokwxwvmkvr mkd ijyr ynib urymwk nkrashmwkrd bj ower m vjyshrbr rashmkmbwjk jkr cjnhd pmer bjlr fnmhwxwrd mkd wkiswurd bj invp mk rabrkb bpmb pr vjnhd urmvp bpr ibmbr jxrkhwopbrkrd ywkd vmsmlhr jx urvjokwgwko ijnkdhrii ijnkd mkd ipmsrhrii ipmsr wdj kjb drry ytirhx bpr xwkmh mnbpjuwbt lnb yt rasruwrkvr cwbp qmbm pmi hrxb kjdjnlb bpmb bpr xjhhjcwko wi bpr sujsru msshwvmvwjk mkd wkbrusurbmbwjk w jxxruyt bprjuwri wk bpr pjsr bpmb bpr riirkvr jx jqwkmcmk qmumbr cwhh urymwk wkbmvb

这很明显是频率分析。虽然已经有造好的轮子了（一开始不会做就直接丢进去了，也是一种选择啊），但还是想自己瞎搞搞搞看。写完了之后封装了一下，就是这样的：

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
const int LEN = 26;
struct Letter{char ch;int fre;}; // fre for frequency
bool cmp(const Letter& lhs, const Letter& rhs){return lhs.fre > rhs.fre;}
class FREQUENCY_ATTACK
{
public:
	Letter letters[LEN];
	char cipher_text[1000];
	char in_table[LEN];
	char out_table[LEN];
	map<char, char> dict;
	
	void load_cipher_text(const char* str){strcpy(cipher_text, str);}
	
	void init_letters()
	{
		for(int i = 0;i < LEN;i++)
		{
			letters[i].fre = 0;
			letters[i].ch = i + 'a';
		}
	}
	
	void get_frequency()
	{
		for(int i = 0;i < strlen(cipher_text);i++)
			letters[cipher_text[i]-'a'].fre++;
		sort(letters, letters + LEN, cmp);
	}
	
	void print_frequency()
	{
		for(int ch = 0;ch < LEN;ch++)
			printf("%c: %d\n", letters[ch].ch, letters[ch].fre);
		putchar('\n');
		printf("order by frequency: ");
		for(int i = 0;i < LEN;i++)
			putchar(letters[i].ch);
		putchar('\n');
		putchar('\n');
	}
	
	void analysis(bool do_print)
	{
		init_letters();
		get_frequency();
		if(do_print) print_frequency();
	}
	
	void dict_generate(const char* str1, const char* str2)
	{
		strcpy(in_table, str1);
		strcpy(out_table, str2);
		for(int i = 0;i < LEN;i++)
			dict[in_table[i]] = out_table[i];
	}
	
	void translate(const char* str)
	{
		for(int i = 0;i < strlen(str);i++)
			putchar(dict[str[i]]);
		putchar('\n');
		putchar('\n');
	}
	
	void print_letters_not_in_out_table(const char* str)
	{
		map<char, int> table;
		for(int i = 0;i < strlen(str);i++)
			table[str[i]] = 1;
		printf("letters that aren't in the out_table: ");
		for(int i = 0;i < LEN;i++)
			if(!table.count(i + 'a'))
				putchar(i + 'a');
		putchar('\n');
		putchar('\n');
	}
};

思路就是先求出频率，再排序，再把这段文本中按频率降序的字母表和大量文本中按频率降序的字母表建立一个映射，思路是这样的，然后main函数里面是这样的，以第二段文本为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main()
{
	// exercise 1.1.2
	FREQUENCY_ATTACK target;
	target.load_cipher_text("wb wi kjb mk rmit bmiq bj rashmwk rmvp yjeryrkb mkd wbi iwokwxwvmkvr mkd ijyr ynib urymwk nkrashmwkrd bj ower m vjyshrbr rashmkmbwjk jkr cjnhd pmer bjlr fnmhwxwrd mkd wkiswurd bj invp mk rabrkb bpmb pr vjnhd urmvp bpr ibmbr jxrkhwopbrkrd ywkd vmsmlhr jx urvjokwgwko ijnkdhrii ijnkd mkd ipmsrhrii ipmsr wdj kjb drry ytirhx bpr xwkmh mnbpjuwbt lnb yt rasruwrkvr cwbp qmbm pmi hrxb kjdjnlb bpmb bpr xjhhjcwko wi bpr sujsru msshwvmvwjk mkd wkbrusurbmbwjk w jxxruyt bprjuwri wk bpr pjsr bpmb bpr riirkvr jx jqwkmcmk qmumbr cwhh urymwk wkbmvb");
	target.analysis(true); // print the frequency
	target.dict_generate("rbmkwjiphdvsunxyoatcqlegfz",
	                     "etanioshldcprufmgxywkbvzq_");
//	                      etaoinrshdclmpufgwybkjvxqz
// the row above shows the frequency of letters in English
	target.translate(target.cipher_text);
	target.translate("bjlr");
	target.print_letters_not_in_out_table("etanioshldcprufmgxywk vzq ");
	return 0;
}

代码应该比较容易看懂，但问题在于dict_generate对应的表是如何生成的呢？因为样本的问题，此表和普遍接受的英语字母频率表并不是完全一致的，所以需要微调，不然直接放进去搞出来的原文并不是readable的。那么怎么调呢？本人的做法是先把这个out_table全填上.（LaTeX不方便输入下划线，就用.替换了），方便确认各个单词的完整度和字母数。然后把et两个字母填进去，因为大数定律，它们更有可能占在原来的位置上。然后知道了et就能找the了。我们注意到，bpr在原文中出现了很多次，有理由相信它对应于the。这样之后发现了形如th.t的单词，就可以填a了。然后还有形如eas.，形如tas.的单词，都能填了。这样之后好像陷入瓶颈了？让我们来找一些特别短的差不多能够猜出来的词吧。已经知道了b对应t，那么bj能对应什么单词呢？也只有to了吧。确定了j对应于o，然后密文中又有很多的jx，又能确定x对应于f了。密文中有个单词w，而单个字母组成的单词似乎只有a和I，a又用掉了，这样就能确定w就是i了……如此。到后面几乎一下就能确定一个单词了，做得很快。print.letters.not.in.out.table是在大后期确定哪个单词还没有使用的。然后找到了一个差不多可以填的单词可以手工模拟一下（懒得写anti.translate这个函数了）其密文再搜索一下找到它。如此这般如此这般，就能做出来啦！（一开始对着书抄密文把y抄成v了，结果搞出来covement，soce这种单词……然后开始我不是用下划线占位而是用空格占位的，后面的单词看着特奇怪，很怀疑自己是不是有映射弄错了……）

其他题目

感觉只有第一个题目比较有意思（因为是手动造轮子吧，虽然扔到quipquip里面也是秒做的），其他题目都太简单了？不是很有挑战，但还可以。

第二题的话直接暴枚二十六个密钥然后找readable的原文，以前遇到凯撒我都是这么做的。今天它要我基于字母频率来攻击……其实也好办，跑一下频率，然后令k = ‘e’ + 26 - ‘t’就好了，大数定律（虽然一点也不大）。第十一题直接模拟，不过这行话是Dodgeson写的吗我居然毫无印象……

第三题这种费米问题，条件给得多了呀……不过我们现在也是在科学地分析嘛，精确点也好。注意对数的妙用，就差不多了。

第四题也足够让我们感受平时的8位密码有多么robust了，从而能够理解为什么各网站在检测密码强度时检测到只有小写字母是“弱”而有小写有大写有数字就是“强”，只要有一个位置的可能，密钥空间就能增加这么这么多。

第五六七八九十题，都是数论相关，包括等价类的应用，求逆元等，基础。其中1.9提到了“离散对数”的概念，这个东西后面还会讲的，在椭圆曲线加密那块。十是欧拉函数，看到它我想到了最近看到的欧拉乘积公式……

第十三题提到了选择明文攻击。这是个有趣的概念，想象两国交战中你作为间谍无法获取密钥的情报但能够发送加密的信息，也就是你能够选择一些原文，知道这段原文的密文。如果是这样，你如何攻击密码呢？仿射自然是很好破译的，但其他呢？

第十四题提到了多次加密。显然，对于仿射加密而言多次加密完全没有扩大密钥空间的作用，没有实质性的效果（除了唬人）。但是对于DES，多次加密就有意义了……

初稿写于2019.07.23

完稿写于2019.07.28