The 25 reference contexts in paper E. Balk A., P. Klyucharev G., Е. Балк А., П. Ключарёв Г. (2016) “Исследование характеристик лавинного эффекта обобщенных клеточных автоматов на основе графов малого диаметра // Small Diameter Graph-based Investigation of Avalanche Effect Characteristics of Generalized Cellular Automata” / spz:neicon:technomag:y:2016:i:4:p:92-105

  1. Start
    2420
    Prefix
    эффекта и статистических свойств выходной последовательности, что делает естественным их применение в качестве базового криптографического примитива для генераторов псевдослучайных чисел, блочных шифров и криптографических хеш-функций. Эти особенности структуры позволяют создать высокоскоростную аппаратную реализацию на основе микросхем ПЛИС (Программируемых логических интегральных схем)
    Exact
    [8]
    Suffix
    . Впервые обобщённые клеточные автоматы были использованы для генерации псевдослучайной последовательности в работе [11], это направление получило развитие в цикле статей [4-9]. В вышеуказанных работах были рассмотрены обобщенные клеточные автоматы на основе графа достаточно большого диаметра .
    (check this in PDF content)

  2. Start
    2582
    Prefix
    Эти особенности структуры позволяют создать высокоскоростную аппаратную реализацию на основе микросхем ПЛИС (Программируемых логических интегральных схем) [8]. Впервые обобщённые клеточные автоматы были использованы для генерации псевдослучайной последовательности в работе
    Exact
    [11]
    Suffix
    , это направление получило развитие в цикле статей [4-9]. В вышеуказанных работах были рассмотрены обобщенные клеточные автоматы на основе графа достаточно большого диаметра . Согласно [3], выбор графа с минимальным диаметром обеспечивает лучшие характеристики лавинного эффекта в обобщенных клеточных автоматах.
    (check this in PDF content)

  3. Start
    2638
    Prefix
    Эти особенности структуры позволяют создать высокоскоростную аппаратную реализацию на основе микросхем ПЛИС (Программируемых логических интегральных схем) [8]. Впервые обобщённые клеточные автоматы были использованы для генерации псевдослучайной последовательности в работе [11], это направление получило развитие в цикле статей
    Exact
    [4-9]
    Suffix
    . В вышеуказанных работах были рассмотрены обобщенные клеточные автоматы на основе графа достаточно большого диаметра . Согласно [3], выбор графа с минимальным диаметром обеспечивает лучшие характеристики лавинного эффекта в обобщенных клеточных автоматах.
    (check this in PDF content)

  4. Start
    2771
    Prefix
    Впервые обобщённые клеточные автоматы были использованы для генерации псевдослучайной последовательности в работе [11], это направление получило развитие в цикле статей [4-9]. В вышеуказанных работах были рассмотрены обобщенные клеточные автоматы на основе графа достаточно большого диаметра . Согласно
    Exact
    [3]
    Suffix
    , выбор графа с минимальным диаметром обеспечивает лучшие характеристики лавинного эффекта в обобщенных клеточных автоматах. Основной задачей данной статьи является исследование свойств обобщенных клеточных автоматов на основе графов с диаметром и .
    (check this in PDF content)

  5. Start
    5607
    Prefix
    Выбор графа обобщенного клеточного автомата Для ряда задач, таких как разработка легковесных криптографических алгоритмов предъявляются повышенные требования к количеству используемых аппаратных ресурсов. В случае ПЛИС, реализация данного требования заключается в минимизации числа задействованных логических элементов, что является важным для целого ряда приложений (например,
    Exact
    [1,2]
    Suffix
    ). Количество используемых в реализации логических элементов, в первую очередь, определяется числом входов так называемой таблицы поиска (LUT), представляющей из себя запоминающее устройство, которое хранит в памяти таблицу истинности булевой функции от r-переменных и осуществляющей поиск значения соответствующей булевой функции вместо непосредственного вычисления значений.
    (check this in PDF content)

  6. Start
    6293
    Prefix
    В связи с тем, что наибольшее распространение получили ПЛИС с таблицей поиска на 4 и 6 входов, далее будут рассматриваться неориентированные 4- и 6-регулярные графы минимального диаметра. Оценим максимально возможный порядок графа заданной степени вершины и диаметра при помощи границы Мура .
    Exact
    [13]
    Suffix
    : (2) Легко заметить, что , а . В теории графов задача нахождения графа максимального порядка по заданной степени вершин и диаметру называется задачей степени/диаметра и обозначается .
    (check this in PDF content)

  7. Start
    6524
    Prefix
    В теории графов задача нахождения графа максимального порядка по заданной степени вершин и диаметру называется задачей степени/диаметра и обозначается . В настоящее время =17, а
    Exact
    [12]
    Suffix
    , что делает затруднительным применение автоматов на их основе в качестве генераторов псевдослучайных последовательностей. Поэтому в дальнейшем будем рассматривать графы , для которых соответственно , , , .
    (check this in PDF content)

  8. Start
    6812
    Prefix
    Поэтому в дальнейшем будем рассматривать графы , для которых соответственно , , , . На сегодняшний день максимальный порядок графов согласно
    Exact
    [12]
    Suffix
    для выбранных значений степени вершин и диаметра принимает следующие значения: , , , . Рассмотрим эти графы применительно к задаче построения обобщённых клеточных автоматов, обладающих хорошими характеристиками лавинного эффекта.
    (check this in PDF content)

  9. Start
    7171
    Prefix
    Рассмотрим эти графы применительно к задаче построения обобщённых клеточных автоматов, обладающих хорошими характеристиками лавинного эффекта. Граф получен эвристическим методом согласно алгоритму
    Exact
    [15]
    Suffix
    . Первоначально генерируется случайный граф , состоящий из вершин. После этого для уменьшения диаметра к графу итеративно применятся вариант алгоритма КерниганаЛина [16,17] , который удаляет 2 или более несмежных ребра и заменяет их новыми, таким образом, что граф остается регулярным.
    (check this in PDF content)

  10. Start
    7347
    Prefix
    Граф получен эвристическим методом согласно алгоритму [15]. Первоначально генерируется случайный граф , состоящий из вершин. После этого для уменьшения диаметра к графу итеративно применятся вариант алгоритма КерниганаЛина
    Exact
    [16,17]
    Suffix
    , который удаляет 2 или более несмежных ребра и заменяет их новыми, таким образом, что граф остается регулярным. При этом множество заменяемых ребер не пересекается с множеством новых ребер, т.е. .
    (check this in PDF content)

  11. Start
    7693
    Prefix
    При этом множество заменяемых ребер не пересекается с множеством новых ребер, т.е. . Это продолжается до тех пор, пока не достигнут целевой диаметр или другие изменения невозможны. Граф =390 был впервые рассмотрен в работе
    Exact
    [18]
    Suffix
    . Для его построения был использован вариант метода распределения меток (voltage assignment) [19]. Предварительно рассмотрим конечный, неориентированный граф который может содержать петли, кратные ребра и полуребра.
    (check this in PDF content)

  12. Start
    7787
    Prefix
    Это продолжается до тех пор, пока не достигнут целевой диаметр или другие изменения невозможны. Граф =390 был впервые рассмотрен в работе [18]. Для его построения был использован вариант метода распределения меток (voltage assignment)
    Exact
    [19]
    Suffix
    . Предварительно рассмотрим конечный, неориентированный граф который может содержать петли, кратные ребра и полуребра. Полуребрами графа называются ребра, имеющие только одну инцидентную вершину [18].
    (check this in PDF content)

  13. Start
    7985
    Prefix
    Предварительно рассмотрим конечный, неориентированный граф который может содержать петли, кратные ребра и полуребра. Полуребрами графа называются ребра, имеющие только одну инцидентную вершину
    Exact
    [18]
    Suffix
    . Согласно [21], можно представить ненаправленные ребра графа , которые не являются полуребрами, в виде пары противоположно направленных дуг, называемых стрелами (darts). Пусть – стрела, тогда обозначим стрелу, противоположно направленную к стреле (т.е.
    (check this in PDF content)

  14. Start
    8000
    Prefix
    Предварительно рассмотрим конечный, неориентированный граф который может содержать петли, кратные ребра и полуребра. Полуребрами графа называются ребра, имеющие только одну инцидентную вершину [18]. Согласно
    Exact
    [21]
    Suffix
    , можно представить ненаправленные ребра графа , которые не являются полуребрами, в виде пары противоположно направленных дуг, называемых стрелами (darts). Пусть – стрела, тогда обозначим стрелу, противоположно направленную к стреле (т.е.
    (check this in PDF content)

  15. Start
    8981
    Prefix
    На первоначальном этапе выбирается подходящий граф (степень его вершин должна быть равна степени вершин искомого графа; в случае построения графа =390 использовался дипольный граф
    Exact
    [18]
    Suffix
    ) и группа меток . Далее случайным образом происходит присваиваивание меток ребрам, петлям, и полуребрам графа . Согласно [18], группа меток не является абелевой и задается как полупрямое произведение абелевых групп.
    (check this in PDF content)

  16. Start
    9109
    Prefix
    На первоначальном этапе выбирается подходящий граф (степень его вершин должна быть равна степени вершин искомого графа; в случае построения графа =390 использовался дипольный граф [18]) и группа меток . Далее случайным образом происходит присваиваивание меток ребрам, петлям, и полуребрам графа . Согласно
    Exact
    [18]
    Suffix
    , группа меток не является абелевой и задается как полупрямое произведение абелевых групп. В процессе работы распределение, создающее в покрывающем графе петли и кратные ребра, сразу отвергается.
    (check this in PDF content)

  17. Start
    9682
    Prefix
    Если в пределах предварительно заданного количества попыток все сгенерированные распределения меток образуют покрывающие графы диаметра больше требуемого, выбирается новая группа. Если подходящее распределение найдено, то результат записывается и процедура останавливается. Согласно
    Exact
    [3]
    Suffix
    хорошие характеристики лавинного эффекта обобщенного клеточного автомата обеспечивают графы, обладающие как можно большим коэффициентом расширения. Задача нахождения значения коэффициента расширения является вычислительно трудной, поэтому, согласно [4], рассмотрим значение 2-го элемента спектра выбранных графов [3].
    (check this in PDF content)

  18. Start
    9932
    Prefix
    Согласно [3] хорошие характеристики лавинного эффекта обобщенного клеточного автомата обеспечивают графы, обладающие как можно большим коэффициентом расширения. Задача нахождения значения коэффициента расширения является вычислительно трудной, поэтому, согласно
    Exact
    [4]
    Suffix
    , рассмотрим значение 2-го элемента спектра выбранных графов [3]. Спектр представляет собой отсортированный по убыванию набор собственных чисел матрицы смежности графа. (3) Для выбранных графов .
    (check this in PDF content)

  19. Start
    9994
    Prefix
    Согласно [3] хорошие характеристики лавинного эффекта обобщенного клеточного автомата обеспечивают графы, обладающие как можно большим коэффициентом расширения. Задача нахождения значения коэффициента расширения является вычислительно трудной, поэтому, согласно [4], рассмотрим значение 2-го элемента спектра выбранных графов
    Exact
    [3]
    Suffix
    . Спектр представляет собой отсортированный по убыванию набор собственных чисел матрицы смежности графа. (3) Для выбранных графов .
    (check this in PDF content)

  20. Start
    10518
    Prefix
    Таким образом, полученные значения , согласно (4), являются, близкими к минимальным. Это означает, что выбранные графы является хорошими расширителями среди графов такого порядка. Характеристики лавинного эффекта для выбранных автоматов В работах
    Exact
    [1-7]
    Suffix
    так же было введено понятие интегральной характеристики лавинного эффекта для обобщенных клеточных автоматов. Рассмотрим два идентичных обобщенных клеточных автомата и Обозначим векторы их ячеек соответственно и .
    (check this in PDF content)

  21. Start
    10928
    Prefix
    Вектор начального заполнения будет различаться в одном разряде. Не нарушая общности будем считать, что номер ячейки, соответствующий такому разряду, равен нулю: (5) Интегральной характеристикой
    Exact
    [3-9]
    Suffix
    лавинного эффекта называется зависимость от номера такта количества различающихся ячеек у двух различных в одной ячейке начальных заполнений клеточного автомата: (6) Пространственной характеристикой лавинного эффекта назовем зависимость отношения от расстояния от вершины с номером 0 до самой дальней вершины, ячейка которой у двух автоматов не совпадае
    (check this in PDF content)

  22. Start
    11780
    Prefix
    Очевидно, что для выбранных автоматов стоит рассматривать усредненное по достаточно большому количеству начальных заполнений значение интегральной и пространственной характеристик лавинного эффекта: . Начиная с некоторого , выполняется и при . Чтобы обеспечить хорошие статистические свойства выходной последовательности необходимо, чтобы , а ,
    Exact
    [3]
    Suffix
    . Локальную функцию связи для всех клеточных автоматов будем выбирать согласно [4] На рисунках ниже приведены графики усредненных значений интегральных характеристик и пространственных характеристик лавинного эффекта в зависимости от номера такта для 10000 пар различных начальных заполнений, различных в одной ячейке.
    (check this in PDF content)

  23. Start
    11862
    Prefix
    Начиная с некоторого , выполняется и при . Чтобы обеспечить хорошие статистические свойства выходной последовательности необходимо, чтобы , а , [3]. Локальную функцию связи для всех клеточных автоматов будем выбирать согласно
    Exact
    [4]
    Suffix
    На рисунках ниже приведены графики усредненных значений интегральных характеристик и пространственных характеристик лавинного эффекта в зависимости от номера такта для 10000 пар различных начальных заполнений, различных в одной ячейке.
    (check this in PDF content)

  24. Start
    12904
    Prefix
    Усредненная интегральная характеристика лавинного эффекта для графа Рис. 6. Усредненная интегральная характеристика лавинного эффекта для графа Полученные результаты в целом подтверждают результаты
    Exact
    [14]
    Suffix
    . Для графов клеточных автоматов малого размера и несмотря на малый диаметр выбранного графа и небольшое значение коэффициента , не получила подтверждение гипотеза 0 0,1 0,2 0,3 0,4 0,5 0,6 0 2 4 6 8 10 12 14 16 Шаг значении .
    (check this in PDF content)

  25. Start
    13545
    Prefix
    Само значение 10, значительно превосходит значение диаметра, что говорит о недостаточно хороших рассеивающих свойствах автомата. Это может быть связано с малым порядком выбранных графов и малым размером окрестности автомата. В работах
    Exact
    [10,11]
    Suffix
    были получены схожие значения интегральной характеристики лавинного эфекта для обобщенных клеточных автоматов большего размера с окрестностью 4. Обобщенный клеточный автомат на основе графа показал хорошие характеристики лавинного эффекта уже при 5.
    (check this in PDF content)