Разработка и реализация математической модели двухключевой криптосистемы - Дипломная работа

.7.2 Существование конечного поля 2.7.3 Мультипликативная группа конечного поля Системы с открытым ключом 3.2 Управление ключамиПроблема защиты информации путем ее преобразования, исключающего ее прочтение посторонним лицом, волновала человеческий ум с давних времен. С широким распространением письменности криптография стала формироваться как самостоятельная наука. Почти одновременно с криптографией возникла также наука о методах раскрытия зашифрованной информации - криптоанализ. Криптография занимается поиском и исследованием математических методов преобразования информации. С развитием информационных технологий проблемы защиты информации начинают интересовать все большее число людей.Описать криптографическую систему с открытым ключом Р. Оценить ее криптостойкость, основанную на сложности разложения числа на простые сомножители. Оценить количество операций, необходимых для шифрации и дешифрации информации; в зависимости от этого и от криптостойкости системы дать рекомендацию на длину ключа. Написать алгоритм дешифрования итерациями для криптосистемы RSA, используя готовые ключи небольшой длины.Сумма, разность и произведение двух целых чисел также является числом целым, но частное от деления a на b может быть как целым, так и не целым. В случае, когда частное от деления a на b - целое, обозначим его q, имеем a = bq, т. е. a равно произведению b на целое. Число q называется неполным частным, а число r - остатком от деления a на b. Всякое целое, делящее одновременно целые a и b, называется их общим делителем. Рассматривая равенства (**) сверху вниз, убеждаемся, что общие делители чисел a и b одинаковы с общими делителями чисел r2 и r3, чисел r3 и r4, …, чисел rn-1 и rn, наконец, с делителями одного числа rn.Число 1 имеет только один положительный делитель, именно 1. Всякое целое, большее единицы, имеет не менее двух делителей, именно 1 и самого себя; если этими делителями исчерпываются все положительные делители целого числа, то оно называется простым. Целое, большее 1, имеющее кроме 1 и себя самого другие положительные делители, называется составным. Если произведение нескольких сомножителей делится на p, то, по крайней мере, один из сомножителей делится на p. Всякое целое, большее единицы, разлагается на произведение простых сомножителей и притом единственным способом, если отвлечься от порядка следования сомножителей.Функция Эйлера j(а) определяется для всех целых положительных а и представляет собою число чисел ряда 0, 1, ..., а-1, взаимно простых с a.Функция j(а) называется мультипликативной, если она удовлетворяет двум следующим условиям: Эта функция определена для всех целых положительных a и не равна нулю по меньшей мере при одном таком a.

Для любых положительных взаимно простых a1 и a2 имеем: j(а1 a2) = j(а1) j(а2) .

2.5Мы будем рассматривать целые числа в связи с остатками от деления их на данное целое положительное m, которое назовем модулем. Каждому целому числу отвечает определенный остаток от деления его на m. Если двум целым a и b отвечает один и тот же остаток r, то они называются равноостаточными по модулю m. Сравнимость чисел a и b по модулю m записывается: a ? b (mod m). Сравнимость чисел a и b по модулю m равносильна: Возможности представить a в виде a = b mt, где t - целое.Числа равноостаточные, или, что то же самое, сравнимые по модулю m, образуют класс чисел по модулю m. Любое число класса называется вычетом по модулю m по отношению ко всем числам того же класса. Взяв от каждого класса по одному вычету, получим полную систему вычетов по модулю m. Любые m чисел, попарно несравнимые по модулю m, образуют полную систему вычетов по этому модулю. Действительно, будучи несравнимы, эти числа тем самым принадлежат к различным классам, а так как их m, т.е. столько же, сколько и классов, то в каждый класс наверно попадет по одному числу.Перемножая почленно сравнения ar1 ? r1 (mod m), ar2 ? r2 (mod m), ..., arc ? rc (mod m), получим ас ? 1 (mod m). Теореме Ферма можно придать более удобную форму, умножая обе части сравнения (2) на а, получим сравнение ap ? a (mod p), справедливое уже при всех целых а, так как оно верно и при а, кратном p. Требуется найти x a-1 (mod n) a * x 1 (mod n) или 5*x 1 (mod 7). В этом случае при решении сравнения a * x 1 (mod m), где (a, m) =1 алгоритм Евклида позволяет найти x (-1)k-1 Qk-1 (mod m), где Qk-1 - знаменатель предпоследней подходящей дроби разложения в цепную дробь. Сначала решают уравнение a * y 1 (mod n), то есть определяют y a-1 (mod n), а затем находят x a-1b (mod n) y * b (mod n).Если для любого натурального m m * 1 0, то характеристикой поля F называют число 0, а поле F называют полем нулевой характеристики. Пусть p - простое число и F - поле; поле Н рациональных дробей над полем F является расширением поля F и, следовательно, имеет ту же характеристику, что и само поле F. Поэтому множество элементов (2.7.1.5) относительно операций " " и "х" образует подполе поля F, а так как F простое поле (т. е. поле, не содержащее других

Содержание

Введение

1. Постановка задачи

2. Математические основы построения RSA-криптосистемы

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

2.2 Простые числа. Разложение на простые сомножители

2.3 Функция Эйлера

2.4 Мультипликативная функция

2.5 Основные понятия теории сравнений

2.5.1 Свойства сравнений

2.5.2 Вычеты. Полная и приведенная системы вычетов

2.5.3 Теоремы Эйлера и Ферма

2.6 Сравнения с одним неизвестным. Вычисление мультипликативного обратного

2.7 Конечные поля

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

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

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

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

Для шифрования информации и организации защиты сетей в России активно используются западные продукты. Это разного рода программы защиты от несанкционированного доступа, а также шифрования файлов, - начиная от Norton Utilities и архиваторов типа PKZIP и заканчивая серьезными приложениями уровня PGP (Pretty Good Private). Даже обычные текстовые редакторы и электронные таблицы содержат те или иные криптографические средства. Широкое распространение получили также межсетевые экраны, средства построения виртуальных частных сетей (Virtual Private Network), организация закрытых каналов обмена информацией и т. д. [9].

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

Наиболее популярна криптосистема RSA, разработанная в 1977 г. и получившая название в честь ее создателей: Рона Ривеста, Ади Шамира и Леонарда Эйдельмана. Возможность гарантированно оценить защищенность алгоритма RSA стала одной из причин его популярности на фоне десятков других схем. Поэтому алгоритм RSA используется в банковских компьютерных сетях, особенно для работы с удаленными клиентами (обслуживание кредитных карточек).

Безопасность RSA обусловлена сложностью разложения большого числа на простые сомножители. На сегодняшний день не существует эффективных алгоритмов разложения числа на сомножители [1]. С помощью длины ключа можно регулировать время разложения числа на простые сомножители, которое с увеличением длины ключа будет расти и при определенной длине выйдет за пределы реального. В то же время произведение двух больших простых чисел или возведение большого числа в степень при использовании «быстрых» алгоритмов - несложная задача, занимающая несколько минут машинного времени при достаточно большой величине ключа [1].

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