Алговики - Вклад [ru]

Дифференцильная атака

2021-11-15T10:48:14Z

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

{{level-a}}

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

=== Общее описание алгоритма ===
Дифференциальный криптоанализ — метод криптоанализа симметричных блочных шифров (и других криптографических примитивов, в частности, хеш-функций и поточных шифров).
Дифференциальный криптоанализ основан на изучении преобразования разностей между шифруемыми значениями на различных раундах шифрования. В качестве разности, как правило, применяется операция побитового суммирования по модулю 2, хотя существуют атаки и с вычислением разности по модулю [math] 2^{32}[/math]. Является статистической атакой. Количество раундов современных шифров (AES, Camellia и др.) рассчитывалось с учётом обеспечения стойкости, в том числе и к дифференциальному криптоанализу.
Все существующие блочные алгоритмы шифрования являются итеративными алгоритмами, то есть при шифровании информация подвергается большому числу одних и тех же подряд идущих преобразований (раундов). В начале алгоритма шифрования из одного длинного секретного ключа при помощи алгоритма генерации раундовых ключей создаются мини-ключи, которые применяются на каждом раунде шифрования. Дифференциальный криптоанализ направлен на нахождение таких раундовых ключей, для последующего определения по ним основного секретного ключа криптосистемы, причем первым определяемым раундовым ключом является ключ последнего раунда шифрования.

=== Математическое описание алгоритма ===
Так как раундовые ключи однозначно получаются из основного секретного ключа, задачей криптоаналитика является нахождение раундовых ключей, после чего восстанавливается секретный ключ. В данном виде атак на блочные алгоритмы шифрования находятся статистические зависимости между двумя текстами с определенной входной разницей <math>Δfirst</math>, после чего определяется наиболее вероятная разница выходных шифртекстов <math>Δlast</math> на предпоследнем раунде <math>R-1</math>. Такая зависимость между входной и выходной разницами пар текстов называется дифференциальной характеристикой. Способы определения дифференциальных характеристик чрезвычайно сложны и разнятся от алгоритма к алгоритму, поэтому опускаются в данной статье. После нахождения дифференциальной характеристики производится атака на блочный алгоритм шифрования.
Пусть <math>p</math> - вероятность дифференциальной характеристики <math>Δfirst→Δlast</math>, воздействущей на <math>b</math> бит результирующего шифртекста. Тогда атака проводится следующим образом:
# Берется небольшая положительная константа <math>c</math> (обычно равная 2 или 3). Генерируется <math>c/p</math> пар текстов с входной разницей <math>Δfirst</math>;
# Все данные пары текстов пропускаются через <math>R</math> раундов алгоритма шифрования, после чего получаются соответствующие шифртексты <math>Y_{R}</math>;
# Для всех возможных значений <math>b</math> бит последнего раундового ключа заводится свой счетчик. Далее для каждой сгенерированной пары шифртекстов <math>Y_{R}</math> данные тексты расшифровываются на всех возможных значениях <math>b</math> бит раундового ключа, в результате чего получаются значения <math>Y_{R-1}</math>;
# Для каждой пары текстов путем их сложения находится своя разница <math>ΔY_{R-1}</math>. Далее значение <math>ΔY_{R-1}</math> сравнивается c <math>Δlast</math>. Если они совпадают, счетчик для данного <math>b</math> бит ключа увеличивается на 1.
После такого полного перебора раундовым ключом является то значение <math>b</math> бит, которое имеет наибольший счетчик. Определив таким образом биты раундового ключа можно найти значение секретного ключа и взломать алгоритм шифрования.

=== Вычислительное ядро алгоритма ===

Вычислительное ядром алгоритма является генерация и шифрование большого числа входных пар текстов алгоритма шифрования с заданной разницей <math>ΔX</math>, получая в итоге пары шифртекстов. После генерации текстов для каждой комбинации пары шифртекстов и возможного значения бит раундового ключа последнего раунда найденной характеристики происходит частичное расшифрование шифртекстов. Если разница между парами текстов <math>ΔY_{R-1}</math> на <math>{R-1}</math> раунде совпадает с искомой разницей <math>ΔU</math>, счетчик данного значения бит раундового ключа последнего раунда инкрементируется. Результатом является значение раундового ключа с наибольшим счетчиком.

=== Макроструктура алгоритма ===

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

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

