Дифференцильная атака - История изменений

Demiandr: /* Информационный граф алгоритма и блок-схема обработки одного текста */

2021-11-15T10:48:14Z

Информационный граф алгоритма и блок-схема обработки одного текста

← Предыдущая версия		Версия от 10:48, 15 ноября 2021
Строка 70:		Строка 70:
	=== Информационный граф алгоритма и блок-схема обработки одного текста ===		=== Информационный граф алгоритма и блок-схема обработки одного текста ===

	Рассмотрим [[глоссарий#Граф алгоритма\|информационный граф]] для обработки всех пар текстов. Как видно из графа, обработка каждой пары текстов происходит ~~параллельно~~, после чего значения всех счетчиков сохраняются в один список.		Рассмотрим [[глоссарий#Граф алгоритма\|информационный граф]] для обработки всех пар текстов. Как видно из графа, обработка каждой пары текстов происходит независимо, после чего значения всех счетчиков сохраняются в один список.
	[[Файл:Infograph.jpg\|обрамить\|центр\| Информационный граф]]		[[Файл:Infograph.jpg\|обрамить\|центр\| Информационный граф]]

	Действия, происходящие для каждой пары текстов в графе, можно подробно рассмотреть с использованием следующей блок-схемы. Как из видно схемы, для каждого текста <math>X</math> сначала генерируется второй текст при помощи добавления к нему разницы <math>Δfirst</math>, взятой из дифференциальной характеристики, после чего происходит шифрование на протяжение <math>R</math> раундов для обеих текстов из пары. После получения шифртекстов <math>Y_R</math> и <math>Y'_R</math> в результате последнего раунда, для всех возможных <math>b</math> бит последнего раундового ключа происходит частичное расшифрование, после чего в каждой паре тексты складываются и их разница <math>ΔY_{R-1}</math> сравнивается с искомой <math>Δlast</math> в характеристике. Если разницы текстов совпадают, данные значения бит раундового ключа заносятся в результат.		Действия, происходящие для каждой пары текстов в графе, можно подробно рассмотреть с использованием следующей блок-схемы. Как из видно схемы, для каждого текста <math>X</math> сначала генерируется второй текст при помощи добавления к нему разницы <math>Δfirst</math>, взятой из дифференциальной характеристики, после чего происходит шифрование на протяжение <math>R</math> раундов для обеих текстов из пары. После получения шифртекстов <math>Y_R</math> и <math>Y'_R</math> в результате последнего раунда, для всех возможных <math>b</math> бит последнего раундового ключа происходит частичное расшифрование, после чего в каждой паре тексты складываются и их разница <math>ΔY_{R-1}</math> сравнивается с искомой <math>Δlast</math> в характеристике. Если разницы текстов совпадают, данные значения бит раундового ключа заносятся в результат.
	[[Файл:Блок схема.jpg\|обрамить\|центр\| Блок схема обработки одного текста]]		[[Файл:Блок схема.jpg\|обрамить\|центр\| Блок-схема обработки одного текста]]
	Стоит отметить, что описанные выше преобразования происходят с каждым текстом, а число данных текстов зависит от вероятности найденной дифференциальной характеристики.		Стоит отметить, что описанные выше преобразования происходят с каждым текстом, а число данных текстов зависит от вероятности найденной дифференциальной характеристики.

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

Demiandr в 10:42, 15 ноября 2021

2021-11-15T10:42:22Z

← Предыдущая версия		Версия от 10:42, 15 ноября 2021
Строка 68:		Строка 68:
	Cчитая базовой операцией операцию шифрования текста на одном раунде с использование дифференциальной характеристики с вероятностью <math>p</math>, на нахождение <math>b</math> бит раундового ключа <math>R-1</math> раунда шифрования потребуется около <math>(2c/p)(R+2^b)</math> операций шифрования, где <math>c</math> - некоторая небольшая константа. Так как основным параметром является вероятность <math>p</math>, от которой зависит число пар текстов, данный алгоритм имеет линейную сложность.		Cчитая базовой операцией операцию шифрования текста на одном раунде с использование дифференциальной характеристики с вероятностью <math>p</math>, на нахождение <math>b</math> бит раундового ключа <math>R-1</math> раунда шифрования потребуется около <math>(2c/p)(R+2^b)</math> операций шифрования, где <math>c</math> - некоторая небольшая константа. Так как основным параметром является вероятность <math>p</math>, от которой зависит число пар текстов, данный алгоритм имеет линейную сложность.

	=== Информационный граф ===		=== Информационный граф алгоритма и блок-схема обработки одного текста ===

	Рассмотрим [[глоссарий#Граф алгоритма\|граф]] для обработки ~~одного текста как аналитически~~, ~~так и~~ в ~~виде рисунка~~. ~~Стоит отметить, что описанные ниже преобразования~~		Рассмотрим [[глоссарий#Граф алгоритма\|информационный граф]] для обработки всех пар текстов. Как видно из графа, обработка каждой пары текстов происходит параллельно, после чего значения всех счетчиков сохраняются в один список.
	~~происходят с каждым текстом~~, ~~а число данных~~ текстов зависит от вероятности найденной дифференциальной характеристики. Общий граф алгоритма дифференциальной атаки будет состоять из большого количества независимых графов, ~~типичных показанному ниже~~.		[[Файл:Infograph.jpg\|обрамить\|центр\| Информационный граф]]
	Как видно ~~из рисунка~~, для каждого текста <math>X</math> сначала генерируется второй текст при помощи добавления к нему разницы <math>Δfirst</math>, взятой из дифференциальной характеристики, после чего происходит шифрование на протяжение <math>R</math> раундов для обеих текстов из пары. После получения шифртекстов <math>Y_R</math> и <math>Y'_R</math> в результате последнего раунда, для всех возможных <math>b</math> бит последнего раундового ключа происходит частичное расшифрование, после чего в каждой паре тексты складываются и их разница <math>ΔY_{R-1}</math> сравнивается с искомой <math>Δlast</math> в характеристике. Если разницы текстов совпадают, данные значения бит раундового ключа заносятся в результат.
	[[Файл:~~Graphdifferential~~.jpg\|обрамить\|центр\|~~Алгоритм~~ обработки ~~только~~ одного текста]]		Действия, происходящие для каждой пары текстов в графе, можно подробно рассмотреть с использованием следующей блок-схемы. Как из видно схемы, для каждого текста <math>X</math> сначала генерируется второй текст при помощи добавления к нему разницы <math>Δfirst</math>, взятой из дифференциальной характеристики, после чего происходит шифрование на протяжение <math>R</math> раундов для обеих текстов из пары. После получения шифртекстов <math>Y_R</math> и <math>Y'_R</math> в результате последнего раунда, для всех возможных <math>b</math> бит последнего раундового ключа происходит частичное расшифрование, после чего в каждой паре тексты складываются и их разница <math>ΔY_{R-1}</math> сравнивается с искомой <math>Δlast</math> в характеристике. Если разницы текстов совпадают, данные значения бит раундового ключа заносятся в результат.
			[[Файл:Блок схема.jpg\|обрамить\|центр\| Блок схема обработки одного текста]]
			Стоит отметить, что описанные выше преобразования происходят с каждым текстом, а число данных текстов зависит от вероятности найденной дифференциальной характеристики.

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

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

2021-11-14T09:56:01Z

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

← Предыдущая версия		Версия от 09:56, 14 ноября 2021
Строка 73:		Строка 73:
	происходят с каждым текстом, а число данных текстов зависит от вероятности найденной дифференциальной характеристики. Общий граф алгоритма дифференциальной атаки будет состоять из большого количества независимых графов, типичных показанному ниже.		происходят с каждым текстом, а число данных текстов зависит от вероятности найденной дифференциальной характеристики. Общий граф алгоритма дифференциальной атаки будет состоять из большого количества независимых графов, типичных показанному ниже.
	Как видно из рисунка, для каждого текста <math>X</math> сначала генерируется второй текст при помощи добавления к нему разницы <math>Δfirst</math>, взятой из дифференциальной характеристики, после чего происходит шифрование на протяжение <math>R</math> раундов для обеих текстов из пары. После получения шифртекстов <math>Y_R</math> и <math>Y'_R</math> в результате последнего раунда, для всех возможных <math>b</math> бит последнего раундового ключа происходит частичное расшифрование, после чего в каждой паре тексты складываются и их разница <math>ΔY_{R-1}</math> сравнивается с искомой <math>Δlast</math> в характеристике. Если разницы текстов совпадают, данные значения бит раундового ключа заносятся в результат.		Как видно из рисунка, для каждого текста <math>X</math> сначала генерируется второй текст при помощи добавления к нему разницы <math>Δfirst</math>, взятой из дифференциальной характеристики, после чего происходит шифрование на протяжение <math>R</math> раундов для обеих текстов из пары. После получения шифртекстов <math>Y_R</math> и <math>Y'_R</math> в результате последнего раунда, для всех возможных <math>b</math> бит последнего раундового ключа происходит частичное расшифрование, после чего в каждой паре тексты складываются и их разница <math>ΔY_{R-1}</math> сравнивается с искомой <math>Δlast</math> в характеристике. Если разницы текстов совпадают, данные значения бит раундового ключа заносятся в результат.
	[[Файл:Graphdifferential.jpg\|обрамить\|центр\|~~Информационная схема работы алгоритма~~]]		[[Файл:Graphdifferential.jpg\|обрамить\|центр\|Алгоритм обработки только одного текста]]

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

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

2021-11-14T09:53:33Z

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

← Предыдущая версия		Версия от 09:53, 14 ноября 2021
Строка 71:		Строка 71:

	Рассмотрим [[глоссарий#Граф алгоритма\|граф]] для обработки одного текста как аналитически, так и в виде рисунка. Стоит отметить, что описанные ниже преобразования		Рассмотрим [[глоссарий#Граф алгоритма\|граф]] для обработки одного текста как аналитически, так и в виде рисунка. Стоит отметить, что описанные ниже преобразования
	происходят с каждым текстом, а число данных текстов зависит от вероятности найденной дифференциальной характеристики.		происходят с каждым текстом, а число данных текстов зависит от вероятности найденной дифференциальной характеристики. Общий граф алгоритма дифференциальной атаки будет состоять из большого количества независимых графов, типичных показанному ниже.
	Как видно из рисунка, для каждого текста <math>X</math> сначала генерируется второй текст при помощи добавления к нему разницы <math>Δfirst</math>, взятой из дифференциальной характеристики, после чего происходит шифрование на протяжение <math>R</math> раундов для обеих текстов из пары. После получения шифртекстов <math>Y_R</math> и <math>Y'_R</math> в результате последнего раунда, для всех возможных <math>b</math> бит последнего раундового ключа происходит частичное расшифрование, после чего в каждой паре тексты складываются и их разница <math>ΔY_{R-1}</math> сравнивается с искомой <math>Δlast</math> в характеристике. Если разницы текстов совпадают, данные значения бит раундового ключа заносятся в результат.		Как видно из рисунка, для каждого текста <math>X</math> сначала генерируется второй текст при помощи добавления к нему разницы <math>Δfirst</math>, взятой из дифференциальной характеристики, после чего происходит шифрование на протяжение <math>R</math> раундов для обеих текстов из пары. После получения шифртекстов <math>Y_R</math> и <math>Y'_R</math> в результате последнего раунда, для всех возможных <math>b</math> бит последнего раундового ключа происходит частичное расшифрование, после чего в каждой паре тексты складываются и их разница <math>ΔY_{R-1}</math> сравнивается с искомой <math>Δlast</math> в характеристике. Если разницы текстов совпадают, данные значения бит раундового ключа заносятся в результат.
	[[Файл:Graphdifferential.jpg\|обрамить\|центр\|Информационная схема работы алгоритма]]		[[Файл:Graphdifferential.jpg\|обрамить\|центр\|Информационная схема работы алгоритма]]

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

2021-11-14T09:15:32Z

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

← Предыдущая версия		Версия от 09:15, 14 ноября 2021
Строка 78:		Строка 78:

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

			Стоить отметить, что существуют другие ресурсы параллелизма, как в алгоритме атаки, так и в алгоритме шифрования, но их параллелизм не является эффективным. Так как в каждой паре существует два текста, каждый текст из пары можно шифровать и расшифровывать параллельно, однако так как число пар в блочном шифре Present может близиться к <math>2^{32}</math> и для каждой пары необходимо находить разницу текстов данной пары, более эффективным является обработка обеих текстов из пары одним процессом.
			Помимо этого, некоторые операции в алгоритме шифрования могут выполняться параллельно. Такими операциями являются операция побитового сложения текста с раундовым ключом и операция подстановки бит частей текста по 4 бита. Так как подобная параллельность обычно достигается при аппаратной реализации шифрования (где каждый бит текста течет по своему каналу), то при программной реализации более эффективным является совмещение преобразований в одно, путем хранения результата преобразований в одной большой таблице. Распараллеливание этих операция для каждого текста из всех обрабатываемых текстов принесет огромные накладные расходы на синхронизацию и обмен информацией между процессами.

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

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

2021-11-14T09:00:02Z

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

← Предыдущая версия		Версия от 09:00, 14 ноября 2021
Строка 70:		Строка 70:
	=== Информационный граф ===		=== Информационный граф ===

	Рассмотрим [[глоссарий#Граф алгоритма\|граф ~~алгоритма~~]] для обработки одного текста как аналитически, так и в виде рисунка.		Рассмотрим [[глоссарий#Граф алгоритма\|граф]] для обработки одного текста как аналитически, так и в виде рисунка. Стоит отметить, что описанные ниже преобразования
			происходят с каждым текстом, а число данных текстов зависит от вероятности найденной дифференциальной характеристики.
			Как видно из рисунка, для каждого текста <math>X</math> сначала генерируется второй текст при помощи добавления к нему разницы <math>Δfirst</math>, взятой из дифференциальной характеристики, после чего происходит шифрование на протяжение <math>R</math> раундов для обеих текстов из пары. После получения шифртекстов <math>Y_R</math> и <math>Y'_R</math> в результате последнего раунда, для всех возможных <math>b</math> бит последнего раундового ключа происходит частичное расшифрование, после чего в каждой паре тексты складываются и их разница <math>ΔY_{R-1}</math> сравнивается с искомой <math>Δlast</math> в характеристике. Если разницы текстов совпадают, данные значения бит раундового ключа заносятся в результат.
	[[Файл:Graphdifferential.jpg\|обрамить\|центр\|Информационная схема работы алгоритма]]		[[Файл:Graphdifferential.jpg\|обрамить\|центр\|Информационная схема работы алгоритма]]


	Как видно из рисунка, для каждого текста <math>X</math> сначала генерируется второй текст при помощи добавления к нему разницы <math>Δfirst</math>, взятой из дифференциальной характеристики, после чего происходит шифрование на протяжение <math>R</math> раундов для обеих текстов из пары. После получения шифртекстов <math>Y_R</math> и <math>Y'_R</math> в результате последнего раунда, для всех возможных <math>b</math> бит последнего раундового ключа происходит частичное расшифрование, после чего в каждой паре тексты складываются и их разница <math>ΔY_{R-1}</math> сравнивается с искомой <math>Δlast</math> в характеристике. Если разницы текстов совпадают, данные значения бит раундового ключа заносятся в результат.

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

Demiandr в 13:54, 13 ноября 2021

2021-11-13T13:54:56Z

← Предыдущая версия		Версия от 13:54, 13 ноября 2021
Строка 102:		Строка 102:
	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===
	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===
	Исследование проводилось на суперкомпьютере "Ломоносов-2".
	~~{\| class="wikitable"~~		Исследование проводилось на суперкомпьютере "Ломоносов-2". При компиляции использовался компилятор Openmpi/4.1.0-icc.
	\|-
	~~! Компилятор C++~~		{\| class="wikitable"
	\|-
	~~\|openmpi~~/4.1.0-icc
	~~\|-}~~

	В следующей таблице представлены времена работы алгоритма для различного числа процессов и обрабатываемых пар текстов.
	{\| class="wikitable"
	\|-		\|-
	\|		\|
Строка 163:		Строка 157:
	\|49,094		\|49,094
	\|24,553		\|24,553
	\|-}		\|-
			\|}
			В следующей таблице представлены времена работы алгоритма для различного числа процессов и обрабатываемых пар текстов.
			Графически результаты эксперимента представлены на рисунке ниже
			[[Файл:Time.png\|обрамить\|центр\|100x150px\|Масштабируемость алгоритма]]
	Алгоритм имеет сильную масштабируемость. Время выполнения алгоритма сокращается почти в 2 раза с увеличением числа обрабатываемых пар текстов в 2 раза.		Алгоритм имеет сильную масштабируемость. Время выполнения алгоритма сокращается почти в 2 раза с увеличением числа обрабатываемых пар текстов в 2 раза.

Demiandr: /* Масштабируемость алгоритма и его реализации */

2021-11-13T13:40:29Z

Масштабируемость алгоритма и его реализации

@@ Строка 102: / Строка 102: @@
 === Возможные способы и особенности параллельной реализации алгоритма ===
 === Масштабируемость алгоритма и его реализации ===
-==== Масштабируемость алгоритма ====
+Исследование проводилось на суперкомпьютере "Ломоносов-2".
-==== Масштабируемость реализации алгоритма ====
+{| class="wikitable"
 === Динамические характеристики и эффективность реализации алгоритма ===

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

2021-11-13T12:50:53Z

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

← Предыдущая версия		Версия от 12:50, 13 ноября 2021
Строка 108:		Строка 108:
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===
			На данный момент в Сети не было найдено существующих реализаций параллельного алгоритма дифференциальной атаки. Подразумевается, что такие реализации существуют, но не находятся в открытом доступе.

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

Demiandr: /* Литература */

2021-11-13T12:46:39Z

Литература

← Предыдущая версия		Версия от 12:46, 13 ноября 2021
Строка 111:		Строка 111:
	== Литература ==		== Литература ==
	<references />		<references />
			M. Heys "A tutorial on linear and differential cryptanalysis" [https://ioactive.com/wp-content/uploads/2015/07/ldc_tutorial.pdf].

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