# Faster and cleaner SHA-1 leading zero histogram with Python

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?

## 3 Answers

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()

• 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 – kelalaka Aug 4 '20 at 20:51
• @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. – superb rain Aug 4 '20 at 21:06
• 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. – kelalaka Aug 4 '20 at 21:18
• Now with the zeroes_me2() it is 0.10-0.12. So I've 2 times speed up now :) – kelalaka Aug 4 '20 at 21:21
• Now with the zeroes_me3() it is 0.09-0.10 – kelalaka Aug 4 '20 at 21:35

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.

• 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? – superb rain Aug 14 '20 at 14:12
• 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. – Maarten Bodewes Aug 14 '20 at 22:19
• That just sounds all wrong. How exactly do you show that difference of 3 bytes? – superb rain Aug 14 '20 at 22:27
• I ran into it on stackoverflow – Maarten Bodewes Aug 14 '20 at 22:30
• 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. – superb rain Aug 15 '20 at 12:28

What I'm not mostly unhappy here is the whole conversions between str, bin and back.

You can avoid this by first using digest() (instead of hexdigest()) to format the digest as bytes instead of a string, then converting the bytes directly to an integer:

hasvalue = hashlib.sha1(random.getrandbits(128).to_bytes(16, byteorder='big', signed=False)).digest()
hasvalue = int.from_bytes(hasvalue, byteorder='big', signed=False)


Then you take the bitlength of that integer and subtract it from 160 (or whatever is the bitlength of the hash you're using) to get the number of leading zeroes:

bitlength = 0
while (hasvalue):
hasvalue >>= 1
bitlength += 1
leading_zeros = 160-bitlength

• This seems lost costlier, on average the while loop will run 159 times. Can you execute a performance as superb rain did? – kelalaka May 11 at 23:53
• Actually I didn't even realize Python had a built-in bit_length(). My way would definitely be slower than that. – fuzzy drawings May 12 at 0:04