Односторонняя функция сжатия: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Интерактивная навигация по истории
(Показать все непатрулированные изменения)
[непроверенная версия][непроверенная версия]
Следующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
← Новая страница: «В Криптографии, '''односторонняя функция сжатии''' - это такая фун…»
 
м + {{изолированная статья}}
Строка 7: Строка 7:
Односторонние функции сжатия часто построены из [[Блочный шифр|блочных шифров]]. Для того, чтобы превратить любой стандартный блочный шифр в одностороннюю функцию сжатия существуют схемы '''Девиса-Мейера''', '''Матиса-Мейера-Осеаса''', '''Миагучи-Пренеля''' (функции сжатия одноблочной длины).{{sfn|Авезова Яна Эдуардовна|p=60}} Эти методы подробно описаны ниже.
Односторонние функции сжатия часто построены из [[Блочный шифр|блочных шифров]]. Для того, чтобы превратить любой стандартный блочный шифр в одностороннюю функцию сжатия существуют схемы '''Девиса-Мейера''', '''Матиса-Мейера-Осеаса''', '''Миагучи-Пренеля''' (функции сжатия одноблочной длины).{{sfn|Авезова Яна Эдуардовна|p=60}} Эти методы подробно описаны ниже.


== Функция сжатия ==
== Функция сжатия ==
Функции сжатия представляют собой функции, которые получают на вход строку переменной длины и преобразуют её в строку фиксированной, обычно меньшей, длины.
Функции сжатия представляют собой функции, которые получают на вход строку переменной длины и преобразуют её в строку фиксированной, обычно меньшей, длины.


Строка 23: Строка 23:
* Стойкость к поиску первого прообраза – отсутствие эффективного полиномиального алгоритма вычисления обратной функции, то есть нельзя восстановить текст <math>m</math> по известной его свертке <math>H(m)</math> за реальное время (необратимость). Это свойство эквивалентно тому, что хэш-функция является односторонней функцией.
* Стойкость к поиску первого прообраза – отсутствие эффективного полиномиального алгоритма вычисления обратной функции, то есть нельзя восстановить текст <math>m</math> по известной его свертке <math>H(m)</math> за реальное время (необратимость). Это свойство эквивалентно тому, что хэш-функция является односторонней функцией.
* Стойкость к поиску второго прообраза (коллизиям первого рода). Зная входное сообщение <math>m_{1}</math> и его свёртку <math>H(m_{1})</math>, вычислительно невозможно найти другой вход <math>m_{2}</math>, чтобы <math>H(m_{1})=H(m_{2})</math>.
* Стойкость к поиску второго прообраза (коллизиям первого рода). Зная входное сообщение <math>m_{1}</math> и его свёртку <math>H(m_{1})</math>, вычислительно невозможно найти другой вход <math>m_{2}</math>, чтобы <math>H(m_{1})=H(m_{2})</math>.
* [[Коллизия хеш-функции|Стойкость к коллизиям]] (коллизиям второго рода). Должно быть вычислительно невозможно подобрать пару сообщений <math>m_{1}</math> и <math>m_{2}</math> , что <math>H(m_{1})=H(m_{2})</math>.{{sfn|С.В.Дубров|2012|p = 65}}
* [[Коллизия хеш-функции|Стойкость к коллизиям]] (коллизиям второго рода). Должно быть вычислительно невозможно подобрать пару сообщений <math>m_{1}</math> и <math>m_{2}</math> , что <math>H(m_{1})=H(m_{2})</math>.{{sfn|С.В.Дубров|2012|p = 65}}
Сведем задачу [[Криптоанализ|криптоанализа]] хэш-функций к задаче поиска коллизии: сколько сообщений надо просмотреть, чтобы найти сообщения с двумя одинаковыми хэшами. Вероятность встретить одинаковые хэши для сообщений из двух разных наборов, содержащих <math>n_{1}</math> и <math>n_{2}</math> текстов, равна <math>P \thickapprox 1 - e^{-\frac{n_{1}\cdot n_{2}}{2^l}}</math>. Если <math>n_{1}=n_{2}=2^{l/2}</math>, то вероятность успеха атаки <math>P \thickapprox 1-e^{-1} \thickapprox 0,63</math>, а сложность проведения атаки <math>2^{l/2+1}</math> операций. Чтобы найти коллизию, надо сгенерировать два псевдослучайных множества сообщений (в каждом множестве <math>2^{n/2}</math> сообщений) и найти для них хэши. Тогда согласно [[парадокс дней рождения|парадоксу дней рождения]] (смотрите также [[атака «дней рождения»]]), вероятность того, что среди них найдется пара сообщений с одинаковыми хэшами, больше 0,5. Атака требует большого объема памяти для хранения текстов и эффективных методов сортировки.{{sfn|С.В.Дубров|2012|pp = 66-67}}
Сведем задачу [[Криптоанализ|криптоанализа]] хэш-функций к задаче поиска коллизии: сколько сообщений надо просмотреть, чтобы найти сообщения с двумя одинаковыми хэшами. Вероятность встретить одинаковые хэши для сообщений из двух разных наборов, содержащих <math>n_{1}</math> и <math>n_{2}</math> текстов, равна <math>P \thickapprox 1 - e^{-\frac{n_{1}\cdot n_{2}}{2^l}}</math>. Если <math>n_{1}=n_{2}=2^{l/2}</math>, то вероятность успеха атаки <math>P \thickapprox 1-e^{-1} \thickapprox 0,63</math>, а сложность проведения атаки <math>2^{l/2+1}</math> операций. Чтобы найти коллизию, надо сгенерировать два псевдослучайных множества сообщений (в каждом множестве <math>2^{n/2}</math> сообщений) и найти для них хэши. Тогда согласно [[парадокс дней рождения|парадоксу дней рождения]] (смотрите также [[атака «дней рождения»]]), вероятность того, что среди них найдется пара сообщений с одинаковыми хэшами, больше 0,5. Атака требует большого объема памяти для хранения текстов и эффективных методов сортировки.{{sfn|С.В.Дубров|2012|pp = 66-67}}


