Участник:Огнева Мария/Метод встречи посередине - История изменений

Sleo в 23:29, 13 ноября 2016

2016-11-13T23:29:23Z

← Предыдущая версия		Версия от 23:29, 13 ноября 2016
Строка 1:		Строка 1:
	{{Assignment}}		{{Assignment\|Sleo}}
	{{algorithm		{{algorithm
	\| name = Метод встречи посередине		\| name = Метод встречи посередине

Maria rojas в 12:10, 1 ноября 2016

2016-11-01T12:10:44Z

← Предыдущая версия		Версия от 12:10, 1 ноября 2016
Строка 1:		Строка 1:
			{{Assignment}}
	{{algorithm		{{algorithm
	\| name = Метод встречи посередине		\| name = Метод встречи посередине

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

2016-11-01T12:09:26Z

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

← Предыдущая версия		Версия от 12:09, 1 ноября 2016
Строка 77:		Строка 77:

	Примем за <math>n</math> количество всевозможных ключей <math>k= (k_1,k_2)</math>. Если предположить, что <math>\|K_1\|=\|K_2\|</math>, то <math>\|K_1\|=\|K_2\|=\sqrt n</math>.		Примем за <math>n</math> количество всевозможных ключей <math>k= (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\log n) </math>.

	== Информационный граф ==		== Информационный граф ==

Maria rojas: /* Входные и выходные данные алгоритма */

2016-11-01T12:08:20Z

Входные и выходные данные алгоритма

← Предыдущая версия		Версия от 12:08, 1 ноября 2016
Строка 96:		Строка 96:
	'''Входные данные''': открытый текст <math>p</math> и шифрованный текст <math>c</math>, имеющие одинаковую длину.		'''Входные данные''': открытый текст <math>p</math> и шифрованный текст <math>c</math>, имеющие одинаковую длину.

	Так как рассматриваемые шифры являются блочными, то равенство длины ~~текста~~ длине ключа не является обязательным, ~~текст может~~ быть длиннее. В такой ситуации тексты представляют собой последовательность блоков, а для шифрования/дешифрования берётся один блок текстов (от открытого и от шифрованного) для максимального ускорения операций.		Так как рассматриваемые шифры являются блочными, то равенство длины текстов длине ключа не является обязательным, тексты могут быть длиннее. В такой ситуации тексты представляют собой последовательность блоков, а для шифрования/дешифрования берётся один блок текстов (от открытого и от шифрованного) для максимального ускорения операций.

	Примем, что длина ключей <math>k_1</math> и <math>k_2</math> равна 64 битам. То есть длина текста равна 64 битам или кратна этому числу.		Примем, что длина ключей <math>k_1</math> и <math>k_2</math> равна 64 битам. То есть длина текста равна 64 битам или кратна этому числу.

Maria rojas: /* Входные и выходные данные алгоритма */

2016-11-01T12:07:20Z

Входные и выходные данные алгоритма

← Предыдущая версия		Версия от 12:07, 1 ноября 2016
Строка 102:		Строка 102:
	'''Выходные данные''': множество пар <math>(k_1,k_2)</math>, для которых нашлись совпадения.		'''Выходные данные''': множество пар <math>(k_1,k_2)</math>, для которых нашлись совпадения.

	Лишние пары могли получиться при шифровании/дешифровании одного ~~блока~~ текстов. Тогда для получения истинного ключа необходимо проверить все пары на блоках открытого и шифрованного текста, которые в алгоритме не использовались.		Лишние пары могли получиться при шифровании/дешифровании одного из блоков текстов. Тогда для получения истинного ключа необходимо проверить все пары на блоках открытого и шифрованного текста, которые в алгоритме не использовались.

	Длина искомого ключа: 128 бит.		Длина искомого ключа: 128 бит.

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

2016-11-01T12:04:34Z

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

← Предыдущая версия		Версия от 12:04, 1 ноября 2016
Строка 129:		Строка 129:
	== Существующие реализации алгоритма ==		== Существующие реализации алгоритма ==
	Реализаций метода в виде библиотек не обнаружено.		Реализаций метода в виде библиотек не обнаружено.
	В свободном доступе существуют коды для метода встречи ~~по середине~~ с использованием шифрования Blowfish и хэш-таблиц на [https://gist.github.com/dchest/1062437 C], а также с использованием шифрования 2DES на [https://github.com/le1ca/class-resources/blob/master/ddes/ddes.py питоне].		В свободном доступе существуют коды для метода встречи посередине с использованием шифрования Blowfish и хэш-таблиц на [https://gist.github.com/dchest/1062437 C], а также с использованием шифрования 2DES на [https://github.com/le1ca/class-resources/blob/master/ddes/ddes.py питоне].

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

Maria rojas: /* Свойства алгоритма */

2016-11-01T11:04:16Z

Свойства алгоритма

← Предыдущая версия		Версия от 11:04, 1 ноября 2016
Строка 109:		Строка 109:
	Соотношение последовательной и параллельной сложности для данного метода равно <math>O(\sqrt n\log n)</math>.		Соотношение последовательной и параллельной сложности для данного метода равно <math>O(\sqrt n\log n)</math>.

	При этом вычислительная мощность алгоритма, равная ~~отношение~~ числа операций к суммарному объему входных и выходных данных – <math>O(\sqrt{n})</math>.		При этом вычислительная мощность алгоритма, равная отношению числа операций к суммарному объему входных и выходных данных, составляет <math>O(\sqrt{n})</math>.

	Алгоритм полностью детерминирован при условии корректности данных.		Алгоритм полностью детерминирован при условии корректности данных.

	Дуги информационного графа, исходящие из вершин, соответствующих операциям шифрования/дешифрования образуют пучки мощности <math>\sqrt{n}</math>.		Дуги информационного графа, исходящие из вершин, соответствующих операциям шифрования/дешифрования, образуют пучки мощности <math>\sqrt{n}</math>.

	= Программная реализация алгоритма =		= Программная реализация алгоритма =

Maria rojas: /* Входные и выходные данные алгоритма */

2016-11-01T11:02:56Z

Входные и выходные данные алгоритма

← Предыдущая версия		Версия от 11:02, 1 ноября 2016
Строка 94:		Строка 94:

	== Входные и выходные данные алгоритма ==		== Входные и выходные данные алгоритма ==
	'''Входные данные''': открытый текст <math>p</math> и шифрованный текст <math>c</math>,имеющие одинаковую длину.		'''Входные данные''': открытый текст <math>p</math> и шифрованный текст <math>c</math>, имеющие одинаковую длину.

	Так как рассматриваемые шифры являются блочными, то равенство длины текста длине ключа не является обязательным, текст может быть длиннее. В такой ситуации тексты ~~являются последовательностью~~ блоков, а для шифрования/дешифрования берётся один блок текстов для максимального ускорения операций.		Так как рассматриваемые шифры являются блочными, то равенство длины текста длине ключа не является обязательным, текст может быть длиннее. В такой ситуации тексты представляют собой последовательность блоков, а для шифрования/дешифрования берётся один блок текстов (от открытого и от шифрованного) для максимального ускорения операций.

	Примем, что длина ключей <math>k_1</math> и <math>k_2</math> равна 64 битам. То есть длина текста равна 64 битам или кратна этому числу.		Примем, что длина ключей <math>k_1</math> и <math>k_2</math> равна 64 битам. То есть длина текста равна 64 битам или кратна этому числу.

Maria rojas: /* Ресурс параллелизма алгоритма */

2016-11-01T11:00:26Z

Ресурс параллелизма алгоритма

← Предыдущая версия		Версия от 11:00, 1 ноября 2016
Строка 87:		Строка 87:

	== Ресурс параллелизма алгоритма ==		== Ресурс параллелизма алгоритма ==
	Как видно из информационного графа, для реализации метода в параллельном варианте ~~потребуются~~ выполнение следующих двух ярусов ярусно-параллельной формы (ЯПФ):		Как видно из информационного графа, для реализации метода в параллельном варианте потребуется выполнение следующих двух ярусов ярусно-параллельной формы (ЯПФ):
	# <math>2* \sqrt{n}</math> шифрований/дешифрований		# <math>2* \sqrt{n}</math> шифрований/дешифрований
	# <math>n</math> сравнений		# <math>n</math> сравнений

Maria rojas: /* Информационный граф */

2016-11-01T10:59:47Z

Информационный граф

← Предыдущая версия		Версия от 10:59, 1 ноября 2016
Строка 82:		Строка 82:
	Опишем информационный граф алгоритма.		Опишем информационный граф алгоритма.

	На вход подаётся открытый и шифрованный тексты. После открытый текст шифруется (Enc) по всем ключам <math>k_1</math>, а дешифрованный дешифруется (Dec) по всем ключам <math>k_2</math>. Далее полученные тексты сравниваются между собой (Cmp) и все ключи, на которых они совпали, являются ~~выходом~~ алгоритма.		На вход подаётся открытый и шифрованный тексты. После открытый текст шифруется (Enc) по всем ключам <math>k_1</math>, а дешифрованный дешифруется (Dec) по всем ключам <math>k_2</math>. Далее полученные тексты сравниваются между собой (Cmp) и все ключи, на которых они совпали, являются выходами алгоритма.

	[[file:Graph MITM.jpg\|thumb\|center\|600px\|Рисунок 1. Граф алгоритма c отображением входных и выходных данных. Plaintext — открытый текст, ciphertext — шифрованный текст, Enc — операция шифрования, Dec — операция дешифрования, Cmp — операция сравнения, Key — полученный ключ]]		[[file:Graph MITM.jpg\|thumb\|center\|600px\|Рисунок 1. Граф алгоритма c отображением входных и выходных данных. Plaintext — открытый текст, ciphertext — шифрованный текст, Enc — операция шифрования, Dec — операция дешифрования, Cmp — операция сравнения, Key — полученный ключ]]