Криптография с открытым ключом

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

 

Факультет заочного обучения

 

Кафедра «Информационные системы»

 

 

ИНФОРМАЦИОННАЯ БЕЗОПАСНОСТЬ

 

Контрольная работа

 

 

Выполнил: Студент гр.   «05» ноября 2013 г.

Принял:     «__»____________2013 г.

Оценка_________________________ 

 

 

г. Петропавловск-Камчатский, 2013

Содержание

Введение 3

Криптография с открытым ключом 6

Шифр Эль Гамаля 8

Заключение…………………………………………………………………….10

Литература…………………………………………………………………..…11

 

 

Введение

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

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

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

Почему  проблема использования криптографических  методов в информационных системах (ИС) стала в настоящий момент особо актуальна?

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

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

Проблемой защиты информации путем ее преобразования занимается криптология (kryptos - тайный, logos - наука). Криптология разделяется на два направления - криптографию и криптоанализ. Цели этих направлений прямо противоположны.

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

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

Современная криптография включает в себя четыре крупных раздела:

• Симметричные криптосистемы.
• Криптосистемы с открытым ключом.
• Системы электронной подписи.
• Управление ключами.

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

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

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

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

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

Отправитель

Адресат

Система

с открытым ключом

Система

с открытым ключом

 

 

 

Закрытый ключ

Открытый ключ

 

 

Криптографические системы с открытым ключом используют так называемые необратимые или односторонние функции, которые обладают следующим свойством: при заданном значении x относительно просто вычислить значение f(x), однако если y=f(x), то нет простого пути для вычисления значения x.

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

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

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

1. Преобразование исходного текста  должно быть необратимым и  исключать его восстановление  на основе открытого ключа.

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

Алгоритмы шифрования с открытым ключом получили широкое распространение в современных  информационных системах. Так, алгоритм RSA стал мировым стандартом де-факто  для открытых систем и рекомендован МККТТ.

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

1. Разложение больших чисел ан простые множители.
2. Вычисление логарифма в конечном поле.
3. Вычисление корней алгебраических уравнений.

 

Криптография с открытым ключом

В 1976 г. У.Диффи и М.Хеллманом [DH76] был предложен новый тип криптографической системы - система с открытым ключом [public key cryptosystem]. В схеме с открытым ключом имеется два ключа, открытый [public] и секретный [private, secret], выбранные таким образом, что их последовательное применение к массиву данных оставляет этот массив без изменений. Шифрующая процедура использует открытый ключ, дешифрующая - секретный. Дешифрование кода без знания секретного ключа практически неосуществимо; в частности, практически неразрешима задача вычисления секретного ключа по известному открытому ключу. Основное преимущество криптографии с открытым ключом - упрощенный механизм обмена ключами. При осуществлении коммуникации по каналу связи передается только открытый ключ, что делает возможным использование для этой цели обычного канала и устраняет потребность в специальном защищенном канале для передачи ключа.

С появлением систем с открытым ключом понятие о защите информации, а  вместе с ним функции криптографии значительно расширились. Если раньше основной задачей криптографических  систем считалось надежное шифрование информации, в настоящее время  область применения криптографии включает также цифровую подпись (аутентификацию), лицензирование, нотаризацию (свидетельствование), распределенное управление, схемы голосования, электронные деньги и многое другое (см. [BFS91], ч.7, [S94], ч.1). Наиболее распространенные функции криптографических систем с открытым ключом - шифрование и цифровая подпись, причем роль цифровой подписи в последнее время возросла по сравнению с традиционным шифрованием: некоторые из систем с открытым ключом поддерживают цифровую подпись, но не поддерживают шифрование.

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

Из-за особенностей алгоритмов, лежащих  в основе систем с открытым ключом, их быстродействие при обработке  единичного блока информации обычно в десятки раз меньше, чем быстродействие систем с симметричным ключом на блоке  той же длины. Для повышения эффективности  систем с открытым ключом часто применяются  смешанные методы, реализующие криптографические  алгоритмы обоих типов. При шифровании информации выбирается случайный симметричный ключ, вызывается алгоритм с симметричным ключом для шифрования исходного  текста. а затем алгоритм с открытым ключом для шифрования симметричного ключа. По коммуникационному каналу передается текст, зашифрованный симметричным ключом, и симметричный ключ, зашифрованный открытым ключом. Для расшифровки действия производятся в обратном порядке: сначала при помощи секретного ключа получателя расшифровывается симметричный ключ, а затем при помощи симметричного ключа - полученный по каналу зашифрованный текст. Для формирования электронной подписи по подписываемому тексту вычисляется его однонаправленная хэш-функция (дайджест) [one-way hash function, digest], представляющая собой один короткий блок информации, характеризующий весь текст в целом; задача восстановления текста по его хэш-функции или подбора другого текста, имеющего ту же хэш-функцию, практически неразрешима. При непосредственном формировании подписи, вместо шифрования секретным ключом каждого блока текста секретный ключ применяется только к хэш-функции; по каналу передается сам текст и сформированная подпись хэш-функции. Для проверки подписи снова вычисляется хэш-функция от полученного по каналу текста, после чего при помощи открытого ключа проверяется, что подпись соответствует именно данному значению хэш-функции. Алгоритмы вычисления однонаправленных хэш-функций, как правило, логически тесно связаны с алгоритмами шифрования с симметричным ключом.

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

 

