Вопросы эффективности
Построение стойких и высокоэффективных криптографических схем -- основная задача криптографии. Так что, вообще говоря, к тематике данного подраздела можно отнести все исследования, посвященные хэш-функциям. Поэтому, оговоримся сразу, что здесь мы рассматриваем лишь некоторые общие принципы разработки эффективных хэш-функций, а также те ситуации, для которых существуют способы повышения скорости хэширования. 
В разделе 5.5 приведена конструкция семейства односторонних хэш-функций, предложенная Импальяццо и Наором. Эта конструкция основана на модулярной задаче о рюкзаке и весьма эффективна, поскольку хэширование очередного блока сообщения состоит в выполнении лишь операции сложения целых чисел по модулю, являющемуся степенью двойки. Однако, у этой конструкции имеется серьезный недостаток -- большая длина констант. Кроме того, здесь речь идет о семействе функции, а для практики лучше пожертвовать доказуемой стойкостью, но получить схему (например, электронной подписи), не зависящую от "истории". 
При разработке практически стойких и высокоэффективных криптографических хэш-функций можно руководствоваться следующими эвристическими принципами, сформулированными Ривестом: 
•	любой из известных алгоритмов построения коллизий не должен быть эффективнее метода "грубой силы" (т. е. метода, основанного на "парадоксе дня рождения"); 
•	алгоритм должен допускать эффективную программную реализацию на 32-разрядном процессоре; 
•	алгоритм не должен использовать сложных структур данных и подпрограмм; 
•	алгоритм должен быть оптимизирован с точки зрения его реализации на микропроцессорах типа Intel. 
Как показывает анализ известных хэш-функций, практически все эффективные хэш-алгоритмы представляют собой последовательное применение к хэш-коду предыдущего шага и очередному блоку хэшируемого текста некоторой фиксированной функции (элементарной хэш-функции или функции сжатия). Хэш-кодом всего сообщения является хэш-код, получаемый после последнего шага: ). Для того, чтобы хэш-функция была эффективной и надежной, очевидно, и элементарная хэш-функция в целом должна удовлетворять вышеперечисленным свойствам (хотя она и не может обеспечить такой же стойкости). 
Максимальной эффективности, скорее всего, удастся достигнуть для хэш-функций, конструируемых "с нуля", а не использующих алгоритмы блочного шифрования. При построении хэш-функций "с нуля", в частности при проектировании элементарных хэш-функций, следует использовать известные методы и принципы построения надежных шифраторов (например, шенноновский подход, основанный на комбинации преобразований замены и перестановок (permutation and substitution)). 
В последнее время получило развитие еще одно направление исследований в области повышения эффективности алгоритмов хэширования. Рассматривается проблема эффективности с точки зрения решения массовой задачи. А именно, пусть требуется вычислять хэш-коды для большого числа сообщений, незначительно отличающихся друг от друга. При этом мерой эффективности является суммарное время, затрачиваемое на вычисление хэш-кодов всех сообщений. Такая постановка задачи, по-видимому, достаточно типична для систем обслуживания банковских расчетов, где платежные поручения, как правило, имеют типовую форму и отличаются лишь в некоторых полях документа (однако следует учитывать, что защищаемой, а значит и хэшируемой, может оказаться как раз только эта "значимая" информация, поэтому практическое приложение такого подхода требует дополнительного изучения с привлечением не только криптографов-математиков, но и специалистов в области банковских расчетов). 
При данном подходе прежде всего необходимо формализовать свойство, что документы незначительно отличаются. Определяют близость двух сообщений (текстов, документов) как минимально необходимое количество элементарных преобразований, позволяющих перейти от одного сообщения к другому. Под элементарным понимается одно из следующих преобразований: удаление произвольного блока из сообщения; добавление произвольного блока в сообщение; замена произвольного блока сообщения на произвольный другой блок; перестановка двух блоков в сообщении. 
Основная идея заключается в том, что помимо собственно процедуры хэширования определяется алгоритм, который позволяет вычислять по значению хэш-кода заданного сообщения хэш-код сообщения, получаемого из заданного элементарным преобразованием. Естественно, при этом стремятся к тому, чтобы этот алгоритм был значительно эффективнее, чем непосредственное хэширование. Попутно, заметим, что эта идея может изучаться не только в применении к хэшированию, но и к криптографическому преобразованию произвольного типа (шифрование, цифровая подпись, вычисление имитоприставки и т. д.). 
Авторы  демонстрируют принципиальную осуществимость этой идеи на следующем примере. В качестве основного алгоритма хэширования рассматривается следующий. Хэшируемое сообщение представляется в виде последовательности блоков: , которые интерпретируются как целые числа. Фиксируется простое число и некоторый набор первообразных элементов конечного поля . Хэш-кодом сообщения является . Нетрудно показать, что если рассматривать набор как описание отдельной хэш-функции, то соответствующее семейство является в предположении трудности задачи дискретного логарифмирования семейством хэш-функций с трудно обнаружимыми коллизиями (см. раздел 5.5). 
Непосредственное хэширование требует возведений в степень и умножение в конечном поле . Тогда, как легко понять, для того, чтобы получить хэш-код сообщения с удаленным блоком , достаточно прежний хэш-код домножить на , т. е. требуется всего одно возведение и одно умножение. 
В настоящее время этот подход практически не исследован. Здесь открывается широкое поле для работы исследователей. Прежде всего, требует изучения вопрос о существовании такой схемы без ослабления требований по стойкости (в различных определениях) криптографического преобразования. Далее, безусловно интересно построить примеры подобных схем хэширования на основе различных подходов (на базе шифратора, с "нуля" и т. д.). Остается открытым вопрос и относительно того, когда и в каких протоколах такой подход будет эффективнее традиционного.