ctf
November 1, 2021

WriteUps of crypto chals in 东华杯2021

我在东华杯出的几道题目…

The_RSA

「Description」

我的加密系统有可能有点点问题。

「SourceCode」

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
from Crypto.Util.number import*
from hashlib import sha256
import socketserver
import signal
import string
import random
from secret import flag

table = string.ascii_letters+string.digits
flag = bytes_to_long(flag)

MENU = br'''[+] 1.Get Encrypt:
[+] 2.Exit:
'''

class Task(socketserver.BaseRequestHandler):
    def _recvall(self):
        BUFF_SIZE = 2048
        data = b''
        while True:
            part = self.request.recv(BUFF_SIZE)
            data += part
            if len(part) < BUFF_SIZE:
                break
        return data.strip()

    def send(self, msg, newline=True):
        try:
            if newline:
                msg += b'\n'
            self.request.sendall(msg)
        except:
            pass

    def recv(self, prompt=b'[-] '):
        self.send(prompt, newline=False)
        return self._recvall()

    def proof_of_work(self):
        proof = (''.join([random.choice(table)for _ in range(20)])).encode()
        sha = sha256( proof ).hexdigest().encode()
        self.send(b"[+] sha256(XXXX+" + proof[4:] + b") == " + sha )
        XXXX = self.recv(prompt = b'[+] Plz Tell Me XXXX :')
        if len(XXXX) != 4 or sha256(XXXX + proof[4:]).hexdigest().encode() != sha:
            return False
        return True

    def EncRy(self):
        p,q = getPrime(512),getPrime(512)
        n = p * q
        phi = (p - 1) * (q - 1)
        e = inverse(self.d, phi)
        c = pow(flag, e, n)
        return(e,n,c)

    def handle(self):
        signal.alarm(60)
        if not self.proof_of_work():
            return
        self.send(b"Welcome to my RSA!")
        self.d = getPrime(random.randint(435, 436))

        while 1:
            self.send(MENU)
            self.send(b"Now!What do you want to do?")
            option = self.recv()
            if option == b'1':
                self.send(str(self.EncRy()).encode())
            else:
                break

        self.request.close()

class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass

class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass

if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 10004
    print("HOST:POST " + HOST+":" + str(PORT))
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

「Analyze」

题目给出 [task.py] ，在 handle 部分即定义一个435位的素数 并把它用作 RSA 的私钥，由此去生成 RSA 之中的所有参数，并对flag进行加密，给出每组加密使用的公钥 以及对应的密文

可以发现所有的密文都是通过 去产生实现的，于是可以通过以下式子(1) 去构造格(2) ，LLL之后就能够拿到目标向量(3)

接着根据闵科夫斯基定理去计算大概需要几条拿到SVP，即想要得到的私钥 ，发现需要10组数据即可。

「Exp」

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
from Crypto.Util.number import*
import gmpy2
from pwn import *
from hashlib import sha256
import string
from pwnlib.util.iters import mbruteforce

table = string.ascii_letters+string.digits
def pow():
    io.recvuntil("XXXX+")
    suffix = io.recv(16).decode("utf8")
    io.recvuntil("== ")
    cipher = io.recvline().strip().decode("utf8")
    proof = mbruteforce(lambda x: sha256((x + suffix).encode()).hexdigest() ==
                        cipher, table, length=4, method='fixed')
    io.sendlineafter("XXXX :", proof) 

io = remote("0.0.0.0",10004)
pow()
io.interactive()

e0,n0,c0 = 
e1,n1,c1 = 
e2,n2,c2 = 
e3,n3,c3 = 
e4,n4,c4 = 
e5,n5,c5 = 
e6,n6,c6 = 
e7,n7,c7 = 
e8,n8,c8 = 
e9,n9,c9 = 

