Очень плавный хэш

редактировать

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

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

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

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

Содержание

1 VSN и VSSR
- 1.1 Примеры VSN и VSSR
2 Алгоритм VSH, базовые версии
3 Свойства VSH
4 Варианты VSH
5 VSDL и VSH -DL вариант
6 Безопасность VSH
- 6.1 Мультипликативное свойство
- 6.2 Атака на усеченную версию
7 См. Также
8 Ссылки

VSN и VSSR

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

Для фиксированных констант c и n целое число m является очень гладким числом (VSN), если наибольший простой множитель m не превосходит (войти n).

Целое число b является очень гладким квадратичным остатком по модулю n, если наибольшее простое число в факторизации b s не больше (log n) и существует такое целое число x, что $б ≡ Икс 2 по модулю n {\ Displaystyle B \ Equiv x ^ {2} \ mod n}$ $b \ эквив x ^ 2 \ mod n$ . Целое число x называется модульным квадратным корнем числа b.

Нас интересуют только нетривиальные квадратные корни, у которых x ≥ n. Если x < n, the root can be easily computed using algorithms from fields of характеристики 0, например вещественное поле. Следовательно, они не подходят для криптографических примитивов.

Очень гладкое число Нетривиальный модульный квадратный корень (VSSR) - это следующая проблема: пусть n будет произведением двух неизвестных простых чисел примерно одинакового размера и пусть $k ≤ (log ⁡ n) c {\ стиль отображения к \ Leq (\ журнал п) ^ {с}}$ $k \ le (\ log n) ^ c$ . Пусть $p 1 = 2, p 2 = 3, p 3 = 5,… {\ displaystyle p_ {1} = 2, p_ {2} = 3, p_ {3} = 5, \ dots}$ $p_1 = 2, p_2 = 3, p_3 = 5, \ dots$ - последовательность простых чисел. VSSR представляет собой следующую задачу: для данного n найти $x ∈ Z n ∗ {\ displaystyle x \ in \ mathbb {Z} _ {n} ^ {*}}$ $x \ in \ mathbb {Z} ^ * _ n$ такое, что $x 2 ≡ ∏ я знак равно 0 kpiei {\ displaystyle \ textstyle x ^ {2} \ Equiv \ prod _ {i = 0} ^ {k} p_ {i} ^ {e_ {i}}}$ $\ textstyle x ^ 2 \ Equiv \ prod_ {i = 0} ^ k p_i ^ {e_i}$ и по меньшей мере одно из e 0,..., e k является нечетным.

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

Примеры VSN и VSSR

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

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

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

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

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

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

x0= 1
Пусть $L {\ displaystyle L}$ $L$ , наименьшее целое число, большее или равное $l / k {\ displaystyle l / k}$ $l / к$ - количество блоков. Пусть $mi = 0 {\ displaystyle m_ {i} = 0}$ $m_i = 0$ для $l < i ≤ L k {\displaystyle l$ $l <i \ leq Lk$ (padding)
Пусть $ℓ = ∑ i = 1 kli 2 i - 1 {\ displaystyle \ textstyle \ ell = \ sum _ {i = 1} ^ {k} l_ {i} 2 ^ {i-1}}$ $\ textstyle \ ell = \ sum_ {i = 1} ^ k l_i 2 ^ {i-1}$ с $ℓ i ∈ {0, 1 } {\ displaystyle \ ell _ {i} \ in \ {0,1 \}}$ $\ ell_i \ in \ {0, 1 \}$ - двоичное представление длины сообщения $ℓ {\ displaystyle \ ell}$ $\ ell$ и определим $m L K + i = ℓ i {\ displaystyle m_ {Lk + i} = \ ell _ {i}}$ $m_ {Lk + i} = \ ell_i$ для $1 ≤ i ≤ k {\ displaystyle 1 \ leq i \ leq k}$ $1 \ leq i \ leq k$ .
для j = 0, 1,..., L последовательно вычислить $xj + 1 = xj 2 ∏ i = 1 kpimjk + i mod n {\ displaystyle x_ {j + 1 } = x_ {j} ^ {2} \ prod _ {i = 1} ^ {k} p_ {i} ^ {m_ {jk + i}} \ mod n}$ $x_ {j + 1} = x_j ^ 2 \ prod_ {i = 1} ^ k p_i ^ { m_ {jk + i}} \ mod n$
return x L + 1.

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

Свойства VSH

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

Варианты VSH

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

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

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

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

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

Как и в предыдущем разделе, $pi {\ displaystyle p_ {i}}$ $p_ {i}$ мы обозначаем $i {\ displaystyle i}$ $i$ - й премьер. Кроме того, пусть $c {\ displaystyle c}$ $c$ будет фиксированной константой, а $p {\ displaystyle p}$ $p$ , $q {\ displaystyle q}$ $q$ быть простыми числами с $p = 2 q + 1 {\ displaystyle p = 2q + 1}$ $p = 2q + 1$ и пусть $k ≤ (log ⁡ p) c {\ displaystyle k \ leq (\ log p) ^ {c }}$ $k \ leq (\ log p) ^ c$ . VSDL представляет собой следующую проблему: для заданного $p {\ displaystyle p}$ $p$ найти целые числа $e 1,..., ek {\ displaystyle e_ {1},..., e_ {k}}$ $e_1,..., e_k$ так, что $2 e 1 ≡ ∏ i = 2 kpiei mod p {\ displaystyle 2 ^ {e_ {1 }} \ Equiv \ prod _ {i = 2} ^ {k} p_ {i} ^ {e_ {i}} \ mod p}$ $2 ^ {e_1} \ Equiv \ prod_ {i = 2} ^ k p_i ^ {e_i} \ mod p$ с $| e i | < q {\displaystyle |e_{i}|$ $| e_i | <q$ для $i = 1,..., k {\ displaystyle i = 1,..., k}$ $i = 1,..., k$ и хотя бы один из $e 1,..., е К {\ displaystyle e_ {1},..., e_ {k}}$ $e_1,..., e_k$ ненулевое значение.

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

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

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

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

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

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

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

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

Существует атака частичного столкновения на VSH, усеченная до младших l битов.

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

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

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

См. Также

Ссылки