Разработка псевдослучайной функции повышенной эффективности на основе конструкции расширенного каскада

Разработка псевдослучайной функции повышенной эффективности на основе конструкции расширенного каскада

РЕФЕРАТ

псевдослучайная функция информационная безопасность

Дипломная работа посвящена разработке псевдослучайной функции повышенной эффективности на основе конструкции расширенного каскада.

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

Во второй главе предложена математическая модель оценки стойкости криптографической системы защиты информации, описаны ее элементы. Рассмотрены основные теоретико-числовые предположения: проблема принятия решения Диффи-Хеллмана и её вычислительный аналог.

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

• РЕФЕРАТ
• ВВЕДЕНИЕ
• 1 АНАЛИЗ СУЩЕСТВУЮЩИХ УГРОЗ ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ. ОСНОВНЫЕ СРЕДСТВА ЗАЩИТЫ ДАННЫХ
• 1.1 Концептуальная модель информационной безопасности
• 1.2 Системная классификация и общий анализ угроз безопасности информации
• 1.3 Средства обеспечения информационной безопасности.
• 1.4 Выводы
• 2 АНАЛИЗ ТЕОРЕТИКО-СЛОЖНОСТНОЙ МОДЕЛИ ОЦЕНКИ СТОКОСТИ КРИПТОГРАФИЧЕСКИХ СИСТЕМ И ПРОТОКОЛОВ
• 2.1 Системный анализ существующих моделей оценки стойкости криптографических систем
• 2.2 Математическая модель безопасности криптосистемы
• 2.3 Оценка практической эффективности и сложности взлома криптосистем и их примитивов
• 2.4 Модель случайного оракула
• 3 АНАЛИЗ И ПРОЕКТИРОВАНИЕ ПСЕВДОСЛУЧАЙНЫХ ФУНКЦИЙ С ПОВЫШЕННОЙ ЭФФЕКТИВНОСТЬЮ
• 3.1 Применение псевдослучайной функции в качестве криптографического примитива
• 3.2 Постановка проблемы и обоснование выбранного решения
• 3.3 Обоснование и использование теоретико-сложностных предположений
• 3.4 Построение конструкции классического каскада на основе классического решения
• 3.5 Применение конструкции расширенного каскада для построения псевдослучайных функций повышенной эффективности
• 3.5.1 Реализация псевдослучайной функции Наора-Рейнголда с помощью расширенного каскада
• 3.5.2 Построение псевдослучайной функции Бонеха, Монтгомери и Рагунатана на основе псевдослучайной функции Додиса-Ямпольского
• 3.6 Разработка псевдослучайной функции с экспоненциальной областью определения и доказательство её стойкости
• 3.6 Выводы
• 4 БЕЗОПАСНОСТЬ И ЭКОЛОГИЧНОСТЬ РАБОТЫ
• 4.1 Общая оценка условий труда оператора ПЭВМ
• 4.2 Анализ опасных и вредных производственных факторов труда оператора ПЭВМ
• 4.3 Анализ возможных чрезвычайных ситуаций и мер по их предотвращению и устранению
• 4.4 Выводы
• 5 РАСЧЁТ ЭКОНОМИЧЕСКОЙ ЭФФЕКТИВНОСТИ ИНВЕСТИЦИЙ В СРЕДСТВА КРИПТОГРАФИЧЕСКОЙ ЗАЩИТЫ
• 5.1 Сравнительный анализ методов оценки эффективности средств обеспечения информационной безопасности
• 5.2 Применение методики дисконтирования денежных потоков для оценки эффективности инвестиций в средства криптографической защиты информации
• 5.3 Расчет эффективности инвестиций в средства криптографической защиты информации
• 5.4 Выводы
• ЗАКЛЮЧЕНИЕ
• СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
• ВВЕДЕНИЕ
• В современных условиях перед учреждениями и организациями всех форм собственности особо остро встает задача сохранения не только материальных ценностей, но и информации, в том числе и сведений, составляющих коммерческую или государственную тайну, а также персональных данных. Беззастенчивая кража предприятиями и организациями интеллектуальной собственности друг друга стала практически массовым процессом. К этому следует добавить целенаправленные действия по сманиванию или подкупу рабочих и служащих предприятий конкурента с целью овладения секретами коммерческой и производственной деятельности.
• Для того чтобы справиться со стремительным нарастанием потока информации, вызванным научно-техническим прогрессом, организации вынуждены постоянно совершенствовать используемые средства, способы и методы защиты конфиденциальной информации. Одним из наиболее востребованных способов защиты стало применение криптографических алгоритмов. Криптографические методы защиты информации позволяют исключить угрозу нарушения конфиденциальности данных путем их шифрования, обеспечить целостность информации при хранении и передаче по каналам связи, а так же предотвратить несанкционированный доступ механизмами аутентификации.

