Разработка алгоритмов деления для криптосистем

МИНИСТЕРСТВО ОБРАЗОВАНИЯ  И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

фГбОУ ВПО «Ставропольский государственный университет»

Физико-математический факультет

Кафедра ОРГАНИЗАЦИИ И  ТЕХНОЛОГИИ ЗАЩИТЫ ИНФОРМАЦИИ

КУРСОВАЯ РАБОТА

по  дисциплине

«Инженерно-техническая защита информации»

на  тему:

«РАЗРАБОТКА АЛГОРИТМОВ ДЕЛЕНИЯ ДЛЯ КРИПТОГРАФИЧЕСКИХ СИСТЕМ»

Работа  допущена к защите  ___________________________   ______________

^{(подпись руководителя)        (дата)}  

Работа  выполнена и

защищена с оценкой __________________  Дата защиты ______________

Члены комиссии  _______________     _______________  _________________

       ^{(должность)       (подпись)         (И.О. Фамилия)}

_______________     _______________  __________________

_______________     _______________  __________________

Ставрополь, 2012 г. 
СОДЕРЖАНИЕ

ВВЕДЕНИЕ

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

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

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

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

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

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

Обьектом работы являются существующие криптосистемы, в основе которых лежат рассматриваемые алгоритмы.

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

Целью работы является повышение качества работы криптосистем путем создания нового алгоритма.

1 Анализ задач деления чисел в криптографических  приложениях

1.1 Цели поддержки безопасности

Рассмотрим три цели поддержки информационной безопасности: конфиденциальность, целостность и  готовность.

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

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

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

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

1.2 Типы атак угрожающих конфиденциальности информации

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

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

1. Вмешательство В- относится к неправомочному доступу или перехвату данных. Например, файл, передаваемый через Интернет, может содержать конфиденциальную информацию. Объект, не имеющий полномочий, может прервать передачу и использовать передаваемую информацию для собственной выгоды. Чтобы предотвратить вмешательство, данные могут быть представлены так, что перехвативший не сможет понять их. Для этого применимы методы шифрования, приводимые в этой книге.
2. Наблюдение за трафиком и его анализ. – хотя шифрование данных может сделать их непонятными для злоумышленника, он, анализируя сетевой трафик, может получить некоторую другую информацию. Например, он может найти электронный адрес (адрес электронной почты) передатчика или приемника. Он может также собрать пары запросов и ответов, что поможет ему понять активность действий наблюдаемой организации.

2) Атаки, угрожающие целостности:

1. Модификация- После прерывания или доступа к информации атакующий изменяет информацию с определенной выгодой для себя. Например, клиент передает сообщение банку, чтобы провести некоторую операцию. Атакующий прерывает сообщение и изменяет тип операции, чтобы принести этим пользу себе. Обратите внимание, что иногда атакующий просто удаляет или задерживает сообщение, чтобы навредить системе или извлечь выгоду из самого факта задержки операции.
2. Имитация источника (spoofing) заключается в том, что атакующий имитирует кого-то, кто имеет право на производимые действия. Например, атакующий захватывает банковскую кредитную карточку и PIN-код клиента банка. Он может действовать как настоящий клиент. Иногда атакующий имитирует приемник. Например, пользователь хочет войти в контакт с банком, но ему предоставляется другой сайт, который имитирует, что это – банк, и атакующий получает необходимую ему информацию от пользователя.

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

3) Атаки, угрожающие готовности

Принято решение рассмотреть только одну атаку угрожающую готовности - отказ в обслуживании.

Отказ в обслуживании. Отказ в обслуживании (Denial of Service — DoS) — очень общее название атаки. Она может замедлить или полностью  прервать обслуживание системы. Атакующий  может использовать несколько стратегий, чтобы достигнуть этого. Атакующий может передать так много фиктивных запросов серверу, что это приведет к сбою сервера из-за высокой нагрузки. Атакующий может также прервать и удалить ответ сервера клиенту, порождая у клиента впечатление, что сервер не отвечает. Атакующий может прервать запросы от клиентов, порождая у клиента уверенность, что сервер не отвечает. Атакующий может прерывать запросы клиентов, заставляя клиентов передать запросы много раз и перезагружать систему.