Шифр Эль Гамаля

Криптографы постоянно вели поиски более эффективных систем открытого шифрования, и в 1985 году Эль Гамаль предложил следующую схему на основе возведения в степень по модулю большого простого числа. Для этого задается большое простое число Р. Сообщения представляются целыми числами S из интервала (1, Р). Оригинальный протокол передачи сообщения S выглядит в варианте Шамира, одного из авторов RSA, так:

1. Отправитель А и получатель В знают лишь Р. А генерирует случайное число Х из интервала (1,Р) и В тоже генерирует случайное число Y из того же интервала.

2. А шифрует сообщение S1=S**X MOD Р и посылает В.

3.  В шифрует его своим ключом S2=S1**Y MOD Р и посылает S2 к А.

4. А "снимает" свой ключ S3=S2**(-X) MOD Р и возвращает S3 к В.

5. Получатель В расшифровывает сообщение: S=S3**(-Y) MOD Р.

Этот протокол можно применить, например, для таких неожиданных  целей, как игра в блэкджек по телефону. Крупье шифрует карты своим ключом и передает их игроку. Игрок выбирает наугад одну из карт, шифрует карты своим ключом и возвращает их крупье. Крупье "снимает" с выбранной карты свой ключ и отсылает ее игроку. "Сняв" с этой карты свой ключ игрок узнает ее номинал и принимает решение: спасовать, тянуть еще или раскрываться. Теперь, хотя колода находится у крупье, но он не может ее раскрыть, так как карты зашифрованы ключом игрока. Крупье выбирает свою карту аналогично игроку. (Аналогичный алгоритм для игры в карты можно реализовать и на основе шифрования заменой операцией XOR. Однако им нельзя распространять ключи из-за легкого перехвата и взлома.)

В системе Эль Гамаля большая степень защиты, чем у алгоритма RSA достигается с тем же по размеру N, что позволяет почти на порядок увеличить скорость шифрования и расшифрования. Криптостойкость системы Эль-Гамаля основана на том, что можно легко вычислить степень целого числа, то есть произвести умножение его самого на себя любое число раз так же, как и при операциях с обычными числами. Однако трудно найти показатель степени, в которую нужно возвести заданное число, чтобы получить другое, тоже заданное. В общем случае эта задача дискретного логарифмирования кажется более трудной, чем разложение больших чисел на простые сомножители, на основании чего можно предположить, что сложности вскрытия систем RSA и Эль Гамаля будут сходными. С точки зрения практической реализации, как программным, так и аппаратным способом ощутимой разницы между этими двумя стандартами нет. Однако в криптостойкости они заметно различаются. Если рассматривать задачу разложения произвольного целого числа длиной в 512 бит на простые множители и задачу логарифмирования целых чисел по 512 бит, вторая задача, по оценкам математиков, несравненно сложнее первой. Однако есть одна особенность. Если в системе, построенной с помощью алгоритма RSA, криптоаналитику удалось разложить открытый ключ N одного из абонентов на два простых числа, то возможность злоупотреблений ограничивается только этим конкретным пользователем. В случае же системы, построенной с помощью алгоритма Эль Гамаля, угрозе раскрытия подвергнутся все абоненты криптографической сети. Кроме того, упомянутые выше Ленстра и Манасси не только поколебали стойкость RSA, разложив девятое число Ферма на простые множители за неприлично короткое время, но и, как было замечено некоторыми экспертами, указали "брешь" в способе Эль Гамаля. Дело в том, что подход, применявшийся при разложении на множители девятого числа Ферма, позволяет существенно усовершенствовать методы дискретного логарифмирования для отдельных специальных простых чисел. То есть тот, кто предлагает простое Р для алгоритма Эль Гамаля, имеет возможность выбрать специальное простое, для которого задача дискретного логарифмирования будет вполне по силам обычным ЭВМ. Следует заметить, что этот недостаток алгоритма Эль Гамаля не фатален. Достаточно предусмотреть процедуру, гарантирующую случайность выбора простого Р в этой системе, и тогда только что высказанное возражение теряет силу. Стоит отметить, что чисел специального вида, ослабляющих метод Эль Гамаля, очень мало и случайным их выбором можно пренебречь.