Псевдослучайные функции (ПСФ) являются одним из фундаментальных блоков современной криптографии и имеют невероятное количество приложений в схемах шифрования, генерации ключей, обеспечении целостности передаваемых данных, механизмах электронно-цифровых подписей, аутентификации и даже для защиты от Dos-атак. Быстрые ПСФ, построенные на основе блочных шифров типа AES, имеют один существенный недостаток — их криптографическая стойкость базируется на интерактивных доказательствах, а значит, они являются гораздо более чувствительными к адаптивным разновидностям атак. Ввиду этого повышение эффективности ПСФ, стойкость которых выводится из тяжелоразрешимости теоретико-числовых предположений типа вычисления дискретного логарифма и является априори выше стойкости «быстрых» ПСФ, представляется достаточно актуальной задачей.

Результатом выполнения дипломной работы является новая конструкция псевдослучайной функции повышенной эффективности с доказанной стойкостью на основе предположения о сложности решения ?-DDH проблемы в ?. Для расширения области определения исходной ПСФ предлагается использовать конструкцию расширенного каскада, предложенную Бонехом, Монтгомери и Рагунатаном в. Стойкость псевдослучайной функции определяется на основе описанной математической модели оценки безопасности криптосистемы в результате игр, проводимых злоумышленником с запросчиком.

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

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

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

1. АНАЛИЗ СУЩЕСТВУЮЩИХ УГРОЗ ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ. ОСНОВНЫЕ СРЕДСТВА ЗАЩИТЫ ДАННЫХ

1.1 Концептуальная модель информационной безопасности

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

В качестве компонентов концептуальной модели безопасности информации на первом уровне декомпозиции возможно выделение следующих объектов [45]:

— объекты угроз;

— угрозы;

— источники угроз;

— цели угроз со стороны злоумышленников;

— источники информации;

— способы неправомерного овладения конфиденциальной информацией (способы доступа);

— направления защиты информации;

— способы защиты информации;

— средства защиты информации.

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

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

Источниками угроз выступают конкуренты, преступники, коррупционеры, административно-управленческие органы.

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

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

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

Основными направлениями защиты информации являются правовая, организационная и инженерно-техническая защиты информации.

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

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

1.2 Системная классификация и общий анализ угроз безопасности информации

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

— ознакомление с конфиденциальной информацией различными путями и способами без нарушения ее целостности;

— модификация информации в криминальных целях как частичное или значительное изменение состава и содержания сведений;

— уничтожение информации с целью прямого нанесения материального ущерба.

Среди действий, приводящих к неправомерному овладению информацией, выделяют следующие:

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

— утечку — бесконтрольный выход конфиденциальной информации за пределы организации или доверенного круга лиц;

— несанкционированный доступ — противоправное преднамеренное овладение конфиденциальной информацией лицом, не имеющим права доступа к охраняемым секретам.

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

Уровень воздействия угрозы определяет целевую направленность негативного воздействия на информацию на синтаксическом, семантическом или прагматическом уровнях, а также общую ориентацию системы защиты. Согласно определению информационной безопасности, угрозы можно классифицировать следующим образом (рисунок 1.1) [28, 31]:

