仿射密码与希尔密码深度解析

Posted on | In ,
Words count in article: 3.3k | Reading time ≈ 14

前言

仿射密码和希尔密码是两个很有趣的古典密码，两者之间还有一定的联系。

本文想对仿射密码和希尔密码的加密解密进行深度解析，并附有精彩例题。之所以厚颜无耻地说是“深度解析”，是因为网络上的文章 🙂🙂🙂。

环境要求：

  1. gmpy2 （gmpy2 安装教程）
  2. numpy （pip install numpy）

仿射密码

仿射密码在 CTF-Wiki 中写得已经很精彩了，这里简练地回顾一下：

仿射密码原理

加密函数：$E(x)=(ax+b) \pmod m$
解密函数: $D(x)=a^{-1} (x-b) \pmod m$

密钥空间

字符集中 $m$ 往往是 26,（其实经常不是 🙂 ）
$(a, m) = 1$, 所以 $a \text{ 取值空间大小为 } \varphi (m) = 12$,
$b \in [0,26)$
密钥空间是 $26 \times 12 = 312 $
故，在已知部分明文的情况下才可以攻击!

破解方法

  1. 如果我们知道其中任意一个参数，那我们便可以很容易地快速枚举另外一个参数得到答案；
  2. 如果知道两个加密前后的字母也可以解密。

$$
y_1=(ax_1+b) \pmod {m}
\\
y_2=(ax_2+b) \pmod {m}
$$

两式相减：$y_1−y_2=a(x_1−x_2) \mod {26}$ 求得
$$
a = (y_1−y_2) * (x_1−x_2)^{-1} \mod{m}
\\
b = y_1 - ax_1 \mod {m}
$$

这样就求得了参数 a, b，然后用解密函数还原明文：
$$
Message = D(x)=a^{-1} (x-b) \pmod m
$$

字符集和模数的问题

刚刚其实偷偷说了，很多情况（指题目）字符集不是 “a-z” 或者 “A-Z” 这么简单，a/ A 并不一定代表 0，只是在教学的时候常常用这样的方式，毕竟 26 这个数字还是比较小的，爆破也很容易。
模数 m 很多时候也可以任性，不需要恰巧等于字符集的大小。比如，如果字符集的大小为 256，这个时候参数 a 的取值会比较困难。（之前说了，要满足 $(a, m) = 1$，否则无法求逆元，仿射密码本身存在问题）
而这也是密码学的一个小门槛，只会使用工具的人，不擅长也不喜欢处理这些细节。一旦题目更改，原先的工具就失效了。
所以在处理密码的时候需要关注字符集，对应编码。

当然下面也介绍一个一劳永逸的方法。

例题赏析

TWCTF 2016 的 super_express 虽然在 Wiki 里面有了，讲解也很到位，但是还是觉得太精彩了，所以这里引用一下，也为后面统一的解密方法做铺垫。

仿射密码例题

TWCTF 2016 的 super_express

文件一：problem.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import sys
key = '****CENSORED***************'
flag = 'TWCTF{*******CENSORED********}'

if len(key) % 2 == 1:
    print("Key Length Error")
    sys.exit(1)

n = int(len(key) / 2)
encrypted = ''
for c in flag:
    c = ord(c)
    for a, b in zip(key[0:n], key[n:2*n]):
        c = (ord(a) * c + ord(b)) % 251
    encrypted += '%02x' % c

print encrypted

文件二：encrypted

1
805eed80cbbccb94c36413275780ec94a857dfec8da8ca94a8c313a8ccf9

分析思路

可以发现，虽然对于 flag 中的每个字母都加密了 n 次，如果我们仔细分析的话，我们可以发现

$$
\begin{align*}
c_1&=a_1c+b_1 \\
c_2&=a_2c_1+b_2 \\
&=a_1a_2c+a_2b_1+b_2 \\
&=kc+d
\end{align*}
$$

