前置知识

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

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

对称加密

我们设$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)来构造流密码。