NepCTF 2022 [P or S]

mycipher.py

from secret import keys
from Crypto.Util.number import *
assert(len(keys)==6)
Pbox=[
[0, 3, 6, 9, 10, 11, 13, 16, 18, 19, 20, 24, 25, 27, 28, 29, 30, 31],
[0, 1, 3, 8, 9, 11, 12, 14, 16, 18, 19, 23, 24, 25, 26, 28, 29],
[0, 1, 2, 3, 9, 10, 11, 13, 19, 20, 22, 25, 27, 28, 29, 31],
[0, 2, 3, 5, 6, 7, 8, 13, 16, 19, 21, 25, 26, 27, 28],
[2, 4, 6, 7, 9, 11, 12, 13, 16, 17, 20, 21, 22, 23, 24, 25, 27, 31],
[2, 10, 13, 15, 16, 17, 21, 22, 23, 24, 29, 31],
[1, 2, 8, 11, 12, 13, 16, 17, 19, 21, 22, 24, 25, 26, 27, 28, 30, 31],
[0, 3, 6, 13, 14, 17, 19, 21, 22, 23, 26, 27, 28],
[1, 5, 7, 8, 11, 12, 14, 15, 19, 23, 25, 27, 31],
[0, 2, 3, 6, 7, 8, 9, 10, 11, 12, 16, 18, 19, 22, 23, 24, 25, 26, 27, 28],
[0, 1, 6, 7, 10, 15, 16, 21, 24, 25, 29, 30],
[1, 4, 5, 6, 7, 12, 13, 15, 18, 19, 20, 22, 26, 27, 29, 31],
[0, 3, 5, 8, 9, 17, 21, 22, 24, 25, 26, 27, 30],
[0, 2, 3, 4, 5, 6, 7, 8, 11, 17, 19, 20, 24, 25, 26, 27, 30],
[2, 6, 7, 8, 11, 12, 14, 16, 20, 21, 22, 24, 29, 30, 31],
[0, 2, 5, 6, 7, 8, 9, 10, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 29, 31],
[0, 1, 2, 3, 4, 5, 8, 10, 11, 12, 13, 16, 17, 18, 20, 21, 22, 23, 25, 26, 28, 29, 30],
[3, 5, 6, 8, 10, 13, 14, 17, 19, 20, 21, 22, 24, 26, 27, 29, 30],
[1, 3, 6, 12, 14, 15, 16, 17, 18, 21, 24, 25, 26, 27, 28],
[0, 1, 2, 3, 5, 6, 7, 8, 9, 12, 13, 19, 20, 23, 26, 29, 30],
[3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 20, 21, 22, 25, 26, 27, 28, 29, 30],
[0, 1, 2, 4, 6, 7, 9, 10, 11, 13, 15, 16, 18, 19, 20, 21, 25, 31],
[0, 2, 7, 10, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 29, 31],
[1, 2, 3, 5, 7, 8, 18, 19, 21, 22, 23, 25, 31],
[3, 4, 7, 8, 10, 11, 13, 14, 17, 18, 19, 21, 22, 23, 24, 28, 29],
[0, 2, 6, 7, 8, 10, 11, 12, 13, 16, 18, 19, 21, 23, 31],
[0, 1, 3, 4, 8, 13, 14, 16, 18, 19, 21, 26, 27, 30, 31],
[5, 6, 7, 9, 13, 14, 15, 18, 19, 20, 21, 24, 25, 28],
[1, 3, 4, 5, 6, 7, 11, 14, 16, 17, 19, 20, 21, 22, 23, 25, 30, 31],
[2, 3, 4, 6, 7, 11, 13, 17, 18, 19, 20, 23, 24, 25, 26, 28, 29, 30, 31],
[0, 1, 2, 3, 4, 7, 9, 10, 13, 15, 16, 19, 22, 23, 24, 25, 27],
[0, 1, 3, 4, 12, 16, 18, 19, 26, 30]]

