0x00 课程视频

0x01 什么是密码学

【基本概念与作用应该都知道一点吧，这里不做基础介绍了_(:з」∠)_……

古典密码学主要关注信息的保密书写和传递，以及与其相应的破译方法。

现代密码学不只关注信息保密问题，
还同时涉及信息完整性验证、信息发布的不可抵赖性、以及在分布式计算中产生的来源于内部和外部的攻击的所有信息安全问题。

CTF中的古典密码学题目有时也会出现在杂项里面，
古典加密常常不给出加密算法，需要判断或者尝试一下。

而CTF中的现代加密常常会给出加密算法，或者以一些形式提示某种常用的加密算法。
即通过公开的加密算法和题目给的条件来思考解密的算法并加以实现。

密码学描述中，对传输者和窃取者有习惯名称。

可以用数学中的函数形式来表达加密解密的过程。

• $k$代表密钥，$m$代表明文，$c$代表密文。
• $E$代表加密函数，$D$代表解密函数。
• 加密过程为：$c=E(k,m)$
• 解密过程为：$m=D(k,c)$

0x02 凯撒加密

定义

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

按密匙进行移位后，可以得到一张一一对应的密码表，
基本的加密解密过程都可以通过查表来完成。

外圈对应明文，内圈对应密文。
加密时：将明文字母一一替换成内圈字母，
解密时：将密文字母一一替换成外圈字母。

• 类型：单表替代加密。
• 加密对象：一般为字母。
• 加密方式：字母按偏移量（密钥）移位。
• 安全性：非常差。
  密钥只有25种情况，很轻易就能枚举出来。

加密脚本

from string import ascii_uppercase

Plaintext = "game.granbluefantasy.jp" # 在这里输入明文
Key = 3 # 在这里输入密钥

Plaintext = Plaintext.upper() # 为了加密过程简单，将字符串字母全转换为大写

def Encrypt(Plaintext, Key): # 加密函数，操作为减少偏移量
    Ciphertext = ""
    for i in Plaintext:
        if i not in ascii_uppercase:
            Ciphertext += i
        else:
            Ciphertext += chr(((ord(i) - ord("A") - Key) % 26) + ord("A"))
    return Ciphertext

print(Encrypt(Plaintext, Key)) # 直接输出加密结果

运行结果：

爆破脚本

由于密钥情况很少，可以直接爆破枚举出来，
观察找出有意义的字符串，则为明文。

from string import ascii_uppercase

Ciphertext = "DXJB.DOXKYIRBCXKQXPV.GM" # 在这里输入密文

Ciphertext = Ciphertext.upper()

def Decrypt(Ciphertext, Key): # 解密函数，假定加密过程为减少偏移量
    Plaintext = ""
    for i in Ciphertext:
        if i not in ascii_uppercase:
            Plaintext += i
        else:
            Plaintext += chr(((ord(i) - ord("A") + Key) % 26) + ord("A"))
    return Plaintext


for Key in range(26): # 爆破密钥，范围为0~26
    print("Key = ", Key, "--->", Decrypt(Ciphertext, Key), sep="")

运行结果：

可以发现Key = 3时，
出现了一串有意义的字符串GAME.GRANBLUEFANTASY.JP。

0x03 关键词加密

定义

关键词加密(Keyword Cipher)也是一种单表替代加密，与凯撒加密不同之处在于密钥可以更为复杂。

加密时需要选择一个关键词，
如果这个关键词有重复的字母，去除除第一次出现之外的所有的相同的字母。

e.g.

如果选定的关键词为“success”，则使用“suce”。

将该关键词写在字母表的下方，并用字母表的其他字母按标准的顺序填写余下的空间，
这样就构建了字母一一对应关系的密码表。

加密时用下面一行中的字母对应替换上面一行的字母；
解密时用上面一行中的字母对应替换下面一行的字母。（也可能反过来）

• 类型：单表替代加密。
• 加密对象：一般为字母。
• 加密方式：用关键词（密钥）生成密码表，然后按照密码表替换字母。
• 安全性：一般。
  密钥不能轻易枚举出来，
  但通过密码分析可能破译出密码。

示例

生成密码表

假定关键词为angstromcf。

则生成密码表如图：

上面一行为标准的字母表。

下面一行先将关键词angstromcf填上，
然后将剩余未出现的字母，按照顺序填入。

加密

对于明文：actf{yum_delicious_salad}。

定加密的替换方式为：上面一行替换下面一行，
即：将明文中的上面一行中的字母，对应替换成下面一行的字母。

