5
\$\begingroup\$

I found a problem on here that ask to find an MD5 hash whose hexdigits starts like decimal digits of Pi. Is there a faster program or method to solve this than my program? This uses brute force search. The site says that a has with 12 first digits like Pi exists but I was unable to find 10 correct digits from the beginning. How can one optimize this program?

# -*- coding: utf-8 -*-
import calendar
import time
import hashlib

def next_string(s):
    strip_zs = s.rstrip('z')
    if strip_zs:
        return strip_zs[:-1] + chr(ord(strip_zs[-1]) + 1) + 'a' * (len(s) - len(strip_zs))
    else:
        return 'a' * (len(s) + 1)

starttime = calendar.timegm(time.gmtime())
fo = open("testfile.txt", "r+")
a = fo.readline()
print("Putkaposti Piinkova salasana thus 39b.")
print("Find a MD5-hash whose hexrepresentation starts like the decimal representation of pi.")
print("Let us continue from the string "+a+".")
print("Ctrl+C quits the program and saves the results to the file result.txt.")
try:
    while True:
# Let us save the results every half an hour.
     now = calendar.timegm(time.gmtime())
     if now - starttime > 30*60:
        f = open("testfile.txt","w") 
        f.write(a)
        f.close()
        starttime = now

     if str(hashlib.md5(a.encode('utf-8')).hexdigest())[0:10] == "3141592653":
        f = open("result.txt","w") 
        f.write(a)
        f.close()
        print("Found! Print result to the screen and to the file result.txt.")
        print(a)
     a = next_string(a)
except KeyboardInterrupt:
    f = open("testfile.txt","w") 
    f.write(a)
    f.close()
\$\endgroup\$
1
\$\begingroup\$

When speeding up code, you need to measure the performance of the code on a standard test case, and then try many experiments focussing on the hot spots (the bits of code that are executed most often and take the majority of the time).

So the first thing to do is to refactor the code so that it is easily measurable.

def test1(key='a', target='3141592653'):
    """Return a string whose MD5 hexdigest starts with target. The search
    starts at the string key.

    """
    target_len = len(target)
    starttime = calendar.timegm(time.gmtime())
    while True:
        now = calendar.timegm(time.gmtime())
        if now - starttime > 30*60:
            starttime = now
        if str(hashlib.md5(key.encode('utf-8')).hexdigest())[0:target_len] == target:
            return key
        strip_zs = key.rstrip('z')
        if strip_zs:
            key = strip_zs[:-1] + chr(ord(strip_zs[-1]) + 1) + 'a' * (len(key) - len(strip_zs))
        else:
            key = 'a' * (len(key) + 1)

I've stripped the file-reading and writing code, and the exception handling, because it's not important for testing performance, and I've inlined the code for next_string so that we can improve that along with the rest of the code.

The refactored code is designed to be easy to measure — you can pass different values for target to get different levels of difficulty. Here's my chosen test case:

>>> from timeit import timeit
>>> timeit(lambda:test1(target='000000'), number=1)
10.682760871015489

The first thing we can try is to skip the code for periodic saving — if the KeyboardInterrupt handling is reliable, then there's no need for a second mechanism to save your progress.

def test2(key='a', target='3141592653'):
    """Return a string whose MD5 hexdigest starts with target. The search
    starts at the string key.

    """
    target_len = len(target)
    while True:
        if str(hashlib.md5(key.encode('utf-8')).hexdigest())[0:target_len] == target:
            return key
        strip_zs = key.rstrip('z')
        if strip_zs:
            key = strip_zs[:-1] + chr(ord(strip_zs[-1]) + 1) + 'a' * (len(key) - len(strip_zs))
        else:
            key = 'a' * (len(key) + 1)

This is about twice as fast as test1:

>>> timeit(lambda:test2(target='000000'), number=1)
5.272445386042818

This means that about half the time in test1 was being spent in calendar.timegm and time.gmtime!

The next thing to try is to avoid the encoding and decoding steps. The only characters you use are lower-case "a" to "z", and these all encode to UTF-8 as single bytes. So we could maintain a bytearray instead of a string.

def test3(key='a', target='3141592653'):
    """Return a string whose MD5 hexdigest starts with target. The search
    starts at the string key.

    """
    key = bytearray(key.encode('ascii'))
    key_indexes = range(len(key) - 1, -1, -1)
    md5 = hashlib.md5
    a, z = b'az'
    while True:
        if md5(key).hexdigest().startswith(target):
            return key.decode('ascii')
        for i in key_indexes:
            key[i] += 1
            if key[i] > z:
                key[i] = a
                if i == 0:
                    key.append(a)
                    key_indexes = range(len(key) - 1, -1, -1)
            else:
                break

Note that I've also cached hashlib.md5 in a local variable to avoid having to look it up on each iteration.

This is about three times as fast as test1:

>>> timeit(lambda:test3(target='000000'), number=1)
3.3292323709465563

Instead of calling the hexdigest method, we could call digest instead:

import binascii

def test4(key='a', target='3141592653'):
    """Return a string whose MD5 hexdigest starts with target. The search
    starts at the string key.

    """
    key = bytearray(key.encode('ascii'))
    key_indexes = range(len(key) - 1, -1, -1)
    target_digest = binascii.unhexlify(target)
    md5 = hashlib.md5
    a, z = b'az'
    while True:
        if md5(key).digest().startswith(target_digest):
            return key.decode('ascii')
        for i in key_indexes:
            key[i] += 1
            if key[i] > z:
                key[i] = a
                if i == 0:
                    key.append(a)
                    key_indexes = range(len(key) - 1, -1, -1)
            else:
                break

(Note that this imposes the limitation that the target has an even number of hexadecimal digits.)

This gives a small further improvement:

>>> timeit(lambda:test4(target='000000'), number=1)
3.105254566995427

That's the limit of piecewise improvements that I can spot, so it doesn't look as though this approach is going to get you anywhere near to 12 digits. We expect the time taken to grow by about 16 times for each additional hexadecimal digit, so the expected runtime of test4(target='314159265358') would be well over a year.

|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.