对称密码、线性代数和2024网鼎杯白虎的crypto01

当对称的每一个部分都是线性的时候，其实可以用线性代数的方法去解

@V 在他的文章里已经总结了三种方法了，那我在这里就在补充一种

PS：同时感谢@石卡酷提供的灵感

题目：CRYPTO01.zip

审题，直接看encrypt函数，就是执行rounds = 14轮的

$$M_{i+1} = P^{-1}(S(P(M_i)) \oplus K)$$

其中$M_i$是第$i$轮的明文，$K$是密钥

接下来主要做的是分析$P$和$S$这两个操作

P操作（Permutation）·

P操作就是置换（Permutation）操作，即只改变传入数字的二进制比特的位置，不会把0比特变成1比特或把1变成0

位置是怎么改变的由元组P_permutation决定，令$p_i$为P_permutation的第$i$个元素，令$m_i$为消息$M$的第$i$个比特的话，这里的P操作就是

$$P(M) := m_i \to m_{p_i}$$

这个操作肯定是线性的，要用线性代数的方式实现这个操作，只需要实现一个置换矩阵即可

举个栗子（注：这也是Wiki上的例子），假设P_permutation是

$$\pi = (2, 1, 3, 0)$$

根据置换矩阵的性质，其第$i$行上只有第$\pi_i$列为$1$，所以得到的矩阵就是

$$M_P = \begin{bmatrix} 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ \end{bmatrix}$$

简单做个验算，可以得到

$$\begin{bmatrix} 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ \end{bmatrix} \begin{bmatrix} 0 \\ 1 \\ 2 \\ 3 \end{bmatrix} = \begin{bmatrix} 2 \\ 1 \\ 3 \\ 0 \end{bmatrix} = \pi$$

对题目中的P_permutation构造置换矩阵也是同样的方法，只不过矩阵更大而已

那么现在的P操作就是（令$v_{M}$为明文$M$的二进制向量表达）

$$P(v_M) = M_p \cdot v_M$$

然后$P^{-1}$就是$P$的逆操作，这个直接求逆矩阵即可

$$P^{-1}(v_M) = M_p^{-1} \cdot v_M$$

参考代码

flag = b'flag{199999999999997}'
message = pad(flag)
message = [Integer(bytes_to_long(message[i:i+8])) for i in range(0, len(message), 8)]

n = len(P_permutation)
def n2v(m):
    return vector(m.bits() + [0] * (n - m.nbits()))

def v2n(v):
    return Integer(''.join([str(vi) for vi in v[::-1]]), 2)

# Matrix P and Pinv
m = message[0]
MP = matrix(GF(2), n)
for i in range(n):
    MP[i, P_permutation[i]] = 1
MPinv = MP ** (-1)

assert n2v(P(m)) == MP * n2v(m)
assert n2v(P_inv(m)) == MPinv * n2v(m)

S操作（Substitution）·

S操作就是替换（Substitution）操作，理论上S操作不应该是线性操作，但是稍微分析一下

令$m_i$为消息$M$的第$i$个比特的话，这里的S操作就是

$$S(M) := m_i \to m_i\ \oplus\ [(m_{i-IV}\ \&\ MASK_i)\ \oplus\ (m_{i-IV}\ |\ MASK_i)]$$

看起来有点复杂，先对中括号里面的化简

理论上需要一堆离散数学的运算进行化简，但因为这里只有$m_{i-IV}$和$MASK_i$两个变量，所以可以偷懒打个真值表

$$\begin{array}{c|c|c} m_{i-IV} & MASK_i & (m_{i-IV}\ \&\ MASK_i)\ \oplus\ (m_{i-IV}\ |\ MASK_i) \\ 0 & 0 & 0 \oplus 0 = 0 \\ 0 & 1 & 0 \oplus 1 = 1 \\ 1 & 0 & 0 \oplus 1 = 1 \\ 1 & 1 & 1 \oplus 0 = 0 \\ \end{array}$$

相同为$0$不同为$1$，这就是一个异或操作，所以S操作可以化简为三个东西的异或

$$S(M) := m_i \to m_i\ \oplus\ m_{i-IV}\ \oplus\ \ MASK_i$$

这里已经可以看出其实S操作是线性的了，不妨把异或操作转换为模$2$的加法操作，就更明显了

