Алгебраические характеристики нелинейности отображения: степень нелинейности, порядок аффинности, индекс аффинности.

Больше информации: Фомичебник 210.

Степень нелинейности функции векторных пространств – наибольшая из степеней нелинейности её координатных функций. Обозначение .

Функция называется сильно нелинейной, если все её координатные функции нелинейны.

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

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

Оценка сложности решения нелинейных булевых систем уравнений с использованием индекса аффинности и порядка аффинности отображения.

Метод дифференциального криптоанализа, его применение для определения ключа алгоритма DES.

Больше информации: Фомичебник 371.

Дифференциальный криптоанализ – метод определения ключа криптосистемы, использующий сопоставление различий пар значений открытого и шифрованного текста. Применяется, в основном, для блочных шифров и hash-функций.

Важная характеристика криптографической функции – матрица M, строки которой соответствуют всевозможным разностям исходных элементов, столбцы – всевозможным разностям образов элементов, на пересечениях стоят количества случаев, при которых данные пары разностей имеют место. Элементы на пересечениях называются дифференциальными характеристиками функции.

Недостатком метода является большая трудоёмкость построения матрицы M для функций над многомерными полями.

Применение к алгоритму DES. Пусть есть пара блоков открытого текста и , зашифрованных на ключе k Раундовые ключи: . Размерность векторного пространства: 32. Рассмотрим – разность между блоками текстов после первой итерации DES. . В частности, для ; для .

Пусть вероятность того, что выражение принимает нулевое значение равна (для любой итерации DES, величину считаем независимой для различных итераций).

Положим, что сумма блоков исходного текста равна (0,b). Тогда для 14 цикла шифрования вероятность того, что оценивается снизу вероятностью того, что И семикратно (итого 14 множителей для каждого цикла).

Тогда после 16 итерации с некоторой вероятностью имеем: . Это равенство раскладывается на систему 32 уравнений с 48 неизвестными. Система имеет в среднем 65.536 решений, собираемых из решений 8 подсистем, соответствующим S-боксам. Сложность решения систем пренебрежимо мала. После чего, оставшаяся часть ключа k угадывается перебором и проверяется на другом фрагменте текста. . Применимость: с. 374.

Идея метода линейного криптоанализа.

Перемешивающие свойства отображений и их композиций. Экспонент и субэкспонент системы матриц (матрицы).

Больше информации: Фомичебник 200

Под перемешиванием понимается распространение зависимости отдельной компоненты входного вектора на компоненты выходного вектора. Полное перемешивание входов – существенная зависимость каждой координатной функции ото всех компонент входного вектора.

Перемешивающий граф функции – двудоьный орграф, вершины которого – номера координатных функций и входных переменных, а рёбра указывают на существенную зависимость данной функции от данной переменной. Матрица смежности этого графа – перемешивающая матрица.

Функция называется совершенной, если все элементы матрицы перемешивания положительны.

Экспонентом системы матриц называется длина минимальной последовательности матриц из этой системы, последовательное перемножение элементов которой даёт положительную матрицу.

Субэкспонентом системы матриц называется длина минимальной последовательности матриц, для которй сумма произведений первой, первой и второй, первой*второй*третьей, и т.д. есть положительная матрица.

(Суб)экспонент матрицы есть (суб)экспонент системы матриц, включающей в тсебя только одну эту матрицу.

Субэкспонент не может превышать экспонент.

Метод последовательного опробования частей ключа шифра, использующий несовершенство преобразования.

Приближения нелинейных отображений. Метод статаналогов. Максимально нелинейные Bf.

Больше информации: Фомичебник 213

Предположим, что функции f и g имеют одинаковые входные и выходные множества. Функция g называется приближением (статистическим аналогом, статаналогом) функции f, если их требуемые свойства близки или совпадают, но функция g при этом проще поддаётся анализу/моделированию/реализации.

Расстояние между функциями – количество векторов, на которых значения функций различны. Обозначение: . Расстояние между множествами функций – наименьшее расстояние между двумя функциями из этих множеств.

Нелинейность функции – расстояние от функции до множества аффинных функций.

Функция называется максимально нелинейной, если ля её спектра Уолша ( ) выполняется: . Максимально нелинейная функция характеризуется максимальным значением нелинейности.

Корреляционно-иммунные и эластичные функции

Больше информации: Фомичебник 215

Функция f: Pn -> P называется корреляционно-иммунной порядка r, если функция f-l сбалансирована при любой линейной l, существенно зависящей не более, чем от r переменных. Наличие корреляционного иммунитета порядка r обозначается .

Сбалансированная функция f называется r-эластичной, если для неё имеет место .

