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

Интерактивная навигация по истории

(Показать все непатрулированные изменения)

[непроверенная версия]

← Предыдущая правка

Содержимое удалено Содержимое добавлено

ВизуальныйВики-текст

Линейный

Текущая версия от 00:36, 1 декабря 2021

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

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

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

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

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

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

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

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

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

Функция сжатия в одну сторону должна обладать следующими свойствами:

Стойкость к поиску первого прообраза — отсутствие эффективного полиномиального алгоритма вычисления обратной функции, то есть нельзя восстановить текст $m$ по известной его свертке $H(m)$ за реальное время (необратимость). Это свойство эквивалентно тому, что хеш-функция является односторонней функцией.
Стойкость к поиску второго прообраза (коллизиям первого рода). Зная входное сообщение $m_{1}$ и его свёртку $H(m_{1})$ , вычислительно невозможно найти другой вход $m_{2}$ , чтобы $H(m_{1})=H(m_{2})$ .
Стойкость к коллизиям (коллизиям второго рода). Должно быть вычислительно невозможно подобрать пару сообщений $m_{1}$ и $m_{2}$ , что $H(m_{1})=H(m_{2})$ .^[7]

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

Вероятность встретить одинаковые хеши для сообщений из двух разных наборов, содержащих $n_{1}$ и $n_{2}$ текстов, равна $P\thickapprox 1-e^{-{\frac {n_{1}\cdot n_{2}}{2^{l}}}}$ . Если $n_{1}=n_{2}=2^{l/2}$ , то вероятность успеха атаки $P\thickapprox 1-e^{-1}\thickapprox 0,63$ , а сложность проведения атаки $2^{l/2+1}$ операций.

Чтобы найти коллизию, надо сгенерировать два псевдослучайных множества сообщений (в каждом множестве $2^{n/2}$ сообщений) и найти для них хеши. Тогда, согласно парадоксу дней рождения (см. также атака «дней рождения»), вероятность того, что среди них найдется пара сообщений с одинаковыми хешами, больше 0,5. Атака требует большого объёма памяти для хранения текстов и эффективных методов сортировки.^[8]

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

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

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

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

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

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

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

В данной схеме блок сообщения $m_{i}$ и предыдущее значение хеш-функции $H_{i-1}$ поступают в качестве ключа и блока открытого текста соответственно на вход блочного шифра $E$ . Получившийся в результате шифрования блок закрытого текста суммируется (операция XOR) с результатом предыдущей итерации хеширования ( $H_{i-1}$ ) для получения следующего значения хеш-функции ( $H_{i}$ ).^[11]

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

H_{i}=E_{m_{i}}{(H_{i-1})}\oplus {H_{i-1}}.

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

Важным свойством конструкции Дэвиса — Мейера является то, что даже если базовый блок шифрования является полностью безопасным, можно вычислить неподвижные точки для построения: для любого $m$ можно найти значение $h$ такое что $E_{m}(h)\oplus h=h$ : просто нужно установить $h=E_{m}^{-1}(0)$ .^[12]

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

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

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

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

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

H_{i}=E_{g(H_{i-1})}(m_{i})\oplus m_{i}.

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

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

H_{i}=E_{g(H_{i-1})}(m_{i})\oplus H_{i-1}\oplus m_{i}.

Примечания

↑ Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Fifth Printing, August 2001.
↑ Брюс Шнайер, 2006, pp. 37—38.
↑ В.В.Ященко, 1999, p. 30.
↑ Авезова, 2015, p. 60.
↑ С.Баричев, Р.Серов, 2001, pp. 106—108.
↑ А.В. Антонов, 2012, pp. 106—107.
↑ С.В.Дубров, 2012, p. 65.
↑ С.В.Дубров, 2012, pp. 66—67.
↑ Авезова, 2015, pp. 60—61.
↑ Kelsey, Schneier, 2005, pp. 474—490.
↑ ¹ ² Авезова, 2015, p. 61.
↑ Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Fifth Printing, August 2001, p. 375.
↑ Winternitz, 1984, pp. 88—90.
↑ Авезова, 2015, pp. 61—62.
↑ Авезова, 2015, p. 62.

Литература

