mozhucy's blog.

深入浅出密码学读书笔记

字数统计: 1.1k阅读时长: 4 min
2018/11/26 Share

替换密码 (11.16)

  • 这个在古典密码中比较常见,属于对称加密,那么攻击替换密码时有两种方式,一种是穷举,这个在秘钥可能性比较少的时候可以使用.还有一种攻击方式就是词频分析,替换密码映射的规律导致了明文的统计规律能被很好的保存在密文中,如果我们有足够多的密文,那么就可以利用词频统计来进行替换密码的攻击,词频分析时,还可以遵循一些常见的特性.如E是出现频率最高的字母,英语中U总是跟在Q后面,或者一些高频符号” “以及高频短单词THE AND等.

现代密码重要的一项运算-模运算

  • 模运算: a,r,m属于Z,且m > 0.如果m 除 a-r可以记做a === r mod m,m称作模数,r为余数
  • 对于给定的模数m和整数a,可能存在无限多个有效的余数.例如a = 12,m = 9时,我们可以得到 12 === 3 mod 9,12 === 21 mod 9…..因为9|(12 - 3),这里引出等价类的概念,x|y即x除y的操作背后是一个系统.整数级{….,-24,-15,-6,3,12,21,30,….}构成了一个等价类,同理模数9还有8个等价类
  • 等价类中的成员行为等价,利用这个性质可以简化模运算,例如计算3^17mod5,可以拆成(3 3)*(3 3)(3 ** 3)(3 3)*(3 3)*(3 ** 2),进而化简为128mod5,化简为8mod5,得到3
  • 一般余数r的选择范围是 0 <= r <= m - 1.这里引入环的概念,环由两部分组成,集合Zm = {0,1,2,3,…,m - 1},两种操作”+”,”x”使得对所有a,b属于Zm都有 a+b === c mod m,a*b === d mod m,其中c,d属于Zm
  • 如果两个数相加/乘的结果都在环内,则程该环为封闭环,

序列密码和分组密码

  • 序列密码单独加密每个位,序列密码还可以分为同步序列密码和异步序列密码,同步密码的密码顺序仅仅取决于秘钥,异步密码的密码顺序取决于秘钥和密文
  • 异步密码其实就是一个流加密

OTP

  • 当密钥被同时异或加密了多个密文时,会发生c1 = m1 xor key,c2 = m2 xor key,这个时候我们将c1,c2互相异或,就会得到两串英文互相异或的结果m1 xor m2,当样本足够多的时候,便能根据其中的规律统计出m1 - mn,进而反求出key,最后利用key解密密文,是唯密文攻击的一种
  • 那么一般根据什么规律呢
1
2
3
for i in range(65,89):
for j in range(65,89):
print i^j
  • 可以看到由于异或运算的特性,ascii码过于接近的互相异或以后都是很小的值,而且这些值大多数都处在不可见字符区域,而两串密文异或以后,就是两个字符串的异或,由于空格等标点的存在,所以异或以后会存在一些可见字符范围内的,数据量足够的情况下,便可以利用统计出的下标对应,如果大于一个比较接近全体样本数据的数字,那么加入到可疑空格的位置
  • 将样本中的空格统计结束以后,便可以进行密钥位的反求,最后进行解密
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
import string

def strxor(a, b): # xor two strings (trims the longer input)
return "".join([chr(ord(x) ^ ord(y)) for (x, y) in zip(a, b)])

ciphers = ['daaa4b4e8c996dc786889cd63bc4df4d1e7dc6f3f0b7a0b61ad48811f6f7c9bfabd7083c53ba54',
'c5a342468c8c7a88999a9dd623c0cc4b0f7c829acaf8f3ac13c78300b3b1c7a3ef8e193840bb',
'dda342458c897a8285df879e3285ce511e7c8d9afff9b7ff15de8a16b394c7bdab920e7946a05e9941d8308e',
'd9b05b4cd5ce7c8f938bd39e24d0df191d7694dfeaf8bfbb56e28900e1b8dff1bb985c2d5aa154',
'd9aa4b00c88b7fc79d99d38223c08d54146b88d3f0f0f38c03df8d52f0bfc1bda3d7133712a55e9948c32c8a',
'c4b60e46c9827cc79e9698936bd1c55c5b6e87c8f0febdb856fe8052e4bfc9a5efbe5c3f57ad4b9944de34',
'd9aa5700da817f94d29e81936bc4c1555b7b94d5f5f2bdff37df8252ffbecfb9bbd7152a12bc4fc00ad7229090',
'c4e24645cd9c28939a86d3982ac8c819086989d1fbf9f39e18d5c601fbb6dab4ef9e12795bbc549959d9229090',
'd9aa4b598c80698a97df879e2ec08d5b1e7f89c8fbb7beba56f0c619fdb2c4bdef8313795fa149dc0ad4228f',
'cce25d48d98a6c8280df909926c0de19143983c8befab6ff21d99f52e4b2daa5ef83143647e854d60ad5269c87',
'd9aa4b598c85668885df9d993f85e419107783cdbee3bbba1391b11afcf7c3bfaa805c2d5aad42995ede2cdd82977244',
'e1ad40478c82678995df809e2ac9c119323994cffbb7a7b713d4c626fcb888b5aa920c354be853d60ac5269199',
'c4ac0e53c98d7a8286df84936bc8c84d5b50889aedfebfba18d28352daf7cfa3a6920a3c',
'd9aa4f548c9a609ed297969739d18d5a146c8adebef1bcad11d49252c7bfd1f1bc87152b5bbc07dd4fd226948397',
'c4a40e698c9d6088879397d626c0c84d5b6d8edffbb792b902d49452ffbec6b6ef8e193840',
'c5ad5900df8667929e9bd3bf6bc2df5c1e6dc6cef6f2b6ff21d8921ab3a4c1bdaa991f3c12a949dd0ac5269c']

target_cipher = "c2967e7fc59d57899d8bac852ac3c866127fb9d7f1e5b68002d9871cccb8c6b2aa".decode("hex")

key = [0]*100

for i in range(len(ciphers)):
flag = [0] * len(ciphers[i].decode("hex"))
for j in range(len(ciphers)):
if i != j:
# print strxor(ciphers[i].decode("hex"),ciphers[j].decode("hex"))
for index,c in enumerate(strxor(ciphers[i].decode("hex"),ciphers[j].decode("hex"))):
if c.isalpha():
flag[index] += 1

space = []
for k in range(len(flag)):
if flag[k] > 8:
space.append(k)
print space
spacexor = strxor(ciphers[i].decode("hex")," "*len(ciphers[i].decode("hex")))
for k in space:
key[k] = ord(spacexor[k])

print key
flag = ""
for i in range(len(target_cipher)):
if(key[i] != 0):
flag += chr(key[i] ^ ord(target_cipher[i]))
else:
flag += "?"
print flag
CATALOG
  1. 1. 替换密码 (11.16)
  2. 2. 现代密码重要的一项运算-模运算
  3. 3. 序列密码和分组密码
  4. 4. OTP