Starting MD5 hash like Pi
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 &gt; 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:

&gt;&gt;&gt; from timeit import timeit
&gt;&gt;&gt; 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:

&gt;&gt;&gt; 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] &gt; 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:

&gt;&gt;&gt; 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] &gt; 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:

&gt;&gt;&gt; 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.