==Структура Меркла — Дамгарда==
== Структура Меркла — Дамгарда ==
{{Главная статья|Структура Меркла — Дамгарда}}
{{Главная статья|Структура Меркла — Дамгарда}}
[[Image:Merkle-Damgard hash big.svg|thumb|400px|right|Структура Меркла-Дамгарда, где IV – начальное значение свертки (фиксированный вектор), f –
[[Image:Merkle-Damgard hash big.svg|thumb|400px|right|Структура Меркла-Дамгарда, где IV – начальное значение свертки (фиксированный вектор), f –
Строка 34: Строка 34:


Наиболее широко используются хэш-функции, основанные на этой конструкции в [[MD5]], [[SHA-1]] и [[SHA-2]].
Наиболее широко используются хэш-функции, основанные на этой конструкции в [[MD5]], [[SHA-1]] и [[SHA-2]].

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


Строка 79: Строка 79:


:<math>H_i = E_{g(H_{i-1})}(m_i)\oplus H_{i-1}\oplus m_i.</math>
:<math>H_i = E_{g(H_{i-1})}(m_i)\oplus H_{i-1}\oplus m_i.</math>



<!--
<!--
Строка 97: Строка 96:


== Литература ==
== Литература ==

=== Книги ===
=== Книги ===


Строка 160: Строка 160:
|ref = R. Winternitz. ''A secure one-way hash function built from DES.'' In Proceedings of the IEEE Symposium on Information Security and Privacy
|ref = R. Winternitz. ''A secure one-way hash function built from DES.'' In Proceedings of the IEEE Symposium on Information Security and Privacy
}}
}}

=== Научные статьи ===
=== Научные статьи ===
* {{статья
* {{статья
Строка 177: Строка 178:
|ref = А.В. Антонов
|ref = А.В. Антонов
}}
}}

{{изолированная статья}}


[[Категория:Криптография]]
[[Категория:Криптография]]

Версия от 23:17, 9 декабря 2016

