总览。

CTF 中的密码学可以按照时间分为 古典密码学 和 现代密码学 。

我个人也愿意将其按照是否需要介入大量数学思考来分成简单密码学题目或者需要思考的密码学题目。

同时，我们应该认识到，古典密码所用的方法即是 置换加密 和 替代加密。而现代密码学虽然也离不开这两种基本操作，但是其中还添加了大量的数学原理与抗密码分析技术。

下面将从 CTF 比赛中常见的题目类型、解题思路方法等进行一个讨论。

暂时没想到怎么展示思维导图，点击下载 思维导图

古典密码

一般而言，古典密码的题我们又可以分为 有密钥的 和 无密钥的 。

编码

事实上，从这个角度而言，没有密钥的我们也可以称其为一种编码。故也可以将 base64 等这种也囊括进来了。为了便于区分，我个人统一将这类称为编码。

像这种就主要考察选手是否知道这种密码/编码或者能否从密文和已知信息中推断出加密/编码的方式。

ASCII 编码

即将 flag 中的字符全部转化为其对应的 ASCII 码，再将编码后的数字还可以进行进制转化。

base 家族编码

base 家族编码主要常用的是 base64 编码，也有相应的其他类似的 base32 ， base16 等，但基本原理差不多。base64 、 base32 、 base16 可以分别编码转化 8 位字节为 6 位、 5 位、 4 位，用16, 32, 64 个字符来编码。

base64 的编码原理为把 3 个 8 位字节共 24 位，分成 4 个部分再填入 4 个字节的低 6 位，每个字节中高 2 位用 0 进行填充。这样一共需要 $2^6 = 64$​ 个字符即可全部表示。标准的 base64 替换表为 ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/ ，这种直接就可以用 Python 解码也可以通过在线的网站。

若遇到修改了替换表的，则需要手动修改一下替换表，写个小脚本，如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from base64 import b64encode, b64decode

stand_table = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
custom_table = "abcdefghijklmnopqrstuvwxyz+/ABCDEFGHIJKLMNOPQRSTUVWXYZ9876543210"

flag = b"flag{th1s_1s_cust0m_base64}"

# encode
encode_flag = b64encode(flag).decode().translate(str.maketrans(stand_table, custom_table))
# encode_flag = 'zKVFz8RY+dfXxXfXx9nZA8qU/v2GyxnJnHr2'

# decode
new_flag = b64decode(encode_flag.translate(str.maketrans(custom_table, stand_table))).decode()
# new_flag = "flag{th1s_1s_cust0m_base64}"

shellcode 编码

在进行 PWN 的时候，经常会将代码（shellcode）转化为16进制再进行执行。这个本质和 ASCII 差不多。

以至于，可以直接用 Python print 搞定。

1
2
3
4
5
6
# flag = "flag{this_1s_shellc0de_encode}"
# encode_flag = "".join(list(map(lambda x:"\\x%2x" % ord(x), flag)))

encode_flag = "\x66\x6c\x61\x67\x7b\x74\x68\x69\x73\x5f\x31\x73\x5f\x73\x68\x65\x6c\x6c\x63\x30\x64\x65\x5f\x65\x6e\x63\x6f\x64\x65\x7d"
print(encode_flag)
# flag{this_1s_shellc0de_encode}

Quoted-printable 编码

Quoted-printable是使用可打印的ASCII字符（如字母、数字与「=」）表示各种编码格式下的字符，以便能在 7-bit 数据通路上传输 8-bit 数据, 或者更一般地说在非8-bit clean媒体上正确处理数据。 这被定义为MIME content transfer encoding，用于e-mail。

编码解码可以通过在线网站进行。Quoted-printable1。Quoted-printable2。

flag = “蒲就是flag”
encode = “=E8=92=B2=E5=B0=B1=E6=98=AFflag”

XXencode 编码

XXencode编码，也是一个二进制字符转换为普通打印字符方法。 跟UUencode编码原理方法很相似，唯独不同的是可打印字符不同。

将输入文本以每三个字节为单位进行编码。如果最后剩下的数据少于三个字节，则用 0 补齐。这三个字节共有 24 个 bit，以 6 bit 为单位分为 4 个组，每个组以十进制来表示所出现的数值只会落在 0 ~63 。以所对应值的位置字符代替。它所选择的可打印字符是：+-0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz ，一共 64 个字符。

与 base64 打印字符相比，就是 UUencode 多一个 - 字符，少一个 / 字符。

编码解码还是用在线网站。XXencode 。

心情好也可以用 Python 来实现一个。

1
2
flag = "flag{this_1s_XXenc0de}"
encode_flag = "KNalVNrhoO4ZnLn3nLpVMNKtXA4FZTE++"

UUencode 编码

UUencode是一种二进制到文字的编码。最早在unix 邮件系统中使用，全称：Unix-to-Unix encoding。

UUencode 将输入文本以每三个字节为单位进行编码，如果最后剩下的资料少于三个字节，不够的部份用零补齐。三个字节共有 24 个 bit，以 6-bit 为单位分为 4 个组，每个组以十进制来表示所出现的字节的数值。这个数值只会落在 0 ~ 63 之间。然后将每个数加上 32，所产生的结果刚好落在 ASCII 字符集中可打印字符中。

说白了，和前面的 XXencode 如出一辙，只是加了一个偏移而映射为 ASCII 的可打印字符集中，也就是映射表不同而已。

编码解码还是用在线网站。UUencode。