Теперь, следует разделить атаки на две группы:

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

1.3 Механизмы обеспечения информационной безопасности

Необходимо рассмотреть  восемь механизмов обеспечения информационной безопасности:

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

2) Целостность данных - механизм целостности данных добавляет в конце данных короткий контрольный признак, который создается определенным процессом отдельно от данных. Приемник получает данные и контрольный признак. На основании полученных данных он создает новый контрольный признак и сравнивает только что созданный с полученным. Если эти два контрольных признака совпадают, целостность данных была сохранена.

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

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

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

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

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

8) Контроль доступа использует методы доказательства, что пользователь имеет право доступа к данным или ресурсам, принадлежащим системе. Примеры такого доказательства — пароли и PIN-коды.

1.4 Методы реализации информационной безопасности

Теперь, следует рассмотреть  методы реализации информационной безопасности. Их два:

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

1. Шифрование симметричными ключами иногда называют шифрованием c секретным ключом или криптографией с секретным ключом. Например, объект, назовем его Алиса, может передать сообщение другому объекту, который называется Боб, по опасному каналу, для того, чтобы ее противник, который называется Ева, не смог понять содержание сообщения, просто подслушав его по каналу. Алиса зашифровала сообщение, используя алгоритм шифрования; Боб расшифровывает сообщение, используя алгоритм расшифровки. В шифровании симметричными ключами применяется единственный ключ засекречивания и для шифрования, и для расшифровки. Шифрование/дешифрование можно представить как электронный замок. При шифровании симметричным ключом Алиса помещает сообщение в блок и закрывает блок, используя совместный ключ засекречивания; Боб отпирает замок другим экземпляром того же ключа и извлекает сообщение.
2. Шифрование асимметричными ключами. При шифровании асимметричными ключами (иногда называемом шифрованием с открытыми ключами или криптографией с открытыми ключами) мы имеем ту же самую ситуацию, что и при шифровании симметричными ключами, но с небольшой разницей. Во-первых, мы имеем два ключа вместо одного: из них один открытый ключ (public key), другой — индивидуальный или секретный (private key). Для того чтобы передать защищенное сообщение Бобу, Алиса сначала зашифровала сообщение, используя открытый ключ Боба. Чтобы расшифровывать сообщение, Боб использует свой собственный секретный ключ.
3. Хэширование. При хэшировании из сообщения переменной длины может быть создан дайджест фиксированной длины, обычно намного меньшего размера, чем исходное сообщение. Сообщение и дайджест нужно передать Бобу. Дайджест используется, чтобы обеспечить проверку целостности данных, которая обсуждалась раньше.

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

1.5 Выводы по главе

Для информационной безопасности было определено три главные цели: конфиденциальность, целостность и готовность. Также, было отмечено , что конфиденциальности информации угрожают два типа атак: вмешательство — и наблюдение за трафиком и его анализ. Четыре типа атак могут угрожать целостности информации: модификация, имитация источника, повторная передача информации и отказ от сообщения. Атака "прекращение обслуживания запроса" угрожает готовности информации.

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

2 анализ существующих алгоритмов деления чисел

2.1 Арифметика целых чисел

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

Множество целых чисел

Множество целых чисел, обозначенных Z, содержит все числа (без дробей) от минус бесконечности до плюс бесконечности в соответствии с рисунком 1.

Рисунок 1 – Множество  чисел Z

2.2 Бинарные операции

