Bxb0's blog

一些基本的密码题

Posted on In
Symbols count in article: 5.1k Reading time ≈ 5 mins.

一些基本的密码题。

hill-cipher

考点：hill、a Known Plaintext Attack

题目给到的：

1
2
3
4
5
密文：bbcbp_zqrafjq}ehowmdw{jifop_y_wo_hqoaoetavcicwdadgoafkatlkuf

alphabet：{}abcdefghijklmnopqrstuvwxyz_

flag格式：securinets{

知道此题hill密码及flag格式，那很明显就是 a Known Plaintext Attack

首先对于hill密码，它的实质就是一种矩阵的乘法，而矩阵的乘法是分为很多阶的，因此hill密码也是有多阶的。

1
2
3
(密钥矩阵 ✖ 明文矩阵)mod n = 密文矩阵

n是alphabet表的大小

比如三阶hill密码，密钥是k，明文是p1p2p3

image-20220308220518604

矩阵相乘后再模n

对于此题，由于明文长度是11，因此对于a Known Plaintext Attack，它的密钥矩阵只可能是二阶或三阶，因为如果密钥是四阶的话我们必须知道16个字节的明文才行。

所以我们分别尝试一下二阶与三阶来求解出对应的密钥，再利用其解密一下后面的密文以此来看密钥是否正确。

由于numpy库没有提供求一个模内矩阵的逆的方法，自己算还是挺麻烦的，但我们可以使用 cryptonita.mod 库中的inv_matrix方法。

下面是分别尝试此题二阶和三阶密钥的过程，在尝试三阶时发现密钥正确：（即下面中将求出的三阶密钥来解密C1，发现解出的P1的前2个字节和已知的明文一致。）

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
>>> from cryptonita.mod import inv_matrix
>>> enc = "bbcbp_zqrafjq}ehowmdw{jifop_y_wo_hqoaoetavcicwdadgoafkatlkuf"
>>> table = "{}abcdefghijklmnopqrstuvwxyz_"
>>> p = "securinets{"
>>> m = len(table)
>>> enc_index = [table.index(i) for i in enc]
>>> p_index = [table.index(i) for i in p]
>>> enc_index
[3, 3, 4, 3, 17, 28, 27, 18, 19, 2, 7, 11, 18, 1, 6, 9, 16, 24, 14, 5, 24, 0, 11, 10, 7, 16, 17, 28, 26, 28, 24, 16, 28, 9, 18, 16, 2, 16, 6, 21, 2, 23, 4, 10, 4, 24, 5, 2, 5, 8, 16, 2, 7, 12, 2, 21, 13, 12, 22, 7]
>>> p_index
[20, 6, 4, 22, 19, 10, 15, 6, 21, 20, 0]
>>> import numpy as np
>>> P = np.array([20, 6, 4, 22]).reshape(2, 2).T
>>> P
array([[20,  4],
       [ 6, 22]])
>>> C = np.array([3, 3, 4, 3]).reshape(2, 2).T
>>> C
array([[3, 4],
       [3, 3]])
>>> iC = inv_matrix(C, m)
>>> iC
array([[28, 11],
       [ 1, 28]], dtype=int32)
>>> iK = np.dot(P, iC)
>>> iK = np.dot(P, iC)%m
>>> iK
array([[13, 13],
       [16, 15]], dtype=int32)
>>> C1 = np.array([17, 28, 27, 18]).reshape(2, 2).T
>>> P1 = np.dot(iK, C1)%m
>>> P1
array([[ 5,  5],
       [25,  6]], dtype=int32)
>>> P0 = np.dot(iK, C)%m
>>> P0
array([[20,  4],
       [ 6, 22]], dtype=int32)
>>> P = np.array(enc_index[:9]).reshape(3, 3).T
>>> P
array([[ 3,  3, 27],
       [ 3, 17, 18],
       [ 4, 28, 19]])
>>> C = np.array(p_index[:9]).reshape(3, 3).T
>>> C
array([[20, 22, 15],
       [ 6, 19,  6],
       [ 4, 10, 21]])
>>> iC = inv_matrix(C, m)
>>> iC
array([[ 5,  9, 27],
       [18,  3,  7],
       [25,  1,  4]], dtype=int32)
>>> iK = np.dot(P, iC)%m
>>> iK
array([[19,  5,  7],
       [17,  9, 11],
       [13, 23,  3]], dtype=int32)
>>> P0 = np.dot(iK, C)%m
>>> P0
array([[ 3,  3, 27],
       [ 3, 17, 18],
       [ 4, 28, 19]], dtype=int32)
>>> P
array([[ 3,  3, 27],
       [ 3, 17, 18],
       [ 4, 28, 19]])
>>> C1 = np.array(enc_index[9:18]).reshape(3, 3).T
>>> C1
array([[ 2, 18,  9],
       [ 7,  1, 16],
       [11,  6, 24]])
>>> P1 = np.dot(iK, C1)%m
>>> P1
array([[ 5, 12, 13],
       [15,  4, 10],
       [17, 14,  6]], dtype=int32)
>>> len(p_index)
11
>>> P = np.array(p_index[:9]).reshape(3, 3).T
>>> C = np.array(enc_index[:9]).reshape(3, 3).T
>>> iC = inv_matrix(C, m)
>>> iK = np.dot(P, iC)%m
>>> iK
array([[26, 14,  4],
       [12, 17, 16],
       [ 8, 12, 15]], dtype=int32)
>>> P0 = np.dot(iK, C)%m
>>> P
array([[20, 22, 15],
       [ 6, 19,  6],
       [ 4, 10, 21]])
>>> P0
array([[20, 22, 15],
       [ 6, 19,  6],
       [ 4, 10, 21]], dtype=int32)
>>> p_index
[20, 6, 4, 22, 19, 10, 15, 6, 21, 20, 0]
>>> C1 = np.array(enc_index[9:18]).reshape(3, 3).T
>>> P1 = np.dot(iK, C1)%m
>>> P1
array([[20, 13,  3],
       [ 0, 10, 10],
       [ 4, 14, 15]], dtype=int32)
>>> iK = np.array([[26, 14,  4], [12, 17, 16], [8, 12, 15]])

得到密钥矩阵后，解密所有密文：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import numpy as np
from cryptonita.mod import inv_matrix

ik = [[26, 14, 4], [12, 17, 16], [8, 12, 15]]
enc = "bbcbp_zqrafjq}ehowmdw{jifop_y_wo_hqoaoetavcicwdadgoafkatlkuf"
table = "{}abcdefghijklmnopqrstuvwxyz_"
enc_index = [table.index(i) for i in enc]
m = len(table)
flag = ''

for i in range(0, len(enc_index), 3):
    for j in range(3):
        tmp = 0
        for k in range(3):
            tmp += ik[j][k]*enc_index[i+k]
            tmp %= m
        flag += table[tmp]    
print(flag)

Daredevil’s server

考点：rsa、签名的基本原理

nc连上后，有几个选项，如下是其中加密函数选项得到的：

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
TOKEN = b'd4r3d3v!l'
def chall():
    s = Sign()
    while True:
        choice = input("> ").rstrip()
        if choice == 'P':
            print("\nN : {}".format(hex(s.n)))
            print("\ne : {}".format(hex(s.e)))
        elif choice == 'S':
            try:
                msg = bytes.fromhex(input('msg to sign : '))
                if TOKEN in msg:
                    print('[!] NOT ALLOWED')
                else:
                    m = bytes_to_long(msg)
                    print("\nsignature : {}".format(hex(s.sign(m))))      #pow(msg,d,n)
                    print('\n')
            except:
                print('\n[!] ERROR (invalid input)')
                
        elif choice == 'V':
            try:

                msg = bytes.fromhex(input("msg : "))
                m = bytes_to_long(msg)
                signature = int(input("signature : "),16)
                if m < 0 or m > s.n:
                    print('[!] ERROR')
                
                if s.verify(m, signature):                           #pow(sign, e, n) == msg
                    if long_to_bytes(m) == TOKEN:
                        print(SECRET)
                
                    else:
                        print('\n[+] Valid signature')
                       
                else:
                    print('\n[!]Invalid signature')
   
            except:
                print('\n[!] ERROR(invalid input)')


        elif choice == 'Q':
            print('OK BYE :)')
            exit(0)
        else:
            print('\n[*] SEE OPTIONS')

如上可以知道：P是得到此rsa签名使用的N和e；S是我们输入一个消息返回其签名值，V输入一个消息及其签名值，判断此消息与签名值是否是对应的，如对应且输入的消息是：b’d4r3d3v!l’ 那就输出flag。

我们知道签名是私钥签名，公钥验证，此题我们关键就是要得到 b’d4r3d3v!l’ 消息的签名值，但S选项中有一个判断，如果输入的消息是 b’d4r3d3v!l’ 则不给签名，因此我们的目的就是绕过这里。

如何绕呢？

就是输入一个和 b’d4r3d3v!l’ 不一样的消息，但他们经过此rsa签名后的签名值相同。

假设输入的消息是m，那我们输入 m*(N+1) 的签名值和m就是一样的了。

由二项式定理：

image-20220308224057165

那么 (N+1)^d = (N…. + 1) = 1

image-20220308223318114

所以，我们输入 m*(N+1) 在S中进行签名，再将签名值在V中验证就得到flag了。

-------------本文结束感谢您的阅读-------------