КМЗИ-3. Алгебраические характеристики нелинейности отображения степень нелинейности, порядок аффинности, индекс аффинности
 Скачать 159 Kb.
|
|
Алгебраические характеристики нелинейности отображения: степень нелинейности, порядок аффинности, индекс аффинности. Больше информации: Фомичебник 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. Метод полного перебора ключей. Характеристики метода при различных условиях. Больше информации: Фомичебник 335 Метод полного перебора (тотального опробования) ключей заключается в последовательном переборе всех элементов ключевого множества с проверкой на истинность каждого значения. Надёжность метода составляет 100%, метод не требует памяти. Предположим, что для любого входного блока появление любого выходного блока равновероятно, а криптоаналитику известна пара шифртекст – открытый текст, длиннее расстояния единственности. Очевидно, что трудоёмкость метода не превосходит произведения трудоёмкости опробования на мощность ключевого множества. Математическое ожидание трудоёмкости опробования в данном случае составляет  . Для любого алфавита из более чем двух символов, эта величина лежит в промежутке от 1 до 2. Математическое ожидание количества ключей, требующих опробования составляет n/2ю Таким образом, средние затраты на полный перебор ключевого множества в данном случае составляют от n/2 до n.Если криптоаналитик располагает лишь некоторыми характеристиками открытого текста, надёжность метода снижается, а трудоёмкость возрастает в связи с необходимостью отбраковки «кандидатов в открытые тексты». Трудоёмкость выделения кандидатов составляет  , Трудоёмкость поиска коллизий (отбраковки) определяется по принципу «парадокса дней рождения» (с.339)Если криптосистема заведомо обладает эквивалентными ключами, трудоёмкость метода полного перебора сокращается в соответствии с количеством классов эквивалентности ключевого множества. Усиление свойства совершенства. Строгий лавинный критерий. Критерий распространения. Бент-функции. Больше информации: Фомичебник 209 Существуют более строгие критерии качества отображений, нежели признак совершенства. Строгий лавинный критерий требует, чтобы искажение одного бита входа вызывало равномерное вероятностное распределение искажений на значениях  , вектор a содержит единственную ненулевую координату. То есть, эта функция сбалансирована.Отображение удовлетворяет строгому лавинному критерию порядка r, если любые её координатные функции после фиксации произвольных r переменных удовлетворяют строгому лавинному критерию. Отображение удовлетворяет критерию распространения степени l, если каждая координатная функция отображения является сбалансированной. Вектор a имеет не более l ненулевых координат.Отображение удовлетворяет критерию распространения степени l порядка r, если каждая координатная функция c фиксацией произвольных r переменных отображения является сбалансированной. Вектор a имеет не более l ненулевых координат.Отображение называется бент-функцией, если оно удовлетворяет критерию распространения всех степеней. Линейной структурой называется вектор a, при котором  . Бент-функция не может иметь линейных структур.Степенью нелинейности Bf называется максимальная степень монома в её полиноме Жегалкина. Классификация методов криптоанализа. Методы криптоанализа на основе каталогов. Больше информации: Фомичебник 334,341 Методология: Методы опробования (алгоритмические) Алгебраические (аналитические) методы Статистические методы (частотный анализ) Методы по применимости: Универсальные Специальные Каталогом множества называется листинг элементов множества, упорядоченных по определённому признаку. Криптоаналитические методы, основанные на каталогах требуют больших объёмов и высокого быстродействия памяти. Криптоаналитическая атака на основе каталога ключей предусматривает использование каталога, хранящего пары (ключ – зашифрованный образец). При достаточном объёме памяти данный метод обладает 100% надёжностью, однако, его применение сильно ограничивается тем, что образец текста является фиксированным для одного каталога. Эффективный метод защиты от данной атаки – использование ключевых множеств больших мощностей. Криптоаналитическая атака на основе каталога криптограмм1 предусматривает использовании каталога, содержащего упорядоченныен криптограммы, созданные с использованием разных ключей на основании одного и того же открытого текста. Идея та же: восстановить хотя бы один ключ. Теоретическая и практическая стойкость шифров. Больше информации: Фомичебник 327,260 Стойкость шифра – способность противостоять атакам криптоаналитика (попыткам определения ключа или открытого текста). Рассматривается совершенная и практичесаая стойкость. Практическая стойкость – способность противостоять атакам криптоаналитика, обладающего реальными материальными и вычислительными возможностями в течение ограниченного времени. Теоретическая (совершенная) стойкость – способность противостоять атакам криптоаналитика, обладающего неограниченными материальными и вычислительными возможностями; при применении совершенно стойких шифров не создаётся никаких вероятностных связей между открытым и закрытым текстом. Основные подходы к оценке стойкости и основные характеристики стойкости. Больше информации: Фомичебник 327 Основные подходы: Системный и асимптотический анализ трудоёмкости дешифрования1 Анализ количества необходимого шифрматериала2 Анализ стоимости дешифрования3 Характеристики стойкости: Средняя (максимальная) трудоёмкость дешифрования Амимптотические оценки сложности дешифрования Стоимость дешифрования Классификация методов криптоанализа. Методы криптоанализа, использующие каталоги. Больше информации: Фомичебник 334,341 Методология: Методы опробования (алгоритмические) Алгебраические (аналитические) методы Статистические методы (частотный анализ) Криптоаналитическая атака на основе каталога ключей предусматривает использование каталога, хранящего пары (ключ – зашифрованный образец). При достаточном объёме памяти данный метод обладает 100% надёжностью, однако, его применение сильно ограничивается тем, что образец текста является фиксированным для одного каталога. Эффективный метод защиты от данной атаки – использование ключевых множеств больших мощностей. Криптоаналитическая атака на основе каталога криптограмм1 предусматривает использовании каталога, содержащего упорядоченныен криптограммы, созданные с использованием разных ключей на основании одного и того же открытого текста. Идея та же: восстановить хотя бы один ключ. Метод «Встреча в середине атаки» Больше информации: Фомичебник 347 Метод «встречи в середине атаки», также известный как «метод согласования» – один из метода опробования ключей, основанный на декомпозиции функции шифрования таким образом, чтобы каждая из образовавшихся частей не зависела существенно ото всех элементов ключа. Метод реализуется в два этапа. Условия. Итеративный симметричный блочный шифр, раундовые ключи независимы. Этап 1: Инициализация памяти. Последовательность раундов шифрования разбивается на две последовательности. Вычисляется промежуточная криптограмма, получаемая пропусканием открытого блока x через первую последовательность. При этом в памяти фиксируется результат шифрования и все раундовые ключи. Выполняется для всех возможных значений раундовых ключей. Смещение границы разделения последовательностей к началу снижает требования к памяти и несколько ускоряет данный этап, однако, на 2ом этапе вызывает большую трудоёмкость (не имеет прямого отношения к общей трудоёмкости метода). Этап 2: Оперативный этап. Тот же блок промежуточного шифрованного текста вычисляется путём применения обратных раундовых преобразований, соответствующих второй последовательности, при фиксированном наборе раундовых ключей. Если полученное значение совпадает с одним из полученных на первом этапе, совокупность соответствующих раундовых ключей относится к кандидатам на истинные. Позже эти ключи проходят отбраковку по другим критериям (к примеру, проверяются для других блоков шифртекста). Трудоёмкость1 атаки составляет (r+2)*2^(n/2). Распределение ключей с использованием симметричного шифрования. Двухсторонние и трёхсторонние протоколы. Больше информации: Фомичебник 241 Двухсторонние протоколы: Простой протокол. Пользователь А отправляет пользователю Б криптограмму, содержащую сеансовый ключ и метку вермени. Криптограмма шифруется при помощи предварительно распределённого ключа шифрования сеансовых ключей. Протокол с аутентификацией. А отправляет Б случайное число. Б шифрует это число на ключе шифрования сеансовых ключей. В криптограмму также помещается сеансовый ключ и уникальный идентификатор пользователя Б. Криптограмма отправляется пользователю А. Протокол с двухсторонней аутентификацией. Аналогичен предыдущему протоколу, но здесь каждая из двух сторон генерирует случайное число и каждая из двух сторон генерирует компоненты, из который вычисляется общий сеансовый ключ (в предыдущем протоколе ключ выбирала одна сторона) Трёхсторонний протокол Трёхсторонний протокол вовлекает двоих участников информационного обмена, а также Центр генерации и рапределения ключей (ЦГРК). В ответ на запрос пользователя А об установлении связи с Б генерируется два пакета шифрованных данных: один содержит сеансовый ключ, зашифрованный для А, друго – сеансовый ключ и идентификатор А, зашифрованные для Б. Все пакеты отправляются А. А расшифровывает свой ключ и направляет второй пакет Б. Б, тем самым, убеждается в подлинности А и получает сеансовый ключ. Ключевой протокол, использующий модули безопасности. Модулем безопасности называется аппаратное устройство, обеспечивающее защищённое хранение ключевого материала и криптографических функций. С помощью модуля безопасности можно увеличить безопасность схем передачи ключей. Все ключи передачи сеансового ключа шифруются мастер-ключом, прошитым в устройстве. При необходимости установления связи модуль расшифровывает соответствующий ключ передачи, генерирует сеансовый ключ и шифрует его. Ни ключи передачи сеансовых ключей, ни мастер-ключ никогда не покидают модуль безопасности в открытом виде. Аналогично происходит извлечение сеансового ключа из зашифрованного сообщения. Попытка физического воздействия на модуль безопасности приводит к необратимому разрушению хранящейся там информации. Аналитические методы. Составление и решение системы уравнений. Методы линеаризации. Линаризация с помощью опробования части переменных. Больше информации: Фомичебник 350 Аналитические методы криптоанализа подразумевают, что аналитику известен алгоритм шифрования и, возможно, некоторое количество пар открытый текст – шифрованный текст. Задачи криптоанализа решаются посредством составления и решения систем уравнений, в которые ключ входит как набор неизвестных компонент, а в качестве известных компонент выступают известные данные (в частности, имеющийся криптоматериал и параметры криптосистемы). Составленные системы можно хранить в памяти в форме АНФ1. Трудоёмкость решения системы не меньше количества шифрматериала, использованного при её составлении. Как правило, эта величина существенно больше2. Нелинейные системы, которые очень часто используются в криптографии, можно при определённых условиях свести к линейным системам, которые значительно лучше изучены, проще и быстрее решаются. Этот процесс называется линеаризацией. Линеаризация с помощью опробования функций и переменных состоит в замене исходной нелинейной системы на линейную, множество истинных решений которой включает в себя решения исходной системы. Если порядок аффинности исходной функции равен r, значит, можно заменить нелинейное отображение на систему из r уравнений, объединение решений который даст в результате решение нелинейной системы. При использовании метода оказывается затруднительно построить эту систему. Метод формального кодирования. Больше информации: Фомичебник 231 Метод формального кодирования позволяет свести нелинейную систему уравнений к линейной путём замены всех мономов ранга 2 и выше на новые переменные. Полученная система будет являться линейной, однако, она будет содержать больше переменных, некоторые из которых алгебраически зависимы. Оказывается выгодно после решения системы линейных уравнений произвести отбраковку ложных решений. Для этого применяется функция fz(x1….xn) (возможно, частично определённая). Функция задаётся на множестве «заменяющих переменных» и на выходе даёт значение коэффициента соответствующего монома. Для выполнения критерия, эта функция должна доопределяться монотонно. Теорема о понижении степени нелинейности уравнения с помощью умножения на функцию Метод Хеллмана опробования ключей. Больше информации: Фомичебник 343 Метод Хеллмана – метод опробования ключей. Является универсальным, но эффективен далеко не всегда. Создан для криптоанализа блочных шифров типа DES. Задача: найти ключ шифрования по паре открытый текст – шифрованный текст. Первый этап: Предварительный. Выбираются параметры атаки: число ключей r и число итераций предварительного этапа m Выбирается r ключей. Каждый из ключей подвергается m раз рекурсивному преобразованию  . Из полученной цепочки берутся только первое и последнее значения. Полученный список упорядочивается по последнему значению. Здесь  – некоторое преобразование  .Второй этап: Поиск неизвестного ключа. Преобразование применяется к шифртексту. Если полученное значение обнаружено в построенном списке, предыдущий за ним (по итерациям) элемент списка объявляется кандидатом в ключи. Для того, чтобы найти его, придётся повторить вычисления предварительного этапа. Если же совпадений не обнаружено, с помощью функций f(a, (b0)) вычисляется b1, (b1) сравнивается со списком, но кандидаты в ключи – уже результаты 3й с конца итерации подготовительного этапа, и т.д.Полученные кандидаты в ключи отбраковываются альтернативными методами. Надёжность и трудоёмкость – в Фомичебнике 345. Статистический (корреляционный) метод определения начального заполнения генератора Гёффе. Больше информации: Фомичебник 314,367 Суть генератора Гёффе – существует два региста сдвига, генерирующих знаки гаммы. Выход третьего ЛРС определяет, какой из двух знаков отправляется на выход генератора. Анализ комбинирующей функции генератора Гёффе показывает, что  обладает «удачным» линейным приближением  , совпадающее с данной функцией в 75% случаев. Фиксируя всевозможные значения начального вектора ЛРС1, можно, изучая статистику выхода, судить о его истинности.Число неэквивалентных ключей-коммутаторов в схеме типа «накопитель-коммутатор-функция усложнения» Приближение булевых функций. Понятие о статистических методах анализа. Статистические (вероятностные) методы – семейство методов криптоанализа, характеризующееся применением в криптологии методов теории вероятности и математической статистики посредством введения вероятностных мер и рассмотрения объектов криптосистемы как случайных. Метод поиска линейной подсистемы Статистические методы анализа. Решение систем уравнений со случайной правой частью. Принцип балансирования Т-П-Н. Вероятностные методы криптоанализа. Дифференциальный криптоанализ. Метод, использующий каталог функций. 1 Фомичебник 327,330 2 Фомичебник 331 3 Фомичебник 332 1 Фомичебник 343 1 Фомичебник 327,330 2 Фомичебник 331 3 Фомичебник 332 1 Фомичебник 343 1 Фомичебник 348 1 Подробнее о трудоёмкости вычисления: Фомичебник 351 2 Подробнее о трудоёмкости решения: Фомичебник 353 |