根据第二行的推导，我们可以得到其实 $c_n$ 也是这样的形式，可以看成 $c_n=xc+y$ ，
由于是线性变化，所以依然是仿射变换的形式。
这里使用选择明文攻击：
251 < 256 = 16^2
加上源码中 encrypted += '%02x' % c
易知 encrypted 中两个十六进制字母表示一个数字

破解脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 计算 a, b
import gmpy2
flag = 'TWCTF{*******CENSORED********}'
encryption = "805eed80cbbccb94c36413275780ec94a857dfec8da8ca94a8c313a8ccf9"
encrypted = [int(encryption[i:i+2], 16) for i in xrange(0, len(encryption), 2)]

x = map(ord, ('T', 'W'))
y = encrypted[:2]
dx = x[0]-x[1]
dy = y[0]-y[1]

a = dy * gmpy2.invert(dx, 251) %251
b = (y[0] - a * x[0]) % 251

text = ""
inv_a = gmpy2.invert(a, 251) % 251
for y in encrypted:
    text += chr( inv_a * (y-b) % 251)

print(text)
# TWCTF{Faster_Than_Shinkansen!}

一道让人感到酣畅淋漓的密码学题目就此解决。

统一攻击脚本

下面是我写的攻击脚本

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
# -*- coding: utf-8 -*-
# Author: ZER0-Nu1L
# Python2.7
import gmpy2

'''
Affine Cipher Attack
+---------------------------------------+
|  k = (a, b)                           |
|  Enc: eₖ(x) = y ≡ a·x + b mod n       |
|  y₁=(ax₁+b) mod n                     |
|  y₂=(ax₂+b) mod n                     |
|---------------------------------------|
|  a = (y₁−y₂) · (x₁−x₂)⁻¹ mod n        |
|  b = y₁ - ax₁ mod n                   |
|  x ≡ a⁻¹·(y - b) mod n                |
+---------------------------------------+
''' 

def Affine_attack(message, cipher, n, type="utf"):
    '''
    message, cipher 都以字符串的形式输入，
    type 表示 message, cipher 的编码方式，
    为了兼容'a-z'的字符集，特加入 type = 'alpha'
    '''
    cip_p = cipher[:2] # part
    mes_p = message[:2]

    cip_n = str2num(cip_p, type)
    mes_n = str2num(mes_p, type)
    dx = (mes_n[0] - mes_n[1]) % n
    dy = (cip_n[0] - cip_n[1]) % n
    a = (gmpy2.invert(dx, n) * dy) % n
    b = (cip_n[0] - a * mes_n[0]) % n

    message = ""
    a_inv = gmpy2.invert(a, n)
    for char in cipher:
        message += chr( a_inv * ( ord(char) - ordertype(type) - b) % n + ordertype(type) )
    print message

def str2num(str, type="utf"):
    '''
    将字符集映射到数字集
    '''
    if type == "alpha":
        return map(lambda x : ord(x)- ord('a'), str)
    elif type == "utf":
        return map(ord, str)
    else:
        return -1

def ordertype(type = "utf"):
    '''
    返回字符集映射关系（整数）
    '''
    if type == 'alpha':
        return ord('a')
    elif type == 'utf':
        return 0
    else:
        return -1

if __name__ == "__main__":
    '''
    只需要把数据处理成函数能解决的形式，就能对接接口，直接实现攻击
    '''
    # a-z 字符集
    cipher = "gzyyf"
    message = 'he'
    Affine_attack(message, cipher, 26, "alpha")
    
    # TWCTF 2016
    encryption = "805eed80cbbccb94c36413275780ec94a857dfec8da8ca94a8c313a8ccf9"
    message ="TWCTF{"
    cipher = ""
    for i in xrange(0, len(encryption), 2):
        cipher += chr(int(encryption[i:i+2], 16))
    Affine_attack(message, cipher, 251)
    cipher

