Перейти к содержанию

VSH

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис

В криптографии очень гладкая хеш-функция (англ. Very Smooth Hash (VSH)) — n-битная эффективная криптографическая функция хеширования, разработанная в 2005 году Скоттом Котини, Лестрой Арьен и Роном Штайнфельдом. Является устойчивой к коллизиям в предположении большой вычислительной сложности нахождения нетривиального квадратного корня очень гладкого числа по модулю n. [1] Под понятием очень гладкой функции подразумевается, что граница гладкости является фиксированной полиномиальной функцией от n. Данный алгоритм хеширования предполагает одиночное умножение на [math]\displaystyle{ \Omega(n) }[/math] бит сообщения и использует арифметику RSA-типа, что избавляет от необходимости отдельного хранения кода хеш-функции. Поэтому данный алгоритм полезен во встроенных средах, где пространство кода ограничено. Очень гладкая хеш-функция также может быть использована для создания односторонней функции с потайным входом, которая может быть применена в схемах подписи для ускорения проверки и усиления конфиденциальности.

VSSR и VSN

Для VSH основной математической проблемой является устойчивость к коллизиям, которая по сути состоит в извлечении корней по модулю n из очень гладких чисел, называемых очень гладкими корнями (VSSR). В свою очередь, проблема вычисления очень гладкого корня по модулю n тесно связана с факторизацией целых чисел с использованием общего метода решета числового поля.[2][3]

Для фиксированных постоянных c и n целое число m называется очень гладким числом, если все простые множители m не больше чем (log n)c. Целое число b является очень гладким квадратичным остатком по модулю n, если наибольшее простой множитель b — не более чем (log n)c и существует целое x такое что [math]\displaystyle{ b \equiv x^2 \mod n }[/math]. Целое x называют очень корнем квадратным по модулю  b.

Нас интересуют только корни где x2 ≥ n. Так как, если x2 < n, то корень может быть легко вычислен, используя поле характеристики 0. Вычисление очень гладкого корня является следующей задачей: пусть n является произведением двух простых чисел примерно одного размера и пусть [math]\displaystyle{ k\le(\log n)^c }[/math], а [math]\displaystyle{ p_1 = 2, p_2 = 3, p_3 = 5,\dots }[/math] последовательность простых чисел. По данному n необходимо найти [math]\displaystyle{ x \in \mathbb{Z}^*_n }[/math], такое, что [math]\displaystyle{ \textstyle x^2 \equiv \prod_{i=0}^k p_i^{e_i} }[/math] и хотя бы один из e0,…,ek будет нечетным.

Пример VSN и VSSR

Пусть зафиксированы следующие параметры: [math]\displaystyle{ c=5 }[/math] и [math]\displaystyle{ n=31 }[/math].

Тогда [math]\displaystyle{ m_1 = 35 = 5 \cdot 7 }[/math] очень гладкое число от данных параметров, потому что [math]\displaystyle{ (\log 31)^5~\dot{=}~7.37 }[/math] больше чем все простые множители [math]\displaystyle{ m_1 }[/math]. С другой стороны, [math]\displaystyle{ m_2 = 55 = 5\cdot 11 }[/math] не является очень гладким числом от [math]\displaystyle{ c=5 }[/math] и [math]\displaystyle{ n=31 }[/math].

Целое число [math]\displaystyle{ b_1 = 9 }[/math] является очень гладким квадратичным остатком по модулю [math]\displaystyle{ n }[/math], потому что это число очень гладкое (от [math]\displaystyle{ c, n }[/math]) и существует [math]\displaystyle{ x_1 = 3 }[/math], такое что [math]\displaystyle{ x_1^2 = b_1 }[/math] (mod [math]\displaystyle{ n }[/math]). Это тривиальный квадратный корень, потому что [math]\displaystyle{ 3^2 \not\geq n }[/math] и поэтому модуль при возведении в квадрат не учитывается.

Целое число [math]\displaystyle{ b_2 = 15 }[/math] также является квадратичным остатком по модулю [math]\displaystyle{ n }[/math]. Все простые множители меньше чем 7.37, а все квадратные корни по модулю равны [math]\displaystyle{ x_2 = 20 }[/math], так как [math]\displaystyle{ 20^2 = 400 \equiv 15 }[/math] (mod [math]\displaystyle{ n }[/math]). Задача VSSR состоит в том, чтобы найти [math]\displaystyle{ x_2 }[/math] по данным [math]\displaystyle{ b_2 }[/math] и [math]\displaystyle{ n }[/math]. И вычислительно так же сложна, как факторизация [math]\displaystyle{ n }[/math].

VSH, базовый алгоритм

Пусть [math]\displaystyle{ p_1 = 2, p_2 = 3, \ldots }[/math] последовательность простых чисел. Пусть [math]\displaystyle{ k }[/math] длина блока, наибольшее целое число, такое, что [math]\displaystyle{ \textstyle \prod_{i = 1}^k p_i \lt n }[/math]. Пусть [math]\displaystyle{ m }[/math] есть [math]\displaystyle{ \ell }[/math]-битное сообщение, состоящее из [math]\displaystyle{ (m_1,\ldots,m_{\ell}) }[/math], которое должно быть хешировано, причем [math]\displaystyle{ \ell \lt 2^k }[/math].Чтобы вычислить хеш [math]\displaystyle{ m }[/math][4]:

  1. x0 = 1
  2. Пусть [math]\displaystyle{ L }[/math] наименьшее целое число, большее или равное [math]\displaystyle{ l/k }[/math], будет числом блоков. Пусть [math]\displaystyle{ m_i = 0 }[/math] для [math]\displaystyle{ l \lt i \leq Lk }[/math]
  3. Пусть [math]\displaystyle{ \textstyle \ell = \sum_{i=1}^k l_i 2^{i-1} }[/math] с [math]\displaystyle{ \ell_i \in \{0, 1\} }[/math] — бинарное представление сообщения длины [math]\displaystyle{ \ell }[/math] и определим [math]\displaystyle{ m_{Lk+i}= \ell_i }[/math] для [math]\displaystyle{ 1 \leq i \leq k }[/math].
  4. для каждого j = 0, 1,…, L вычисляем [math]\displaystyle{ x_{j+1} = x_j^2 \prod_{i=1}^k p_i^{m_{jk+i}}\mod n }[/math]
  5. возвращаем xL + 1.

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