— угрозы нарушения физической целостности, проявляющиеся в уничтожении либо разрушении элементов;

— угрозы нарушения логической структуры, проявляющиеся в искажении структуры, разрушении логических связей;

— угрозы нарушения содержания, проявляющиеся в несанкционированной модификации, искажении блоков информации, внешнем навязывании ложной информации;

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

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

Рисунок 1.1 — Классификация угроз информационной безопасности по уровням воздействия [31, 28]

Согласно [24, 33] предлагается следующая классификация угроз (рисунок 1.2):

— нарушение конфиденциальности (раскрытие) информации;

— нарушение целостности информации (ее полное или частичное уничтожение, искажение, фальсификация, дезинформация);

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

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

Рисунок 1.2 — Классификация угроз информационной безопасности по уровням воздействия [24, 33]

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

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

— ошибки в процессе обработки информации:

· отказ — нарушение работоспособности какого-либо элемента системы, приводящее к невозможности выполнения им основных своих функций;

· сбой — временное нарушение работоспособности какого-либо элемента системы, следствием чего может быть неправильное выполнение им в этот момент своей функции;

· ошибка — неправильное (разовое или систематическое) выполнение элементом одной или нескольких функций, происходящее вследствие специфического (постоянного или временного) его состояния;

· побочное влияние — негативное воздействие на систему в целом или отдельные ее элементы, оказываемое какими-либо явлениями, происходящими внутри системы или во внешней среде;

— стихийные бедствия и несчастные случаи.

Рисунок 1.3 — Природа происхождения угроз информационной безопасности Преднамеренное происхождение угрозы обусловливается злоумышленными действиями людей, осуществляемыми в целях реализации одного или нескольких видов следующих угроз [31]:

— хищение носителей информации;

— подключение к каналам связи;

— перехват электромагнитных излучений;

— несанкционированный доступ;

— разглашение информации;

— копирование данных.

Можно выделить следующие две разновидности предпосылок возникновения угроз: объективные и субъективные (рисунок 1.4).

Рисунок 1.4 — Предпосылки возникновения угроз информационной безопасности Объективными являются причины, не связанные непосредственно с деятельностью людей и вызывающие случайные по характеру происхождения угрозы и могут выражаться:

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

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

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

— деятельность разведорганов иностранных государств. Это специально организуемая деятельность государственных органов, профессионально ориентированных на добывание необходимой информации всеми доступными способами и средствами.

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

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

— злоумышленные действия недобросовестных сотрудников — хищение (копирование) или уничтожение информационных массивов или/и программ по эгоистическим или корыстным мотивам.

— плохое психофизическое состояние персонала, приводящее к ошибкам в осуществляемой деятельности;

— недостаточная подготовка специалистов и низкий уровень их знаний.

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

— люди;

— технические средства;

— модели, алгоритмы, программы;

— технологические схемы обработки;

— внешняя среда.

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

1.3 Средства обеспечения информационной безопасности

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

С учетом сложившейся практики обеспечения безопасности выделяют следующие направления защиты информации (рисунок 1.5):

- правовая защита — специальные законы, нормативные акты, правила, процедуры и мероприятия, обеспечивающие защиту информации на правовой основе;

— организационная защита — регламентация производственной деятельности и взаимоотношений исполнителей на нормативно-правовой основе, исключающая или ослабляющая нанесение какого-либо ущерба исполнителям;

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

Рисунок 1.5 — Направления обеспечения информационной безопасности

Правовые меры направлены на решение следующих вопросов:

— категорирование открытого и ограниченного доступа информации;

— определение полномочий по доступу к информации;

— права должностных лиц на установление и изменение полномочий;

— способы и процедуры доступа;

— порядок контроля, документирования и анализа действий персонала;

— ответственность за нарушение установленных требований и правил;

