前置知识

对称密码：通信双方使用相同的密钥。

公钥密码：通信双方使用不同的密钥，又称为“非对称密码”。

对称加密

我们设$M$为明文空间，$K$为密钥空间，$C$为密文空间。
设$(E,D)$为对称加密方案，$E$为加密算法（Encrypt），$D$为解密算法（Decrypt）。

加密算法需要有两个输入：一个是要加密的明文$m$，另一个为密钥$k$。
解密算法也要有两个输入：一个是要解密的密文$c$，另一个为密钥$k$。

为了保证解密正确性，对于对称加密方案$(E,D)$，需要满足$m=D(k,E(k,m))$

完善保密性

如果$\forall m_0,m_1\in M(|m_0|=|m_1|),\forall c\in C$，得到：（$Pr[…]$为概率）

那么$(E,D)$有完善保密性，其中$k\in K$随机。

简单来说，给定一个任意密文$c$，每个明文加密成$c$的概率相等，攻击者只窃听到密文无法知道对应的明文。密文不会泄露明文的任何信息。

特点：

1.唯密文攻击（Ciphertext Only Attack，指仅知密文的情况下进行攻击）无效。
2.消息长度相等（$|m_0|=|m_1|$）。

一次一密

一次一密（OTP，One-time pad）满足完善保密性，极其简单。

对于比特串形式（信息编码后转化为二进制存储）的密文明文，密钥为随机的。加密时，明文和密钥逐比特异或可得到密文，解密时，密文和密钥逐比特异或可得到明文。

[UTCTF2020]OTP

1
2
3
4
5
6
7
8
Encoded A: 213c234c2322282057730b32492e720b35732b2124553d354c22352224237f1826283d7b0651
Encoded B: 3b3b463829225b3632630b542623767f39674431343b353435412223243b7f162028397a103e

Original A: 5448452042455354204354462043415445474f52592049532043525950544f47524150485921
Original B: 4e4f205448452042455354204f4e452049532042494e415259204558504c4f49544154494f4e

A XOR A: 7574666c61677b7477305f74696d335f703464737d7574666c61677b7477305f74696d335f70
B XOR B: 7574666c61677b7477305f74696d335f703464737d7574666c61677b7477305f74696d335f70

既然题目说是用了一次一密，A和B应该是无关的两组数据，那么flag就与AB分别进行了异或：

所以，事实上我们只需要将AB两组任选一组异或一次即可，不过题目已经很贴心的给出了异或结果。此外，我还看到了熟悉的666c6167：

1
2
3
4
5
from Crypto.Util.number import *

X='7574666c61677b7477305f74696d335f703464737d7574666c61677b7477305f74696d335f70'
print(long_to_bytes(int(X,16)))
#b'utflag{tw0_tim3_p4ds}utflag{tw0_tim3_p'

多次一密

一次一密尽管满足无条件安全，但是需要一次性的密钥，且存在密钥分发问题，效率太低，引入多次一密（Many Times Pad），思路就是多次使用同一个较短的密钥。

De1CTF XORZ

1
2
3
4
5
6
7
8
9
10
11
12
13
from itertools import *
from data import flag,plain

key=flag.strip("de1ctf{").strip("}")
assert(len(key<38))
salt="WeAreDe1taTeam"
ki=cycle(key)
si=cycle(salt)
cipher = ''.join([hex(ord(p) ^ ord(next(ki)) ^ ord(next(si)))[2:].zfill(2) for p in plain])
print cipher