在函数 Affine_attack 中分离了字符集处理和选择明文攻击的代码实现，用 str2num 函数将字符集映射到数字集；用 ordertype 函数将字符集返回用到的字符集的基，在还原密文的时候使用。
函数 Affine_attack 就此可以根据参数 字符串 message, 字符串cipher, 模数n, 字符集type 直接破解密码。
脚本里面包含了两个样例，一个是字符集上的，一个是 TWCTF 2016 super_express 这道题目，super_express 需要对密文进行简单地处理，把它转化成字符串的格式，然后只用调用函数即可。:happy:

希尔密码

希尔密码更精彩一些，和仿射密码一样，是域上的线性运算。和仿射密码不同的是，这里的线性运算是矩阵乘法，是多表替换的古典密码。
这部分 CTF-Wiki 写得很少，只有寥寥几句。推荐的工具也不是特别好用的感觉。各路博客也质量也一般般，近乎是直接上代码，代码质量也一般（无意冒犯无意冒犯）。
笔者在华东师范大学数学系课件里面找到了相关的描述。

原理

基础数学知识

定义1：设 $A$ 为定义在集合 $Z_m $ 上的 $n$ 阶方阵，若存在一个定
义在 $Z_m$ 上的方阵B，使得
$$
AB = BA = E \mod {m}
$$
则称 $A$ 模 $m$ 可逆，$B$ 为 $A$ 的模 m 逆矩阵，记为
$$
B = A^{−1} \mod m
$$
和 $Z_m$ 上的整数运算一样，需要满足一定条件才能得到逆运算的结果（这里是逆矩阵）。

定义在集合 $Z_m $上的 $n$ 阶方阵 $A$ 模 $m$ 可逆 $\Leftrightarrow$ $m$ 与 $det(A)$ 互素。

求逆矩阵的方法和大学线性代数里面的类似，但是不一样。
$$
A^{-1}=\frac{1}{|A|} A^{\star} \mod m
\\
\text{其中}\ \frac{1}{|A|} = |A|^{-1} \mod m
$$
以上是基础知识。

加密解密流程

加密：

  1. 将明文中的字符映射到数字上。（和仿射密码类似）
  2. 选择一个 n 阶可逆整数方阵 $A$ ，称为 $Hill_n$ 密码的加密矩阵。
  3. 根据加密矩阵，将明文字母分组。
    比如，加密矩阵如果是 2 × 2 的方阵，明文就要每两个为列，组成 2 × n 的矩阵 $X$
  4. $A \times X = C$ 加密得到 2 × n 的密文矩阵 $C$.
  5. 密文矩阵再逐列拼起来，再从数字映射到字母，得到密文串。

解密：

解密和加密类似，先通过刚刚的方法计算出 模 m 的逆矩阵，然后用 $A^{-1}$ 再进行解密:
$$
A^{-1} \times C = X
$$
然后用上述相同的方法转换成明文串。

加解密脚本

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
# -*- coding: utf-8 -*-
# Author: ZER0-Nu1L
# Python2.7

import numpy as np
import gmpy2

'''
Hill Cipher Encrypt & Decrypt
+-------------------------+
|  A*=|A| · A⁻¹           |
|  A⁻¹=|A|⁻¹ · A* mod n   |
+-------------------------+
'''
def str2num(str, type="utf"):
    '''
    将字符集映射到数字集
    '''
    if type == "alpha":
        return map(lambda x : ord(x)- ord('a'), str)
    elif type == "utf":
        return map(ord, str)
    else:
        return -1

def num2str(lst, type="utf"):
    '''
    将数字集映射到字符集
    '''
    length = len(lst)
    if type == "alpha":
        for i in xrange(length):
            lst[i] = chr(lst[i]+ord('a'))
        return "".join(lst)
    elif type == "utf":
        for i in xrange(length):
            lst[i] = chr(i)
        return "".join(lst)
    else:
        return -1