В данном пункте приведены
<source lang="c++">
double p = 0.000001;//вероятность найденной характеристики
int c = 2;//константа
int R = 12;//число раундов шифра
int b = 4;//число бит раундового ключа, которые можно определить найденной характеристикой
__uint64 deltafirst=(2^34);// найденная характеристика (разница между парой текстов)
__uint64 deltalast=1;(найденная разница между текстами на предпоследнем раунде_
__uint64 firsttext;//первый текст из пары
__uint64 secondtext;//второй текст из пары
int result[pow(2,b)]={};//массив возможных значений бит раундового ключа
for (__uint64 i=0; i<(c/p);i++)
{
firsttext=i;//генерация первого текста пары
secondtext=i^deltafirst;//генерация второго текста пары
for (int j=0; j<R;j++)
{
firsttext = cipher(firsttext);
secondtext = cipher(secondtext);
}
for (int k=0; k< pow(2,b);k++)
{
firsttext = decipher(firsttext,k)
secondtext = decipher(secondtext,k)
if (deltalast == firsttext ^ secondtext)
{
result[k]++
}
}
}
int max=0
for (int k=0; k< pow(2,b);k++)
{
if (result[k] > max) max=result[k]
}
</source>
=== Последовательная сложность алгоритма ===

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> в характеристике. Если разницы текстов совпадают, данные значения бит раундового ключа заносятся в результат.
[[Файл:Блок схема.jpg|обрамить|центр| Блок-схема обработки одного текста]]
Стоит отметить, что описанные выше преобразования происходят с каждым текстом, а число данных текстов зависит от вероятности найденной дифференциальной характеристики.

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

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

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

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

'''Входные данные''': алгоритм шифрования, константа <math>c</math>, вероятность характеристики <math>p</math>, число бит раундового ключа <math>b</math>, число раундов шифрования <math>R</math>, входная разница между парами текстов <math>deltafirst</math>, выходная разница между парами текстов <math>deltalast</math>

'''Объём входных данных''': Объем входных не изменяется, изменяются только сами входные данные.

'''Выходные данные''': Биты раундового ключа последнего раунда.

'''Объём выходных данных''': <math>b</math>.

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

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

=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===

Исследование проводилось на суперкомпьютере "Ломоносов-2". При компиляции использовался компилятор Openmpi/4.1.0-icc.

{| class="wikitable"
|-
|
! colspan="6"|Число процессов
|-
! Число генерируемых пар текстов
|1
|2
|4
|8
|16
|32
|-
|<math>10^7</math>
|42,1364
|21,1016
|11,6119
|6,1043
|3,06838
|1,5346
|-
|<math>2*10^7</math>
|84,4536
|45,0574
|23,3564
|12,2063
|6,13689
|3,0685
|-
|<math>4*10^7</math>
|169,6
|85,1138
|46,0756
|24,4103
|12,276
|6,1380
|-
|<math>8*10^7</math>
|339,081
|170,628
|95,0417
|48,8382
|24,5472
|12,275
|-
|<math>16*10^7</math>
|683,5931
|345,1143
|175,181
|97,6816
|49,094
|24,553
|-
|}
В следующей таблице представлены времена работы алгоритма для различного числа процессов и обрабатываемых пар текстов.
Графически результаты эксперимента представлены на рисунке ниже
[[Файл:Time.png|обрамить|центр|100x150px|Масштабируемость алгоритма]]
Алгоритм имеет сильную масштабируемость. Время выполнения алгоритма сокращается почти в 2 раза с увеличением числа обрабатываемых пар текстов в 2 раза.

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
На данный момент в Сети не было найдено существующих реализаций параллельного алгоритма дифференциальной атаки. Подразумевается, что такие реализации существуют, но не находятся в открытом доступе.

== Литература ==
<references />
M. Heys "A tutorial on linear and differential cryptanalysis" [https://ioactive.com/wp-content/uploads/2015/07/ldc_tutorial.pdf].

[[Категория:Статьи в работе]]
[[Категория:Матрично-векторные операции]]

[[En:Dense matrix-vector multiplication]]

Дифференцильная атака

2021-11-15T10:42:22Z

Demiandr:

{{level-a}}

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

=== Общее описание алгоритма ===
Дифференциальный криптоанализ — метод криптоанализа симметричных блочных шифров (и других криптографических примитивов, в частности, хеш-функций и поточных шифров).
Дифференциальный криптоанализ основан на изучении преобразования разностей между шифруемыми значениями на различных раундах шифрования. В качестве разности, как правило, применяется операция побитового суммирования по модулю 2, хотя существуют атаки и с вычислением разности по модулю [math] 2^{32}[/math]. Является статистической атакой. Количество раундов современных шифров (AES, Camellia и др.) рассчитывалось с учётом обеспечения стойкости, в том числе и к дифференциальному криптоанализу.
Все существующие блочные алгоритмы шифрования являются итеративными алгоритмами, то есть при шифровании информация подвергается большому числу одних и тех же подряд идущих преобразований (раундов). В начале алгоритма шифрования из одного длинного секретного ключа при помощи алгоритма генерации раундовых ключей создаются мини-ключи, которые применяются на каждом раунде шифрования. Дифференциальный криптоанализ направлен на нахождение таких раундовых ключей, для последующего определения по ним основного секретного ключа криптосистемы, причем первым определяемым раундовым ключом является ключ последнего раунда шифрования.

=== Математическое описание алгоритма ===
Так как раундовые ключи однозначно получаются из основного секретного ключа, задачей криптоаналитика является нахождение раундовых ключей, после чего восстанавливается секретный ключ. В данном виде атак на блочные алгоритмы шифрования находятся статистические зависимости между двумя текстами с определенной входной разницей <math>Δfirst</math>, после чего определяется наиболее вероятная разница выходных шифртекстов <math>Δlast</math> на предпоследнем раунде <math>R-1</math>. Такая зависимость между входной и выходной разницами пар текстов называется дифференциальной характеристикой. Способы определения дифференциальных характеристик чрезвычайно сложны и разнятся от алгоритма к алгоритму, поэтому опускаются в данной статье. После нахождения дифференциальной характеристики производится атака на блочный алгоритм шифрования.
Пусть <math>p</math> - вероятность дифференциальной характеристики <math>Δfirst→Δlast</math>, воздействущей на <math>b</math> бит результирующего шифртекста. Тогда атака проводится следующим образом:
# Берется небольшая положительная константа <math>c</math> (обычно равная 2 или 3). Генерируется <math>c/p</math> пар текстов с входной разницей <math>Δfirst</math>;
# Все данные пары текстов пропускаются через <math>R</math> раундов алгоритма шифрования, после чего получаются соответствующие шифртексты <math>Y_{R}</math>;
# Для всех возможных значений <math>b</math> бит последнего раундового ключа заводится свой счетчик. Далее для каждой сгенерированной пары шифртекстов <math>Y_{R}</math> данные тексты расшифровываются на всех возможных значениях <math>b</math> бит раундового ключа, в результате чего получаются значения <math>Y_{R-1}</math>;
# Для каждой пары текстов путем их сложения находится своя разница <math>ΔY_{R-1}</math>. Далее значение <math>ΔY_{R-1}</math> сравнивается c <math>Δlast</math>. Если они совпадают, счетчик для данного <math>b</math> бит ключа увеличивается на 1.
После такого полного перебора раундовым ключом является то значение <math>b</math> бит, которое имеет наибольший счетчик. Определив таким образом биты раундового ключа можно найти значение секретного ключа и взломать алгоритм шифрования.

=== Вычислительное ядро алгоритма ===

Вычислительное ядром алгоритма является генерация и шифрование большого числа входных пар текстов алгоритма шифрования с заданной разницей <math>ΔX</math>, получая в итоге пары шифртекстов. После генерации текстов для каждой комбинации пары шифртекстов и возможного значения бит раундового ключа последнего раунда найденной характеристики происходит частичное расшифрование шифртекстов. Если разница между парами текстов <math>ΔY_{R-1}</math> на <math>{R-1}</math> раунде совпадает с искомой разницей <math>ΔU</math>, счетчик данного значения бит раундового ключа последнего раунда инкрементируется. Результатом является значение раундового ключа с наибольшим счетчиком.

=== Макроструктура алгоритма ===

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

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

В данном пункте приведены
<source lang="c++">
double p = 0.000001;//вероятность найденной характеристики
int c = 2;//константа
int R = 12;//число раундов шифра
int b = 4;//число бит раундового ключа, которые можно определить найденной характеристикой
__uint64 deltafirst=(2^34);// найденная характеристика (разница между парой текстов)
__uint64 deltalast=1;(найденная разница между текстами на предпоследнем раунде_
__uint64 firsttext;//первый текст из пары
__uint64 secondtext;//второй текст из пары
int result[pow(2,b)]={};//массив возможных значений бит раундового ключа
for (__uint64 i=0; i<(c/p);i++)
{
firsttext=i;//генерация первого текста пары
secondtext=i^deltafirst;//генерация второго текста пары
for (int j=0; j<R;j++)
{
firsttext = cipher(firsttext);
secondtext = cipher(secondtext);
}
for (int k=0; k< pow(2,b);k++)
{
firsttext = decipher(firsttext,k)
secondtext = decipher(secondtext,k)
if (deltalast == firsttext ^ secondtext)
{
result[k]++
}
}
}
int max=0
for (int k=0; k< pow(2,b);k++)
{
if (result[k] > max) max=result[k]
}
</source>
=== Последовательная сложность алгоритма ===

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> в характеристике. Если разницы текстов совпадают, данные значения бит раундового ключа заносятся в результат.
[[Файл:Блок схема.jpg|обрамить|центр| Блок схема обработки одного текста]]
Стоит отметить, что описанные выше преобразования происходят с каждым текстом, а число данных текстов зависит от вероятности найденной дифференциальной характеристики.

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

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

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

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

'''Входные данные''': алгоритм шифрования, константа <math>c</math>, вероятность характеристики <math>p</math>, число бит раундового ключа <math>b</math>, число раундов шифрования <math>R</math>, входная разница между парами текстов <math>deltafirst</math>, выходная разница между парами текстов <math>deltalast</math>

'''Объём входных данных''': Объем входных не изменяется, изменяются только сами входные данные.

'''Выходные данные''': Биты раундового ключа последнего раунда.

'''Объём выходных данных''': <math>b</math>.

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

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

=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===

Исследование проводилось на суперкомпьютере "Ломоносов-2". При компиляции использовался компилятор Openmpi/4.1.0-icc.

{| class="wikitable"
|-
|
! colspan="6"|Число процессов
|-
! Число генерируемых пар текстов
|1
|2
|4
|8
|16
|32
|-
|<math>10^7</math>
|42,1364
|21,1016
|11,6119
|6,1043
|3,06838
|1,5346
|-
|<math>2*10^7</math>
|84,4536
|45,0574
|23,3564
|12,2063
|6,13689
|3,0685
|-
|<math>4*10^7</math>
|169,6
|85,1138
|46,0756
|24,4103
|12,276
|6,1380
|-
|<math>8*10^7</math>
|339,081
|170,628
|95,0417
|48,8382
|24,5472
|12,275
|-
|<math>16*10^7</math>
|683,5931
|345,1143
|175,181
|97,6816
|49,094
|24,553
|-
|}
В следующей таблице представлены времена работы алгоритма для различного числа процессов и обрабатываемых пар текстов.
Графически результаты эксперимента представлены на рисунке ниже
[[Файл:Time.png|обрамить|центр|100x150px|Масштабируемость алгоритма]]
Алгоритм имеет сильную масштабируемость. Время выполнения алгоритма сокращается почти в 2 раза с увеличением числа обрабатываемых пар текстов в 2 раза.

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
На данный момент в Сети не было найдено существующих реализаций параллельного алгоритма дифференциальной атаки. Подразумевается, что такие реализации существуют, но не находятся в открытом доступе.

== Литература ==
<references />
M. Heys "A tutorial on linear and differential cryptanalysis" [https://ioactive.com/wp-content/uploads/2015/07/ldc_tutorial.pdf].

[[Категория:Статьи в работе]]
[[Категория:Матрично-векторные операции]]

[[En:Dense matrix-vector multiplication]]

Файл:Блок схема.jpg

2021-11-15T10:31:16Z

Demiandr:

схема работы

Файл:Infograph.jpg

2021-11-15T10:00:41Z

Demiandr:

Граф алгоритма атаки

Дифференцильная атака

2021-11-14T09:56:01Z

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

{{level-a}}

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

=== Общее описание алгоритма ===
Дифференциальный криптоанализ — метод криптоанализа симметричных блочных шифров (и других криптографических примитивов, в частности, хеш-функций и поточных шифров).
Дифференциальный криптоанализ основан на изучении преобразования разностей между шифруемыми значениями на различных раундах шифрования. В качестве разности, как правило, применяется операция побитового суммирования по модулю 2, хотя существуют атаки и с вычислением разности по модулю [math] 2^{32}[/math]. Является статистической атакой. Количество раундов современных шифров (AES, Camellia и др.) рассчитывалось с учётом обеспечения стойкости, в том числе и к дифференциальному криптоанализу.
Все существующие блочные алгоритмы шифрования являются итеративными алгоритмами, то есть при шифровании информация подвергается большому числу одних и тех же подряд идущих преобразований (раундов). В начале алгоритма шифрования из одного длинного секретного ключа при помощи алгоритма генерации раундовых ключей создаются мини-ключи, которые применяются на каждом раунде шифрования. Дифференциальный криптоанализ направлен на нахождение таких раундовых ключей, для последующего определения по ним основного секретного ключа криптосистемы, причем первым определяемым раундовым ключом является ключ последнего раунда шифрования.

=== Математическое описание алгоритма ===
Так как раундовые ключи однозначно получаются из основного секретного ключа, задачей криптоаналитика является нахождение раундовых ключей, после чего восстанавливается секретный ключ. В данном виде атак на блочные алгоритмы шифрования находятся статистические зависимости между двумя текстами с определенной входной разницей <math>Δfirst</math>, после чего определяется наиболее вероятная разница выходных шифртекстов <math>Δlast</math> на предпоследнем раунде <math>R-1</math>. Такая зависимость между входной и выходной разницами пар текстов называется дифференциальной характеристикой. Способы определения дифференциальных характеристик чрезвычайно сложны и разнятся от алгоритма к алгоритму, поэтому опускаются в данной статье. После нахождения дифференциальной характеристики производится атака на блочный алгоритм шифрования.
Пусть <math>p</math> - вероятность дифференциальной характеристики <math>Δfirst→Δlast</math>, воздействущей на <math>b</math> бит результирующего шифртекста. Тогда атака проводится следующим образом:
# Берется небольшая положительная константа <math>c</math> (обычно равная 2 или 3). Генерируется <math>c/p</math> пар текстов с входной разницей <math>Δfirst</math>;
# Все данные пары текстов пропускаются через <math>R</math> раундов алгоритма шифрования, после чего получаются соответствующие шифртексты <math>Y_{R}</math>;
# Для всех возможных значений <math>b</math> бит последнего раундового ключа заводится свой счетчик. Далее для каждой сгенерированной пары шифртекстов <math>Y_{R}</math> данные тексты расшифровываются на всех возможных значениях <math>b</math> бит раундового ключа, в результате чего получаются значения <math>Y_{R-1}</math>;
# Для каждой пары текстов путем их сложения находится своя разница <math>ΔY_{R-1}</math>. Далее значение <math>ΔY_{R-1}</math> сравнивается c <math>Δlast</math>. Если они совпадают, счетчик для данного <math>b</math> бит ключа увеличивается на 1.
После такого полного перебора раундовым ключом является то значение <math>b</math> бит, которое имеет наибольший счетчик. Определив таким образом биты раундового ключа можно найти значение секретного ключа и взломать алгоритм шифрования.

=== Вычислительное ядро алгоритма ===

Вычислительное ядром алгоритма является генерация и шифрование большого числа входных пар текстов алгоритма шифрования с заданной разницей <math>ΔX</math>, получая в итоге пары шифртекстов. После генерации текстов для каждой комбинации пары шифртекстов и возможного значения бит раундового ключа последнего раунда найденной характеристики происходит частичное расшифрование шифртекстов. Если разница между парами текстов <math>ΔY_{R-1}</math> на <math>{R-1}</math> раунде совпадает с искомой разницей <math>ΔU</math>, счетчик данного значения бит раундового ключа последнего раунда инкрементируется. Результатом является значение раундового ключа с наибольшим счетчиком.

=== Макроструктура алгоритма ===

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

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

В данном пункте приведены
<source lang="c++">
double p = 0.000001;//вероятность найденной характеристики
int c = 2;//константа
int R = 12;//число раундов шифра
int b = 4;//число бит раундового ключа, которые можно определить найденной характеристикой
__uint64 deltafirst=(2^34);// найденная характеристика (разница между парой текстов)
__uint64 deltalast=1;(найденная разница между текстами на предпоследнем раунде_
__uint64 firsttext;//первый текст из пары
__uint64 secondtext;//второй текст из пары
int result[pow(2,b)]={};//массив возможных значений бит раундового ключа
for (__uint64 i=0; i<(c/p);i++)
{
firsttext=i;//генерация первого текста пары
secondtext=i^deltafirst;//генерация второго текста пары
for (int j=0; j<R;j++)
{
firsttext = cipher(firsttext);
secondtext = cipher(secondtext);
}
for (int k=0; k< pow(2,b);k++)
{
firsttext = decipher(firsttext,k)
secondtext = decipher(secondtext,k)
if (deltalast == firsttext ^ secondtext)
{
result[k]++
}
}
}
int max=0
for (int k=0; k< pow(2,b);k++)
{
if (result[k] > max) max=result[k]
}
</source>
=== Последовательная сложность алгоритма ===

Cчитая базовой операцией операцию шифрования текста на одном раунде с использование дифференциальной характеристики с вероятностью <math>p</math>, на нахождение <math>b</math> бит раундового ключа <math>R-1</math> раунда шифрования потребуется около <math>(2c/p)(R+2^b)</math> операций шифрования, где <math>c</math> - некоторая небольшая константа. Так как основным параметром является вероятность <math>p</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|обрамить|центр|Алгоритм обработки только одного текста]]

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

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

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

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

'''Входные данные''': алгоритм шифрования, константа <math>c</math>, вероятность характеристики <math>p</math>, число бит раундового ключа <math>b</math>, число раундов шифрования <math>R</math>, входная разница между парами текстов <math>deltafirst</math>, выходная разница между парами текстов <math>deltalast</math>

'''Объём входных данных''': Объем входных не изменяется, изменяются только сами входные данные.

'''Выходные данные''': Биты раундового ключа последнего раунда.

'''Объём выходных данных''': <math>b</math>.

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

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

=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===

Исследование проводилось на суперкомпьютере "Ломоносов-2". При компиляции использовался компилятор Openmpi/4.1.0-icc.

{| class="wikitable"
|-
|
! colspan="6"|Число процессов
|-
! Число генерируемых пар текстов
|1
|2
|4
|8
|16
|32
|-
|<math>10^7</math>
|42,1364
|21,1016
|11,6119
|6,1043
|3,06838
|1,5346
|-
|<math>2*10^7</math>
|84,4536
|45,0574
|23,3564
|12,2063
|6,13689
|3,0685
|-
|<math>4*10^7</math>
|169,6
|85,1138
|46,0756
|24,4103
|12,276
|6,1380
|-
|<math>8*10^7</math>
|339,081
|170,628
|95,0417
|48,8382
|24,5472
|12,275
|-
|<math>16*10^7</math>
|683,5931
|345,1143
|175,181
|97,6816
|49,094
|24,553
|-
|}
В следующей таблице представлены времена работы алгоритма для различного числа процессов и обрабатываемых пар текстов.
Графически результаты эксперимента представлены на рисунке ниже
[[Файл:Time.png|обрамить|центр|100x150px|Масштабируемость алгоритма]]
Алгоритм имеет сильную масштабируемость. Время выполнения алгоритма сокращается почти в 2 раза с увеличением числа обрабатываемых пар текстов в 2 раза.

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
На данный момент в Сети не было найдено существующих реализаций параллельного алгоритма дифференциальной атаки. Подразумевается, что такие реализации существуют, но не находятся в открытом доступе.

== Литература ==
<references />
M. Heys "A tutorial on linear and differential cryptanalysis" [https://ioactive.com/wp-content/uploads/2015/07/ldc_tutorial.pdf].

[[Категория:Статьи в работе]]
[[Категория:Матрично-векторные операции]]

[[En:Dense matrix-vector multiplication]]

Дифференцильная атака

2021-11-14T09:53:33Z

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

{{level-a}}

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

=== Общее описание алгоритма ===
Дифференциальный криптоанализ — метод криптоанализа симметричных блочных шифров (и других криптографических примитивов, в частности, хеш-функций и поточных шифров).
Дифференциальный криптоанализ основан на изучении преобразования разностей между шифруемыми значениями на различных раундах шифрования. В качестве разности, как правило, применяется операция побитового суммирования по модулю 2, хотя существуют атаки и с вычислением разности по модулю [math] 2^{32}[/math]. Является статистической атакой. Количество раундов современных шифров (AES, Camellia и др.) рассчитывалось с учётом обеспечения стойкости, в том числе и к дифференциальному криптоанализу.
Все существующие блочные алгоритмы шифрования являются итеративными алгоритмами, то есть при шифровании информация подвергается большому числу одних и тех же подряд идущих преобразований (раундов). В начале алгоритма шифрования из одного длинного секретного ключа при помощи алгоритма генерации раундовых ключей создаются мини-ключи, которые применяются на каждом раунде шифрования. Дифференциальный криптоанализ направлен на нахождение таких раундовых ключей, для последующего определения по ним основного секретного ключа криптосистемы, причем первым определяемым раундовым ключом является ключ последнего раунда шифрования.

=== Математическое описание алгоритма ===
Так как раундовые ключи однозначно получаются из основного секретного ключа, задачей криптоаналитика является нахождение раундовых ключей, после чего восстанавливается секретный ключ. В данном виде атак на блочные алгоритмы шифрования находятся статистические зависимости между двумя текстами с определенной входной разницей <math>Δfirst</math>, после чего определяется наиболее вероятная разница выходных шифртекстов <math>Δlast</math> на предпоследнем раунде <math>R-1</math>. Такая зависимость между входной и выходной разницами пар текстов называется дифференциальной характеристикой. Способы определения дифференциальных характеристик чрезвычайно сложны и разнятся от алгоритма к алгоритму, поэтому опускаются в данной статье. После нахождения дифференциальной характеристики производится атака на блочный алгоритм шифрования.
Пусть <math>p</math> - вероятность дифференциальной характеристики <math>Δfirst→Δlast</math>, воздействущей на <math>b</math> бит результирующего шифртекста. Тогда атака проводится следующим образом:
# Берется небольшая положительная константа <math>c</math> (обычно равная 2 или 3). Генерируется <math>c/p</math> пар текстов с входной разницей <math>Δfirst</math>;
# Все данные пары текстов пропускаются через <math>R</math> раундов алгоритма шифрования, после чего получаются соответствующие шифртексты <math>Y_{R}</math>;
# Для всех возможных значений <math>b</math> бит последнего раундового ключа заводится свой счетчик. Далее для каждой сгенерированной пары шифртекстов <math>Y_{R}</math> данные тексты расшифровываются на всех возможных значениях <math>b</math> бит раундового ключа, в результате чего получаются значения <math>Y_{R-1}</math>;
# Для каждой пары текстов путем их сложения находится своя разница <math>ΔY_{R-1}</math>. Далее значение <math>ΔY_{R-1}</math> сравнивается c <math>Δlast</math>. Если они совпадают, счетчик для данного <math>b</math> бит ключа увеличивается на 1.
После такого полного перебора раундовым ключом является то значение <math>b</math> бит, которое имеет наибольший счетчик. Определив таким образом биты раундового ключа можно найти значение секретного ключа и взломать алгоритм шифрования.

=== Вычислительное ядро алгоритма ===

Вычислительное ядром алгоритма является генерация и шифрование большого числа входных пар текстов алгоритма шифрования с заданной разницей <math>ΔX</math>, получая в итоге пары шифртекстов. После генерации текстов для каждой комбинации пары шифртекстов и возможного значения бит раундового ключа последнего раунда найденной характеристики происходит частичное расшифрование шифртекстов. Если разница между парами текстов <math>ΔY_{R-1}</math> на <math>{R-1}</math> раунде совпадает с искомой разницей <math>ΔU</math>, счетчик данного значения бит раундового ключа последнего раунда инкрементируется. Результатом является значение раундового ключа с наибольшим счетчиком.

=== Макроструктура алгоритма ===

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

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

В данном пункте приведены
<source lang="c++">
double p = 0.000001;//вероятность найденной характеристики
int c = 2;//константа
int R = 12;//число раундов шифра
int b = 4;//число бит раундового ключа, которые можно определить найденной характеристикой
__uint64 deltafirst=(2^34);// найденная характеристика (разница между парой текстов)
__uint64 deltalast=1;(найденная разница между текстами на предпоследнем раунде_
__uint64 firsttext;//первый текст из пары
__uint64 secondtext;//второй текст из пары
int result[pow(2,b)]={};//массив возможных значений бит раундового ключа
for (__uint64 i=0; i<(c/p);i++)
{
firsttext=i;//генерация первого текста пары
secondtext=i^deltafirst;//генерация второго текста пары
for (int j=0; j<R;j++)
{
firsttext = cipher(firsttext);
secondtext = cipher(secondtext);
}
for (int k=0; k< pow(2,b);k++)
{
firsttext = decipher(firsttext,k)
secondtext = decipher(secondtext,k)
if (deltalast == firsttext ^ secondtext)
{
result[k]++
}
}
}
int max=0
for (int k=0; k< pow(2,b);k++)
{
if (result[k] > max) max=result[k]
}
</source>
=== Последовательная сложность алгоритма ===

Cчитая базовой операцией операцию шифрования текста на одном раунде с использование дифференциальной характеристики с вероятностью <math>p</math>, на нахождение <math>b</math> бит раундового ключа <math>R-1</math> раунда шифрования потребуется около <math>(2c/p)(R+2^b)</math> операций шифрования, где <math>c</math> - некоторая небольшая константа. Так как основным параметром является вероятность <math>p</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|обрамить|центр|Информационная схема работы алгоритма]]

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

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

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

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

'''Входные данные''': алгоритм шифрования, константа <math>c</math>, вероятность характеристики <math>p</math>, число бит раундового ключа <math>b</math>, число раундов шифрования <math>R</math>, входная разница между парами текстов <math>deltafirst</math>, выходная разница между парами текстов <math>deltalast</math>

'''Объём входных данных''': Объем входных не изменяется, изменяются только сами входные данные.

'''Выходные данные''': Биты раундового ключа последнего раунда.

'''Объём выходных данных''': <math>b</math>.

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

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

=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===

Исследование проводилось на суперкомпьютере "Ломоносов-2". При компиляции использовался компилятор Openmpi/4.1.0-icc.

{| class="wikitable"
|-
|
! colspan="6"|Число процессов
|-
! Число генерируемых пар текстов
|1
|2
|4
|8
|16
|32
|-
|<math>10^7</math>
|42,1364
|21,1016
|11,6119
|6,1043
|3,06838
|1,5346
|-
|<math>2*10^7</math>
|84,4536
|45,0574
|23,3564
|12,2063
|6,13689
|3,0685
|-
|<math>4*10^7</math>
|169,6
|85,1138
|46,0756
|24,4103
|12,276
|6,1380
|-
|<math>8*10^7</math>
|339,081
|170,628
|95,0417
|48,8382
|24,5472
|12,275
|-
|<math>16*10^7</math>
|683,5931
|345,1143
|175,181
|97,6816
|49,094
|24,553
|-
|}
В следующей таблице представлены времена работы алгоритма для различного числа процессов и обрабатываемых пар текстов.
Графически результаты эксперимента представлены на рисунке ниже
[[Файл:Time.png|обрамить|центр|100x150px|Масштабируемость алгоритма]]
Алгоритм имеет сильную масштабируемость. Время выполнения алгоритма сокращается почти в 2 раза с увеличением числа обрабатываемых пар текстов в 2 раза.

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
На данный момент в Сети не было найдено существующих реализаций параллельного алгоритма дифференциальной атаки. Подразумевается, что такие реализации существуют, но не находятся в открытом доступе.

== Литература ==
<references />
M. Heys "A tutorial on linear and differential cryptanalysis" [https://ioactive.com/wp-content/uploads/2015/07/ldc_tutorial.pdf].

[[Категория:Статьи в работе]]
[[Категория:Матрично-векторные операции]]

[[En:Dense matrix-vector multiplication]]

Дифференцильная атака

2021-11-14T09:15:32Z

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

{{level-a}}

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

=== Общее описание алгоритма ===
Дифференциальный криптоанализ — метод криптоанализа симметричных блочных шифров (и других криптографических примитивов, в частности, хеш-функций и поточных шифров).
Дифференциальный криптоанализ основан на изучении преобразования разностей между шифруемыми значениями на различных раундах шифрования. В качестве разности, как правило, применяется операция побитового суммирования по модулю 2, хотя существуют атаки и с вычислением разности по модулю [math] 2^{32}[/math]. Является статистической атакой. Количество раундов современных шифров (AES, Camellia и др.) рассчитывалось с учётом обеспечения стойкости, в том числе и к дифференциальному криптоанализу.
Все существующие блочные алгоритмы шифрования являются итеративными алгоритмами, то есть при шифровании информация подвергается большому числу одних и тех же подряд идущих преобразований (раундов). В начале алгоритма шифрования из одного длинного секретного ключа при помощи алгоритма генерации раундовых ключей создаются мини-ключи, которые применяются на каждом раунде шифрования. Дифференциальный криптоанализ направлен на нахождение таких раундовых ключей, для последующего определения по ним основного секретного ключа криптосистемы, причем первым определяемым раундовым ключом является ключ последнего раунда шифрования.

=== Математическое описание алгоритма ===
Так как раундовые ключи однозначно получаются из основного секретного ключа, задачей криптоаналитика является нахождение раундовых ключей, после чего восстанавливается секретный ключ. В данном виде атак на блочные алгоритмы шифрования находятся статистические зависимости между двумя текстами с определенной входной разницей <math>Δfirst</math>, после чего определяется наиболее вероятная разница выходных шифртекстов <math>Δlast</math> на предпоследнем раунде <math>R-1</math>. Такая зависимость между входной и выходной разницами пар текстов называется дифференциальной характеристикой. Способы определения дифференциальных характеристик чрезвычайно сложны и разнятся от алгоритма к алгоритму, поэтому опускаются в данной статье. После нахождения дифференциальной характеристики производится атака на блочный алгоритм шифрования.
Пусть <math>p</math> - вероятность дифференциальной характеристики <math>Δfirst→Δlast</math>, воздействущей на <math>b</math> бит результирующего шифртекста. Тогда атака проводится следующим образом:
# Берется небольшая положительная константа <math>c</math> (обычно равная 2 или 3). Генерируется <math>c/p</math> пар текстов с входной разницей <math>Δfirst</math>;
# Все данные пары текстов пропускаются через <math>R</math> раундов алгоритма шифрования, после чего получаются соответствующие шифртексты <math>Y_{R}</math>;
# Для всех возможных значений <math>b</math> бит последнего раундового ключа заводится свой счетчик. Далее для каждой сгенерированной пары шифртекстов <math>Y_{R}</math> данные тексты расшифровываются на всех возможных значениях <math>b</math> бит раундового ключа, в результате чего получаются значения <math>Y_{R-1}</math>;
# Для каждой пары текстов путем их сложения находится своя разница <math>ΔY_{R-1}</math>. Далее значение <math>ΔY_{R-1}</math> сравнивается c <math>Δlast</math>. Если они совпадают, счетчик для данного <math>b</math> бит ключа увеличивается на 1.
После такого полного перебора раундовым ключом является то значение <math>b</math> бит, которое имеет наибольший счетчик. Определив таким образом биты раундового ключа можно найти значение секретного ключа и взломать алгоритм шифрования.

=== Вычислительное ядро алгоритма ===

Вычислительное ядром алгоритма является генерация и шифрование большого числа входных пар текстов алгоритма шифрования с заданной разницей <math>ΔX</math>, получая в итоге пары шифртекстов. После генерации текстов для каждой комбинации пары шифртекстов и возможного значения бит раундового ключа последнего раунда найденной характеристики происходит частичное расшифрование шифртекстов. Если разница между парами текстов <math>ΔY_{R-1}</math> на <math>{R-1}</math> раунде совпадает с искомой разницей <math>ΔU</math>, счетчик данного значения бит раундового ключа последнего раунда инкрементируется. Результатом является значение раундового ключа с наибольшим счетчиком.

=== Макроструктура алгоритма ===

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

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

В данном пункте приведены
<source lang="c++">
double p = 0.000001;//вероятность найденной характеристики
int c = 2;//константа
int R = 12;//число раундов шифра
int b = 4;//число бит раундового ключа, которые можно определить найденной характеристикой
__uint64 deltafirst=(2^34);// найденная характеристика (разница между парой текстов)
__uint64 deltalast=1;(найденная разница между текстами на предпоследнем раунде_
__uint64 firsttext;//первый текст из пары
__uint64 secondtext;//второй текст из пары
int result[pow(2,b)]={};//массив возможных значений бит раундового ключа
for (__uint64 i=0; i<(c/p);i++)
{
firsttext=i;//генерация первого текста пары
secondtext=i^deltafirst;//генерация второго текста пары
for (int j=0; j<R;j++)
{
firsttext = cipher(firsttext);
secondtext = cipher(secondtext);
}
for (int k=0; k< pow(2,b);k++)
{
firsttext = decipher(firsttext,k)
secondtext = decipher(secondtext,k)
if (deltalast == firsttext ^ secondtext)
{
result[k]++
}
}
}
int max=0
for (int k=0; k< pow(2,b);k++)
{
if (result[k] > max) max=result[k]
}
</source>
=== Последовательная сложность алгоритма ===

Cчитая базовой операцией операцию шифрования текста на одном раунде с использование дифференциальной характеристики с вероятностью <math>p</math>, на нахождение <math>b</math> бит раундового ключа <math>R-1</math> раунда шифрования потребуется около <math>(2c/p)(R+2^b)</math> операций шифрования, где <math>c</math> - некоторая небольшая константа. Так как основным параметром является вероятность <math>p</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|обрамить|центр|Информационная схема работы алгоритма]]

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

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

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

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

'''Входные данные''': алгоритм шифрования, константа <math>c</math>, вероятность характеристики <math>p</math>, число бит раундового ключа <math>b</math>, число раундов шифрования <math>R</math>, входная разница между парами текстов <math>deltafirst</math>, выходная разница между парами текстов <math>deltalast</math>

'''Объём входных данных''': Объем входных не изменяется, изменяются только сами входные данные.

'''Выходные данные''': Биты раундового ключа последнего раунда.

'''Объём выходных данных''': <math>b</math>.

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

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

=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===

Исследование проводилось на суперкомпьютере "Ломоносов-2". При компиляции использовался компилятор Openmpi/4.1.0-icc.

{| class="wikitable"
|-
|
! colspan="6"|Число процессов
|-
! Число генерируемых пар текстов
|1
|2
|4
|8
|16
|32
|-
|<math>10^7</math>
|42,1364
|21,1016
|11,6119
|6,1043
|3,06838
|1,5346
|-
|<math>2*10^7</math>
|84,4536
|45,0574
|23,3564
|12,2063
|6,13689
|3,0685
|-
|<math>4*10^7</math>
|169,6
|85,1138
|46,0756
|24,4103
|12,276
|6,1380
|-
|<math>8*10^7</math>
|339,081
|170,628
|95,0417
|48,8382
|24,5472
|12,275
|-
|<math>16*10^7</math>
|683,5931
|345,1143
|175,181
|97,6816
|49,094
|24,553
|-
|}
В следующей таблице представлены времена работы алгоритма для различного числа процессов и обрабатываемых пар текстов.
Графически результаты эксперимента представлены на рисунке ниже
[[Файл:Time.png|обрамить|центр|100x150px|Масштабируемость алгоритма]]
Алгоритм имеет сильную масштабируемость. Время выполнения алгоритма сокращается почти в 2 раза с увеличением числа обрабатываемых пар текстов в 2 раза.

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
На данный момент в Сети не было найдено существующих реализаций параллельного алгоритма дифференциальной атаки. Подразумевается, что такие реализации существуют, но не находятся в открытом доступе.

== Литература ==
<references />
M. Heys "A tutorial on linear and differential cryptanalysis" [https://ioactive.com/wp-content/uploads/2015/07/ldc_tutorial.pdf].

[[Категория:Статьи в работе]]
[[Категория:Матрично-векторные операции]]

[[En:Dense matrix-vector multiplication]]

Дифференцильная атака

2021-11-14T09:00:02Z

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

Дифференцильная атака

2021-11-13T13:54:56Z

Demiandr:

Файл:Time.png

2021-11-13T13:45:10Z

Demiandr:

Время работы

Дифференцильная атака

2021-11-13T13:40:29Z

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

Дифференцильная атака

2021-11-13T12:50:53Z

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

Дифференцильная атака

2021-11-13T12:46:39Z

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

Дифференцильная атака

2021-11-04T13:24:13Z

Demiandr: Новая страница: «{{level-a}} == Свойства и структура алгоритма == === Общее описание алгоритма === Дифференциальн...»

Дифференацильная атака

2021-11-04T13:14:13Z

Demiandr: /* Математическое описание алгоритма */

Дифференацильная атака

2021-11-04T12:38:16Z

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

Дифференацильная атака

2021-11-04T12:20:05Z

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

Дифференацильная атака

2021-11-04T12:19:19Z

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

Дифференацильная атака

2021-11-04T12:14:29Z

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

Дифференацильная атака

2021-11-04T12:13:20Z

Demiandr:

Файл:Graphdifferential.jpg

2021-11-04T11:50:05Z

Demiandr:

work

Дифференацильная атака

2021-11-04T11:31:07Z

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

Дифференацильная атака

2021-11-04T11:30:24Z

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

{{level-a}}

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

=== Общее описание алгоритма ===
Дифференциальный криптоанализ — метод криптоанализа симметричных блочных шифров (и других криптографических примитивов, в частности, хеш-функций и поточных шифров).
Дифференциальный криптоанализ основан на изучении преобразования разностей между шифруемыми значениями на различных раундах шифрования. В качестве разности, как правило, применяется операция побитового суммирования по модулю 2, хотя существуют атаки и с вычислением разности по модулю {\displaystyle 2^{32}}2^{32}. Является статистической атакой. Применим для взлома DES, FEAL и некоторых других шифров, как правило, разработанных ранее начала 90-х. Количество раундов современных шифров (AES, Camellia и др.) рассчитывалось с учётом обеспечения стойкости, в том числе и к дифференциальному криптоанализу.
Все существующие блочные алгоритмы шифрования являются итеративными алгоритмами, то есть при шифровании информация подвергается большому числу одних и тех же подряд идущих преобразований (раундов). В начале алгоритма шифрования из одного длинного секретного ключа при помощи алгоритма генерации раундовых ключей создаются мини-ключи, которые применяются на каждом раунде шифрования. Дифференциальный криптоанализ направлен на нахождение таких раундовых ключей, для последующего определения по ним основного секретного ключа криптосистемы, причем первым определяемым раундовым ключом является ключ последнего раунда шифрования.

=== Математическое описание алгоритма ===
Пусть <math>ΔX=({ΔX_1}{ΔX_2}{ΔX_3}...{ΔX_3})</math>
Задачей криптоаналитика является нахождение
Пусть <math>{p}</math> - вероя

=== Вычислительное ядро алгоритма ===

Вычислительное ядром алгоритма является генерация и шифрование большого числа входных пар текстов алгоритма шифрования с заданной разницей <math>ΔX</math>, получая в итоге пары шифртекстов. После генерации текстов для каждой комбинации пары шифртекстов и возможного значения бит раундового ключа последнего раунда найденной характеристики происходит частичное расшифрование шифртекстов. Если разница между парами текстов <math>ΔY_{R-1}</math> на <math>{R-1}</math> раунде совпадает с искомой разницей <math>ΔU</math>, счетчик данного значения бит раундового ключа последнего раунда инкрементируется. Результатом является значение раундового ключа с наибольшим счетчиком.

=== Макроструктура алгоритма ===

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

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

В данном пункте приведены
<source lang="c++">
double p = 0.000001;//вероятность найденной характеристики
int c = 2;//константа
int R = 12;//число раундов шифра
int b = 4;//число бит раундового ключа, которые можно определить найденной характеристикой
__uint64 deltafirst=(2^34);// найденная характеристика (разница между парой текстов)
__uint64 deltalast=1;(найденная разница между текстами на предпоследнем раунде_
__uint64 firsttext;//первый текст из пары
__uint64 secondtext;//второй текст из пары
int result[pow(2,b)]={};//массив возможных значений бит раундового ключа
for (__uint64 i=0; i<(c/p);i++)
{
firsttext=i;//генерация первого текста пары
secondtext=i^deltafirst;//генерация второго текста пары
for (int j=0; j<R;j++)
{
firsttext = cipher(firsttext);
secondtext = cipher(secondtext);
}
for (int k=0; k< pow(2,b);k++)
{
firsttext = decipher(firsttext,k)
secondtext = decipher(secondtext,k)
if (deltalast == firsttext ^ secondtext)
{
result[k]++
}
}
}
int max=0
for (int k=0; k< pow(2,b);k++)
{
if (result[k] > max) max=result[k]
}
</source>
=== Последовательная сложность алгоритма ===

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

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

Опишем [[глоссарий#Граф алгоритма|граф алгоритма]] как аналитически, так и в виде рисунка.

[[Файл:YeqAX.png|500px|thumb|center|Рисунок 1. Граф последовательного умножения плотной матрицы на вектор с отображением входных и выходных данных]]

Граф алгоритма умножения плотной матрицы на вектор состоит из одной группы вершин, расположенной в целочисленных узлах двумерной области, соответствующая ей операция <math>a+bc</math>.

Естественно введённые координаты области таковы:
* <math>i</math> — меняется в диапазоне от <math>1</math> до <math>m</math>, принимая все целочисленные значения;
* <math>j</math> — меняется в диапазоне от <math>1</math> до <math>n</math>, принимая все целочисленные значения.

Аргументы операции следующие:
*<math>a</math>:
** при <math>j = 1</math> константа <math>0.</math>;
** при <math>j > 1</math> — результат срабатывания операции, соответствующей вершине с координатами <math>i, j-1</math>;
*<math>b</math> — элемент ''входных данных'', а именно <math>a_{ij}</math>;
*<math>c</math> - элемент входных данных <math>x_{j}</math>;

Результат срабатывания операции является:
* при <math>j < n</math> - ''промежуточным данным'' алгоритма;
* при <math>j = n</math> - выходным данным.

Описанный граф можно посмотреть на рисунке, выполненном для случая <math>m = 4, n = 5</math>. Здесь вершины обозначены голубым цветом. Изображена подача только входных данных из вектора <math>x</math>, подача элементов матрицы <math>A</math>, идущая во все вершины, на рисунке не представлена.

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

Для алгоритма умножения квадратной матрицы на вектор порядка n в параллельном варианте требуется последовательно выполнить следующие ярусы:

* по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>n</math> операций).

Для умножения матрицы размером <math>m</math> строк на <math>n</math> столбцов на вектор порядка <math>n</math> в последовательном (наиболее быстром) варианте требуется:

* по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>m</math> операций).

При этом использование режима накопления требует совершения умножений и сложений в режиме двойной точности, а в параллельном варианте это означает, что практически все промежуточные вычисления для выполнения алгоритма в режиме накопления должны быть двойной точности. В отличие от последовательного варианта это означает некоторое увеличение требуемой памяти.

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

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

'''Входные данные''': алгоритм шифрования, константа <math>c</math>, вероятность характеристики <math>p</math>, число бит раундового ключа <math>b</math>, число раундов шифрования <math>R</math>, входная разница между парами текстов <math>deltafirst</math>, выходная разница между парами текстов <math>deltalast</math>

'''Объём входных данных''': Объем входных не изменяется, изменяются только сами входные данные.

'''Выходные данные''': Биты раундового ключа последнего раунда.

'''Объём выходных данных''': <math>b</math>.

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

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

=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
[[file:Масштабируемость перемножения матрицы и вектора производительность.png|thumb|center|700px|Рисунок 5. Параллельная реализация произведения матрицы на вектор Максимальная производительность. ]]
[[file:Масштабируемость перемножения матрицы и вектора эффективность.png|thumb|center|700px|Рисунок 6. Параллельная реализация произведения матрицы на вектор Максимальная эффективность. ]]
Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма:
* число процессоров [4 : 256]
* размерность матрицы [1024 : 51200]
Эффективность выполнения реализации алгоритма
* Минимальная эффективность 0,02%
* Максимальная эффективность 9,55%
Оценка масштабируемости
* По числу процессов: -0.01517 – при увеличении числа процессов эффективность убывает достаточно интенсивно на всей рассмотренной области изменений параметров запуска. Уменьшение эффективности на рассмотренной области работы параллельной программы звязано с увеличением числа пересылок с ростом числа процессов и как следствие ростом накладных расходов на организацию вычислений. Основной вклад в значение эффективности вносит область с малым числом процессов и малой задачей, там эффективность достигает максимума в 9,5%. Далее эффективность очень резко падает до уровня около 1% Присутствует область, на которой при увеличении числа процессов эффективность возрастает, но при дальнейшем росте продолжает снижаться. Это скорее всего объясняется декомпозицей данных, при которой наступает момент, когда размер матрицы позволяет блокам укладываться в КЭШ-память. Так же это подтверждает проявление этого явления, но со смещением по числу процессов, и при увеличении вычислительной сложности задачи.
* По размеру задачи: -0.0014 – при увеличении размера задачи эффективность в целом уменьшается по рассматриваемой области, хотя и менее интенсивно, чем при увеличении числа процессов. Снижение эффективности объясняется тем, что при росте вычислительной сложности существенно возрастают объемы передаваемых данных. При увеличении размера данных наступает момент резкого снижения эффективности с значений около 1% к долям процента и минимуму. С увеличением числа процессоров такой переход появляется на большем объеме данных. Это свидетельствует о том, что присутствует момент, когда данных слишком много и эффективность работы с ними становится значительно ниже, но чем больше имеется процессов, там позже наступает такой момент декомпозиции. Присутствует область возрастания эффективности, на всех рассмотренных размерах матрицы. Это объясняется тем, что при малом размере задачи данные хорошо укладываются в КЭШ память, что приводит к высокой эффективности работы приложения при малом размере задачи. При дальнейшем увеличении размера эффективность уменьшается при выходе за границы КЭШ-памяти.
* По двум направлениям: -0.0001546 – при рассмотрении увеличения, как вычислительной сложности, так и числа процессов по всей рассмотренной области значений уменьшается, интенсивность уменьшения эффективности не очень высока. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров составляет около 9% говорит о том, что уменьшение эффективности по всей области довольно равномерное, но интенсивно лишь в не очень больших участках по площади. На остальной области значений параметров изменения эффективности не столь значительны и находятся на приблизительно одном и том же уровне.

[http://git.algowiki-project.org/Teplov/Scalability/blob/master/matrix_vector_mult/mpi_mat_vect_time.c Реализация алгоритма на языке C]

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

== Литература ==
<references />

[[Категория:Статьи в работе]]
[[Категория:Матрично-векторные операции]]

[[En:Dense matrix-vector multiplication]]

Дифференацильная атака

2021-11-04T10:45:58Z

{{level-a}}

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

=== Общее описание алгоритма ===
Дифференциальный криптоанализ — метод криптоанализа симметричных блочных шифров (и других криптографических примитивов, в частности, хеш-функций и поточных шифров).
Дифференциальный криптоанализ основан на изучении преобразования разностей между шифруемыми значениями на различных раундах шифрования. В качестве разности, как правило, применяется операция побитового суммирования по модулю 2, хотя существуют атаки и с вычислением разности по модулю {\displaystyle 2^{32}}2^{32}. Является статистической атакой. Применим для взлома DES, FEAL и некоторых других шифров, как правило, разработанных ранее начала 90-х. Количество раундов современных шифров (AES, Camellia и др.) рассчитывалось с учётом обеспечения стойкости, в том числе и к дифференциальному криптоанализу.
Все существующие блочные алгоритмы шифрования являются итеративными алгоритмами, то есть при шифровании информация подвергается большому числу одних и тех же подряд идущих преобразований (раундов). В начале алгоритма шифрования из одного длинного секретного ключа при помощи алгоритма генерации раундовых ключей создаются мини-ключи, которые применяются на каждом раунде шифрования. Дифференциальный криптоанализ направлен на нахождение таких раундовых ключей, для последующего определения по ним основного секретного ключа криптосистемы, причем первым определяемым раундовым ключом является ключ последнего раунда шифрования.

=== Математическое описание алгоритма ===
Пусть <math>ΔX=({ΔX_1}{ΔX_2}{ΔX_3}...{ΔX_3})</math>
Задачей криптоаналитика является нахождение
Пусть <math>{p}</math> - вероя

=== Вычислительное ядро алгоритма ===

Вычислительное ядром алгоритма является генерация и шифрование большого числа входных пар текстов алгоритма шифрования с заданной разницей <math>ΔX</math>, получая в итоге пары шифртекстов. После генерации текстов для каждой комбинации пары шифртекстов и возможного значения бит раундового ключа последнего раунда найденной характеристики происходит частичное расшифрование шифртекстов. Если разница между парами текстов <math>ΔY_{R-1}</math> на <math>{R-1}</math> раунде совпадает с искомой разницей <math>ΔU</math>, счетчик данного значения бит раундового ключа последнего раунда инкрементируется. Результатом является значение раундового ключа с наибольшим счетчиком.

=== Макроструктура алгоритма ===

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

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

В данном пункте приведены
<source lang="c++">
double p = 0.000001;//вероятность найденной характеристики
int c = 2;//константа
int R = 12;//число раундов шифра
int b = 4;//число бит раундового ключа, которые можно определить найденной характеристикой
__uint64 deltafirst=(2^34);// найденная характеристика (разница между парой текстов)
__uint64 deltalast=1;(найденная разница между текстами на предпоследнем раунде_
__uint64 firsttext;//первый текст из пары
__uint64 secondtext;//второй текст из пары
int result[pow(2,b)]={};//массив возможных значений бит раундового ключа
for (__uint64 i=0; i<(c/p);i++)
{
firsttext=i;//генерация первого текста пары
secondtext=i^deltafirst;//генерация второго текста пары
for (int j=0; j<R;j++)
{
firsttext = cipher(firsttext);
secondtext = cipher(secondtext);
}
for (int k=0; k< pow(2,b);k++)
{
firsttext = decipher(firsttext,k)
secondtext = decipher(secondtext,k)
if (deltalast == firsttext ^ secondtext)
{
result[k]++
}
}
}
int max=0
for (int k=0; k< pow(2,b);k++)
{
if (result[k] > max) max=result[k]
}
</source>
=== Последовательная сложность алгоритма ===

Cчитая базовой операцией операцию шифрования текста на одном раунде с использование дифференциальной характеристики с вероятностью <math>p</math>, на нахождение <math>b</math> бит раундового ключа <math>R-1</math> раунда шифрования потребуется около <math>(2с/p)(R+2^b)</math> операций шифрования, где <math>с</math> - некоторая небольшая константа. Так как основным параметром является вероятность <math>p</math>, от которой зависит числе пар текстов, данный алгоритм имеет линейную сложность.

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

Опишем [[глоссарий#Граф алгоритма|граф алгоритма]] как аналитически, так и в виде рисунка.

[[Файл:YeqAX.png|500px|thumb|center|Рисунок 1. Граф последовательного умножения плотной матрицы на вектор с отображением входных и выходных данных]]

Граф алгоритма умножения плотной матрицы на вектор состоит из одной группы вершин, расположенной в целочисленных узлах двумерной области, соответствующая ей операция <math>a+bc</math>.

Естественно введённые координаты области таковы:
* <math>i</math> — меняется в диапазоне от <math>1</math> до <math>m</math>, принимая все целочисленные значения;
* <math>j</math> — меняется в диапазоне от <math>1</math> до <math>n</math>, принимая все целочисленные значения.

Аргументы операции следующие:
*<math>a</math>:
** при <math>j = 1</math> константа <math>0.</math>;
** при <math>j > 1</math> — результат срабатывания операции, соответствующей вершине с координатами <math>i, j-1</math>;
*<math>b</math> — элемент ''входных данных'', а именно <math>a_{ij}</math>;
*<math>c</math> - элемент входных данных <math>x_{j}</math>;

Результат срабатывания операции является:
* при <math>j < n</math> - ''промежуточным данным'' алгоритма;
* при <math>j = n</math> - выходным данным.

Описанный граф можно посмотреть на рисунке, выполненном для случая <math>m = 4, n = 5</math>. Здесь вершины обозначены голубым цветом. Изображена подача только входных данных из вектора <math>x</math>, подача элементов матрицы <math>A</math>, идущая во все вершины, на рисунке не представлена.

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

Для алгоритма умножения квадратной матрицы на вектор порядка n в параллельном варианте требуется последовательно выполнить следующие ярусы:

* по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>n</math> операций).

Для умножения матрицы размером <math>m</math> строк на <math>n</math> столбцов на вектор порядка <math>n</math> в последовательном (наиболее быстром) варианте требуется:

* по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>m</math> операций).

При этом использование режима накопления требует совершения умножений и сложений в режиме двойной точности, а в параллельном варианте это означает, что практически все промежуточные вычисления для выполнения алгоритма в режиме накопления должны быть двойной точности. В отличие от последовательного варианта это означает некоторое увеличение требуемой памяти.

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

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

'''Входные данные''': алгоритм шифрования, константа <math>c</math>, вероятность характеристики <math>p</math>, число бит раундового ключа <math>b</math>, число раундов шифрования <math>R</math>, входная разница между парами текстов <math>deltafirst</math>, выходная разница между парами текстов <math>deltalast</math>

'''Объём входных данных''': Объем входных не изменяется, изменяются только сами входные данные.

'''Выходные данные''': Биты раундового ключа последнего раунда.

'''Объём выходных данных''': <math>b</math>.

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

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

=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
[[file:Масштабируемость перемножения матрицы и вектора производительность.png|thumb|center|700px|Рисунок 5. Параллельная реализация произведения матрицы на вектор Максимальная производительность. ]]
[[file:Масштабируемость перемножения матрицы и вектора эффективность.png|thumb|center|700px|Рисунок 6. Параллельная реализация произведения матрицы на вектор Максимальная эффективность. ]]
Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма:
* число процессоров [4 : 256]
* размерность матрицы [1024 : 51200]
Эффективность выполнения реализации алгоритма
* Минимальная эффективность 0,02%
* Максимальная эффективность 9,55%
Оценка масштабируемости
* По числу процессов: -0.01517 – при увеличении числа процессов эффективность убывает достаточно интенсивно на всей рассмотренной области изменений параметров запуска. Уменьшение эффективности на рассмотренной области работы параллельной программы звязано с увеличением числа пересылок с ростом числа процессов и как следствие ростом накладных расходов на организацию вычислений. Основной вклад в значение эффективности вносит область с малым числом процессов и малой задачей, там эффективность достигает максимума в 9,5%. Далее эффективность очень резко падает до уровня около 1% Присутствует область, на которой при увеличении числа процессов эффективность возрастает, но при дальнейшем росте продолжает снижаться. Это скорее всего объясняется декомпозицей данных, при которой наступает момент, когда размер матрицы позволяет блокам укладываться в КЭШ-память. Так же это подтверждает проявление этого явления, но со смещением по числу процессов, и при увеличении вычислительной сложности задачи.
* По размеру задачи: -0.0014 – при увеличении размера задачи эффективность в целом уменьшается по рассматриваемой области, хотя и менее интенсивно, чем при увеличении числа процессов. Снижение эффективности объясняется тем, что при росте вычислительной сложности существенно возрастают объемы передаваемых данных. При увеличении размера данных наступает момент резкого снижения эффективности с значений около 1% к долям процента и минимуму. С увеличением числа процессоров такой переход появляется на большем объеме данных. Это свидетельствует о том, что присутствует момент, когда данных слишком много и эффективность работы с ними становится значительно ниже, но чем больше имеется процессов, там позже наступает такой момент декомпозиции. Присутствует область возрастания эффективности, на всех рассмотренных размерах матрицы. Это объясняется тем, что при малом размере задачи данные хорошо укладываются в КЭШ память, что приводит к высокой эффективности работы приложения при малом размере задачи. При дальнейшем увеличении размера эффективность уменьшается при выходе за границы КЭШ-памяти.
* По двум направлениям: -0.0001546 – при рассмотрении увеличения, как вычислительной сложности, так и числа процессов по всей рассмотренной области значений уменьшается, интенсивность уменьшения эффективности не очень высока. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров составляет около 9% говорит о том, что уменьшение эффективности по всей области довольно равномерное, но интенсивно лишь в не очень больших участках по площади. На остальной области значений параметров изменения эффективности не столь значительны и находятся на приблизительно одном и том же уровне.

[http://git.algowiki-project.org/Teplov/Scalability/blob/master/matrix_vector_mult/mpi_mat_vect_time.c Реализация алгоритма на языке C]

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

== Литература ==
<references />

[[Категория:Статьи в работе]]
[[Категория:Матрично-векторные операции]]

[[En:Dense matrix-vector multiplication]]

Участник:Demiandr

2021-11-04T10:06:15Z

Demiandr: /* Вычислительное ядро алгоритма */

{{level-a}}

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

=== Общее описание алгоритма ===
Дифференциальный криптоанализ — метод криптоанализа симметричных блочных шифров (и других криптографических примитивов, в частности, хеш-функций и поточных шифров).
Дифференциальный криптоанализ основан на изучении преобразования разностей между шифруемыми значениями на различных раундах шифрования. В качестве разности, как правило, применяется операция побитового суммирования по модулю 2, хотя существуют атаки и с вычислением разности по модулю {\displaystyle 2^{32}}2^{32}. Является статистической атакой. Применим для взлома DES, FEAL и некоторых других шифров, как правило, разработанных ранее начала 90-х. Количество раундов современных шифров (AES, Camellia и др.) рассчитывалось с учётом обеспечения стойкости, в том числе и к дифференциальному криптоанализу.
Все существующие блочные алгоритмы шифрования являются итеративными алгоритмами, то есть при шифровании информация подвергается большому числу одних и тех же подряд идущих преобразований (раундов). В начале алгоритма шифрования из одного длинного секретного ключа при помощи алгоритма генерации раундовых ключей создаются мини-ключи, которые применяются на каждом раунде шифрования. Дифференциальный криптоанализ направлен на нахождение таких раундовых ключей, для последующего определения по ним основного секретного ключа криптосистемы, причем первым определяемым раундовым ключом является ключ последнего раунда шифрования.

=== Математическое описание алгоритма ===
Пусть <math>ΔX=({ΔX_1}{ΔX_2}{ΔX_3}...{ΔX_3})</math>
Задачей криптоаналитика является нахождение
Пусть <math>{p}</math> - вероя

=== Вычислительное ядро алгоритма ===

Вычислительное ядром алгоритма является генерация и шифрование большого числа входных пар текстов алгоритма шифрования с заданной разницей <math>ΔX</math>, получая в итоге пары шифртекстов. После генерации текстов для каждой комбинации пары шифртекстов и возможного значения бит раундового ключа последнего раунда найденной характеристики происходит частичное расшифрование шифртекстов. Если разница между парами текстов <math>ΔY_{R-1}</math> на <math>{R-1}</math> раунде совпадает с искомой разницей <math>ΔU</math>, счетчик данного значения бит раундового ключа последнего раунда инкрементируется. Результатом является значение раундового ключа с наибольшим счетчиком.

=== Макроструктура алгоритма ===

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

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

В данном пункте приведены
<source lang="c++">
double p = 0.000001;//вероятность найденной характеристики
int c = 2;//константа
int R = 12;//число раундов шифра
int b = 4;//число бит раундового ключа, которые можно определить найденной характеристикой
__uint64 deltafirst=(2^34);// найденная характеристика (разница между парой текстов)
__uint64 deltalast=1;(найденная разница между текстами на предпоследнем раунде_
__uint64 firsttext;//первый текст из пары
__uint64 secondtext;//второй текст из пары
int result[pow(2,b)]={};//массив возможных значений бит раундового ключа
for (__uint64 i=0; i<(c/p);i++)
{
firsttext=i;//генерация первого текста пары
secondtext=i^deltafirst;//генерация второго текста пары
for (int j=0; j<R;j++)
{
firsttext = cipher(firsttext);
secondtext = cipher(secondtext);
}
for (int k=0; k< pow(2,b);k++)
{
firsttext = decipher(firsttext,k)
secondtext = decipher(secondtext,k)
if (deltalast == firsttext ^ secondtext)
{
result[k]++
}
}
}
int max=0
for (int k=0; k< pow(2,b);k++)
{
if (result[k] > max) max=result[k]
}
</source>
=== Последовательная сложность алгоритма ===

Cчитая базовой операцией операцию шифрования текста на одном раунде с использование дифференциальной характеристики с вероятностью <math>p</math>, на нахождение <math>b</math> бит раундового ключа <math>R-1</math> раунда шифрования потребуется около <math>(2с/p)(R+2^b)</math> операций шифрования, где <math>с</math> - некоторая небольшая константа. Так как основным параметром является вероятность <math>p</math>, от которой зависит числе пар текстов, данный алгоритм имеет линейную сложность.

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

Опишем [[глоссарий#Граф алгоритма|граф алгоритма]] как аналитически, так и в виде рисунка.

[[Файл:YeqAX.png|500px|thumb|center|Рисунок 1. Граф последовательного умножения плотной матрицы на вектор с отображением входных и выходных данных]]

Граф алгоритма умножения плотной матрицы на вектор состоит из одной группы вершин, расположенной в целочисленных узлах двумерной области, соответствующая ей операция <math>a+bc</math>.

Естественно введённые координаты области таковы:
* <math>i</math> — меняется в диапазоне от <math>1</math> до <math>m</math>, принимая все целочисленные значения;
* <math>j</math> — меняется в диапазоне от <math>1</math> до <math>n</math>, принимая все целочисленные значения.

Аргументы операции следующие:
*<math>a</math>:
** при <math>j = 1</math> константа <math>0.</math>;
** при <math>j > 1</math> — результат срабатывания операции, соответствующей вершине с координатами <math>i, j-1</math>;
*<math>b</math> — элемент ''входных данных'', а именно <math>a_{ij}</math>;
*<math>c</math> - элемент входных данных <math>x_{j}</math>;

Результат срабатывания операции является:
* при <math>j < n</math> - ''промежуточным данным'' алгоритма;
* при <math>j = n</math> - выходным данным.

Описанный граф можно посмотреть на рисунке, выполненном для случая <math>m = 4, n = 5</math>. Здесь вершины обозначены голубым цветом. Изображена подача только входных данных из вектора <math>x</math>, подача элементов матрицы <math>A</math>, идущая во все вершины, на рисунке не представлена.

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

Для алгоритма умножения квадратной матрицы на вектор порядка n в параллельном варианте требуется последовательно выполнить следующие ярусы:

* по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>n</math> операций).

Для умножения матрицы размером <math>m</math> строк на <math>n</math> столбцов на вектор порядка <math>n</math> в последовательном (наиболее быстром) варианте требуется:

* по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>m</math> операций).

При этом использование режима накопления требует совершения умножений и сложений в режиме двойной точности, а в параллельном варианте это означает, что практически все промежуточные вычисления для выполнения алгоритма в режиме накопления должны быть двойной точности. В отличие от последовательного варианта это означает некоторое увеличение требуемой памяти.

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

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

'''Входные данные''': алгоритм шифрования, константа <math>c</math>, вероятность характеристики <math>p</math>, число бит раундового ключа <math>b</math>, число раундов шифрования <math>R</math>, входная разница между парами текстов <math>deltafirst</math>, выходная разница между парами текстов <math>deltalast</math>

'''Объём входных данных''': Объем входных не изменяется, изменяются только сами входные данные.

'''Выходные данные''': Биты раундового ключа последнего раунда.

'''Объём выходных данных''': <math>b</math>.

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

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

=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
[[file:Масштабируемость перемножения матрицы и вектора производительность.png|thumb|center|700px|Рисунок 5. Параллельная реализация произведения матрицы на вектор Максимальная производительность. ]]
[[file:Масштабируемость перемножения матрицы и вектора эффективность.png|thumb|center|700px|Рисунок 6. Параллельная реализация произведения матрицы на вектор Максимальная эффективность. ]]
Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма:
* число процессоров [4 : 256]
* размерность матрицы [1024 : 51200]
Эффективность выполнения реализации алгоритма
* Минимальная эффективность 0,02%
* Максимальная эффективность 9,55%
Оценка масштабируемости
* По числу процессов: -0.01517 – при увеличении числа процессов эффективность убывает достаточно интенсивно на всей рассмотренной области изменений параметров запуска. Уменьшение эффективности на рассмотренной области работы параллельной программы звязано с увеличением числа пересылок с ростом числа процессов и как следствие ростом накладных расходов на организацию вычислений. Основной вклад в значение эффективности вносит область с малым числом процессов и малой задачей, там эффективность достигает максимума в 9,5%. Далее эффективность очень резко падает до уровня около 1% Присутствует область, на которой при увеличении числа процессов эффективность возрастает, но при дальнейшем росте продолжает снижаться. Это скорее всего объясняется декомпозицей данных, при которой наступает момент, когда размер матрицы позволяет блокам укладываться в КЭШ-память. Так же это подтверждает проявление этого явления, но со смещением по числу процессов, и при увеличении вычислительной сложности задачи.
* По размеру задачи: -0.0014 – при увеличении размера задачи эффективность в целом уменьшается по рассматриваемой области, хотя и менее интенсивно, чем при увеличении числа процессов. Снижение эффективности объясняется тем, что при росте вычислительной сложности существенно возрастают объемы передаваемых данных. При увеличении размера данных наступает момент резкого снижения эффективности с значений около 1% к долям процента и минимуму. С увеличением числа процессоров такой переход появляется на большем объеме данных. Это свидетельствует о том, что присутствует момент, когда данных слишком много и эффективность работы с ними становится значительно ниже, но чем больше имеется процессов, там позже наступает такой момент декомпозиции. Присутствует область возрастания эффективности, на всех рассмотренных размерах матрицы. Это объясняется тем, что при малом размере задачи данные хорошо укладываются в КЭШ память, что приводит к высокой эффективности работы приложения при малом размере задачи. При дальнейшем увеличении размера эффективность уменьшается при выходе за границы КЭШ-памяти.
* По двум направлениям: -0.0001546 – при рассмотрении увеличения, как вычислительной сложности, так и числа процессов по всей рассмотренной области значений уменьшается, интенсивность уменьшения эффективности не очень высока. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров составляет около 9% говорит о том, что уменьшение эффективности по всей области довольно равномерное, но интенсивно лишь в не очень больших участках по площади. На остальной области значений параметров изменения эффективности не столь значительны и находятся на приблизительно одном и том же уровне.

[http://git.algowiki-project.org/Teplov/Scalability/blob/master/matrix_vector_mult/mpi_mat_vect_time.c Реализация алгоритма на языке C]

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

== Литература ==
<references />

[[Категория:Статьи в работе]]
[[Категория:Матрично-векторные операции]]

[[En:Dense matrix-vector multiplication]]

Участник:Demiandr

2021-11-04T10:03:39Z

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

{{level-a}}

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

=== Общее описание алгоритма ===
Дифференциальный криптоанализ — метод криптоанализа симметричных блочных шифров (и других криптографических примитивов, в частности, хеш-функций и поточных шифров).
Дифференциальный криптоанализ основан на изучении преобразования разностей между шифруемыми значениями на различных раундах шифрования. В качестве разности, как правило, применяется операция побитового суммирования по модулю 2, хотя существуют атаки и с вычислением разности по модулю {\displaystyle 2^{32}}2^{32}. Является статистической атакой. Применим для взлома DES, FEAL и некоторых других шифров, как правило, разработанных ранее начала 90-х. Количество раундов современных шифров (AES, Camellia и др.) рассчитывалось с учётом обеспечения стойкости, в том числе и к дифференциальному криптоанализу.
Все существующие блочные алгоритмы шифрования являются итеративными алгоритмами, то есть при шифровании информация подвергается большому числу одних и тех же подряд идущих преобразований (раундов). В начале алгоритма шифрования из одного длинного секретного ключа при помощи алгоритма генерации раундовых ключей создаются мини-ключи, которые применяются на каждом раунде шифрования. Дифференциальный криптоанализ направлен на нахождение таких раундовых ключей, для последующего определения по ним основного секретного ключа криптосистемы, причем первым определяемым раундовым ключом является ключ последнего раунда шифрования.

=== Математическое описание алгоритма ===
Пусть <math>ΔX=({ΔX_1}{ΔX_2}{ΔX_3}...{ΔX_3})</math>
Задачей криптоаналитика является нахождение
Пусть <math>{p}</math> - вероя

=== Вычислительное ядро алгоритма ===

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

=== Макроструктура алгоритма ===

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

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

В данном пункте приведены
<source lang="c++">
double p = 0.000001;//вероятность найденной характеристики
int c = 2;//константа
int R = 12;//число раундов шифра
int b = 4;//число бит раундового ключа, которые можно определить найденной характеристикой
__uint64 deltafirst=(2^34);// найденная характеристика (разница между парой текстов)
__uint64 deltalast=1;(найденная разница между текстами на предпоследнем раунде_
__uint64 firsttext;//первый текст из пары
__uint64 secondtext;//второй текст из пары
int result[pow(2,b)]={};//массив возможных значений бит раундового ключа
for (__uint64 i=0; i<(c/p);i++)
{
firsttext=i;//генерация первого текста пары
secondtext=i^deltafirst;//генерация второго текста пары
for (int j=0; j<R;j++)
{
firsttext = cipher(firsttext);
secondtext = cipher(secondtext);
}
for (int k=0; k< pow(2,b);k++)
{
firsttext = decipher(firsttext,k)
secondtext = decipher(secondtext,k)
if (deltalast == firsttext ^ secondtext)
{
result[k]++
}
}
}
int max=0
for (int k=0; k< pow(2,b);k++)
{
if (result[k] > max) max=result[k]
}
</source>
=== Последовательная сложность алгоритма ===

Cчитая базовой операцией операцию шифрования текста на одном раунде с использование дифференциальной характеристики с вероятностью <math>p</math>, на нахождение <math>b</math> бит раундового ключа <math>R-1</math> раунда шифрования потребуется около <math>(2с/p)(R+2^b)</math> операций шифрования, где <math>с</math> - некоторая небольшая константа. Так как основным параметром является вероятность <math>p</math>, от которой зависит числе пар текстов, данный алгоритм имеет линейную сложность.

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

Опишем [[глоссарий#Граф алгоритма|граф алгоритма]] как аналитически, так и в виде рисунка.

[[Файл:YeqAX.png|500px|thumb|center|Рисунок 1. Граф последовательного умножения плотной матрицы на вектор с отображением входных и выходных данных]]

Граф алгоритма умножения плотной матрицы на вектор состоит из одной группы вершин, расположенной в целочисленных узлах двумерной области, соответствующая ей операция <math>a+bc</math>.

Естественно введённые координаты области таковы:
* <math>i</math> — меняется в диапазоне от <math>1</math> до <math>m</math>, принимая все целочисленные значения;
* <math>j</math> — меняется в диапазоне от <math>1</math> до <math>n</math>, принимая все целочисленные значения.

Аргументы операции следующие:
*<math>a</math>:
** при <math>j = 1</math> константа <math>0.</math>;
** при <math>j > 1</math> — результат срабатывания операции, соответствующей вершине с координатами <math>i, j-1</math>;
*<math>b</math> — элемент ''входных данных'', а именно <math>a_{ij}</math>;
*<math>c</math> - элемент входных данных <math>x_{j}</math>;

Результат срабатывания операции является:
* при <math>j < n</math> - ''промежуточным данным'' алгоритма;
* при <math>j = n</math> - выходным данным.

Описанный граф можно посмотреть на рисунке, выполненном для случая <math>m = 4, n = 5</math>. Здесь вершины обозначены голубым цветом. Изображена подача только входных данных из вектора <math>x</math>, подача элементов матрицы <math>A</math>, идущая во все вершины, на рисунке не представлена.

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

Для алгоритма умножения квадратной матрицы на вектор порядка n в параллельном варианте требуется последовательно выполнить следующие ярусы:

* по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>n</math> операций).

Для умножения матрицы размером <math>m</math> строк на <math>n</math> столбцов на вектор порядка <math>n</math> в последовательном (наиболее быстром) варианте требуется:

* по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>m</math> операций).

При этом использование режима накопления требует совершения умножений и сложений в режиме двойной точности, а в параллельном варианте это означает, что практически все промежуточные вычисления для выполнения алгоритма в режиме накопления должны быть двойной точности. В отличие от последовательного варианта это означает некоторое увеличение требуемой памяти.

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

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

'''Входные данные''': алгоритм шифрования, константа <math>c</math>, вероятность характеристики <math>p</math>, число бит раундового ключа <math>b</math>, число раундов шифрования <math>R</math>, входная разница между парами текстов <math>deltafirst</math>, выходная разница между парами текстов <math>deltalast</math>

'''Объём входных данных''': Объем входных не изменяется, изменяются только сами входные данные.

'''Выходные данные''': Биты раундового ключа последнего раунда.

'''Объём выходных данных''': <math>b</math>.

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

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

=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
[[file:Масштабируемость перемножения матрицы и вектора производительность.png|thumb|center|700px|Рисунок 5. Параллельная реализация произведения матрицы на вектор Максимальная производительность. ]]
[[file:Масштабируемость перемножения матрицы и вектора эффективность.png|thumb|center|700px|Рисунок 6. Параллельная реализация произведения матрицы на вектор Максимальная эффективность. ]]
Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма:
* число процессоров [4 : 256]
* размерность матрицы [1024 : 51200]
Эффективность выполнения реализации алгоритма
* Минимальная эффективность 0,02%
* Максимальная эффективность 9,55%
Оценка масштабируемости
* По числу процессов: -0.01517 – при увеличении числа процессов эффективность убывает достаточно интенсивно на всей рассмотренной области изменений параметров запуска. Уменьшение эффективности на рассмотренной области работы параллельной программы звязано с увеличением числа пересылок с ростом числа процессов и как следствие ростом накладных расходов на организацию вычислений. Основной вклад в значение эффективности вносит область с малым числом процессов и малой задачей, там эффективность достигает максимума в 9,5%. Далее эффективность очень резко падает до уровня около 1% Присутствует область, на которой при увеличении числа процессов эффективность возрастает, но при дальнейшем росте продолжает снижаться. Это скорее всего объясняется декомпозицей данных, при которой наступает момент, когда размер матрицы позволяет блокам укладываться в КЭШ-память. Так же это подтверждает проявление этого явления, но со смещением по числу процессов, и при увеличении вычислительной сложности задачи.
* По размеру задачи: -0.0014 – при увеличении размера задачи эффективность в целом уменьшается по рассматриваемой области, хотя и менее интенсивно, чем при увеличении числа процессов. Снижение эффективности объясняется тем, что при росте вычислительной сложности существенно возрастают объемы передаваемых данных. При увеличении размера данных наступает момент резкого снижения эффективности с значений около 1% к долям процента и минимуму. С увеличением числа процессоров такой переход появляется на большем объеме данных. Это свидетельствует о том, что присутствует момент, когда данных слишком много и эффективность работы с ними становится значительно ниже, но чем больше имеется процессов, там позже наступает такой момент декомпозиции. Присутствует область возрастания эффективности, на всех рассмотренных размерах матрицы. Это объясняется тем, что при малом размере задачи данные хорошо укладываются в КЭШ память, что приводит к высокой эффективности работы приложения при малом размере задачи. При дальнейшем увеличении размера эффективность уменьшается при выходе за границы КЭШ-памяти.
* По двум направлениям: -0.0001546 – при рассмотрении увеличения, как вычислительной сложности, так и числа процессов по всей рассмотренной области значений уменьшается, интенсивность уменьшения эффективности не очень высока. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров составляет около 9% говорит о том, что уменьшение эффективности по всей области довольно равномерное, но интенсивно лишь в не очень больших участках по площади. На остальной области значений параметров изменения эффективности не столь значительны и находятся на приблизительно одном и том же уровне.

[http://git.algowiki-project.org/Teplov/Scalability/blob/master/matrix_vector_mult/mpi_mat_vect_time.c Реализация алгоритма на языке C]

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

== Литература ==
<references />

[[Категория:Статьи в работе]]
[[Категория:Матрично-векторные операции]]

[[En:Dense matrix-vector multiplication]]

Участник:Demiandr

2021-11-04T10:03:03Z

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

{{level-a}}

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

=== Общее описание алгоритма ===
Дифференциальный криптоанализ — метод криптоанализа симметричных блочных шифров (и других криптографических примитивов, в частности, хеш-функций и поточных шифров).
Дифференциальный криптоанализ основан на изучении преобразования разностей между шифруемыми значениями на различных раундах шифрования. В качестве разности, как правило, применяется операция побитового суммирования по модулю 2, хотя существуют атаки и с вычислением разности по модулю {\displaystyle 2^{32}}2^{32}. Является статистической атакой. Применим для взлома DES, FEAL и некоторых других шифров, как правило, разработанных ранее начала 90-х. Количество раундов современных шифров (AES, Camellia и др.) рассчитывалось с учётом обеспечения стойкости, в том числе и к дифференциальному криптоанализу.
Все существующие блочные алгоритмы шифрования являются итеративными алгоритмами, то есть при шифровании информация подвергается большому числу одних и тех же подряд идущих преобразований (раундов). В начале алгоритма шифрования из одного длинного секретного ключа при помощи алгоритма генерации раундовых ключей создаются мини-ключи, которые применяются на каждом раунде шифрования. Дифференциальный криптоанализ направлен на нахождение таких раундовых ключей, для последующего определения по ним основного секретного ключа криптосистемы, причем первым определяемым раундовым ключом является ключ последнего раунда шифрования.

=== Математическое описание алгоритма ===
Пусть <math>ΔX=({ΔX_1}{ΔX_2}{ΔX_3}...{ΔX_3})</math>
Задачей криптоаналитика является нахождение
Пусть <math>{p}</math> - вероя

=== Вычислительное ядро алгоритма ===

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

=== Макроструктура алгоритма ===

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

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

В данном пункте приведены
<source lang="c++">
double p = 0.000001;//вероятность найденной характеристики
int c = 2;//константа
int R = 12;//число раундов шифра
int b = 4;//число бит раундового ключа, которые можно определить найденной характеристикой
__uint64 deltafirst=(2^34);// найденная характеристика (разница между парой текстов)
__uint64 deltalast=1;(найденная разница между текстами на предпоследнем раунде_
__uint64 firsttext;//первый текст из пары
__uint64 secondtext;//второй текст из пары
int result[pow(2,b)]={};//массив возможных значений бит раундового ключа
for (__uint64 i=0; i<(c/p);i++)
{
firsttext=i;//генерация первого текста пары
secondtext=i^deltafirst;//генерация второго текста пары
for (int j=0; j<R;j++)
{
firsttext = cipher(firsttext);
secondtext = cipher(secondtext);
}
for (int k=0; k< pow(2,b);k++)
{
firsttext = decipher(firsttext,k)
secondtext = decipher(secondtext,k)
if (deltalast == firsttext ^ secondtext)
{
result[k]++
}
}
}
int max=0
for (int k=0; k< pow(2,b);k++)
{
if (result[k] > max) max=result[k]
}
</source>
=== Последовательная сложность алгоритма ===

Cчитая базовой операцией операцию шифрования текста на одном раунде с использование дифференциальной характеристики с вероятностью <math>p</math>, на нахождение <math>b</math> бит раундового ключа <math>R-1</math> раунда шифрования потребуется около <math>(2с/p)(R+2^b)</math> операций шифрования, где <math>с</math> - некоторая небольшая константа. Так как основным параметром является вероятность <math>p</math>, от которой зависит числе пар текстов, данный алгоритм имеет линейную сложность.

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

Опишем [[глоссарий#Граф алгоритма|граф алгоритма]] как аналитически, так и в виде рисунка.

[[Файл:YeqAX.png|500px|thumb|center|Рисунок 1. Граф последовательного умножения плотной матрицы на вектор с отображением входных и выходных данных]]

Граф алгоритма умножения плотной матрицы на вектор состоит из одной группы вершин, расположенной в целочисленных узлах двумерной области, соответствующая ей операция <math>a+bc</math>.

Естественно введённые координаты области таковы:
* <math>i</math> — меняется в диапазоне от <math>1</math> до <math>m</math>, принимая все целочисленные значения;
* <math>j</math> — меняется в диапазоне от <math>1</math> до <math>n</math>, принимая все целочисленные значения.

Аргументы операции следующие:
*<math>a</math>:
** при <math>j = 1</math> константа <math>0.</math>;
** при <math>j > 1</math> — результат срабатывания операции, соответствующей вершине с координатами <math>i, j-1</math>;
*<math>b</math> — элемент ''входных данных'', а именно <math>a_{ij}</math>;
*<math>c</math> - элемент входных данных <math>x_{j}</math>;

Результат срабатывания операции является:
* при <math>j < n</math> - ''промежуточным данным'' алгоритма;
* при <math>j = n</math> - выходным данным.

Описанный граф можно посмотреть на рисунке, выполненном для случая <math>m = 4, n = 5</math>. Здесь вершины обозначены голубым цветом. Изображена подача только входных данных из вектора <math>x</math>, подача элементов матрицы <math>A</math>, идущая во все вершины, на рисунке не представлена.

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

Для алгоритма умножения квадратной матрицы на вектор порядка n в параллельном варианте требуется последовательно выполнить следующие ярусы:

* по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>n</math> операций).

Для умножения матрицы размером <math>m</math> строк на <math>n</math> столбцов на вектор порядка <math>n</math> в последовательном (наиболее быстром) варианте требуется:

* по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>m</math> операций).

При этом использование режима накопления требует совершения умножений и сложений в режиме двойной точности, а в параллельном варианте это означает, что практически все промежуточные вычисления для выполнения алгоритма в режиме накопления должны быть двойной точности. В отличие от последовательного варианта это означает некоторое увеличение требуемой памяти.

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

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

'''Входные данные''': алгоритм шифрования, константа <math>c</math>, вероятность характеристики <math>p</math>, число бит раундового ключа <math>b</math>, число раундов шифрования <math>R</math>, входная разница между парами текстов <math>deltafirst</math>, выходная разница между парами текстов <math>deltalast</math>

'''Объём входных данных''': Объем входных не изменяется, изменяются только сами входные данные.

'''Выходные данные''': Биты раундового ключа последнего раунда.

'''Объём выходных данных''': <math>b</math>.

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

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''линейным'' (отношение квадратической или билинейной к линейной).

При этом вычислительная мощность алгоритма умножения матрицы на вектор, как отношение числа операций к суммарному объему входных и выходных данных – всего лишь ''константа''.

При этом алгоритм умножения матрицы на вектор полностью детерминирован. Использование другого порядка выполнения ассоциативных операций в данной версии нами не рассматривается.

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

=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
[[file:Масштабируемость перемножения матрицы и вектора производительность.png|thumb|center|700px|Рисунок 5. Параллельная реализация произведения матрицы на вектор Максимальная производительность. ]]
[[file:Масштабируемость перемножения матрицы и вектора эффективность.png|thumb|center|700px|Рисунок 6. Параллельная реализация произведения матрицы на вектор Максимальная эффективность. ]]
Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма:
* число процессоров [4 : 256]
* размерность матрицы [1024 : 51200]
Эффективность выполнения реализации алгоритма
* Минимальная эффективность 0,02%
* Максимальная эффективность 9,55%
Оценка масштабируемости
* По числу процессов: -0.01517 – при увеличении числа процессов эффективность убывает достаточно интенсивно на всей рассмотренной области изменений параметров запуска. Уменьшение эффективности на рассмотренной области работы параллельной программы звязано с увеличением числа пересылок с ростом числа процессов и как следствие ростом накладных расходов на организацию вычислений. Основной вклад в значение эффективности вносит область с малым числом процессов и малой задачей, там эффективность достигает максимума в 9,5%. Далее эффективность очень резко падает до уровня около 1% Присутствует область, на которой при увеличении числа процессов эффективность возрастает, но при дальнейшем росте продолжает снижаться. Это скорее всего объясняется декомпозицей данных, при которой наступает момент, когда размер матрицы позволяет блокам укладываться в КЭШ-память. Так же это подтверждает проявление этого явления, но со смещением по числу процессов, и при увеличении вычислительной сложности задачи.
* По размеру задачи: -0.0014 – при увеличении размера задачи эффективность в целом уменьшается по рассматриваемой области, хотя и менее интенсивно, чем при увеличении числа процессов. Снижение эффективности объясняется тем, что при росте вычислительной сложности существенно возрастают объемы передаваемых данных. При увеличении размера данных наступает момент резкого снижения эффективности с значений около 1% к долям процента и минимуму. С увеличением числа процессоров такой переход появляется на большем объеме данных. Это свидетельствует о том, что присутствует момент, когда данных слишком много и эффективность работы с ними становится значительно ниже, но чем больше имеется процессов, там позже наступает такой момент декомпозиции. Присутствует область возрастания эффективности, на всех рассмотренных размерах матрицы. Это объясняется тем, что при малом размере задачи данные хорошо укладываются в КЭШ память, что приводит к высокой эффективности работы приложения при малом размере задачи. При дальнейшем увеличении размера эффективность уменьшается при выходе за границы КЭШ-памяти.
* По двум направлениям: -0.0001546 – при рассмотрении увеличения, как вычислительной сложности, так и числа процессов по всей рассмотренной области значений уменьшается, интенсивность уменьшения эффективности не очень высока. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров составляет около 9% говорит о том, что уменьшение эффективности по всей области довольно равномерное, но интенсивно лишь в не очень больших участках по площади. На остальной области значений параметров изменения эффективности не столь значительны и находятся на приблизительно одном и том же уровне.

[http://git.algowiki-project.org/Teplov/Scalability/blob/master/matrix_vector_mult/mpi_mat_vect_time.c Реализация алгоритма на языке C]

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

== Литература ==
<references />

[[Категория:Статьи в работе]]
[[Категория:Матрично-векторные операции]]

[[En:Dense matrix-vector multiplication]]

Участник:Demiandr

2021-11-04T10:01:04Z

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

{{level-a}}

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

=== Общее описание алгоритма ===
Дифференциальный криптоанализ — метод криптоанализа симметричных блочных шифров (и других криптографических примитивов, в частности, хеш-функций и поточных шифров).
Дифференциальный криптоанализ основан на изучении преобразования разностей между шифруемыми значениями на различных раундах шифрования. В качестве разности, как правило, применяется операция побитового суммирования по модулю 2, хотя существуют атаки и с вычислением разности по модулю {\displaystyle 2^{32}}2^{32}. Является статистической атакой. Применим для взлома DES, FEAL и некоторых других шифров, как правило, разработанных ранее начала 90-х. Количество раундов современных шифров (AES, Camellia и др.) рассчитывалось с учётом обеспечения стойкости, в том числе и к дифференциальному криптоанализу.
Все существующие блочные алгоритмы шифрования являются итеративными алгоритмами, то есть при шифровании информация подвергается большому числу одних и тех же подряд идущих преобразований (раундов). В начале алгоритма шифрования из одного длинного секретного ключа при помощи алгоритма генерации раундовых ключей создаются мини-ключи, которые применяются на каждом раунде шифрования. Дифференциальный криптоанализ направлен на нахождение таких раундовых ключей, для последующего определения по ним основного секретного ключа криптосистемы, причем первым определяемым раундовым ключом является ключ последнего раунда шифрования.

=== Математическое описание алгоритма ===
Пусть <math>ΔX=({ΔX_1}{ΔX_2}{ΔX_3}...{ΔX_3})</math>
Задачей криптоаналитика является нахождение
Пусть <math>{p}</math> - вероя

=== Вычислительное ядро алгоритма ===

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

=== Макроструктура алгоритма ===

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

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

В данном пункте приведены
<source lang="c++">
double p = 0.000001;//вероятность найденной характеристики
int c = 2;//константа
int R = 12;//число раундов шифра
int b = 4;//число бит раундового ключа, которые можно определить найденной характеристикой
__uint64 deltafirst=(2^34);// найденная характеристика (разница между парой текстов)
__uint64 deltalast=1;(найденная разница между текстами на предпоследнем раунде_
__uint64 firsttext;//первый текст из пары
__uint64 secondtext;//второй текст из пары
int result[pow(2,b)]={};//массив возможных значений бит раундового ключа
for (__uint64 i=0; i<(c/p);i++)
{
firsttext=i;//генерация первого текста пары
secondtext=i^deltafirst;//генерация второго текста пары
for (int j=0; j<R;j++)
{
firsttext = cipher(firsttext);
secondtext = cipher(secondtext);
}
for (int k=0; k< pow(2,b);k++)
{
firsttext = decipher(firsttext,k)
secondtext = decipher(secondtext,k)
if (deltalast == firsttext ^ secondtext)
{
result[k]++
}
}
}
int max=0
for (int k=0; k< pow(2,b);k++)
{
if (result[k] > max) max=result[k]
}
</source>
=== Последовательная сложность алгоритма ===

Cчитая базовой операцией операцию шифрования текста на одном раунде с использование дифференциальной характеристики с вероятностью <math>p</math>, на нахождение <math>b</math> бит раундового ключа <math>R-1</math> раунда шифрования потребуется около <math>(2с/p)(R+2^b)</math> операций шифрования, где <math>с</math> - некоторая небольшая константа. Так как основным параметром является вероятность <math>p</math>, от которой зависит числе пар текстов, данный алгоритм имеет линейную сложность.

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

Опишем [[глоссарий#Граф алгоритма|граф алгоритма]] как аналитически, так и в виде рисунка.

[[Файл:YeqAX.png|500px|thumb|center|Рисунок 1. Граф последовательного умножения плотной матрицы на вектор с отображением входных и выходных данных]]

Граф алгоритма умножения плотной матрицы на вектор состоит из одной группы вершин, расположенной в целочисленных узлах двумерной области, соответствующая ей операция <math>a+bc</math>.

Естественно введённые координаты области таковы:
* <math>i</math> — меняется в диапазоне от <math>1</math> до <math>m</math>, принимая все целочисленные значения;
* <math>j</math> — меняется в диапазоне от <math>1</math> до <math>n</math>, принимая все целочисленные значения.

Аргументы операции следующие:
*<math>a</math>:
** при <math>j = 1</math> константа <math>0.</math>;
** при <math>j > 1</math> — результат срабатывания операции, соответствующей вершине с координатами <math>i, j-1</math>;
*<math>b</math> — элемент ''входных данных'', а именно <math>a_{ij}</math>;
*<math>c</math> - элемент входных данных <math>x_{j}</math>;

Результат срабатывания операции является:
* при <math>j < n</math> - ''промежуточным данным'' алгоритма;
* при <math>j = n</math> - выходным данным.

Описанный граф можно посмотреть на рисунке, выполненном для случая <math>m = 4, n = 5</math>. Здесь вершины обозначены голубым цветом. Изображена подача только входных данных из вектора <math>x</math>, подача элементов матрицы <math>A</math>, идущая во все вершины, на рисунке не представлена.

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

Для алгоритма умножения квадратной матрицы на вектор порядка n в параллельном варианте требуется последовательно выполнить следующие ярусы:

* по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>n</math> операций).

Для умножения матрицы размером <math>m</math> строк на <math>n</math> столбцов на вектор порядка <math>n</math> в последовательном (наиболее быстром) варианте требуется:

* по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>m</math> операций).

При этом использование режима накопления требует совершения умножений и сложений в режиме двойной точности, а в параллельном варианте это означает, что практически все промежуточные вычисления для выполнения алгоритма в режиме накопления должны быть двойной точности. В отличие от последовательного варианта это означает некоторое увеличение требуемой памяти.

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

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

'''Входные данные''': алгоритм шифрования, константа <math>c</math>, вероятность характеристики <math>p</math>, число бит раундового ключа <math>b</math>, число раундов шифрования <math>R</math>, входная разница между парами текстов deltafirst</math>, выходная разница между парами текстов deltalast</math>

'''Объём входных данных''': Объем входных не изменяется, изменяются только сами входные данные.

'''Выходные данные''': Биты раундового ключа последнего раунда.

'''Объём выходных данных''': <math>b</math>.

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

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''линейным'' (отношение квадратической или билинейной к линейной).

При этом вычислительная мощность алгоритма умножения матрицы на вектор, как отношение числа операций к суммарному объему входных и выходных данных – всего лишь ''константа''.

При этом алгоритм умножения матрицы на вектор полностью детерминирован. Использование другого порядка выполнения ассоциативных операций в данной версии нами не рассматривается.

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

=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
[[file:Масштабируемость перемножения матрицы и вектора производительность.png|thumb|center|700px|Рисунок 5. Параллельная реализация произведения матрицы на вектор Максимальная производительность. ]]
[[file:Масштабируемость перемножения матрицы и вектора эффективность.png|thumb|center|700px|Рисунок 6. Параллельная реализация произведения матрицы на вектор Максимальная эффективность. ]]
Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма:
* число процессоров [4 : 256]
* размерность матрицы [1024 : 51200]
Эффективность выполнения реализации алгоритма
* Минимальная эффективность 0,02%
* Максимальная эффективность 9,55%
Оценка масштабируемости
* По числу процессов: -0.01517 – при увеличении числа процессов эффективность убывает достаточно интенсивно на всей рассмотренной области изменений параметров запуска. Уменьшение эффективности на рассмотренной области работы параллельной программы звязано с увеличением числа пересылок с ростом числа процессов и как следствие ростом накладных расходов на организацию вычислений. Основной вклад в значение эффективности вносит область с малым числом процессов и малой задачей, там эффективность достигает максимума в 9,5%. Далее эффективность очень резко падает до уровня около 1% Присутствует область, на которой при увеличении числа процессов эффективность возрастает, но при дальнейшем росте продолжает снижаться. Это скорее всего объясняется декомпозицей данных, при которой наступает момент, когда размер матрицы позволяет блокам укладываться в КЭШ-память. Так же это подтверждает проявление этого явления, но со смещением по числу процессов, и при увеличении вычислительной сложности задачи.
* По размеру задачи: -0.0014 – при увеличении размера задачи эффективность в целом уменьшается по рассматриваемой области, хотя и менее интенсивно, чем при увеличении числа процессов. Снижение эффективности объясняется тем, что при росте вычислительной сложности существенно возрастают объемы передаваемых данных. При увеличении размера данных наступает момент резкого снижения эффективности с значений около 1% к долям процента и минимуму. С увеличением числа процессоров такой переход появляется на большем объеме данных. Это свидетельствует о том, что присутствует момент, когда данных слишком много и эффективность работы с ними становится значительно ниже, но чем больше имеется процессов, там позже наступает такой момент декомпозиции. Присутствует область возрастания эффективности, на всех рассмотренных размерах матрицы. Это объясняется тем, что при малом размере задачи данные хорошо укладываются в КЭШ память, что приводит к высокой эффективности работы приложения при малом размере задачи. При дальнейшем увеличении размера эффективность уменьшается при выходе за границы КЭШ-памяти.
* По двум направлениям: -0.0001546 – при рассмотрении увеличения, как вычислительной сложности, так и числа процессов по всей рассмотренной области значений уменьшается, интенсивность уменьшения эффективности не очень высока. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров составляет около 9% говорит о том, что уменьшение эффективности по всей области довольно равномерное, но интенсивно лишь в не очень больших участках по площади. На остальной области значений параметров изменения эффективности не столь значительны и находятся на приблизительно одном и том же уровне.

[http://git.algowiki-project.org/Teplov/Scalability/blob/master/matrix_vector_mult/mpi_mat_vect_time.c Реализация алгоритма на языке C]

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

== Литература ==
<references />

[[Категория:Статьи в работе]]
[[Категория:Матрично-векторные операции]]

[[En:Dense matrix-vector multiplication]]

Участник:Demiandr

2021-11-04T09:50:34Z

Demiandr: /* Программная реализация алгоритма */

{{level-a}}

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

=== Общее описание алгоритма ===
Дифференциальный криптоанализ — метод криптоанализа симметричных блочных шифров (и других криптографических примитивов, в частности, хеш-функций и поточных шифров).
Дифференциальный криптоанализ основан на изучении преобразования разностей между шифруемыми значениями на различных раундах шифрования. В качестве разности, как правило, применяется операция побитового суммирования по модулю 2, хотя существуют атаки и с вычислением разности по модулю {\displaystyle 2^{32}}2^{32}. Является статистической атакой. Применим для взлома DES, FEAL и некоторых других шифров, как правило, разработанных ранее начала 90-х. Количество раундов современных шифров (AES, Camellia и др.) рассчитывалось с учётом обеспечения стойкости, в том числе и к дифференциальному криптоанализу.
Все существующие блочные алгоритмы шифрования являются итеративными алгоритмами, то есть при шифровании информация подвергается большому числу одних и тех же подряд идущих преобразований (раундов). В начале алгоритма шифрования из одного длинного секретного ключа при помощи алгоритма генерации раундовых ключей создаются мини-ключи, которые применяются на каждом раунде шифрования. Дифференциальный криптоанализ направлен на нахождение таких раундовых ключей, для последующего определения по ним основного секретного ключа криптосистемы, причем первым определяемым раундовым ключом является ключ последнего раунда шифрования.

=== Математическое описание алгоритма ===
Пусть <math>ΔX=({ΔX_1}{ΔX_2}{ΔX_3}...{ΔX_3})</math>
Задачей криптоаналитика является нахождение
Пусть <math>{p}</math> - вероя

=== Вычислительное ядро алгоритма ===

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

=== Макроструктура алгоритма ===

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

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

В данном пункте приведены
<source lang="c++">
double p = 0.000001;//вероятность найденной характеристики
int c = 2;//константа
int R = 12;//число раундов шифра
int b = 4;//число бит раундового ключа, которые можно определить найденной характеристикой
__uint64 deltafirst=(2^34);// найденная характеристика (разница между парой текстов)
__uint64 deltalast=1;(найденная разница между текстами на предпоследнем раунде_
__uint64 firsttext;//первый текст из пары
__uint64 secondtext;//второй текст из пары
int result[pow(2,b)]={};//массив возможных значений бит раундового ключа
for (__uint64 i=0; i<(c/p);i++)
{
firsttext=i;//генерация первого текста пары
secondtext=i^deltafirst;//генерация второго текста пары
for (int j=0; j<R;j++)
{
firsttext = cipher(firsttext);
secondtext = cipher(secondtext);
}
for (int k=0; k< pow(2,b);k++)
{
firsttext = decipher(firsttext,k)
secondtext = decipher(secondtext,k)
if (deltalast == firsttext ^ secondtext)
{
result[k]++
}
}
}
int max=0
for (int k=0; k< pow(2,b);k++)
{
if (result[k] > max) max=result[k]
}
</source>
=== Последовательная сложность алгоритма ===

Cчитая базовой операцией операцию шифрования текста на одном раунде с использование дифференциальной характеристики с вероятностью <math>p</math>, на нахождение <math>b</math> бит раундового ключа <math>R-1</math> раунда шифрования потребуется около <math>(2с/p)(R+2^b)</math> операций шифрования, где <math>с</math> - некоторая небольшая константа. Так как основным параметром является вероятность <math>p</math>, от которой зависит числе пар текстов, данный алгоритм имеет линейную сложность.

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

Опишем [[глоссарий#Граф алгоритма|граф алгоритма]] как аналитически, так и в виде рисунка.

[[Файл:YeqAX.png|500px|thumb|center|Рисунок 1. Граф последовательного умножения плотной матрицы на вектор с отображением входных и выходных данных]]

Граф алгоритма умножения плотной матрицы на вектор состоит из одной группы вершин, расположенной в целочисленных узлах двумерной области, соответствующая ей операция <math>a+bc</math>.

Естественно введённые координаты области таковы:
* <math>i</math> — меняется в диапазоне от <math>1</math> до <math>m</math>, принимая все целочисленные значения;
* <math>j</math> — меняется в диапазоне от <math>1</math> до <math>n</math>, принимая все целочисленные значения.

Аргументы операции следующие:
*<math>a</math>:
** при <math>j = 1</math> константа <math>0.</math>;
** при <math>j > 1</math> — результат срабатывания операции, соответствующей вершине с координатами <math>i, j-1</math>;
*<math>b</math> — элемент ''входных данных'', а именно <math>a_{ij}</math>;
*<math>c</math> - элемент входных данных <math>x_{j}</math>;

Результат срабатывания операции является:
* при <math>j < n</math> - ''промежуточным данным'' алгоритма;
* при <math>j = n</math> - выходным данным.

Описанный граф можно посмотреть на рисунке, выполненном для случая <math>m = 4, n = 5</math>. Здесь вершины обозначены голубым цветом. Изображена подача только входных данных из вектора <math>x</math>, подача элементов матрицы <math>A</math>, идущая во все вершины, на рисунке не представлена.

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

Для алгоритма умножения квадратной матрицы на вектор порядка n в параллельном варианте требуется последовательно выполнить следующие ярусы:

* по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>n</math> операций).

Для умножения матрицы размером <math>m</math> строк на <math>n</math> столбцов на вектор порядка <math>n</math> в последовательном (наиболее быстром) варианте требуется:

* по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>m</math> операций).

При этом использование режима накопления требует совершения умножений и сложений в режиме двойной точности, а в параллельном варианте это означает, что практически все промежуточные вычисления для выполнения алгоритма в режиме накопления должны быть двойной точности. В отличие от последовательного варианта это означает некоторое увеличение требуемой памяти.

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

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

'''Входные данные''': матрица <math>A</math> (элементы <math>a_{ij}</math>), вектор <math>x</math> (элементы <math>x_{i}</math>).

'''Объём входных данных''': <math>mn+n</math> .

'''Выходные данные''': вектор <math>y</math> (элементы <math>y_{i}</math>).

'''Объём выходных данных''': <math>m</math>.

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

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''линейным'' (отношение квадратической или билинейной к линейной).

При этом вычислительная мощность алгоритма умножения матрицы на вектор, как отношение числа операций к суммарному объему входных и выходных данных – всего лишь ''константа''.

При этом алгоритм умножения матрицы на вектор полностью детерминирован. Использование другого порядка выполнения ассоциативных операций в данной версии нами не рассматривается.

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

=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
[[file:Масштабируемость перемножения матрицы и вектора производительность.png|thumb|center|700px|Рисунок 5. Параллельная реализация произведения матрицы на вектор Максимальная производительность. ]]
[[file:Масштабируемость перемножения матрицы и вектора эффективность.png|thumb|center|700px|Рисунок 6. Параллельная реализация произведения матрицы на вектор Максимальная эффективность. ]]
Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма:
* число процессоров [4 : 256]
* размерность матрицы [1024 : 51200]
Эффективность выполнения реализации алгоритма
* Минимальная эффективность 0,02%
* Максимальная эффективность 9,55%
Оценка масштабируемости
* По числу процессов: -0.01517 – при увеличении числа процессов эффективность убывает достаточно интенсивно на всей рассмотренной области изменений параметров запуска. Уменьшение эффективности на рассмотренной области работы параллельной программы звязано с увеличением числа пересылок с ростом числа процессов и как следствие ростом накладных расходов на организацию вычислений. Основной вклад в значение эффективности вносит область с малым числом процессов и малой задачей, там эффективность достигает максимума в 9,5%. Далее эффективность очень резко падает до уровня около 1% Присутствует область, на которой при увеличении числа процессов эффективность возрастает, но при дальнейшем росте продолжает снижаться. Это скорее всего объясняется декомпозицей данных, при которой наступает момент, когда размер матрицы позволяет блокам укладываться в КЭШ-память. Так же это подтверждает проявление этого явления, но со смещением по числу процессов, и при увеличении вычислительной сложности задачи.
* По размеру задачи: -0.0014 – при увеличении размера задачи эффективность в целом уменьшается по рассматриваемой области, хотя и менее интенсивно, чем при увеличении числа процессов. Снижение эффективности объясняется тем, что при росте вычислительной сложности существенно возрастают объемы передаваемых данных. При увеличении размера данных наступает момент резкого снижения эффективности с значений около 1% к долям процента и минимуму. С увеличением числа процессоров такой переход появляется на большем объеме данных. Это свидетельствует о том, что присутствует момент, когда данных слишком много и эффективность работы с ними становится значительно ниже, но чем больше имеется процессов, там позже наступает такой момент декомпозиции. Присутствует область возрастания эффективности, на всех рассмотренных размерах матрицы. Это объясняется тем, что при малом размере задачи данные хорошо укладываются в КЭШ память, что приводит к высокой эффективности работы приложения при малом размере задачи. При дальнейшем увеличении размера эффективность уменьшается при выходе за границы КЭШ-памяти.
* По двум направлениям: -0.0001546 – при рассмотрении увеличения, как вычислительной сложности, так и числа процессов по всей рассмотренной области значений уменьшается, интенсивность уменьшения эффективности не очень высока. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров составляет около 9% говорит о том, что уменьшение эффективности по всей области довольно равномерное, но интенсивно лишь в не очень больших участках по площади. На остальной области значений параметров изменения эффективности не столь значительны и находятся на приблизительно одном и том же уровне.

[http://git.algowiki-project.org/Teplov/Scalability/blob/master/matrix_vector_mult/mpi_mat_vect_time.c Реализация алгоритма на языке C]

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

== Литература ==
<references />

[[Категория:Статьи в работе]]
[[Категория:Матрично-векторные операции]]

[[En:Dense matrix-vector multiplication]]

Участник:Demiandr

2021-11-04T09:42:19Z

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

{{level-a}}

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

=== Общее описание алгоритма ===
Дифференциальный криптоанализ — метод криптоанализа симметричных блочных шифров (и других криптографических примитивов, в частности, хеш-функций и поточных шифров).
Дифференциальный криптоанализ основан на изучении преобразования разностей между шифруемыми значениями на различных раундах шифрования. В качестве разности, как правило, применяется операция побитового суммирования по модулю 2, хотя существуют атаки и с вычислением разности по модулю {\displaystyle 2^{32}}2^{32}. Является статистической атакой. Применим для взлома DES, FEAL и некоторых других шифров, как правило, разработанных ранее начала 90-х. Количество раундов современных шифров (AES, Camellia и др.) рассчитывалось с учётом обеспечения стойкости, в том числе и к дифференциальному криптоанализу.
Все существующие блочные алгоритмы шифрования являются итеративными алгоритмами, то есть при шифровании информация подвергается большому числу одних и тех же подряд идущих преобразований (раундов). В начале алгоритма шифрования из одного длинного секретного ключа при помощи алгоритма генерации раундовых ключей создаются мини-ключи, которые применяются на каждом раунде шифрования. Дифференциальный криптоанализ направлен на нахождение таких раундовых ключей, для последующего определения по ним основного секретного ключа криптосистемы, причем первым определяемым раундовым ключом является ключ последнего раунда шифрования.

=== Математическое описание алгоритма ===
Пусть <math>ΔX=({ΔX_1}{ΔX_2}{ΔX_3}...{ΔX_3})</math>
Задачей криптоаналитика является нахождение
Пусть <math>{p}</math> - вероя

=== Вычислительное ядро алгоритма ===

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

=== Макроструктура алгоритма ===

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

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

В данном пункте приведены
<source lang="c++">
double p = 0.000001;//вероятность найденной характеристики
int c = 2;//константа
int R = 12;//число раундов шифра
int b = 4;//число бит раундового ключа, которые можно определить найденной характеристикой
__uint64 deltafirst=(2^34);// найденная характеристика (разница между парой текстов)
__uint64 deltalast=1;(найденная разница между текстами на предпоследнем раунде_
__uint64 firsttext;//первый текст из пары
__uint64 secondtext;//второй текст из пары
int result[pow(2,b)]={};//массив возможных значений бит раундового ключа
for (__uint64 i=0; i<(c/p);i++)
{
firsttext=i;//генерация первого текста пары
secondtext=i^deltafirst;//генерация второго текста пары
for (int j=0; j<R;j++)
{
firsttext = cipher(firsttext);
secondtext = cipher(secondtext);
}
for (int k=0; k< pow(2,b);k++)
{
firsttext = decipher(firsttext,k)
secondtext = decipher(secondtext,k)
if (deltalast == firsttext ^ secondtext)
{
result[k]++
}
}
}
int max=0
for (int k=0; k< pow(2,b);k++)
{
if (result[k] > max) max=result[k]
}
</source>
=== Последовательная сложность алгоритма ===

Cчитая базовой операцией операцию шифрования текста на одном раунде с использование дифференциальной характеристики с вероятностью <math>p</math>, на нахождение <math>b</math> бит раундового ключа <math>R-1</math> раунда шифрования потребуется около <math>(2с/p)(R+2^b)</math> операций шифрования, где <math>с</math> - некоторая небольшая константа. Так как основным параметром является вероятность <math>p</math>, от которой зависит числе пар текстов, данный алгоритм имеет линейную сложность.

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

Опишем [[глоссарий#Граф алгоритма|граф алгоритма]] как аналитически, так и в виде рисунка.

[[Файл:YeqAX.png|500px|thumb|center|Рисунок 1. Граф последовательного умножения плотной матрицы на вектор с отображением входных и выходных данных]]

Граф алгоритма умножения плотной матрицы на вектор состоит из одной группы вершин, расположенной в целочисленных узлах двумерной области, соответствующая ей операция <math>a+bc</math>.

Естественно введённые координаты области таковы:
* <math>i</math> — меняется в диапазоне от <math>1</math> до <math>m</math>, принимая все целочисленные значения;
* <math>j</math> — меняется в диапазоне от <math>1</math> до <math>n</math>, принимая все целочисленные значения.

Аргументы операции следующие:
*<math>a</math>:
** при <math>j = 1</math> константа <math>0.</math>;
** при <math>j > 1</math> — результат срабатывания операции, соответствующей вершине с координатами <math>i, j-1</math>;
*<math>b</math> — элемент ''входных данных'', а именно <math>a_{ij}</math>;
*<math>c</math> - элемент входных данных <math>x_{j}</math>;

Результат срабатывания операции является:
* при <math>j < n</math> - ''промежуточным данным'' алгоритма;
* при <math>j = n</math> - выходным данным.

Описанный граф можно посмотреть на рисунке, выполненном для случая <math>m = 4, n = 5</math>. Здесь вершины обозначены голубым цветом. Изображена подача только входных данных из вектора <math>x</math>, подача элементов матрицы <math>A</math>, идущая во все вершины, на рисунке не представлена.

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

Для алгоритма умножения квадратной матрицы на вектор порядка n в параллельном варианте требуется последовательно выполнить следующие ярусы:

* по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>n</math> операций).

Для умножения матрицы размером <math>m</math> строк на <math>n</math> столбцов на вектор порядка <math>n</math> в последовательном (наиболее быстром) варианте требуется:

* по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>m</math> операций).

При этом использование режима накопления требует совершения умножений и сложений в режиме двойной точности, а в параллельном варианте это означает, что практически все промежуточные вычисления для выполнения алгоритма в режиме накопления должны быть двойной точности. В отличие от последовательного варианта это означает некоторое увеличение требуемой памяти.

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

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

'''Входные данные''': матрица <math>A</math> (элементы <math>a_{ij}</math>), вектор <math>x</math> (элементы <math>x_{i}</math>).

'''Объём входных данных''': <math>mn+n</math> .

'''Выходные данные''': вектор <math>y</math> (элементы <math>y_{i}</math>).

'''Объём выходных данных''': <math>m</math>.

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

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''линейным'' (отношение квадратической или билинейной к линейной).

При этом вычислительная мощность алгоритма умножения матрицы на вектор, как отношение числа операций к суммарному объему входных и выходных данных – всего лишь ''константа''.

При этом алгоритм умножения матрицы на вектор полностью детерминирован. Использование другого порядка выполнения ассоциативных операций в данной версии нами не рассматривается.

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

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

В простейшем варианте алгоритм умножения матрицы на вектор на Фортране можно записать так:

<source lang="fortran">

DO I = 1, M
S = 0.
DO J = 1, N
S = S + DPROD(A(I,J), X(J))
END DO
Y(I) = S
END DO
</source>
При этом для реализации режима накопления переменная <math>S</math> должна быть двойной точности.

=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====

[[file:mv mult 1.PNG|thumb|center|700px|Рисунок 2. Умножение плотной матрицы на вектор. Общий профиль обращений в память]]

На рис.2 представлен профиль обращений в память для реализации умножения плотной матрицы на вектор. В данном алгоритме задействовано три массива. Выделенный зеленым фрагмент 1 образован обращениями к результирующему вектору; фрагмент 2 – обращениями к исходному вектору; остальные обращения (фрагмент 3) выполняются к матрице, на которую умножается исходный вектор.

Если посмотреть на исходный код, становится понятным, что каждый фрагмент устроен очень просто:
<source lang="C">
for(int i = 0; i < size; i++)
for(int j = 0; j < size; j++)
vec_out[i] += matrix[i][j] * vec_in[j];
</source>

Видно, что фрагмент 1 (обращения к массиву vec_out) состоит из последовательного перебора всех элементов вектора, только к каждому элементу происходит подряд size обращений. Во фрагменте 2 (массив vec_in) выполняется обычный последовательный перебор, который затем повторяется size раз. Фрагмент 3 также представляет собой последовательный перебор всех элементов матрицы, который выполняется только один раз.

Самой высокой локальностью обладает фрагмент 1 из-за повторяющихся подряд обращений к одним и тем же элементам. Однако фрагмент 2 также обладает высокой как пространственной, так и временной локальностью, поскольку число повторных проходов достаточно велико. Фрагмент 3, как и остальные, характеризуется высокой пространственной локальностью (из-за последовательного перебора), однако очень низкой временной локальностью – повторные обращения в нем просто отсутствуют.

===== Количественная оценка локальности =====

Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен [http://git.algowiki-project.org/Voevodin/locality/blob/master/benchmarks/d_matrix_vect_mult/d_matrix_vect_mult.h здесь] (функция Kernel). Условия запуска описаны [http://git.algowiki-project.org/Voevodin/locality/blob/master/README.md здесь].

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

На рис.3 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что производительность данной программы очень высока, даже немного выше, чем производительность теста Linpack. Одна из основных причин этому – очень высокая локальность обращений к векторам.

[[file:mv mult daps ru.PNG|thumb|center|700px|Рисунок 3. Сравнение значений оценки daps]]

Вторая характеристика – cvg – предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать, тем лучше локальность.

На рис.4 приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Можно увидеть, что, согласно данной оценке, локальность реализации умножения матрицы на вектор высока, хотя и не среди первых значений. Однако можно заметить, что полученное значение лишь совсем немного ниже оценки cvg для, например, реализации метода Гаусса или лучших вариантов перемножения матрицы.

[[file:mv mult cvg.PNG|thumb|center|700px|Рисунок 4. Сравнение значений оценки cvg]]

=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
[[file:Масштабируемость перемножения матрицы и вектора производительность.png|thumb|center|700px|Рисунок 5. Параллельная реализация произведения матрицы на вектор Максимальная производительность. ]]
[[file:Масштабируемость перемножения матрицы и вектора эффективность.png|thumb|center|700px|Рисунок 6. Параллельная реализация произведения матрицы на вектор Максимальная эффективность. ]]
Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма:
* число процессоров [4 : 256]
* размерность матрицы [1024 : 51200]
Эффективность выполнения реализации алгоритма
* Минимальная эффективность 0,02%
* Максимальная эффективность 9,55%
Оценка масштабируемости
* По числу процессов: -0.01517 – при увеличении числа процессов эффективность убывает достаточно интенсивно на всей рассмотренной области изменений параметров запуска. Уменьшение эффективности на рассмотренной области работы параллельной программы звязано с увеличением числа пересылок с ростом числа процессов и как следствие ростом накладных расходов на организацию вычислений. Основной вклад в значение эффективности вносит область с малым числом процессов и малой задачей, там эффективность достигает максимума в 9,5%. Далее эффективность очень резко падает до уровня около 1% Присутствует область, на которой при увеличении числа процессов эффективность возрастает, но при дальнейшем росте продолжает снижаться. Это скорее всего объясняется декомпозицей данных, при которой наступает момент, когда размер матрицы позволяет блокам укладываться в КЭШ-память. Так же это подтверждает проявление этого явления, но со смещением по числу процессов, и при увеличении вычислительной сложности задачи.
* По размеру задачи: -0.0014 – при увеличении размера задачи эффективность в целом уменьшается по рассматриваемой области, хотя и менее интенсивно, чем при увеличении числа процессов. Снижение эффективности объясняется тем, что при росте вычислительной сложности существенно возрастают объемы передаваемых данных. При увеличении размера данных наступает момент резкого снижения эффективности с значений около 1% к долям процента и минимуму. С увеличением числа процессоров такой переход появляется на большем объеме данных. Это свидетельствует о том, что присутствует момент, когда данных слишком много и эффективность работы с ними становится значительно ниже, но чем больше имеется процессов, там позже наступает такой момент декомпозиции. Присутствует область возрастания эффективности, на всех рассмотренных размерах матрицы. Это объясняется тем, что при малом размере задачи данные хорошо укладываются в КЭШ память, что приводит к высокой эффективности работы приложения при малом размере задачи. При дальнейшем увеличении размера эффективность уменьшается при выходе за границы КЭШ-памяти.
* По двум направлениям: -0.0001546 – при рассмотрении увеличения, как вычислительной сложности, так и числа процессов по всей рассмотренной области значений уменьшается, интенсивность уменьшения эффективности не очень высока. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров составляет около 9% говорит о том, что уменьшение эффективности по всей области довольно равномерное, но интенсивно лишь в не очень больших участках по площади. На остальной области значений параметров изменения эффективности не столь значительны и находятся на приблизительно одном и том же уровне.

[http://git.algowiki-project.org/Teplov/Scalability/blob/master/matrix_vector_mult/mpi_mat_vect_time.c Реализация алгоритма на языке C]

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

== Литература ==
<references />

[[Категория:Статьи в работе]]
[[Категория:Матрично-векторные операции]]

[[En:Dense matrix-vector multiplication]]

Участник:Demiandr

2021-11-04T09:40:32Z

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

{{level-a}}

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

=== Общее описание алгоритма ===
Дифференциальный криптоанализ — метод криптоанализа симметричных блочных шифров (и других криптографических примитивов, в частности, хеш-функций и поточных шифров).
Дифференциальный криптоанализ основан на изучении преобразования разностей между шифруемыми значениями на различных раундах шифрования. В качестве разности, как правило, применяется операция побитового суммирования по модулю 2, хотя существуют атаки и с вычислением разности по модулю {\displaystyle 2^{32}}2^{32}. Является статистической атакой. Применим для взлома DES, FEAL и некоторых других шифров, как правило, разработанных ранее начала 90-х. Количество раундов современных шифров (AES, Camellia и др.) рассчитывалось с учётом обеспечения стойкости, в том числе и к дифференциальному криптоанализу.
Все существующие блочные алгоритмы шифрования являются итеративными алгоритмами, то есть при шифровании информация подвергается большому числу одних и тех же подряд идущих преобразований (раундов). В начале алгоритма шифрования из одного длинного секретного ключа при помощи алгоритма генерации раундовых ключей создаются мини-ключи, которые применяются на каждом раунде шифрования. Дифференциальный криптоанализ направлен на нахождение таких раундовых ключей, для последующего определения по ним основного секретного ключа криптосистемы, причем первым определяемым раундовым ключом является ключ последнего раунда шифрования.

=== Математическое описание алгоритма ===
Пусть <math>ΔX=({ΔX_1}{ΔX_2}{ΔX_3}...{ΔX_3})</math>
Задачей криптоаналитика является нахождение
Пусть <math>{p}</math> - вероя

=== Вычислительное ядро алгоритма ===

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

=== Макроструктура алгоритма ===

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

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

В данном пункте приведены
<source lang="c++">
double p = 0.000001;//вероятность найденной характеристики
int c = 2;//константа
int R = 12;//число раундов шифра
int b = 4;//число бит раундового ключа, которые можно определить найденной характеристикой
__uint64 deltafirst=(2^34);// найденная характеристика (разница между парой текстов)
__uint64 deltalast=1;(найденная разница между текстами на предпоследнем раунде_
__uint64 firsttext;//первый текст из пары
__uint64 secondtext;//второй текст из пары
int result[pow(2,b)]={};//массив возможных значений бит раундового ключа
for (__uint64 i=0; i<(c/p);i++)
{
firsttext=i;//генерация первого текста пары
secondtext=i^deltafirst;//генерация второго текста пары
for (int j=0; j<R;j++)
{
firsttext = cipher(firsttext);
secondtext = cipher(secondtext);
}
for (int k=0; k< pow(2,b);k++)
{
firsttext = decipher(firsttext,k)
secondtext = decipher(secondtext,k)
if (deltalast == firsttext ^ secondtext)
{
result[k]++
}
}
}
int max=0
for (int k=0; k< pow(2,b);k++)
{
if (result[k] > max) max=result[k]
}

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

Cчитая базовой операцией операцию шифрования текста на одном раунде с использование дифференциальной характеристики с вероятностью <math>p</math>, на нахождение <math>b</math> бит раундового ключа <math>R-1</math> раунда шифрования потребуется около <math>(2с/p)(R+2^b)</math> операций шифрования, где <math>с</math> - некоторая небольшая константа. Так как основным параметром является вероятность <math>p</math>, от которой зависит числе пар текстов, данный алгоритм имеет линейную сложность.

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

Опишем [[глоссарий#Граф алгоритма|граф алгоритма]] как аналитически, так и в виде рисунка.

[[Файл:YeqAX.png|500px|thumb|center|Рисунок 1. Граф последовательного умножения плотной матрицы на вектор с отображением входных и выходных данных]]

Граф алгоритма умножения плотной матрицы на вектор состоит из одной группы вершин, расположенной в целочисленных узлах двумерной области, соответствующая ей операция <math>a+bc</math>.

Естественно введённые координаты области таковы:
* <math>i</math> — меняется в диапазоне от <math>1</math> до <math>m</math>, принимая все целочисленные значения;
* <math>j</math> — меняется в диапазоне от <math>1</math> до <math>n</math>, принимая все целочисленные значения.

Аргументы операции следующие:
*<math>a</math>:
** при <math>j = 1</math> константа <math>0.</math>;
** при <math>j > 1</math> — результат срабатывания операции, соответствующей вершине с координатами <math>i, j-1</math>;
*<math>b</math> — элемент ''входных данных'', а именно <math>a_{ij}</math>;
*<math>c</math> - элемент входных данных <math>x_{j}</math>;

Результат срабатывания операции является:
* при <math>j < n</math> - ''промежуточным данным'' алгоритма;
* при <math>j = n</math> - выходным данным.

Описанный граф можно посмотреть на рисунке, выполненном для случая <math>m = 4, n = 5</math>. Здесь вершины обозначены голубым цветом. Изображена подача только входных данных из вектора <math>x</math>, подача элементов матрицы <math>A</math>, идущая во все вершины, на рисунке не представлена.

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

Для алгоритма умножения квадратной матрицы на вектор порядка n в параллельном варианте требуется последовательно выполнить следующие ярусы:

* по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>n</math> операций).

Для умножения матрицы размером <math>m</math> строк на <math>n</math> столбцов на вектор порядка <math>n</math> в последовательном (наиболее быстром) варианте требуется:

* по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>m</math> операций).

При этом использование режима накопления требует совершения умножений и сложений в режиме двойной точности, а в параллельном варианте это означает, что практически все промежуточные вычисления для выполнения алгоритма в режиме накопления должны быть двойной точности. В отличие от последовательного варианта это означает некоторое увеличение требуемой памяти.

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

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

'''Входные данные''': матрица <math>A</math> (элементы <math>a_{ij}</math>), вектор <math>x</math> (элементы <math>x_{i}</math>).

'''Объём входных данных''': <math>mn+n</math> .

'''Выходные данные''': вектор <math>y</math> (элементы <math>y_{i}</math>).

'''Объём выходных данных''': <math>m</math>.

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

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''линейным'' (отношение квадратической или билинейной к линейной).

При этом вычислительная мощность алгоритма умножения матрицы на вектор, как отношение числа операций к суммарному объему входных и выходных данных – всего лишь ''константа''.

При этом алгоритм умножения матрицы на вектор полностью детерминирован. Использование другого порядка выполнения ассоциативных операций в данной версии нами не рассматривается.

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

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

В простейшем варианте алгоритм умножения матрицы на вектор на Фортране можно записать так:

<source lang="fortran">

DO I = 1, M
S = 0.
DO J = 1, N
S = S + DPROD(A(I,J), X(J))
END DO
Y(I) = S
END DO
</source>
При этом для реализации режима накопления переменная <math>S</math> должна быть двойной точности.

=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====

[[file:mv mult 1.PNG|thumb|center|700px|Рисунок 2. Умножение плотной матрицы на вектор. Общий профиль обращений в память]]

На рис.2 представлен профиль обращений в память для реализации умножения плотной матрицы на вектор. В данном алгоритме задействовано три массива. Выделенный зеленым фрагмент 1 образован обращениями к результирующему вектору; фрагмент 2 – обращениями к исходному вектору; остальные обращения (фрагмент 3) выполняются к матрице, на которую умножается исходный вектор.

Если посмотреть на исходный код, становится понятным, что каждый фрагмент устроен очень просто:
<source lang="C">
for(int i = 0; i < size; i++)
for(int j = 0; j < size; j++)
vec_out[i] += matrix[i][j] * vec_in[j];
</source>

Видно, что фрагмент 1 (обращения к массиву vec_out) состоит из последовательного перебора всех элементов вектора, только к каждому элементу происходит подряд size обращений. Во фрагменте 2 (массив vec_in) выполняется обычный последовательный перебор, который затем повторяется size раз. Фрагмент 3 также представляет собой последовательный перебор всех элементов матрицы, который выполняется только один раз.

Самой высокой локальностью обладает фрагмент 1 из-за повторяющихся подряд обращений к одним и тем же элементам. Однако фрагмент 2 также обладает высокой как пространственной, так и временной локальностью, поскольку число повторных проходов достаточно велико. Фрагмент 3, как и остальные, характеризуется высокой пространственной локальностью (из-за последовательного перебора), однако очень низкой временной локальностью – повторные обращения в нем просто отсутствуют.

===== Количественная оценка локальности =====

Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен [http://git.algowiki-project.org/Voevodin/locality/blob/master/benchmarks/d_matrix_vect_mult/d_matrix_vect_mult.h здесь] (функция Kernel). Условия запуска описаны [http://git.algowiki-project.org/Voevodin/locality/blob/master/README.md здесь].

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

На рис.3 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что производительность данной программы очень высока, даже немного выше, чем производительность теста Linpack. Одна из основных причин этому – очень высокая локальность обращений к векторам.

[[file:mv mult daps ru.PNG|thumb|center|700px|Рисунок 3. Сравнение значений оценки daps]]

Вторая характеристика – cvg – предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать, тем лучше локальность.

На рис.4 приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Можно увидеть, что, согласно данной оценке, локальность реализации умножения матрицы на вектор высока, хотя и не среди первых значений. Однако можно заметить, что полученное значение лишь совсем немного ниже оценки cvg для, например, реализации метода Гаусса или лучших вариантов перемножения матрицы.

[[file:mv mult cvg.PNG|thumb|center|700px|Рисунок 4. Сравнение значений оценки cvg]]

=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
[[file:Масштабируемость перемножения матрицы и вектора производительность.png|thumb|center|700px|Рисунок 5. Параллельная реализация произведения матрицы на вектор Максимальная производительность. ]]
[[file:Масштабируемость перемножения матрицы и вектора эффективность.png|thumb|center|700px|Рисунок 6. Параллельная реализация произведения матрицы на вектор Максимальная эффективность. ]]
Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма:
* число процессоров [4 : 256]
* размерность матрицы [1024 : 51200]
Эффективность выполнения реализации алгоритма
* Минимальная эффективность 0,02%
* Максимальная эффективность 9,55%
Оценка масштабируемости
* По числу процессов: -0.01517 – при увеличении числа процессов эффективность убывает достаточно интенсивно на всей рассмотренной области изменений параметров запуска. Уменьшение эффективности на рассмотренной области работы параллельной программы звязано с увеличением числа пересылок с ростом числа процессов и как следствие ростом накладных расходов на организацию вычислений. Основной вклад в значение эффективности вносит область с малым числом процессов и малой задачей, там эффективность достигает максимума в 9,5%. Далее эффективность очень резко падает до уровня около 1% Присутствует область, на которой при увеличении числа процессов эффективность возрастает, но при дальнейшем росте продолжает снижаться. Это скорее всего объясняется декомпозицей данных, при которой наступает момент, когда размер матрицы позволяет блокам укладываться в КЭШ-память. Так же это подтверждает проявление этого явления, но со смещением по числу процессов, и при увеличении вычислительной сложности задачи.
* По размеру задачи: -0.0014 – при увеличении размера задачи эффективность в целом уменьшается по рассматриваемой области, хотя и менее интенсивно, чем при увеличении числа процессов. Снижение эффективности объясняется тем, что при росте вычислительной сложности существенно возрастают объемы передаваемых данных. При увеличении размера данных наступает момент резкого снижения эффективности с значений около 1% к долям процента и минимуму. С увеличением числа процессоров такой переход появляется на большем объеме данных. Это свидетельствует о том, что присутствует момент, когда данных слишком много и эффективность работы с ними становится значительно ниже, но чем больше имеется процессов, там позже наступает такой момент декомпозиции. Присутствует область возрастания эффективности, на всех рассмотренных размерах матрицы. Это объясняется тем, что при малом размере задачи данные хорошо укладываются в КЭШ память, что приводит к высокой эффективности работы приложения при малом размере задачи. При дальнейшем увеличении размера эффективность уменьшается при выходе за границы КЭШ-памяти.
* По двум направлениям: -0.0001546 – при рассмотрении увеличения, как вычислительной сложности, так и числа процессов по всей рассмотренной области значений уменьшается, интенсивность уменьшения эффективности не очень высока. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров составляет около 9% говорит о том, что уменьшение эффективности по всей области довольно равномерное, но интенсивно лишь в не очень больших участках по площади. На остальной области значений параметров изменения эффективности не столь значительны и находятся на приблизительно одном и том же уровне.

[http://git.algowiki-project.org/Teplov/Scalability/blob/master/matrix_vector_mult/mpi_mat_vect_time.c Реализация алгоритма на языке C]

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

== Литература ==
<references />

[[Категория:Статьи в работе]]
[[Категория:Матрично-векторные операции]]

[[En:Dense matrix-vector multiplication]]

Участник:Demiandr

2021-11-04T09:23:59Z

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

{{level-a}}

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

=== Общее описание алгоритма ===
Дифференциальный криптоанализ — метод криптоанализа симметричных блочных шифров (и других криптографических примитивов, в частности, хеш-функций и поточных шифров).
Дифференциальный криптоанализ основан на изучении преобразования разностей между шифруемыми значениями на различных раундах шифрования. В качестве разности, как правило, применяется операция побитового суммирования по модулю 2, хотя существуют атаки и с вычислением разности по модулю {\displaystyle 2^{32}}2^{32}. Является статистической атакой. Применим для взлома DES, FEAL и некоторых других шифров, как правило, разработанных ранее начала 90-х. Количество раундов современных шифров (AES, Camellia и др.) рассчитывалось с учётом обеспечения стойкости, в том числе и к дифференциальному криптоанализу.
Все существующие блочные алгоритмы шифрования являются итеративными алгоритмами, то есть при шифровании информация подвергается большому числу одних и тех же подряд идущих преобразований (раундов). В начале алгоритма шифрования из одного длинного секретного ключа при помощи алгоритма генерации раундовых ключей создаются мини-ключи, которые применяются на каждом раунде шифрования. Дифференциальный криптоанализ направлен на нахождение таких раундовых ключей, для последующего определения по ним основного секретного ключа криптосистемы, причем первым определяемым раундовым ключом является ключ последнего раунда шифрования.

=== Математическое описание алгоритма ===
Пусть <math>ΔX=({ΔX_1}{ΔX_2}{ΔX_3}...{ΔX_3})</math>
Задачей криптоаналитика является нахождение
Пусть <math>{p}</math> - вероя

=== Вычислительное ядро алгоритма ===

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

=== Макроструктура алгоритма ===

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

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

Для всех <math>i</math> от <math>1</math> до <math>m</math> по возрастанию выполняются

:<math>y_{i} = \sum_{j = 1}^{n} a_{ij} x_{j}</math>

Особо отметим, что вычисления сумм вида <math>\sum_{j = 1}^{n} a_{ij} x_{j}</math> производят в режиме накопления прибавлением к текущему (временному) значению вычисляемой компоненты вектора <math>y_{i}</math> произведений <math>a_{ij} x_{j}</math> для <math>j</math> от <math>1</math> до <math>n</math>, '''c возрастанием''' <math>j</math>, вначале все компоненты инициализируются нулями. При суммировании "по убыванию" общая схема принципиально не отличается и потому нами не рассматривается. Другие порядки выполнения суммирования приводят к изменению параллельных свойств алгоритма и будут рассматриваться нами в отдельных описаниях.

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

Cчитая базовой операцией операцию шифрования текста на одном раунде с использование дифференциальной характеристики с вероятностью <math>p</math>, на нахождение <math>b</math> бит раундового ключа <math>R-1</math> раунда шифрования потребуется около <math>(2с/p)(R+2^b)</math> операций шифрования, где <math>с</math> - некоторая небольшая константа. Так как основным параметром является вероятность <math>p</math>, от которой зависит числе пар текстов, данный алгоритм имеет линейную сложность.

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

Опишем [[глоссарий#Граф алгоритма|граф алгоритма]] как аналитически, так и в виде рисунка.

[[Файл:YeqAX.png|500px|thumb|center|Рисунок 1. Граф последовательного умножения плотной матрицы на вектор с отображением входных и выходных данных]]

Граф алгоритма умножения плотной матрицы на вектор состоит из одной группы вершин, расположенной в целочисленных узлах двумерной области, соответствующая ей операция <math>a+bc</math>.

Естественно введённые координаты области таковы:
* <math>i</math> — меняется в диапазоне от <math>1</math> до <math>m</math>, принимая все целочисленные значения;
* <math>j</math> — меняется в диапазоне от <math>1</math> до <math>n</math>, принимая все целочисленные значения.

Аргументы операции следующие:
*<math>a</math>:
** при <math>j = 1</math> константа <math>0.</math>;
** при <math>j > 1</math> — результат срабатывания операции, соответствующей вершине с координатами <math>i, j-1</math>;
*<math>b</math> — элемент ''входных данных'', а именно <math>a_{ij}</math>;
*<math>c</math> - элемент входных данных <math>x_{j}</math>;

Результат срабатывания операции является:
* при <math>j < n</math> - ''промежуточным данным'' алгоритма;
* при <math>j = n</math> - выходным данным.

Описанный граф можно посмотреть на рисунке, выполненном для случая <math>m = 4, n = 5</math>. Здесь вершины обозначены голубым цветом. Изображена подача только входных данных из вектора <math>x</math>, подача элементов матрицы <math>A</math>, идущая во все вершины, на рисунке не представлена.

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

Для алгоритма умножения квадратной матрицы на вектор порядка n в параллельном варианте требуется последовательно выполнить следующие ярусы:

* по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>n</math> операций).

Для умножения матрицы размером <math>m</math> строк на <math>n</math> столбцов на вектор порядка <math>n</math> в последовательном (наиболее быстром) варианте требуется:

* по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>m</math> операций).

При этом использование режима накопления требует совершения умножений и сложений в режиме двойной точности, а в параллельном варианте это означает, что практически все промежуточные вычисления для выполнения алгоритма в режиме накопления должны быть двойной точности. В отличие от последовательного варианта это означает некоторое увеличение требуемой памяти.

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

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

'''Входные данные''': матрица <math>A</math> (элементы <math>a_{ij}</math>), вектор <math>x</math> (элементы <math>x_{i}</math>).

'''Объём входных данных''': <math>mn+n</math> .

'''Выходные данные''': вектор <math>y</math> (элементы <math>y_{i}</math>).

'''Объём выходных данных''': <math>m</math>.

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

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''линейным'' (отношение квадратической или билинейной к линейной).

При этом вычислительная мощность алгоритма умножения матрицы на вектор, как отношение числа операций к суммарному объему входных и выходных данных – всего лишь ''константа''.

При этом алгоритм умножения матрицы на вектор полностью детерминирован. Использование другого порядка выполнения ассоциативных операций в данной версии нами не рассматривается.

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

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

В простейшем варианте алгоритм умножения матрицы на вектор на Фортране можно записать так:

<source lang="fortran">

DO I = 1, M
S = 0.
DO J = 1, N
S = S + DPROD(A(I,J), X(J))
END DO
Y(I) = S
END DO
</source>
При этом для реализации режима накопления переменная <math>S</math> должна быть двойной точности.

=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====

[[file:mv mult 1.PNG|thumb|center|700px|Рисунок 2. Умножение плотной матрицы на вектор. Общий профиль обращений в память]]

На рис.2 представлен профиль обращений в память для реализации умножения плотной матрицы на вектор. В данном алгоритме задействовано три массива. Выделенный зеленым фрагмент 1 образован обращениями к результирующему вектору; фрагмент 2 – обращениями к исходному вектору; остальные обращения (фрагмент 3) выполняются к матрице, на которую умножается исходный вектор.

Если посмотреть на исходный код, становится понятным, что каждый фрагмент устроен очень просто:
<source lang="C">
for(int i = 0; i < size; i++)
for(int j = 0; j < size; j++)
vec_out[i] += matrix[i][j] * vec_in[j];
</source>

Видно, что фрагмент 1 (обращения к массиву vec_out) состоит из последовательного перебора всех элементов вектора, только к каждому элементу происходит подряд size обращений. Во фрагменте 2 (массив vec_in) выполняется обычный последовательный перебор, который затем повторяется size раз. Фрагмент 3 также представляет собой последовательный перебор всех элементов матрицы, который выполняется только один раз.

Самой высокой локальностью обладает фрагмент 1 из-за повторяющихся подряд обращений к одним и тем же элементам. Однако фрагмент 2 также обладает высокой как пространственной, так и временной локальностью, поскольку число повторных проходов достаточно велико. Фрагмент 3, как и остальные, характеризуется высокой пространственной локальностью (из-за последовательного перебора), однако очень низкой временной локальностью – повторные обращения в нем просто отсутствуют.

===== Количественная оценка локальности =====

Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен [http://git.algowiki-project.org/Voevodin/locality/blob/master/benchmarks/d_matrix_vect_mult/d_matrix_vect_mult.h здесь] (функция Kernel). Условия запуска описаны [http://git.algowiki-project.org/Voevodin/locality/blob/master/README.md здесь].

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

На рис.3 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что производительность данной программы очень высока, даже немного выше, чем производительность теста Linpack. Одна из основных причин этому – очень высокая локальность обращений к векторам.

[[file:mv mult daps ru.PNG|thumb|center|700px|Рисунок 3. Сравнение значений оценки daps]]

Вторая характеристика – cvg – предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать, тем лучше локальность.

На рис.4 приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Можно увидеть, что, согласно данной оценке, локальность реализации умножения матрицы на вектор высока, хотя и не среди первых значений. Однако можно заметить, что полученное значение лишь совсем немного ниже оценки cvg для, например, реализации метода Гаусса или лучших вариантов перемножения матрицы.

[[file:mv mult cvg.PNG|thumb|center|700px|Рисунок 4. Сравнение значений оценки cvg]]

=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
[[file:Масштабируемость перемножения матрицы и вектора производительность.png|thumb|center|700px|Рисунок 5. Параллельная реализация произведения матрицы на вектор Максимальная производительность. ]]
[[file:Масштабируемость перемножения матрицы и вектора эффективность.png|thumb|center|700px|Рисунок 6. Параллельная реализация произведения матрицы на вектор Максимальная эффективность. ]]
Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма:
* число процессоров [4 : 256]
* размерность матрицы [1024 : 51200]
Эффективность выполнения реализации алгоритма
* Минимальная эффективность 0,02%
* Максимальная эффективность 9,55%
Оценка масштабируемости
* По числу процессов: -0.01517 – при увеличении числа процессов эффективность убывает достаточно интенсивно на всей рассмотренной области изменений параметров запуска. Уменьшение эффективности на рассмотренной области работы параллельной программы звязано с увеличением числа пересылок с ростом числа процессов и как следствие ростом накладных расходов на организацию вычислений. Основной вклад в значение эффективности вносит область с малым числом процессов и малой задачей, там эффективность достигает максимума в 9,5%. Далее эффективность очень резко падает до уровня около 1% Присутствует область, на которой при увеличении числа процессов эффективность возрастает, но при дальнейшем росте продолжает снижаться. Это скорее всего объясняется декомпозицей данных, при которой наступает момент, когда размер матрицы позволяет блокам укладываться в КЭШ-память. Так же это подтверждает проявление этого явления, но со смещением по числу процессов, и при увеличении вычислительной сложности задачи.
* По размеру задачи: -0.0014 – при увеличении размера задачи эффективность в целом уменьшается по рассматриваемой области, хотя и менее интенсивно, чем при увеличении числа процессов. Снижение эффективности объясняется тем, что при росте вычислительной сложности существенно возрастают объемы передаваемых данных. При увеличении размера данных наступает момент резкого снижения эффективности с значений около 1% к долям процента и минимуму. С увеличением числа процессоров такой переход появляется на большем объеме данных. Это свидетельствует о том, что присутствует момент, когда данных слишком много и эффективность работы с ними становится значительно ниже, но чем больше имеется процессов, там позже наступает такой момент декомпозиции. Присутствует область возрастания эффективности, на всех рассмотренных размерах матрицы. Это объясняется тем, что при малом размере задачи данные хорошо укладываются в КЭШ память, что приводит к высокой эффективности работы приложения при малом размере задачи. При дальнейшем увеличении размера эффективность уменьшается при выходе за границы КЭШ-памяти.
* По двум направлениям: -0.0001546 – при рассмотрении увеличения, как вычислительной сложности, так и числа процессов по всей рассмотренной области значений уменьшается, интенсивность уменьшения эффективности не очень высока. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров составляет около 9% говорит о том, что уменьшение эффективности по всей области довольно равномерное, но интенсивно лишь в не очень больших участках по площади. На остальной области значений параметров изменения эффективности не столь значительны и находятся на приблизительно одном и том же уровне.

[http://git.algowiki-project.org/Teplov/Scalability/blob/master/matrix_vector_mult/mpi_mat_vect_time.c Реализация алгоритма на языке C]

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

== Литература ==
<references />

[[Категория:Статьи в работе]]
[[Категория:Матрично-векторные операции]]

[[En:Dense matrix-vector multiplication]]

Участник:Demiandr

2021-11-04T09:16:53Z

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

{{level-a}}

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

=== Общее описание алгоритма ===
Дифференциальный криптоанализ — метод криптоанализа симметричных блочных шифров (и других криптографических примитивов, в частности, хеш-функций и поточных шифров).
Дифференциальный криптоанализ основан на изучении преобразования разностей между шифруемыми значениями на различных раундах шифрования. В качестве разности, как правило, применяется операция побитового суммирования по модулю 2, хотя существуют атаки и с вычислением разности по модулю {\displaystyle 2^{32}}2^{32}. Является статистической атакой. Применим для взлома DES, FEAL и некоторых других шифров, как правило, разработанных ранее начала 90-х. Количество раундов современных шифров (AES, Camellia и др.) рассчитывалось с учётом обеспечения стойкости, в том числе и к дифференциальному криптоанализу.
Все существующие блочные алгоритмы шифрования являются итеративными алгоритмами, то есть при шифровании информация подвергается большому числу одних и тех же подряд идущих преобразований (раундов). В начале алгоритма шифрования из одного длинного секретного ключа при помощи алгоритма генерации раундовых ключей создаются мини-ключи, которые применяются на каждом раунде шифрования. Дифференциальный криптоанализ направлен на нахождение таких раундовых ключей, для последующего определения по ним основного секретного ключа криптосистемы, причем первым определяемым раундовым ключом является ключ последнего раунда шифрования.

=== Математическое описание алгоритма ===
Пусть <math>ΔX=({ΔX_1}{ΔX_2}{ΔX_3}...{ΔX_3})</math>
Задачей криптоаналитика является нахождение
Пусть <math>{p}</math> - вероя

=== Вычислительное ядро алгоритма ===

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

=== Макроструктура алгоритма ===

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

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

Для всех <math>i</math> от <math>1</math> до <math>m</math> по возрастанию выполняются

:<math>y_{i} = \sum_{j = 1}^{n} a_{ij} x_{j}</math>

Особо отметим, что вычисления сумм вида <math>\sum_{j = 1}^{n} a_{ij} x_{j}</math> производят в режиме накопления прибавлением к текущему (временному) значению вычисляемой компоненты вектора <math>y_{i}</math> произведений <math>a_{ij} x_{j}</math> для <math>j</math> от <math>1</math> до <math>n</math>, '''c возрастанием''' <math>j</math>, вначале все компоненты инициализируются нулями. При суммировании "по убыванию" общая схема принципиально не отличается и потому нами не рассматривается. Другие порядки выполнения суммирования приводят к изменению параллельных свойств алгоритма и будут рассматриваться нами в отдельных описаниях.

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

Cчитая базовой операцией операцию шифрования текста на одном раунде с использование дифференциальной характеристики с вероятностью <math>p</math>, на нахождение <math>b</math> бит раундового ключа <math>R-1</math> раунда шифрования потребуется около <math>(2с/p)(R+2^b)</math> операций шифрования.
При классификации по последовательной сложности, таким образом, алгоритм умножения матрицы на вектор относится к алгоритмам ''с квадратической сложностью''.

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

Опишем [[глоссарий#Граф алгоритма|граф алгоритма]] как аналитически, так и в виде рисунка.

[[Файл:YeqAX.png|500px|thumb|center|Рисунок 1. Граф последовательного умножения плотной матрицы на вектор с отображением входных и выходных данных]]

Граф алгоритма умножения плотной матрицы на вектор состоит из одной группы вершин, расположенной в целочисленных узлах двумерной области, соответствующая ей операция <math>a+bc</math>.

Естественно введённые координаты области таковы:
* <math>i</math> — меняется в диапазоне от <math>1</math> до <math>m</math>, принимая все целочисленные значения;
* <math>j</math> — меняется в диапазоне от <math>1</math> до <math>n</math>, принимая все целочисленные значения.

Аргументы операции следующие:
*<math>a</math>:
** при <math>j = 1</math> константа <math>0.</math>;
** при <math>j > 1</math> — результат срабатывания операции, соответствующей вершине с координатами <math>i, j-1</math>;
*<math>b</math> — элемент ''входных данных'', а именно <math>a_{ij}</math>;
*<math>c</math> - элемент входных данных <math>x_{j}</math>;

Результат срабатывания операции является:
* при <math>j < n</math> - ''промежуточным данным'' алгоритма;
* при <math>j = n</math> - выходным данным.

Описанный граф можно посмотреть на рисунке, выполненном для случая <math>m = 4, n = 5</math>. Здесь вершины обозначены голубым цветом. Изображена подача только входных данных из вектора <math>x</math>, подача элементов матрицы <math>A</math>, идущая во все вершины, на рисунке не представлена.

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

Для алгоритма умножения квадратной матрицы на вектор порядка n в параллельном варианте требуется последовательно выполнить следующие ярусы:

* по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>n</math> операций).

Для умножения матрицы размером <math>m</math> строк на <math>n</math> столбцов на вектор порядка <math>n</math> в последовательном (наиболее быстром) варианте требуется:

* по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>m</math> операций).

При этом использование режима накопления требует совершения умножений и сложений в режиме двойной точности, а в параллельном варианте это означает, что практически все промежуточные вычисления для выполнения алгоритма в режиме накопления должны быть двойной точности. В отличие от последовательного варианта это означает некоторое увеличение требуемой памяти.

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

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

'''Входные данные''': матрица <math>A</math> (элементы <math>a_{ij}</math>), вектор <math>x</math> (элементы <math>x_{i}</math>).

'''Объём входных данных''': <math>mn+n</math> .

'''Выходные данные''': вектор <math>y</math> (элементы <math>y_{i}</math>).

'''Объём выходных данных''': <math>m</math>.

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

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''линейным'' (отношение квадратической или билинейной к линейной).

При этом вычислительная мощность алгоритма умножения матрицы на вектор, как отношение числа операций к суммарному объему входных и выходных данных – всего лишь ''константа''.

При этом алгоритм умножения матрицы на вектор полностью детерминирован. Использование другого порядка выполнения ассоциативных операций в данной версии нами не рассматривается.

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

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

В простейшем варианте алгоритм умножения матрицы на вектор на Фортране можно записать так:

<source lang="fortran">

DO I = 1, M
S = 0.
DO J = 1, N
S = S + DPROD(A(I,J), X(J))
END DO
Y(I) = S
END DO
</source>
При этом для реализации режима накопления переменная <math>S</math> должна быть двойной точности.

=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====

[[file:mv mult 1.PNG|thumb|center|700px|Рисунок 2. Умножение плотной матрицы на вектор. Общий профиль обращений в память]]

На рис.2 представлен профиль обращений в память для реализации умножения плотной матрицы на вектор. В данном алгоритме задействовано три массива. Выделенный зеленым фрагмент 1 образован обращениями к результирующему вектору; фрагмент 2 – обращениями к исходному вектору; остальные обращения (фрагмент 3) выполняются к матрице, на которую умножается исходный вектор.

Если посмотреть на исходный код, становится понятным, что каждый фрагмент устроен очень просто:
<source lang="C">
for(int i = 0; i < size; i++)
for(int j = 0; j < size; j++)
vec_out[i] += matrix[i][j] * vec_in[j];
</source>

Видно, что фрагмент 1 (обращения к массиву vec_out) состоит из последовательного перебора всех элементов вектора, только к каждому элементу происходит подряд size обращений. Во фрагменте 2 (массив vec_in) выполняется обычный последовательный перебор, который затем повторяется size раз. Фрагмент 3 также представляет собой последовательный перебор всех элементов матрицы, который выполняется только один раз.

Самой высокой локальностью обладает фрагмент 1 из-за повторяющихся подряд обращений к одним и тем же элементам. Однако фрагмент 2 также обладает высокой как пространственной, так и временной локальностью, поскольку число повторных проходов достаточно велико. Фрагмент 3, как и остальные, характеризуется высокой пространственной локальностью (из-за последовательного перебора), однако очень низкой временной локальностью – повторные обращения в нем просто отсутствуют.

===== Количественная оценка локальности =====

Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен [http://git.algowiki-project.org/Voevodin/locality/blob/master/benchmarks/d_matrix_vect_mult/d_matrix_vect_mult.h здесь] (функция Kernel). Условия запуска описаны [http://git.algowiki-project.org/Voevodin/locality/blob/master/README.md здесь].

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

На рис.3 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что производительность данной программы очень высока, даже немного выше, чем производительность теста Linpack. Одна из основных причин этому – очень высокая локальность обращений к векторам.

[[file:mv mult daps ru.PNG|thumb|center|700px|Рисунок 3. Сравнение значений оценки daps]]

Вторая характеристика – cvg – предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать, тем лучше локальность.

На рис.4 приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Можно увидеть, что, согласно данной оценке, локальность реализации умножения матрицы на вектор высока, хотя и не среди первых значений. Однако можно заметить, что полученное значение лишь совсем немного ниже оценки cvg для, например, реализации метода Гаусса или лучших вариантов перемножения матрицы.

[[file:mv mult cvg.PNG|thumb|center|700px|Рисунок 4. Сравнение значений оценки cvg]]

=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
[[file:Масштабируемость перемножения матрицы и вектора производительность.png|thumb|center|700px|Рисунок 5. Параллельная реализация произведения матрицы на вектор Максимальная производительность. ]]
[[file:Масштабируемость перемножения матрицы и вектора эффективность.png|thumb|center|700px|Рисунок 6. Параллельная реализация произведения матрицы на вектор Максимальная эффективность. ]]
Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма:
* число процессоров [4 : 256]
* размерность матрицы [1024 : 51200]
Эффективность выполнения реализации алгоритма
* Минимальная эффективность 0,02%
* Максимальная эффективность 9,55%
Оценка масштабируемости
* По числу процессов: -0.01517 – при увеличении числа процессов эффективность убывает достаточно интенсивно на всей рассмотренной области изменений параметров запуска. Уменьшение эффективности на рассмотренной области работы параллельной программы звязано с увеличением числа пересылок с ростом числа процессов и как следствие ростом накладных расходов на организацию вычислений. Основной вклад в значение эффективности вносит область с малым числом процессов и малой задачей, там эффективность достигает максимума в 9,5%. Далее эффективность очень резко падает до уровня около 1% Присутствует область, на которой при увеличении числа процессов эффективность возрастает, но при дальнейшем росте продолжает снижаться. Это скорее всего объясняется декомпозицей данных, при которой наступает момент, когда размер матрицы позволяет блокам укладываться в КЭШ-память. Так же это подтверждает проявление этого явления, но со смещением по числу процессов, и при увеличении вычислительной сложности задачи.
* По размеру задачи: -0.0014 – при увеличении размера задачи эффективность в целом уменьшается по рассматриваемой области, хотя и менее интенсивно, чем при увеличении числа процессов. Снижение эффективности объясняется тем, что при росте вычислительной сложности существенно возрастают объемы передаваемых данных. При увеличении размера данных наступает момент резкого снижения эффективности с значений около 1% к долям процента и минимуму. С увеличением числа процессоров такой переход появляется на большем объеме данных. Это свидетельствует о том, что присутствует момент, когда данных слишком много и эффективность работы с ними становится значительно ниже, но чем больше имеется процессов, там позже наступает такой момент декомпозиции. Присутствует область возрастания эффективности, на всех рассмотренных размерах матрицы. Это объясняется тем, что при малом размере задачи данные хорошо укладываются в КЭШ память, что приводит к высокой эффективности работы приложения при малом размере задачи. При дальнейшем увеличении размера эффективность уменьшается при выходе за границы КЭШ-памяти.
* По двум направлениям: -0.0001546 – при рассмотрении увеличения, как вычислительной сложности, так и числа процессов по всей рассмотренной области значений уменьшается, интенсивность уменьшения эффективности не очень высока. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров составляет около 9% говорит о том, что уменьшение эффективности по всей области довольно равномерное, но интенсивно лишь в не очень больших участках по площади. На остальной области значений параметров изменения эффективности не столь значительны и находятся на приблизительно одном и том же уровне.

[http://git.algowiki-project.org/Teplov/Scalability/blob/master/matrix_vector_mult/mpi_mat_vect_time.c Реализация алгоритма на языке C]

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

== Литература ==
<references />

[[Категория:Статьи в работе]]
[[Категория:Матрично-векторные операции]]

[[En:Dense matrix-vector multiplication]]

Участник:Demiandr

2021-11-04T08:53:17Z

{{level-a}}

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

=== Общее описание алгоритма ===
Дифференциальный криптоанализ — метод криптоанализа симметричных блочных шифров (и других криптографических примитивов, в частности, хеш-функций и поточных шифров).
Дифференциальный криптоанализ основан на изучении преобразования разностей между шифруемыми значениями на различных раундах шифрования. В качестве разности, как правило, применяется операция побитового суммирования по модулю 2, хотя существуют атаки и с вычислением разности по модулю {\displaystyle 2^{32}}2^{32}. Является статистической атакой. Применим для взлома DES, FEAL и некоторых других шифров, как правило, разработанных ранее начала 90-х. Количество раундов современных шифров (AES, Camellia и др.) рассчитывалось с учётом обеспечения стойкости, в том числе и к дифференциальному криптоанализу.
Все существующие блочные алгоритмы шифрования являются итеративными алгоритмами, то есть при шифровании информация подвергается большому числу одних и тех же подряд идущих преобразований (раундов). В начале алгоритма шифрования из одного длинного секретного ключа при помощи алгоритма генерации раундовых ключей создаются мини-ключи, которые применяются на каждом раунде шифрования. Дифференциальный криптоанализ направлен на нахождение таких раундовых ключей, для последующего определения по ним основного секретного ключа криптосистемы, причем первым определяемым раундовым ключом является ключ последнего раунда шифрования.

=== Математическое описание алгоритма ===
Пусть <math>ΔX=({ΔX_1}{ΔX_2}{ΔX_3}...{ΔX_3})</math>
Задачей криптоаналитика является нахождение
Пусть <math>{p}</math> - вероя

=== Вычислительное ядро алгоритма ===

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

=== Макроструктура алгоритма ===

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

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

Для всех <math>i</math> от <math>1</math> до <math>m</math> по возрастанию выполняются

:<math>y_{i} = \sum_{j = 1}^{n} a_{ij} x_{j}</math>

Особо отметим, что вычисления сумм вида <math>\sum_{j = 1}^{n} a_{ij} x_{j}</math> производят в режиме накопления прибавлением к текущему (временному) значению вычисляемой компоненты вектора <math>y_{i}</math> произведений <math>a_{ij} x_{j}</math> для <math>j</math> от <math>1</math> до <math>n</math>, '''c возрастанием''' <math>j</math>, вначале все компоненты инициализируются нулями. При суммировании "по убыванию" общая схема принципиально не отличается и потому нами не рассматривается. Другие порядки выполнения суммирования приводят к изменению параллельных свойств алгоритма и будут рассматриваться нами в отдельных описаниях.

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

Cчитая базовой операцией операцию шифрования текста на одном раунде с использование дифференциальной характеристики с вероятностью <math>p</math>, на нахождение <math>b</math> бит раундового ключа <math>R-1</math> раунда шифрования потребуется около <math>(2*с/p)*(R+2^b)</math> операций шифрования.
При классификации по последовательной сложности, таким образом, алгоритм умножения матрицы на вектор относится к алгоритмам ''с квадратической сложностью'' (в случае неквадратной матрицы - с ''билинейной'').

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

Опишем [[глоссарий#Граф алгоритма|граф алгоритма]] как аналитически, так и в виде рисунка.

[[Файл:YeqAX.png|500px|thumb|center|Рисунок 1. Граф последовательного умножения плотной матрицы на вектор с отображением входных и выходных данных]]

Граф алгоритма умножения плотной матрицы на вектор состоит из одной группы вершин, расположенной в целочисленных узлах двумерной области, соответствующая ей операция <math>a+bc</math>.

Естественно введённые координаты области таковы:
* <math>i</math> — меняется в диапазоне от <math>1</math> до <math>m</math>, принимая все целочисленные значения;
* <math>j</math> — меняется в диапазоне от <math>1</math> до <math>n</math>, принимая все целочисленные значения.

Аргументы операции следующие:
*<math>a</math>:
** при <math>j = 1</math> константа <math>0.</math>;
** при <math>j > 1</math> — результат срабатывания операции, соответствующей вершине с координатами <math>i, j-1</math>;
*<math>b</math> — элемент ''входных данных'', а именно <math>a_{ij}</math>;
*<math>c</math> - элемент входных данных <math>x_{j}</math>;

Результат срабатывания операции является:
* при <math>j < n</math> - ''промежуточным данным'' алгоритма;
* при <math>j = n</math> - выходным данным.

Описанный граф можно посмотреть на рисунке, выполненном для случая <math>m = 4, n = 5</math>. Здесь вершины обозначены голубым цветом. Изображена подача только входных данных из вектора <math>x</math>, подача элементов матрицы <math>A</math>, идущая во все вершины, на рисунке не представлена.

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

Для алгоритма умножения квадратной матрицы на вектор порядка n в параллельном варианте требуется последовательно выполнить следующие ярусы:

* по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>n</math> операций).

Для умножения матрицы размером <math>m</math> строк на <math>n</math> столбцов на вектор порядка <math>n</math> в последовательном (наиболее быстром) варианте требуется:

* по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>m</math> операций).

При этом использование режима накопления требует совершения умножений и сложений в режиме двойной точности, а в параллельном варианте это означает, что практически все промежуточные вычисления для выполнения алгоритма в режиме накопления должны быть двойной точности. В отличие от последовательного варианта это означает некоторое увеличение требуемой памяти.

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

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

'''Входные данные''': матрица <math>A</math> (элементы <math>a_{ij}</math>), вектор <math>x</math> (элементы <math>x_{i}</math>).

'''Объём входных данных''': <math>mn+n</math> .

'''Выходные данные''': вектор <math>y</math> (элементы <math>y_{i}</math>).

'''Объём выходных данных''': <math>m</math>.

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

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''линейным'' (отношение квадратической или билинейной к линейной).

При этом вычислительная мощность алгоритма умножения матрицы на вектор, как отношение числа операций к суммарному объему входных и выходных данных – всего лишь ''константа''.

При этом алгоритм умножения матрицы на вектор полностью детерминирован. Использование другого порядка выполнения ассоциативных операций в данной версии нами не рассматривается.

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

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

В простейшем варианте алгоритм умножения матрицы на вектор на Фортране можно записать так:

<source lang="fortran">

DO I = 1, M
S = 0.
DO J = 1, N
S = S + DPROD(A(I,J), X(J))
END DO
Y(I) = S
END DO
</source>
При этом для реализации режима накопления переменная <math>S</math> должна быть двойной точности.

=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====

[[file:mv mult 1.PNG|thumb|center|700px|Рисунок 2. Умножение плотной матрицы на вектор. Общий профиль обращений в память]]

На рис.2 представлен профиль обращений в память для реализации умножения плотной матрицы на вектор. В данном алгоритме задействовано три массива. Выделенный зеленым фрагмент 1 образован обращениями к результирующему вектору; фрагмент 2 – обращениями к исходному вектору; остальные обращения (фрагмент 3) выполняются к матрице, на которую умножается исходный вектор.

Если посмотреть на исходный код, становится понятным, что каждый фрагмент устроен очень просто:
<source lang="C">
for(int i = 0; i < size; i++)
for(int j = 0; j < size; j++)
vec_out[i] += matrix[i][j] * vec_in[j];
</source>

Видно, что фрагмент 1 (обращения к массиву vec_out) состоит из последовательного перебора всех элементов вектора, только к каждому элементу происходит подряд size обращений. Во фрагменте 2 (массив vec_in) выполняется обычный последовательный перебор, который затем повторяется size раз. Фрагмент 3 также представляет собой последовательный перебор всех элементов матрицы, который выполняется только один раз.

Самой высокой локальностью обладает фрагмент 1 из-за повторяющихся подряд обращений к одним и тем же элементам. Однако фрагмент 2 также обладает высокой как пространственной, так и временной локальностью, поскольку число повторных проходов достаточно велико. Фрагмент 3, как и остальные, характеризуется высокой пространственной локальностью (из-за последовательного перебора), однако очень низкой временной локальностью – повторные обращения в нем просто отсутствуют.

===== Количественная оценка локальности =====

Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен [http://git.algowiki-project.org/Voevodin/locality/blob/master/benchmarks/d_matrix_vect_mult/d_matrix_vect_mult.h здесь] (функция Kernel). Условия запуска описаны [http://git.algowiki-project.org/Voevodin/locality/blob/master/README.md здесь].

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

На рис.3 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что производительность данной программы очень высока, даже немного выше, чем производительность теста Linpack. Одна из основных причин этому – очень высокая локальность обращений к векторам.

[[file:mv mult daps ru.PNG|thumb|center|700px|Рисунок 3. Сравнение значений оценки daps]]

Вторая характеристика – cvg – предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать, тем лучше локальность.

На рис.4 приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Можно увидеть, что, согласно данной оценке, локальность реализации умножения матрицы на вектор высока, хотя и не среди первых значений. Однако можно заметить, что полученное значение лишь совсем немного ниже оценки cvg для, например, реализации метода Гаусса или лучших вариантов перемножения матрицы.

[[file:mv mult cvg.PNG|thumb|center|700px|Рисунок 4. Сравнение значений оценки cvg]]

=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
[[file:Масштабируемость перемножения матрицы и вектора производительность.png|thumb|center|700px|Рисунок 5. Параллельная реализация произведения матрицы на вектор Максимальная производительность. ]]
[[file:Масштабируемость перемножения матрицы и вектора эффективность.png|thumb|center|700px|Рисунок 6. Параллельная реализация произведения матрицы на вектор Максимальная эффективность. ]]
Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма:
* число процессоров [4 : 256]
* размерность матрицы [1024 : 51200]
Эффективность выполнения реализации алгоритма
* Минимальная эффективность 0,02%
* Максимальная эффективность 9,55%
Оценка масштабируемости
* По числу процессов: -0.01517 – при увеличении числа процессов эффективность убывает достаточно интенсивно на всей рассмотренной области изменений параметров запуска. Уменьшение эффективности на рассмотренной области работы параллельной программы звязано с увеличением числа пересылок с ростом числа процессов и как следствие ростом накладных расходов на организацию вычислений. Основной вклад в значение эффективности вносит область с малым числом процессов и малой задачей, там эффективность достигает максимума в 9,5%. Далее эффективность очень резко падает до уровня около 1% Присутствует область, на которой при увеличении числа процессов эффективность возрастает, но при дальнейшем росте продолжает снижаться. Это скорее всего объясняется декомпозицей данных, при которой наступает момент, когда размер матрицы позволяет блокам укладываться в КЭШ-память. Так же это подтверждает проявление этого явления, но со смещением по числу процессов, и при увеличении вычислительной сложности задачи.
* По размеру задачи: -0.0014 – при увеличении размера задачи эффективность в целом уменьшается по рассматриваемой области, хотя и менее интенсивно, чем при увеличении числа процессов. Снижение эффективности объясняется тем, что при росте вычислительной сложности существенно возрастают объемы передаваемых данных. При увеличении размера данных наступает момент резкого снижения эффективности с значений около 1% к долям процента и минимуму. С увеличением числа процессоров такой переход появляется на большем объеме данных. Это свидетельствует о том, что присутствует момент, когда данных слишком много и эффективность работы с ними становится значительно ниже, но чем больше имеется процессов, там позже наступает такой момент декомпозиции. Присутствует область возрастания эффективности, на всех рассмотренных размерах матрицы. Это объясняется тем, что при малом размере задачи данные хорошо укладываются в КЭШ память, что приводит к высокой эффективности работы приложения при малом размере задачи. При дальнейшем увеличении размера эффективность уменьшается при выходе за границы КЭШ-памяти.
* По двум направлениям: -0.0001546 – при рассмотрении увеличения, как вычислительной сложности, так и числа процессов по всей рассмотренной области значений уменьшается, интенсивность уменьшения эффективности не очень высока. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров составляет около 9% говорит о том, что уменьшение эффективности по всей области довольно равномерное, но интенсивно лишь в не очень больших участках по площади. На остальной области значений параметров изменения эффективности не столь значительны и находятся на приблизительно одном и том же уровне.

[http://git.algowiki-project.org/Teplov/Scalability/blob/master/matrix_vector_mult/mpi_mat_vect_time.c Реализация алгоритма на языке C]

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

== Литература ==
<references />

[[Категория:Статьи в работе]]
[[Категория:Матрично-векторные операции]]

[[En:Dense matrix-vector multiplication]]