$$S(M) := m_i \to m_i + m_{i-IV} + \ MASK_i \pmod 2$$

到这里还有一个问题，就是$i-IV$可能会小于$0$，所以还要做个分类讨论，$i-IV$小于$0$的时候根据左移补$0$的性质，要设$m_{i-IV} = 0$

$$S(M) := m_i \to \begin{cases} m_i + m_{i-IV} + \ MASK_i \pmod 2 &, i \ge IV \\ m_i + \ MASK_i \pmod 2 &, i < IV \\ \end{cases}$$

这里直接转换为矩阵还真不好转，所以我的做法是把$m_i + m_{i-IV}$做成一个$M_S$矩阵，然后把后面的MASK做成向量$v_{MASK}$，以

$$S(v_M) \equiv M_S \cdot v_{M} + v_{MASK} \pmod 2$$

的方式进行运算

$M_S$矩阵的构造也不难，根据公式就是把$m_i$和$m_{i-IV}$加起来，所以如果$i \ge IV$的话把第$i$行的第$i$和$i - IV$列设为$1$；如果$i < IV$的话把第$i$行设为$1$即可（这个就不验算了）

参考代码

flag = b'flag{199999999999997}'
message = pad(flag)
message = [Integer(bytes_to_long(message[i:i+8])) for i in range(0, len(message), 8)]

n = len(P_permutation)
def n2v(m):
    return vector(m.bits() + [0] * (n - m.nbits()))

def v2n(v):
    return Integer(''.join([str(vi) for vi in v[::-1]]), 2)

# Matrix S
# m_i+1 = (m_i + m_i-7) + mask_i
m = message[0]
MS = matrix(GF(2), n)
for i in range(n):
    MS[i, i] = 1
    if i >= 7:
        MS[i, i-7] = 1

vmask = n2v(Integer(MASK))
assert n2v(S(m)) == MS * n2v(m) + vmask

加密操作·

到这里就可以重写一下加密操作了

已知加密操作为rounds = 14轮的

$$M_{i+1} = P^{-1}(S(P(M_i)) \oplus K)$$

而且根据上面分析可知

$$\begin{aligned} P(v_M) &= M_p \cdot v_M \\ P^{-1}(v_M) &= M_p^{-1} \cdot v_M \\ S(v_M) &\equiv M_S \cdot v_{M} + v_{MASK} \pmod 2 \end{aligned}$$

所以重写一下就是

$$\begin{aligned} v_{M_{i+1}} &= P^{-1}(S(M_p \cdot v_{M_i}) \oplus K) \\ &\equiv P^{-1}((M_S \cdot M_p \cdot v_{M_i} + v_{MASK}) \oplus K) \pmod 2 \\ &\equiv P^{-1}(M_S M_p \cdot v_{M_i} + v_{MASK} + v_K) \pmod 2 \\ &\equiv M_p^{-1} \cdot (M_S M_p \cdot v_{M_i} + v_{MASK} + v_K) \pmod 2 \\ &\equiv M_p^{-1}M_S M_p \cdot v_{M_i} + M_p^{-1} \cdot (v_{MASK} + v_K) \pmod 2 \\ \end{aligned}$$

不妨令

$$\begin{aligned} A &= M_p^{-1}M_S M_p \\ b &= M_p^{-1} (v_{MASK} + v_K) \end{aligned}$$

的话，就是

$$v_{M_{i+1}} \equiv A \cdot v_{M_i} + b \pmod 2$$

重复$k$次

$$v_{M_{i+k}} \equiv A^k \cdot v_{M_i} + (\sum_{j=0}^{k-1} A^j) b \pmod 2$$

于是得到加密操作为

$$v_C = Enc(v_M) \equiv A^{14} \cdot v_{M} + (\sum_{j=0}^{14-1} A^j) b \pmod 2$$

不妨令$d = (\sum_{j=0}^{14-1} A^j) b$，可以进一步化简为

$$v_C \equiv A^{14} \cdot v_{M} + d \pmod 2$$

解密操作·

最后就是解密了

再看一遍加密操作，加密是分组的，每一组是$8$个字节，而比赛中的flag头是wdflag{，就可以知道$7$个字节，那么只要枚举剩下的一个字节，就可以知道一组明密文对

也就是现在我知道$v_M$和$v_C$，只需要计算

$$d \equiv v_C - (A^{14} \cdot v_{M}) \pmod 2$$

就可以得到一个等效的密钥$d$，后续给定任意的密文组$C'$，只需要计算

$$v_{M'} \equiv (A^{14})^{-1} \cdot (v_{C'} - d) \pmod 2$$