def enc(v):
    t=v
    for i in keys:
       q=[]
       for j in Pbox:
           q.append(sum([t[k] for k in j])%2)
       t=[int(q[j])^int(i[j]) for j in range(32)]
    return t

assert(len(flag)==32)
fb=bin(bytes_to_long(flag))[2:].zfill(32*8)
ciphertext=""
for i in range(0,len(fb),32):
    t=enc([int(j) for j in fb[i:i+32]])
    ciphertext+="".join([str(j) for j in t])

print(ciphertext)
"""
0111110000100101000001101011110111101100000010110011101111000101111110111111100100100010001011000101000110110011111101000001001000000101111000001110001111001001100100111000011011101111111101001011100000100100110011111101100111001100111111110001111011101100

"""

思路

刚开始看到这题的时候其实是很有思路的,思路也挺正确的。

最主要的加密操作就是,这两句

for j in Pbox:
		q.append(sum([t[k] for k in j])%2)
t=[int(q[j])^int(i[j]) for j in range(32)]

异或和模二上加法是一样的,那么就可以将这一步的加密操作看成是一个矩阵的线性方程

$$ t_{i+1}=P\times t_{i} + k_{i} $$

其中$P$是Pbox构成的矩阵,也就是

$$ P_{ij^{\prime}}=1,where\quad j^{\prime}=Pbox[i][j] $$

然后呢每一组明文的整个加密过程就是递归上述的操作6次。由于方程是线性的,很容易想到要去求$k$,然后进行逆运算。于是就在这里卡了很久。

$k$是求不出来的

但还可以把单次加密的过程看成一个矩阵的运算

$$ \begin{bmatrix}t_{i+1} & 0 \\ 1 & 0\end{bmatrix} = \begin{bmatrix}P & k_{i} \\ 0 & 1\end{bmatrix} \times \begin{bmatrix}t_{i} & 0 \\ 1 & 0\end{bmatrix} $$

整个加密依然是一个递归的过程,就是输入的形式与输出的形式相同

$$ \begin{bmatrix}c & 0 \\ 1 & 0\end{bmatrix} =\begin{bmatrix}P & k_{0} \\ 0 & 1\end{bmatrix} \times\begin{bmatrix}P & k_{1} \\ 0 & 1\end{bmatrix}\times\cdots\times\begin{bmatrix}P & k_{5} \\ 0 & 1\end{bmatrix} \times\begin{bmatrix}m & 0 \\ 1 & 0\end{bmatrix} $$

我们又知道明文的前缀是”flag”,就可以进行已知明文攻击,把前面那一串求出来。

EXP

当我想用上面的式子写exp的时候,不对劲,写不出来。毕竟是写在草稿上的东西

还是用一开始的式子

$$ c=P^{6}m+P^{5}k_{0}+p^{4}k_{1}+\cdots+k_{5} $$

令后面一坨为$R$,$c=P^{6}m+R$

exp.sage

from Crypto.Util.number import *

