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.