Очень гладкий хеш - Very smooth hash

Очень гладкий хеш (VSH)
Общий
Дизайнеров	Скотт Контини, Арьен К. Ленстра, Рон Стейнфельд
Впервые опубликовано	2005
Преемники	VSH *
Деталь
Размеры дайджеста	1024 бит и выше

В криптография, Очень гладкий хеш (VSH) доказуемо безопасный криптографическая хеш-функция изобретен в 2005 году Скоттом Контини, Арьеном Ленстра и Роном Стейнфельдом.^[1]Доказанно безопасный означает, что обнаружение столкновений так же сложно, как и некоторые известные сложные математические задачи. В отличие от других доказуемо безопасных стойкий к столкновениям хешей, VSH эффективен и применим на практике. Асимптотически, требуется только одно умножение на журнал (п) биты сообщения и использует арифметику типа RSA. Следовательно, VSH может быть полезен во встроенных средах, где пространство кода ограничено.

Было предложено два основных варианта VSH. Во-первых, найти столкновение доказуемо так же сложно, как найти нетривиальный модульный квадратный корень из очень гладкого числа по модулюп. Другой использует простой модуль п (без люк ), и его доказательство безопасности опирается на трудность нахождения дискретных логарифмов очень гладких чисел по модулюп. Обе версии имеют одинаковую эффективность.

VSH не подходит в качестве замены случайный оракул, но может быть использован для создания доказуемо безопасной случайной хеш-функции. Эта функция может заменить функция люка используется в Схема подписи Крамера – Шупа, сохраняя доказуемую безопасность и сокращая время проверки примерно на 50%.

ВСН и ВССР

Все широко используемые криптографические хеш-функции не основаны на сложных математических задачах. Те немногие функции, которые построены на сложных математических задачах, называются доказуемо безопасный. Обнаружение столкновений тогда, как известно, так же сложно, как решить сложную математическую задачу. Для базовой версии функции Very Smooth Hash эта сложная проблема состоит в том, чтобы найти модульные квадратные корни (VSSR) из определенных специальных чисел (VSN).^[1] Предполагается, что это так сложно, как факторинг целых чисел.

Для фиксированной постоянной c и п целое число м это Очень гладкое число (VSN) если наибольший простой фактор м не больше (журналп)^c.

Целое число б это Очень гладкий квадратичный остаток ' по модулю п если наибольшее простое число в бs факторизация не более (logп)^c и существует целое число Икс такой, что ${ Displaystyle б эквив х ^ {2} мод п}$ . Целое число Икс считается Модульный квадратный корень изб.

Нас интересуют только нетривиальные квадратные корни, у которых Икс² ≥ п. Если Икс² < п, корень можно легко вычислить с помощью алгоритмов из полей характеристики 0, например реальное поле. Следовательно, они не подходят для криптографических примитивов.

Нетривиальный модульный квадратный корень для очень гладких чисел (VSSR) следующая проблема: Пусть п быть произведением двух неизвестных простых чисел примерно одинакового размера, и пусть ${ Displaystyle к Leq ( журнал п) ^ {с}}$ . Позволять ${ displaystyle p_ {1} = 2, p_ {2} = 3, p_ {3} = 5, dots}$ - последовательность простых чисел. ВССР - это следующая проблема: Учитывая п, найти ${ displaystyle x in mathbb {Z} _ {n} ^ {*}}$ такой, что ${ Displaystyle TextStyle х ^ {2} Equiv prod _ {я = 0} ^ {k} p_ {я} ^ {е_ {я}}}$ и хотя бы один из е₀,...,е_k странно.

В Допущение ВССР это то, что нет вероятностный полином (в ${ displaystyle log n}$ ) временной алгоритм, который решает VSSR с неотъемлемый вероятность. Это считается бесполезным для практики предположением, поскольку оно не говорит о том, для какого размера модулей VSSR является вычислительно трудным. Вместо Расчетное предположение VSSR используется. В нем говорится, что решить VSSR так же сложно, как факторинг труднодоступный ${ displaystyle s}$ битовый модуль, где ${ displaystyle s}$ несколько меньше размера ${ displaystyle n}$ .

Примеры ВСН и ВССР

Пусть параметры фиксируются следующим образом: ${ displaystyle c = 5}$ и ${ displaystyle n = 31}$ .

