9
\$\begingroup\$

I've written a python code for finding the distribution of the leading zeros of SHA-1. Using random inputs and hashing-then-counting. Normally it is expected to fit the n/2^i curve where n is the number of trials. After this, a plot is drawn.

import hashlib
import random
import matplotlib.pyplot as plt

leading = [0] * 160

trials = 10000000000

for i in range(trials):
    
    randomInput= random.getrandbits(128)
    
    hasvalue = hashlib.sha1(str(randomInput).encode('ASCII')).hexdigest()

    b = bin(int(hasvalue, 16))
    c= b[2:].zfill(160)
    zeroes = str(c).index('1')
    leading[zeroes] = leading[zeroes] + 1

The most time-consuming part of this code is of course the SHA-1 calculation and we cannot do something for that except parallelization with pymp or some other library. What I'm not mostly unhappy here is the whole conversions between str, bin and back.

Any improvements for a cleaner code and little speed up?

\$\endgroup\$
3
+50
\$\begingroup\$

Instead of str(random.getrandbits(128)).encode('ASCII') I'd use os.urandom(16). Much simpler, ought to be more random, shorter result, and a bit faster (at least for me). Or convert your random number to bytes directly, even faster (at least for me):

>>> timeit(lambda: str(random.getrandbits(128)).encode('ASCII'))
1.320366100000001
>>> timeit(lambda: os.urandom(16))
0.7796178000000111
>>> timeit(lambda: random.getrandbits(128).to_bytes(16, 'big'))
0.6476696999999945

From the doc:

os.urandom(size)
Return a string of size random bytes suitable for cryptographic use.

And to count zeros, perhaps use digest(), make an int from it and ask for its bit length:

    hashvalue = hashlib.sha1(os.urandom(16)).digest()
    i = int.from_bytes(hashvalue, 'big')
    zeroes = 160 - i.bit_length()

Benchmark results (numbers are times, so lower=faster):

0.56 zeroes_you
0.31 zeroes_me
0.29 zeroes_me2
0.26 zeroes_me3

0.60 zeroes_you
0.31 zeroes_me
0.28 zeroes_me2
0.24 zeroes_me3

0.57 zeroes_you
0.31 zeroes_me
0.28 zeroes_me2
0.24 zeroes_me3

Benchmark code:

import hashlib
import random
import os
from timeit import repeat

def zeroes_you():
    randomInput= random.getrandbits(128)
    hashvalue = hashlib.sha1(str(randomInput).encode('ASCII')).hexdigest()
    b = bin(int(hashvalue, 16))
    c= b[2:].zfill(160)
    zeroes = str(c).index('1')

def zeroes_me():
    hashvalue = hashlib.sha1(os.urandom(16)).digest()
    i = int.from_bytes(hashvalue, 'big')
    zeroes = 160 - i.bit_length()

def zeroes_me2():
    randomInput = random.getrandbits(128)
    hashvalue = hashlib.sha1(randomInput.to_bytes(16, 'big')).digest()
    i = int.from_bytes(hashvalue, 'big')
    zeroes = 160 - i.bit_length()
    
def zeroes_me3(randbits=random.getrandbits, sha1=hashlib.sha1, int_from_bytes=int.from_bytes):
    hashvalue = sha1(randbits(128).to_bytes(16, 'big')).digest()
    zeroes = 160 - int_from_bytes(hashvalue, 'big').bit_length()

for _ in range(3):
    for zeroes in zeroes_you, zeroes_me, zeroes_me2, zeroes_me3:
        t = min(repeat(zeroes, number=100000))
        print('%.2f' % t, zeroes.__name__)
    print()
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ One issue might be it is blockable, in this case it make the run slower. I'll test. I'm not sure that my Ubuntu has run it in block mode or not. Here an article about it; Removing the Linux /dev/random blocking pool \$\endgroup\$ – kelalaka Aug 4 at 20:51
  • 1
    \$\begingroup\$ @kelalaka I'm using Windows, os.urandom has always been faster for me. Note the answer update, maybe at least the second part is useful for you. \$\endgroup\$ – superb rain Aug 4 at 21:06
  • 1
    \$\begingroup\$ I think it is blocking here. 0.20 zeroes_you and 0.34 zeroes_me plus-minus 2 at most. with your second part, it falls to 0.13. Nice and clean. \$\endgroup\$ – kelalaka Aug 4 at 21:18
  • 1
    \$\begingroup\$ Now with the zeroes_me2() it is 0.10-0.12. So I've 2 times speed up now :) \$\endgroup\$ – kelalaka Aug 4 at 21:21
  • 1
    \$\begingroup\$ Now with the zeroes_me3() it is 0.09-0.10 \$\endgroup\$ – kelalaka Aug 4 at 21:35
1
\$\begingroup\$

I agree with the other answer and yourself that you should try and keep away from encoding / decoding binary values altogether. The same goes for finding the highest bit from a number; converting to a string to find a character is vastly less performant than looking for bits directly. However, that's already mentioned in the other answer, so this is just code review following up on that.

I'm not sure why you would not just use i (formatted as a byte array) as input, I just wanted to mention that as the RNG might well be dependent on a hash, and may therefore be a bigger bottleneck than the SHA-1 hash itself. Just a small note that getrandbits uses the Mersenne Twister underneath, so you should get non-secure but well distributed random numbers from it (so that particular random number generator probably won't be a bottleneck).

Since Python 3.6 you can use underscores in number literals (10_000_000_000 is easier to distinguish as 10 billion on the short scale). Otherwise you can write it down as 10 * 1000 * 1000 * 1000 which at least makes is readable without having to manually count zeros.

[EDIT] I've removed the part of str method adding additional characters (which it seemingly still does). For this question the encoding of the characters afterwards as ASCII seems to resolve the issue anyway. Encoding as a string and then converting back to bytes immediately after still doesn't seem to be the way to go, obviously.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 10**10 might be good, too. Your paragraph about encodings doesn't make sense. In what way does str default to UTF-8? Do you mean str.encode? And that doesn't default to including BOM (str(123).encode() just gives me b'123'). And what do you mean with "binary values"? And ascii doesn't work, you probably mean 'ascii'. And why ASCII? Gives the same result as UTF-8 (if it gives one at all). And the OP already does use ASCII, so why do you tell them? \$\endgroup\$ – superb rain Aug 14 at 14:12
  • \$\begingroup\$ It's the str function itself that adds the BOM as "characters". OK, you are right, directly encoding afterwards may again remove the BOM. However the intermediate string, if you will look at it, will be 3 chars / bytes larger because of the BOM. Of course, first converting to characters and then to bytes again makes little sense anyway. \$\endgroup\$ – Maarten Bodewes Aug 14 at 22:19
  • \$\begingroup\$ That just sounds all wrong. How exactly do you show that difference of 3 bytes? \$\endgroup\$ – superb rain Aug 14 at 22:27
  • \$\begingroup\$ I ran into it on stackoverflow \$\endgroup\$ – Maarten Bodewes Aug 14 at 22:30
  • \$\begingroup\$ About the edit: str doesn't add additional characters here. They're using it twice, once on an integer (producing a string of just digits and no additional characters) and once on a character string (returning that string itself, unmodified). Never on a byte string. \$\endgroup\$ – superb rain Aug 15 at 12:28

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.