5.3 Вопросы эффективности

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

В разделе 5.5 приведена конструкция семейства односторонних хэш-функций, предложенная Импальяццо и Наором. Эта конструкция основана на модулярной задаче о рюкзаке и весьма эффективна, поскольку хэширование очередного блока сообщения состоит в выполнении лишь операции сложения целых чисел по модулю, являющемуся степенью двойки. В работе [IR] приводится набросок доказательства стойкости этого семейства хэш-функций. Однако, у этой конструкции имеется серьезный недостаток -- большая длина констант. Кроме того, здесь речь идет о семействе функции, а для практики лучше пожертвовать доказуемой стойкостью, но получить схему (например, электронной подписи), не зависящую от "истории".

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

• любой из известных алгоритмов построения коллизий не должен быть эффективнее метода "грубой силы" (т. е. метода, основанного на "парадоксе дня рождения");

• алгоритм должен допускать эффективную программную реализацию на 32-разрядном процессоре;

• алгоритм не должен использовать сложных структур данных и подпрограмм;

• алгоритм должен быть оптимизирован с точки зрения его реализации на микропроцессорах типа Intel.

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

Максимальной эффективности, скорее всего, удастся достигнуть для хэш-функций, конструируемых "с нуля", а не использующих алгоритмы блочного шифрования. При построении хэш-функций "с нуля", в частности при проектировании элементарных хэш-функций, следует использовать известные методы и принципы построения надежных шифраторов (например, шенноновский подход, основанный на комбинации преобразований замены и перестановок (permutation and substitution)).

В последнее время получило развитие еще одно направление исследований в области повышения эффективности алгоритмов хэширования. В работе [BGG1] рассматривается проблема эффективности с точки зрения решения массовой задачи. А именно, пусть требуется вычислять хэш-коды для большого числа сообщений, незначительно отличающихся друг от друга. При этом мерой эффективности является суммарное время, затрачиваемое на вычисление хэш-кодов всех сообщений. Такая постановка задачи, по-видимому, достаточно типична для систем обслуживания банковских расчетов, где платежные поручения, как правило, имеют типовую форму и отличаются лишь в некоторых полях документа (однако следует учитывать, что защищаемой, а значит и хэшируемой, может оказаться как раз только эта "значимая" информация, поэтому практическое приложение такого подхода требует дополнительного изучения с привлечением не только криптографов-математиков, но и специалистов в области банковских расчетов).

При данном подходе прежде всего необходимо формализовать свойство, что документы незначительно отличаются. В работе [BGG1] авторы определяют близость двух сообщений (текстов, документов) как минимально необходимое количество элементарных преобразований, позволяющих перейти от одного сообщения к другому. Под элементарным понимается одно из следующих преобразований: удаление произвольного блока из сообщения; добавление произвольного блока в сообщение; замена произвольного блока сообщения на произвольный другой блок; перестановка двух блоков в сообщении.

Основная идея заключается в том, что помимо собственно процедуры хэширования определяется алгоритм, который позволяет вычислять по значению хэш-кода заданного сообщения хэш-код сообщения, получаемого из заданного элементарным преобразованием. Естественно, при этом стремятся к тому, чтобы этот алгоритм был значительно эффективнее, чем непосредственное хэширование. Попутно, заметим, что эта идея может изучаться не только в применении к хэшированию, но и к криптографическому преобразованию произвольного типа (шифрование, цифровая подпись, вычисление имитоприставки и т. д.).

Авторы статьи [BGG1] демонстрируют принципиальную осуществимость этой идеи на следующем примере. В качестве основного алгоритма хэширования рассматривается следующий. Хэшируемое сообщение представляется в виде последовательности блоков: , которые интерпретируются как целые числа. Фиксируется простое число и некоторый набор первообразных элементов конечного поля . Хэш-кодом сообщения является . Нетрудно показать, что если рассматривать набор как описание отдельной хэш-функции, то соответствующее семейство является в предположении трудности задачи дискретного логарифмирования семейством хэш-функций с трудно обнаружимыми коллизиями (см. раздел 5.5).

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

В настоящее время этот подход практически не исследован. Здесь открывается широкое поле для работы исследователей. Прежде всего, требует изучения вопрос о существовании такой схемы без ослабления требований по стойкости (в различных определениях) криптографического преобразования. Далее, безусловно интересно построить примеры подобных схем хэширования на основе различных подходов (на базе шифратора, с "нуля" и т. д.). Остается открытым вопрос и относительно того, когда и в каких протоколах такой подход будет эффективнее традиционного.