密码学 从入门到放弃 古典密码

发表于 分类于 阅读次数：

XMan Day2，整理一下bibi师傅的笔记。

古典密码部分。

古典密码学通常可以拿到加密算法【否则要么脑洞要么就是特征明显的题，且大部分是唯密文攻击。

前情提要介绍一下编码

编码

编码是为了传输方便以及协议中的格式统一。

HEX

  • 实际存储内容的16进制表示。
  • 冗余：1：2【1个byte会变成2个bytes进行存储。
  • 识别：只存在0-9，A-F，a-f。
  • 一般用处：可作为各类编码转换的过渡，最常见的是str和int的转换。

Base家族

  • Base64/32/16：用64/32/16种bytes表示所有的bytes。
  • 越多的可见字符数来表现其他所有的字符越节省空间。
  • Base16==hex【使用特定的16个字符表达所有的字符，24→28。
  • Base64【base32同理，使用特定的64个字符表达所有的字符， 26→28。
  • 单个字符取前六个bits根据编码表转码，后两位bits归入下一个字符。

例题

当Base64的表被替换，该如何编码解码。

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
# /usr/bin/python
# encoding: utf-8
base64_table = ['=', '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', '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',
                '+', '/'][::-1]


def encode_b64(s):
    l = len(s)
    i = 0
    result = ''
    while i < l:
        # 将字符转换为二进制编码，然后对齐
        s1 = s[i]
        b1 = bin(ord(s1))[2:]
        cb1 = b1.rjust(8, '0')
        i += 1
        if i >= l:
            cb2 = '00000000'
        else:
            s2 = s[i]
            b2 = bin(ord(s2))[2:]
            cb2 = b2.rjust(8, '0')
        i += 1
        if i >= l:
            cb3 = '00000000'
        else:
            s3 = s[i]
            b3 = bin(ord(s3))[2:]
            cb3 = b3.rjust(8, '0')
        # 将三字节转换为四字节
        cb = cb1 + cb2 + cb3
        rb1 = cb[:6]
        rb2 = cb[6:12]
        rb3 = cb[12:18]
        rb4 = cb[18:]
        # 转换后的编码转为十进制备用
        ri1 = int(rb1, 2)
        ri2 = int(rb2, 2)
        ri3 = int(rb3, 2)
        ri4 = int(rb4, 2)
        # 处理末尾为０的情况，以＇＝＇填充
        if i - 1 >= l and ri3 == 0:
            ri3 = -1
        if i >= l and ri4 == 0:
            ri4 = -1
        result += base64_table[ri1] + base64_table[ri2] + base64_table[ri3] + base64_table[ri4]
        i += 1
    return result


print encode_b64(open("flag", "r").read())
# output: mZOemISXmpOTkKCHkp6Rgv==

两种思路，一是自己实现一个base64的解密算法来解，二是替换原表中的字符来恢复正常的编码，这儿列出第二种解题脚本。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
base64_table = ['=', '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', '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',
                '+', '/'][::-1]

old_base64_table = ['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', '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', '+', '/', '=', ]
res = ""
for i in "mZOemISXmpOTkKCHkp6Rgv==":
    res += old_base64_table[base64_table.index(i)]

print(res)

其他

还有URLencode、morsecode、jsfuck、uuencode、Xxencode、Unicode编码、Escape/Unescape编码、HTML实体编码等诸多编码，挖坑待补充。

古典密码

移位密码

仅对密文的排列顺序进行变化。

简单移位

将密文以数字k的长度4进行分组，后按k的排列顺序排列密文，而攻击方法为肉眼识别、爆破秘钥、根据flag字符串逆推。

曲路密码

一般是将明文填入一个表中，并按照一定的曲路遍历，攻击方法只需逆向遍历。

云影密码

仅包含01248，以0分割，其他数字取和后按照26字母表转化。

栅栏密码

秘钥只有一个k，表示栅栏长度。把密文按每组k个分组，循环k次，取每组第k个字符拼接。

替代密码

会变更密文。

单表替换

以下为特例，一般是以乱序表来替换，经典的单表替代密码就是用一个替代表对每一个位置的字符进行查表替换，词频分析可解。

凯撒密码

通过把字母在字母表上移动一定位数来实现加密解密，秘钥空间小，可直接爆破。

例题
1
2
3
4
5
6
7
8
9
10
11
12
def caesar_encrypt(m, k):
    r = ""
    for i in m:
        r += chr((ord(i) + k) % 128)
    return r


from secret import m, k

print caesar_encrypt(m, k).encode("base64")

# output:bXNobgJyaHB6aHRwdGgE

解法为爆破。

1
2
3
4
5
6
7
8
9
10
def caesar_encrypt(m, k):
    r = ""
    for i in m:
        r += chr((ord(i) + k) % 128)
    return r


m = "bXNobgJyaHB6aHRwdGgE"
for i in range(1, 129):
    print  caesar_encrypt(m.decode("base64"), i)
埃特巴什码

通过将字母表的位置完全镜面对称后获得字母的替代表进行加密，攻击方法为将其替代回去。

培根密码

AB表达两种字体，五个一组。类似二进制。

猪圈密码

图形替代密码，不做赘述。

仿射密码

依据公式c=am+b mod n来生成仿射密码的替代表。

  • m为明文对应字母得到的数字。
  • n为字符数量。
  • c为密文。
  • a、b为秘钥。

解密方法为求a关于n的逆元，公式m = modinv(a)(c-b) mod n，攻击方法有爆破、词频统计和已知明文攻击【如果知道一对(m,c)，那么知道a和b是简单的。

多表替换

维吉尼亚密码

秘钥不是固定不变的，随位置产生而改变，若密文为LOVE，则四个为一组进行循环加密。

词频统计

依赖在英语语言中字母的使用频率进行分析。

单表替换：统计所有字母频率，替换频率最近的。

多表替换：抽取使用相同替换表的所有密文，然后使用单表替换。

TWCTF2016 vigenere

先进行base64编码后维吉尼亚加密。

卡西斯基实验

若连续三个相同字母如ABC在密文中重复出现会是什么原因。

不同明文，不同秘钥：碰巧

相同明文，相同秘钥：如the经常连续出现，出现的间距的秘钥长度的倍数

解密方式为寻找重复出现的密文，求间距最大公约数。