Функция f: Pn -> Pm называется корреляционно-иммунной порядка r, если каждая её координатная функция обладает корреляционным иммунитетом порядка r.

Ключевая система шифра. Жизненный цикл ключей: генерация, рассылка, хранение, смена. Депонирование ключей.

Больше информации: Фомичебник 235

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

Первая стадия жизненного цикла ключа – генерация (или создание) ключа. На этом этапе стоит задача создания ключа, наиболее близкого к случайному, удовлетворяющего требованиям криптографической функции (длина, отсутствие заведомой слабости, прочие специфические требования криптосистем…). Генерация ключей осуществляется при помощи программных или аппаратных генераторов случайных чисел, либо датчиков случайных чисел. Все необходимые статистические тесты ключа также производятся на стадии генерации.

Рассылка ключей – этап жизненного цикла, на котором обеспечивается доставка ключей до потребителя. Самым важным вопросом здесь является сохранение секретности ключа (а вернее – баланса секретности, стоимости обслуживания и оперативности функционирования). Существует набор различных способов доставки: курьерская доставка, использование альтернативного защищённого канала связи или защищённая передача по открытому каналу, схема разделения секрета и передача по нескольким каналам параллельно. Целостность переданного ключа также проверяется на этом этапе.

Секретность ключа также важно обеспечивать на этапе хранения. Существует ряд широко известных методов хранения ключа (подробнее Фомичебник 240). Депонирование ключа – процесс, подразумевающий создание резервной копии ключа на случай его утери или повреждения.

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

Схема Блома (предварительного распределения ключей).

Больше информации: www.ru.wikipedia.org/wiki/Схема_Блома

Ссылка на Фомичебник: 246

Схема Блома предназначена для предварительного распределения ключевого материала среди участников защищённых взаимодействий.

Открытыми ключами пользователей являются уникальные вектора r, доступные в открытом виде для пользователей. Закрытыми ключами являются m+1 коэффициенты многочлена.

Сеансовым ключом является многочлен f(x,y)=+{a(ij)x(i)y(j)}. Для выработки ключа необходимо подставить в многочлен открытые ключи участников взаимодействия. Параметры x, y коммутативны.

Понятие практической стойкости криптосистемы. Подходы к оценке криптостойкости систем.

Больше информации: Фомичебник 327

Стойкость криптографической системы – способность противостоять атакам криптоаналитика (попыткам определения ключа или открытого текста). Рассматривается совершенная и практичесаая стойкость.

Практическая стойкость криптографической системы – способность противостоять атакам криптоаналитика, обладающего реальными материальными и вычислительными возможностями в течение ограниченного времени.

Стойкость количественно характеризуется вычислительной сложностью решения задачи дешифрования.

В применении к практической стойкости, по вычислительной стойкости криптосистемы делятся на системы временной стойкости и системы гарантированной стойкости. Граница между этими классами проводится в соответствии с «законом Мура».

Основные подходы:

1. Системный и асимптотический анализ трудоёмкости дешифрования¹

2. Анализ количества необходимого шифрматериала²

3. Анализ стоимости дешифрования³

Необходимые условия совершенства композиции преобразований.

Больше информации: Фомичебник 206

Полугруппа преобразований G не имеет признака совершенства, если мультиграф перемешивания не является сильно связным. Циклическая полугруппа не имеет признака совершенства, если образующее преобразование не обладает сильно связным графом.перемешивания.

Если мультиграф множества преобразований сильно связен, то преобразование g несовершенно, если его матрица перемешивания M(g) не положительна. В частности, несовершенно, если неположительная.

Понятие о криптографическом анализе.

Криптографический анализ – всестороннее исследование криптосистемы, в ходе которого оцениваются её криптографические характеристики.

Цель криптографического анализа при разработке системы: определение возможности и условий применения криптосистемы для защиты информации.

Цель криптоаналитика: установление возможности и условий, требуемых для вскрытия криптосистемы.

Криптоанализ системы:

1. Исследование свойств криптографических функций системы.

2. Разработка, моделирование и исследование методов вскрытия системы (криптоаналитических атак)

3. Разработка и обоснование рекомендаций по использованию системы.

Разновидности задач криптоанализа:

1. Известен выходной криптографический материал системы

2. Имеется экземпляр (математическая модель) криптографических функций

3. Имеются пары открытый текст – шифрованный текст.

Методология:

1. Методы опробования (алгоритмические)

2. Алгебраические (аналитические) методы

3. Статистические методы (частотный анализ)

Методы по применимости:

1. Универсальные

2. Специальные

Вероятностные методы криптографического анализа характеризуются надёжностью ниже 1.