/
merklehellman.py
110 lines (80 loc) · 2.44 KB
/
merklehellman.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
#Python file for Merkle-Hellman Implementation
#Function used to encrypt message
def encrypt(message):
serverPublicKey = [99, 1235, 865, 990, 5, 1443, 895, 1477]
cipherText = ""
for c in message:
temp = ord(c)
s = '{0:08b}'.format(temp)
i = 7
num = 0
for ch in s:
if ch == '1':
num += serverPublicKey[i]
i-=1
cipherText += format(num, '04x')
return cipherText
#Function used to get a powerset of a set
def powerSet(s):
x = len(s)
ps = []
for i in range(1 << x):
ps.append([s[j] for j in range(x) if (i & (1 << j))])
return ps
#BruteForce Knapsack Encryption
def bruteForceKnapsack(cipherText, pk):
i = 1
sets = powerSet(pk)
cipherList = [''.join(t) for t in zip(*[iter(cipherText)]*4)]
message = ""
for c in cipherList:
num = int(c,16)
p = 0
found = False
while not found:
guess = sum(sets[p])
if guess == num:
asciiVal = ""
curr = 7;
while curr >= 0:
if pk[curr] in sets[p]:
asciiVal += "1"
curr -= 1
else:
asciiVal += "0"
curr -= 1
message += chr(int(asciiVal,2))
found = True
else:
p += 1
return message
#Decrypt Knapsack Algorithm using Private Key
def decrypt(cipherText):
cipherList = [''.join(t) for t in zip(*[iter(cipherText)]*4)]
message = ""
privateKey = [3, 7, 11, 30, 61, 135, 377, 851]
n = 1037
m = 1506
inverse_n = 1217
for c in cipherList:
num = int(c,16)
temp = (num*inverse_n)%m
asciiVal = ""
curr = 7
while temp > 0:
if temp >= privateKey[curr]:
asciiVal += "1"
temp -= privateKey[curr]
else:
asciiVal += "0"
curr -= 1
while len(asciiVal) < 8:
asciiVal += "0"
message += chr(int(asciiVal,2))
return message
publicKey = [99, 1235, 865, 990, 5, 1443, 895, 1477]
superIncreasing = [3, 7, 11, 30, 61, 135, 377, 851]
flag = encrypt("gigem{merkle-hellman-knapsack}")
print(flag)
message = bruteForceKnapsack(flag, publicKey)
print(message)