Модели шифров и открытых текстов

Министерство образования и науки РФ

НЕГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

МОСКОВСКИЙ ИНСТИТУТ КОМПЛЕКСНОЙ БЕЗОПАСНОСТИ

Реферат

по дисциплине «Криптографическая защита информации»

на тему:

«Модели шифров и открытых текстов»

Выполнил:

Студент 3 курса  ОТЗИ

Каралин А.Н.

Проверил:

Москва  2012

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

ПРИНЦИПЫ ПОСТРОЕНИЯ БЛОЧНЫХ ШИФРОВ

ПОНЯТИЕ КРИПТОАНАЛИЗА. ВИДЫ КРИПТОАНАЛИЗА. ОБЩАЯ КЛАССИФИКАЦИЯ

МЕТОДЫ АНАЛИЗА АЛГОРИТМОВ БЛОЧНОГО ШИФРОВАНИЯ

ЗАКЛЮЧЕНИЕ

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

ВВЕДЕНИЕ

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

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

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

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

ПРИНЦИПЫ ПОСТРОЕНИЯ БЛОЧНЫХ ШИФРОВ

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

Как правило, алфавитом, на котором действует блочный шифр, является множество двоичных векторов-блоков открытого текста одинаковой длины (64, 128 и т. д.). Сама реализация преобразований столь больших алфавитов является сложной задачей, а использование преобразований с целью шифрования требует от них еще ряда специальных качеств.

К. Шеннон сформулировал общий принцип построения шифрующих преобразований — принцип "перемешивания". Суть его состоит в требовании, чтобы применение шифрующего преобразования к наборам аргументов, отличающихся в незначительном числе позиций, приводило к существенному изменению результата. Обеспечить выполнение этого требования в сочетании с простотой реализации конкретного отображения в общем случае представляется затруднительным. Поэтому К. Шеннон предложил реализовывать сложные преобразования в виде суперпозиции нескольких простых некоммутирующих отображений. Подход К. Шеннона, использующий итеративное построение преобразований, в настоящее время является магистральным путем синтеза блочных шифров.

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

Обычно используются базовые преобразования двух типов — сложные в криптографическом отношении локальные преобразования над отдельными частями шифруемых блоков и простые преобразования, переставляющие между собой части шифруемых блоков. В криптографической литературе первые преобразования получили название "перемешивающих", а вторые — "рассеивающих". Качественно можно сказать, что перемешивание усложняет восстановление взаимосвязи статистических и аналитических свойств открытого и шифрованного текстов, а рассеивание распространяет влияние одного знака открытого текста на большое число знаков шифртекста, что позволяет сгладить влияние статистических свойств открытого текста на свойства шифртекста. Следует отметить, что в данном случае перемешивание понимается в обычном смысле, а не как качественное свойство шифра, введенное К. Шенноном.

Алгоритм шифрования выполняет некоторое число циклов (итераций). Каждый цикл состоит в применении преобразований первого и второго типов. Такой принцип построения дает возможность реализовать каждый цикл шифрования с использованием однотипных узлов, а также выполнять расшифрование путем обработки данных в обратном направлении.

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

Получили распространение алгоритмы, в которых осуществляются преобразования над векторами, представляющими собой левую и правую половины содержимого регистра сдвига. Для построения таких алгоритмов часто используется кон­струкция, называемая сетью Фейстеля (Feistel Network) (см. рис. 1).

Рис. 1

Преобразование, реализуемое сетью Фейстеля в i-м цикле шифрования, имеет вид

где X — входной блок, разделенный на две половины X1, и Х2, a (Y1,Y2) — результат зашифрования блока X на ключе ki с помощью функции fi.

Алгоритм шифрования реализуется несколькими итерациями преобразования сети Фейстеля с использованием ключа k. При этом очередная (i-я) итерация использует в качестве входного блока X результат предыдущей итерации и ключ ki, вычисляемый определенным образом по ключу k.

Функция fi может зависеть или не зависеть от номера итерации.

Ценность преобразований подобного вида заключается в том, что даже если fi не является обратимой функцией, преобразование сети Фейстеля обратимо. В самом деле, из (1) сразу следует, что

ПОНЯТИЕ КРИПТОАНАЛИЗА. ВИДЫ КРИПТОАНАЛИЗА. ОБЩАЯ КЛАССИФИКАЦИЯ

Итак, теперь мы имеем представление о том, как строятся блочные шифры.

Рассмотрим конкретную ситуацию, чтобы понять суть криптоанализа, и попытаемся дать классификацию методам криптоанализа в целом.

