В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 6 Функции хэширования Функции хэширования поистине универсальны. Они могут применяться для шифрования, аутентификации и даже в простых схемах цифровых под- писей 1 . Функция хэширования — это функция, которая принимает на вход строку битов (или байтов) произвольной длины и выдает результат фиксированной длины. Стандартной областью применения функций хэширования являются цифровые подписи. Для обеспечения аутентификации можно подписывать само сообщение m . Тем не менее в большинстве схем цифровых подписей операции с открытым ключом обходятся довольно дорого в плане вычисли- тельных ресурсов. Поэтому, вместо того чтобы подписывать само сообщение m , можно применить к нему функцию хэширования и подписать значение h ( m ) . Результат применения функции h обычно составляет от 128 до 512 бит в длину, что совсем немного в сравнении с тысячами или миллионами бит со- общения m . Таким образом, подписать значение h ( m ) гораздо быстрее, чем подписать непосредственно сообщение m . Чтобы данная конструкция была безопасной, функция хэширования должна удовлетворять следующему усло- вию: невозможно построить два разных сообщения m 1 и m 2 , результаты хэ- ширования которых были бы одинаковы. Более подробно свойства безопас- ности функций хэширования рассматриваются несколько ниже. Иногда функции хэширования называют функциями профилей сообщений (message digest) , а результат применения функции хэширования — профилем (digest) или цифровым отпечатком пальца (digital fingerprint) . Мы же пред- почитаем более распространенное название функция хэширования (hash func- tion) , поскольку, помимо создания профилей сообщений, эти функции име- ют массу областей применения. Следует также предупредить вас о возмож- 1 Самая первая схема цифровой подписи, разработанная Лесли Лэмпортом (Leslie Lam- port), принадлежит именно к этому типу [21]. 104 6.1. Безопасность функций хэширования 105 ной путанице: термином “функция хэширования” иногда называют функцию отображения, которая применяется для доступа к хэш-таблицам — структу- ре данных, используемой во многих алгоритмах. Эти так называемые функ- ции хэширования схожи с криптографическими функциями хэширования, однако между ними есть существенное различие. Функции хэширования, ис- пользуемые в криптографии, обладают особыми свойствами безопасности. К функциям отображения хэш-таблиц предъявляются более слабые требо- вания. Никогда не путайте эти функции. В нашей книге речь идет только о криптографических функциях хэширования. В криптографии функции хэширования имеют множество применений. Они выполняют роль “связующего звена” между различными частями крип- тографической системы. Если вас не устраивает значение с переменной дли- ной, вы можете применить к нему функцию хэширования, чтобы превратить его в значение с фиксированной длиной. Функции хэширования могут при- меняться в качестве криптографических генераторов псевдослучайных чисел для создания нескольких ключей на основе одного общего секретного ключа. И наконец, функции хэширования обладают свойством односторонности, бла- годаря которому разные части системы оказываются изолированными друг от друга, поэтому, даже если злоумышленнику удастся узнать какое-нибудь одно значение, он не сможет вычислить по нему другие. Несмотря на повсеместное применение функций хэширования, мы знаем о них гораздо меньше, чем о блочных шифрах. Это одно из слабых мест криптографического сообщества. В сравнении с блочными шифрами функ- ции хэширования крайне мало исследованы, а практические предложения функций хэширования весьма немногочисленны. 6.1 Безопасность функций хэширования Как уже отмечалось, функция хэширования отображает строку m про- извольной длины на значение h ( m ) фиксированной длины. Обычно длина результата функции хэширования составляет от 128 до 512 бит. К функции хэширования предъявляется несколько требований. Самое простое из них — односторонность (one-way property) : для любого сообщения m легко вычис- лить значение h ( m ) , однако для любого значения x невозможно найти такое m , что h ( m ) = x . Другими словами, сама односторонняя функция вычисля- ется довольно легко, а вычисление функции, обратной по отношению к ней, осуществить практически невозможно (отсюда и название “односторонняя”). Среди многих других свойств, которыми должна обладать хорошая функ- ция хэширования, наиболее часто упоминают сопротивляемость коллизиям (collision resistance) . Последнее требование строже, чем свойство односторон- |