e.g.

第一个a字母，替换成a，
第二个c字母，替换成g，
第三个t字母，替换成q。

则得到密文：agqr{yue_stdcgciup_padas}。

解密

对于密文：agqr{yue_stdcgciup_padas}。

由于加密时为上面一行替换下面一行，
所以解密的替换方式为：下面一行替换上面一行，
即：将密文中的下面一行中的字母，对应替换成上面一行的字母。

e.g.

第一个a字母，替换成a，
第二个g字母，替换成c，
第三个q字母，替换成t。

则得到明文：actf{yum_delicious_salad}。

0x04 仿射加密

比较复杂的加密方法，因为涉及到一定的数学知识。

定义

在仿射加密中，如果只对字母加密（注意这个前提），
则每个字母都对应一个数字（字母a~z分别对应数字0~25）。

密钥为：$0\sim25$之间的数字对$(a,b)$。
其中$a$与$26$的最大公约数必须为$1$，$\gcd(𝑎, 26) = 1$
即$a$与$26$互素。

e.g.

$a = 5$就可以，
因为只有$1$能整除$5$和$26$，$\gcd(5, 26) = 1$。

$a = 2$就不可以，
因为$\gcd(2, 26) = 2$。

记：$p$为明文字母对应的数字，$c$为密文字母对应的数字。

• 加密算法为： $$c \equiv a \cdot p + b \pmod{26}$$

  需要注意是计算完$a \cdot p + b$再取模。
  也就是代码为(a*p+b)%26，而不是a*p+(b%26)。

• 解密算法为： $$p \equiv a^{-1} \cdot (c-b) \pmod{26}$$ 其中$a^{-1}$代表$a$的逆元。

特别的：当$a=1$时，这种加密方法就是凯撒加密，其中$b$就是偏移量。

需注意这种方法的加密对象也可能包括数字等其他符号。

其实前面的加密方法也可以包括其他字符。

比如凯撒加密，只需要把012接在xyz后面参与加密即可。

如加密方式为+2，
则明文abc xyz 012 789，加密为cde z01 234 9ab。

不过前面的加密方式一般均为字母，
而仿射加密则有可能包含数字（如后面的例题）。

只需要把其他字符也对应一个相应的编号即可。

甚至可以就用ASCII码表，就可以加密所有ASCII表中的字符了。

e.g.

对于a这个字符，转化为数字97，
假设通过加密算法运算，得到结果为33，转化为字符!。
则将a加密为!。

对于7这个字符，转化为数字55,
假设通过加密算法运算，得到结果为83，转化为字符S。
则将7加密为S。

