Хэш функции

Эта страница написана следующими людьми:

Хэш функция определяется как отображение \$h: \mathbb{B}^\ast \to \mathbb{B}^n\$ (принимает произвольное число битов и возвращает ровно \$n\$). Дополнительно требуется наличие следующих свойств:

  • Детерминизм: для каждого \$m\$ значение \$h(m)\$ всегда будет одинаковым

  • Необратимость: по значению \$h(m)\$ вычислительно сложно восстановить \$m\$ (лучше, чем перебором не получится)

  • Слабая устойчивость к коллизиям: для фиксированного \$m_1\$ вычислительно сложно найти такое \$m_2\$, что \$h(m_1) = h(m_2)\$

  • Сильная устойчивость к коллизиям: вычислительно сложно найти такие \$m_1\$ и \$m_2\$, что \$h(m_1) = h(m_2)\$

  • Равномерная распределенность значений: вероятность получить каждое значение почти совпадают, т.е.\$ |\text{Pr}_m[x = h(m)] - \frac{1}{2^n}| < \frac{1}{poly(n)} \$

Популярные хэш-фукнции:

  • MD5 генерирует 128-битный хэш. Это алгоритм, позволяющий быстро вычислить хэш, однако является небезопасным.

  • SHA1 генерирует 160-битный хэш. Этот алгоритм признан небезопасным и более не используется

  • SHA2 семейство алгоритмов, являющихся усовершенствованием SHA1

    • SHA224 генерирует 224-битный хэш

    • SHA256 генерирует 256-битный хэш

    • SHA384 генерирует 384-битный хэш

    • SHA512 генерирует 512-битный хэш

В терминале для вычисления хэш-функций есть утилита shasum. Чтобы выбрать алгоритм, необходимо передать флаг -a <TYPE> (1, 224, 256, 384, 512)