В Криптографии, односторонняя функция сжатии - это такая функция, которая образует значение длиной n на выходе при задании двух входных значений длиной n.[1] Одностороннее преобразование означает, что легко вычислить значение хэш-функции по прообразу, но трудно создать прообраз, значение хэш-функции которого равно заданной величине.[2][3]

Односторонняя функция сжатия

Односторонняя функция сжатия используется, например, в структуре Меркла — Дамгарда внутри криптографических хэш-функциях.

Односторонние функции сжатия часто построены из блочных шифров. Для того, чтобы превратить любой стандартный блочный шифр в одностороннюю функцию сжатия существуют схемы Девиса-Мейера, Матиса-Мейера-Осеаса, Миагучи-Пренеля (функции сжатия одноблочной длины).[4] Эти методы подробно описаны ниже.

Функция сжатия

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

Например, если вход А имеет длину в 128 бит, вход B в 128 бит, и они сжаты вместе в один выход в 128 бит. Это то же самое, как если бы один единственный 256-битовый вход сжимался вместе в один выход в 128 бит.

Некоторые функции сжатия имеют различный размер двух входов, но выход, как правило, имеет такой же размер, как и один из входов. Например, вход А может быть 256 бит, вход B 128 бит, и они сжаты вместе с одним выходом в 128 бит. То есть, в общей сложности 384 входных битов сжимаются вместе до 128 выходных битов.[5]

Таким образом, смешивание выполняется за счет достижения лавинного эффекта.То есть, каждый выходной бит зависит от каждого входного бита.[6]

Односторонняя функция

Основная статья: Односторонняя функция
Функция сжатия в одну сторону должна обладать следующими свойствами:
  • Стойкость к поиску первого прообраза – отсутствие эффективного полиномиального алгоритма вычисления обратной функции, то есть нельзя восстановить текст по известной его свертке за реальное время (необратимость). Это свойство эквивалентно тому, что хэш-функция является односторонней функцией.
  • Стойкость к поиску второго прообраза (коллизиям первого рода). Зная входное сообщение и его свёртку , вычислительно невозможно найти другой вход , чтобы .
  • Стойкость к коллизиям (коллизиям второго рода). Должно быть вычислительно невозможно подобрать пару сообщений и , что .[7]

Сведем задачу криптоанализа хэш-функций к задаче поиска коллизии: сколько сообщений надо просмотреть, чтобы найти сообщения с двумя одинаковыми хэшами. Вероятность встретить одинаковые хэши для сообщений из двух разных наборов, содержащих и текстов, равна . Если , то вероятность успеха атаки , а сложность проведения атаки операций. Чтобы найти коллизию, надо сгенерировать два псевдослучайных множества сообщений (в каждом множестве сообщений) и найти для них хэши. Тогда согласно парадоксу дней рождения (смотрите также атака «дней рождения»), вероятность того, что среди них найдется пара сообщений с одинаковыми хэшами, больше 0,5. Атака требует большого объема памяти для хранения текстов и эффективных методов сортировки.[8]

Структура Меркла — Дамгарда

Основная статья: Структура Меркла — Дамгарда
Структура Меркла-Дамгарда, где IV – начальное значение свертки (фиксированный вектор), f – функция сжатия.

Суть конструкции заключается в итеративном процессе последовательных преобразований, когда на вход каждой итерации поступает блок исходного текста и выход предыдущей итерации.[9]

Наиболее широко используются хэш-функции, основанные на этой конструкции в MD5, SHA-1 и SHA-2.

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

Атака нахождения второго прообраза (учитывая сообщение , злоумышленник находит еще одно сообщение , чтобы удовлетворить ) может быть выполнена в соответствии с Килси и Шнайером, для сообщения из 2k блоков может быть выполнена за время k × 2n/2+1 + 2n-k+1. Важно отметить, если сообщения длинные, то сложность атаки находится между 2n/2 и 2n, а когда длина сообщения становится меньше, сложность приближается к 2n.[10]

Роль функции сжатия может осуществлять любой блочный шифр E. Данная идея легла в основу развития конструкции Меркла-Дамгарда в схемах Девиса-Мейера, Матиса-Мейера-Осеаса, Миагучи-Пренеля.[11]

Структура Девиса-Мейера

