Parity_RSA 二分法攻击

First Post:

Last Update:

Word Count:
990

Read Time:
5 min

Parity_RSA

[QCTF] baby_rsa

Analyze

先看题：

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

table = string.ascii_letters + string.digits
menu = b'''
Give me your information and I'll tell you about the parity after decryption.
Let me see your options...
1.encrypt message
2.get flag
3.exit
'''
e = 0x10001
p = getPrime(512)
q = getPrime(512)
N = p * q
phi = (p - 1) * (q - 1)
d = inverse(e, phi)

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(12)])).encode()
        sha = sha256(proof).hexdigest().encode()
        self.send(b"[+] sha256(XXXX+" + proof[4:] + b") == " + sha)
        XXXX = self.recv(prompt=b'[+] Give Me XXXX :')
        if len(XXXX) != 4 or sha256(XXXX + proof[4:]).hexdigest().encode() != sha:
            return False
        return True

    def handle(self):
        print(1)
        signal.alarm(2400)
        if not self.proof_of_work():
            self.send(b'bye~')
            return

        self.send(menu)
        self.send(('e = ' + hex(e)).encode())
        self.send(('N = ' + hex(N)).encode())
        while True:
            num = self.recv(prompt=b'what\'s your choise?')
            if num == b'1':
                c = int(self.recv(prompt=b'the message:').decode(), 16)
                m = pow(c, d, N)
                if m % 2:
                    self.send(b'odd...')
                if m % 2 == 0:
                    self.send(b'even...')
            elif num == b'2':
                c = pow(bytes_to_long(flag, e, N))
                self.send(('c = ' + hex(c)).encode())
            elif num == b'3':
                self.send(b'bye~')
                return
            else:
                return
        

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


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


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

先nc一下题目提供的端口：

1
2
3
4
5
6
ncat scr1w.dlut.edu.cn 28088

#Output:
#[+] sha256(XXXX+iemdocJd) == 419017b5ab02fca75dc806b09ce4bbec1fafe03292d5e17a54551cb2d00b7f40
#[+] Give Me XXXX :

简单的sha256爆破：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from pwn import *
from hashlib import sha256
from gmpy2 import *
def break_sha(last, shav):
    s = string.ascii_letters + string.digits
    for v1 in s:
        for v2 in s:
            for v3 in s:
                for v4 in s:
                    t = (v1 + v2 + v3 + v4).encode() + last
                    if sha256(t).hexdigest() == shav:
                        return (v1 + v2 + v3 + v4).encode()
s1=b'iemdocJd'
s2=b'ee2571d3f23fb615fdbe01cea04a20352920f0b02c65e06fc14aa71cb20067e1'
print(break_sha(s1,s2.decode()))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#Output:
#Give me your information and I'll tell you about the parity after decryption.
#Let me see your options...
#1.encrypt message
#2.get flag
#3.exit
#
#e = 0x10001
#N = #0xab068236ae895f50991b85a495b05cab628f23408c6847aa19cb91e6b22e5b1a4e67d1c99b36f53da55230a26b496cb60a5092c728a24ffc0e5a195a456481f1e4c82512af6b8003e092045aa0b3dc79c4d12beea95729e6c1fce16215e0ef47d77bb3dc7417006a16af9b88841627c4462608af4e6d4fa8f369d126cf8bbad9
#what's your choise?

#Input:
#2

#Output:
#c = 0x5fff63ca6bbf96b571128a2502bee3de7be1be0cb84e6f70c2750aaf174475335e0cb59a54a2811154b2c76dd01a2a05660b5485efbfc956d05f254b9fbac53644eea31ea59cc8a8782b4618558aeff0129d85d24dbc0adf431d0929a26803035cff7a2cbc7da52c4dee682078d46e15c2849898fa3defbc700c5878314ae646

通过输入一个加密的密文，服务器会告诉你用私钥d解密该密文后，所得的明文结果是even还是odd，通过这种机制，我们可以向服务器传入的值进行一些修改操作，我们传入 即 为，而服务器会将解密成后告诉我们其模下的奇偶性。即为，而服务器会将解密成后告诉我们其模下的奇偶性。即为，而服务器会将解密成后告诉我们其模下的奇偶性。

我们知道任意一个自然数,其与的乘积一定为偶数，所以在下：

若，即解密后的传入参数没有经过取模操作的话,那么其奇偶性一定为even，因为为偶数

若，即解密后的传入参数经过了取模操作，那么其奇偶性一定为odd，因为为偶数，为奇数

根据上面两点我们可以得到以下结论：

若返回even，则

若返回odd，即

通过返回的结果，我们可以将明文所在的缩小到原来范围的，若我们继续传入，则可将范围再次缩小

如此进行下去，我们只需要次即可得到

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 hashlib import sha256
from gmpy2 import *
from Crypto.Util.number import *

e = 0x10001
n = 0x93022347fcf4a51c3a62dc83e93f4dc91dc6331b5541cd912fd7e0891a8419ce77fce50220cff791d9d7ca4f3af19531a3358a0301f85f284441a4ea9b38c84aa7901a11c9f6a5d6305933635294197d2f6cd63f9649ca9669a766e7f802a668d9b265d30fe8b657d369919ad278c52de26fac04e42f750999cce7dd6eb75a0f
c = 0xec722e27f20c32794072fa699c7a657bee39134accd623166c785a8e44f22a5523274f68eda3c75a5117ddc9cc13fcfd611a4971530a6e6bf166b3cfdf7e92fd943c17d8b25990bfe24bc7718232789e4e2126b08d7117b4c90aa0702ef83d9cf98583f02c819676535e60c84f918dec8cd57a39dbf2d5a62924339cc00f665

def break_sha(last, shav):
    s = string.ascii_letters + string.digits
    for v1 in s:
        for v2 in s:
            for v3 in s:
                for v4 in s:
                    t = (v1 + v2 + v3 + v4).encode() + last
                    if sha256(t).hexdigest() == shav:
                        return (v1 + v2 + v3 + v4).encode()

ldata=0
rdata=n
num=0
io = remote("scr1w.dlut.edu.cn", 28092)
io.recvuntil(b'sha256(XXXX+')
str1 = io.recvuntil(b')', drop=True)
print(str1)
io.recvuntil(b'== ')
str2 = io.recvuntil(b'\n', drop=True)
print(str2)
res = break_sha(str1, str2.decode())
print(res)
io.recvuntil(b'[+] Give Me XXXX :')
io.sendline(res)

while rdata-ldata>2:
    num+=1
    t=powmod(2,num*e,n)
    data=hex((c*t)%n)[2:]

    io.recvuntil(b"what's your choise?")
    io.sendline(b'1')
    # io.recvuntil(b'the message:')
    io.recv()
    io.sendline(data)
    ans=io.recvline()
    print(ans)
    if ans==b'odd...\n':
        ldata = (ldata + rdata) // 2 if (ldata + rdata) % 2 == 0 else (ldata + rdata) // 2 + 1
    elif ans==b'even...\n':
        rdata = (ldata + rdata) // 2 if (ldata + rdata) % 2 == 0 else (ldata + rdata) // 2 + 1
    print(rdata-ldata)
    # print(ldata,rdata)

# while powmod(ldata,e,n)!=c:
#     ldata-=1
print("l=",ldata)
print("r=",rdata)
print(long_to_bytes(ldata))
reward
Alipay
Wechat
≡