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

VSSR и VSN

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

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

Нас интересуют только корни где x ² ≥ n . Так как, если x ² < n , то корень может быть легко вычислен, используя поле характеристики 0. Вычисление очень гладкого корня является следующей задачей: пусть n является произведением двух простых чисел примерно одного размера и пусть ${\displaystyle k\leq (\log n)^{c}}$ , а ${\displaystyle p_{1}=2,p_{2}=3,p_{3}=5,\dots }$ последовательность простых чисел. По данному n необходимо найти ${\displaystyle x\in \mathbb {Z} _{n}^{*}}$ , такое, что ${\displaystyle \textstyle x^{2}\equiv \prod _{i=0}^{k}p_{i}^{e_{i}}}$ и хотя бы один из e ₀ ,…, e _k будет нечетным.

Пример VSN и VSSR

Пусть зафиксированы следующие параметры: ${\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}$ не является очень гладким числом от ${\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}}$ (mod ${\displaystyle n}$ ). Это тривиальный квадратный корень, потому что ${\displaystyle 3^{2}\not \geq n}$ и поэтому модуль при возведении в квадрат не учитывается.

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

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

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

1. x ₀ = 1
2. Пусть ${\displaystyle L}$ наименьшее целое число, большее или равное ${\displaystyle l/k}$ , будет числом блоков. Пусть ${\displaystyle m_{i}=0}$ для ${\displaystyle l<i\leq Lk}$
3. Пусть ${\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 i\leq k}$ .
4. для каждого j = 0, 1,…, L вычисляем ${\displaystyle x_{j+1}=x_{j}^{2}\prod _{i=1}^{k}p_{i}^{m_{jk+i}}\mod n}$
5. возвращаем x _{L + 1} .

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

Свойства VSH

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

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

Вариации VSH

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

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

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

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

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

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

См. также

• Криптографические хеш-функции
• Хеширование

Примечания

Литература

• S.Contini, A.Lestra, R.Steinfield. // Eurocrypt. — 2006. — С. 1—13 .
• M.-J.O.Saarinen. // INDOCRYPT. — 2006.
• Bart Preneel. [ The First 30 Years of Cryptographic Hash

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