Конкурс aes и блочная криптосистема Rijndael 44
Скачать 0.88 Mb.
|
1) на основе имеющейся криптограммы µ § и соответствующего ей открытого текста µ § составляется система уравнений относительно µ §: µ §, µ §, (3.1) полным перебором всех возможных значений ключевого параметра находится некоторое множество решений µ §; 2) если количество найденных решений µ §, то считается что истинное значение ключевого параметра определено, если µ § (несколько осмысленных открытых текстов), то определено подмножество значений искомого ключевого параметра и в этом случае целесообразно увеличить количество уравнений в системе. Если считать проверку одного варианта ключа µ § в выражении (3.1) за одну операцию, то полный перебор ключей потребует µ § операций. Пусть ключ в алгоритме шифрования выбирается случайно и равновероятно из множества µ §. Тогда с вероятностью µ § трудоемкость метода полного перебора равна 1. Это происходит в том случае, когда случайно выбран ключ, расположенный в нашем порядке на первом месте. Поэтому естественно в качестве оценки трудоемкости метода взять математическое ожидание числа шагов в переборе до попадания на использованный ключ. Пусть случайная величина µ § - число опробований включительно до момента обнаружения использованного ключа. При µ § случайные величины µ §1, если использованный ключ находиться в порядке на месте µ § и µ §0 в противном случае. Тогда: µ §. (3.2) Если считать, что все ключи расположены в установленном порядке, то процедуру равновероятного выбора ключа можно представить как равновероятный выбор числа µ § в последовательности натуральных чисел µ §. Тогда µ § для любого µ §. Подставляя полученное значение в (3.2) имеем: µ §. (3.3) При больших µ § можно приблизительно считать, что µ §. Например, для криптосистемы DES µ §, тогда средняя трудоемкость полного перебора µ §. При использовании современных вычислительных систем, среднее время взлома шифра Цезаря составляет µ § секунды, а шифра Вернама - µ § лет. Метод полного перебора допускает распараллеливание. Один из способов распараллеливания заключается в том, что множество натуральных чисел µ § разбивается на непересекающиеся подмножества µ §. Система из µ § вычислительных машин перебирает ключи так, что µ §-ая машина осуществляет перебор ключей из множества µ §, µ §. Система прекращает работу, если одна из вычислительных машин определила ключ. Например, если одна вычислительная машина опробует ключ за µ § секунд, то для того чтобы найти ключ криптосистемы DES полным перебором за 24 часа требуется µ § вычислительных машин. 3.3. Методы бесключевого чтения При рассмотрении поточных криптосистем гаммирования были определены требования к гамме. Нарушение этих требований дает противнику возможность реализовать криптоатаку на криптосистему. Рассмотрим некоторые методы криптоанализа криптосистем гаммирования не требующие определения ключа [11]. Метод чтения в колонках реализует способ восстановления текста, зашифрованного неравновероятной гаммой. Суть метода состоит в следующем. Пусть µ § есть вероятность использования знака µ § в гамме, причем полагаем, что не все вероятности µ § равны µ §, где µ § - длина гаммы. Без ущерба для общности положим µ §, µ §, µ §. В µ §-м такте шифрованию подверглась одна из µ § следующих букв открытого текста, µ §: µ §, µ §, ЎK, µ §. (3.4) Открытый текст может быть получен подбором µ §-го знака в µ §-й колонке табл. 3.1 (элементы таблицы рассматриваются по modµ §, где µ § - мощность алфавита). Таблица 3.1. Таблица дешифрования µ §µ §ЎKµ §ЎKµ §0µ §ЎKµ §ЎKµ §1µ §-1ЎKµ §-1ЎKµ §-1ЎKЎKЎKЎKЎKЎKµ §µ §ЎKµ §ЎKµ § Знаки в каждой колонке упорядочены по вероятности их использования в открытом тексте. Это облегчает чтение в колонках, т.к. «читаемый текст» с повышенной вероятностью расположен в верхних строках таблицы. В случае, когда все µ §>0, но при этом имеют разные значения при составлении таблицы необходимо исключить из рассмотрения µ § наименее вероятных знаков гаммы. В этом случае существует ненулевая вероятность потери истинного решения, т.е. исходного открытого текста. Применение данного метода тем успешнее, чем меньше высота колонок µ §, характеризующая многозначность решения задачи. При µ § близких к µ §, чтение в колонках теряет смысл, т. к. табл. 3.1 может содержать большое количество осмысленных, но и взаимно противоречивых открытых текстов. Данный метод может быть использован и в случае, когда текст зашифрован периодической гаммой. Пусть дана криптограмма µ §. Известен период ключевой последовательности µ §. Сформируем две подпоследовательности исходной криптограммы: µ § Будем полагать, что открытыми текстами, подлежащими шифрованию, являются содержательные тексты с известными вероятностями букв алфавита µ §, µ §, где µ § - номер буквы алфавита. Также будем считать, что на множестве µ § задано равномерное распределение, т.е. ключом является реализация выборки объемом µ § из равномерного распределения µ §. Тогда вероятность того, что µ §-я и (µ §)-я буквы открытого текста были равны соответственно, µ § и µ §, при условии, что µ §-я и (µ §)-я буквы криптограммы равны соответственно, µ § и µ § определяется выражением: µ §. (3.5) Так как в рассматриваемой криптосистеме множество ключей задано латинским квадратом, следовательно, используемый ключ однозначно определен любым переходом в этой замене. Если числитель (3.5) не равен нулю, то справедливо равенство: µ §. (3.6) Для каждой пары µ § и µ § букв исходной криптограммы упорядочим в соответствии с убыванием полученных значения условных вероятностей (3.6) пары букв открытого текста µ § и µ §. Построив такие колонки для каждого µ §, в результате получаем таблицу (см. табл. 3.2), в которой верхние пары имеют большую условную вероятность, чем нижние. Буквы искомого содержательного текста будут находится вероятнее всего в первых строках и задача сводится к подбору таких пар букв, чтобы в результате получался читаемый текст. Таблица 3.2. Таблица дешифрования µ §ЎKµ §ЎKµ §µ §ЎKµ §ЎKµ §ЎK.ЎKµ §ЎKЎK Период ключевой последовательности µ § может быть определен с помощью методов Фридмана [1]. Рассмотрим эти методы. Основаны методы на введенном У. Фридманом понятии индекса совпадения. Индексом совпадения последовательности µ § называется величина µ §, (3.7) где µ §, µ § - некоторая последовательность; µ § - частота встречаемости (число мест в тексте) µ §- буквы в последовательности µ §. Индекс совпадения µ § последовательности равен вероятности µ § совпадения символов данной последовательности на случайно и равновероятно выбранных местах µ § и µ §, причем µ § и µ §,µ §µ §. При µ § µ §, где µ § - вероятность µ §го символа из алфавита µ § в содержательных текстах. При случайном выборе последовательности µ § индекс совпадения µ § является случайной величиной, и представляет интерес подсчет его математического ожидания. Математическое ожидание индекса совпадения для открытых текстов определяется выражением: µ §. (3.8) Если реализация µ § представляет собой выборку из равномерного вероятностного распределения, то справедливо выражение: µ §. (3.9) Для любой последовательности µ § вероятность совпадения µ § двух случайно и равновероятно выбранных букв последовательности приблизительно равна: µ §. (3.10) Пусть µ § - криптограмма, полученная в результате шифрования случайного текста при случайном и равновероятно выбранном ключе. Тогда математическое ожидание индекса совпадения для криптограммы равно: µ §. (3.11) Для криптосистемы гаммирования с периодической гаммой, получаемого шифрованием открытого текста µ § с помощью равновероятного выбора ключа µ § из множества всех локально-периодических последовательностей µ § периода d и µ § справедливо: µ § (3.12) При µ § (т.е. µ §): µ § (3.13) Первый метод Фридмана состоит в том, что вычисляется индекс совпадения µ § для имеющейся криптограммы в соответствии с выражением (3.7) и затем его значение сравнивается с (3.13) при µ §. При достаточной близости индекса совпадения к одному из значений (3.13), при некотором µ §, предполагают, что период равен этому значению µ §. Первый метод Фридмана эффективен для µ §, т.к. значение µ § для фиксированного периода µ § совпадает со значениями целого ряда различных периодов ключевой последовательности. Второй метод Фридмана также основан на вычислении индекса совпадения. Суть второго метода Фридмана состоит в опробовании возможных периодов µ § по следующей схеме. Из исходной криптограммы µ § для предполагаемого периода µ § ключевой последовательности выписывается µ § подпоследовательностей: µ § (3.14) Для каждой подпоследовательности подсчитывается ее индекс совпадения µ §. Если все индексы совпадения в среднем близки к значению µ § (среднее значение индекса совпадения случайных криптограмм, полученных с помощью гамм периода 1), то принимают величину µ § за истинный период, в противном случае опробуется следующая величина периода. Второй метод Фридмана позволяет эффективно определять периоды µ §. Метод восстановления текстов, основанный на атаке с помощью вставки символа (insertion attack). Рассмотрим существо метода. Пусть открытый текст µ § с помощью гаммы µ §преобразуется в соответствии с уравнением шифрования: µ §, (3.15) в криптограмму µ §. Криптоаналитику известна криптограмма, но не известен открытый текст и гамма. Предположим, что криптоаналитик располагает еще одной криптограммой, полученной зашифрованием той же гаммой видоизмененного открытого текста, полученного из оригинального текста вставкой в некоторой позиции известного бита µ §. Пусть видоизмененный открытый текст имеет вид µ §, а соответствующая криптограмма µ § По двум криптограммам, начиная с момента вставки, можно определить и гамму и открытый текст: µ §, µ §; µ §, µ §; µ §, µ §, ЎK. Все вычисления выполняются по modµ §. Момент вставки символа µ § можно определить, сравнивая видоизмененную и оригинальную криптограммы. Если значение вставленного символа неизвестны, то можно реализовать подбор вариантов его значения. Для защиты от такого рода атак достаточно никогда не использовать одинаковые отрезки гаммы для повторного шифрования. 3.4. Методы криптоанализа с использованием теории статистических решений Рассмотрим симметричную криптосистему, криптоаналитику априорно известно: 1) криптографическое преобразование µ § с точностью до ключа µ §; 2) криптограмма µ § длинной n. Задача криптоаналитика состоит в оценке неизвестного параметра µ § криптографического преобразования µ §. Допущения (предположения) [10]: 1) исходный текст µ § представляет собой случайную последовательность с некоторым заданным дискретным распределением вероятностей µ §, µ §, µ §. 2) µ § - является детерминированной неизвестной величиной. Метод частотного криптоанализа базируется на реализации методов теории статистических решений, а именно, на методе максимального правдоподобия [10]. В соответствии с этим методом формируется функция правдоподобия: µ §, (3.16) где µ § - дискретное распределение крипто граммы Y в ситуации, когда значение ключа µ § фиксировано: µ § (3.17) Тогда: µ §. (3.18) Функция правдоподобия µ § позволяет судить, насколько правдоподобно получить криптограмму µ § при условии, что ключ равен µ §. На практике оперируют не самой функцией правдоподобия, а ее монотонным преобразованием, в частности логарифмом функции правдоподобия: µ §. (3.19) Для получения оценочного значения ключа требуется отыскать такое его значение, которое максимизирует значение функционала: µ §. (3.20) Рассмотрим применение частотного метода криптоанализа к криптосистеме Цезаря для двух случаев: 1) источник открытых сообщений представляет собой стационарный источник дискретных сообщений без памяти; 2) источник открытых сообщений представляет собой однородную цепь Маркова. Случай 1. Стационарный источник дискретных сообщений без памяти. Открытый текст представляется в виде: µ §. (3.21) Введем величину, имеющую смысл частоты встречаемости символа µ § в µ §: µ §, (3.22) где µ § - символ Кронекера, µ § - условие нормировки. Совместное n-мерное дискретное распределение вероятностей исходного текста имеет вид: µ §, (3.23) где µ § - распределение вероятностей для одного символа алфавита µ §. Тогда логарифм функционала правдоподобия имеет вид: µ § (3.24) Тогда: µ §. (3.25) Например, для криптосистемы Цезаря выражение (3.20) будет иметь вид: µ §. (3.26) Случай 2. Марковский источник открытых сообщений (однородная цепь Маркова). Открытый текст представляет собой реализацию однородной цепи Маркова, которая задана: - матрицей вероятностей переходов µ §; - вектором начального распределения вероятностей µ §. Введем в рассмотрение выражение для частот встречаемости биграмм µ §: µ §, (3.27) При этом должно выполняться условие нормировки µ §. Оценка ключа будет определяться в соответствии с выражением: µ §. (3.28) Например, для криптосистемы Цезаря оценка ключа будет иметь вид: µ §Точность решения задачи криптоанализа частотным методом, т.е. точность оценки µ § характеризуется вероятностью ошибки: µ §. (3.29) Алгоритм криптоанализа является состоятельным, если при увеличении длины криптограммы µ § вероятность ошибки стремиться к нулю µ §. Более сложные выражения для оценки ключа µ § получаются, если снять допущение о детерминированности ключа. Алгоритм криптоанализа в этом случае базируется на байесовском методе теории статистических решений и подробно описан в [10]. 3.5. Линейный криптоанализ Метод линейного криптоанализа разработан в 1993 году японским криптологом Митсуру Матсуи. В первоначальном виде этот метод сформулирован применительно к криптоанализу криптосистемы DES. В настоящее время создаются новые модификации этого метода [10]. Идея метода линейного криптоанализа основана на том, что существует возможность заменить нелинейную функцию криптографического преобразования ее линейным аналогом. Линейный криптоанализ базируется на знании криптоаналитиком пар «открытый текст - криптограмма», а также алгоритма шифрования. Будем считать, что при генерации исходного текста µ § случайные биты независимы и равновероятны µ §, µ §, µ §. Линейным статистически аналогом (или приближенным линейным аналогом) называется: µ §, (3.30) если вероятность µ §. Величина µ § называется эффективностью линейного аналога, а коэффициенты µ §, µ §, µ § - параметрами линейного аналога. По существу µ § характеризует степень линейности функции криптографического преобразования и имеет максимальное значение µ §. При применении метода линейного криптоанализа решаются две взаимосвязанные задачи [4,10]: 1) нахождение эффективного линейного статистического аналога и вычисление его вероятности; 2) определение ключа (или нескольких бит ключа) с использованием эффективного линейного статистического аналога. Практическая реализация метода линейного криптоанализа связана с реализацией следующих последовательных шагов. 1. Тщательно анализируется криптографическая функция и определяется множество линейных статистических аналогов. На этом шаге в первую очередь анализируются S-блоки функции усложнения µ §. Для этого необходимо для каждого S-блока сформировать таблицы значений µ §, где: µ § - номер S-блока. Значение µ § представляет собой количество совпадений суммы по mod2 некоторых битов входных данных с суммой по mod2 некоторых битов выходных данных. В ходе анализа прослеживаются все возможные комбинации двоичных векторов µ §. Каждая пара векторов используется в качестве маски, которая накладывается на возможные пары «вход-выход» S-блока. Эти маски указывают на биты входа и выхода, которые необходимо сложить по mod2, а затем сравнить полученные результаты. Далее проводится анализ полученных таблиц µ § и отыскивается такие значения µ §, для которых выполняется условие |
Похожие:
 | Программа по формированию навыков безопасного поведения на дорогах... Использование современных педагогических технологий: модульно – блочная технология с применением приемов работы «французских мастерских»,... |  | С. В. Тронин >10. 01. 2013 положение о районном конкурс Районный конкурс для педагогов на лучшую методическую разработку с использованием интерактивной доски (далее Конкурс) проводится... |
