Problem Intro
We need to generate a one-time pad to communicate securely. The keys for the pad are generated by hashing a salt (our puzzle input) with an increasing integer index (starting from 0). The hash function is MD5.
A hash is a key only if it meets two conditions:
- It contains three of the same character in a row (a triplet).
- One of the next 1000 hashes contains five of that same character in a row.
We need to find the index that produces the 64th key.
Part 1
Given the actual salt in your puzzle input, what index produces your 64th one-time pad key?
This is a straightforward hashing problem. For each index, we generate an MD5 hash and check for a triplet. If we find one, we then check the next 1000 hashes for a sequence of five of the same character.
To make this efficient, I used a cache. Since we are repeatedly calculating hashes for overlapping ranges of indices, caching the results of the hash calculations significantly speeds up the process. I used functools.lru_cache for this purpose.
Here’s the main logic:
import hashlib
import functools
import re
# ...
def find_keys(salt, repeats=0):
keys = []
index = 0
while len(keys) < KEYS_TO_FIND:
to_hash = salt + str(index)
hash_hex = hash_method(to_hash, repeats)
if match := triple_chars_match.search(hash_hex):
five_char_seq = 5*match.group()[0]
for i in range(1, 1001):
subsequent_hash = hash_method(salt+str(index+i), repeats)
if five_char_seq in subsequent_hash:
keys.append(hash_hex)
break
index += 1
return index, keys
@functools.lru_cache(None)
def hash_method(to_hash, repeats):
result = to_hash
for _ in range(repeats+1):
result = hashlib.md5(result.encode()).hexdigest()
return result
The find_keys function iterates through indices, generates hashes, and checks for the key conditions. The hash_method is decorated with @functools.lru_cache(None), which caches the results of the hash calculations. The None argument for maxsize means the cache can grow without bound.
Part 2
To make the keys harder to crack, the hash function is modified. Instead of just hashing once, you hash 2016 additional times. That is, you hash the salt+index combination, then hash the result of that, and so on, for a total of 2017 hashes.
This is a simple modification to our existing solution. We can pass the number of repeats to our hash_method. The lru_cache will still work, but it will be caching the results of the stretched hashes.
I modified the find_keys and hash_method to accept a repeats parameter. For Part 2, we call find_keys with repeats=2016.
index, keys = find_keys(salt, MD5_REPEATS)
logging.info("Part 2: 64th key produced at index %d", index-1)
Results
Here’s the output from the solution:
Part 1: 64th key produced at index 15167
Part 2: 64th key produced at index 19967
Execution time: 1.1523 seconds