Криптосистема Эль Гамаля.Электронная подпись Эль Гамаля

Министерство  образования Республики Беларусь 
 

Учреждение  образования

Белорусский Государственный университет

 информатики  и радиоэлектроники 
 
 
 
 

Республиканский конкурс научных работ студентов

высших  учебных заведений Республики Беларусь 
 

     Девиз: Для меня нет неудач, просто бывают не те победы… 
 
 
 

Криптосистема Эль Гамаля.Электронная подпись Эль Гамаля.

      
 

 Выполнил:

        Баханович Дмитрий Анатольевич

 студент 3 курса, гр.  761401 
 

Научный руководитель:

Данцевич  Светлана Фёдоровна

ассистент кафедры

высшей  математики 
 
 
 
 
 
 
 
 
 

Минск, 2009

     Реферат 

    Работа  15 с., 6 источников.

Защита информации, криптографический   метод, криптосистемы с открытым ключом, криптосистема Эль-Гамаля, электронная подпись, открытый и секретный ключи, отправитель и адресат сообщения. 

     Объект  исследования или  разработки 

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

      Цель работы 

      Целью работы является освоение практического  применения криптосистемы Эль-Гамаля и цифровой подписи на её основе. 

      Метод проведения работы 

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

      Результаты работы 

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

Было продемонстрировано практическое применение методик защиты информации. 
 

Область применения 

Практические занятия по прикладной математике.

 
 
 
 
 

       СОДЕРЖАНИЕ

ВВЕДЕНИЕ           4

1 Криптосистемы  с открытым ключом    5

2 Криптосистема Эль-Гамаля    6

3 Пример шифрования  с помощью криптосистемы Эль-Гамаля    7

4 Электронная  подпись          9

5 Схема Эль-Гамаля          10

6 Пример формирования  цифровой подписи по схеме  Эль-Гамаля     11

ЗАКЛЮЧЕНИЕ     14

ЛИТЕРАТУРА     15 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     ВВЕДЕНИЕ 

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

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

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

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

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

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

      1. Криптосистемы с открытым ключом 

     Основы  криптографии с открытыми ключами  были выдвинуты Уитфилдом Диффи (Whitfield Diffie) и Мартином Хеллманом (Martin Hellman), и независимо Ральфом Мерклом(Ralph Merkle). Их вкладом в криптографию было убеждение, что ключи можно использовать парами - ключ шифрования и ключ дешифрирования - и что может быть невозможно получить один ключ из другого. Диффи и Хеллман впервые представили эту идею на Национальной компьютерной конференции 1976г., через несколько месяцев была опубликована их основополагающая работа "New Directions in Cryptography" ("Новые направления в криптографии"). Первая работа Меркла вышла в 1978г.

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

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

-     разложение больших чисел на простые множители (RSA);

-     вычисление логарифма в конечном поле (криптосистема Эль-Гамаля);

- вычисление корней алгебраических уравнений (на основе эллиптических уравнений).

      Криптосистемы с открытым ключом можно использовать в трех назначениях:

- как самостоятельные средства защиты передаваемых и хранимых данных;

- как средства для распределения ключей;

- средства аутентификации пользователей. 
 
 
 
 

     2. Криптосистема Эль-Гамаля 

     Появилась в 1985  году [3] как реакция на излишнюю сложность криптосистемы RSA. Криптостойкость её базируется на иной проблеме – проблеме дискретного логарифма: решение уравнения    в кольце  с простым   на сегодняшний день осуществляется единственным способом – последовательным перебором степеней    до получения требуемого класса вычетов Проблема и состоит в нахождении иного, не переборного метода определения степени в данном уравнении.

      В основе криптосистемы Эль-Гамаля лежит большое простое число   Для реальных, не учебных криптосистем оно должно содержать от 150 до 300 десятичных знаков. А это означает, что   находится в диапазоне от    до    Как мы знаем, кольцо классов вычетов    является полем, так как в нём все ненулевые классы вычетов обратимы относительно умножения. Более того, известно, что мультипликативная группа  этого поля имеет порядок   и является циклической.  Предполагается также, что среди делителей   имеется другое большое простое число   Пусть одна из образующих этой мультипликативной группы. Найти эту образующую – также не простая задача. Но это предварительная проблема, стоит перед разработчиками криптосистемы в период её формирования. Параметры   и   общедоступны, считаются открытыми ключами криптосистемы.

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

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

3. Пример шифрования с помощью криптосистемы Эль-Гамаля 

      С помощью алгоритма Эль-Гамаля зашифруем девиз: 

БГУИР-ВИВАТ

      Передаваемая  информация первоначально преобразуется  в цифровую форму – в некоторое десятичное число  (это обозначение идёт от слова «сообщение»), данный этап  шифрованием, собственно, и не считается. Авторы криптосистемы предложили самый немудрёный способ перевода словесной информации в числовую: букву “а” заменяем числом 01, букву “б” – числом 02,…, “я” – числом 33, пробел - 00. 

Б    Г    У   И   Р     -   В    И   В   А   Т

02  04 21  10  18  00  03  10  03  01  20 

Получим сообщение: С=204211018000310030120 

Выберем открытые ключи:

P=213452567387503920589

g=2

Секретный ключ:

X=5

Вычислим третий открытый ключ криптосистемы по формуле:

 
 

Для передачи сообщения    формируем сеансовый ключ 

Пусть k=3. 

Вычислим значение:

Таким образом, шифрованное сообщение:  

 
 

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

 
 
 
 

Числа: 
 

Он знает заранее.

      Итак, получателю отправляется криптограмма с конкретными числами (m, )=( ,8)

Получатель, приняв данную криптограмму, для её прочтения вычисляет следующие величины:

 
 

К=32768(mod P) 

Осталось найти    в поле  

 
 

Получим исходное сообщение:

 
 

Или 

Б    Г    У   И   Р     -   В    И   В   А   Т