потом ${ Displaystyle m_ {1} = 35 = 5 cdot 7}$ является очень гладким числом по отношению к этим параметрам, потому что ${ displaystyle ( log 31) ^ {5} ~ { dot {=}} ~ 7.37}$ больше чем все ${ displaystyle m_ {1}}$ основные факторы. С другой стороны, ${ displaystyle m_ {2} = 55 = 5 cdot 11}$ не является VSN под ${ displaystyle c = 5}$ и ${ displaystyle n = 31}$ .

Целое число ${ displaystyle b_ {1} = 9}$ очень гладкий квадратичный остаток по модулю ${ displaystyle n}$ потому что это очень гладкое число (под ${ displaystyle c, n}$ ) и у нас есть ${ displaystyle x_ {1} = 3}$ такой, что ${ displaystyle x_ {1} ^ {2} = b_ {1}}$ (мод ${ displaystyle n}$ ). Это тривиальный модульный квадратный корень, потому что ${ displaystyle 3 ^ {2} not geq n}$ и поэтому модуль не участвует при возведении в квадрат.

Целое число ${ displaystyle b_ {2} = 15}$ также является очень гладким квадратичным остатком по модулю ${ displaystyle n}$ . Все простые множители меньше 7,37, а модульный квадратный корень равен ${ displaystyle x_ {2} = 20}$ поскольку ${ Displaystyle 20 ^ {2} = 400 экв 15}$ (мод ${ displaystyle n}$ ). Таким образом, это нетривиальный корень. Задача ВССР - найти ${ displaystyle x_ {2}}$ данный ${ displaystyle b_ {2}}$ и ${ displaystyle n}$ . И мы предполагаем, что это вычислительно так же сложно, как разложение на множители ${ displaystyle n}$ .

Алгоритм VSH, базовые версии