maxN = max(n0,n1,n2,n3,n4,n5,n6,n7,n8,n9)
M = gmpy2.iroot(maxN,2)[0]
from sage.all import*
L = Matrix(ZZ,[[M,e0,e1,e2,e3,e4,e5,e6,e7,e8,e9],
               [0,-n0,0,0,0,0,0,0,0,0,0],
               [0,0,-n1,0,0,0,0,0,0,0,0],
               [0,0,0,-n2,0,0,0,0,0,0,0],
               [0,0,0,0,-n3,0,0,0,0,0,0],
               [0,0,0,0,0,-n4,0,0,0,0,0],
               [0,0,0,0,0,0,-n5,0,0,0,0],
               [0,0,0,0,0,0,0,-n6,0,0,0],
               [0,0,0,0,0,0,0,0,-n7,0,0],
               [0,0,0,0,0,0,0,0,0,-n8,0],
               [0,0,0,0,0,0,0,0,0,0,-n9]])
v = L.LLL()[0]
d = v[0]//M

m = long_to_bytes(pow(c0,d,n0))
print(m)

BlockEncrypt

「Description」

你能猜猜看我的flag是什么吗

「SourceCode」

[task.py]

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
from Crypto.Util.number import*
from Crypto.Cipher import AES
from secret import flag
from my_encrypt import block_encrypt
from hashlib import sha256
import socketserver
import signal
import string
import random
import os

table = string.ascii_letters+string.digits

MENU = br'''[+] 1.Encrypt the Flag:
[+] 2.Encrypt your Plaintext:
[+] 3.Exit:
'''

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

def xor(msg1,msg2):
    assert len(msg1)==len(msg2)
    return long_to_bytes(bytes_to_long(msg1)^bytes_to_long(msg2))

class Task(socketserver.BaseRequestHandler):
    def _recvall(self):
        BUFF_SIZE = 2048
        data = b''
        while True:
            part = self.request.recv(BUFF_SIZE)
            data += part
            if len(part) < BUFF_SIZE:
                break
        return data.strip()

    def send(self, msg, newline=True):
        try:
            if newline:
                msg += b'\n'
            self.request.sendall(msg)
        except:
            pass

    def recv(self, prompt=b'[-] '):
        self.send(prompt, newline=False)
        return self._recvall()

    def proof_of_work(self):
        proof = (''.join([random.choice(table)for _ in range(20)])).encode()
        sha = sha256( proof ).hexdigest().encode()
        self.send(b"[+] sha256(XXXX+" + proof[4:] + b") == " + sha )
        XXXX = self.recv(prompt = b'[+] Plz Tell Me XXXX :')
        if len(XXXX) != 4 or sha256(XXXX + proof[4:]).hexdigest().encode() != sha:
            return False
        return True


    def enc_msg(self,msg):
        return block_encrypt(pad(msg),self.key,self.ivv)

    def handle(self):
        signal.alarm(50)
        if not self.proof_of_work():
            return
        self.ivv = os.urandom(16)
        self.key = os.urandom(16)
        while 1:
            self.send(MENU,newline = False)
            option = self.recv()

            if (option == b'1'):
                self.send(b"My Encrypted flag is:")
                self.send(self.enc_msg(flag))

            elif option == b'2':
                self.send(b"Give me Your Plain & I'll give you the Cipher.")
                plaintext = self.recv()
                self.send(b'PlainText:' + plaintext + b'\nCipherText:' + self.enc_msg(plaintext))
            else:
                break
        self.send(b"\n[.]Down the Connection.")
        self.request.close()

class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass

class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass

if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 10004
    print("HOST:POST " + HOST+":" + str(PORT))
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

[my_encrypt.py]

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
from Crypto.Util.number import *
Sbox = (
    0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
    0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
    0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
    0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
    0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
    0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
    0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
    0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
    0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
    0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
    0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
    0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
    0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
    0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
    0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
    0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16,
)

