10
\$\begingroup\$

I tried to make a program to find a string whose MD5-hash starts like the digits of pi, where dot is omitted. Is there a faster way to do it than this:

import hashlib
import random
import string
n = 1
while True:
    word = ''.join(random.choice(string.ascii_lowercase) for _ in range(20))
    if (str(hashlib.md5(word.encode('utf-8')).hexdigest()))[:n] == '31415926535897932384626433832795'[0:n]:
        print('n='+str(n)+", "+word)
        n = n + 1
\$\endgroup\$
  • \$\begingroup\$ Have your program actually returned any output yet? Have you found a string? \$\endgroup\$ – Simon Forsberg May 4 '16 at 17:17
  • \$\begingroup\$ @SimonForsberg Yes. The string kgrkyinwuezpenmoonig gives me six correct numbers. \$\endgroup\$ – guest May 4 '16 at 17:21
  • \$\begingroup\$ Oh, right, you are iterating to increase the number of characters you are matching step by step... so you still haven't found anything that matches seven or more numbers? \$\endgroup\$ – Simon Forsberg May 4 '16 at 17:24
  • \$\begingroup\$ @SimonForsberg Yes. It looks like there should be a better check. For example n=1 might return a string that matches for six first digits. But I have not yet found a string that matches seven or more digits. \$\endgroup\$ – guest May 4 '16 at 17:28
  • \$\begingroup\$ may i ask the purpose of this? \$\endgroup\$ – THE AMAZING May 4 '16 at 20:14
3
\$\begingroup\$

The algorithm you're using is a brute-force algorithm. It will require around (24)n hash checks for a match of n digits. Each additional digit will require an average of 16-1 more time to calculate than the previous one.

The first, and hopefully obvious, step would be to get a better algorithm for a huge speedup - unfortunately, this is non-trivial in this case.

An additional step could be to use a language that is, typically, faster than Python. You probably want a compiled language like C/C++, or even Java.

Lastly, this is a perfect parallel computing problem. You have lots of small pieces (i.e. pick some text and hash it) and each is distinct, so they're easy to do in parallel.

Here I've given some improvements for a Python program, brute-force algorithm, singly-threaded.

The most important aspect of the code is how quickly we can create the word and calculate the md5 hash. I've rewritten your code to not use an infinite loop, but instead loop for a specific number of tries. This lets us time things using timeit.

from hashlib import md5
from random import choice, shuffle
from string import ascii_lowercase
from timeit import timeit
from itertools import product, islice
from os.path import commonprefix

def find_hash_pi_external(tries):
    n = 1
    for _ in range(tries):
        word = ''.join(choice(ascii_lowercase) for _ in range(20))
        if (str(md5(word.encode('utf-8')).hexdigest()))[:n] == '31415926535897932384626433832795'[0:n]:
            print('n=' + str(n) + ", " + word)
            n = n + 1

Some other comments:

  • The method hexdigest() returns a string, so you don't need to call str() there.
  • You can exclude the 0 in a[0:n].
  • You don't always have to increment n by one - sometimes you've found one that will match more than n characters.
def find_hash_pi_1(tries):
    pi = '31415926535897932384626433832795'
    n = 1
    for _ in range(tries):
        word = ''.join(choice(ascii_lowercase) for _ in range(20))
        hash = md5(word.encode('utf-8')).hexdigest()
        if hash[:n] == pi[:n]:
            n = len(commonprefix([pi, hash])) # note: commonprefix is slow so we only use it if there is a success
            print('n=' + str(n) + ", word=" + word + ", hash=" + hash)
            n = n + 1

The code above calls choice many times to make each word random. We don't need to do that - instead, we need only different word value in the each step of the loop. It also creates the word as a string, but the md5 module requires bytes. It is expensive to convert, so we can try to create the word as bytes without the string intermediate.

def find_hash_pi_2(tries):
    pi = '31415926535897932384626433832795'
    n = 1
    letters = bytes(ascii_lowercase, 'utf-8')
    for word in islice(product(letters, repeat=20), tries):
        word = bytes(word)
        hash = md5(word).hexdigest()
        if hash[:n] == pi[:n]:
            n = len(commonprefix([pi, hash])) # note: commonprefix is slow so we only use it if we have a hit
            print('n=' + str(n) + ", word=" + word.decode('utf-8') + ", hash=" + hash)
            n += 1                  

At this point the profiler is telling me that the built-in method _hashlib.openssl_md5 takes up about 10% of our time. There is still space to improve, but our brute-force algorithm that uses separate md5() calls will be difficult to improve by much more.

Below I've shown the timeit output for all three solutions

if __name__ == "__main__":
    print(timeit('find_hash_pi_external(2 ** 16)', setup="from __main__ import find_hash_pi_external", number=1))
    print(timeit('find_hash_pi_1(2 ** 16)', setup="from __main__ import find_hash_pi_1", number=1))
    print(timeit('find_hash_pi_2(2 ** 16)', setup="from __main__ import find_hash_pi_2", number=1))

Results:

n=1, iaathglhsnzablgilhim
n=2, vjvcpilnwymbckhubdxl
n=3, gteyvjexqwahhbgasvco
n=4, rhjccvcubaeqfurjbfgi
1.227025089520841
n=1, word=wanforjhvqrpgnbbvlap, hash=3feca550be69a201c6147a0a20dbf338
n=2, word=eulvqycsfrgqhotpqsah, hash=3177a30c82a3b12856def16568d8b155
n=3, word=knmwruvaahghowwsyqyx, hash=3146373e28453b9dc7d1bb9961917dec
n=4, word=qrsgbfrcwrzwlqjgmryp, hash=31414f71ee6ba9516c9d0acb16e67662
1.239360037012343
n=1, word=aaaaaaaaaaaaaaaaaabp, hash=3f6056bb268f4176685134ae56a838da
n=2, word=aaaaaaaaaaaaaaaaaaqt, hash=311468ef9220551699d61e9b70e43aa7
n=4, word=aaaaaaaaaaaaaaaaafml, hash=314125241241d57b8085afe08b50bdf0
0.10168091144473257
\$\endgroup\$
  • 1
    \$\begingroup\$ Please work on writing good English. Things like assigning genders to objects, bad verb endings, inconsistent plurals, and not having (some) articles make your post hard to read. Also, your point about parallel computing is right but badly reasoned; it's good because every element in this process – that is, either every step or string – doesn't depend on any global state, and in the case of each string being parallel, doesn't even depend on previous results. \$\endgroup\$ – Fund Monica's Lawsuit May 5 '16 at 4:45
  • 1
    \$\begingroup\$ @vaeta I edited your post with some improved grammar - please take a look at it and revert it if you think I've changed too much, or let me know if you think I didn't accurately say what you intended. \$\endgroup\$ – Dannnno May 11 '16 at 23:00
  • \$\begingroup\$ @Dannnno Thanks a lot, now it's more readable :). I change only one line (try to precise why don't need random words -- permutation is only one of possible solution) \$\endgroup\$ – vaeta May 12 '16 at 11:10
0
\$\begingroup\$

Google searching "31415926535897932384626433832795 md5" (no quotes) shows that https://www.freerainbowtables.com/gethashlist.php?type=md5 lists this, though I don't know enough about rainbow tables to understand how to use this to generate a string.

Also, although this is pretty cool, you realize you're outputting hex digits as though they were decimal, right?

\$\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.