| 10 Олимпиада-конференция: научно-технический конкурс, конкурс технического... Оргкомитет, Методические комиссии, жюри, Экспертные комиссии | | Конкурс материалов «Информатизация системы образования» Положение... Конкурс материалов «Информатизация системы образования» (далее – Конкурс) проводится «Журналом руководителя управления образованием»,... |
| Конкурс дитячого малюнка "Охорона праці очима дітей" Стартує конкурс дитячого малюнка "Охорона праці очима дітей"01 марта 2012 года стартует конкурс детского рисунка «Мама и папа, берегите... | | Конкурс проводится в муниципальных образовательных организациях,... Областной конкурс «Лидер чтения – 2014 года» (далее Конкурс) проводится в рамках областного межведомственного культурного проекта... |
| Конкурс представлен работами в 4 номинациях: «Рисую космос» «Всероссийское педагогическое собрание» проведен конкурс работ педагогов и учащихся образовательных учреждений Воронежской области... | | Информация о проведении Месячника чеченского языка и литературы в... «Даймехкан 1алам», классные часы «Ненан меттах лаьцна дош», конкурс чтецов «Къона поэт», уроки – беседы о чеченском языке «Язык народа... |
| 4. Конкурс имеет два уровня: Первая Лига и Высшая Лига Фонд имени космонавта Павла Романовича Поповича в рамках реализации проекта “Дорога в Космос” проводит Ежегодный международный конкурс... | | Конкурс «Лучшее школьное методическое объединение 2014». Положение... Конкурс методических разработок урока в контексте требований фгос ООО для учителей русского языка и литературы «Современный урок:... |
| Конкурс проектных работ Конкурс исследовательских работ конкурс рефератов... Мау имц г. Томска, тгпу, маоу гимназия №18 г. Томска в феврале-марте 2013г проводят сетевую муниципальную научно-практическую конференцию... | | Урок конкурс Конкурс профессионального мастерства в группе пк-301 Слова мастера: Вы находитесь в преддверии конкурса профессионального мастерства по профессии «Кондитер» в группе пк-301, и почетное... |
| Конкурс слоганов о сквернословии 5-8 март стенд Конкурс презентаций «Сквернословие и здоровье» | | Конкурс руководитель результат «Вдохновение» 4б класс 21 уч-ся Всероссийский... |
| Конкурс Чтение наизусть Данный конкурс оценивается по пятибалльной системе | | Конкурс проводится в целях пропаганды среди молодежи здорового образа... «Добрая воля, здоровое сердце, чистая страна!» (далее – Конкурс), требования к участникам и работам Конкурса, порядок их предоставления... |
