Криптография - статьи



MD5


Первый момент в оптимизации этого алгоритма - это замена следующих макросов с 4-мя логическими операциями:

#define F(x, y, z) (((x) & (y)) | ((~x) & (z)))

#define G(x, y, z) (((x) & (z)) | ((y) & (~z)))

На макросы с 3-мя логическими операциями:

#define F(x, y, z) ((((y) ^ (z)) & (x)) ^ (z))

#define G(x, y, z) ((((x) ^ (y)) & (z)) ^ (y))

Конечно же, это даст небольшой, но все-таки прирост в скорости.

Второй же момент заключается в следующем: присмотримся внимательно к пункту 7 стандартного алгоритма и увидим, что если мы ограничим пароль для перебора 16-тью символами (т.к. на бОльшую глубину перебор уже бесполезен), то при формировании буфера Z у нас остаются несколько DWORD'ов, которые заполнены нулями. Посмотрим, какие именно:

16 символов пароля + 1 байт нуля + Cnt (16 байт) + 1 байт (0x80) = итого 34 байта или 9 DWORD'ов.

Далее у нас идут нули, до конца же массива занят еще только один DWORD - x[14].

И фактически пустые DWORD'ы - это x[9], x[10], x[11], x[12], x[13] и x[15].

Поэтому, во всех 64 итерациях (4 блока по 16 строк) алгоритма MD5, везде, где к результату прибавляется какой-то из этих DWORD'ов, то его можно не прибавлять вообще - там же нуль!

Этот нехитрый маневр увеличивает скорость данной конкретной реализации MD5 еще на 8-10%.

Кстати, эту идею можно развить и дальше:

  • При длине пароля 8..12 символа игнорировать x[8].
  • При длине пароля 4..8 символа игнорировать x[7] и x[8].
  • При длине пароля 1..4 символа игнорировать x[6], x[7] и x[8].
  • Что еще немного, конечно, но все-таки увеличит скорость перебора.

    Итого - после всех этих манипуляций время выполнения алгоритма MD5 стало занимать ~280-320 тактов, т.е. в среднем около 5 тактов на каждую из 64 итераций. Неплохо. :)

    Но, уже создавая эту статью, у меня появились определенные мысли, как можно еще оптимизировать этот код. ;) Вполне возможно, что в следующей версии PWLInside будет еще что-то новенькое в плане оптимизации MD5!

    Я также надеюсь, что вышеприведенная информация по оптимизации RC4 и MD5, возможно, поможет кому-нибудь, кто использует эти алгоритмы в своих разработках и позволит с минимальными "затратами" сделать эти программы еще более быстрыми :)




    Содержание  Назад  Вперед