# output:
# 49380d773440222d1b421b3060380c3f403c3844791b202651306721135b6229294a3c3222357e766b2f15561b35305e3c3b670e49382c295c6c170553577d3a2b791470406318315d753f03637f2b614a4f2e1c4f21027e227a4122757b446037786a7b0e37635024246d60136f7802543e4d36265c3e035a725c6322700d626b345d1d6464283a016f35714d434124281b607d315f66212d671428026a4f4f79657e34153f3467097e4e135f187a21767f02125b375563517a3742597b6c394e78742c4a725069606576777c314429264f6e330d7530453f22537f5e3034560d22146831456b1b72725f30676d0d5c71617d48753e26667e2f7a334c731c22630a242c7140457a42324629064441036c7e646208630e745531436b7c51743a36674c4f352a5575407b767a5c747176016c0676386e403a2b42356a727a04662b4446375f36265f3f124b724c6e346544706277641025063420016629225b43432428036f29341a2338627c47650b264c477c653a67043e6766152a485c7f33617264780656537e5468143f305f4537722352303c3d4379043d69797e6f3922527b24536e310d653d4c33696c635474637d0326516f745e610d773340306621105a7361654e3e392970687c2e335f3015677d4b3a724a4659767c2f5b7c16055a126820306c14315d6b59224a27311f747f336f4d5974321a22507b22705a226c6d446a37375761423a2b5c29247163046d7e47032244377508300751727126326f117f7a38670c2b23203d4f27046a5c5e1532601126292f577776606f0c6d0126474b2a73737a41316362146e581d7c1228717664091c

根据题目有：

flag是求出key，题目已经告诉我们salt的值了，换一下位置：

首先，我们对key长度是未知的，明文应该全是可见字符，猜测key的内容应该也为可见字符。能不能有一种方法可以求得key的长度呢？

可以对密文按照假定的key长度分组，如果key长度为3的话，应该分组为：

1
2
3
[0,3,6,9...]
[1,4,7,10...]
[2,5,8,11...]

我们对组内每个元素异或所有的可见字符，将结果所有可见字符放入集合求交集，结果不为空那么说明长度正确。

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
from Crypto.Util.number import *
from Crypto.Util.strxor import strxor
from string import printable

keytable = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_"
ci = "49380d773440222d1b421b3060380c3f403c3844791b202651306721135b6229294a3c3222357e766b2f15561b35305e3c3b670e49382c295c6c170553577d3a2b791470406318315d753f03637f2b614a4f2e1c4f21027e227a4122757b446037786a7b0e37635024246d60136f7802543e4d36265c3e035a725c6322700d626b345d1d6464283a016f35714d434124281b607d315f66212d671428026a4f4f79657e34153f3467097e4e135f187a21767f02125b375563517a3742597b6c394e78742c4a725069606576777c314429264f6e330d7530453f22537f5e3034560d22146831456b1b72725f30676d0d5c71617d48753e26667e2f7a334c731c22630a242c7140457a42324629064441036c7e646208630e745531436b7c51743a36674c4f352a5575407b767a5c747176016c0676386e403a2b42356a727a04662b4446375f36265f3f124b724c6e346544706277641025063420016629225b43432428036f29341a2338627c47650b264c477c653a67043e6766152a485c7f33617264780656537e5468143f305f4537722352303c3d4379043d69797e6f3922527b24536e310d653d4c33696c635474637d0326516f745e610d773340306621105a7361654e3e392970687c2e335f3015677d4b3a724a4659767c2f5b7c16055a126820306c14315d6b59224a27311f747f336f4d5974321a22507b22705a226c6d446a37375761423a2b5c29247163046d7e47032244377508300751727126326f117f7a38670c2b23203d4f27046a5c5e1532601126292f577776606f0c6d0126474b2a73737a41316362146e581d7c1228717664091c"
s = b"WeAreDe1taTeam"

