Издательство «НАУЧНЫЕ ТЕХНОЛОГИИ»

ВВЕДЕНИЕ

В системах шифрования и идентификации к криптографическим функциям векторных пространств предъявляется требование совершенности, то есть зависимости каждой координатной функции от всех переменных [1]. Обобщениями свойства совершенности являются строгий лавинный критерий, критерии распространения, свойство «бент». Изучение совершенности криптографических функций — актуальная задача, так как в криптосистемах функции выбираются не случайно, а из отображений с рядом заданных свойств.

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

1. ПРИМИТИВНОСТЬ ГРАФОВ И НЕОТРИЦАТЕЛЬНЫХ МАТРИЦ

Для оценки свойства совершенности используется математический аппарат матриц и графов.

Матрицу M над полем действительных чисел называют положительной (неотрицательной), если положительны (неотрицательны) все её элементы, обозначают: M>0 (M³0). Квадратную 0,1-матрицу M называют примитивной, если M^t>0 при некотором натуральном t. Наименьшее натуральное g, при котором Mγ>0, называется экспонентом (показателем примитивности) матрицы M, обозначается expM.

Читать далее …

СПИСОК ЛИТЕРАТУРЫ:

1. Фомичев В.М. Методы дискретной математики в криптологии. // В. М. Фомичев. — М.: Диалог-МИФИ, 2010 — 424 с.

2. Берж К. Теория графов и её применение. М.: ИЛ, 1962г. — 320с.

3. Сачков В.Н., Тараканов В.Е. Комбинаторика неотрицательных матриц. — М.: ТВП, 2000. — 448 с.

4. Кяжин С.Н., Фомичев В.М. О примитивных наборах натуральных чисел // Прикладная дискретная математика, №2(16), 2012.

5. Wielandt H. Unzerlegbare nicht negative Matrizen // Math. Zeitschr. 1950. No. 52. P. 642-648.

6. Фомичев В.М. Оценки экспонентов примитивных графов // Прикладная дискретная математика, №2(12), 2011.

7. Когос К.Г., Фомичев В.М. Положительные свойства неотрицательных матриц // Прикладная дискретная математика, №4(18), 2012.

8. Кяжин С.Н., Фомичев В.М. Алгоритмы анализа примитивности ориентированных графов // Безопасность информационных технологий, №1, 2012.

9. Коренева А.М., Фомичев В.М. Об одном обобщении блочных шифров Фейстеля // Прикладная дискретная математика, №3(17), 2012.