Свойства VSH

  • Не нужно знать заранее длину сообщения.
  • Сложность обнаружения коллизий равна сложности нахождения очень гладкого корня, поэтому VSH устойчива к коллизиям. Стойкость к коллизиям единственное доказанное свойство для VSH.[5][6]
  • Функция сжатия не является стойкой к коллизиям. Однако хеш-функция устойчива к коллизиям на основе VSSR-предположения. Следующая версия VSH* использует стойкую к коллизиям функцию сжатия и работает в 5 раз быстрее на коротких сообщениях.[7]
  • VSH мультипликативна:

Пусть x, y, and z — трехбитные строчки равной длины, где z состоит только из нулевых бит и удовлетворяет x AND y = z. Тогда H(z)H(x OR y) ≡ H(x)H(y) (mod n). VSH уступает классической атаке на временную память, которая применяется к мультипликативным и аддитивным хешам.[8]

Вариации VSH

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

  • Кубический VSH (вместо квадратичного).
  • VSH с увеличением количества простых чисел.
  • VSH с вычисленным произведением простых чисел.
  • Быстрый VSH.
  • Быстрый VSH с увеличенным числом блоков.
  • VSH-DL

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

Very Smooth Number Discrete Logarithm (VSDL) — это дискретный логарифм от некоторого VSN, взятый по модулю некоторого числа n.

Аналогично введенным ранее обозначениям, возьмем [math]\displaystyle{ p_i }[/math] как [math]\displaystyle{ i }[/math]-е простое число. Пусть [math]\displaystyle{ c }[/math] — фиксированная постоянная и [math]\displaystyle{ p }[/math], [math]\displaystyle{ q }[/math] — простые числа, такие, что [math]\displaystyle{ p = 2q + 1 }[/math] и [math]\displaystyle{ k \leq (\log p)^c }[/math]. VSDL-задача: по данному [math]\displaystyle{ p }[/math] найти целые [math]\displaystyle{ e_1,...,e_k }[/math], такие, что [math]\displaystyle{ 2^{e_1} \equiv \prod_{i=2}^k p_i^{e_i} \mod p }[/math], где [math]\displaystyle{ |e_i| \lt q }[/math] для всех [math]\displaystyle{ i = 1,...,k }[/math], причем, хотя бы один из [math]\displaystyle{ e_1,...,e_k }[/math] ненулевой.

Предположение VSDL состоит в том, что не существует вероятностного полиномиального по времени алгоритма, решающего VSDL. Существует тесная связь между сложностью вычисления VSDL и сложностью вычисления дискретного логарифма по модулю [math]\displaystyle{ p }[/math].

См. также

Примечания

  1. ↑ S.Contini, A.Lestra, R.Steinfield. VSH, an Efficient and Provable Collision-Resistant Hash Function. // Eurocrypt. — 2006. — С. 1—2. Архивировано 4 декабря 2018 года.
  2. ↑ S.Contini, A.Lestra, R.Steinfield. VSH, an Efficient and Provable Collision-Resistant Hash Function. // Eurocrypt. — 2006. — С. 3. Архивировано 4 декабря 2018 года.
  3. ↑ Bart Preneel. [https://www.esat.kuleuven.be/cosic/publications/article-1532.pdf The First 30 Years of Cryptographic Hash Functions and the NIST SHA-3 Competition] // Cryptographers’ Track at the RSA Conference. — 2010. — С. 5. Архивировано 11 августа 2017 года.
  4. ↑ S.Contini, A.Lestra, R.Steinfield. VSH, an Efficient and Provable Collision-Resistant Hash Function. // Eurocrypt. — 2006. — С. 6. Архивировано 4 декабря 2018 года.
  5. ↑ S.Contini, A.Lestra, R.Steinfield. VSH, an Efficient and Provable Collision-Resistant Hash Function. // Eurocrypt. — 2006. — С. 8. Архивировано 4 декабря 2018 года.
  6. ↑ M.-J.O.Saarinen. Security of VSH in the real world // INDOCRYPT. — 2006. — С. 2. Архивировано 8 августа 2017 года.
  7. ↑ S.Contini, A.Lestra, R.Steinfield. VSH, an Efficient and Provable Collision-Resistant Hash Function. // Eurocrypt. — 2006. — С. 14. Архивировано 4 декабря 2018 года.
  8. ↑ M.-J.O.Saarinen. Security of VSH in the real world // INDOCRYPT. — 2006. — С. 3—4. Архивировано 8 августа 2017 года.
  9. ↑ S.Contini, A.Lestra, R.Steinfield. VSH, an Efficient and Provable Collision-Resistant Hash Function. // Eurocrypt. — 2006. — С. 10—13. Архивировано 4 декабря 2018 года.

Литература

Functions and the NIST SHA-3 Competition] // Cryptographers’ Track at the RSA Conference. — 2010. — С. 5. Архивировано 11 августа 2017 года.

Источник — https://xn--h1ajim.xn--p1ai/index.php?title=VSH&oldid=5861942