В криптографии необходимо рассмотреть три бинарных операции в приложении к множеству целых чисел. Бинарные операции имеют два входа и один выход. Для целых чисел определены три общих бинарных операции — сложение, вычитание и умножение. Каждая из этих операций имеет два входа ( a и b ) и выход ( c ), как это показано на рисунке 2. Два входа принимают числа из множества целых чисел; выход выводит результат операции — число из множества целых чисел.

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

Рисунок 2 - Три бинарных операции для множества целых чисел

Пример 1.

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

Рисунок 3 – Бинарные операции на множестве двух целых чисел

2.3 Деление целых чисел

В арифметике целых чисел, если мы a делим на n, мы можем получить q и r. Отношения между этими четырьмя целыми числами можно показать как 

a=q*x+r (1)

В равенстве (1) a это делимое ; q это частное ; n это делитель и r это остаток. Необходимо отметить, что это не операция, поскольку результат деления a на n — это два целых числа, q и r. Следует называть это уравнением деления.

Пример 2.

Предположим, что a = 255, а n = 23. Можно найти q = 11 и r = 2, используя алгоритм деления, из элементарной арифметики известно, что оно определяется, как показано на рисунке 3.

Рисунок 3 – Нахождение частного и остатка

Большинство компьютерных языков может найти частное и  остаток, используя заданные языком операторы. Например, на языке C оператор "/" может найти частное, а оператор "%" — остаток.

Используя вышеупомянутое уравнение деления в криптографии, налагаются два ограничения:

1) Первое требование: чтобы делитель был положительным целым числом ( n > 0 ).

2) Второе требование: чтобы остаток был неотрицательным целым числом ( r > 0 ). Рисунок 4 показывает эти требования с двумя указанными ограничениями.

Рисунок 4 - Алгоритм деления целых чисел

Пример 3

Используется калькулятор, а r и q отрицательны, при отрицательном a. Как можно сделать, чтобы выполнялось ограничение, что число r должно быть положительным? Решение простое: мы уменьшаем значение q на 1 и добавляем значение n к r, чтобы r стало положительным.

Уменьшая ( –23 ), получим ( –24 ) и добавим 11 к ( –2 ), чтобы получить + 9. Полученное равенство эквивалентно исходному.

Граф уравнения деления

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

Рисунок 5 - Граф алгоритма деления

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

2.4 Теория делимости

Теперь, необходимо рассмотреть теорию делимости. Если a не равно нулю, а r = 0, в равенстве деления мы имеем  a = q x n

Тогда известно, что a делится на n (или n — делитель a ). Можно также сказать, что a делится без остатка на n. Когда мы не интересуемся значением q, мы можем записать вышеупомянутые отношения как n|a. Если остаток не является нулевым, то n не делится, и мы можем записать отношения как n†a.

2.4.1 Свойства теории делимости

Следующие несколько свойств теории делимости которые необходимо рассмотреть:

1) Свойство 1: если a|1, то a=±1.

2) Свойство 2: если a|b и b|a, то a=±b

3) Свойство 3: если a|b и b|c, то a|c

4) Свойство 4: если a|b и a|c, то a|(m x b + n x c), где m и n — произвольные целые числа.

2.4.2 Все делители

Положительное целое  число может иметь больше чем  один делитель. Например, целое число 32 имеет шесть делителей: 1, 2, 4, 8, 16 и 32. Необходимо упомянуть два свойства делителей положительных целых чисел:

1) Свойство 1: целое число 1 имеет только один делитель — само себя.

2) Свойство 2: любое положительное целое число имеет по крайней мере два делителя — 1 и само себя (но может иметь больше).

2.4.3 Наибольший общий делитель

Одно целое число, часто необходимое в криптографии, — наибольший общий делитель двух положительных целых чисел. Например, общие делители чисел 12 и 140 есть 1, 2 и 4. Однако наибольший общий делитель — 4 это показано на рисунке 6.

Рисунок 6 - Общие делители двух целых чисел

Наибольший общий делитель двух положительных целых чисел  — наибольшее целое число, которое  делит оба целых числа.

