Конкурс aes и блочная криптосистема Rijndael 44
Скачать 0.88 Mb.
|
В выражении (4.5) использовано предположение о равновероятности ключей. Найдем µ §. По формуле полной вероятности µ §. Учитывая, что µ §, получаем: µ §, при µ §.„S (4.6) На рис. 4.1 представлен граф совершенно стойкой криптосистемы. Рис. 4.1. Граф совершенно стойкой криптосистемы Совершенно стойкие криптосистемы, характеризуются следующими свойствами: каждое открытое сообщение µ § связывается с криптограммой µ § только одной линией; все ключи равновероятны. 4.2. Идеально стойкие криптосистемы Криптосистема включает в себя два статистических выбора: выбор сообщения и выбор ключа. Можно измерять количество информации, создаваемой при выборе сообщения, через энтропию [5,10,13]: µ §. (4.7) Суммирование производиться по всем сообщениям. Аналогично, неопределенность, связанная с выбором ключа определяется выражением: µ §. (4.8) В совершенно стойких криптосистемах количество информации в сообщении равно самое большоеµ §, где µ § - число открытых сообщений (эта величина достигается для равновероятных сообщений). Эта информация может быть скрыта полностью лишь тогда, когда неопределенность ключа не меньше µ §. Это является первым примером общего принципа, который будет часто встречаться ниже: существует предел, которого нельзя превзойти при заданной неопределенности ключа ЁC количество неопределенности, которое может быть введено в решение, не может быть больше, чем неопределенность ключа. Предположим теперь, что, например, для английского текста используется шифр простой замены и что перехвачено определенное число, скажем µ §, букв зашифрованного текста. Если µ § достаточно велико, то почти всегда существует единственное решение задачи криптоанализа, т.е. единственная последовательность, имеющая смысл на английском языке, в которую переводится перехваченный материал с помощью простой подстановки. Для меньших N шансы на не единственность решения увеличиваются; и для определенных малых значений µ §, вообще говоря, будет существовать некоторое число подходящих отрывков осмысленного английского текста. При µ §=1, очевидно, возможна любая буква открытого текста и апостериорная вероятность любой буквы будет равна ее априорной вероятности. Для одной буквы система является совершенно стойкой. В теории связи показано [10,13], что естественной математической мерой неопределенности того, что действительно было передано, при условии, что известен только искаженный шумом вариант ЁC принятый сигнал, является условная энтропия передаваемого сигнала при условии, что принятый сигнал известен. Эта условная энтропия носит название ненадежности. С криптографической точки зрения криптосистема почти тождественна системе связи при наличии шума. На сообщение действует некоторый статистический элемент (криптосистема к выбранным ключом). В результате получается криптограмма, подлежащая дешифрованию. Основное различие заключается в следующем: во-первых, в том, что преобразование при помощи шифра имеет обычно более сложную природу, чем возникающее за счет шума в канале; и, во-вторых, ключ в секретной системе обычно выбирается из конечного множества, в то время как шум в канале чаще является непрерывным, выбранным по существу из бесконечного множества. Учитывая эти соображения, естественно использовать ненадежность в качестве теоретической меры секретности. Следует отметить, что имеются две основные ненадежности: ненадежность ключа и ненадежность сообщения. Они будут обозначаться через µ §и µ §, соответственно. Их величины определяются соотношениями: µ §, (4.9) µ §. (4.10) где µ §, µ § - совместные вероятности ключа и криптограммы и сообщения и криптограммы, соответственно; µ §, µ § - апостериорные вероятности ключа и сообщения при перехваченной криптограмме. В (4.9) и (4.10) суммирование осуществляется по всем возможным ключам и сообщениям, соответственно, а также по криптограммам определенной длины µ §. Таким образом, µ § и µ § являются функциями числа µ §, т.е. числа перехваченных символов криптограммы. Если ненадежность равна нулю, следует, что одно сообщение (или ключ) имеет единичную вероятность, а все другие - нулевую. Этот случай соответствует полной осведомленности криптоаналитика. Постепенное убывание ненадежности с ростом N соответствует увеличению сведений об исходном ключе или сообщении. В совершенно стойких криптосистемах для сообщений неограниченной длины требуется ключ бесконечного объема. Если использовать ключ конечного объема, то ненадежности ключа и сообщения, вообще говоря, будут стремиться к нулю, хотя это и не обязательно. На самом деле можно удерживать значение µ § равным ее начальному значению µ §. Тогда, независимо от того, сколько зашифрованного материала перехвачено, единственного решения не будет, а будет много решений со сравнимыми по величине вероятностями. Определим идеально стойкую криптосистему как такую, в которой величины µ § и µ § не стремятся к нулю при µ §. Строго идеально стойкая криптосистема - это такая криптосистема, в которой величина µ § остается равной µ §. Неформально, строгая идеальность означает, что количество решений криптограммы равно количеству различных ключей и все решения равновероятны. Примером строго идеальной криптосистемы может служить простая подстановка, примененная к искусственному языку, в котором все буквы равновероятны и последовательные буквы выбираются независимо. В этом случае µ §=µ § и µ § растет линейно по прямой с наклоном µ §, где µ § - мощность алфавита, до тех пор, пока она не пересечет линию µ §, после чего она остается равной этой константе. Из сказанного выше очевидно, что одной из важнейших характеристик языка является его избыточность. Избыточность языка ЁC это количественная мера взаимной зависимости символов и их неравновероятности. Избыточность языка определяется как: µ §, (4.11) где µ § - энтропия на букву сообщения. Таким образом, на основании рассмотренного можно ввести понятие расстояния единственности криптосистемы. Пусть рассматривается криптосистема и µ § - энтропия ключа. Пусть µ § - избыточность шифруемого сообщения, а µ § - длина сообщения, такая, что µ §, т.е. при этой длине перехваченной криптограммы ключ почти однозначно восстановлен. Тогда справедливо неравенство: µ §. (4.12) Число µ § называется расстоянием единственности криптосистемы. Анализ неравенства (4.12) позволяет сделать следующие выводы: для восстановления ключа с высокой вероятностью достаточно перехватить µ § символов криптограммы; если значение избыточности µ §=0, то ключ никогда не будет определен, так как µ §; с практической точки зрения требуется менять ключ криптосистемы задолго до достижения µ §; для уменьшения µ § требуется преобразовывать исходный текст (например, использовать сжимающее кодирование), так как в этом случае значение µ § уменьшается, а энтропия преобразованного текста не изменяется. Оценку расстояния единственности криптосистемы можно использовать при ее разработке. 4.3. Практическая стойкость криптосистем Вопрос о практической стойкости, поставленный К.Шенноном, формулируется так: «Надежна ли криптосистема, если криптоаналитик располагает ограниченным временем и ограниченными вычислительными возможностями для анализа перехваченных криптограмм?». С одной стороны, криптосистема должна обеспечивать надежную защиту информации, с другой стороны, должна быть удобна с точки зрения технической реализации и эксплуатации. Так как криптосистемы, обеспечивающие идеальную стойкость, в большинстве случаев практически неприменимы, то вопрос относиться прежде всего к криптосистемам, использующим ключи ограниченного размера и способным обрабатывать большие объемы информации. По К.Шеннону, практически стойкая криптосистема по своим свойствам должна быть близка к идеальным криптосистемам. Например, высокая стойкость шифра гаммирования обеспечивается при использовании шифрующей последовательности, близкой по своим свойствам к равномерно распределенной случайной последовательности, поэтому криптографические свойства шифра гаммирования определяется свойствами используемого генератора гаммы. Системный подход к оценке стойкости криптосистемы подразумевается определенную детализацию понятия стойкости криптосистемы. В результате этой детализации формируется ряд критериев математического и технического характера, которым должна удовлетворять стойкая криптосистема. Основной количественной мерой стойкости криптосистемы является вычислительная сложность решения задачи дешифрования. Вычислительная сложность определяется несколькими характеристиками. Предположим, перед криптоаналитиком поставлена задача дешифрования криптосистемы µ § по набору криптограмм µ §, µ §. Пусть µ § - класс применимых к криптосистеме µ § алгоритмов дешифрования, которыми располагает криптоаналитик. При этом криптоаналитик рассматривает как вероятностное пространство µ § элементарных событий множество пар ключей и открытых текстов, если открытые тексты неизвестны, или множество ключей, если открытые тексты известны. Для алгоритма µ § обозначим через µ § среднюю трудоемкость его реализации, измеряемую в некоторых условных вычислительных операциях. При этом величина трудоемкости обычно усредняется по множеству µ §. Одной из основных характеристик практической стойкости криптосистемы µ § является средняя трудоемкость µ § дешифрования, определяемая как µ §. (4.13) При этом важно отметить следующее [11,13]. Существуют алгоритмы дешифрования, определенные не на всем вероятностном пространстве µ §, а лишь на некоторой его части. Кроме того, некоторые алгоритмы дешифрования устроены так, что их реализация приводит к успеху не на всей области определения, а лишь на некотором ее подмножестве. Поэтому к важнейшим характеристикам алгоритма дешифрования µ § необходимо отнести не только его трудоемкость, но и надежность алгоритма дешифрования µ §, под которой понимается средняя доля информации, дешифруемой с помощью алгоритма µ §. Если надежность алгоритма дешифрования мала, то с точки зрения криптографа он является неопасным, а с точки зрения криптоаналитика неэффективным. Таким образом, при получении оценки (4.13) целесообразно рассматривать лишь те алгоритмы дешифрования, надежность которых велика. При этом для определения наилучшего алгоритма дешифрования криптосистемы µ § можно использовать различные критерии в зависимости от конкретных условий. Например, можно считать наилучшим алгоритм дешифрования µ §, для которого наименьшее значение принимает величина µ §. Эту величину можно интерпретировать как средние трудозатраты, необходимые для успешного дешифрования криптосистемы. Сложность дешифрования зависит от количественных и качественных характеристик криптограмм, которыми располагает криптоаналитик. Количественные характеристики определяются числом перехваченных криптограмм и их длинами. Качественные характеристики связаны с достоверностью перехваченных криптограмм (наличие искажений, пропусков и т.д.). По К. Шеннону, каждая криптосистема имеет объективную характеристику µ § - среднюю вычислительную сложность дешифрования (по всем криптограммам длины µ § и ключам). Величина µ § характеризует предельные возможности дешифрования криптосистемы при неограниченном количестве шифрматериала и абсолютной квалификации криптоаналитика. Оценивая стойкость криптосистемы, криптоаналитик получает верхние оценки предельной стойкости, так как практическое дешифрование использует ограниченное количество шифрматериала и ограниченный класс так называемых известных методов дешифрирования. Важной характеристикой криптостойкости криптосистемы является временная сложность ее дешифрования. Оценка временной сложности дешифрования криптосистемы подразумевается более детальную проработку реализации алгоритмов дешифрования с учетом характеристик вычислительного устройства, используемого для дешифрования. К таким характеристикам вычислительного устройства, реализующего алгоритмы дешифрования, относятся архитектура, быстродействие, объем и структура памяти, быстрота доступа к памяти и др. Следовательно, время дешифрования криптосистемы определяется имеющимся классом алгоритмов дешифрования µ § и вычислительными возможностями криптоаналитика. Выбор наилучшего алгоритма осложняется и тем, что различным вычислительным устройствам могут соответствовать различные наилучшие алгоритмы дешифрования. Вопрос о криптостойкости криптосистемы имеет некоторые особенности с точки зрения криптоаналитика и криптографа. Криптоаналитик атакует криптосистему, располагая конкретными интеллектуальными, вычислительными и экономическими ресурсами. Его цель - успешное дешифрование криптосистемы. Криптограф оценивает стойкость криптосистемы, имитируя атаку на криптосистему со стороны криптоаналитика противника. Для этого криптограф моделирует действия криптоаналитика, оценивая по максимуму интеллектуальные, вычислительные, технические и другие возможности противника. Цель криптографа ЁC убедиться в высокой криптостойкости разработанной криптосистемы. Используя понятие практической криптостойкости можно классифицировать криптосистемы по величине стойкости, или по продолжительности временного периода, в течение которого криптосистема с высокой надежностью обеспечивает требуемый уровень защиты информации. Кроме рассмотренных подходов к оценке стойкости криптосистем существуют еще ряд подходов [11]. Асимптотический анализ стойкости. Этот подход развивается теорией сложности вычислений. При исследовании криптосистемы оценка его стойкости увязывается с некоторым параметром криптосистемы, обычно это длина ключа, и проводится асимптотический анализ оценок стойкости. Считается, как правило, что криптосистема имеет высокую криптостойкость, если последняя выражается через длину ключа экспоненциально, и криптосистема имеет низкую криптостойкость, если стойкость выражается в виде многочлена от длины ключа. Оценка количества необходимого шифрматериала. Данный подход основан не на сложности вычислений при реализации дешифрования, а на оценке среднего количества материала, который необходимо проанализировать криптоаналитику для вскрытия криптосистемы. Оценка количества необходимого криптоаналитику шифрматериала представляет интерес с той точки зрения, что является нижней оценкой стойкости криптосистемы в смысле вычислительной сложности дешифрования. Стоимостный подход. Этот подход предусматривает оценку стоимости дешифрования криптосистемы. Особенно он актуален тогда, когда для дешифрования криптосистемы необходимо разработать и построить новый вычислительный комплекс. Стоимостный подход полезен с точки зрения сопоставления материальных затрат на дешифрования криптосистемы и ценности информации, защищаемой криптосистемой. В заключении необходимо отметить, что в связи с развитием вычислительных средств, а также прогрессом в области разработки методов дешифрования, требуется пересматривать оценки стойкости криптосистем. 4.4. Имитостойкость и помехоустойчивость криптосистем В предыдущих пунктах рассмотрены вопросы криптостойкости криптосистем. Криптостойкость, наряду с имитостойкостью и помехоустойчивостью, является составляющей классической триады требований к криптосистемам. Имитостойкость (imitation resistance) ЁC свойство криптосистемы, характеризующее способность противостоять активным атакам со стороны противника, целью которых является навязывание ложного сообщения, подмена передаваемого сообщения или изменение данных. Ложная информация считается навязанной, если она принята приемным устройством к исполнению. Предположим, что имеется связь между двумя абонентами А и В. Абонент А может в определенный момент времени отправить абоненту В криптограмму µ §, полученную криптосистемой µ §, µ §, на ключе µ §. До момента передачи канал связи «пуст», но абонент В вводит в криптосистему ключ µ § в ожидании криптограммы от абонента А. Возможности противника можно сформулировать в виде предположений: 1) противник знает действующий алгоритм криптопреобразования; 2) противник имеет доступ к каналу связи; 3) противник может считывать в канале любое сообщение; 4) противник может формировать и вставлять в канал связи любое сообщение; 5) противник может заменять передаваемое сообщение на любое другое; 6) все действия противник может выполнять мгновенно (противник располагает требуемыми техническими средствами); 7) противник не знает действующего ключа криптопреобразования. Рассмотрим виды имитации [1,2,11]. |
Похожие:
 | Программа по формированию навыков безопасного поведения на дорогах... Использование современных педагогических технологий: модульно – блочная технология с применением приемов работы «французских мастерских»,... |  | С. В. Тронин >10. 01. 2013 положение о районном конкурс Районный конкурс для педагогов на лучшую методическую разработку с использованием интерактивной доски (далее Конкурс) проводится... |
