VSH
В криптографии очень гладкая хеш-функция (англ. Very Smooth Hash (VSH)) — n-битная эффективная криптографическая функция хеширования, разработанная в 2005 году Скоттом Котини, Лестрой Арьен и Роном Штайнфельдом. Является устойчивой к коллизиям в предположении большой вычислительной сложности нахождения нетривиального квадратного корня очень гладкого числа по модулю n. [1] Под понятием очень гладкой функции подразумевается, что граница гладкости является фиксированной полиномиальной функцией от n. Данный алгоритм хеширования предполагает одиночное умножение на бит сообщения и использует арифметику RSA-типа, что избавляет от необходимости отдельного хранения кода хеш-функции. Поэтому данный алгоритм полезен во встроенных средах, где пространство кода ограничено. Очень гладкая хеш-функция также может быть использована для создания односторонней функции с потайным входом, которая может быть применена в схемах подписи для ускорения проверки и усиления конфиденциальности.
VSSR и VSN
[править | править код]Для VSH основной математической проблемой является устойчивость к коллизиям, которая по сути состоит в извлечении корней по модулю n из очень гладких чисел, называемых очень гладкими корнями (VSSR). В свою очередь, проблема вычисления очень гладкого корня по модулю n тесно связана с факторизацией целых чисел с использованием общего метода решета числового поля.[2][3]
Для фиксированных постоянных c и n целое число m называется очень гладким числом, если все простые множители m не больше чем (log n)c. Целое число b является очень гладким квадратичным остатком по модулю n, если наибольшее простой множитель b — не более чем (log n)c и существует целое x такое что . Целое x называют очень корнем квадратным по модулю b.
Нас интересуют только корни где x2 ≥ n. Так как, если x2 < n, то корень может быть легко вычислен, используя поле характеристики 0. Вычисление очень гладкого корня является следующей задачей: пусть n является произведением двух простых чисел примерно одного размера и пусть , а последовательность простых чисел. По данному n необходимо найти , такое, что и хотя бы один из e0,…,ek будет нечетным.
Пример VSN и VSSR
[править | править код]Пусть зафиксированы следующие параметры: и .
Тогда очень гладкое число от данных параметров, потому что больше чем все простые множители . С другой стороны, не является очень гладким числом от и .
Целое число является очень гладким квадратичным остатком по модулю , потому что это число очень гладкое (от ) и существует , такое что (mod ). Это тривиальный квадратный корень, потому что и поэтому модуль при возведении в квадрат не учитывается.
Целое число также является квадратичным остатком по модулю . Все простые множители меньше чем 7.37, а все квадратные корни по модулю равны , так как (mod ). Задача VSSR состоит в том, чтобы найти по данным и . И вычислительно так же сложна, как факторизация .
VSH, базовый алгоритм
[править | править код]Пусть последовательность простых чисел. Пусть длина блока, наибольшее целое число, такое, что . Пусть есть -битное сообщение, состоящее из , которое должно быть хешировано, причем .Чтобы вычислить хеш [4]:
- x0 = 1
- Пусть наименьшее целое число, большее или равное , будет числом блоков. Пусть для
- Пусть с — бинарное представление сообщения длины и определим для .
- для каждого j = 0, 1,…, L вычисляем
- возвращаем 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.
Аналогично введенным ранее обозначениям, возьмем как -е простое число. Пусть — фиксированная постоянная и , — простые числа, такие, что и . VSDL-задача: по данному найти целые , такие, что , где для всех , причем, хотя бы один из ненулевой.
Предположение VSDL состоит в том, что не существует вероятностного полиномиального по времени алгоритма, решающего VSDL. Существует тесная связь между сложностью вычисления VSDL и сложностью вычисления дискретного логарифма по модулю .
См. также
[править | править код]Примечания
[править | править код]- ↑ S.Contini, A.Lestra, R.Steinfield. VSH, an Efficient and Provable Collision-Resistant Hash Function. // Eurocrypt. — 2006. — С. 1—2. Архивировано 4 декабря 2018 года.
- ↑ S.Contini, A.Lestra, R.Steinfield. VSH, an Efficient and Provable Collision-Resistant Hash Function. // Eurocrypt. — 2006. — С. 3. Архивировано 4 декабря 2018 года.
- ↑ 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 года.
- ↑ S.Contini, A.Lestra, R.Steinfield. VSH, an Efficient and Provable Collision-Resistant Hash Function. // Eurocrypt. — 2006. — С. 6. Архивировано 4 декабря 2018 года.
- ↑ S.Contini, A.Lestra, R.Steinfield. VSH, an Efficient and Provable Collision-Resistant Hash Function. // Eurocrypt. — 2006. — С. 8. Архивировано 4 декабря 2018 года.
- ↑ M.-J.O.Saarinen. Security of VSH in the real world // INDOCRYPT. — 2006. — С. 2. Архивировано 8 августа 2017 года.
- ↑ S.Contini, A.Lestra, R.Steinfield. VSH, an Efficient and Provable Collision-Resistant Hash Function. // Eurocrypt. — 2006. — С. 14. Архивировано 4 декабря 2018 года.
- ↑ M.-J.O.Saarinen. Security of VSH in the real world // INDOCRYPT. — 2006. — С. 3—4. Архивировано 8 августа 2017 года.
- ↑ S.Contini, A.Lestra, R.Steinfield. VSH, an Efficient and Provable Collision-Resistant Hash Function. // Eurocrypt. — 2006. — С. 10—13. Архивировано 4 декабря 2018 года.
Литература
[править | править код]- S.Contini, A.Lestra, R.Steinfield. VSH, an Efficient and Provable Collision-Resistant Hash Function. // Eurocrypt. — 2006. — С. 1—13.
- M.-J.O.Saarinen. Security of VSH in the real world // INDOCRYPT. — 2006.
- 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 года.