— проблема доказательства вины нарушителя;

— соответствующие карательные санкции.

Организационные меры включают в себя:

— мероприятия, осуществляемые при проектировании, строительстве и оборудовании объектов защиты;

— мероприятия по разработке правил доступа пользователей к ресурсам системы (разработка политики безопасности);

— мероприятия, осуществляемые при подборе и подготовке персонала;

— организацию охраны и надежного пропускного режима;

— организацию учета, хранения, использования и уничтожения документов и носителей с конфиденциальной информацией;

— распределение реквизитов разграничения доступа (паролей, ключей шифрования и т. п.);

— организацию явного и скрытого контроля за работой пользователей;

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

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

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

— идентификацию и аутентификацию субъектов;

— разграничение доступа к ресурсам;

— регистрацию и анализ событий;

— криптографическое закрытие информации;

— резервирование ресурсов и компонентов системы обработки информации и др.

Инженерно-техническая защита представлена физическими, аппаратными и программными средствами, а также криптографическими методами.

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

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

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

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

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

— нейтрализации технических каналов утечки информации (защита информации от ее утечки по техническим каналам;

— поиска закладных устройств (защита от использования закладных устройств съема информации);

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

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

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

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

По функциональному назначению программные средств можно разделить на следующие группы:

— идентификация технических средств (терминалов, ПК, носителей информации), задач и пользователей;

— определение прав технических средств (дни и время работы, разрешенные к использованию задачи) и пользователей;

— контроль работы технических средств и пользователей;

— регистрация работы технических средств и пользователей при обработке информации ограниченного использования;

— уничтожения информации в ЗУ после использования;

— сигнализации при несанкционированных действиях;

— вспомогательные программы различного назначения: контроля работы механизма защиты, проставления грифа секретности на выдаваемых документах.

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

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

Цели, преследуемые средствами криптографической защиты, можно сформулировать следующим образом [Ади02, 32]:

— обеспечение конфиденциальности данных (security) или предотвращение несанкционированного доступа к данным. Наиболее остро эта задача встает при передаче данных через открытые каналы связи либо хранении информации на общедоступных носителях. Является основной задачей криптографии и решается шифрованием данных.

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

— обеспечение аутентификации, причем под аутентификацией может пониматься как проверка подлинности самих субъектов при обмене данными (entity authentication), так и проверка соответствия получаемой информации отправителям (data origin authentication).

— обеспечение невозможности отказа от авторства (non-repudation), или предотвращение возможности отказа субъекта от совершенных им действий. Эта задача неотделима от двойственной — обеспечение невозможности приписывания авторства. Основным способом решения данной проблемы является использование цифровой подписи.

1.4 Выводы

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

— меры организационной защиты позволяют справиться со многими угрозами, однако имеют склонность к зависимости от субъективных факторов;

— применение аппаратных средств требует значительного вложения средств и не обеспечивает необходимый уровень гибкости;

— программные средства настолько гибки, что легко поддаются модификации, в том числе несанкционированной;

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

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

2. АНАЛИЗ ТЕОРЕТИКО-СЛОЖНОСТНОЙ МОДЕЛИ ОЦЕНКИ СТОКОСТИ КРИПТОГРАФИЧЕСКИХ СИСТЕМ И ПРОТОКОЛОВ

2.1 Системный анализ существующих моделей оценки стойкости криптографических систем

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

Информационно-теоретическая модель безопасности предполагает невозможность совершения противником взлома даже при условии обладания им бесконечно большими вычислительными ресурсами. Методы доказательства стойкости криптосистемы в такой модели тесно сопряжены с теорией информации. В случае если эта модель не опирается на решение проблем, неограниченная вычислительная стойкость которых считается недоказанно стойкой, тогда говорят о безусловной модели безопасности (unconditional secure model), частным случаем которой является абсолютно стойкая модель.

Алгоритм считается абсолютно стойким (absolute secure), если знания противника только шифротекстов, вне зависимости от их объёма, недостаточно для восстановления открытого текста. Это означает, что шифротекст не обладает никакой информацией об открытом тексте, за исключением, возможно, длины. Еще Клод Э. Шеннон в 1945 году теоретически доказал, что абсолютную безопасность можно достигнуть только в случае использования одноразовых ключей длиной не короче самого сообщения. Таким образом, из известных алгоритмов только шифрование одноразовым блокнотом (оne-time pad, шифр Вернама) является абсолютно стойким, так как его невозможно вскрыть при бесконечных ресурсах. Все остальные криптосистемы подвержены вскрытию грубой силой с использованием одного только шифротекста простым перебором ключей и проверкой осмысленности полученного открытого текста. Абсолютно стойкие криптосистемы устойчивы к появлению всех возможных новых видов криптоанализа — их стойкость доказана полностью.

Теоретико-сложностная модель безопасности подразумевает, что способность взлома противником криптосистемы основывается на его умении решать соответствующую вычислительно сложную задачу (intractable problems). Иными словами, он должен обладать достаточно большими вычислительными ресурсами, размер которых задаётся параметром безопасности (параметром стойкости, security parameter). Алгоритмы, основанные на стандартной модели, называют вычислительно стойкими (computational secure, практически стойкими, fit-to-application security, сильными) и не подлежат взлому в обозримом будущем, а доказательство их стойкости выводится из теории сложности.

Трудность с использованием этой модели состоит в том, что вычислительная сложность большинства задач лишь обоснованно предполагается, но не является доказанной. Если же удастся доказать обратное, то протокол, построенный на основе стандартной модели, очевидно также окажется нестойким.

В дипломной работе для доказательства стойкости разработанной нами ПСФ мы использовали теоретико-сложностную математическую модель безопасности. Для ее построения необходимо определить следующие параметры:

— границы параметра безопасности;

— цель противника и объем доступной ему информации;

— величину практически неосуществимого объема вычислений;

— величину пренебрежимо малой вероятности;

— достаточные слабые условия существования выбранного нами теоретико-сложностного предположения.

2.2 Математическая модель безопасности криптосистемы

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

— количество всех возможных ключей или вероятность подбора ключа за заданное время с заданными ресурсами;

— количество операций или время (с заданными ресурсами), необходимое для взлома шифра с заданной вероятностью;

— стоимость вычисления ключевой информации или исходного текста.

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

В отношении противника принимается ряд следующих допущений, которые лежат в основе математической модели:

— противник знает алгоритм шифрования (или выработки ЭЦП) и особенности его реализации в конкретном случае, но не знает секретного ключа;

— противнику доступны все зашифрованные тексты, и он может иметь доступ к некоторым исходным текстам, для которых известны соответствующие им зашифрованные тексты;

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

Криптографической атакой на шифр (или просто атакой) называются любые действия противника, направленные на вызов отклонений в работе криптографической системы. Наиболее распространенными вариантами являются попытки прочтения либо подделки зашифрованного сообщения средствами криптоанализа. Удачную атаку, дискредитирующую атакуемую систему, называют взломом или вскрытием.

Любую атаку противника, направленную на взлом криптографической системы, можно свести к одной из четырем, представленных ниже в порядке их эффективности и сложности осуществления [29, 40,42, 43, 56]:

— атака на основе известного шифротекста (сiphertext-only attack, COA): является основным видом атаки — противник, имея только шифротекст, пытается восстановить открытый текст либо получить ключ. Этот вид атаки является наиболее трудным, поскольку противник обладает наименьшим объемом информации.

— атака на основе известного открытого текста (known-plaintext attack, KPA): противник, имея одну или несколько пар открытого и шифрованного одним и тем же ключом текста, пытается восстановить открытый текст из шифротекста, не относящегося к этим парам или получить ключ.

— атака на основе подобранного (выбранного) открытого текста (chosen-plaintext attack, CPA): противник имеет возможность получить заранее выбранные им открытые тексты в зашифрованном виде. Такую атаку также иногда называют «полуночной» (midnight attack), или атакой «за чашкой кофе» (coffee-break attack). Цель противника — получить ключ, используя пары открытых и зашифрованных текстов.

— атака на основе подобранного шифротекста (chosen-ciphertext attack, CCA): противник может получить выбранные им шифротексты в расшифрованном виде. Цель противника, как и в CPA, — получить ключ, используя пары открытых и зашифрованных текстов.

Все приведенные атаки также имеют адаптивную разновидность — в этом случае противник может проанализировать полученные результаты и на их основе осуществить последующий выбор и коррекцию своих запросов.

Первые два типа атак являются пассивными, так как противник просто получает шифротексты, и возможно, также какие-то открытые тексты. Две последние атаки, наоборот, являются активными, ведь противник может получать ответы на созданные им самим запросы.

Атаки на основе выбранного шифротекста/открытого текста выглядят достаточно реалистично. Действительно, для осуществления первой атаки единственным необходимым условие для противника является наличие открытого канала передачи зашифрованных сообщений. Второй тип атаки был порожден использованием криптозащиты для неконфиденциальных или временно конфиденциальных сообщений. Например, высока вероятность того, что каждое из сообщений начинается с приветствия и оканчивается фиксированной подписью. С высокой степенью вероятности можно предугадать содержимое заголовка IP-пакета. Подобные прогнозируемые данные позволяют получить частично известный открытый текст, а соответствующий тип атак также принято относить к атакам с известным открытым текстом. Также часто информация является секретной до периода его опубликования (например, ежеквартальные финансовые отчеты). В этом случае противник, перехватив шифротекст, позднее из открытых источников может получить исходный текст.

Определение практически неосуществимого объема вычислений для противника ограничивается требованием экспоненциальной зависимости сложности взлома от растущего параметра безопасности и полиномиальной — для операций санкционированного пользователя.

Под пренебрежимо малой вероятностью мы будем любую вероятность, которая для любого полинома p и для всех достаточно больших п не превосходит 1/р (п), где п — параметр безопасности.

В качестве вычислительно сложной проблемы, к которой сводится взлом ПСФ, была выбрана разновидность проблемы Диффи-Хеллмана. В качестве техники доказательства использовалась редукция (reduction) — сведение эффективыми математическими преобразованиями адаптивной атаки против ПСФ на основе подобранного шифротекста к решению выбранной нами вычислительно неразрешимой задачи.

2.3 Оценка практической эффективности и сложности взлома криптосистем и их примитивов

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

Сложность алгоритма определяется вычислительными мощностями, необходимыми для его выполнения и измеряется двумя параметрами: временной сложностью (time complexity)? и пространственной сложностью или требованиями к памяти (space complexity) ?. Оба параметра обычно представляются в виде функций от аргумента n, где n — размер входных данных.

Вычислительная сложность алгоритма выражается с помощью нотации «О большого», то есть описывается порядком величины вычислительной сложности. «О большое» — член разложения функции сложности, быстрее всего растущий с ростом п, в результате чего все члены низшего порядка игнорируются. Например, если временная сложность заданного алгоритма составляет, то вычислительная сложность, равная порядку, записывается в виде .

Использование нотации «большого О» позволяет выявить зависимость требований к времени и объёму памяти от объёма входных данных. Например, если, то удвоение входных данных также удвоит и время выполнения алгоритма. Если, то добавление одного бита к входным данным удвоит время алгоритма.

Согласно теории сложности алгоритмы классифицируют в соответствии с их временной или пространственной сложностью следующим образом. Алгоритм называется постоянным (constant algorithm), если сложность его выполнения не зависит от объёма входных данных n:. Алгоритм является линейным (linear algorithm), если его сложность его выполнения линейно зависит от объёма входных данных:. По аналогии с линейным алгоритмом различают квадратичные, кубические и т. п. в зависимости от константы m в. Алгоритмы, сложность которых определяется как, называются полиномиальными (polynomial algorithm), а алгоритмы с полиномиальной временной сложностью — алгоритмами с полиномиальным временем (polynomial time).

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

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

Таблица 2.1 — Время выполнения различных классов алгоритмов

Что касается временной сложности вскрытия грубой силой алгоритмов различных классов, то она прямо пропорциональна количеству возможных ключей, которое в свою очередь экспоненциально зависит от длины ключа. Для ключа длиной n сложность вскрытия алгоритма грубой силой равна. Обычно в зависимости от этого значения определяется нижняя граница длины ключа. Например, для 56-битового ключа временная сродность взлома грубой силой алгоритма DES равна 2⁵⁶, а для 112-битового — 2¹¹², причем в первом случае вскрытие возможно, а вот втором — уже нет.

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

Таблица 2.2 — Поразрядные оценки сложности основных операций в кольце вычетов (29)

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

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

Существует множество хорошо известных трудноразрешимых задач, которые часто используются в современной криптографии. Например, к неразрешимым задачам относятся задача факторизации целых чисел (integer factorization problem), задача дискретного логарифмирования (discrete logarithm problem), задача Диффи-Хеллмана (Diffie-Hellman problem) и некоторые родственные задачи. Эти задачи можно рассматривать в качестве эталонов, поскольку они имеют долгую историю и в настоящее время продолжают считаться трудноразрешимыми.

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

Проблемы можно разбить на классы в соответствии со сложностью их решения. Самые важные классы и их предполагаемые соотношения представлены на рисунке 2.2.

Рисунок 2.2 — Классы сложности проблем Класс Р состоит из всех проблем, которые можно решить за полиномиальное время. Класс NP составляют проблемы, которые можно решить за полиномиальное время только на недетермированной (вероятностной) машине Тьюринга. Машина предполагает решение проблемы путем «удачного угадывания» либо перебором всех предположений параллельно, каждое за полиномиальное время. Таким образом, многие симметричные и асимметричные алгоритмы могут быть взломаны за недетерминированное полиномиальное время. Для данного шифротекста C противник выбирает наугад открытый текст Х и ключ k, а затем за полиномиальное время осуществляет его шифрование и сверяет с данным шифротекстом.

Класс NP включает в себя класс Р, так как любая проблема, решаемая за полиномиальное время на детерминированной машине Тьюринга, будет также решена за полиномиальное время на детерминированной машине Тьюринга. Если все NP проблемы решаются за полиномиальное время на детерминированной машине, то P = NP. Несмотря на то, что интуитивно чувствуется разная сложность различных NP-проблем, еще не было доказано, что, впрочем, как и обратное.

NP-полные проблемы входят в класс NP и так же сложны, как и любая проблема класса NP. Если NP-полная проблема решается за полиномиальное время, то P = NP, и наоборот: если для любой проблемы класса NP возможно доказательство отсутствия существования детерминированного алгоритма с полиномиальным временем выполнения, то и для NP-полной проблемы не существует детерминированного алгоритма с полиномиальным временем решения. Таким образом, доказательство решаемости NP-полных проблем за детерминированное полиномиальное время, очевидно, разрешит вопрос о равенстве классов P и NP и будет означать возможность взлома многих шифров слабыми, детерминированными алгоритмами.

Следующим в иерархии сложности стоит класс PSPACE. Проблемы этого класса могут быть решены в полиномиальном пространстве, но не обязательно за полиномиальное время. PSPACE включает в себя класс NP при видимой сложности некоторых проблем класса PSPACE перед NP. Их равенство также пока не доказано. Кроме того, существует также класс PSPACE-полных проблем, для которых справедливо следующее условие: если любая из них является NP-проблемой, то PSPACE = NP, и если любая из них является P-проблемой, то PSPACE = P.

И, наконец, существует класс проблем EXPTIME, которые решаются за экспоненциальное время. EXPTIME не равно Р.

Опишем основополагающие теоретико-числовые проблемы в криптографии: проблему принятии решения Дифии-Хеллмана и вычислительную проблему Диффи-Хеллмана.

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

Проблема Диффи-Хеллмана формализует проблему дискретного логарифмирования. Предположение о сложности решения проблемы принятия решения Диффи-Хеллмана лежит в основе многих криптографических протоколов, среди которых наиболее известны криптосистемы Эль Гамаля и Крамера-Шоупа.

Рассмотрим мультипликативную циклическую группу (cyclic group)? порядка p с порождающим элементом g. Предположение о сложности решения DDH проблемы заключается в том, что для данных g^a и g^b со случайно выбранными элементами значение g^ab выглядит совершенно неотличимым от случайно выбранного элемента из ?.

Формально говоря, два нижеприведенных распределения вероятностей вычислительно не различимы для параметра безопасности p:

—, где a и b случайно и независимо выбраны из .

—, где a, b, c случайно и независимо выбраны из .

Строка вида в отечественной и зарубежной литературе часто называется кортежем, строкой или тройкой Диффи-Хеллмана (DDH triples, DDH tuples).

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

В случае существования эффективного алгоритма вычисления дискретного логарифма в? взлом DDH в группе? представляет собой тривиальною задачу. Тогда для данных определение, является ли, заключается в вычисление дискретного логарифма, а затем в сравнении значений z и .

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

Сложность DDH также связана со сложностью решения вычислительной проблемы Диффи-Хеллмана (computational Diffie-Hellman assumption, CDH). Она заключается в утверждении о том, что если возможно эффективно вычислить при данных, тогда легко различить описанные выше вероятностные распределения. Поэтому предположение и DDH считается более строгим, чем CDH.

Проблема распознавания DDH строки является саморедуцируемой (random self-reducible). Грубо говоря, это понятие означает, что если что-то является сложной задачей даже для небольшого фрагмента, то это будет сложно практически для любого объема входных данных, и если что-то легко решить для небольшого фрагмента входных данных, то это можно считать легкой задачей для почти любого объема входных данных.

2.4 Модель случайного оракула

Случайный оракул (random oracle) представляет собой абстрактную функцию, которую можно представить в виде следующей модели. Пусть существует некий чёрный ящик, на вход которого можно подать строку любой длины. При первом запросе случайный оракул на выход выдаёт строку истинно случайных чисел фиксированной длины и записывает пару «запрос/ответ» в память. При последующих запросах оракул проверяет, был ли такой запрос, и в случае положительного ответа выдаёт записанный ответ. В противном случае цикл повторяется: генерируется и выводится истинно случайная строка, в память записывается пара «запроса/ответа». Такое гипотетическое устройство могло бы состоять из генератора истинно случайных чисел с памятью и процессором, но при стремящемся к бесконечности количестве запросов его память и быстродействие также должны стремиться к бесконечности.

Под оракулом функции (function oracle) может пониматься «черный ящик», обладающий секретным ключом, к которому злоумышленник может обратиться с просьбой выполнить криптографическую операцию, и затем делать на основании его ответов те или иные выводы. Другая аналогия может выступать представление оракула посредником между злоумышленником и неким криптографическим алгоритмом, который принимает запрос от злоумышленника, передаёт их в качестве входных данных для алгоритма, а затем возвращает результат его выполнения злоумышленнику.

Модель запросчика функции (function challenger) является объединением описанных выше моделей. В зависимости от результата подброшенной «случайной монеты» запросчик предоставляет доступ либо к случайному оракулу, либо к оракулу функции, тем самым за запрос атакующего алгоритма отвечая случайным значением или действительно вычисленным по алгоритму. Модель запросчика часто используется в интерактивных доказательствах в экспериментах по неразличимости выдаваемых алгоритмом значений от выбранных случайным образом.

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