def Hill_enc(message, An, n, type="utf"):
    '''
    message 为字符串，
    An 是 np.array() 形式的密钥，dtype = np.int, n 是模数，
    type 表示 message 的编码方式，
    '''
    # message -> Xn
    d = An.shape[1]
    Xn = np.array(str2num(message, type))
    Xn = np.array([Xn[i:i+d] for i in xrange(0, Xn.size, d)]).T
    # Hill encrypt
    Cn = np.dot(An, Xn) % n
    # Cn -> Cipher
    cipher_lst = list(Cn.flatten('F'))
    cipher = num2str(cipher_lst, type)
    return cipher

def an_inv(An):
    '''
    用前面描述的方法求出 A⁻¹ mod n
    '''
    det = int(np.linalg.det(An))
    An_inv = np.linalg.inv(An)                  # 此时 An_inv.dtype == np.float8
    An_star = np.array(An_inv * det, np.int)    # 为了避免后面出现偏差，乘完之后赶紧 np.int
                                                # 涉及逆元等返回 np 默认 dtype 的时候，注意类型处理
    det_inv = int(gmpy2.invert(det, 26))
    An_inv = det_inv * An_star % 26
    return An_inv % 26

def Hill_dec(cipher, An, n, type):
    '''
    cipher 为字符串，
    An 是 np.array() 形式的密钥，dtype = np.int, n 是模数，
    type 表示 cipher 的编码方式，
    '''
    # cipher -> Cn
    d = An.shape[0]
    Cn = np.array(str2num(cipher, type))
    Cn = np.array([Cn[i:i+d] for i in xrange(0, Cn.size, d)]).T
    # Hill decrypt
    An_inv = an_inv(An)
    Xn = np.dot(An_inv, Cn) % n
    # Xn -> message
    # message_lst = [int(Xn[i%2-i//2][i//2]) for i in xrange(0, Xn.size)] # 以纵列为顺序展开矩阵
    message_lst = list(Xn.flatten('F'))     # 以纵列为顺序展开矩阵
    message = num2str(message_lst, type)
    return message

核心代码

矩阵逆元

Hill 密码解密的关键在于求出 矩阵A 的逆元（模 n 情况下的）；
理论如下：

$$
A^{-1} = \frac{1}{|A|} A^{\star}
\\
\frac{1}{|A|} = |A|^{-1} \pmod n
\\
\therefore A^{-1} = |A|^{-1} · A^{\star} \pmod n
$$

需要注意的是逆矩阵会有非整数，但是伴随矩阵一定是整数（整数矩阵），所以依旧可以 $A^{\star}=|A| · A^{-1}$ 的方式求出伴随矩阵。

求法：
$$
A^{\star} = |A| · A^{-1}
\\
A^{-1} = |A|^{-1} · A^{\star} \pmod n
$$

Numpy

这段代码大量使用了 numpy 这个第三方库里的对象、函数、方法。
其中和线性代数相关的函数有：

函数 描述 助记
dot 如果一维数组，得到两数组的內积
如果二维数组（矩阵）之间的运算，得到矩阵积；		 dot - ·
linalg.det 数组的行列式 hanglie
linalg.solve(A, B) 求解线性矩阵方程
inv 计算矩阵的乘法逆矩阵 invert

当然代码中还用到了诸如 Cn.flatten('F') 这样的宝藏方法。
还需要注意的是，Numpy 默认的矩阵元素是 np.float 类型，且求逆矩阵、一些运算之后，矩阵类型都会变成 np.float 类型，这对解密的正确性的打击是毁灭性的。
3.9999 会被直接当成 3，而且如果不够注意的话，会导致连环的效应😢 。

其他

这里也兼容了各种字符集。

题目示例

题目选自 Viking 战队2018级的招新题：被线性代数支配的恐惧。

文件

