Очень гладкий хеш

Очень гладкий хеш (VSH)
Общий
Дизайнеры	Скотт Контини , Арьен К. Ленстра , Рон Стейнфелд
Впервые опубликовано	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 такое, что $b\equiv x^{2}\mod n$ . Говорят, что целое число x является модульным квадратным корнем из b .

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

Нетривиальный модульный квадратный корень очень гладкого числа (VSSR) — это следующая задача: пусть n — произведение двух неизвестных простых чисел примерно одинакового размера, и пусть $k\leq (\log n)^{c}$ . Позволять $p_{1}=2,p_{2}=3,p_{3}=5,\dots$ быть последовательностью простых чисел. VSSR — это следующая задача: по заданному n найти $x\in \mathbb {Z} _{n}^{*}$ такой, что $\textstyle x^{2}\equiv \prod _{i=0}^{k}p_{i}^{e_{i}}$ хотя бы одно из e0 _ek ,..., нечетно _и .

Предположение VSSR состоит в том, что не существует вероятностного полинома (в $\log n$ ) временной алгоритм, который решает VSSR с немалой вероятностью. Это считается бесполезным для практики предположением, поскольку оно не говорит о том, для какого размера модулей VSSR является вычислительно трудным. Вместо этого вычислительное предположение VSSR используется . В нем говорится, что решение VSSR считается таким же сложным, как и факторизация трудно поддающегося факторингу фактора. $s$ битовый модуль, где $s$ несколько меньше размера $n$ .

Примеры VSN и VSSR [ править ]

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

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

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

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

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

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

х ₀ = 1
Позволять $L$ , наименьшее целое число, большее или равное $l/k$ , — количество блоков. Позволять $m_{i}=0$ для $l<i\leq Lk$ (дополнение)
Позволять $\textstyle \ell =\sum _{i=1}^{k}l_{i}2^{i-1}$ с $\ell _{i}\in \{0,1\}$ быть двоичным представлением длины сообщения $\ell$ и определить $m_{Lk+i}=\ell _{i}$ для $1\leq i\leq k$ .
для j = 0, 1,..., L последовательно вычислить $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 (атака с выбранным открытым текстом) .
Эффективность : стоимость каждой итерации меньше стоимости трех модульных умножений. Базовая версия VSH вообще требует однократного умножения на каждый $\Omega (\log n/\log \log n)$ биты сообщения.

Варианты ВШ [ править ]

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

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

Вариант VSDL и VSH-DL [ править ]

VSH -DL — это вариант VSH с дискретным логарифмом, у которого нет лазейки , его безопасность зависит от сложности нахождения дискретного логарифма по модулю простого числа p . ^[1]

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

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

Предположение VSDL состоит в том, что не существует вероятностного полинома (в $\log p$ ) временной алгоритм, который решает VSDL с немалой вероятностью. Существует сильная связь между сложностью VSDL и сложностью вычисления дискретного логарифма по модулю. $p$ , что напоминает, но несколько слабее, связь между 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 $\ell$ биты, которые имеют $2^{\ell /2}$ сложность, а не $2^{\ell }$ как и ожидалось.

Атака на усеченную версию [ править ]

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

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

Сложность этой атаки на VSH заключается в следующем:

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

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

См. также [ править ]

Ссылки [ править ]

^ Jump up to: Перейти обратно: ^а ^б ^с ^д ^и Контини, С.; Ленстра, А.; Стейнфельд, Р. (23 июня 2005 г.), VSH, эффективная и доказуемая устойчивая к коллизиям хэш-функция.
^ Сааринен, М.-ЙО (2006), «Безопасность VSH в реальном мире» (PDF) , Прогресс в криптологии - INDOCRYPT 2006 , Конспекты лекций по информатике, том. 4329, стр. 95–103, номер документа : 10.1007/11941378_8 , ISBN. 978-3-540-49767-7 ^{[ мертвая ссылка ]}

[main-1] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и Контини, С.; Ленстра, А.; Стейнфельд, Р. (23 июня 2005 г.), VSH, эффективная и доказуемая устойчивая к коллизиям хэш-функция.

[attack-2] Сааринен, М.-ЙО (2006), «Безопасность VSH в реальном мире» (PDF) , Прогресс в криптологии - INDOCRYPT 2006 , Конспекты лекций по информатике, том. 4329, стр. 95–103, номер документа : 10.1007/11941378_8 , ISBN. 978-3-540-49767-7 ^{[ мертвая ссылка ]}

[1]

[2]