Какова сложность хеш-функции sha1

Question

Как размер моей подстроки растет, как я могу найти сложность этого раздела кода?

if size > 160: 
    sub = (hashlib.sha1(sub.encode('utf-8')).hexdigest()) 

Мне стало любопытно, когда я заметил, что моя программа работает так, как если бы хеш-функция выполнялась в постоянное время. Для моей программы, если «размер» равен 165, в худшем случае вышеуказанный код выполнит 165х. Тест, который я только что сделал, показывает, что sha1 выполняется с неустойчивыми отношениями с длиной.

Length Time 
0 0 
1 0.015000105 
2 0.016000032 
3 0.046000004 
4 0.046999931 
5 0.062000036 
6 0.078000069 
7 0.078000069 
8 0.07799983 
9 0.108999968 

код тест:

import string 
import random 
import hashlib 
import time 

def randomly(size=6, chars=string.ascii_uppercase + string.digits): 
    return ''.join(random.choice(chars) for _ in range(size)) 

for i in range(1, 10000001, 1000000): 
    random_str = randomly(i) 
    start = time.time() 
    str_hash = hashlib.sha1(random_str.encode('utf-8')).hexdigest() 
    print time.time() - start 

Answer 1

Я не согласен с DarthGizka. Вот подробное описание из того же wikipedia article:

Pre-processing: 
append the bit '1' to the message i.e. by adding 0x80 if characters are 8 bits. 
append 0 ≤ k < 512 bits '0', thus the resulting message length (in bits) 
    is congruent to 448 (mod 512) 
append ml, in a 64-bit big-endian integer. So now the message length is a multiple of 512 bits. 

Process the message in successive 512-bit chunks: 
break message into 512-bit chunks 
for each chunk 
    break chunk into sixteen 32-bit big-endian words w[i], 0 ≤ i ≤ 15 

    Extend the sixteen 32-bit words into eighty 32-bit words: 
    for i from 16 to 79 
     w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1 

     ...... 

Работа заполнения является только предварительной обработки. Больше работы сделано в пределах for each chunk. Поскольку размер данных mattkaeo превышает 1000000 символов (кроме 1-го), цикл должен потреблять наибольшее время, в то время как потребление отступов ничтожно.

Результат mattkaeo не очень линейный, я считаю, потому, что он запускает каждый образец только один раз, поэтому системный шум (например, ОС и другие процессы разделяют мощность процессора) значителен. Я бегу каждый образец в 200 раз:

import timeit 
for i in range(1, 10000001, 1000000): 
    random_str = randomly(i) 
    print timeit.timeit('hashlib.sha1(random_str).hexdigest()', 
         setup='import hashlib; random_str="%s".encode("utf-8")' % random_str, 
         number=200) 

В результате значительно более линейна:

0.000172138214111 
0.303541898727 
0.620085954666 
0.932041883469 
1.29230999947 
1.57217502594 
1.93531990051 
2.24045419693 
2.56945014 
2.95437908173 

Answer 2

SHA-1 алгоритма колодка ввода («сообщения») до кратного 512 бит, после того, как добавление «1» бит и размера входных данных. Из описания алгоритма в Википедии:

append the bit '1' to the message i.e. by adding 0x80 if characters are 8 bits 
append 0 ≤ k < 512 bits '0' 
append ml (message length), in a 64-bit big-endian integer. 

Именно поэтому время работы является шагом функцией входа, остается постоянной в течение некоторого времени, а затем прыгает.

Однако этот эффект уменьшается, поскольку размер сообщений увеличивается по сравнению с размером блока (шагом) 64 байта.

Другие заметно изменения происходят, как сообщение размеры подход и превышать различную память кэша размером: как правило, 32 КБ для кэша уровня 1 (L1), 256 Кбайт для L2 и 4, 8 или даже 20 МБ для кэш L3, чтобы от самого быстрого до самого медленного. Доступ к кэшированной памяти еще медленнее.

В случае с матеркео хэширование обнаружило бы, что кеши будут теплыми (то есть, многие данные все равно будут находиться в кеше), если данные не будут значительно превышать размер кеша. Разница между теплым кешем и не кэшированной памятью имеет тенденцию быть более заметной, чем для теплого или холодного кеша с низкой скоростью попадания.