| 10 Олимпиада-конференция: научно-технический конкурс, конкурс технического... Оргкомитет, Методические комиссии, жюри, Экспертные комиссии | | Конкурс материалов «Информатизация системы образования» Положение... Конкурс материалов «Информатизация системы образования» (далее – Конкурс) проводится «Журналом руководителя управления образованием»,... |
| Конкурс дитячого малюнка "Охорона праці очима дітей" Стартує конкурс дитячого малюнка "Охорона праці очима дітей"01 марта 2012 года стартует конкурс детского рисунка «Мама и папа, берегите... | | Конкурс проводится в муниципальных образовательных организациях,... Областной конкурс «Лидер чтения – 2014 года» (далее Конкурс) проводится в рамках областного межведомственного культурного проекта... |
| Конкурс представлен работами в 4 номинациях: «Рисую космос» «Всероссийское педагогическое собрание» проведен конкурс работ педагогов и учащихся образовательных учреждений Воронежской области... | | Информация о проведении Месячника чеченского языка и литературы в... «Даймехкан 1алам», классные часы «Ненан меттах лаьцна дош», конкурс чтецов «Къона поэт», уроки – беседы о чеченском языке «Язык народа... |
| 4. Конкурс имеет два уровня: Первая Лига и Высшая Лига Фонд имени космонавта Павла Романовича Поповича в рамках реализации проекта “Дорога в Космос” проводит Ежегодный международный конкурс... | | Конкурс «Лучшее школьное методическое объединение 2014». Положение... Конкурс методических разработок урока в контексте требований фгос ООО для учителей русского языка и литературы «Современный урок:... |
| Конкурс проектных работ Конкурс исследовательских работ конкурс рефератов... Мау имц г. Томска, тгпу, маоу гимназия №18 г. Томска в феврале-марте 2013г проводят сетевую муниципальную научно-практическую конференцию... | | Урок конкурс Конкурс профессионального мастерства в группе пк-301 Слова мастера: Вы находитесь в преддверии конкурса профессионального мастерства по профессии «Кондитер» в группе пк-301, и почетное... |
| Конкурс слоганов о сквернословии 5-8 март стенд Конкурс презентаций «Сквернословие и здоровье» | | Конкурс руководитель результат «Вдохновение» 4б класс 21 уч-ся Всероссийский... |
| Конкурс Чтение наизусть Данный конкурс оценивается по пятибалльной системе | | Конкурс проводится в целях пропаганды среди молодежи здорового образа... «Добрая воля, здоровое сердце, чистая страна!» (далее – Конкурс), требования к участникам и работам Конкурса, порядок их предоставления... |
