Merkle's Puzzles implementation in Python
Today i found this youtube video explaining the Merkle's Puzzles algorithm, so i tried to replicate it using python to understand how it works.
The first thing i needed was to create three "security parameters" called s, n and N.
- s: Length of a "secret key"
- n: Length of the message
- N: How many puzzles i want it to make
Then i had to make the puzzles using some kind of "key based" encryption method, so i used a library called pycripto as my private encryption method for the emiter and reciever.
To make a puzzle i used this piece of code, using the three parameters i define before:
for i in range(0, N):
secret = str(randint(1000000000000000000000000, 9999999999999999999999999))
key = str(randint(1000, 9999))
enc_suite = AES.new(key*4, AES.MODE_CBC, key*4)
msg = enc_suite.encrypt('0'*(n-s) + secret)
msgs.append(msg)
keys.append(key)
secrets.append(secret)
This code makes N random keys and secrets, then it encrypts the message using the pycrypto library and it stores the block in an array called msgs[]. This block is sent and the reciever needs to bruteforce the key of a random message.
I used a random bruteforce method because i was using the random library anyways.
decrypted_msg = ''
rand_msg_solve = randint(0, N)
while not decrypted_msg.find('0'*(n-s)) == 0:
key = str(randint(1000, 9999))
dec_suite = AES.new(key*4, AES.MODE_CBC, key*4)
decrypted_msg = dec_suite.decrypt(msgs[rand_msg_solve])
When the reciever finds a decrypted message that starts with "0"*(n-s) it send the number of that decrypted message to the emiter, and then this message is defined as a private key for authentication.
You can found my code in my Github Account. It was a fun experiment to make, and i think i'll implement it in future projects with my Raspberry Pi.