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
| from Crypto.Util.number import *
from hashlib import sha256
import socketserver
import signal
import os
import string
import random
from sympy.ntheory.modular import crt
from line_profiler import LineProfiler
flag = os.getenv('DASFLAG')
def euclide_ext(a, b):
x, xx, y, yy = 1, 0, 0, 1
while b:
q = a // b
a, b = b, a % b
x, xx = xx, x - xx * q
y, yy = yy, y - yy * q
return x, y, a
class Montgomery:
n: int
k: int
r: int
r_inv: int
n_inv: int
def __init__(self, n, k):
self.n = n
self.k = k
self.r = 2 ** k
self.r_inv, self.n_inv, gcd = euclide_ext(self.r, self.n)
self.n_inv = -self.n_inv
if gcd != 1:
raise ValueError("gcd(r,n) must be 1")
if self.r * self.r_inv - self.n * self.n_inv != 1:
raise ValueError(
f"For ({self.r} that created from {2} ** {k},{n}) doesn't exists diophantine equation decision"
)
self.r_inv = self.r_inv % self.n
def mon_pro(self, a_n, b_n):
t = a_n * b_n
u = (t + (t * self.n_inv % self.r) * self.n) >> self.k
if u > self.n:
u -= self.n
return u
def mon_exp(self, a: int, e: int):
a = a * self.r % self.n
x = self.r % self.n
for i in reversed(range(0, e.bit_length())):
x= self.mon_pro(x, x)
if (e & (1 << i)) :
x= self.mon_pro(x, a)
return self.mon_pro(x, 1)
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 handle(self):
bits=1024
p=getPrime(bits)
q=getPrime(bits)
e=getPrime(bits-10)
n=p*q
print(p,",",q)
print(flag)
P=Montgomery(p,bits)
Q=Montgomery(q,bits)
self.send(str((n,e)).encode())
signal.alarm(300)
for i in range(600):
lp = LineProfiler()
lp.add_function(Q.mon_pro)
lp_exp = lp(P.mon_exp)
lq_exp = lp(Q.mon_exp)
self.send(b"leave message 4 me",newline=False)
m=int(self.recv())
cp=lp_exp(m,e)
cq=lq_exp(m,e)
c=crt([p,q],[cp,cq])
d={}
for i in lp.code_map:
for j in lp.code_map[i]:
d[j]=(lp.code_map[i][j]['total_time'],lp.code_map[i][j]['nhits'])
self.send(str(d).encode())
self.send(b"can you break me?",newline=False)
guess=int(self.recv())
if guess in {p,q}:
self.send(flag.encode())
else:
self.send(b"sorry~")
exit
class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
pass
class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
pass
if __name__ == "__main__":
HOST, PORT = '0.0.0.0', 9999
print("HOST:POST " + HOST+":" + str(PORT))
server = ForkedServer((HOST, PORT), Task)
server.allow_reuse_address = True
server.serve_forever()
|