1
HNBSIRVQQBRFGPS
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
#include <stdio.h>
#include <string.h>
void encrypt(char *msg, int key1[][3], int *key2, int n);
int main()
{
	int key[3][3] =
		{{1, 1, 1},
		 {0, 1, 1},
		 {1, 0, 1}};

	int key2[3] = {2, 5, 4};
	char flag[100];

	FILE *file = fopen("flag.txt", "r");
	if (file == NULL)
	{
		printf("Flag不在这里哦");
		return 0;
	}
	fgets(flag, 0X100, file);
	printf("%d\n", strlen(flag));
	encrypt(flag, key, key2, 3);
	FILE *cipher = fopen("cipher.txt", "w");
	fputs(flag, cipher);
}

void encrypt(char *msg, int key1[][3], int *key2, int n)
{
	int f = strlen(msg) / n;
	int len = strlen(msg);
	int tmp[n];

	for (int i = 0; i < len; i++)
		msg[i] -= 'A';

	for (int i = 0; i < f; i++)
	{
		for (int j = 0; j < n; j++)
		{
			int t = 0;
			for (int k = 0; k < n; k++)
				t += (key1[j][k] * msg[i * n + k]);
			tmp[j] = t;
		}
		for (int k = 0; k < n; k++)
			msg[i * n + k] = (tmp[k] + key2[k]) % 26;
	}
	for (int i = 0; i < len; i++)
		msg[i] += 'A';
}

分析

这道题不是原生的希尔密码，有希尔密码+仿射密码的味道。（Exciting ）
我用 Python 重写代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import numpy as np

An = np.array([[1,1,1],[0,1,1],[1,0,1]])
Bn = np.array([[2]*5,[5]*5,[4]*5])

f = open("flag.txt","r").read()
Xn = []
for char in f:
    Xn.append(ord(char)-ord('A'))
Xn = np.array(X).reshape(5,3)

Xn = ( np.dot(An, Xn.T) + Bn ) % 26

Xn = np.transpose(Xn).flatten()
cipher = ""
for item in Xn:
    cipher += chr(item+ord('A'))

print(cipher)

这就很清晰了，加密方案是：
$$
A_n \times X_n + B_n = C_n
$$
换汤不换药，打走小白工具侠。解密方法是：

$$
X_n = (C_n - B_n) \times A_n^{-1}
$$

用上之前的脚本（调用 || ctrl + c && ctrl +v）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 被线代支配的恐惧
import Hill # 刚刚的脚本

An = np.array([[1,1,1],[0,1,1],[1,0,1]])
Bn = np.array([[2]*5,[5]*5,[4]*5])
cipher = "HNBSIRVQQBRFGPS".lower()
# Hill_dec(Cipher, An, 26, "alpha")

# Cipher -> Cn
d = An.shape[0]
Cn = np.array(str2num(cipher, "alpha"))
Cn = np.array([Cn[i:i+d] for i in xrange(0, Cn.size, d)]).T
# Hill decrypt
An_inv = an_inv(An)
Xn = np.dot(An_inv, Cn-Bn) % 26
# Xn -> message
# message_lst = [int(Xn[i%2-i//2][i//2]) for i in xrange(0, Xn.size)] # 以纵列为顺序展开矩阵
message_lst = list(Xn.flatten('F'))     # 以纵列为顺序展开矩阵
message = num2str(message_lst, "alpha").upper()
print "flag:"
print message

message : XIANDAIHENYOUQU.

参考文章

  1. Single table Substitution Cipher
  2. Multi-table Substitution Cipher
------ The end ------

本文标题:仿射密码与希尔密码深度解析

文章作者:Andy Wu

发布时间:2020年03月22日 - 16:03

最后更新:2020年05月01日 - 23:05

原始链接:https://zer0-nu1l.github.io/2020/03/22/%E4%BB%BF%E5%B0%84%E5%AF%86%E7%A0%81%E4%B8%8E%E5%B8%8C%E5%B0%94%E5%AF%86%E7%A0%81/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。