Книги

Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Chapter 9 // Hash Functions and Data Integrity. — 5-e изд. — August 2001. — С. 328.
Брюс Шнайер. Прикладная криптография. — 2-e изд. — 2006. — С. 37—38. — 610 с.
В.В.Ященко. Введение в криптографию. — 1999. — С. 30. — 271 с.
С.Баричев, Р.Серов. Основы современной криптографии. — Москва, 2001. — С. 106—108. — 122 с.
С.В.Дубров. Основы современной криптографии. — Новосибирск, 2012. — С. 65—67. — 260 с.
John Kelsey and Bruce Schneier. Second preimages on n-bit hash functions for much less than 2n work. — 2005. — С. 474–490.
R. Winternitz. A secure one-way hash function built from DES. — IEEE Press, 1984. — С. 88—90.

Научные статьи

Авезова Яна Эдуардовна. Современные подходы к построению хеш-функций на примере финалистов конкурса sha-3. — Москва, 2015.
А. В. Антонов. [www.hups.mil.gov.ua/periodic-app/article/1988/soivt_2012_2_23.pdf Развитие метода построения хеш-функции]. — Харьков, 2012.

[_6e8afacc39d6c03a-1] Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Fifth Printing, August 2001.

[_6d578b99171d74d9-2] Брюс Шнайер, 2006, pp. 37—38.

[_2c77b861826fe91b-3] В.В.Ященко, 1999, p. 30.

[_dc309fb952bfc57f-4] Авезова, 2015, p. 60.

[_8caf175febbdf06f-5] С.Баричев, Р.Серов, 2001, pp. 106—108.

[_3dd9d2c1e976019e-6] А.В. Антонов, 2012, pp. 106—107.

[_8c73eacd1c2ff1f2-7] С.В.Дубров, 2012, p. 65.

[_3b3f045831a094b4-8] С.В.Дубров, 2012, pp. 66—67.

[_d0d90239b58bd57c-9] Авезова, 2015, pp. 60—61.

[_6d478a8fa80364f8-10] Kelsey, Schneier, 2005, pp. 474—490.

[_dc309fb952bfc57e-11] ¹ ² Авезова, 2015, p. 61.

[_2021349612098005-12] Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Fifth Printing, August 2001, p. 375.

[_8b6e809063142a6a-13] Winternitz, 1984, pp. 88—90.

[_e56ae37417b9a384-14] Авезова, 2015, pp. 61—62.

[_dc309fb952bfc57d-15] Авезова, 2015, p. 62.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

@@ Строка 1: / Строка 1: @@
-В [[криптография|криптографии]], '''односторонняя функция сжатия''' — это такая функция, которая образует значение длиной n на выходе при задании двух входных значений длиной n.{{sfn|Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Fifth Printing|August 2001|page = 328}} [[Односторонняя функция|Одностороннее]] преобразование означает, что легко вычислить значение хэш-функции по прообразу, но трудно создать прообраз, значение [[Хеширование|хэш-функции]] которого равно заданной величине.{{sfn|Брюс Шнайер|2006|pp = 37—38}}{{sfn|В.В.Ященко|1999|p = 30}}
+'''Односторонняя функция сжатия''' в [[Криптография|криптографии]] — [[Функция (математика)|функция]], которая образует значение длиной <math>n</math> на выходе при задании двух входных значений длиной <math>n</math>{{sfn|Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Fifth Printing|August 2001|page = 328}}. [[Односторонняя функция|Одностороннее]] преобразование означает, что легко вычислить значение хеш-функции по прообразу, но трудно создать прообраз, значение [[Хеширование|хеш-функции]] которого равно заданной величине{{sfn|Брюс Шнайер|2006|pp = 37—38}}{{sfn|В.В.Ященко|1999|p = 30}}.
 [[Файл:One-way compression.svg|thumb|200px|right|Односторонняя функция сжатия]]
-Односторонняя функция сжатия используется, например, в [[Структура Меркла — Дамгарда|структуре Меркла — Дамгарда]] внутри [[Криптографическая хеш-функция|криптографических хэш-функций]].
+Односторонняя функция сжатия используется, например, в [[Структура Меркла — Дамгора|структуре Меркла — Дамгора]] внутри [[Криптографическая хеш-функция|криптографических хеш-функций]].
-Односторонние функции сжатия часто построены из [[Блочный шифр|блочных шифров]]. Для того, чтобы превратить любой стандартный блочный шифр в одностороннюю функцию сжатия существуют схемы '''Девиса-Мейера''', '''Матиса-Мейера-Осеаса''', '''Миагучи-Пренеля''' (функции сжатия одноблочной длины).{{sfn|Авезова|2015|p=60}} Эти методы подробно описаны ниже.
+Односторонние функции сжатия часто построены из [[Блочный шифр|блочных шифров]]. Для того, чтобы превратить любой стандартный блочный шифр в одностороннюю функцию сжатия существуют схемы Дэвиса — Мейера, Матиса — Мейера — Осеаса, [[Функция Миагути — Пренеля|Миагути — Пренеля]] (функции сжатия одноблочной длины){{sfn|Авезова|2015|p=60}}.
 == Функция сжатия ==
@@ Строка 21: / Строка 21: @@
 Функция сжатия в одну сторону должна обладать следующими свойствами:
-* Стойкость к поиску первого прообраза — отсутствие эффективного полиномиального алгоритма вычисления обратной функции, то есть нельзя восстановить текст <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>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>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>2^{n/2}</math> сообщений) и найти для них хеши. Тогда, согласно [[парадокс дней рождения|парадоксу дней рождения]] (см. также [[атака «дней рождения»]]), вероятность того, что среди них найдется пара сообщений с одинаковыми хешами, больше 0,5. Атака требует большого объёма памяти для хранения текстов и эффективных методов сортировки.{{sfn|С.В.Дубров|2012|pp = 66—67}}
-== Структура Меркла — Дамгарда ==
+== Структура Меркла — Дамгора ==
-{{Главная статья|Структура Меркла — Дамгарда}}
+{{Главная статья|Структура Меркла — Дамгора}}
-[[Файл:Merkle-Damgard hash big.svg|thumb|400px|right|Структура Меркла-Дамгарда, где IV — начальное значение свертки (фиксированный вектор), f — функция сжатия.]]
+[[Файл:Merkle-Damgard hash big.svg|thumb|400px|right|Структура Меркла — Дамгора, где IV — начальное значение свертки (фиксированный вектор), <math>f</math> — функция сжатия.]]
-Суть конструкции заключается в итеративном процессе последовательных преобразований, когда на вход каждой итерации поступает блок исходного текста и выход предыдущей итерации.{{sfn|Авезова|2015|pp = 60—61}}
+Суть конструкции заключается в итеративном процессе последовательных преобразований, когда на вход каждой итерации поступает блок исходного текста и выход предыдущей итерации{{sfn|Авезова|2015|pp = 60—61}}.
-Наиболее широко используются хэш-функции, основанные на этой конструкции в [[MD5]], [[SHA-1]] и [[SHA-2]].
+Наиболее широко используются хеш-функции, основанные на этой конструкции в [[MD5]], [[SHA-1]] и [[SHA-2]].
-Хэш-функция должна преобразовывать входное сообщение произвольной длины в выходное фиксированной длины. Это может быть достигнуто путём разбиения входного сообщения на ряд одинаковых по размеру блоков, и их последовательной обработки односторонней функцией сжатия. Функция сжатия может быть либо специально разработана для хеширования, либо представлять собой функцию блочного шифрования.
+Хеш-функция должна преобразовывать входное сообщение произвольной длины в выходное фиксированной длины. Это может быть достигнуто путём разбиения входного сообщения на ряд одинаковых по размеру блоков, и их последовательной обработки односторонней функцией сжатия. Функция сжатия может быть либо специально разработана для хеширования, либо представлять собой функцию блочного шифрования.
 [[Атака нахождения прообраза|Атака нахождения второго прообраза]] (учитывая сообщение <math>m_{1}</math>, злоумышленник находит ещё одно сообщение <math>m_{2}</math>, чтобы удовлетворить <math>H(m_{1})=H(m_{2})</math>) может быть выполнена в соответствии с Килси и Шнайером, для сообщения из 2<sup>k</sup> блоков может быть выполнена за время k × 2<sup>n/2+1</sup> + 2<sup>n-k+1</sup>. Важно отметить, если сообщения длинные, то сложность атаки находится между 2<sup>n/2</sup> и 2<sup>n</sup>, а когда длина сообщения становится меньше, сложность приближается к 2<sup>n</sup>.{{sfn|Kelsey, Schneier|2005|pp = 474—490}}
-Роль функции сжатия может осуществлять любой блочный шифр E. Данная идея легла в основу развития конструкции Меркла-Дамгарда в схемах Девиса-Мейера, Матиса-Мейера-Осеаса, Миагучи-Пренеля.{{sfn|Авезова|2015|p = 61}}
+Роль функции сжатия может осуществлять любой блочный шифр E. Данная идея легла в основу развития конструкции Меркла — Дамгора в схемах Дэвиса — Мейера, Матиса — Мейера — Осеаса, Миагути — Пренеля{{sfn|Авезова|2015|p = 61}}.
-== Структура Девиса-Мейера ==
+== Структура Дэвиса — Мейера ==
-[[Файл:Davies-Meyer hash.svg|thumb|230px|right|Схема Девиса-Мейера]]
+[[Файл:Davies-Meyer hash.svg|thumb|230px|right|Схема Дэвиса — Мейера]]
-В данной схеме блок сообщения <math>m_{i}</math> и предыдущее значение хэш-функции <math>H_{i-1}</math> поступают в качестве ключа и блока открытого текста соответственно на вход блочного шифра <math>E</math>. Получившийся в результате шифрования блок закрытого текста суммируется ([[Сложение по модулю 2|операция XOR]]) с результатом предыдущей итерации хеширования (<math>H_{i-1}</math>) для получения следующего значения хэш-функции (<math>H_{i}</math>).{{sfn|Авезова|2015|p = 61}}
+В данной схеме блок сообщения <math>m_{i}</math> и предыдущее значение хеш-функции <math>H_{i-1}</math> поступают в качестве ключа и блока [[Открытый текст|открытого текста]] соответственно на вход блочного шифра <math>E</math>. Получившийся в результате шифрования блок закрытого текста суммируется ([[Сложение по модулю 2|операция XOR]]) с результатом предыдущей итерации хеширования (<math>H_{i-1}</math>) для получения следующего значения хеш-функции (<math>H_{i}</math>).{{sfn|Авезова|2015|p = 61}}
-В [[Математические обозначения|математических обозначениях]] схему Девиса-Мейера можно записать как:
+В [[Математические обозначения|математических обозначениях]] схему Дэвиса — Мейера можно записать как:
 : <math>H_i = E_{m_i}{(H_{i-1})} \oplus {H_{i-1}}.</math>
-Если блочный шифр использует, например, 256-битный ключ, то каждый блок сообщений (<math>m_{i}</math>) представляет собой 256-битный фрагмент сообщения. Если же блочный шифр использует размер блока в 128 бит, то входные и выходные значения хэш-функции в каждом раунде составляют 128 бит.
+Если блочный шифр использует, например, 256-битный ключ, то каждый блок сообщений (<math>m_{i}</math>) представляет собой 256-битный фрагмент сообщения. Если же блочный шифр использует размер блока в 128 бит, то входные и выходные значения хеш-функции в каждом раунде составляют 128 бит.
-Важным свойством конструкции Девиса-Мейера является то, что даже если базовый блок шифрования является полностью безопасным, можно вычислить неподвижные точки для построения: для любого <math>m</math> можно найти значение <math>h</math> такое что <math>E_m(h) \oplus h = h</math> : просто нужно установить <math>h = E_m^{-1}(0)</math>.{{sfn|Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Fifth Printing|August 2001|p = 375}}
+Важным свойством конструкции Дэвиса — Мейера является то, что даже если базовый блок шифрования является полностью безопасным, можно вычислить неподвижные точки для построения: для любого <math>m</math> можно найти значение <math>h</math> такое что <math>E_m(h) \oplus h = h</math> : просто нужно установить <math>h = E_m^{-1}(0)</math>.{{sfn|Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Fifth Printing|August 2001|p = 375}}
-Безопасность структуры Девиса-Мейера была впервые доказана Р.Винтерницом.{{sfn|Winternitz|1984|pp = 88—90}}
+Безопасность структуры Дэвиса — Мейера была впервые доказана Винтерницом{{sfn|Winternitz|1984|pp = 88—90}}.
-== Структура Матиса-Мейера-Осеаса ==
+== Структура Матиса — Мейера — Осеаса ==
 [[Файл:Matyas-Meyer-Oseas hash.svg|thumb|230px|right|Схема Матиса-Мейера-Осеаса]]
-Это версия схемы Девиса-Мейера: блоки сообщения применяются как ключи [[Криптосистема|криптосистемы]]. Схема может быть использована, если блоки данных и ключ шифрования имеют один и тот же размер. Например, [[Advanced Encryption Standard|AES]] хорошо подходит для этой цели.
+Это версия схемы Девиса — Мейера: блоки сообщения применяются как ключи [[Криптосистема|криптосистемы]]. Схема может быть использована, если блоки данных и ключ шифрования имеют один и тот же размер. Например, [[Advanced Encryption Standard|AES]] хорошо подходит для этой цели.
 В данной конструкции блок сообщения <math>m_{i}</math> и предыдущее значение хеш-функции <math>H_{i-1}</math> поступают в качестве ключа и блока открытого текста соответственно на вход блочного шифра <math>E</math>. Но уже значение <math>H_{i-1}</math> подвергается предварительной обработке функцией <math>g</math> из-за возможных различий в размерах хеш-суммы и размере ключа шифра <math>E</math>. Эта функция реализует отображение n-битного значения хеш-
 функции в k-битный ключ шифра <math>E</math>. В результате применения операции шифрования, получается блок закрытого текста, который суммируется с соответствующим ему блоком открытого текста (<math>m_{i}</math>).{{sfn|Авезова|2015|pp = 61—62}}
-В математических обозначениях схему Матиса-Мейера-Осеаса можно записать как:
+В математических обозначениях схему Матиса — Мейера — Осеаса можно записать как:
 : <math>H_i = E_{g(H_{i-1})}(m_i)\oplus m_i.</math>
-== Структура Миагучи-Пренеля ==
+== Структура Миагути — Пренеля ==
-{{Основная статья|Односторонняя функция сжатия Миагучи-Пренеля}}
+{{Основная статья|Функция Миагути — Пренеля}}
 [[Файл:Miyaguchi-Preneel hash.svg|thumb|230px|right|Схема Миагучи-Пренеля]]
+Схема Миагути — Пренеля — расширенная версия схемы Матиса — Мейера — Осеаса. Отличие в том, что блок закрытого текста суммируется не только с соответствующим ему блоком открытого текста (<math>m_{i}</math>), но и с результатом предыдущей итерации хеширования (<math>H_{i-1}</math>). Чтобы сделать алгоритм более устойчивым к атаке, исходный текст, ключ шифра и зашифрованный текст складываются с помощью операции XOR и создают новый [[Хеш-сумма|дайджест]]. Эта схема используется в [[Whirlpool]] для создания хеш-функции. Результат суммирования <math>H_{i}</math> определяется уравнением{{sfn|Авезова|2015|p = 62}}:
-Схема Миагучи-Пренеля — расширенная версия схемы Матиса-Мейера-Осеаса. Отличие в том, что блок закрытого текста суммируется не только с соответствующим ему блоком открытого текста (<math>m_{i}</math>), но и с результатом предыдущей итерации хеширования (<math>H_{i-1}</math>). Чтобы сделать алгоритм более устойчивым к атаке, исходный текст, ключ шифра и зашифрованный текст складываются с помощью операции XOR и создают новый [[Хеш-сумма|дайджест]]. Эта схема используется в [[Whirlpool]] для создания хэш-функции. Результат суммирования <math>H_{i}</math> определяется уравнением{{sfn|Авезова|2015|p = 62}}:
 : <math>H_i = E_{g(H_{i-1})}(m_i)\oplus H_{i-1}\oplus m_i.</math>
-== См. также ==
-* [[Whirlpool (криптография)]]
-* [[Блочный шифр]]
 == Примечания ==
-{{примечания|32em}}
+{{примечания}}
 == Литература ==
@@ Строка 156: / Строка 150: @@
 * {{статья
   |автор          = Авезова Яна Эдуардовна
-  |заглавие       = СОВРЕМЕННЫЕ ПОДХОДЫ К ПОСТРОЕНИЮ ХЭШ-ФУНКЦИЙ НА ПРИМЕРЕ ФИНАЛИСТОВ КОНКУРСА SHA-3
+  |заглавие       = Современные подходы к построению хеш-функций на примере финалистов конкурса sha-3
   |ссылка         = http://cyberrus.com/wp-content/uploads/2015/09/vkb_11_8.pdf
   |место          = Москва
@@ Строка 163: / Строка 157: @@
 }}
 * {{статья
-  |автор          = А.В. Антонов
+  |автор          = А. В. Антонов
-  |заглавие       = РАЗВИТИЕ МЕТОДА ПОСТРОЕНИЯ ХЕШ-ФУНКЦИИ
+  |заглавие       = Развитие метода построения хеш-функции
   |ссылка         = www.hups.mil.gov.ua/periodic-app/article/1988/soivt_2012_2_23.pdf
   |место          = Харьков

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

Текущая версия от 00:36, 1 декабря 2021

Содержание

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

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

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

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

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

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

Примечания

Литература

Книги

Научные статьи

Навигация

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

Текущая версия от 00:36, 1 декабря 2021

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

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

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

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

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

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

Примечания

Литература

Книги

Научные статьи

Навигация

Поиск