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
| from random import randint
from Crypto.Util.number import getPrime, inverse, long_to_bytes, bytes_to_long
from math import gcd
import signal
from secret import flag
def gen_coprime_num(pbits):
lbits = 2 * pbits + 8
lb = 2**lbits
ub = 2**(lbits + 1)
while True:
r = randint(lb, ub)
s = randint(lb, ub)
if gcd(r, s) == 1:
return r, s
def mult_mod(A, B, p):
result = [0] * (len(A) + len(B) - 1)
for i in range(len(A)):
for j in range(len(B)):
result[i + j] = (result[i + j] + A[i] * B[j]) % p
return result
def gen_key(p):
f = [randint(1, 2**128) for i in ":)"]
h = [randint(1, 2**128) for i in ":("]
R1, S1 = gen_coprime_num(p.bit_length())
R2, S2 = gen_coprime_num(p.bit_length())
B = [[randint(1, p - 1) for i in ":("] for j in ":)"]
P = []
for b in B:
P.append(mult_mod(f, b, p))
Q = []
for b in B:
Q.append(mult_mod(h, b, p))
for i in range(len(P)):
for j in range(len(P[i])):
P[i][j] = P[i][j] * R1 % S1
Q[i][j] = Q[i][j] * R2 % S2
sk = [(R1, S1), (R2, S2), f, h, p]
pk = [P, Q, p]
return sk, pk
def encrypt(pk, pt):
P, Q, p = pk
pt = bytes_to_long(pt)
PP = 0
QQ = 0
for i in range(len(P)):
u = randint(1, p)
for j in range(len(P[0])):
PP = PP + P[i][j] * (u * pt**j % p)
QQ = QQ + Q[i][j] * (u * pt**j % p)
return PP, QQ
def decrypt(sk, ct):
RS1, RS2, f, h, p = sk
R1, S1 = RS1
R2, S2 = RS2
P, Q = ct
invR1 = inverse(R1, S1)
invR2 = inverse(R2, S2)
P = (P * invR1 % S1) % p
Q = (Q * invR2 % S2) % p
f0q = f[0] * Q % p
f1q = f[1] * Q % p
h0p = h[0] * P % p
h1p = h[1] * P % p
a = f1q + p - h1p % p
b = f0q + p - h0p % p
pt = -b * inverse(a, p) % p
pt = long_to_bytes(pt)
return pt
signal.alarm(30)
p = getPrime(256)
sk, pk = gen_key(p)
ticket = long_to_bytes(randint(1, p))
enc_ticket = encrypt(pk, ticket)
print(pk)
print(enc_ticket)
for i in range(2):
op = int(input("op>").strip())
if op == 1:
msg = input("pt:").strip().encode()
ct = encrypt(pk, msg)
print(f"ct: {ct}")
elif op == 2:
user_input = input("ct:").strip().split(" ")
if len(user_input) == 2:
ct = [int(user_input[0]), int(user_input[1])]
else:
print("invalid ct.")
break
user_input = input("your f:").strip().split(" ")
if len(user_input) == 2:
user_f = [int(user_input[0]), int(user_input[1])]
else:
print("invalid f.")
break
user_input = input("your h:").strip().split(" ")
if len(user_input) == 2:
user_h = [int(user_input[0]), int(user_input[1])]
else:
print("invalid h.")
break
user_input = input("your R1 S1:").strip().split(" ")
if len(user_input) == 2:
user_r1s1 = [int(user_input[0]), int(user_input[1])]
else:
print("invalid R1 S1.")
break
user_input = input("your R2 S2:").strip().split(" ")
if len(user_input) == 2:
user_r2s2 = [int(user_input[0]), int(user_input[1])]
else:
print("invalid R2 S2.")
break
pt = decrypt((user_r1s1, user_r2s2, user_f, user_h, p), ct)
if pt == ticket:
print(flag)
else:
print(pt.hex())
else:
print("invalid op.")
break
print("bye!")
|