Pbox=[
[0, 3, 6, 9, 10, 11, 13, 16, 18, 19, 20, 24, 25, 27, 28, 29, 30, 31],
[0, 1, 3, 8, 9, 11, 12, 14, 16, 18, 19, 23, 24, 25, 26, 28, 29],
[0, 1, 2, 3, 9, 10, 11, 13, 19, 20, 22, 25, 27, 28, 29, 31],
[0, 2, 3, 5, 6, 7, 8, 13, 16, 19, 21, 25, 26, 27, 28],
[2, 4, 6, 7, 9, 11, 12, 13, 16, 17, 20, 21, 22, 23, 24, 25, 27, 31],
[2, 10, 13, 15, 16, 17, 21, 22, 23, 24, 29, 31],
[1, 2, 8, 11, 12, 13, 16, 17, 19, 21, 22, 24, 25, 26, 27, 28, 30, 31],
[0, 3, 6, 13, 14, 17, 19, 21, 22, 23, 26, 27, 28],
[1, 5, 7, 8, 11, 12, 14, 15, 19, 23, 25, 27, 31],
[0, 2, 3, 6, 7, 8, 9, 10, 11, 12, 16, 18, 19, 22, 23, 24, 25, 26, 27, 28],
[0, 1, 6, 7, 10, 15, 16, 21, 24, 25, 29, 30],
[1, 4, 5, 6, 7, 12, 13, 15, 18, 19, 20, 22, 26, 27, 29, 31],
[0, 3, 5, 8, 9, 17, 21, 22, 24, 25, 26, 27, 30],
[0, 2, 3, 4, 5, 6, 7, 8, 11, 17, 19, 20, 24, 25, 26, 27, 30],
[2, 6, 7, 8, 11, 12, 14, 16, 20, 21, 22, 24, 29, 30, 31],
[0, 2, 5, 6, 7, 8, 9, 10, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 29, 31],
[0, 1, 2, 3, 4, 5, 8, 10, 11, 12, 13, 16, 17, 18, 20, 21, 22, 23, 25, 26, 28, 29, 30],
[3, 5, 6, 8, 10, 13, 14, 17, 19, 20, 21, 22, 24, 26, 27, 29, 30],
[1, 3, 6, 12, 14, 15, 16, 17, 18, 21, 24, 25, 26, 27, 28],
[0, 1, 2, 3, 5, 6, 7, 8, 9, 12, 13, 19, 20, 23, 26, 29, 30],
[3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 20, 21, 22, 25, 26, 27, 28, 29, 30],
[0, 1, 2, 4, 6, 7, 9, 10, 11, 13, 15, 16, 18, 19, 20, 21, 25, 31],
[0, 2, 7, 10, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 29, 31],
[1, 2, 3, 5, 7, 8, 18, 19, 21, 22, 23, 25, 31],
[3, 4, 7, 8, 10, 11, 13, 14, 17, 18, 19, 21, 22, 23, 24, 28, 29],
[0, 2, 6, 7, 8, 10, 11, 12, 13, 16, 18, 19, 21, 23, 31],
[0, 1, 3, 4, 8, 13, 14, 16, 18, 19, 21, 26, 27, 30, 31],
[5, 6, 7, 9, 13, 14, 15, 18, 19, 20, 21, 24, 25, 28],
[1, 3, 4, 5, 6, 7, 11, 14, 16, 17, 19, 20, 21, 22, 23, 25, 30, 31],
[2, 3, 4, 6, 7, 11, 13, 17, 18, 19, 20, 23, 24, 25, 26, 28, 29, 30, 31],
[0, 1, 2, 3, 4, 7, 9, 10, 13, 15, 16, 19, 22, 23, 24, 25, 27],
[0, 1, 3, 4, 12, 16, 18, 19, 26, 30]]

enc = '0111110000100101000001101011110111101100000010110011101111000101111110111111100100100010001011000101000110110011111101000001001000000101111000001110001111001001100100111000011011101111111101001011100000100100110011111101100111001100111111110001111011101100'

P = zero_matrix(GF(2), 32, 32)
for i in range(len(Pbox)):
    for j in range(len(Pbox[i])):
        P[i, Pbox[i][j]] = 1

m0 = bin(bytes_to_long(b'flag'))[2:].zfill(4*8)
m0 = matrix(GF(2), 32, 1, [int(i) for i in m0])
c0 = matrix(GF(2), 32, 1)
for i in range(32):
    c0[i, 0] = int(enc[i])
R = c0 - (P^6 * m0)
flag = b''
for i in range(32, len(enc), 32):
    c = matrix(GF(2), 32, 1)
    for j in range(32):
        c[j, 0] = int(enc[i+j])
    m = (P^6).inverse() * (c - R)
    bm = ''
    for j in range(32):
        bm += str(m[j, 0])
    flag += long_to_bytes(int(bm, 2))
flag = b'NepCTF' + flag
print(flag)
#b'NepCTF{P_has_no_Semantic_Security}'