Пусть две стороны, которые мы назовем законными участниками обмена информацией, пытаются наладить секретную связь. Отправитель шифрует с использованием блочного алгоритма E сообщение T, в результате у получателя окажется шифртекст T'. Связь между исходным текстом T, шифртекстом T' и алгоритмом зашифрования E может быть символически выражена с помощью следующей формулы: T' = E(T). Шифрованное сообщение T' передается отправителем получателю по каналу связи. Чтобы законный получатель мог ознакомиться с содержимым полученного сообщения, он должен предварительно его расшифровать, то есть применить к шифртексту T' алгоритм расшифрования D, в результате чего будет восстановлено исходное сообщение T. Таким образом, расшифрование данных осуществляется согласно уравнению T=D(T').

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

- дешифровать сообщение T', то есть получить соответствующий ему открытый текст T полностью или частично, или хотя бы сделать некоторые заключения о содержании перехваченного сообщения, опираясь на обнаруженные в нем закономерности;

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

Под раскрытием шифра понимают успешную реализацию хотя бы одной из указанных угроз. Первая угроза, если будет осуществлена, нарушит секретность сообщения, а вторая нарушит его подлинность. Степень успеха в реализации перечисленных выше угроз также может быть различной. Если исключить случайную удачу, то успешная реализация угрозы секретности данных означает овладение злоумышленником алгоритмом расшифрования D, или построение функционально эквивалентного ему алгоритма D', позволяющего для любого зашифрованного сообщения T', или хотя бы для шифртекстов из некоторого класса, получить соответствующее открытое сообщение T. Аналогично, успешная реализация угрозы целостности данных означает овладение злоумышленником алгоритмом зашифрования E, или построение функционально эквивалентного ему алгоритма E', позволяющего для любого открытого сообщения T, или хотя бы для сообщений из некоторого класса, получить соответствующее зашифрованное сообщение T'. Или, в наименее успешном для злоумышленника случае, создание алгоритма, позволяющего построить такое зашифрованное сообщение T' без знания соответствующего ему открытого сообщения T, которое законный получатель принял бы за подлинное.

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

- дешифруемый текст T', также могут иметься перехваченные ранее шифрованные сообщения (T1',T2', ...,Tn'), зашифрованные с использованием того же самого алгоритма, что и T';

- открытые сообщения, соответствующие некоторым ранее перехваченным шифровкам:

(T1,T2, ...,Tm), Ti' = E(Ti), i= 1, ..., m, где m меньше либо равно n;

- возможность получить для произвольного выбранного злоумышленником открытого сообщения T соответствующий шифртекст T' =E(T);

- возможность получить для произвольного выбранного злоумышленником шифрованного сообщения T' соответствующий открытый текст T=D(T').

Соответственно этим трем возможностям различают следующие основные виды криптоанализа:

- анализ на основе только шифртекста;

- анализ на основе невыбранного открытого текста;

- анализ на основе выбранного открытого текста;

- анализ на основе выбранного шифртекста;

Первая возможность есть в распоряжении аналитика практически всегда. Вторая возможность также вполне реальна: например, разведке через агентуру удалось достать расшифровку одного из секретных сообщений. Более того, эта возможность весьма типична в тех сферах, где срок жизни секретной информации весьма мал, и она быстро предается огласке – при передаче рекламных материалов, различных репортажей, публикуемых впоследствии средствами массовой информации и т.д., словом везде, где надо опередить конкурентов всего на несколько часов или дней. Третья и четвертая возможности, хотя и кажутся экзотическими, тем не менее также могут иметь место – если сотрудник организации, работающий на другую сторону, имеет доступ к общим шифровальным средствам. Конечно, третий случай имеет смысл применительно к задаче дешифрования, а четвертый – навязывания ложных данных. Первые два актуальны для обеих угроз. В рассматриваемой нами жизненной ситуации присутствует еще одна сторона, криптограф, в задачу которого входит снабдить законных участников обмена такими алгоритмами за- и расшифрования, чтобы злоумышленник не смог выполнить ни одну из своих угроз даже в самой благоприятной для него ситуации, то есть при возможности криптоанализа на основе произвольно выбранного открытого текста. Иными словами, задачей криптографа является разработка секретной и аутентичной системы передачи данных. Вообще говоря, это различные, хотя порой и связанные довольно тесно в конкретных шифрах свойства криптосистем.

МЕТОДЫ АНАЛИЗА АЛГОРИТМОВ БЛОЧНОГО ШИФРОВАНИЯ

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