Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих - страница 54

Хеш-функция должна обеспечивать достаточно равномерное распределение. Итак, хеш-функция получает строку и возвращает номер ячейки, соответствующий этой строке.

Сравнение файлов

Одну из разновидностей хеш-функций составляет алгоритм SHA (Secure Hash Algorithm). Он получает строку и возвращает хеш-код этой строки.

Возможно, терминология не настолько проста, насколько хотелось бы. Алгоритм SHA — хеш-функция; эта функция генерирует хеш-код, который представляет собой короткую строку. Хеш-функция для хеш-таблиц преобразует строку в индекс массива, тогда как SHA преобразует строку в другую строку.

Для каждой строки алгоритм SHA генерирует свой уникальный хеш-код.

примечание

Хеш-коды SHA достаточно длинные. Здесь приводится только начало.

Алгоритм SHA позволяет определить, совпадают ли два файла. Такая возможность особенно полезна для очень больших файлов. Допустим, у вас имеется 4-гигабайтный файл и вы хотите проверить, хранится ли у вашего друга точно такой же файл. Вам не придется пересылать большой файл по электронной почте; вместо этого можно вычислить хеш-коды SHA двух файлов и сравнить их.

Проверка паролей

Алгоритм SHA также может использоваться для сравнения строк при отсутствии информации об исходной строке. Например, только представьте, что сервис Gmail атакован хакерами! Ваш пароль стал добычей злоумышленников? А вот и нет. Google хранит не исходный пароль, а только хеш-код пароля по алгоритму SHA! Когда вы вводите пароль, Google хеширует его и сравнивает результат с хеш-кодом, хранящимся в базе данных.

Сравниваются только хеш-коды — хранить пароль не нужно! Алгоритм SHA очень часто используются для хеширования паролей. Хеширование является односторонним: вы можете получить хеш-код строки…

…но не сможете восстановить исходную строку по хеш-коду:

Это означает, что даже если злоумышленник похитит хеш-коды SHA с серверов Gmail, он не сможет по ним восстановить исходные пароли! Пароль можно преобразовать в хеш, но не наоборот.

Под термином SHA скрывается целое семейство алгоритмов: SHA-0, SHA-1, SHA-2 и SHA-3. На момент написания книги в алгоритмах SHA-0 и SHA-1 были обнаружены слабости. Если вы применяете алгоритм SHA для хеширования паролей, выбирайте SHA-2 или SHA-3. В настоящее время «золотым стандартом» хеширования паролей считается функция bcrypt (хотя идеальной защиты не бывает).

У хеширования SHA есть еще одна важная особенность: оно является локально-нечувствительным. Предположим, имеется строка, для которой генерируется хеш-код:

Если изменить в строке всего один символ, а потом сгенерировать хеш заново, строка полностью изменяется!

И это хорошо, потому что сравнение хешей не позволит атакующему определить, насколько он близок к взлому пароля.

Иногда требуется обратный результат: локально-чувствительная функция хеширования. Здесь на помощь приходит алгоритм Simhash. При незначительном изменении строки Simhash генерирует хеш-код, который почти не отличается от исходного. Это позволяет сравнивать хеш-коды и определять, насколько похожи две строки, — весьма полезная возможность!

• Google использует Simhash для выявления дубликатов в процессе индексирования.

• Преподаватель может использовать Simhash для обнаружения плагиата (копирования рефератов из Интернета).

• Scribd позволяет пользователям загружать документы или книги, чтобы они стали доступны для других пользователей. Но Scribd не хочет, чтобы пользователи размещали информацию, защищенную авторским правом! С помощью Simhash сайт может обнаружить, что отправленная информация похожа на книгу о Гарри Поттере, и при обнаружении сходства автоматически запретить ее размещение.

Simhash используется для выявления сходства между фрагментами текста.

Алгоритм Диффи—Хеллмана заслуживает упоминания, потому что он изящ­но решает давно известную задачу. Как зашифровать сообщение так, чтобы его мог прочитать только тот человек, которому адресовано сообщение?

Проще всего определить подстановочный шифр: