Метод встречи посередине - История изменений

ASA в 13:24, 21 июля 2022

2022-07-21T13:24:55Z

← Предыдущая версия		Версия от 13:24, 21 июля 2022
Строка 134:		Строка 134:

	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===

	~~=== Локальность данных и вычислений ===~~

	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===

	=== ~~Масштабируемость алгоритма и его реализации~~ ===		=== Результаты прогонов ===
	Исследование масштабируемости реализации алгоритма проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета]. Изменяемые параметры запуска:
	* Размер ключа – от 8 до 20 бит с шагом 1
	* Число ядер – от 1 до 8 (значения являются степенью числа 2)
	Ниже представлен график зависимости [[Глоссарий#Производительность\|производительности]] от числа ядер и размера ключа (размер задачи – экспоненциальная функция от размера ключа). Для измерения производительности в качестве базовой операции используется операция опробования ключа и время в секундах. Количество арифметических операций, содержащихся в операции опробования, может быть разным в зависимости от используемого алгоритма шифрования.
	~~[[File:Масштабируемость.jpg\|thumb\|center\|900px\|Рисунок 2. Масштабируемость реализации алгоритма]]~~

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

	~~[https://github.com/AlBatarina/Super2016/blob/master/meet_in_the_middle/meet.c Исследованная параллельная реализация на языке C]~~

	~~=== Динамические характеристики и эффективность реализации алгоритма ===~~

	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===

	~~=== Существующие реализации алгоритма ===~~

	Одна из реализаций атаки "встреча посередине" с использованием хэш-таблицы представлена в свободном доступе по ссылке [https://gist.github.com/dchest/1062437 github]

	В свободном доступе существуют коды для метода "встречи посередине" с использованием шифрования Blowfish и хэш-таблиц на [https://gist.github.com/dchest/1062437 C], а также с использованием шифрования 2DES на [https://github.com/le1ca/class-resources/blob/master/ddes/ddes.py питоне].

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

	<references \>		<references />

	[[Категория:Статьи в работе]]		[[Категория:Статьи в работе]]

	[[en:Meet-in-the-middle attack]]		[[en:Meet-in-the-middle attack]]

ASA в 14:30, 14 марта 2018

2018-03-14T14:30:44Z

← Предыдущая версия		Версия от 14:30, 14 марта 2018
Строка 163:		Строка 163:

	<references \>		<references \>

			[[Категория:Статьи в работе]]

			[[en:Meet-in-the-middle attack]]

Konshin: /* Общее описание алгоритма */

2018-01-16T08:33:19Z

Общее описание алгоритма

← Предыдущая версия		Версия от 08:33, 16 января 2018
Строка 14:		Строка 14:

	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===
	Криптоанализом назвают науку восстановления (дешифрования) открытого (нешифрованного) текста без доступа к ключу. Попытка криптоанализа называется атакой.		Криптоанализом назвают науку восстановления (дешифрования) открытого (нешифрованного) текста без доступа к ключу. Попытка криптоанализа называется "атакой".

	Метод "Встреча посередине" криптоанализа блочных шифров был впервые предложен в 1977 году Уитфилдом Диффи и Мартином Хеллманом <ref>Diffie Whitfield, Hellman Martin E. ''Exhaustive Cryptanalysis of the NBS Data Encryption Standard.'' - Journal Computer vol.10 pp.74–84 - June 1977</ref>. Встреча посередине используется для ускорения перебора ключей шифра за счёт увеличения требуемой памяти. Метод применим в случае каскадного построения сложного шифра из нескольких простых, другими словами, в случае последовательного применения шифрующих преобразований на разных ключах к блокам открытого текста.		Метод "Встреча посередине" криптоанализа блочных шифров был впервые предложен в 1977 году Уитфилдом Диффи и Мартином Хеллманом <ref>Diffie Whitfield, Hellman Martin E. ''Exhaustive Cryptanalysis of the NBS Data Encryption Standard.'' - Journal Computer vol.10 pp.74–84 - June 1977</ref>. Встреча посередине используется для ускорения перебора ключей шифра за счёт увеличения требуемой памяти. Метод применим в случае каскадного построения сложного шифра из нескольких простых, другими словами, в случае последовательного применения шифрующих преобразований на разных ключах к блокам открытого текста.

Konshin: /* Общее описание алгоритма */

2018-01-15T17:55:56Z

Общее описание алгоритма

← Предыдущая версия		Версия от 17:55, 15 января 2018
Строка 16:		Строка 16:
	Криптоанализом назвают науку восстановления (дешифрования) открытого (нешифрованного) текста без доступа к ключу. Попытка криптоанализа называется атакой.		Криптоанализом назвают науку восстановления (дешифрования) открытого (нешифрованного) текста без доступа к ключу. Попытка криптоанализа называется атакой.

	Метод "Встреча посередине" криптоанализа блочных шифров был впервые предложен в 1977 году Уитфилдом Диффи и Мартином Хеллманом <ref>~~(June 1977) «Exhaustive~~ Cryptanalysis of the NBS Data Encryption ~~Standard»~~. Computer ~~10 (6): 74–84~~. ~~DOI:~~10.~~1109/C~~-M.1977~~.217750~~</ref>. Встреча посередине используется для ускорения перебора ключей шифра за счёт увеличения требуемой памяти. Метод применим в случае каскадного построения сложного шифра из нескольких простых, другими словами, в случае последовательного применения шифрующих преобразований на разных ключах к блокам открытого текста.		Метод "Встреча посередине" криптоанализа блочных шифров был впервые предложен в 1977 году Уитфилдом Диффи и Мартином Хеллманом <ref>Diffie Whitfield, Hellman Martin E. ''Exhaustive Cryptanalysis of the NBS Data Encryption Standard.'' - Journal Computer vol.10 pp.74–84 - June 1977</ref>. Встреча посередине используется для ускорения перебора ключей шифра за счёт увеличения требуемой памяти. Метод применим в случае каскадного построения сложного шифра из нескольких простых, другими словами, в случае последовательного применения шифрующих преобразований на разных ключах к блокам открытого текста.

	В качестве примера шифра, поддающегося атаке "встреча посередине" можно привести криптоалгоритм 2DES, являющийся модификацией шифра DES. В 2DES открытый текст шифруется дважды алгоритмом DES на двух разных 56-битных ключах. Однако из-за атаки "встреча посередине" сложность перебора двойного ключа (112 бит) шифра 2DES составляет <math>2^{57}</math> вместо ожидаемых <math>2^{112}</math>.		В качестве примера шифра, поддающегося атаке "встреча посередине" можно привести криптоалгоритм 2DES, являющийся модификацией шифра DES. В 2DES открытый текст шифруется дважды алгоритмом DES на двух разных 56-битных ключах. Однако из-за атаки "встреча посередине" сложность перебора двойного ключа (112 бит) шифра 2DES составляет <math>2^{57}</math> вместо ожидаемых <math>2^{112}</math>.

Konshin: /* Общее описание алгоритма */

2018-01-15T17:48:42Z

Общее описание алгоритма

← Предыдущая версия		Версия от 17:48, 15 января 2018
Строка 14:		Строка 14:

	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===
			Криптоанализом назвают науку восстановления (дешифрования) открытого (нешифрованного) текста без доступа к ключу. Попытка криптоанализа называется атакой.

	Метод "Встреча посередине" криптоанализа блочных шифров был впервые предложен в 1977 году Уитфилдом Диффи и Мартином Хеллманом <ref>(June 1977) «Exhaustive Cryptanalysis of the NBS Data Encryption Standard». Computer 10 (6): 74–84. DOI:10.1109/C-M.1977.217750</ref>. Встреча посередине используется для ускорения перебора ключей шифра за счёт увеличения требуемой памяти. Метод применим в случае каскадного построения сложного шифра из нескольких простых, другими словами, в случае последовательного применения шифрующих преобразований на разных ключах к блокам открытого текста.		Метод "Встреча посередине" криптоанализа блочных шифров был впервые предложен в 1977 году Уитфилдом Диффи и Мартином Хеллманом <ref>(June 1977) «Exhaustive Cryptanalysis of the NBS Data Encryption Standard». Computer 10 (6): 74–84. DOI:10.1109/C-M.1977.217750</ref>. Встреча посередине используется для ускорения перебора ключей шифра за счёт увеличения требуемой памяти. Метод применим в случае каскадного построения сложного шифра из нескольких простых, другими словами, в случае последовательного применения шифрующих преобразований на разных ключах к блокам открытого текста.

Konshin: /* Существующие реализации алгоритма */

2018-01-15T17:43:36Z

Существующие реализации алгоритма

← Предыдущая версия		Версия от 17:43, 15 января 2018
Строка 155:		Строка 155:

	Одна из реализаций атаки "встреча посередине" с использованием хэш-таблицы представлена в свободном доступе по ссылке [https://gist.github.com/dchest/1062437 github]		Одна из реализаций атаки "встреча посередине" с использованием хэш-таблицы представлена в свободном доступе по ссылке [https://gist.github.com/dchest/1062437 github]

			В свободном доступе существуют коды для метода "встречи посередине" с использованием шифрования Blowfish и хэш-таблиц на [https://gist.github.com/dchest/1062437 C], а также с использованием шифрования 2DES на [https://github.com/le1ca/class-resources/blob/master/ddes/ddes.py питоне].

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

	<references \>		<references \>

Konshin: /* Последовательная сложность алгоритма */

2018-01-15T17:34:23Z

Последовательная сложность алгоритма

← Предыдущая версия		Версия от 17:34, 15 января 2018
Строка 94:		Строка 94:
	3. C генерацией одной (достаточно большой) хэш-таблицы — <math>O(\|K_1\|) + O(\|K_2\|)=O(\|K_1\|+\|K_2\|)</math>		3. C генерацией одной (достаточно большой) хэш-таблицы — <math>O(\|K_1\|) + O(\|K_2\|)=O(\|K_1\|+\|K_2\|)</math>

	Пусть n - количество всевозможных пар <math>k_1,k_2</math> и пусть <math>\|K_1\|=\|K_2\|</math>. В этом случае <math>\|K_1\|=\|K_2\|=\sqrt n</math>.		Пусть <math>n</math> - количество всевозможных пар <math>k_1,k_2</math> и пусть <math>\|K_1\|=\|K_2\|</math>. В этом случае <math>\|K_1\|=\|K_2\|=\sqrt n</math>.

	Тогда сложность алгоритма в первых двух пунктах составляет <math>O(\sqrt n\log(n))</math>, в третьем — <math>O(\sqrt n)</math>.		Тогда сложность алгоритма в первых двух пунктах составляет <math>O(\sqrt n\log(n))</math>, в третьем — <math>O(\sqrt n)</math>.

Konshin: /* Последовательная сложность алгоритма */

2018-01-15T17:33:55Z

Последовательная сложность алгоритма

← Предыдущая версия		Версия от 17:33, 15 января 2018
Строка 86:		Строка 86:
	4. Сложность поиска в достаточно большой хэш-таблице составит <math>O(1)</math> для каждого поиска		4. Сложность поиска в достаточно большой хэш-таблице составит <math>O(1)</math> для каждого поиска

	Итого асимптотическая сложность алгоритма:		Итого: асимптотическая сложность алгоритма:

	1. С генерацией двух таблиц — <math>O(\|K_1\|+\|K_2\|) + O((\|K_1\|+\|K_2\|)\log(\|K_1\|+\|K_2\|)) + O(\|K_1\|+\|K_2\|)=O((\|K_1\|+\|K_2\|)\log(\|K_1\|+\|K_2\|))</math>		1. С генерацией двух таблиц — <math>O(\|K_1\|+\|K_2\|) + O((\|K_1\|+\|K_2\|)\log(\|K_1\|+\|K_2\|)) + O(\|K_1\|+\|K_2\|)=O((\|K_1\|+\|K_2\|)\log(\|K_1\|+\|K_2\|))</math>

Konshin: /* Последовательная сложность алгоритма */

2018-01-15T17:33:15Z

Последовательная сложность алгоритма

← Предыдущая версия		Версия от 17:33, 15 января 2018
Строка 78:		Строка 78:
	Всюду далее считаем, что алгоритм не прекращает работу при нахождении первого совпадения, а ищет все совпадения.		Всюду далее считаем, что алгоритм не прекращает работу при нахождении первого совпадения, а ищет все совпадения.

	1. Сложность вычисления таблиц значений <math>z_i,z_j^'</math> составит <math>O(\|K_1\|+\|K_2\|)</math> операций опробования		1. Сложность вычисления таблиц значений <math>z_i,z_j^′</math> составит <math>O(\|K_1\|+\|K_2\|)</math> операций опробования

	2. Объединение таблиц и их сортировка будет иметь сложность <math>O((\|K_1\|+\|K_2\|)\log(\|K_1\|+\|K_2\|))</math> (например, при сортировке слиянием).		2. Объединение таблиц и их сортировка будет иметь сложность <math>O((\|K_1\|+\|K_2\|)\log(\|K_1\|+\|K_2\|))</math> (например, при сортировке слиянием).

Konshin: /* Схема реализации последовательного алгоритма */

2018-01-15T17:32:56Z

Схема реализации последовательного алгоритма

← Предыдущая версия		Версия от 17:32, 15 января 2018
Строка 73:		Строка 73:
	2. В случае записи значений в порядке вычисления отсортировать массив		2. В случае записи значений в порядке вычисления отсортировать массив

	3. Опробовать ключи <math>k_2^j</math>, выполняя поиск совпадения с таблицей значений <math>z_j^'</math>. Для нахождения совпадения использовать поиск по хэш-таблице (если она есть) или бинарный поиск		3. Опробовать ключи <math>k_2^j</math>, выполняя поиск совпадения с таблицей значений <math>z_j^′</math>. Для нахождения совпадения использовать поиск по хэш-таблице (если она есть) или бинарный поиск

	=== Последовательная сложность алгоритма ===		=== Последовательная сложность алгоритма ===