Позволять ${ displaystyle n}$ быть большим составным RSA и пусть ${ Displaystyle p_ {1} = 2, p_ {2} = 3, ldots}$ последовательность простых чисел. Позволять ${ displaystyle k}$ , длина блока - наибольшее целое число, такое что ${ displaystyle textstyle prod _ {я = 1} ^ {k} p_ {i}$ . Позволять ${ displaystyle m}$ быть ${ displaystyle ell}$ -битовое сообщение для хеширования, состоящее из битов ${ displaystyle (m_ {1}, ldots, m _ { ell})}$ и предположим, что ${ displaystyle ell <2 ^ {k}}$ . Чтобы вычислить хэш ${ displaystyle m}$ :

Икс₀ = 1
Позволять ${ displaystyle L}$ , наименьшее целое число, большее или равное ${ displaystyle l / k}$ , - количество блоков. Позволять ${ displaystyle m_ {i} = 0}$ за ${ Displaystyle L <я Leq Lk}$ (обивка)
Позволять ${ displaystyle textstyle ell = sum _ {i = 1} ^ {k} l_ {i} 2 ^ {i-1}}$ с ${ displaystyle ell _ {i} in {0,1 }}$ быть двоичным представлением длины сообщения ${ displaystyle ell}$ и определить ${ displaystyle m_ {Lk + i} = ell _ {i}}$ за ${ Displaystyle 1 Leq я Leq k}$ .
за j = 0, 1,..., L последовательно вычислить ${ displaystyle x_ {j + 1} = x_ {j} ^ {2} prod _ {i = 1} ^ {k} p_ {i} ^ {m_ {jk + i}} mod n}$
возвращаться Икс_{L + 1}.

Функция на шаге 4 называется функцией сжатия.

Свойства VSH

Длину сообщения не нужно знать заранее.
Найти коллизию в VSH так же сложно, как и решить VSSR. Таким образом, VSH (сильно) стойкий к столкновениям, что также подразумевает сопротивление второму прообразу. Устойчивость к прообразу VSH не доказана.
Функция сжатия не устойчива к столкновениям. Тем не менее, хэш-функция VSH устойчива к коллизиям на основе предположения VSSR. Измененная версия VSH, называемая VSH *, использует функцию сжатия, устойчивую к коллизиям, и примерно в 5 раз быстрее при хешировании коротких сообщений.
Поскольку длина вывода VSH - это длина защищенного модуля RSA, VSH кажется вполне подходящим на практике для создания подписей RSA «хэш-затем-знак» для сообщений произвольной длины. Однако такая подпись должна быть тщательно разработана, чтобы обеспечить ее безопасность. Наивный подход легко сломать CPA (атака по выбранному открытому тексту).
Эффективность: Стоимость каждой итерации меньше стоимости 3 модульных умножений. Базовая версия VSH вообще требует однократного умножения на ${ Displaystyle Omega ( журнал п / журнал журнал п)}$ биты сообщения.

Варианты ВШ

Было предложено несколько улучшений, ускорений и более эффективных вариантов VSH.^[1] Ни один из них не меняет основную концепцию функции. Эти улучшения называются:

Кубинг ВСХ (вместо возведения в квадрат).
VSH с увеличенным количеством малых простых чисел.
VSH с предварительно вычисленными произведениями простых чисел.
Быстрый ВШ.
Быстрый VSH с увеличенной длиной блока.

Вариант VSDL и VSH-DL

В ВШ-ДЛ представляет собой вариант VSH с дискретным логарифмом, не имеющий люк, его надежность зависит от сложности нахождения дискретного логарифма по простому модулю п.^[1]

Очень гладкий дискретный логарифм чисел (VSDL) это проблема, при которой для очень гладкого числа мы хотим найти его дискретный логарифм по модулю некоторого числа п.

Как и в предыдущем разделе, ${ displaystyle p_ {i}}$ мы обозначаем ${ displaystyle i}$ -е простое число. Пусть кроме того ${ displaystyle c}$ фиксированная константа и ${ displaystyle p}$ , ${ displaystyle q}$ быть простым с ${ displaystyle p = 2q + 1}$ и разреши ${ Displaystyle к Leq ( журнал р) ^ {с}}$ . VSDL - это следующая проблема: учитывая ${ displaystyle p}$ найти целые числа ${ displaystyle e_ {1}, ..., e_ {k}}$ такой, что ${ Displaystyle 2 ^ {е_ {1}} Equiv prod _ {я = 2} ^ {k} p_ {i} ^ {e_ {i}} mod p}$ с ${ displaystyle | e_ {i} |$ за ${ Displaystyle я = 1, ..., к}$ и хотя бы один из ${ displaystyle e_ {1}, ..., e_ {k}}$ ненулевой.

В Предположение VSDL это то, что нет вероятностный полином (в ${ displaystyle log p}$ ) временной алгоритм, который решает VSDL с неотъемлемый вероятность. Существует тесная связь между твердостью VSDL и трудностью вычисления дискретного логарифма по модулю ${ displaystyle p}$ , который напоминает, но несколько слабее, чем связь между VSSR и целочисленной факторизацией.

Безопасность VSH

Сильный сопротивление столкновению - единственное доказанное свойство VSH. Это не подразумевает сопротивление прообразу или другие важные свойства хэш-функции, и авторы заявляют, что «VSH не следует использовать для моделирования случайные оракулы, "и не могут быть заменены на конструкции, которые от них зависят (Подписи RSA, немного MAC ).^[1] VSH не следует рассматривать как хеш-функцию общего назначения, как это обычно понимается в техника безопасности.

Мультипликативное свойство

VSH мультипликативен: пусть Икс, y, и z быть тремя битовыми строками одинаковой длины, где zсостоит только из нулевых битов, и строки удовлетворяют х И у = г. Легко заметить, чтоH (z) H (x OR y) ≡ H (x) H (y) (mod n). В результате VSH уступает классической атаке компромисса времени и памяти, которая применяется к мультипликативным и аддитивным хешам.

Этот факт может быть использован для построения прообраза атаки против VSH ${ displaystyle ell}$ биты, которые имеют ${ displaystyle 2 ^ { ell / 2}}$ сложность, а не ${ displaystyle 2 ^ { ell}}$ как и ожидалось.

Атака на усеченную версию

VSH производит очень длинный хэш (обычно 1024 бита). Нет никаких указаний на то, что усеченный хэш VSH обеспечивает безопасность, соизмеримую с длиной хеша.

Существует частичная атака на VSH, усеченная до наименее значимой. л биты.^[2]

Сложность этой атаки против VSH:

Предварительное вычисление таблицы в автономном режиме: ${ displaystyle 2 ^ { ell / 3}}$ время и место.
Обнаружение столкновений: ${ displaystyle 2 ^ { ell / 3}}$ итераций.
Общая стоимость: примерно ${ displaystyle 2 ^ { ell / 3}}$ , скорее, чем ${ displaystyle 2 ^ { ell / 2}}$ как и ожидалось от хеш-функции с хорошими свойствами псевдослучайности.

Это, вероятно, исключает применимость VSH в схемах цифровой подписи, которые создают подписи короче, чем результат хеширования VSH, таких как схемы подписи с эллиптической кривой.