InvSbox = (
    0x52, 0x09, 0x6A, 0xD5, 0x30, 0x36, 0xA5, 0x38, 0xBF, 0x40, 0xA3, 0x9E, 0x81, 0xF3, 0xD7, 0xFB,
    0x7C, 0xE3, 0x39, 0x82, 0x9B, 0x2F, 0xFF, 0x87, 0x34, 0x8E, 0x43, 0x44, 0xC4, 0xDE, 0xE9, 0xCB,
    0x54, 0x7B, 0x94, 0x32, 0xA6, 0xC2, 0x23, 0x3D, 0xEE, 0x4C, 0x95, 0x0B, 0x42, 0xFA, 0xC3, 0x4E,
    0x08, 0x2E, 0xA1, 0x66, 0x28, 0xD9, 0x24, 0xB2, 0x76, 0x5B, 0xA2, 0x49, 0x6D, 0x8B, 0xD1, 0x25,
    0x72, 0xF8, 0xF6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xD4, 0xA4, 0x5C, 0xCC, 0x5D, 0x65, 0xB6, 0x92,
    0x6C, 0x70, 0x48, 0x50, 0xFD, 0xED, 0xB9, 0xDA, 0x5E, 0x15, 0x46, 0x57, 0xA7, 0x8D, 0x9D, 0x84,
    0x90, 0xD8, 0xAB, 0x00, 0x8C, 0xBC, 0xD3, 0x0A, 0xF7, 0xE4, 0x58, 0x05, 0xB8, 0xB3, 0x45, 0x06,
    0xD0, 0x2C, 0x1E, 0x8F, 0xCA, 0x3F, 0x0F, 0x02, 0xC1, 0xAF, 0xBD, 0x03, 0x01, 0x13, 0x8A, 0x6B,
    0x3A, 0x91, 0x11, 0x41, 0x4F, 0x67, 0xDC, 0xEA, 0x97, 0xF2, 0xCF, 0xCE, 0xF0, 0xB4, 0xE6, 0x73,
    0x96, 0xAC, 0x74, 0x22, 0xE7, 0xAD, 0x35, 0x85, 0xE2, 0xF9, 0x37, 0xE8, 0x1C, 0x75, 0xDF, 0x6E,
    0x47, 0xF1, 0x1A, 0x71, 0x1D, 0x29, 0xC5, 0x89, 0x6F, 0xB7, 0x62, 0x0E, 0xAA, 0x18, 0xBE, 0x1B,
    0xFC, 0x56, 0x3E, 0x4B, 0xC6, 0xD2, 0x79, 0x20, 0x9A, 0xDB, 0xC0, 0xFE, 0x78, 0xCD, 0x5A, 0xF4,
    0x1F, 0xDD, 0xA8, 0x33, 0x88, 0x07, 0xC7, 0x31, 0xB1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xEC, 0x5F,
    0x60, 0x51, 0x7F, 0xA9, 0x19, 0xB5, 0x4A, 0x0D, 0x2D, 0xE5, 0x7A, 0x9F, 0x93, 0xC9, 0x9C, 0xEF,
    0xA0, 0xE0, 0x3B, 0x4D, 0xAE, 0x2A, 0xF5, 0xB0, 0xC8, 0xEB, 0xBB, 0x3C, 0x83, 0x53, 0x99, 0x61,
    0x17, 0x2B, 0x04, 0x7E, 0xBA, 0x77, 0xD6, 0x26, 0xE1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0C, 0x7D,
)

xc = lambda a: (((a << 1) ^ 0x1B) & 0xFF) if (a & 0x80) else (a << 1)

R = (
    0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40,
    0x80, 0x1B, 0x36, 0x6C, 0xD8, 0xAB, 0x4D, 0x9A,
    0x2F, 0x5E, 0xBC, 0x63, 0xC6, 0x97, 0x35, 0x6A,
    0xD4, 0xB3, 0x7D, 0xFA, 0xEF, 0xC5, 0x91, 0x39,
)

