| 219 |
Kevin |
1 |
# Encrypted Data
|
|
|
2 |
data_set = ((3781,14409),(31552,3930),(27214,15442),(5809,30274),
|
|
|
3 |
(5400,31486),(19936,721),(27765,29284),(29820,7710),
|
|
|
4 |
(31590,26470),(3781,14409),(15898,30844),(19048,12914),
|
|
|
5 |
(16160,3129),(301,17252),(24689,7776),(28856,15720),
|
|
|
6 |
(30555,24611),(20501,2922),(13659,5015),(5740,31233),
|
|
|
7 |
(1616,14170),(4294,2307),(2320,29174),(3036,20132),
|
|
|
8 |
(14130,22010),(25910,19663),(19557,10145),(18899,27609),
|
|
|
9 |
(26004,25056),(5400,31486),(9526,3019),(12962,15189),
|
|
|
10 |
(29538,5408),(3149,7400),(9396,3058),(27149,20535),
|
|
|
11 |
(1777,8737),(26117,14251),(7129,18195),(25302,10248),
|
|
|
12 |
(23258,3468),(26052,20545),(21958,5713),(346,31194),
|
|
|
13 |
(8836,25898),(8794,17358),(1777,8737),(25038,12483),
|
|
|
14 |
(10422,5552),(1777,8737),(3780,16360),(11685,133),
|
|
|
15 |
(25115,10840),(14130,22010),(16081,16414),(28580,20845),
|
|
|
16 |
(23418,22058),(24139,9580),(173,17075),(2016,18131),
|
|
|
17 |
(19886,22344),(21600,25505),(27119,19921),(23312,16906),
|
|
|
18 |
(21563,7891),(28250,21321),(28327,19237),(15313,28649),
|
|
|
19 |
(24271,8480),(26592,25457),(9660,7939),(10267,20623),
|
|
|
20 |
(30499,14423),(5839,24179),(12846,6598),(9284,27858),
|
|
|
21 |
(24875,17641),(1777,8737),(18825,19671),(31306,11929),
|
|
|
22 |
(3576,4630),(26664,27572),(27011,29164),(22763,8992),
|
|
|
23 |
(3149,7400),(8951,29435),(2059,3977),(16258,30341),
|
|
|
24 |
(21541,19004),(5865,29526),(10536,6941),(1777,8737),
|
|
|
25 |
(17561,11884),(2209,6107),(10422,5552),(19371,21005),
|
|
|
26 |
(26521,5803),(14884,14280),(4328,8635),(28250,21321),
|
|
|
27 |
(28327,19237),(15313,28649))
|
|
|
28 |
|
|
|
29 |
def Extended_Euclidian(a, b):
|
|
|
30 |
''' Takes values a and b and returns a tuple (r,s,t) in the following format:
|
|
|
31 |
r = s * a + t * b where r is the GCD and s and t are the inverses of a and b'''
|
|
|
32 |
t_ = 0
|
|
|
33 |
t = 1
|
|
|
34 |
s_ = 1
|
|
|
35 |
s = 0
|
|
|
36 |
q = a//b
|
|
|
37 |
r = a - q * b
|
|
|
38 |
# print("%d\t= %d * %d + %d" % (a, q, b, r))
|
|
|
39 |
while r > 0:
|
|
|
40 |
temp = t_ - q * t
|
|
|
41 |
t_ = t
|
|
|
42 |
t = temp
|
|
|
43 |
temp = s_ - q * s
|
|
|
44 |
s_ = s
|
|
|
45 |
s = temp
|
|
|
46 |
a = b
|
|
|
47 |
b = r
|
|
|
48 |
q = a//b
|
|
|
49 |
r = a - q * b
|
|
|
50 |
# print("%d\t= %d * %d + %d" % (a, q, b, r))
|
|
|
51 |
r = b
|
|
|
52 |
return (r, s, t)
|
|
|
53 |
|
|
|
54 |
def Inverse(a, b):
|
|
|
55 |
'''Returns the multiplicative inverse of a mod b'''
|
|
|
56 |
ret = Extended_Euclidian(a,b)
|
|
|
57 |
if (ret[1] < 0):
|
|
|
58 |
inv = ret[1] + b
|
|
|
59 |
else:
|
|
|
60 |
inv = ret[1]
|
|
|
61 |
return inv
|
|
|
62 |
|
|
|
63 |
def Decrypt(n):
|
|
|
64 |
'''Decodes an encoding where n = a * 26^2 + b * 26 + c'''
|
|
|
65 |
a = int(n / 676)
|
|
|
66 |
n = n - (a * 676)
|
|
|
67 |
b = int(n / 26)
|
|
|
68 |
n = n - (b * 26)
|
|
|
69 |
c = n
|
|
|
70 |
return (a, b, c)
|
|
|
71 |
|
|
|
72 |
if __name__ == '__main__':
|
|
|
73 |
p = 31847
|
|
|
74 |
a = 7899
|
|
|
75 |
|
|
|
76 |
# For each encrypted data packet, decrypt it using the following function:
|
|
|
77 |
# d(y_1,y_2) = y_2(y_1^a)^-1 mod p
|
|
|
78 |
for i in data_set:
|
|
|
79 |
d = i[1] * Inverse(i[0]**a,p) % p
|
|
|
80 |
s = Decrypt(d)
|
|
|
81 |
print("%c%c%c" % (chr(s[0]+65), chr(s[1]+65), chr(s[2]+65)), end='')
|
|
|
82 |
print()
|