Блог

Я пытаюсь запустить атаку по словарю на хэш sha512. Я знаю, что хэш состоит из двух слов, все в нижнем регистре, разделенных пробелом. Эти слова взяты из известного словаря (02-dictionary.txt), который содержит 172 820 слов. В настоящее время мой код выглядит следующим образом:

 import hashlib
import sys
import time

def crack_hash(word, target):
    dict_hash = hashlib.sha512(word.encode())
    if dict_hash.hexdigest() == target:
        return (True, word)
    else:
        return (False, None)

if __name__ == "__main__":
    target_hash = sys.argv[1].strip()
    
    fp = open("02-dictionary.txt", "r")

    words = []
    start_time = time.time()
    for word in fp:
        words.append(word)
    fp.close()

    for word1 in words:
        for word2 in words:
            big_word = word1.strip()   " "   word2.strip()
            print(big_word)
            soln_found, soln_word = crack_hash(big_word.strip(), target_hash)
            if soln_found:
                print('Solution found')
                print("The word was:", soln_word)
                break

    end_time = time.time()
    total_time = end_time - start_time
    print("Time taken:", round(total_time, 5), "seconds")
 

Однако, когда я запускаю этот код, программа работает невероятно медленно. Я знаю, что Python не самый эффективный язык, но я предполагаю, что проблема в большей степени связана с выбором структуры данных. Существует ли более эффективная структура данных? Я попытался использовать array модуль, но в документации создается впечатление, что он предназначен для использования для более примитивных типов (int, поплавки, шорты, булы, символы и т.д.), А не для более сложных типов, таких как строки (или списки символов). Каков наилучший способ улучшения этого кода? Примерно за час работы я преодолел только около 1% всех возможных словосочетаний.

Проблема в том, что вы вычисляете 178000 ² = 31684000000 (около 2 ³⁵) хэшей. Это большая работа. Я внес несколько изменений, чтобы добиться некоторой оптимизации в чистом python, но я подозреваю, что накладные расходы на вызовы hashlib довольно значительны. Я думаю, что выполнение всего этого в машинном коде приведет к более значительному ускорению.

Оптимизация включает в себя следующее:

• Предварительное вычисление слов в словаре в байтовые объекты
• Предварительное вычисление частичного результата хэширования первой части хэша

 import hashlib
import sys
import time


def try_all(words, target_hash):
    for word1 in words:
        hash_prefix = hashlib.sha512(word1   b' ')
        for word2 in words:
            prefix_copy = hash_prefix.copy()
            prefix_copy.update(word2)
            # print(big_word)
            if prefix_copy.digest() == target_hash:
                print('Solution found')
                big_word = (word1   b' '   word2).decode('utf8')
                print(f'The word was: {big_word}')
                return


def read_all_words(filename):
    with open(filename, "rt") as f:
        return [line.strip().encode('utf-8') for line in f]


def get_test_hash(words):
    phrase = words[-2]   b' '   words[-1]  # pick target towards end
    return hashlib.sha512(phrase).digest()


if __name__ == "__main__":
    words = read_all_words("02-dictionary.txt")
    TESTING = True
    if TESTING:
        words = words[:5000]  # reduce the size of the word list for testing only
        target_hash = get_test_hash(words)
    else:
        target_hash = bytes.fromhex(sys.argv[1].strip())
    start_time = time.time()
    try_all(words, target_hash)
    end_time = time.time()
    total_time = end_time - start_time
    print(f"Time taken: {round(total_time, 5)} seconds")
    print(f'{total_time / pow(len(words), 2)} seconds per hash')
 

На моем ноутбуке это происходит со скоростью около 1,1 * 10-6 ^{секунд на хэш, поэтому для перебора всех слов в словаре потребуется чуть менее 10 часов процессорного времени.}