BeginCTF Crypto WP

Crypto

baby_classic

task

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
from random import *
from string import *
import numpy as np
from secret import plaintext

ls = ascii_uppercase + '_.*'

def generate_str(length):
    s = ""
    for i in range(length):
        s += choice(ls)
    return s

def str2mat(s):
    res = np.zeros((len(s) // 6, 6),dtype=int)
    for i in range(0,len(s)):
        res[i // 6, i % 6] = ls.index(s[i])
    return res

def mat2str(mat):
    s = ""
    for i in range(len(mat) * 6):
        s += ls[mat[i // 6, i % 6]]
    return s

def encrypt(plaintext,key1,key2):
    mat_plaintext = str2mat(plaintext)
    mat_key1 = str2mat(key1)
    mat_key2 = str2mat(key2)

    enc_matrix = np.dot(mat_plaintext,mat_key1) % 29
    for i in range(len(enc_matrix)):
        for j in range(len(enc_matrix[i])):
            enc_matrix[i][j] = (enc_matrix[i][j] + mat_key2[0][j]) % 29

    return mat2str(enc_matrix)

if __name__ == "__main__":

    assert len(plaintext) == 72
    m = generate_str(48)
    key1 = generate_str(36)
    key2 = generate_str(6)
    c = encrypt(m, key1, key2)
    ciphertext = encrypt(plaintext, key1, key2)

    '''
    flag = "begin{" + hashlib.md5(plaintext.encode()).hexdigest() + "}"
    '''

    print(f"m = {m}")
    print(f"c = {c}")
    print(f"ciphertext = {ciphertext}")


'''
output:
m = VOWAS*TED.AE_UMLVFV*W*HSSSTZIZZZDAKCLXZKM_E*VR*Y
c = QLOKQGUWMUTGZSDINCQVIVOLISFB_FC.IC_OSPLOBGOVSCZY
ciphertext = MHDTBJSZXLHH.Z.VWGLXUV.SDQUPAMEPNVQVQZX_CBDZHM_IBZRGLJP_YSBDXN.VACLDGCO_
'''

观察代码可以得知原文构造了一个8x6的矩阵
密钥是key1为6x6的矩阵，key2是1x6的矩阵
所以设一个未知数

1
2
3
4
5
6
7
key1=[[x11,x12,x13,x14,x15,x16],
      [x21,x22,x23,x24,x25,x26],
      [x31,x32,x33,x34,x35,x36],
      [x41,x42,x43,x44,x45,x46],
      [x51,x52,x53,x54,x55,x56],
      [x61,x62,x63,x64,x65,x66]]
key2=[y1,y2m,y3,y4,y5,y6]

这里我们把给定的明文和密文也转化为矩阵

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

然后我们开始观察加密方式可以得到c=m*key1+key2
**也就是说我们可以列出8个方程{(m[1][1]*key1[1][1]+m[1][2]key[2][1]+……+m[1][6]key[6][1])+key2}mod29=c[1][1]

1
2
3
4
5
6
7
8
f1=m[0][0]*x13+m[0][1]*x23+m[0][2]*x33+m[0][3]*x43+m[0][4]*x53+m[0][5]*x63 - c[0][5] + y3
f2=m[1][0]*x13+m[1][1]*x23+m[1][2]*x33+m[1][3]*x43+m[1][4]*x53+m[1][5]*x63 - c[1][5] + y3
f3=m[2][0]*x13+m[2][1]*x23+m[2][2]*x33+m[2][3]*x43+m[2][4]*x53+m[2][5]*x63 - c[2][5] + y3
f4=m[3][0]*x13+m[3][1]*x23+m[3][2]*x33+m[3][3]*x43+m[3][4]*x53+m[3][5]*x63 - c[3][5] + y3
f5=m[4][0]*x13+m[4][1]*x23+m[4][2]*x33+m[4][3]*x43+m[4][4]*x53+m[4][5]*x63 - c[4][5] + y3
f6=m[5][0]*x13+m[5][1]*x23+m[5][2]*x33+m[5][3]*x43+m[5][4]*x53+m[5][5]*x63 - c[5][5] + y3
f7=m[6][0]*x13+m[6][1]*x23+m[6][2]*x33+m[6][3]*x43+m[6][4]*x53+m[6][5]*x63 - c[6][5] + y3
f8=m[7][0]*x13+m[7][1]*x23+m[7][2]*x33+m[7][3]*x43+m[7][4]*x53+m[7][5]*x63 - c[7][5] + y3

由于这是一个带mod的方程，所以考虑使用Gröbner基求未知数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#sage
PR.<x13,x23,x33,x43,x53,x63,y3> = PolynomialRing(Zmod(p))

f1=m[0][0]*x13+m[0][1]*x23+m[0][2]*x33+m[0][3]*x43+m[0][4]*x53+m[0][5]*x63 - c[0][5] + y3
f2=m[1][0]*x13+m[1][1]*x23+m[1][2]*x33+m[1][3]*x43+m[1][4]*x53+m[1][5]*x63 - c[1][5] + y3
f3=m[2][0]*x13+m[2][1]*x23+m[2][2]*x33+m[2][3]*x43+m[2][4]*x53+m[2][5]*x63 - c[2][5] + y3
f4=m[3][0]*x13+m[3][1]*x23+m[3][2]*x33+m[3][3]*x43+m[3][4]*x53+m[3][5]*x63 - c[3][5] + y3
f5=m[4][0]*x13+m[4][1]*x23+m[4][2]*x33+m[4][3]*x43+m[4][4]*x53+m[4][5]*x63 - c[4][5] + y3
f6=m[5][0]*x13+m[5][1]*x23+m[5][2]*x33+m[5][3]*x43+m[5][4]*x53+m[5][5]*x63 - c[5][5] + y3
f7=m[6][0]*x13+m[6][1]*x23+m[6][2]*x33+m[6][3]*x43+m[6][4]*x53+m[6][5]*x63 - c[6][5] + y3
f8=m[7][0]*x13+m[7][1]*x23+m[7][2]*x33+m[7][3]*x43+m[7][4]*x53+m[7][5]*x63 - c[7][5] + y3
Fs = [f1, f2, f3,f4, f5, f6,f7, f8]
I = Ideal(Fs)
B = I.groebner_basis()
t=[]
for b in B:
    assert b.degree() == 1
    mi = ZZ(-b(0, 0, 0,0,0,0,0))
    t.append(mi)
print(t)

所以，根据以上公式，我们可以求出key1，key2

1
2
3
4
5
6
7
8
9
key1 = [
    [8, 25, 26, 22, 17, 3],
    [4, 26, 12, 23, 6, 0],
    [16, 20, 16, 20, 2, 16],
    [25, 15, 24, 25, 5, 21],
    [25, 23, 18, 1, 19, 11],
    [22, 26, 1, 13, 22, 23],
]
key2 = [[27, 5, 17, 28, 23, 25]]

手撕密钥成功后我们进行解密操作

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
p = 29
'''
m = [
    [21, 14, 22, 0, 18, 28],
    [19, 4, 3, 27, 0, 4],
    [26, 20, 12, 11, 21, 5],
    [21, 28, 22, 28, 7, 18],
    [18, 18, 19, 25, 8, 25],
    [25, 25, 3, 0, 10, 2],
    [11, 23, 25, 10, 12, 26],
    [4, 28, 21, 17, 28, 24],
]
c = [
    [16, 11, 14, 10, 16, 6],
    [20, 22, 12, 20, 19, 6],
    [25, 18, 3, 8, 13, 2],
    [16, 21, 8, 21, 14, 11],
    [8, 18, 5, 1, 26, 5],
    [2, 27, 8, 2, 26, 14],
    [18, 15, 11, 14, 1, 6],
    [14, 21, 18, 2, 25, 24],
]
'''
#sage
ciphertext = [
    [14, 2, 15, 20, 7, 13],
    [20, 20, 6, 12, 13, 11],
    [0, 20, 10, 22, 28, 10],
    [13, 18, 3, 22, 4, 22],
    [5, 11, 3, 16, 6, 16],
    [6, 10, 25, 22, 22, 25],
    [18, 20, 6, 27, 8, 5],
    [5, 20, 19, 13, 3, 12],
    [3, 20, 0, 7, 17, 13],
    [17, 21, 7, 19, 7, 7],
    [25, 8, 10, 22, 6, 6],
    [13, 27, 18, 3, 20, 1],
]
c=matrix(Zmod(p),ciphertext)
key = matrix(Zmod(p),key1)
ls = string.ascii_uppercase + '_.*'
def mat2str(mat):
    s = ""
    for i in range(len(mat) * 6):
        s += ls[mat[i // 6][i % 6]]
    return s
m=[[24, 14, 20, 26 ,10, 13],
[14, 22 ,26, 19 , 7 , 4],
[26, 12 ,24 ,18 ,19 , 4],
[17 ,24 ,26 ,14 , 5, 26],
[19 , 7 , 4 ,26 ,12 , 0],
[19 ,17 , 8, 23 ,28 ,28],
[ 1, 20 ,19, 26 ,19 , 7],
[ 8, 18 ,26 , 8 ,18, 26],
[ 1,  4 , 6,  8 ,13, 13],
[ 8 ,13 , 6 ,26 ,14 , 5],
[26 , 2 ,17 ,24, 15, 19],
[14 ,11, 14 , 6 ,24, 27]]
m=mat2str(m)
flag = "begin{" + hashlib.md5(m.encode()).hexdigest() + "}"
print(flag)

这个小丑解法仅供大家娱乐，看看就好

别的师傅分享的正经解法如下：https://shinichicun.top/

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
from string import *
import hashlib

def str2mat(s, ff):
    if ff:
        res = matrix(Zmod(p), [[0]*7]*(len(s)//6))
        for i in range(0, len(s)):
            res[i // 6, i % 6] = ls.index(s[i])
        for i in range(len(s)//6):
            res[i, -1] = 1
    else:
        res = matrix([[0]*6]*(len(s)//6))
        for i in range(0, len(s)):
            res[i // 6, i % 6] = ls.index(s[i])
    return res


def mat2str(mat):
    s = ""
    for i in range(len(list(mat))*6):
        s += ls[mat[i // 6, i % 6]]
    return s


ls = ascii_uppercase + '_.*'
p = 29
m = "VOWAS*TED.AE_UMLVFV*W*HSSSTZIZZZDAKCLXZKM_E*VR*Y"
c = "QLOKQGUWMUTGZSDINCQVIVOLISFB_FC.IC_OSPLOBGOVSCZY"
c1 = "MHDTBJSZXLHH.Z.VWGLXUV.SDQUPAMEPNVQVQZX_CBDZHM_IBZRGLJP_YSBDXN.VACLDGCO_"
m = str2mat(m, 1)
c = str2mat(c, 0)
c1 = str2mat(c1, 0)
k = m.solve_right(c)
k2 = matrix(Zmod(p), [list(k[-1])]*len(list(c1)))
k1 = k[:-1].inverse()
m = (c1-k2) * k1
print(mat2str(m))

本文标题:BeginCTF Crypto WP

文章作者:

发布时间:2024年02月06日 - 23时43分

最后更新:2024年02月07日 - 00时24分

原始链接:https://averbeih.github.io/2024/02/06/BeginCTF-Crypto-WP/

许可协议: "署名-非商用-相同方式共享 3.0" 转载请保留原文链接及作者。

文章目录
  1. 1. baby_classic
  • task
    • ,