def t2m(text):
    text = bytes_to_long(text)
    matrix = []
    for i in range(16):
        byte = (text >> (8 * (15 - i))) & 0xFF
        if i % 4 == 0:
            matrix.append([byte])
        else:
            matrix[i // 4].append(byte)
    return matrix


def m2t(matrix):
    text = 0
    for i in range(4):
        for j in range(4):
            text |= (matrix[i][j] << (120 - 8 * (4 * i + j)))
    return long_to_bytes(text)


class myAES:
    def __init__(self, MasterKey):
        self.ChangeKey(MasterKey)

    def ChangeKey(self, MasterKey):
        self.RoundKeys = t2m(MasterKey)
        # print self.RoundKeys

        for i in range(4, 4 * 11):
            self.RoundKeys.append([])
            if i % 4 == 0:
                byte = self.RoundKeys[i - 4][0]        \
                     ^ Sbox[self.RoundKeys[i - 1][1]]  \
                     ^ R[i // 4]
                self.RoundKeys[i].append(byte)

                for j in range(1, 4):
                    byte = self.RoundKeys[i - 4][j]    \
                         ^ Sbox[self.RoundKeys[i - 1][(j + 1) % 4]]
                    self.RoundKeys[i].append(byte)
            else:
                for j in range(4):
                    byte = self.RoundKeys[i - 4][j]    \
                         ^ self.RoundKeys[i - 1][j]
                    self.RoundKeys[i].append(byte)

        # print self.RoundKeys

    def encrypt(self, plaintext):
        self.plain_state = t2m(plaintext)

        self.__add_round_key(self.plain_state, self.RoundKeys[:4])

        for i in range(1, 10):
            self.__round_encrypt(self.plain_state, self.RoundKeys[4 * i : 4 * (i + 1)])

        self.__sub_bytes(self.plain_state)
        self.__shift_rows(self.plain_state)
        self.__sub_bytes(self.plain_state)
        self.__add_round_key(self.plain_state, self.RoundKeys[40:])

        return m2t(self.plain_state)

    def __add_round_key(self, s, k):
        for i in range(4):
            for j in range(4):
                s[i][j] ^= k[i][j]

    def __round_encrypt(self, state_matrix, key_matrix):
        self.__sub_bytes(state_matrix)
        self.__shift_rows(state_matrix)
        self.__mix_columns(state_matrix)
        self.__add_round_key(state_matrix, key_matrix)

    def __sub_bytes(self, s):
        for i in range(4):
            for j in range(4):
                s[i][j] = Sbox[s[i][j]]

    def __shift_rows(self, s):
        s[0][1], s[1][1], s[2][1], s[3][1] = s[1][1], s[2][1], s[3][1], s[0][1]
        s[0][2], s[1][2], s[2][2], s[3][2] = s[2][2], s[3][2], s[0][2], s[1][2]
        s[0][3], s[1][3], s[2][3], s[3][3] = s[3][3], s[0][3], s[1][3], s[2][3]

    def __mix_single_column(self, a):
        # please see Sec 4.1.2 in The Design of Rijndael
        t = a[0] ^ a[1] ^ a[2] ^ a[3]
        u = a[0]
        a[0] ^= t ^ xc(a[0] ^ a[1])
        a[1] ^= t ^ xc(a[1] ^ a[2])
        a[2] ^= t ^ xc(a[2] ^ a[3])
        a[3] ^= t ^ xc(a[3] ^ u)

    def __mix_columns(self, s):
        for i in range(4):
            self.__mix_single_column(s[i])

def xor(a,b):
    assert len(a) == len(b)
    tmp = []
    for i in range(len(a)):
        tmp.append(a[i]^b[i])
    return bytes(tmp)

def exchange_plain(plaintext):
    new_plain = []
    for i in plaintext:
        new_plain.append(i<<1)
    new_plain = bytes(new_plain)
    return new_plain

def block_encrypt(plaintext,key,iv):
    aes = myAES(key)
    block = len(plaintext)//16
    new_plain = exchange_plain(plaintext)
    cipher = b''
    for i in range(block):
        iv = aes.encrypt(iv) 
        cipher += xor(iv,new_plain[16*i:16*i+16])
    return cipher

「Analyze」

针对题目给出附件有my_encrypt.pyc，只不过是python3.9的，不是很好反编译完全，在线网站只能够反编译得到大概，但看不到对block_encrypt以及exchange_plain中for循环内部的信息。

但是这道题，给出的块加密使用的key和iv都是在初始化阶段内容中就已经固定了的，在一次连接之中不会更改，那么其实我们就可以去猜这种特征的加密模式会有什么样的漏洞。倘若是OFB模式又或者是CFB模式，根据CTF-Wiki上这张图

img

我们就可以得知，是将IV加密之后在与明文异或，但是下一轮的IV是上一轮IV加密后的内容，那么，我们就可以通过这个弱点，将其攻破，任意密文解密。

而该道题，我们可以看到一个exchange_plain这个函数，那么他应该会是对明文进行操作改变，但是我们并不知道如何操作，只能去一个个试，猜出来他是针对明文每一个字节都左移了1位，那么，我们就可以尝试解密flag了，只要长度足够的进行已知明文攻击，就可以拿到加密过后的每组IV，与加密后的flag进行异或之后进行明文恢复操作就可以拿到flag.

「Exp」

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
from pwn import *
from Crypto.Util.number import *
from hashlib import sha256
import string
from pwnlib.util.iters import mbruteforce

table = string.ascii_letters+string.digits
def pow():
    io.recvuntil("XXXX+")
    suffix = io.recv(16).decode("utf8")
    io.recvuntil("== ")
    cipher = io.recvline().strip().decode("utf8")
    proof = mbruteforce(lambda x: sha256((x + suffix).encode()).hexdigest() ==
                        cipher, table, length=4, method='fixed')
    io.sendlineafter("XXXX :", proof) 

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

def enc(plaintext):
    print(io.recvuntil(b'[-]').decode())
    io.sendline(b"2")
    print(io.recvuntil(b'[-] ').decode())
    io.sendline(plaintext)
    io.recvuntil(b"CipherText:")
    c = io.recvuntil(b'[+]')[:-4]
    return c

def xor(msg1,msg2):
    assert len(msg1)==len(msg2)
    return long_to_bytes(bytes_to_long(msg1)^bytes_to_long(msg2))

if __name__ == "__main__":
    io = remote("127.0.0.1",10004)
    pow()
    print(io.recvuntil(b'[-] ').decode())
    io.sendline(b"1")
    print(io.recvuntil(b"My Encrypted flag is:").decode())
    c = io.recvuntil(b'[+]')[1:-4]

    cipherlen = len(c) - 1
    fakeplain = cipherlen * b'\x01'
    blocksize = cipherlen//16
    newcipher = enc(fakeplain)
    fakeplain = pad(fakeplain)
    new_plain = []
    for i in fakeplain:
        new_plain.append((i)<<1)
    new_plain = bytes(new_plain)
    s = (xor(new_plain,newcipher[:]))

    fakeplain2 = (xor(s,c))
    new_plain = []
    for i in fakeplain2:
        new_plain.append((i)>>1)
    new_plain = bytes(new_plain)
    print(new_plain)

MyCryptoSystem

「Description」

再来看看这个加密系统吧

「SourceCode」

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
from Crypto.Util.number import*
import random
from secret import flag
from hashlib import sha256
import socketserver
import signal
import string

def trans_flag(flag):
    new_flag = []
    for i in range(6):
        new_flag.append(bytes_to_long(flag[i*7:i*7+7]))
    return new_flag

kbits = 1024
table = string.ascii_letters+string.digits
flag = trans_flag(flag)

def Setup(kbits):
    p_bit = kbits//2
    q_bit = kbits - p_bit
    while 1:
        p = getPrime(p_bit)
        p_tmp = (p-1)//2
        if isPrime(p_tmp):
            break
    while 1:
        q = getPrime(q_bit)
        q_tmp = (q-1)//2
        if isPrime(q_tmp):
            break
    N = p*q
    while 1:
        g = random.randrange(N*N)
        if (pow(g,p_tmp * q_tmp,N*N) - 1)%N == 0 and  (pow(g,p_tmp * q_tmp,N*N) - 1)//N >= 1 and (pow(g,p_tmp * q_tmp,N*N) - 1)//N <= N - 1:
            break
    public = (N,g)
    return public,p

def KeyGen(public):
    N,g = public
    a = random.randrange(N*N)
    h = pow(g,a,N*N)

    pk = h
    sk = a 

    return pk,sk

def Encrypt(public,pk,m):
    N,g = public
    r = random.randrange(N*N)
    A = pow(g,r,N*N)
    B = (pow(pk,r,N*N) * (1 + m * N)) % (N * N)
    return A,B

def Add(public,dataCipher1,dataCipher2):
    N = public[0]
    A1,B1 = dataCipher1
    A2,B2 = dataCipher2

    A = (A1*A2)%(N*N)
    B = (B1*B2)%(N*N)

    return (A,B)

def hint(p):
    _p = getPrime(2048)
    _q = getPrime(2048)
    n = _p*_q
    e = 0x10001
    s = getPrime(300)
    tmp = (160 * s ** 5 - 4999 * s ** 4 + 3 * s ** 3 +1)

    phi = (_p-1)*(_q-1)
    d = inverse(e,phi)
    k = (_p-s)*d
    enc = pow(p,e,n)
    return (tmp,k,enc,n)

class Task(socketserver.BaseRequestHandler):
    def _recvall(self):
        BUFF_SIZE = 2048
        data = b''
        while True:
            part = self.request.recv(BUFF_SIZE)
            data += part
            if len(part) < BUFF_SIZE:
                break
        return data.strip()

    def send(self, msg, newline=True):
        try:
            if newline:
                msg += b'\n'
            self.request.sendall(msg)
        except:
            pass

    def recv(self, prompt=b'SERVER <INPUT>: '):
        self.send(prompt, newline=False)
        return self._recvall()

    def proof_of_work(self):
        proof = (''.join([random.choice(table)for _ in range(20)])).encode()
        sha = sha256(proof).hexdigest().encode()
        self.send(b"[+] sha256(XXXX+" + proof[4:] + b") == " + sha )
        XXXX = self.recv(prompt = b'[+] Plz Tell Me XXXX :')
        if len(XXXX) != 4 or sha256(XXXX + proof[4:]).hexdigest().encode() != sha:
            return False
        return True

    def handle(self):
        proof = self.proof_of_work()
        if not proof:
            self.request.close()


        public,p = Setup(kbits)
        signal.alarm(60)
        pk = []

        for i in range(6):
            pki,ski = KeyGen(public)
            pk.append(pki)

        msg = [123,456,789,123,456,789]
        CipherPair = []
        for i in range(len(pk)):
            TMP = Encrypt(public,pk[i],msg[i])
            CipherPair.append(((TMP),pk[i]))

        CipherDate = []
        for i in range(len(pk)):
            CipherDate.append(Add(public,Encrypt(public,pk[i],flag[i]),CipherPair[i][0]))

        self.send(b'What do you want to get?\n[1]pk_list\n[2]public_parameters\n[3]hint_for_p\n[4]EncRypt_Flag\n[5]exit')
        while 1:
            option = self.recv()
            if option == b'1':
                self.send(b"[~]My pk_list is:")
                self.send(str(pk).encode())
            elif option == b'2':
                self.send(b"[~]My public_parameters is")
                self.send(str(public).encode())
            elif option == b'3':
                self.send(b"[~]My hint for p is")
                self.send(str(hint(p)).encode())
            elif option == b'4':
                self.send(b'[~]What you want is the flag!')
                self.send(str(CipherDate).encode())
            else:
                break
        self.request.close()

class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass

class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass

if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 10004
    print("HOST:POST " + HOST+":" + str(PORT))
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

「Analyze」

一开始先是将flag每7位 bytes_to_long 之后组成一个flag的list，接着我们将每个重要的主体函数都对应转换成数学公式来看

题目给出MENU有4个选项，其中通过 hint_for_p leak 了 ，通过二分拿到 ，计算 就能够拿到 ，到这里我们可以看出来其实这道题的加密系统很像pallier，这里已经能够分解 了，那么必定是不安全的，虽然说他使用了任意的公钥加密。

paper:https://link.springer.com/content/pdf/10.1007%2Fb94617.pdf (37)

只需要去实现该篇论文中的另外一种解密方式就能够成功解密。

「Exp」

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
from pwn import *
from Crypto.Util.number import *
from hashlib import sha256
import string
from pwnlib.util.iters import mbruteforce

table = string.ascii_letters+string.digits
def pow():
    io.recvuntil("XXXX+")
    suffix = io.recv(16).decode("utf8")
    io.recvuntil("== ")
    cipher = io.recvline().strip().decode("utf8")
    proof = mbruteforce(lambda x: sha256((x + suffix).encode()).hexdigest() ==
                        cipher, table, length=4, method='fixed')
    io.sendlineafter("XXXX :", proof) 

io = remote("0.0.0.0",10004)
pow()
io.interactive()

def getS(data):
    left,right = 0,2**301
    for i in range(1000):
        tmp = (left + right)//2
        if 160 * tmp ** 5 - 4999 * tmp ** 4 + 3 * tmp ** 3 +1-data > 0:
            right = tmp
        else:
            left = tmp
    return tmp
def getP(pdata):
    tmp,k,c,n = pdata
    s = getS(tmp)
    e = 0x10001
    a = pow(3,e*k,n)-pow(3,1-s,n)
    _p = GCD(a,n)
    _q = n//_p
    d = inverse(e,(_p-1)*(_q-1))
    return pow(c,d,n)

pdata = 
pk = 
public = 
p = getP(pdata)

msg = [123,456,789,123,456,789]
secret = (p//2,public[0]//p//2)
k = (pow(public[1],secret[0]*secret[1],public[0]**2)-1) // public[0]
public = public[0],k,public[1]
def MDecrypt(public,pk,secret,A,B):
    p_sec , q_sec = secret
    N,k,g = public
    h = pk
    k_1 = inverse(k,N)
    a = ((((pow(h,p_sec * q_sec,N**2) - 1) % (N**2) )//N )* k_1) % N
    r = ((((pow(A,p_sec * q_sec,N**2) - 1) % (N**2) )//N )* k_1) % N
    delta = pow(p_sec * q_sec ,-1 , N)
    gamma = (a * r) % N 
    m = ((((pow(B * inverse(pow(g,gamma,N **2),N**2),p_sec * q_sec, N ** 2) - 1 ) %(N*N)) // N) * delta )%N
    return m
print(len(pk))
CipherDate = 

for i in range(len(pk)):
    A,B = CipherDate[i]
    print(long_to_bytes(MDecrypt(public,pk[i],secret,A,B)-msg[i]).decode(),end='')

Referance

.pyc在线反编译：https://tool.lu/pyc/

OFB模式：https://wiki.x10sec.org/crypto/blockcipher/mode/ofb/

BCP密码系统：https://link.springer.com/content/pdf/10.1007%2Fb94617.pdf (37)4

About this Post

This post is written by Hao Jiang, licensed under CC BY-NC 4.0.

#ctf#cryptography