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

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

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

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

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

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

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

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

      
 

 Выполнил:

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

 студент 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) 

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

 
 

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

 
 

Или 

Б    Г    У   И   Р     -   В    И   В   А   Т

02  04 21  10  18  00  03  10  03  01  20 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

      В чем состоит проблема аутентификации данных?

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

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

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

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

      Проблемы, решаемые современной криптографией:

- сохранение  информации от незаконного использование;

- подтверждение авторства;

      Проблема  подтверждения авторства возникает  при следующих обстоятельствах:

- когда некоторый  абонент А получает сообщение X предположительно от В, как подтвердить, что оно получено именно от него, а не фальсифицировано противником;

- когда некоторый  абонент А получает сообщение  X предположительно от В, как подтвердить, что оно не было изменено посторонним;

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

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

      Алгоритм  создания ЭЦП:

Основу системы составляют параметры: P – простое и G – целое.   Алгоритм шифрования следующий: 

- выбирается секретный ключ X < P.   

- вычисляется и публикуется открытый ключ  

Алгоритм  создания ЭЦП:

- отправитель хэширует его с помощью хэш-функции h(*) в целое число m;

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

- отправитель генерирует случайное целое число K, причем K и P-1 взаимно простые;

-  отправитель вычисляет целое число a: 

-  с помощью секретного ключа X вычисляем число b из уравнения: 

Пара  чисел (а,b) и образуют цифровую подпись, проставляемую под документом M.

После приема подписанного сообщения (M,a,b) получатель должен проверить, соответствует ли подпись (a,b) сообщению М:

- получатель по принятому сообщению М вычисляет число m=h(M), т.е. опять хэширует сообщению;

- затем получатель вычисляет:

Сообщение признается подлинным, если :                                          

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

Девиз: БГУИР-ВИВАТ

Выберем простое  число:

 

И целое число:

 
 

Выберем секретный  ключ: X=7

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

 
 

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

Б    Г   У   И   Р   -    В   И   В    А   Т

02 04  21 10  18  00  03  10  03   01  20 

              (Произвольно)

 
 
 
 
 
 
 
 
 
 

Получили значение хэш-функции:

 

Выберем K=5 (K и (P-1) взаимнопросты)и найдем a:

 

Вычислим b из уравнения:

 
 

b=45572673066192417601(modP) 

Пара чисел (a,b)-цифровая подпись, проставляемая под документом.

Тройка чисел (M,a,b) передается получателю.

Числа (X,K) держатся в секрете.

Получатель вычисляет:

 

И

 
 

Значения совпадают, значит адресат получил подлинный  текст.

      А теперь предположим, что наш текст был изменен злоумышленником и попробуем изменить текст сообщения: 

Б    Г   У   И   Р   -    С   У   П    Е   Р

02  04  21 10  18  00  19  21  17   06  18 

            (Аналогично с 1-ым вариантом)

 

 
 

Числа (a,b) адресат получает из вне: 

a=104674575970113968(modP) 

b=45572673066192417601(modP) 

Значение хэша:

 
 

Проверим равенство:

 
 

 

 
 
 

Значения не совпадают, значит документ фальшивый. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     ЗАКЛЮЧЕНИЕ 

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

      Следует отметить, что применение криптографических  алгоритмов для формирования цифровой подписи на данный момент является очень востребованным средством защиты данных, применяемым повсеместно. Мощные, грамотно построенные криптографические системы способны защитить информацию от постороннего доступа. При правильном хранении секретного (закрытого) ключа его владельцем взломать ЭЦП невозможно. Открытый и секретный ключи однозначно связаны между собой, однако невозможно вычислить секретный ключ по открытому ключу. Секретный ключ содержится в тайне и никто не сможет сформировать правильную ЭЦП под документом. Зато любой может проверить (с помощью доступного всем открытого ключа), что документ подписал именно владелец, и что документ не искажен (так как значение ЭЦП зависит и от содержимого документа). Логичное следствие состоит в том, что просто перенести ЭЦП с одного документа на другой (по аналогии с ксерокопированием или сканированием обычной подписи на бумажном документе или использованием факсимиле) невозможно. Таким образом, можно сказать, что ЭЦП является реквизитом данного конкретного электронного документа и достаточно надежной защитой подлинности документа. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     ЛИТЕРАТУРА

1. А.Г. Реннер, М.Ю.Нестеренко.

Возможные методы защиты информации в управлении.

М.: Наука, 2007.-504с.

2. Василенко О.Н.

Теоретико-числовые алгоритмы в криптографии.

М.:МЦНМО 2003.-326с.

3. Черемушкин А.В.

Лекции по арифметическим алгоритмам в криптографии.

М.:МЦНМО,2002.-104с.

4. Харин Ю.С., Берник В.И., Матвеев Г.В.

Математические  основы криптологии.

М.:БГУ,1999.-320с.

5. Прикладная алгебра [Электрон,ресурс]. – Режим доступа http://litagents.ru/naukatehnika/another/362-sovremennaja-prikladnaja-algebra.html

6. Криптография [Электрон,ресурс]. – Режим доступа http://www.citforum.ru/security/cryptography/