1
2
flag = "flag{this_1s_UUenc0de}"
encode_flag = "?9FQA9R ](")F;&%G>W1H:7-?,7-?555E;F,P9&5](@  "

URL 编码

URL 编码也称为 百分号编码，广泛用于 web 应用中，是特定上下文的统一资源定位符 （URL）的编码机制，实际上也适用于统一资源标志符（URI）的编码。也用于为 application/x-www-form-urlencoded MIME 准备数据，因为它用于通过 HTTP 的请求操作（request）提交 HTML 表单数据。

编码解码还是用在线网站。 URL1。URL2。

最明显的特征莫过于这些百分号了。

当然也可以用 Python 写一个。

1
2
3
4
5
6
7
8
9
import urllib.parse

flag = "flag{Th1s_1s_url_enc0de}"

encode_flag = urllib.parse.quote(flag)
# 'flag%7BTh1s_1s_url_enc0de%7D'

decode_flag = urllib.parse.unquote(encode_flag)
# "flag{Th1s_1s_url_enc0de}"

Unicode 编码

Unicode又称为统一码、万国码、单一码，是国际组织制定的旨在容纳全球所有字符的编码方案，包括字符集、编码方案等，它为每种语言中的每个字符设定了统一且唯一的二进制编码，以满足跨语言、跨平台的要求。

其拥有四种编码方式：&#x[Hex] ， &#[Decimal] ， \U[Hex] ， \U+[Hex] 。

编码解密可以使用在线网站： Unicode1。Unicode2。

Escape/Unescape 编码

Escape/Unescape 编码解码，又叫 %u 编码，采用 UTF-16BE 模式， Escape 编码就是字符对应 UTF-16 的 16 进制表示方式前面加 %u 。Unescape 解码，就是去掉 %u 后，将 16 进制字符还原后，由 UTF-16 转码到目标字符。如：字符 蒲，UTF-16BE 是： 84b2 ，因此 Escape 是 %u84b2 。

编码解码在线网站：escape/unescape。

也可以用 Python 自己写一个

1
2
3
4
5
6
7
8
9
import urllib

flag = 'flag{Th1s_!s_Une3c@pe}'

encode_flag = urllib.parse.quote(flag.encode('unicode-escape')).replace('%5Cu', '%u')
# flag%7BTh1s_%21s_Une3c%40pe%7D

decode_flag = urllib.parse.unquote(encode_flag.replace('%u', '\\u').encode().decode('unicode-escape')) 
# flag{Th1s_!s_Une3c@pe}

敲击码

敲击码(Tap code)是基于 5×5 方格来实现的。其中 K 和 C 位置重合。其映射表如下：

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

则相应的编码方式如下：

若需要编码的字符为 D 则其对应对应的坐标为(1, 4) 则编码后就是 . .... 很朴素的几个就是几个点点，用空格分隔。

也有直接转化为数字的：

编码前：flag = “thisistapcode”

编码后：encode = “44 23 24 43 24 43 44 11 35 13 34 14 15”

莫尔斯电码

这个太出名了，不过多解释了，就是有个对应表。

在线工具： Morse1。Morse2。

猪圈密码

猪圈密码也是一种比较出名的字符替换密码了，特征也是相当明显，就是将字母直接用对于的格子的长相来代替。如：E = 囗 , T = > ，U = < 。

网上关键词一搜就会看到替换表的长相，这里贴一个：

猪圈密码

社会主义核心价值观 编码

这个是新时代的编码方式。

编码解码在线网站：社会主义核心价值观。

编码前：flag = “flag{Th1s_1s_socialist_c0re_values_encode}”

编码后：flag = “公正公正公正友善公正公正民主公正法治法治友善平等平等自由公正爱国和谐民主法治和谐平等诚信平等和谐民主法治和谐平等友善敬业法治和谐公正诚信平等公正和谐公正敬业公正民主公正诚信文明公正敬业法治和谐法治自由平等友善敬业公正和谐和谐富强法治文明公正平等平等诚信平等法治公正公正民主公正友善公正法治平等公正平等法治和谐平等诚信平等公正平等公正诚信自由公正和谐公正友善敬业公正自由公正平等法治诚信和谐”

在线网站：网站1。网站2。

与佛论禅 编码

这个是佛说，与佛谈论宇宙的真谛。佛语道行高深，需要细细参悟。

编码前： flag{This_is_0n_Zen_with_Buddhism}

编码后：佛曰：冥孕怯伽奢不孕死諸摩倒室侄醯集想殿特摩俱羅侄咒等侄彌怛俱得以缽麼闍冥爍栗哆輸奢逝怯他呐集皤波呐能寫罰伽侄蒙滅怯尼特奢等皤若缽真俱至佛俱。侄真蘇吉怯得藐伽罰謹三冥呼怯寫他侄薩梵度曳至特數密怯瑟吉槃梵羅俱密哆呼涅南冥瑟隸哆至呐殿奢瑟者奢佛特怯他梵輸

编码解码网站：与佛论禅。

跳舞的小人

来自福尔摩斯的故事。特征很明显就是很多跳舞的小人，随便搜索一下就能找到替换表。

QWER 编码

这个就是纯属编的，即将电脑键盘的顺序用来编码： QWERT。。。

然后按照顺序进行替换， A=Q , B=W , C=E , D=R 。。。。。。

电脑键盘 编码

还有一种利用键盘的就是将字母围起来。

例如，要把字母 s 围起来，就是 AWEDXZ ，这样来进行编码。。。。

手机九键 编码

这个也是差不多，也就是考虑键盘顺序。

1 2 3
1 [1] ‘ [2] a,b,c [3] d,e,f
2 [4] g,h,i [5] j,k,l [6] m,n,o
3 [7] p,q,r,s [8] t,u,v [9] w,x,y,z

然后就是依次数，如：a = (2,1) , b = (2,2) , c = (2,3) , t = (8,1) , y = (9, 3) ……..

Brainfuck

Brainfuck，是一种极小化的程序语言，它是由 Urban Müller 在 1993 年创造的。由于 fuck 在英语中是脏话，这种语言有时被称为 Brainf*ck 或 Brainf*，或被简称为 BF。

各个指令的含义如下表所示：

字符 含义 C
> 指针加一 ++ptr;
< 指针减一 --ptr;
+ 指针指向的字节的值加一 ++*ptr;
- 指针指向的字节的值减一 --*ptr;
. 输出指针指向的单元内容（ASCII码） putchar(*ptr);
, 输入内容到指针指向的单元（ASCII码） *ptr = getchar();
[ 如果指针指向的单元值为零，向后跳转到对应的]指令的次一指令处 while (*ptr) {
] 如果指针指向的单元值不为零，向前跳转到对应的[指令的次一指令处 }>

编码前 flag = “flag{Th1s_1s_bra!n_f3ck}”

编码后 encode_flag = ++++++++[>>++>++++>++++++>++++++++>++++++++++>++++++++++++>++++++++++++++>++++++++++++++++>++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++++>++++++++++++++++++++++++>++++++++++++++++++++++++++>++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++<<<<<<<<<<<<<<<<-]>>>>>>>++++++.>——.<——-.>——-.>——-.<<<++++.>>+.<<<<+.>>>>>————.<<—.<<<.>>>>>.<<.+++.>>-.<<-.<<<<+.>>>>>>——.<<—.>—.<<<<++.>>>>—-.>—-.++++++++++++++++++.

编码解码在线网站：BrainFuck。

Ook 编码

这个和 brain fuck 是一样的。在线编码解码网站：Ook。

编码前 flag = “flag{Th1s_00K!}”

编码后 encode_flag = Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook! Ook? Ook! Ook! Ook. Ook? Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook? Ook. Ook? Ook! Ook. Ook? Ook. Ook. Ook. Ook. Ook! Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook! Ook. Ook? Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook! Ook? Ook! Ook! Ook. Ook? Ook! Ook! Ook! Ook!
Ook! Ook! Ook? Ook. Ook? Ook! Ook. Ook? Ook! Ook! Ook! Ook! Ook! Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook! Ook. Ook? Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook! Ook? Ook! Ook! Ook. Ook? Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook? Ook. Ook? Ook! Ook. Ook? Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook! Ook. Ook? Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook! Ook? Ook! Ook! Ook. Ook? Ook! Ook!
Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook? Ook. Ook? Ook! Ook.
Ook? Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook. Ook? Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook! Ook? Ook! Ook! Ook. Ook? Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook? Ook. Ook? Ook! Ook. Ook? Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook! Ook. Ook? Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook! Ook? Ook! Ook! Ook. Ook? Ook! Ook! Ook! Ook!
Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook? Ook. Ook? Ook! Ook.
Ook? Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook.
Ook? Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook! Ook? Ook! Ook! Ook. Ook? Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook? Ook. Ook? Ook! Ook.
Ook? Ook. Ook. Ook. Ook. Ook! Ook. Ook? Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook! Ook? Ook! Ook! Ook. Ook? Ook! Ook! Ook! Ook! Ook! Ook! Ook!
Ook! Ook? Ook. Ook? Ook! Ook. Ook? Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook!
Ook! Ook. Ook? Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook! Ook? Ook! Ook! Ook. Ook? Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook!
Ook! Ook! Ook! Ook! Ook? Ook. Ook? Ook! Ook. Ook? Ook! Ook! Ook! Ook! Ook!
Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook!
Ook! Ook! Ook! Ook. Ook! Ook. Ook? Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook! Ook? Ook! Ook! Ook. Ook? Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook? Ook. Ook? Ook! Ook. Ook? Ook. Ook. Ook. Ook. Ook!
Ook. Ook? Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook! Ook? Ook! Ook! Ook. Ook? Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook!
Ook! Ook! Ook! Ook? Ook. Ook? Ook! Ook. Ook? Ook! Ook! Ook! Ook! Ook! Ook!
Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook. Ook? Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook! Ook?
Ook! Ook! Ook. Ook? Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook? Ook. Ook? Ook! Ook. Ook? Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook! Ook. Ook? Ook.

jsfuck

一般用来加密 javascript 代码，密文只包含 ()[]{}!+ 等字符。在线编码解码网站：jsfuck。

编码前 flag = “flag{Th1s_is_JsF3ck}”

编码后 encode_flag = (![]+[])[+[]]+(![]+[])[!+[]+!+[]]+(![]+[])[+!+[]]+(![]+[+[]]+([]+[])[([][(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(![]+[])[!+[]+!+[]]]+[])[!+[]+!+[]+!+[]]+(!![]+[][(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(![]+[])[!+[]+!+[]]])[+!+[]+[+[]]]+([][[]]+[])[+!+[]]+(![]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[])[+!+[]]+([][[]]+[])[+[]]+([][(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(![]+[])[!+[]+!+[]]]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[][(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(![]+[])[!+[]+!+[]]])[+!+[]+[+[]]]+(!![]+[])[+!+[]]])[!+[]+!+[]+[+[]]]+(!![]+[][(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(![]+[])[!+[]+!+[]]])[!+[]+!+[]+[+[]]]+(+[![]]+[][(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(![]+[])[!+[]+!+[]]][([][(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(![]+[])[!+[]+!+[]]]+[])[!+[]+!+[]+!+[]]+(!![]+[][(![]+[])[+[]]+([![]]+[][[]])[+……. (PS: 太长了，这里就不贴了)

密码

而有密钥的，对于古典密码而言，一般可以通过词频分析的方式破解。

但仍然有部分恶心人的出题人，非要脑洞补齐这个密钥才能得到。

当然，如果密钥密钥空间足够小，同时明文又具有明显的标志的（如 flag 字样）也不是不能通过暴力美学的方式来解决的。

栅栏密码

所谓栅栏密码，就是把要加密的明文分成N个一组，然后把每组的第1个字连起来，形成一段无规律的话。

不过栅栏密码本身有一个潜规则，就是组成栅栏的字母一般不会太多。

使用时，先选择一个数作为 key ，该数的作用是将原来的明文进行分组，作为组的数量。（故不可能太大，总不会比明文的长度还大吧。

例子如下（下面是分成两组， key = 2）：

明文：This is an example of the Rail Fence Cipher 。

去除空格： ThisisanexampleoftheRailFenceCipher 。

分组： Th is is an ex am pl eo ft he Ra il Fe nc eC ip he r 。

重组：TiiaeapefhRiFneihr 和 hssnxmlotealecCpe 。

再拼接为密文 TiiaeapefhRiFneihrhssnxmlotealecCpe 。

加解密可以使用在线网站：网站一。网站二。

曲路密码

曲路密码(Curve Cipher)是一种换位密码，需要事先双方约定曲路路径作为密钥。

加解密使用例子如下：

明文：This is an example of the Curve Cipher 。

填入事先约定的好行列的矩阵中，如这里是 $5 \times 7$​ 的矩阵，填不满就算了，但不能不够啊。

1 2 3 4 5 6 7
T h i s i s a
n e x a m p l
e o f t h e C
u r v e C i p
h e r

然后我们约定的路线是蛇形过来。

那么这个的加密密文就是 alCpiepsimhCetasixfvreroehTneuh 。

解密是时候就需要计算一下，密文一共是 $31$ 个，而商议的表格一共是 $5 \times 7 = 35$ 个，故原来最后 $4$ 个格子一定是没有填充的。然后再将密文安装约定的路线开始填充，并且记住最后 $4$ 个格子没有填充。然后再从头写出来就是明文了。

列位移密码

列移位密码(Columnar Transposition Cipher)是一种比较简单的换位密码。下面依旧通过例子来进行讲解。

明文：This is an example of the Columnar Transposition Cipher 。

密钥：i love pjf =ilovepjf。(相同的字母将会导致解不唯一，当然也可以约定一起删除相同的字母)

事先约定表格的规模，这里约定 $6 \times 8$ .约定多的位置填充符为 x 。

i l o v e p j f
T h i s i s a n
e x a m p l e o
f t h e C o l u
m n a r T r a n
s p o s i t i o
n C i p h e r x

然后按照密钥的字典序进行列读，即按照 efijlopv 的顺序，一列一列地读。

然后再按顺序写下来，密文： ipCTihnounoxTefmsnaelairhxtnpCiahaoislortesmersp 。

埃特巴什码

这是一种将字母表进行倒置替换的密码。即 $x = 25 - y \mod 26$​​ 。映射表如下：

1
2
ABCDEFGHIJKLMNOPQRSTUVWXYZ
ZYXWVUTSRQPONMLKJIHGFEDCBA

可以自己 Python 实现一个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from string import ascii_uppercase, ascii_lowercase
flag = "flag{This_is_Atbash_Cipher}"

def encrypt(m):
	"""
	decrypt == encrypt
	"""

	c = ""
	for i in m:
	    if i in ascii_lowercase:
	        c += chr(25 - (ord(i) - ord('a')) % 26 + ord('a'))
	    elif i in ascii_uppercase:
	        c += chr((25 - ord(i) - ord('A')) % 26 + ord('A'))
	    else:
	        c += i

	return c

cipher = encrypt(flag)
# cipher = "uozt{Gsrh_rh_Zgyzhs_Xrksvi}"

plain = encrypt(cipher)
# plain = "flag{This_is_Atbash_Cipher}"

也可以使用在线网站：网站地址。

凯撒密码

这也是一种经典的移位密码，而凯撒密码特指位移为 $3$ 的移位密码。即 $x = y + 3 \mod 26$ 。映射表如下：

1
2
ABCDEFGHIJKLMNOPQRSTUVWXYZ
DEFGHIJKLMNOPQRSTUVWXYZABC

于是可以自己写一个简单的 Python 脚本来实现。

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
from string import ascii_uppercase, ascii_lowercase
flag = "flag{This_is_Caesar_cipher}"

def encrypt(m, key = 3):

	c = ""
	for i in m:
	    if i in ascii_lowercase:
	        c += chr((ord(i) - ord('a') + key) % 26 + ord('a'))
	    elif i in ascii_uppercase:
	        c += chr((ord(i) - ord('A') + key) % 26 + ord('A'))
	    else:
	        c += i

	return c

def decrypt(c, key = 3):

	m = ""
	for i in c:
	    if i in ascii_lowercase:
	        m += chr((ord(i) - ord('a') - key) % 26 + ord('a'))
	    elif i in ascii_uppercase:
	        m += chr((ord(i) - ord('A') - key) % 26 + ord('A'))
	    else:
	        m += i

	return m


cipher = encrypt(flag)
# cipher = iodj{Wklv_lv_Fdhvdu_flskhu}

plain = decrypt(cipher)
# plain = flag{This_is_Caesar_cipher}

如果喜欢用现成的模块，也可以直接使用相关的模块，可以看到，现成的模块把无关字符直接给删除了。

1
2
3
4
5
6
7
In [1]: from pycipher import Caesar

In [2]: Caesar(key=3).encipher('flag{This_is_Caesar_cipher}')
Out[2]: 'IODJWKLVLVFDHVDUFLSKHU'

In [3]: Caesar(key=3).decipher('IODJWKLVLVFDHVDUFLSKHU')
Out[3]: 'FLAGTHISISCAESARCIPHER'

当然也可以用在线的网站进行解密：凯撒密码。

ROT 家族

ROT5/13/18/47 是一种简单的码元位置顺序替换暗码。此类编码具有可逆性，可以自我解密，主要用于应对快速浏览，或者是机器的读取。

ROT5 是 rotate by 5 places 的简写，意思是旋转5个位置，其它皆同。下面分别说说它们的编码方式：

ROT5：只对数字进行编码，用当前数字往前数的第5个数字替换当前数字，例如当前为0，编码后变成5，当前为1，编码后变成6，以此类推顺序循环。

ROT13：只对字母进行编码，用当前字母往前数的第13个字母替换当前字母，例如当前为A，编码后变成N，当前为B，编码后变成O，以此类推顺序循环。

ROT18：这是一个异类，本来没有，它是将ROT5和ROT13组合在一起，为了好称呼，将其命名为ROT18。

ROT47：对数字、字母、常用符号进行编码，按照它们的ASCII值进行位置替换，用当前字符ASCII值往前数的第47位对应字符替换当前字符，例如当前为小写字母z，编码后变成大写字母K，当前为数字0，编码后变成符号_。用于ROT47编码的字符其ASCII值范围是33－126，具体可参考ASCII编码，下面以rot13以例。

明文： flag{This_is_ROT47_cipher} 。

密文： 7=28L%9:D0:D0#~%cf04:A96CN

在线加解密网站：ROT47。

简单替换密码

简单替换密码是指通过一个事先约定好的密码表对明文中的字母进行一一映射替换。从这个角度看，前面的移位密码（包括凯撒密码）都是简单替换密码的特例。

例如下面一个映射表：

1
2
abcdefghijklmnopqrstuvwxyz
phqgiumeaylnofdxjkrcvstzwb

有了替换表，我们可以自己写一个 Python 的脚本进行加解密。

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
from string import ascii_uppercase, ascii_lowercase

table1 = "abcdefghijklmnopqrstuvwxyz"
table2 = "gbhevimlrnfqdxjpocusktzyaw"

def encrypt(m, table):
	c = ""
	m = m.lower()

	for i in m:
	    if i in ascii_lowercase:
	        c += table[ord(i) - ord('a')]
	    else:
	        c += i		

	return c

def decrypt(c, table):
	m = ""
	c = c.lower()

	for i in c:
	    if i in ascii_lowercase:
	        m += ascii_lowercase[table.index(i)]
	    else:
	        m += i

	return m

flag = "flag{congratulate! You have learned the demo of this word frequency analysis attack}"

cipher = encrypt(flag, table2)
# cipher = 'iqgm{hjxmcgskqgsv! ajk lgtv qvgcxve slv evdj ji slru zjce icvokvxha gxgqauru gssghf}'

plain = decrypt(cipher, table2)
# plain = "flag{congratulate! You have learned the demo of this word frequency analysis attack}"

简单替换密码一个常用的攻击方式即是在数据量极大的情况下，通过词频分析进行求解。这类题的一般会给一个很长很长的文本，然后再在文本的最后一段写上 flag 再将这个长文本和 flag 一起进行加密，如此就拥有很大的文本量，以进行词频分析攻击了。

词频攻击常用的一个网站为：quipqiup。

image-20210804174010774

也可以通过这个 paper 的爬山算法来做，在底部其还提供了对应的 Python 代码，但是是 Python2 的。

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
from pycipher import SimpleSubstitution as SimpleSub
import random
import re
from ngram_score import ngram_score
fitness = ngram_score('quadgrams.txt') # load our quadgram statistics

ctext='pmpafxaikkitprdsikcplifhwceigixkirradfeirdgkipgigudkcekiigpwrpucikceiginasikwduearrxiiqepcceindgmieinpwdfprduppcedoikiqiasafmfddfipfgmdafmfdteiki'
ctext = re.sub('[^A-Z]','',ctext.upper())

maxkey = list('ABCDEFGHIJKLMNOPQRSTUVWXYZ')
maxscore = -99e9
parentscore,parentkey = maxscore,maxkey[:]
print "Substitution Cipher solver, you may have to wait several iterations"
print "for the correct result. Press ctrl+c to exit program."
# keep going until we are killed by the user
i = 0
while 1:
    i = i+1
    random.shuffle(parentkey)
    deciphered = SimpleSub(parentkey).decipher(ctext)
    parentscore = fitness.score(deciphered)
    count = 0
    while count < 1000:
        a = random.randint(0,25)
        b = random.randint(0,25)
        child = parentkey[:]
        # swap two characters in the child
        child[a],child[b] = child[b],child[a]
        deciphered = SimpleSub(child).decipher(ctext)
        score = fitness.score(deciphered)
        # if the child was better, replace the parent with it
        if score > parentscore:
            parentscore = score
            parentkey = child[:]
            count = 0
        count = count+1
    # keep track of best score seen so far
    if parentscore>maxscore:
        maxscore,maxkey = parentscore,parentkey[:]
        print '\nbest score so far:',maxscore,'on iteration',i
        ss = SimpleSub(maxkey)
        print '    best key: '+''.join(maxkey)
        print '    plaintext: '+ss.decipher(ctext)

希尔密码

希尔密码开始有点数学的感觉了，这玩意是利用的线性代数的知识，是基于线性代数多重代换密码。

基本的线性代数知识应该还是有。

矩阵乘法即 行 × 列

矩阵可逆：

1、若是矩阵的秩小于n，那么这个矩阵不可逆，反之就是可逆矩阵。

2、若是矩阵行列式的值为0，那么这个矩阵不可逆，反之则为可逆。

3、对于齐次线性方程AX=0，若方程只有零解，那么这个矩阵可逆。

4、对于非齐次线性方程AX=b，若方程有特解，那么这个矩阵可逆。

加密过程

  1. 首先将字母与 0~25 进行字典序映射

    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
    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

  2. 然后选择一个模 $26$ 可逆矩阵 $A$ 作为密钥，$A$ 的规模是 $n \times n$。

  3. 然后将需要加密的明文( $x1,x_2,\cdots x{nm}$ )转化为一个列向量 $X$，如果明文长度太长，可以截断为多组列向量，为了书写方便，这些列向量又可以组成一个矩阵 $B$。

  4. 计算矩阵乘法 $C = A \times B$ 。再将 $C$ 矩阵按照列进行拆分后拼接。

解密过程

  1. 首先得到密钥 $A$ 和 加密矩阵 $C$ 。
  2. 计算矩阵 $A$ 的逆 $A^{-1}$ 。
  3. 计算矩阵乘法 $A^{-1} \times C = A^{-1} \times A \times B = B$ 。
  4. 再将矩阵 $B$ 拆解为对应的向量后，映射回字母。

例子：

加密过程

  1. 明文： thisishillcipher 。

  2. 转化为数字： 19, 7, 8, 18, 8, 18, 7, 8, 11, 11, 2, 8, 15, 7, 4, 17,

  3. 选择一个模 $26$ 可逆矩阵 $A$ （对应的字母版 key 为 hifldcheg）：

  4. 将待加密的明文进行分组：

  5. 将密钥矩阵进行左乘。

  6. 再将完事后的数据 21,12,1,20,24,6,12,19,17,3,13,3,25,12,1,2,16,11 转化为字母密文 vmbuygmtrdndzmbcql

解密过程

  1. 密文：vmbuygmtrdndzmbcql 。

  2. 转化为数字： 21,12,1,20,24,6,12,19,17,3,13,3,25,12,1,2,16,11 。

  3. 计算密钥矩阵 $A$ 的逆矩阵 $A^{-1}$​ 。

  4. 再对密文矩阵进行左乘。

  5. 再将解出的数字 19,18,7,11,15,17,7,8,8,2,7,23,8,18,11,8,4,23 转为明文即可， 明文为 thisishillcipher 。

这里也贴一个在线网站的样例, 在线网站也挺多的。网站一。

image-20210804204205555

当然，也可以自己用 Python 的代码。

下面提供了一个 mod 意义下求解矩阵的逆的代码。

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
97
98
99
100
# 求解 mod 意义下的矩阵的逆

import numpy as np # 计算行列式的值

def gcd(a, b):
	"""
	计算最大公因数
	"""
	while b != 0:
		a, b = b, a%b
	return a

# 检查矩阵格式是否合法以及是否可逆
def check_matrix(A, M):
	if (not isinstance(A, list)) or (not isinstance(A[0], list)) or (not isinstance(A[0][0], int)):
		try:
			mat = np.array(A)
			if mat.shape[0] != mat.shape[1]:
				raise MyError('The number of rows must be equal to the number of columns number')
		except Exception as e:
			raise MyError(f'Invalid matrix format. {e}')
	D = int(np.linalg.det(A)) % M
	if gcd(D, M) > 1:
		raise MyError('This matrix does not have a modular inversion matrix.')

# 矩阵的第一类初等变换：交换矩阵第i行与第j行
def swap_row(A, i, j):
	temp = A[j]
	A[j] = A[i]
	A[i] = temp

# 矩阵的第二类初等变换：将矩阵第i行乘以n
def mul_row(A, i, n, M):
	a = A[i]
	A[i] = [a[x] * n % M for x in range(len(a))]

# 矩阵的第三类初等变换：矩阵第i行减去n倍的j行
def sub_row(A, i, j, n, M):
	a = A[i]
	b = A[j]
	A[i] = [(a[x] - n * b[x]) % M for x in range(len(a))]

# 找到符合要求的第i行
def find_row(A, i, M):
	start = i
	while A[start][i] == 0 or gcd(A[start][i], M) > 1:
		start = start + 1
	return start 

# 返回一个整数的模逆元素
def mod_rev(num, mod):
	if(num == 0 or gcd(num, mod) > 1):
		raise MyError('modular inversion does not exists.')
	else:
		i = 1
		while i * num % mod != 1:
			i = i + 1
		return i


def matrix_rev(A, M):
	try:
		check_matrix(A, M)
		dim = len(A)
		# concatenate with a unit matrix
		for i in range(dim):
			for j in range(dim):
				if j == i:
					A[i].append(1)
				else:
					A[i].append(0)
		# transform
		for i in range(dim):
			target_row = find_row(A, i, M)
			swap_row(A, i, target_row)
			n = mod_rev(A[i][i], M)
			mul_row(A, i, n, M)
			for j in range(dim):
				if j != i:
					sub_row(A, j, i, A[j][i], M)
		# get result
		A_rev = [A[i][dim:] for i in range(dim)]
		return np.matrix(A_rev) % M
	except Exception as e:
		print(e)



if __name == "__main__":
	# A 是矩阵， M 是 MOD，mat 是 A 的逆 
	A = [[ 7,  8,  5],
	     [11,  3,  2],
	     [ 7,  4,  6]]
	M = 26
	mat = matrix_rev(A, M)
	"""
	mat = matrix([[12,  8,  9],
	              [ 0, 11,  5],
	              [25, 18, 21]], dtype=int32)
	"""

由于 希尔密码 存在一定的混淆，并不是简单的替换，即不同位置的相同明文字母在同一组密钥加密下可能会出现很多截然不同的密文，故在较短的密文上进行词频分析是没有什么效果的。但是从上面的加密过程和解密过程可以知道，希尔密码是纯线性的加密，如果能够知道一部分明文密文对，则可以通过构建符合的代数方程对密钥进行求解。

波利比奥斯方阵密码

波利比奥斯方阵密码是一种棋盘密码，通过事先将波利比奥斯棋盘排列好，再将明文字母从棋盘中去查找对应的坐标，然后用字母的坐标进行替换。

如下是一种方阵

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

则明文： this is Polybius Square Cipher 加密后对应的密文为 44232443 2443 3534315412244543 434145114215 132435231542 。

事实上，通过加密过程，我们也可分析出，这个本质上前面的简单替换密码没有任何区别：只是前面将一个字母用另一个字母进行替换表示了；而这里只是将一个字母用一个唯一(不考虑 i j 重合)的二元组来表示了。所以本质没变还是可以通过词频分析进行破解。

Playfair Cipher 密码

Playfair Cipher 是一种双字替换密码，通过双字取代了原来的简单单表替换密码，使得密文更加难以被破译。

例子：

明文： this is Playfair Cipher 。

密钥：Cryptography 。

  1. 整理密钥，去除重复的字母，得到 cryptogah ，也可写本次密钥为 cryptogahbdefiklmnqsuvwxz ，直接也是忽略了 i j。

  2. 然后将密钥去重部分依次填入一个 $5 \times 5$ 的方格中，再将 $26$​ 字母表中剩余的字母继续进行填充，刚好填充完毕这个表格（依旧是将 i 和 j 视为一样，有的版本是将 Z 去除而不是重复 i 和 j）。

    | | 1 | 2 | 3 | 4 | 5 |
    | ——- | —— | —— | —— | —— | —— |
    | 1 | c | r | y | p | t |
    | 2 | o | g | a | h | b |
    | 3 | d | e | f | i/j | k |
    | 4 | l | m | n | q | s |
    | 5 | u | v | w | x | z |

  3. 将明文按照两个一组进行划分，得到： th is is pl ay fa ir ci ph er 。如果是明文中去除空格分组后会出现连续的相同字母，则需要在重复的单词后插入 X 进行分割，如 well -> we ll -> we lx lx 。 如果是奇数则在最后补充 X 以配对。

    这是规定，理由是出现 XX 的概率很小。 非要说结尾是 x. e.g “I am a fox” 那随便填个什么吧，反正不影响语义就行。

  4. 进行密文替换。规则为：

    1. 如果分在同一组的两个字母在表中是同一行，则分别取其右侧的字母来代替。如果在最右侧边缘，则其右侧就是最左侧。如 CY -> RP , RT -> YC 。
    2. 如果分在同一组的两个字母在表中是同一列，则分别取其下方的字母来代替。如果在最下侧边缘，则其下方就是最上方。如 CD -> OL , FW -> NY 。
    3. 如果分在同一组的两个字母在表中在不同的行列，则分别取其形成的四边形的另外两个角的值，顺序按照行优先。如 OF -> AD , PG -> RH 。

  5. 替换后为： PB KQ KQ CQ FA NF PE PD HI MG

  6. 最后得到密文将上面合并，五个一组写出来： PBKQK QCQFA NFPEP DHIMG 。

过程有点太繁琐了，贴一个在线的网站。Playfair Cipher。

image-20210805102631566

也有现成的模块可以直接调用：

1
2
3
4
5
6
7
In [1]: from pycipher import Playfair

In [2]: Playfair("cryptogahbdefiklmnqsuvwxz").encipher("this is Playfair Cipher")
Out[2]: 'PBKQKQCQFANFEPPDHIMG'

In [3]: Playfair("cryptogahbdefiklmnqsuvwxz").decipher("PBKQKQCQFANFEPPDHIMG")
Out[3]: 'THISISPLAYFAIRCIPHER'

维吉尼亚密码

维吉尼亚密码(Vigenère Cipher)是在恺撒密码的基础上扩展出多表代换密码，根据密钥(当密钥长度小于明文长度时可以循环使用)来决定用哪一行的密表来进行替换，以此来对抗字频统计。

映射表如下

维吉尼亚密码映射表

例子：

明文： this is Vigenere Cipher 。

密钥： Cryptography 。（比明文短就进行循环使用。

  1. 进行加密时，将密钥循环拼接直到长度与明文一致。 CryptographyCryptogr 。
  2. 然后依次读取明文和密钥的第 i 位 p[i] 和 k[i]​ ，则第 i 位密文就是映射表中 p[i] 这一列和 k[i] 这一行的交点的字母。
    如明文第一个字母的 T 密钥第一个字母是 C 则密文第一个字母是 V ，依次类推。
    用数学的式子就是，密文字符 $C_i$ 与明文字符 $P_i$ 和密钥字符 $K_i$ 的关系为 $C_i = (P_i + K_i) \mod 26$ 。
  3. 最后加密的结果为 VYGHBGBZGTUDTVAXIVKI 。

也可以用 Python 自己写一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
p = "THISISVIGENERECIPHER"
k = "CRYPTOGRAPHY"

p = p.upper()
k = k.upper()

# encrypt
c = ""
for i in range(len(p)):
    c += chr((ord(p[i]) - ord('A') + ord(k[i%len(k)]) - ord('A')) % 26 + ord('A'))
# c = VYGHBGBZGTUCTVAXIVKI
    
# decrypt
m = ""
for i in range(len(p)):
    m += chr((ord(c[i]) - ord(k[i%len(k)])) % 26 + ord('A'))
# m = THISISVIGENÈRECIPHER

也可以用现成的轮子:

1
2
3
4
5
6
7
In [1]: from pycipher import Vigenere

In [2]: Vigenere('CRYPTOGRAPHY').encipher('THISISVIGENERECIPHER')
Out[2]: 'VYGHBGBZGTUCTVAXIVKI'

In [3]: Vigenere('CRYPTOGRAPHY').decipher("VYGHBGBZGTUCTVAXIVKI")
Out[3]: 'THISISVIGENRECIPHER'

可以对维吉尼亚密码进行未知密码攻击。虽然维吉尼亚密码通过多表代换以抵抗词频分析，但是其仍然具有一定的统计特征，尤其是密钥越短导致密钥循环越多时，每次密钥循环处的相同位置都是一组单表替换的数据。

先提供一个在线网站。

对维吉尼亚密码的未知密钥攻击通常分为一下几个步骤：

  1. 确定密钥长度。
  2. 确定密钥内容。
  3. 根据密钥进行解密。

确定密钥指数的方法有：Kasiski 测试 和 重合指数法等。具体可以参考这个文章：我是链接。也可以参考这个 paper。也可参考这个博客。

这里说说重合指数法，比较有意思。

设一门语言由 $n$ 个字母构成，每个字母发生的概率为 $pi(1 \leq i \leq n)$ ，则重合指数是指其中两个随机元素相同的概率之和，记为 $CI = \sum{i=1}^np_i^2$ 。

所以，很容易得到一个全随机的英文文本中， $CI = 26 \times (\frac{1}{26})^2 = \frac{1}{26} \approx 0.0385$ 。而别人统计，一个有意义的英文文本的 $CI \approx 0.064712$ （通过英文词频计算出来的）。

实际使用中，通常使用 $CI$​​ 的观测值 $CI’= \sum_{i=1}^n\frac{cnt_i}{len} \times \frac{cnt_i - 1}{len - 1}$​​ ，其中 $len$​​ 是文本的长度，$cnt_i$​ 是文本中各个字母出现的次数。

那么 $CI’$​ 的实际作用是什么呢？（以下都是在文本长度足够长的基础上的。

  1. 考虑一个正常的足够长的文本，则计算其 $CI’$ 一定是在 $0.064712$​ 的附近的。那么加密之后的密文用来计算显然也是不会改变这个值的。（只是换了符号嘛，比例并没有变）。

  2. 再考虑将上面的正常有意义的文本随机分成数量相等的 $N$ 份（分开后文本还是足够长）。则计算的 $CI’$ 将发生怎样的变化呢？答案是两个部分计算的值都还是在 $0.064712$ 的附近的。这样的随机抽取并不会改变每个字母的分配概率，则同一个字母在新的部分文本中的比率和这个字母在原来文本中的大致是相等的，故 $CI’$​​ 也是大致相等的。（这个也就是随机抽样

  3. 那么同理等距抽样的结果也是一样的，即用样本反映总体。从有意义的文本中每间隔 $M$ 就抽取一个字母，这样将原来的文本分成 $\frac{len}{M}$ 份（每份文本还是足够长），则每份文本计算的 $CI’$ 依旧是差不多的是在 $0.064712$​ 的附近的。

  4. 现在将其中任意一份的字母，都使用一个单表替换后，再次计算 $CI’$ 这就回到了第一点，只不过的文本变小了点，但只要还是足够大，则 $CI’$ 依旧是差不多的是在 $0.064712$ 的附近的。

  5. 而在维吉尼亚密码的加密中，由于循环使用密钥会导致密钥第 $i$ 位所加密的第 $j$ 位密文满足 $j \equiv i \pmod {len(key)}$ 。 即满足上述的所以的 $j$ 位的明文事实上就是一个原本有意义的文本被分按照间距 $M=len(key)$ 分配到了同一组中，因此其 $CI’$ 必然应该在 $0.064712$​ 的附近。

    1
    2
    3
    4
    5
    6
    plain: THISISVIGENERECIPHER
    key:   KEYKEYKEYKEYKEYKEYKE
        
    其中 TSVERIE 都是使用同一个表进行替换，密钥中的字母 K 选择了某一个这个表
    其中 HIINEPR 都是使用同一个表进行替换，密钥中的字母 E 选择了某一个这个表
    其中 ISGECH 都是使用同一个表进行替换，密钥中的字母 Y 选择了某一个这个表

  6. 所以，我们可以通过枚举 $M$ 将密文分成 $\frac{len}{M}$ 个组，然后计算这些组的 $CI’$ ，简单起见，再取一个平均或者方差，看枚举的 $M$ 中那个的结果使得整体的 CI' 更接近 $0.064712$​ 则密钥的长度就更可能是这个 $M$ 。

确定密钥的内容，也有点多、捂脸。

自动密钥密码

自动密钥密码(Autokey Cipher)是多表替换密码，与维吉尼亚密码密切相关，但使用不同的方法生成密钥，通常来说要比维吉尼亚密码更安全。自动密钥密码主要有两种，关键词自动密钥密码和原文自动密钥密码。

关键词自动密码是在一个关键词之后，接上明文，作为密钥，而后就和维吉尼亚密码一模一样了。

若未知关键词则还是只能进行爆破。参阅 paper。

仿射密码

放射密码也是一种单表替换密码，其做法是通过一组线性变换将一个字母变化到另一个字母。

加解密过程如下：

其中 $A$ 和 $B$ 都是整数，且要求 $gcd(A, 26) = 1$ 以保证 $A^{-1}$ 存在。

在线网站：网站。

也可以自己动手写一个 Python。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import gmpy2

def encrypt(plain, A, B):
    if gmpy2.gcd(A, 26) != 1:
        print("WARNNING: A does not have a modular inversion!")
    
    c = ""
    a = ord('a')
    plain = plain.lower()
    for i in plain:
        c += chr((A * (ord(i) - a) + B) % 26 + a)

    return c

def decrypt(c, A, B):
    assert gmpy2.gcd(A, 26) == 1, "A does not have a modular inversion!"

    A_ = gmpy2.invert(A, 26)
    m = ""
    a = ord('a')
    for i in c:
        m += chr(A_ * (ord(i) - a - B) % 26 + a)

    return m

培根密码

培根密码(Baconian Cipher)是一种替换密码，每个明文字母被一个由 5 字符组成的序列替换，最初的加密方式就是由 A 和 B 组成序列替换明文，比如字母 D 替换成 aaabb，以下是对应关系：

1
2
3
4
5
6
7
8
A = aaaaa  I/J = abaaa  R = baaaa
B = aaaab  K = abaab    S = baaab
C = aaaba  L = ababa    T = baaba
D = aaabb  M = ababb    U/V = baabb
E = aabaa  N = abbaa    W = babaa
F = aabab  O = abbab    X = babab
G = aabba  P = abbba    Y = babba
H = aabbb  Q = abbbb    Z = babbb

在线网站：网站。

ADFGX 和 ADFGVX 密码

ADFGX 密码(ADFGX Cipher)是结合了改良过的 Polybius 方格替代密码与单行换位密码的矩阵加密密码，使用了 5 个合理的密文字母：A，D，F，G，X，这些字母这样选择是因为当转译成摩尔斯电码(ADFGX 密码是德国军队在一战发明使用的密码)不易混淆，目的是尽可能减少转译过程的操作错误。

加密矩阵如下：

A D F G X
A P H Q G M
D E A Y N O
F F D X K R
G C V S Z W
X B U T I/J L

加密过程如下：

  1. 明文： this is ADFGX 。
  2. 列位移密钥： howare 。
  3. 查表横纵坐标：XF AD XG GF XG GF DD FD FA AG FF 。
  4. 重新写入矩阵中，再按。
h o w a r e
X F A D X G
G F X G G F
D D F D F A
A G F F
  1. 密文按照列的字典序读取，密文为：DGDFGFAXGDAFFDGXGFAXFF

可以使用 Python 来用现成的模块

1
2
3
4
5
6
7
8
9
In [1]: from pycipher import ADFGX

In [2]: a = ADFGX('phqgmeaynofdxkrcvszwbutil','HOWARE') # 构建加密矩阵和列位移密钥

In [3]: a.encipher('this is ADFGX')
Out[3]: 'DGDFGFAXGDAFFDGXGFAXFF'

In [5]: a.decipher('DGDFGFAXGDAFFDGXGFAXFF')
Out[5]: 'THISISADFGX'

在线加解密：网站一。网站二。

ADFGVX 密码

ADFGVX 密码与 ADFGX 类似，就是多扩充了一个字母 V 可以将数字囊括进来了。

加密矩阵如下：

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

其余过程一样。也可以用 Python 利用现成的轮子。

1
2
3
4
5
6
7
8
9
In [1]: from pycipher import ADFGVX

In [2]: a = ADFGVX('ph0qg64mea1yl2nofdxkr3cvs5zw7bj9uti8','HOWARE') # 构建加密矩阵和列位移密钥

In [3]: a.encipher('this is ADFGVX')
Out[3]: 'DVXXVAVAXVDAGAGVXVFGAXFG'

In [5]: a.decipher('DVXXVAVAXVDAGAGVXVFGAXFG')
Out[5]: 'THISISADFGVX'

更多类似的密码，请参考博客。

现代密码

一般而言，现代密码主要都包含了一些现代的数论知识和古典密码学理论。在密码学的分类中，可以将现代密码分为 对称密钥密码算法 和 非对称密钥密码算法 。这个名称已经很明显了，这里不再解释。同时，现代密码中还有一类不可忽视的算法即 哈希算法。

非对称密钥密码算法

而在 CTF 比赛中，更多地是考察 非对称密钥密码算法 。因为，这类算法对数论知识的需求更多，可以说几乎是完全建立在数论的基础上的。

众所周知，现代密码学的公钥密码体制都是建立在一个 单向求解简单 问题上的。如基于大整数分解困难问题的 RSA 算法；如基于离散对数计算困难问题的 ElGamal 和 Diffie–Hellman 密钥协商；如基于椭圆曲线的的密码体制，即 ECC。

如上的密码体制，在合理的配置参数下，就目前的算力而言都仍然还是计算安全的。故 CTF 中，必然要给攻击者留下 weak 的漏洞点，否则攻击者是不可能得到 flag 的。（能发现体制 0 day 或者 直接解决数学中的难题橄榄整个加密系统的大犇除外。）而这个漏洞又不可能是 0day （有出题人愿意给出 0day 那当我没说），所以这就造就了这些漏洞必须的现存的，能够被攻击者所知道的。

那么问题就简单的，对于一个密码系统而言，他的漏洞总是有限的，再根据一些题目已知和未知排除不可能的漏洞，则剩下的可能的方法就几乎是唯一的。事实上，随着 CTF 比赛的火热，很多简单的比赛就直接将洞搬过来，也没有进行什么组合和设计，使得新漏洞的出现与出题量之间的比例越来越小，所以这些漏洞就变得很常见了，也就变成了所谓的模板了。（基于这样一个前提，几乎可以做出一个自动化工具来解决大部分的这类题目。）为啥不是全部呢？因为还是有很多用心的出题人会利用这些知识点来进行综合设计，这就更有数学的味道了。

RSA

基本原理
大数分解困难问题

如前面所言，RSA 是基于大整数分解困难问题的，在已知两个数 $p$ 和 $q$ 的情况下，计算两者乘积 $n = p \times q$ 是很容易的。

但是，已知 两者乘积 $n = p \times q$ 的情况下，想求解 $p$ 和 $q$ 是很困难的。

这个是数学家研究的，这里只做应用。

欧拉函数

对于正整数 $n$ ，欧拉函数 $\varphi(n)$ 的意义是小于 $n$ 的正整数中与 $n$ 互质的数的数目。（PS：两个数 $a$ 和 $b$ 互质 $\Leftrightarrow gcd(a,b) = 1$​ 。

根据定义，很容易得到，对于任意质数 $p$ ，有 $\varphi(p)=p-1$ 。

已知任意一个数，求解欧拉函数可以利用唯一分解定理，将整数 $n$ 唯一分解。再利用各个质数的 $\varphi$​ 来求解。最终结果为:

$P={p_1,p_2…}$​ 为所有质数集合

特别地，当 $n = p \times q$ ，$p$ 和 $q$ 都是质数时，有 $\varphi(n)=\varphi(p) \times \varphi(q) = (p-1) \times (q-1)$ 。

欧拉定理

欧拉定理是一个关于同余的定理，其数学表达式如下所示：

这里只做应用，证明请参考 欧拉定理)。

加解密过程
密钥生成

随机生成两个大质数 $p$​ 和 $q$​ ，计算出 $n = p \times q$​ 和 $\varphi(n) = (p-1) \times (q-1)$​ ，随机选取一个数 $e$​ 满足 $gcd(e, \varphi(n)) = 1$​ ，如此可以计算出一个 $e$​ 关于 $\varphi(n)$​ 单独唯一乘法逆元 $d$​ ，即 $e \times d \equiv 1 \pmod {\varphi(n)}$​​ 。销毁生成的质数 $p$​​ ， $q$​ 和 $\varphi(n)$​ ，同时严格保密 $d$​ 。

则 $(e, n)$ 组成了公钥，$(d, n)$​ 组成了私钥。如果不泄漏额外的信息、不使用过小的质数、不做一些高风险的生成，则只根据公钥 $(e, n)$ 想要计算出私钥 $(d, n)$ 是计算不可行的。

加密过程

将需要加密的消息按某种格式转化为一个或多个数字， CTF 中一般就将 flag 转化为一个数字 $m$ ，然后计算密文 $c = m ^ e \mod n$ 。

考虑到有可能会存在 $m|n$ 的情况，而由于 $n = p \times q$ ，故此时必有 $m|p$ 或者 $m|q$ 。由于 $p$ 和 $q$ 都是质数，所以 $m=p$ 或者 $m=q$ 。一方面这个概率是很小的。另一方面，如果真的这么巧， $m=p$ 或者 $m=q$ 那就按照前面的法则再次重新生成一组 $p$ 和 $q$ ，然后再构建即可。

解密过程

设需要解密的密文为 $c$​ ，则明文对应的数字 $m = c ^ d \mod n$​ 。

由上述的解密数学等式中可以明白，一旦 $p$ 、 $q$ 、$\varphi(n)$ 和 $d$ 中有一个或者多个泄露或者被计算出来，则可以对密文进行完全破译。

Elgamal

基本原理
阶

设 $n > 1$ ，且 $gcd(a, n) = 1$，则必然存在一个 $x, 1 \leq x \leq n-1$ ，使得 $a^x \equiv 1 \pmod n$ 。

其中满足上式的最小的 $x$​​ 称为 $a$​ 模 $n$​ 的阶，符号记为 $ord(a)$​ 。

注意，群的阶指的是群中元素的个数。

本原元

观察上述的式子可以发现，根据欧拉定理，显然 $\varphi(n)$ 也是上述方程的一组解，即 $a^{\varphi(n)} \equiv 1 \pmod n$​ 。

但显然 $\varphi(n)$ 并不一定是最小的，即不一定是 $a$ 模 $n$ 的阶。但当 $\varphi(n)$ 是最小的的时候，即 $ord(a) = \varphi(n)$ 时，称 $a$ 为 $n$ 的本原元。

离散对数

基于离散对数计算困难问题，也可以设计出非对称加密体系。 Elgamal 就是其中一种实现。

当模 $p$​ 有本原元时，设 $a$​ 为模 $p$​ 的一个本原元，则当 $x \equiv a^k \pmod p$​ 时，有 $Ind_a x \equiv k \pmod {\varphi(p)}$​​ 。此处 $Ind_a x$​ 即为 $x$​ 以整数 $a$​ 为底，模 $\varphi(p)$​ 时的离散对数值。

而离散对数计算困难则是说，已知 $p$ ，$a$ ， $k$ 计算 $x$ 很容易，但是反过来，已知 $x$ ， $a$ ， $p$ 想要计算 $k$ 则极其困难。

加解密过程
密钥生成

随机选择一个大质数 $p$ ，并且 $p-1$ 应该含有一个很大的质因数（why？可能是为了确保生成元的个数足够多？一个质数 $p$ 的生成元的个数为 $\varphi(p-1)$ 个.这个个数是因为定理：G=\是n阶循环群，a ^ k是G的生成元的充要条件是gcd(k, n) == 1。我的简单证明，如果不互质，则任意x无论怎么去变化都不可能使得 k^x 将 n 的剩余系中的元素遍历完，故 (a^k)^x 也无论如何无法遍历完 G 中的元素了，而原来 a^y 随着 y 的变化是可以遍历完 G 中的元素的，正因为 y 可以取完 n 的剩余系中的每个数，所以，此时的 a^k 也就不可能为生成元了，故需要 gcd(k,n)==1才行是a ^ k是G的生成元）。再求得模 $p$ 的生成元 $g$ 就可以生成 $p$ 阶循环群 $G$ 。此时将 $p$ 和 $g$ 进行公开。

用户随机选择一个整数 $d, (2 \leq d \leq p-2)$​ ，可以计算出 $h = g^d \mod p$​ 。

则 $d$​ 就是私钥，$h$​ 就是公钥。由于计算离散对数是很困难的，故根据 $h$​ 想要计算出 $d$​ 是十分困难的。

加密过程
  1. 假如需要加密的消息是 $m$​ ，（提前将字符串映射为一个数字）；
  2. 发送方随机挑选一个随机数 $r, (2 \leq r \leq p-2)$ ，然后计算 $c_1 = g^r \mod p$​​​ ；
  3. 发送方根据接收方的公钥 $h$​​ 计算 $c_2 = m \times h ^ r \mod p$​ ；
  4. 然后将二元组 $(c_1, c_2)$ 发送。
解密过程
  1. 接收方收到消息 $(c_1, c_2)$ 后，可以通过自己的私钥 $d$​ 进行解密；
  2. 计算出 $c_1^d \equiv (g^r)^d \equiv (g^d)^r \equiv h^r \pmod p$​​ ；​
  3. 再计算出 $c_1^d$ 关于 $p$ 的乘法逆元 $(c_1^d)^{-1}$ ,即有 $c_1^d \times (c_1^d)^{-1} \equiv 1 \pmod p$ ，即 $h^r \times (c_1^d)^{-1} \equiv 1 \pmod p$ ；
  4. 再计算 $c_2 \times (c_1^d)^{-1} \equiv m \times h^r \times (c_1^d)^{-1} \equiv m \pmod p$ 。

以上的过程可以看到，由于每次加密都会生成一个随机数 $r$ ，所以即使的相同的明文在相同的公私钥在不同的加密次中也会加密出不同的密文。而也可以看出，每次该系统的安全性对随机数 $r$ 有着很强的依赖，一定不能使用相同的随机数 $r$ 对同一组明文进行加密。

格密码

基本原理
格（lattice）的定义

给定 $m$ 维欧式空间 $R^m$ 中的 $n$ 个线性无关向量 $b_1,b_2,b_3,\cdot\cdot\cdot,b_n \in R^m$ ，则这组向量产生的格为：

此时称上述的 $n$ 个向量 $b_1,b_2,b_3,\cdot\cdot\cdot,b_n$ 称为格 $L$​ 的一组基。

此时，如果定义 $B$ 是上述的 $n$ 个向量 $b_1,b_2,b_3,\cdot\cdot\cdot,b_n$ 作为列组成的 $m \times n$ 的矩阵，则上述定义也可以转化为：矩阵 $B$ 产生的格为：

于是 格 就是一堆线性无关的向量”胡乱组合“的结果，其本质依然是一个向量。

而在坐标中，一个向量其实可以用一个点进行表示，即讲向量 $\vec{a}=(1,2,3)$​​ 就是用点 $(1，2，3)$ 来表示了该向量。

在这种意义下，格 其实又是 $m$ 维空间中的一组有周期性出现的点的集合。

此时，定义一些名词：

  • 基：上述的 $n$​ 个向量 $b_1,b_2,b_3,\cdot\cdot\cdot,b_n$​ 称为格 $L$​ 的一组基。
  • 秩：上述线性无关向量的个数这个格 $L$​​ 的秩为 $n$​​ 。
  • 位数：上述线性无关向量的维度这个格的维数为 $m$​​ 。

特别地，如果 $m==n$​​​​ 则称这个格是满秩的。

span

格 $L(B)$​ 的基 $B$​ 的所有线性组合所形成的集合，就叫做这组基所张成的空间，记为 $span$​ ，于是有：

我在想这个 span 和 格L 它有区别吗？ 我觉得毫无区别呀

格中逐次最小长度（successive minima）

格中连续最小长度是一个集合， ${\lambda_1, \lambda_2, \lambda_3, \cdot\cdot\cdot, \lambda_n \ | \ \lambda_i \in R }$ 。其中 $\lambda_i$ 含义为，以原点为球心，在向量空间 $R^m$ 中包围 $i$ 个线性无关格向量的最小球半径。 即

所以，很显然对于任意 $\forall \ i \leq j$ 都有 $\lambda_i \leq \lambda_j$​ 。

感谢这篇文章：https://www.gps949.com/2020/09/07/%E6%A0%BC%E5%AF%86%E7%A0%81%E5%AD%A6%E7%AC%94%E8%AE%B0/

格中基本困难问题——最短向量问题（SVP）

给定一个格 $L$ 及其一组基 $B$ 找到格 $L$ 中的非零向量 $\vec{v} \in L$ 使得对于格中任意其他非零向量 $\vec{u} \in L$ 都有 $|\vec{v}| \leq |\vec{u}|$ 。

最近向量问题（Closest Vactor Problem, CVP）

给定一个格 $L$​ 和目标向量 $\vec{t} \in R^m$​ 找到一个非零向量 $\vec{v} \in L$​ 使得对于格中任意非零向量 $\vec{u} \in L$​ 都有 $|\vec{v}-\vec{t}| \leq |\vec{u} - \vec{t}|$​ 。

—-Babai’s nearest plane algorithm