Очень гладкий хеш
Общий | |
---|---|
Дизайнеры | Скотт Контини , Арьен К. Ленстра , Рон Стейнфелд |
Впервые опубликовано | 2005 |
Преемники | ХШ* |
Деталь | |
Размеры дайджеста | 1024 бит и выше |
В криптографии , Very Smooth Hash (VSH) — это доказуемо безопасная криптографическая хэш-функция изобретенная в 2005 году Скоттом Контини, Арьеном Ленстра и Роном Стейнфельдом. [1] Доказуемость означает, что обнаружение столкновений так же сложно, как известная сложная математическая задача. В отличие от других доказуемо безопасных и устойчивых к коллизиям хэшей, VSH эффективен и пригоден для использования на практике. Асимптотически ) бита сообщения требуется только одно умножение для каждого log( n и используется арифметика типа RSA. Таким образом, VSH может быть полезен во встроенных средах, где пространство кода ограничено.
Было предложено два основных варианта VSH. Во-первых, обнаружить столкновение так же сложно, как найти нетривиальный модульный квадратный корень из очень гладкого числа по модулю n . Другой использует простой модуль p (без лазейки ), и его доказательство безопасности основано на сложности нахождения дискретных логарифмов очень гладких чисел по модулю p . Обе версии имеют одинаковую эффективность.
VSH не подходит в качестве замены случайного оракула , но может использоваться для создания доказуемо безопасной рандомизированной хэш-функции с лазейкой. Эта функция может заменить функцию лазейки, используемую в схеме подписи Крамера-Шоупа , сохраняя ее доказуемую безопасность и одновременно ускоряя время проверки примерно на 50%.
ВСН и ВССР [ править ]
Все широко используемые сейчас криптографические хеш-функции не основаны на сложных математических задачах. Те немногие функции, которые построены на сложных математических задачах, называются доказуемо безопасными . Известно, что найти столкновения так же сложно, как решить сложную математическую задачу. Для базовой версии функции Very Smooth Hash эта сложная задача состоит в нахождении модульных квадратных корней (VSSR) из определенных специальных чисел (VSN). [1] Предполагается, что это так же сложно, как факторизовать целые числа .
Для фиксированных констант c и n целое число m является очень гладким числом (VSN), если наибольший простой делитель числа m не превышает (log n ). с .
Целое число b является очень гладким квадратичным вычетом по модулю n, если наибольшее простое число в факторизации b не превышает (log n ) с и существует целое число x такое, что . Говорят, что целое число x является модульным квадратным корнем из b .
Нас интересуют только нетривиальные квадратные корни, те, где x 2 ≥ п . Если х 2 < n корень можно легко вычислить с помощью алгоритмов из полей с характеристиками 0, таких как реальное поле. Поэтому они не подходят для криптографических примитивов.
Нетривиальный модульный квадратный корень очень гладкого числа (VSSR) — это следующая задача: пусть n — произведение двух неизвестных простых чисел примерно одинакового размера, и пусть . Позволять быть последовательностью простых чисел. VSSR представляет собой следующую задачу: по заданному n найти такой, что и хотя бы одно из , e0 ..., ek нечетно .
состоит Предположение VSSR в том, что не существует вероятностного полинома (в ) временной алгоритм, который решает VSSR с немалой вероятностью. Это считается бесполезным для практики предположением, поскольку оно не говорит о том, для какого размера модулей VSSR является вычислительно трудным. Вместо этого вычислительное предположение VSSR используется . В нем говорится, что решение VSSR считается таким же сложным, как и факторизация трудно поддающегося факторингу фактора. битовый модуль, где несколько меньше размера .
Примеры VSN и VSSR [ править ]
Пусть параметры зафиксированы следующим образом: и .
Затем является очень гладким числом по отношению к этим параметрам, потому что больше всех основные факторы. С другой стороны, это не VSN под и .
Целое число очень гладкий квадратичный вычет по модулю потому что это очень гладкое число (под ) и у нас есть такой, что (против ). Это тривиальный модульный квадратный корень, потому что и поэтому модуль не участвует при возведении в квадрат.
Целое число также является очень гладким квадратичным вычетом по модулю . Все простые множители меньше 7,37, а модульный квадратный корень равен с (против ). Таким образом, это нетривиальный корень. Задача ВССР состоит в том, чтобы найти данный и . И мы полагаем, что в вычислительном отношении это так же сложно, как факторинг .
Алгоритм VSH, базовые версии [ править ]
Позволять быть большим составным RSA и пусть последовательность простых чисел. Позволять , длина блока, представляет собой наибольшее целое число такое, что . Позволять быть -битовое сообщение, которое нужно хешировать, состоящее из битов и предположим, что . Чтобы вычислить хэш :
- х 0 = 1
- Позволять , наименьшее целое число, большее или равное , — количество блоков. Позволять для (дополнение)
- Позволять с быть двоичным представлением длины сообщения и определить для .
- для j = 0, 1,..., L последовательно вычислить
- вернуть х L + 1 .
Функция на шаге 4 называется функцией сжатия.
Свойства VSH [ править ]
- Длина сообщения не обязательно должна быть известна заранее.
- Найти коллизию в VSH так же сложно, как решить VSSR. Таким образом, VSH (сильно) устойчив к столкновениям , что также подразумевает устойчивость ко второму прообразу. Устойчивость VSH к прообразу не доказана.
- Функция сжатия не является устойчивой к столкновениям. Тем не менее, хеш-функция VSH устойчива к коллизиям, исходя из предположения VSSR. Измененная версия VSH, называемая VSH* , использует функцию сжатия, устойчивую к коллизиям, и примерно в 5 раз быстрее хэширует короткие сообщения.
- Поскольку выходная длина VSH равна длине безопасного модуля RSA, VSH на практике кажется вполне подходящим для создания подписей RSA «хеш-затем-подпись» для сообщений произвольной длины. Однако такая подпись должна быть тщательно разработана, чтобы обеспечить ее безопасность. Наивный подход можно легко сломать с помощью CPA (атака с выбранным открытым текстом) .
- Эффективность : стоимость каждой итерации меньше стоимости трех модульных умножений. Базовая версия VSH вообще требует однократного умножения на каждый биты сообщения.
Варианты ВШ [ править ]
Было предложено несколько улучшений, ускорений и более эффективных вариантов VSH. [1] Ни один из них не меняет основную концепцию функции. Эти улучшения называются:
- Возведение ВШ в куб (вместо возведения в квадрат).
- VSH с увеличенным количеством маленьких простых чисел.
- VSH с заранее вычисленными произведениями простых чисел.
- Быстрый ВШ.
- Быстрый VSH с увеличенной длиной блока.
Вариант VSDL и VSH-DL [ править ]
VSH -DL — это вариант VSH с дискретным логарифмом, у которого нет лазейки , его безопасность зависит от сложности нахождения дискретного логарифма по модулю простого числа p . [1]
Дискретный логарифм очень гладких чисел (VSDL) — это задача, в которой для очень гладкого числа мы хотим найти его дискретный логарифм по модулю некоторого числа n .
Как и в предыдущем разделе, по мы обозначаем -е простое число. Пусть, кроме того, быть фиксированной константой и , быть простым с и разреши . VSDL представляет собой следующую проблему: учитывая , найти целые числа такой, что с для и хотя бы один из ненулевой.
состоит Предположение VSDL в том, что не существует вероятностного полинома (в ) временной алгоритм, который решает VSDL с немалой вероятностью. Существует сильная связь между сложностью VSDL и сложностью вычисления дискретного логарифма по модулю. , что напоминает, но несколько слабее, связь между VSSR и целочисленной факторизацией.
Безопасность VSH [ править ]
Сильная устойчивость к столкновениям — единственное проверенное свойство VSH. Это не подразумевает устойчивость к прообразу или другие важные свойства хэш-функции, а авторы заявляют, что «VSH не следует использовать для моделирования случайных оракулов », и его нельзя подставлять в зависящие от них конструкции ( сигнатуры RSA , некоторые MAC ). [1] VSH не следует рассматривать как хеш-функцию общего назначения, как ее обычно понимают в технике безопасности .
Мультипликативное свойство [ править ]
VSH мультипликативен: пусть x , y и z — три битовые строки одинаковой длины, где z состоит только из нулевых битов, а строки удовлетворяют условиям x AND y = z . Это легко увидеть H(z)H(x OR y) ≡ H(x)H(y) (mod n) . В результате VSH подчиняется классической памяти времени. компромиссная атака, применимая к мультипликативным и аддитивным хешам.
Этот факт можно использовать для построения атаки на прообраз VSH биты, которые имеют сложность, а не как и ожидалось.
Атака на усеченную версию [ править ]
VSH создает очень длинный хэш (обычно 1024 бита). Нет никаких указаний на то, что усеченный хэш VSH обеспечивает безопасность, соизмеримую с длиной хеша.
Существует атака частичной коллизии на VSH, усеченная до l младших битов. [2]
Сложность этой атаки на VSH заключается в следующем:
- Предварительный расчет таблицы в автономном режиме: время и место.
- Нахождение коллизий: итерации.
- Общая стоимость: примерно , скорее, чем как и ожидалось от хеш-функции с хорошими свойствами псевдослучайности .
Это, вероятно, исключает применимость VSH в схемах цифровых подписей, которые создают подписи короче, чем результат хеширования VSH, таких как схемы подписи с эллиптической кривой.
См. также [ править ]
Ссылки [ править ]
- ^ Перейти обратно: а б с д Это Контини, С.; Ленстра, А.; Стейнфельд, Р. (23 июня 2005 г.), VSH, эффективная и доказуемая, устойчивая к коллизиям хэш-функция.
- ^ Сааринен, М.-ЙО (2006), «Безопасность VSH в реальном мире» (PDF) , Прогресс в криптологии - INDOCRYPT 2006 , Конспекты лекций по информатике, том. 4329, стр. 95–103, номер документа : 10.1007/11941378_8 , ISBN. 978-3-540-49767-7 [ мертвая ссылка ]