2.5 Алгоритм Евклида

Нахождение наибольшего  общего делителя (НОД) двух положительных  целых чисел путем составления  списка всех общих делителей непригодно для достаточно больших чисел.

Алгоритм Евклида основан  на следующих двух фактах:

1) Факт 1: НОД (a, 0) = a

2) Факт 2: НОД (a, b) = НОД (b, r), где r — остаток от деления a на b

Первый факт говорит, что если второе целое число — 0, наибольший общий делитель равен первому числу. Второй факт позволяет нам изменять значение a на b, пока b не станет 0. Например, вычисляя НОД (36, 10), мы можем использовать второй факт несколько раз и один раз первый факт, как показано ниже. НОД(36,10) = НОД(10,6) = НОД(6,4) = НОД(4,2) = НОД(2,0)

Другими словами, НОД (36, 10) = 2, НОД (10, 6) = 2, и так далее. Это  означает, что вместо вычисления НОД (36, 10) мы можем найти НОД (2, 0). Рисунок 7 показывает, как мы используем вышеупомянутые два факта, чтобы вычислить НОД (a, b).

Рисунок 7 - Алгоритм Евклида

Для определения НОД  мы используем две переменные, r1 и r2, чтобы запоминать изменяющиеся значения в течение всего процесса. Они  имеют начальное значение a и b. На каждом шаге мы вычисляем остаток от деления r1 на r2 и храним результат в виде переменной r. Потом заменяем r1, на r2 и r2 на r и продолжаем шаги, пока r не станет равным 0. В этот момент процесс останавливается и НОД (a, b) равен r1.

2.6 Расширенный алгоритм Евклида

Даны два целых числа a и b. Нам зачастую надо найти другие два целых числа, s и t, такие, которые s x a + t x b = НОД(a,b). Расширенный алгоритм Евклида может вычислить НОД (a, b) и в то же самое время вычислить значения s и t. Алгоритм и процесс такого вычисления показан на рисунке 8.

Здесь расширенный алгоритм Евклида использует те же самые шаги, что и простой алгоритм Евклида. Однако в каждом шаге мы применяем  три группы вычислений вместо одной. Алгоритм использует три набора переменных: r,s и t.

Рисунок 8 - Расширенный алгоритм Евклида

На каждом шаге переменные r1, r2 и r используются так же, как в  алгоритме Евклида. Переменным r1 и r2 присваиваются начальные значения a и b соответственно. Переменным s1 и s2 присваиваются  начальные значения 1 и 0 соответственно. Переменным t1 и t2 присваиваются начальные значения 0 и 1, соответственно. Вычисления r, s и t одинаковы, но с одним отличием. Хотя r — остаток от деления r1 на r2, такого соответствия в других двух группах вычислений нет. Есть только одно частное, q, которое вычисляется как r1/r2 и используется для других двух вычислений.

2.7 Линейные диофантовы уравнения

Хотя очень важное приложение расширенного алгоритма  Евклида будет рассмотрено далее, здесь необходимо рассмотреть "нахождение решения линейных диофантовых уравнений двух переменных", а именно, уравнения ax + by = c. Необходимо найти значения целых чисел для x и y, которые удовлетворяют этому уравнению. Этот тип уравнения либо не имеет решений, либо имеет бесконечное число решений. Пусть d = НОД (a, b). Если d†c, то уравнение не имеет решения. Если d|c, то мы имеем бесконечное число решений. Одно из них называется частным, остальные — общими.

Линейное диофантово уравнение — это уравнение двух переменных

ax + by =c .

Если d|c, то можно найти  частное решение вышеупомянутого уравнения, используя следующие шаги. Преобразуем уравнение к a1x + b1y = c1, разделив обе части уравнения на d. Это возможно, потому, что d делит a, b, и c в соответствии с предположением. Найти s и t в равенстве a1s + b1t = 1, используя расширенный алгоритм Евклида. Получим: