Crypto—之古典密码学入门

Crypto之古典密码学

什么是密码学

密码学是一个多面的世界，对一些人来说，它是一个侦探与保密的世界，对另一些人来说，它是数学与计算机的世界。无论你如何看待它，密码学都是神秘而富有冒险色彩的。它还超越了传统的学术学科。它不只是计算机科学的内容，密码学的研究包括历史、政治学、工程、语言军事学、伦理、数学和工业技术学等。
——《经典密码学与现代密码学》

古典密码学主要关注信息的保密书写和传递，以及与其相对应的破译方法。
现代密码学不只关注信息保密问题，还同时涉及信息完整性验证、信息发布的不可抵赖性、以及在分布式计算中产生的来源于内部和外部的攻击的所有信息安全问题。

CTF 中的古典密码学题目有时也会出现在杂项里面，古典加密常常不给出加密算法，需要判断或者尝试一下。
而 CTF 中的现代加密常常会给出加密算法，或者以一些形式提示某种常用的加密算法。即通过公开的加密算法和题目给的条件来思考解密的算法并加以实现。

在有关密码学的一些描述中，常使用Alice和Bob作为两个想要传递消息的两个人，Eve是想要从传递的密文中窃取明文信息的人。

凯撒加密

凯撒加密（Caesar cipher）是一种最简单且最广为人知的加密技术，它属于替代加密，明文中的所有字母都在字母表上向后（或向前）按照一个固定数目进行偏移后被替换成密文。

凯撒加密会生成一个一一对应的密码表，加密和解密过程都是通过查表完成的。
和很多其他的单表替换加密一样，凯撒加密是十分不安全的。可以把移位值看作密钥key，不难想到，在明文空间为26个英文字母时，有效的密钥只有25个。所以很容易枚举出来。

关键词加密

关键词加密（keyword cipher）也是一种单表替代加密，与凯撒加密不同之处在于密钥可以更为复杂，加密时需要选择一个关键词，如果这个关键词有重复的字母，去除第一次出现之外的所有的相同的字母。例如，如果选定的关键词为“success”，则使用“suce”。
将该关键词写在字母表的下方，并用字母表的其他字母按标准的顺序填写余下的空间。这样就构建了字母一一对应的关系，加密时用下面一行中的字母对应替换上面一行的字母；解密时用上面一行中的字母对应替换下面一行的字母。

ACTF2020 Crypto Keysar

Cipher : agqr{yue_stdcgciup_padas}
Key : angstromcf

前10个字母先用key填充，后面的按字母表顺序展开。

a	g	q	r	{	y	u	e	_	s	t	d	c	g	c	i	u	p	_	p	a	d	a	s	}
a	c	t	f	{	y	u	m	_	d	e	l	i	c	i	o	u	s	_	s	a	l	a	d	}

按照上面的表格，对应解密得到flag：actf{yum_delicious_salad}

仿射加密

解密时需要计算（或枚举）密钥数字对中 a 的逆元，也就是 a 对 26 的模反数。
模反数可以简单理解为整数环中的倒数，a 乘以 a 的模反数对 26 取模等于 1。例如 5 对 26 的逆元就是 21。
所以一个数乘以 a，再乘以 a 的逆元，就能算回原来的数。

求逆元可以用 Python 的第三方包 gmpy2 的 invert 函数：

这里a的-1指的是a的逆元

举个例子：

其中

所以尽管套了三层，还是可以当作普通的仿射加密进行破解。

单表替代密码分析

所以枚举的方式获取字母间的对应关系显然是难以承受的。

可以利用不同的英文字母在文段中的出现频率特征，来帮助我们判断某个字母被替换成了某个字母的可能性。

词频分析不仅针对单个字母的出现频率，同时有很多连续的两个字母出现频率较高（双联字母 bigrams），也可以辅助我们进行分析。
以下是平均在1000个单词中，各双联字母出现的次数：

另外，如果有一个较大的单词库，还可以通过单词的格式，进一步帮助我们缩小可能的范围，例如单词happy，为12334格式，success为1233411格式，那么被进行单表替换后，它的格式并不会发生改变。
这种模式匹配的优点在于即使密文长度较短，也能尽可能找到接近真相的结果。
https://quipqiup.com/

维吉尼亚加密

维吉尼亚密码是使用一系列凯撒密码组成密码字母表的加密算法，属于多表密码。为了生成密码，需要使用表格法。这一表格包括了26行字母表，每一行都由前一行向左偏移一位得到。具体使用哪一行字母表进行加密是基于密钥进行的，在过程中会不断地变换。

加密
明文：ATTACKATDAWN
选择关键词：LEMON，重复关键词，直到长度和明文相同，作为密钥：LEMONLEMONLE
通过等长的明文和密钥，依次查表得到密文：LXFOPVEFRNHR

解密
解密的过程则与加密相反。例如：根据密钥第一个字母 L 所对应的 L 行字母表，发现密文第一个字母 L 位于 A 列，因而明文第一个字母为 A 。密钥第二个字母 E 对应 E 行字母表，而密文第二个字母 X 位于此行 T 列，因而明文第二个字母为 T。以此类推便可得到明文。

维吉尼亚加密可以避免直接的词频分析攻击，密文在统计上没有明显的规律，但是仍然有方法可以对其进行破解。
首先提出破解方法的 Frederick Kasiski 是基于这样一个简单的观察“密钥的重复部分与明文中的重复部分的连接，在密文中也产生一个重复部分”。
如果一个字符串在明文中重复，并且被密钥相同的部分加密，那么在密文中也会出现重复的字符串。

举个例子：

关键词 “RUN” 的长度为 3，密文串“KIOV”的间距是 9，密文串 “NU”的间距是 6，这些间距都是关键词长度的倍数，这样重复足够多次，可以帮助我们判断关键词的长度。

一旦确定了关键词的长度，余下的问题就只是如何使用该信息去找到真正的关键词了。关键词的长度揭示了密文可以被如何破解成单码加密的一个集合。
关键词的长度为n，那么破解维吉尼亚加密的问题就变成了解决n个单表加密的问题，需要有足够长的密文，然后通过词频分析逐个解决问题。

替换和编码

古典加密还包括很多种形式的简单替换或编码，这些替换也常常出现杂项中，如摩尔斯电码、福尔摩斯跳舞的小人、敲击码、培根密码……

摩尔斯电码：用一个电键可以敲击出点、划以及中间的停顿。

福尔摩斯跳舞的小人：

敲击码：

培根密码：

使用 Python 脚本进制转换

字符串(str)类型和字节(bytes)类型相互转换

Base64编码解码

整数和字节类型的转换

这种类型转换在密码方向题目中很常见，整数类型可以直接参与数学计算，字节类型会展示可读的字符

参考资料

https://www.bilibili.com/video/BV1VA411u7Tg?p=5