ci = bytes.fromhex(ci)
c = strxor(ci,(s*((len(ci)//len(s))+1))[:len(ci)])

def bruce_printable(s):
	TMP = set()
	for each in printable:
		tmp = chr(ord(each)^s)
		if tmp in keytable:
			TMP.add(tmp)
	return TMP


for k_len in range(1,38):
	candidates = []
	for j in range(k_len):
		block = [c[k_len*i+j] for i in range(len(c)//k_len)]
		candidate=set()
		init = True
		for eachbyte in block:
			tmp_candidate=bruce_printable(eachbyte)
			if init:
				candidate = tmp_candidate
				init = False
			else:
				candidate &= tmp_candidate
		if candidate:
			candidates.append(candidate)
	print(len(candidates))
	if k_len == len(candidates):
		print("[+]",k_len)

这里是对集合set进行了求交集运算，使用了&，类似的还有求并集|，求差集-。

发现key的长度为30，在接下来的运算中就可以进行30的分组，接下来可以挨个爆破key的每个字节，分组后的每组都和所有的可见字符异或，解密后如果都是可见字符，那么这个字符可能就是正确的字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
keytable = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_\'` ;,."

k_len = 30
key_candidates=[]
for j in range(k_len):
	block = [c[k_len*i+j] for i in range(len(c)//k_len)]
	keyi_candidate = []
	for keyi in keytable:
		for eachbyte in block:
			if chr(ord(keyi)^eachbyte) not in keytable:
				break
		else:
			keyi_candidate.append(keyi)
	if not keyi_candidate:
		print("[-] error")
		exit()
	key_candidates.append(keyi_candidate)
print(key_candidates)

我们在得到的可能结果中找到一种能构成有意义的结果的答案，得到：W3lc0m3tOjo1nu55un1ojOt3m0cl3W。

流密码

流密码又叫序列密码，属于对称密码，原理：利用一个伪随机数生成器将短密钥加工成长密钥（密钥流），再将明文和密文逐比特异或即可得到密文，将密文和密钥逐比特异或课得到明文。

既保留了一次一密加解密简单高效的优点，又克服了必须使用长密钥的不实用性。

分组密码和流密码的区别就是有无记忆性。

有限状态自动机

有限状态自动机是具有离散输入和输出的一种模型，由有限状态集、有限输入字符集、优先输出字符集、转移函数组成。

伪随机数生成器

伪随机数生成器（PRG，pseudo-random generator），由于电脑本身无法产生真正的随机序列，只能按照算法生成伪随机序列，这个序列一般是循环周期极长并且能通过随机数检验，而且和真随机序列区分不开，所以叫做伪随机。

例如：我们设$G$是一个高效的确定性函数：

那么可以说$G$是一个PRG，其输入我们称之为种子，输入空间被称为种子空间（$\{0,1\}^s$）。

所以，我们可以定义让$(E,D)$为定义在$(K,M,C)$上的流密码：

不难发现，流密码实质就是一次一密基础上的改造和优化。

在密码学里，很多地方我们需要用到随机数：

key的生成、初始化向量、IV、块加密的CBC,CFB,OFB模式等、OTP……

反馈移位寄存器

寄存器能储存二进制代码，可以理解为一种逻辑电路，由具有存储1位二进制代码的触发器组合起来形成。

存放n位二进制代码的寄存器需要n个触发器构成。

由于异或算法的特点，如果多个数据使用同一个密钥串进行加密，攻击者就不需要猜测密钥串来破解数据：

假如AB为明文，C为密钥：

根据上面的计算，如果多个数据使用同一个密钥串进行加密，攻击者仅需要再提供一个数据，并且通过相同的方式进行加密，获取对应加密后的数据，即可通过异或关系解密想要破解的数据：

所以在流加密中，对密钥的安全性要求大，通常的做法是每次发送数据都生成一个随机数列作为密钥流，并且该密钥流不能过短以至于可被暴力破解。这里我们就需要用到反馈移位寄存器，下图展示了一个n级的反馈移位寄存器：

F我们可以称为反馈函数，如果F为线性函数，称其为线性反馈移位寄存器（LFSR），否则称为非线性反馈移位寄存器（NFSR）。

有关LSFR的知识，单独开一篇文章讲。

在现实通信中，常常使用线性反馈移位寄存器来生成“伪随机”密钥流。

一般来说，反馈移位寄存器都会定义在某个有限域上，从而避免数字太大和太小的问题。

现实生活中分组密码的应用范围比流密码更加广泛，但是分组密码也可以用五种加密方式（ECB,CBC,CFB,OFB,CTR）来构造流密码。