即可解密

另外，因为加密时有对消息进行pad，所以只需要通过对最后一组解密判断pad是否正确，即可知道解出的等效密钥$d$是否正确

参考代码

from sage.all import *
from Crypto.Util.number import *
from hashlib import md5
import string

block_size = 64
rounds = 14


MASK = 0b1110001001111001000110010000100010101111101100101110100001001001
IV = 7

b2i = lambda x: Integer(sum([x[i] * 2**i for i in range(len(x))]))

def pad(x):
    padlen = block_size - len(x) % block_size
    return x + bytes([padlen] * padlen)

def P(x):
    bit_x = x.bits()
    if len(bit_x) < block_size:
        bit_x.extend([0] * (block_size - len(bit_x)))
    bit_x = [bit_x[P_permutation[i]] for i in range(block_size)]
    return b2i(bit_x)

def P_inv(x):
    bit_x = x.bits()
    if len(bit_x) < block_size:
        bit_x.extend([0] * (block_size - len(bit_x)))
    bit_x = [bit_x[inverse_P_permutation[i]] for i in range(block_size)]
    return b2i(bit_x)

def S(x):
    x1 = x
    x2 = x << IV & MASK
    x3 = x << IV & ((1 << block_size) - 1) | MASK
    return x1 ^ x2 ^ x3

def encrypt(message_block, key):
    ret = message_block
    for i in range(rounds):
        print(ret)
        ret = P_inv(S(P(ret)) ^ key)
    return ret

ciphertext = [15556852711617030977, 17425085605625351983, 2506358089440944923, 1278751751083902772, 13156242808241775459, 2735122367365725460, 6194195534313299228, 6194195534313299228]
c = [Integer(ci) for ci in ciphertext]
P_permutation = [51, 44, 35, 24, 50, 59, 31, 58, 57, 7, 23, 10, 47, 6, 60, 18, 37, 56, 1, 36, 55, 14, 49, 0, 28, 40, 45, 25, 29, 19, 15, 26, 17, 54, 2, 8, 48, 42, 11, 32, 3, 61, 30, 22, 52, 12, 62, 9, 33, 4, 27, 53, 34, 20, 43, 41, 13, 39, 5, 46, 16, 21, 38, 63]
inverse_P_permutation = [P_permutation[i] for i in range(block_size)]

n = len(P_permutation)
def n2v(m):
    return vector(m.bits() + [0] * (n - m.nbits()))

def v2n(v):
    return Integer(''.join([str(vi) for vi in v[::-1]]), 2)

# Matrix P and Pinv
MP = matrix(GF(2), n)
for i in range(n):
    MP[i, P_permutation[i]] = 1
MPinv = MP ** (-1)

# Matrix S
# m_i+1 = (m_i + m_i-7) + mask_i
MS = matrix(GF(2), n)
for i in range(n):
    MS[i, i] = 1
    if i >= 7:
        MS[i, i-7] = 1
vmask = n2v(Integer(MASK))

A = MPinv * MS * MP
A14 = A ** rounds
A14inv = A14 ** (-1)

def dec(d, c):
    vm = A14inv * (n2v(c) - d)
    return long_to_bytes(v2n(vm))

vc0 = n2v(c[0])
for s in string.printable:
    m0 = 'wdflag{%s' % s
    m0 = Integer(bytes_to_long(m0.encode()))
    vm0 = n2v(m0)

    d = vc0 - A14 * vm0
    tmp = dec(d, c[-1])
    if tmp[-1] == tmp[-2]:
        print(s)
        break

m = b''.join([dec(d, ci) for ci in c])
print(m)

另外，能否直接从$d$中算出一个更准确的密钥呢

当时我试了一下，是不行的

因为

$$d \equiv (\sum_{j=0}^{14-1} A^j) b \pmod 2$$

如果要知道$v_K$的话至少需要知道$b$，所以要求$\sum_{j=0}^{14-1} A^j$的逆

但实际上这个矩阵是不可逆的，也就是说密钥$K$会存在多解

虽然可以使用solve_right解出一组特解，但这个特解和真实的密钥也会不一样