那么对于字符串Nico2333...，
其中所有的字符都可以加密，而不只是针对字母加密，
加密结果如6$Ja8www(((。

然后对于要加密的字符表中，总字符个数为$m$个，
那么$a$和$b$的取值范围$0 \sim (m-1)$，满足$\gcd(a,m)=1$
同时模数为$m$。

因此真正加密算法应该是： $$c \equiv a \cdot p + b \pmod m$$ 其中$m$代表字符个数，
$a∈(0,m-1), b∈(0,m-1)$，且需满足$\gcd(a,m)=1$。

• 类型：单表替代加密。
• 加密对象：字母、数字等均可。
• 加密方式：将每个符号转换为数字$p$后，通过公式计算$c \equiv a \cdot p + b \pmod{26}$，再将$c$转换为对应符号。
• 安全性：较差。
  若加密对象只为字母，且为一层仿射加密，则情况数为$12\times26 - 1 = 311$种，也可以枚举得到。
  若情况种数较多，仍可能通过密码分析破译出密码。

方法原理

逆元求解

对于逆元的求解，Python中有两个函数可以求解。

1. 可以用Python的第三方库gmpy2的invert函数。

   from gmpy2 import invert
   ans = invert(5, 26) # 表示求5对模数26的逆元。ans = 21
   print(ans)
   # 21
   

   gmpy2包的安装方法可查看"osc_e45irv7l"的「python3安装gmpy2」文章。

2. 可以用Python的第三方库Crypto的inverse函数。

   from Crypto.Util.number import *
   ans = inverse(5, 26) # 表示求5对模数26的逆元。ans = 21
   print(ans)
   # 21
   

   Python3中Crypto库安装可以输入命令pip install pycryptodome

两者区别在于：
对于逆元的求解，两数必须互素。

如果输入的两参数不互素，
gmpy2的invert函数会使程序报错，
而Crypto的inverse不会，其会返回一个很怪的结果【是先将两参数除掉一个最大公约数让其互素，再返回结果……

加密脚本

from string import ascii_lowercase
table = ascii_lowercase # 定义字符集
MOD = len(table) # 确定模数m

def Encrypt(Plaintext, A, B): # 加密函数
    Ciphertext = ""
    for i in Plaintext:
        if i not in ascii_lowercase:
            Ciphertext += i
        else:
            rawIndex = table.find(i) # 先将字符转换为数字编号
            cipherIndex = (rawIndex * A + B) % MOD # 加密函数计算
            Ciphertext += table[cipherIndex]
    return Ciphertext

爆破脚本

首先由于状态数少，所以可以枚举爆破。

并且我们知道答案格式的开头为flag，
所以可以只查找爆破结果为flag开头的字符串输出，得到正确答案。

from Crypto.Util.number import *
from string import ascii_lowercase

table = ascii_lowercase # 定义字符集
MOD = len(table) # 确定模数m

def crack(): # 爆破a、b函数
    for A in range(MOD):
        for B in range(MOD):
            if (A*table.find("f")+B) % MOD == table.find(Ciphertext[0]):
            # 按当前a、b加密f字符后，与密文第一位相同
                if (A*table.find("l")+B) % MOD == table.find(Ciphertext[1]):
                # 按当前a、b加密l字符后，与密文第二位相同。【后两句if类推
                    if (A*table.find("a")+B) % MOD == table.find(Ciphertext[2]):
                        if (A*table.find("g")+B) % MOD == table.find(Ciphertext[3]):
                            # flag均匹配，证明就为当前a、b
                            return (A, B)

def Decrypt(Ciphertext, A, B): # 解密函数
    Plaintext = ""
    inv = inverse(A, MOD) # 求得A对Mod的逆元
    for i in Ciphertext:
        if i not in table:
            Plaintext += i
        else:
            rawIndex = table.find(i) # 先将字符转换为数字编号
            plainIndex = (rawIndex - B) * inv % MOD # 解密函数计算
            Plaintext += table[plainIndex]
    return Plaintext

如果为其他格式开头，相应修改即可。

例题

对于字符串vjsg{dckvzksr}，
其采用了单层仿射加密，字符集为小写字母，
请解密出flag。

已知最终flag为纯数字。

加密过程

可以先尝试解题，
没有思路再根据加密过程得到思路。

加密过程

from string import digits, ascii_lowercase
from secret import numbers, A, B
table = ascii_lowercase # 定义字符集
MOD = len(table) # 确定模数m

assert min([i in digits for i in numbers]) # 验证flag格式正确，不用管

print("numbers =", numbers)

flag = "flag{"+"".join([ascii_lowercase[int(i)] for i in numbers])+"}"
print("flag =", flag)

assert numbers == "".join([str(ascii_lowercase.find(i)) for i in flag[5:-1]]) # 验证flag格式正确，不用管

def Encrypt(Plaintext, A, B): # 加密函数
    Ciphertext = ""
    for i in Plaintext:
        if i not in ascii_lowercase:
            Ciphertext += i
        else:
            rawIndex = table.find(i) # 先将字符转换为数字编号
            cipherIndex = (rawIndex * A + B) % MOD # 加密函数计算
            Ciphertext += table[cipherIndex]
    return Ciphertext

print("Ciphertext =", Encrypt(flag, A, B))

运行结果：

其中的最终flag为flag{18453407}。

---

由代码分析可知，
程序先从secret库中得到flag的数字部分。

然后把数字按照位置转换为字母。

e.g.

将数字0转换为a。
将数字1转换为b。
将数字2转换为c。

最后再用secret库中的A和B，
对flag进行仿射加密，得到密文。

解题过程

知道加密方式为一层仿射加密，且字符集为小写字母。
flag的开头格式为flag。

则可使用爆破脚本。

from Crypto.Util.number import *
from string import ascii_lowercase

Ciphertext = "vjsg{dckvzksr}" # 在这里输入密文

table = ascii_lowercase # 定义字符集
MOD = len(table) # 确定模数m

def crack(): # 爆破a、b函数
    for A in range(MOD):
        for B in range(MOD):
            if (A*table.find("f")+B) % MOD == table.find(Ciphertext[0]):
            # 按当前a、b加密f字符后，与密文第一位相同
                if (A*table.find("l")+B) % MOD == table.find(Ciphertext[1]):
                # 按当前a、b加密l字符后，与密文第二位相同。【后两句if类推
                    if (A*table.find("a")+B) % MOD == table.find(Ciphertext[2]):
                        if (A*table.find("g")+B) % MOD == table.find(Ciphertext[3]):
                            # flag均匹配，证明就为当前a、b
                            return (A, B)

def Decrypt(Ciphertext, A, B): # 解密函数
    Plaintext = ""
    inv = inverse(A, MOD) # 求得A对Mod的逆元
    for i in Ciphertext:
        if i not in table:
            Plaintext += i
        else:
            rawIndex = table.find(i) # 先将字符转换为数字编号
            plainIndex = (rawIndex - B) * inv % MOD # 解密函数计算
            Plaintext += table[plainIndex]
    return Plaintext

A,  B = crack()
print("A = {}, B = {}".format(A, B))

flag = Decrypt(Ciphertext, A, B)
print(flag)

print("".join([str(ascii_lowercase.find(i)) for i in flag[5:-1]]))

运行结果：

得到最终flag为flag{18453407}。

0x05 单表替代密码分析

定义

之前的三种加密算法，均为单表替代加密。
也就是一个字母与一个字母一一对应的关系。

单表替代加密无论过程如何，
最终都形成了一张密码表，
加密解密都通过查表来进行。

因此如果我们不知道具体采用什么加密方法，
就只需要知道哪个字母对应哪个字母，
分析出一张“密码表”，
就能对单表替代加密的密文进行解密了。

这种分析过程就是单表替代密码分析。
采用分析，甚至可以不用知道密钥是什么，就可以直接得到明文。

分析方法

如果暴力枚举分析得到密码表，
则情况数为$26\times25\times24\times\cdots\times2\times1 = 26! = 403291461126605635584000000$。
因此除非加密方法简单，否则几乎不可能通过枚举得到密码表。

基本分析方法有三种：

• 词频分析
• 双联分析
• 模式匹配

将三种分析方法综合运用，找出可能性最大的结果。

词频分析

下图为单个英文字母在文章中出现的频率：

我们对于一串较长密文（如对文章加密），统计每个字母出现的频率。
如果发现某一字母与上表字母的频率接近，
则两字母应该是对应关系。

e.g.

分析后若得到密文中字母X的频率接近为$10.39%$，接近$10.47%$。
因此可以推测密文X对应明文T。

双联分析

词频分析是针对单个字母进行分析，
同时英语单词中也有很多连续的两字母出现频率很高，
称作双联字母(bigrams)。

因此可以用双联分析来辅助我们进行分析。

下表为1000个单词中，各双联字母出现次数。

模式匹配

另外，如果有一个较大的单词库，
还可以通过单词的格式，进一步帮助我们缩小可能的范围。

e.g.

单词happy，为12334格式，
单词success，为1233411格式。

那么被进行单表替换后，它的格式并不会发生改变。

这种模式匹配的优点在于：
即使密文长度较短，也能尽可能找到接近真相的结果。

工具：
利用模式匹配尝试解密单表替代加密的网站。

0x06 维吉尼亚加密

维吉尼亚密码是使用一系列凯撒密码组成密码字母表的加密算法，属于多表密码。

为了生成密码，需要使用密码表。
这一密码表包括了26行字母表，每一行都由前一行向左偏移一位得到。

具体使用哪一行字母表进行加密是基于密钥进行的，
在过程中会不断地变换。

• 类型：多表替代加密。
• 加密对象：一般为字母。
• 加密方式：根据密钥依次查表替换，得到密文。
• 安全性：较强。
  多表加密中，对于两个相同的字符，并不一定都会加密为两个相同的字符。
  如第一个a可能加密为g，但第二个a可能加密为o。
  所以能避免直接的词频分析攻击。
  必须要知道密钥才能得到明文。

加密过程

首先有一串明文和一串密钥，
其中密钥长度要小于明文。

e.g.

明文为SUPERSASSW，
密钥为NICO。

1. 将密钥调整到跟明文一样的长度。
   操作方法为不断重复密钥。

   调整后密钥为NICONICONI。

2. 通过等长的明文和密钥，
   将明文作为列标，密钥作为行标（也可能反之），
   依次查表，得到密文。

   如第一位：
   明文为S，密钥为N，
   对应表的N行S列，则密文为F。

一位位查表完成后，
得到密文为：FCRSEACGFE。

可以明显发现：
明文中四个同样的S，
被分别加密为不同的F、A、G、F。

由于明文与密文并不为一一对应关系，
所以可以避免直接的词频分析攻击。

解密过程

解密的过程就是加密过程反过来。

e.g.

密文FCRSEACGFE，密钥为NICO。

调整密钥为与密文等长字符串为NICONICONI。

根据密钥第一个字母F所对应的N行字母表，
发现密文第一个字母F位于S列，
因而明文第一个字母为S。

密钥第二个字母C对应I行字母表，
而密文第二个字母C位于此行U列，
因而明文第二个字母为U。

以此类推便可得到明文。

破解方法

1. 分析长度

为了传输方便，一般来说密钥都很短小，
所以密钥会重复，以达到明文的长度。

首先提出破解方法的"Frederick Kasiski"是基于这样一个简单的观察：
“密钥的重复部分与明文中的重复部分的连接，在密文中也产生一个重复部分”。

如果一个字符串在明文中重复，并且被密钥相同的部分加密，那么在密文中也会出现重复的字符串。

密文中出现的重复字符串的前后长度，则是关键词长度的倍数。
密文中出现足够多次，就可以根据这几个长度的倍数，来确定真实的长度。

e.g.

$(9,6)$的公约数只有$1$和$3$，
而$1$不可能为密钥长度（否则变为单表加密），
故密钥长度则为$3$。

2. 转化为单表加密问题

找到密钥的长度$n$后，
则多表加密的问题便可以转化为$n$个单表加密的问题。

e.g.

如上例。

找到长度为$n=3$后，
则对于从左往右第$1$、$4$、$7$、$\cdots$位，运用的都是同一种单表加密方式。
同理：对于第$2$、$5$、$8$、$\cdots$位，和$3$、$6$、$9$、$\cdots$位，也是另一种单表加密。

对每一种单表加密逐个分析，得到部分明文，
最终就能得到整个明文。

0x07 替换和编码

古典加密还包含很多种形式的简单替换和编码。
这些替换也常常出现Misc中，如：

• Morse电码
• 敲击码
• 福尔摩斯跳舞的小人
  

  

• 培根密码
  

  

有关编码内容可以阅读Misc部分的数据编码笔记。

类型和编码

• 密码学中数字主要研究整数。

类型转换

整数进制转换

x = 123456 # 十进制整数

x_hex = hex(x)[2:] # 十进制转十六进制
print("hex:",x_hex)
# hex: 1e240

x_bin = bin(x)[2:] # 十进制转二进制
print("hex:",x_hex)
# bin: 11110001001000000

# x_hex与x_bin均为字符串类型

x_a = int(x_hex, 16) # 十六进制转十进制
print(x_a)
# 123456

x_b = int(x_bin, 2) # 二进制转十进制
print(x_b)
# 123456

字符串类型转换

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

字符串类型是纯文本类型。

而字节类型是二进制数据。
表示为b'...'，其中...为可读表示方法。

s = "flag{qwqqqOrzzz}" # 字符串类型

s_bytes = s.encode() # 字符串类型转字节类型
print(s_bytes)
# b'flag{qwqqqOrzzz}'

s_str = s_bytes.decode()
print(s_str)
# flag{qwqqqOrzzz}

整数和字节类型转换

这种类型转换在密码方向题目中很常见。
【但个人刚入门，暂时不知道转换为整数类型有什么用，等以后见识到了再补充_(:з」∠)_……

整数类型可以直接参与数学计算，
字节类型会展示可读的字符。

from Crypto.Util.number import *

s = b'flag{this_is_flag}' # 字节类型

s_int = bytes_to_long(s) # 字节类型转为整数
print(s_int)
# 8922333133093133239960474404255406756030333

s_bytes = long_to_bytes(s_int) # 整数转字节类型
print(s_bytes)
# b'flag{this_is_flag}'

编码

Base64编码

import base64

s = b'flag{this_is_flag}' # 字节类型

s_encode = base64.b64encode(s) # 进行base64编码
print(s_encode)
# b'ZmxhZ3t0aGlzX2lzX2ZsYWd9'

s_decode = base64.b64decode(s_encode) # 进行base64解码
print(s_decode)
# b'flag{this_is_flag}'

0x08 写在最后

这部分涉及到数论的知识，故可能会感觉有点难……
个人刚好为了学ACM数论知识点，补了ACM方面的笔记，算是一举两得2333……

感谢Am473ur师傅的辛勤付出！……

以上……