Схема Девиса-Мейера

В данной схеме блок сообщения и предыдущее значение хэш-функции поступают в качестве ключа и блока открытого текста соответственно на вход блочного шифра . Получившийся в результате шифрования блок закрытого текста суммируется (операция XOR) с результатом предыдущей итерации хеширования () для получения следующего значения хэш-функции ().[11]

В математических обозначениях схему Девиса-Мейера можно записать как:

Если блочный шифр использует, например, 256-битный ключ, то каждый блок сообщений () представляет собой 256-битный фрагмент сообщения. Если же блочный шифр использует размер блока в 128 бит, то входные и выходные значения хэш-функции в каждом раунде составляют 128 бит.

Важным свойством конструкции Девиса-Мейера является то, что даже если базовый блок шифрования является полностью безопасным, можно вычислить неподвижные точки для построения: для любого можно найти значение такое что  : просто нужно установить .[12]

Безопасность структуры Девиса-Мейера была впервые доказана Р.Винтерницом.[13]

Структура Матиса-Мейера-Осеаса

Схема Матиса-Мейера-Осеаса

Это версия схемы Девиса-Мейера: блоки сообщения применяются как ключи криптосистемы. Схема может быть использована, если блоки данных и ключ шифрования имеют один и тот же размер. Например, AES хорошо подходит для этой цели.

В данной конструкции блок сообщения и предыдущее значение хеш-функции поступают в качестве ключа и блока открытого текста соответственно на вход блочного шифра . Но уже значение подвергается предварительной обработке функцией из-за возможных различий в размерах хеш-суммы и размере ключа шифра . Эта функция реализует отображение n-битного значения хеш- функции в k-битный ключ шифра . В результате применения операции шифрования, получается блок закрытого текста, который суммируется с соответствующим ему блоком открытого текста ().[14]

В математических обозначениях схему Матиса-Мейера-Осеаса можно записать как:

Структура Миагучи-Пренеля

Основная статья: Односторонняя функция сжатия Миагучи-Пренеля
Схема Миагучи-Пренеля

Схема Миагучи-Пренеля - расширенная версия схемы Матиса-Мейера-Осеаса. Отличие в том, что блок закрытого текста суммируется не только с соответствующим ему блоком открытого текста (), но и с результатом предыдущей итерации хеширования (). Чтобы сделать алгоритм более устойчивым к атаке, исходный текст, ключ шифра и зашифрованный текст складываются с помощью операции XOR и создают новый дайджест. Эта схема используется в Whirlpool для создания хэш-функции. Результат суммирования определяется уравнением[15]:


Примечания

  1. ↑ Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Fifth Printing, August 2001.
  2. ↑ Брюс Шнайер, 2006, pp. 37-38.
  3. ↑ В.В.Ященко, 1999, p. 30.
  4. ↑ Авезова Яна Эдуардовна, p. 60.
  5. ↑ С.Баричев, Р.Серов, 2001, pp. 106-108.
  6. ↑ А.В. Антонов, 2012, pp. 106-107.
  7. ↑ С.В.Дубров, 2012, p. 65.
  8. ↑ С.В.Дубров, 2012, pp. 66-67.
  9. ↑ Авезова Яна Эдуардовна, 2015, pp. 60-61.
  10. ↑ John Kelsey and Bruce Schneier. Second preimages on n-bit hash functions for much less than 2n work. In Ronald Cramer, editor, EUROCRYPT, volume 3494 of LNCS. Springer, 2005, pp. 474-490.
  11. ↑ 1 2 Авезова Яна Эдуардовна, 2015, p. 61.
  12. ↑ Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Fifth Printing, August 2001, p. 375.
  13. ↑ R. Winternitz. A secure one-way hash function built from DES. In Proceedings of the IEEE Symposium on Information Security and Privacy, 1984, pp. 88-90.
  14. ↑ Авезова Яна Эдуардовна, 2015, pp. 61-62.
  15. ↑ Авезова Яна Эдуардовна, 2015, p. 62.

См. также

Источник — https://ru.wikipedia.org/ruwiki/w/index.php?title=Односторонняя_функция_сжатия&oldid=82393779