Адитья Бхаргава – Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих (страница 30)

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

Алгоритм 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 используется для выявления сходства между фрагментами текста.

Обмен ключами Диффи—Хеллмана

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

Проще всего определить подстановочный шифр: a = 1, b = 2 и т.д. Если после этого я отправлю вам сообщение «4,15,7», вы сможете преобразовать его в «d,o,g». Но чтобы эта схема сработала, необходимо согласовать шифр между сторонами. Договориться о шифре по электронной почте невозможно, потому что злоумышленник может перехватить сообщение, узнать шифр и расшифровать сообщения. Даже если передать шифр при личной встрече, злоумышленник может угадать шифр, если он достаточно прост. Значит, шифр придется ежедневно менять. Но тогда нам придется ежедневно проводить личные встречи для изменения шифра!

Даже если вам удастся ежедневно изменять шифр, подобные простые шифры достаточно легко взламываются методом грубой силы. Допустим, я вижу сообщение «9,6,13,13,16 24,16,19,13,5». Я предполагаю, что при шифровании используется подстановка a = 1, b = 2 и т.д.

Бессмыслица. Пробуем a = 2, b = 3 и т.д.

Сработало! Подобные простые шифры взламываются достаточно легко. Во Вторую мировую войну в Германии использовался намного более сложный шифр, но и он был взломан.

Алгоритм Диффи—Хеллмана решает обе проблемы:

• знание шифра обеими сторонами не обязательно. Следовательно, им не придется встречаться и согласовывать шифр;

• расшифровать зашифрованные сообщения чрезвычайно сложно.

Алгоритм Диффи—Хеллмана использует два ключа: открытый и закрытый. Открытый ключ известен обеим сторонам. Его можно опубликовать на сайте, отправить электронной почтой друзьям и вообще сделать с ним все, что вам заблагорассудится. Его не нужно скрывать. Когда другая сторона захочет отправить вам сообщение, она зашифрует его с применением открытого ключа. Зашифрованное сообщение можно расшифровать только с закрытым ключом. При условии, что вы являетесь единственным владельцем закрытого ключа, никто другой расшифровать сообщение не сможет!

Алгоритм Диффи—Хеллмана продолжает применяться на практике вместе с его наследником RSA. Если вы интересуетесь криптографией, алгоритм Диффи—Хеллмана станет хорошей отправной точкой: он элегантен и не особо сложен.

Линейное программирование

Самое лучшее я приберег напоследок. Линейное программирование — одна из самых интересных областей, которые мне известны.

Линейное программирование используется для максимизации некоторой характеристики при заданных ограничениях. Предположим, ваша компания выпускает два продукта: рубашки и сумки. На рубашку требуется 1 м ткани и 5 пуговиц. На изготовление сумки необходимо 2 м ткани и 2 пуговицы. У вас есть 11 м ткани и 20 пуговиц. Рубашка приносит прибыль $2, а сумка — $3. Сколько рубашек и сумок следует изготовить для получения максимальной прибыли?

Здесь мы пытаемся максимизировать прибыль, а ограничения определяют количество имеющихся материалов.

Другой пример: вы политик, пытающийся получить максимальное количество голосов. Исследования показали, что на каждый голос жителя Сан-Франциско требуется примерно час работы (маркетинг, исследования и т.д.), а на каждый голос жителя Чикаго — 1,5 часа. Вам нужны голоса как минимум 500 жителей Сан-Франциско и как минимум 300 жителей Чикаго. В вашем распоряжении 50 дней. Кроме того, затраты на жителя Сан-Франциско составляют $2, а на жителя Чикаго — $1. Ваш бюджет составляет $1500. Какое максимальное количество голосов вы сможете получить (Сан-Франциско+Чикаго)?

На этот раз вы стремитесь к максимуму голосов при ограничениях по времени и деньгам.

Возможно, вы думаете: «В этой книге много говорилось о вопросах оптимизации. Как они связаны с линейным программированием?» Все алгоритмы, работающие с графами, могут быть реализованы средствами линейного программирования. Линейное программирование — намного более общая область, а задачи с графами составляют ее подмножество.

В линейном программировании используется симплекс-метод. Этот алгоритм достаточно сложен, поэтому я не привожу его в книге. Если вы интересуетесь задачами оптимизации, поищите информацию о линейном программировании!

Эпилог

Надеюсь, этот краткий обзор показал, как много вам еще предстоит узнать. Я считаю, что лучший способ узнать что-то — найти тему, которая вас интересует, и изучить ее. Надеюсь, эта книга закладывает достаточно надежную основу для этого.

5 Kalid, «An Interactive Guide to the Fourier Transform,» Better Explained, http://mng.bx/874X.

Ответы к упражнениям

Глава 1

1.1 Имеется отсортированный список из 128 имен, и вы ищете в нем значение методом бинарного поиска. Какое максимальное количество проверок для этого может потребоваться?

Ответ: 7

1.2 Предположим, размер списка увеличился вдвое. Как изменится максимальное количество проверок?

Ответ: 8

1.3 Известна фамилия, нужно найти номер в телефонной книге.

Ответ: O(log n)

1.4 Известен номер, нужно найти фамилию в телефонной книге. (Подсказка: вам придется провести поиск по всей книге!)

Ответ: O(n).

1.5 Нужно прочитать номера всех людей в телефонной книге.

Ответ: O(n).

1.6 Нужно прочитать телефоны всех людей, фамилии которых начинаются с буквы «А». (Вопрос с подвохом! В нем задействованы концепции, которые более подробно рассматриваются в главе 4. Прочитайте ответ — скорее всего, он вас удивит!)

Ответ: O(n). Возможно, кто-то подумает: «Я делаю это только для одной из 26 букв, а значит, время выполнения должно быть равно O(n/26).» Запомните простое правило: в «O-большое» игнорируются числа, задействованные в операциях сложения, вычитания, умножения или деления. Ни одно из следующих значений не является правильной записью «O-большое»: O(n + 26), O(n – 26), O(n * 26), O(n / 26). Все они эквивалентны O(n)! Почему? Если вам интересно, найдите раздел «Снова об “O-большом”» в главе 4 и прочитайте о константах в этой записи (константа — это просто число; в этом вопросе 26 является константой).

Глава 2

2.1 Допустим, вы строите приложение для управления финансами.

Ежедневно вы записываете все свои траты. В конце месяца вы анализируете расходы и вычисляете, сколько денег было потрачено. При работе с данными выполняется множество операций вставки и относительно немного операций чтения. Какую структуру использовать — массив или список?

Ответ: В данном случае траты добавляются в список ежедневно, а чтение всех данных происходит один раз в месяц. Для массивов характерно быстрое чтение и медленная вставка, а для связанных списков — медленное чтение и быстрая вставка. Так как вставка будет выполняться намного чаще, чем чтение, есть смысл воспользоваться связанным списком. Кроме того, чтение в связанных списках происходит медленно только при обращении к случайным элементам списка. Так как читаться будут все элементы списка, связанный список также неплохо справится с чтением. Итак, связанный список станет хорошим решением этой задачи.