Алгоритм эль гамаля реферат

Обновлено: 18.05.2024

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

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

Протокол Диффи—Хеллмана

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

Протокол обмена состоит из следующих действий.

Алиса выбирает случайное
Боб выбирает случайное
Боб вычисляет сессионный ключ
Алиса вычисляет

Алиса выбирает случайное
Меллори выбирает случайное
Меллори вычисляет сессионный ключ для канала с Алисой

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

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

Стороны договорились о группе точек эллиптической кривой , её циклической подгруппе мощности и генераторе группы (или хотя бы достаточно большой подгруппы группы ).
Алиса выбирает случайное
Боб выбирает случайное
Боб вычисляет точку
Алиса вычисляет точку

Протокол Эль-Гамаля

Протокол Эль-Гамаля ([ElGamal, 1984], [ElGamal, 1985]) за счёт предварительного распространения открытого ключа одной из сторон обеспечивает аутентификацию ключа для этой стороны. Можно гарантировать, что только владелец соответствующего закрытого ключа сможет вычислить сеансовый ключ. Однако подтверждение факта получение ключа (выполнение целей G1 и G8) не является частью протокола.

Протокол MTI/A(0)

В 1986 году Ц. Мацумото (Tsutomu Matsumoto), И. Такашима (Youichi Takashima) и Х. Имаи (Hideki Imai) предложили несколько алгоритмов, позже названных семейством протоколов MTI ([Matsumoto, Tsutomu, Imai 1986]). За счёт предварительного распространения открытых ключей обоих сторон они обеспечивали неявную аутентификацию ключа (цель G7). То есть сессионный ключ гарантированно мог получить только владельцы соответствующих открытых ключей. Мы рассмотрим одного из представителей данного семейства — протокол MTI/A(0).

Предварительно стороны договорились об общих параметрах системы и , где — большое простое число, а — примитивный элемент поля .

Алиса сгенерировала случайное число
Боб сгенерировал случайное число
Боб вычислил сеансовый ключ
Алиса вычислила сеансовый ключ

Протокол Station-to-Station

Протокол STS (Station-to-Station, [Diffie, Oorschot, Wiener 1992]) предназначен для систем мобильной связи. Он использует идеи протокола Диффи—Хеллмана и криптосистемы RSA. Особенностью протокола является использование механизма электронной подписи для взаимной аутентификации сторон.

Каждая из сторон и обладает долговременной парой ключей: закрытым ключом для расшифрования и создания электронной подписи и открытым ключом для шифрования и проверки подписи .

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

Как показала атака Лоу 1996 года ([Lowe 1996]), протокол не может гарантировать аутентификацию субъектов (цель G1), ключей (G7) и подтверждение владения сессионным ключом (G8). Хотя злоумышленник не может получить доступ к новому сессионному ключу, если протокол использовать только для аутентификации субъектов, Алиса может принять злоумышленника за Боба.

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

Цель работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Б Г У И Р - В И В А Т

02 04 21 10 18 00 03 10 03 01 20

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

P=213452567387503920589

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

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

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

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

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

Ключевые слова: криптосистема с открытым ключом, криптосистема Эль-Гамаля, стойкость алгоритма.

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

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

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

В криптографии различают частные ключевые криптографические системы и ключевые криптографические системы с общественностью. Секретный ключ криптографии, также известный как секретный ключ или симметричный ключ шифрования, имеет давнюю историю, и основан он на использовании одного ключа для шифрования и дешифрования. Многие развитые современные частные ключевые криптографические системы основаны на Feistel шифре (например, национальный стандарт шифрования США (DES), шифр (стандарт) DES с трёхкратным шифрованием (3DES), новый национальный стандарт шифрования США (AES), международный алгоритм шифрования данных (IDEA), Blowfish, RC5, CAST и т. д.

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

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

Для данной работы была выбрана криптосистема Эль-Гамаля и на её основе исследована стойкости криптосистемы Эль-Гамаля, некоторые нападения на схеме Эль-Гамаля, чтобы избежать атак.

2. КРИПТОСИСТЕМЫ ЭЛЬ-ГАМАЛЯ

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

Числа — публикуются как открытый ключ, — сохраняется как секретный ключ.

Затем, В вычисляет

или

Пара чисел образует криптотекст. В посылает А пару .

или .

3. СТОЙКОСТЬ АЛГОРИТМА

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

Укажем некоторые определенные недостатки в схеме Эль-Гамаля:

1. Алферов А. П., Зубов А. Ю., Кузьмин А. С., Черемушкин А. В. Основы криптографии. 3-е изд., испр. и доп. — М.: Гелиос АРБ. 2005.

2. Баричев Б. Б., Гончаров В. В., Серов Р. Е. Основы современной криптографии. М.: Горячая линия-Телеком, 2011.

3. Болотов А. А., Гашков С. Б., Фролов А. Б., Часовских А. А. Алгоритмические основы эллиптической криптографии. М. Мэи. 2000.

4. Прасолов В. В., Соловьев Ю. П. Эллиптические функции и алгебраические уравнения. М.: Факториал. 1977.

5. Яковлев А. В., Безбогов А. А., Родин В. В., Шамкин В. Н. Криптографическая защита информации. Издательство ТГТУ. 2006.

6. William Stallings. Cryptography and Network Security Principles and Practice. Prentice Hall. 2011.

Основные термины (генерируются автоматически): открытый ключ, DES, RSA, схема Эль-Гамаля, алгоритм Эль-Гамаля, КРИПТОСИСТЕМа ЭЛЬ-ГАМАЛЯ, секретный ключ, шифрованный текст, дискретное логарифмирование, квадратичный вычет.

Функция "чтения" служит для ознакомления с работой. Разметка, таблицы и картинки документа могут отображаться неверно или не в полном объёме!

Некоммерческое акционерное общество

Факультет аэрокосмических и информационных технологий

Кафедра компьютерной и инфокоммуникационной безопасности

РАСЧЕТНО-ГРАФИЧЕСКАЯ РАБОТА №2

Выполнил: Телқожа А.Н.

Принял: ст.преп. Якубов Б.М.

СодержаниеВведение

Задание 1.Система с открытым ключом Диффи-Хелмана

Задание 2. Шифрование по алгоритму Шамира

Задание 3.Шифрование по алгоритму Эль-Гамаля

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

Протокол Ди́ффи-Хе́ллмана (англ.DiffieHellman, DH) - криптографический протокол, позволяющий двум и более сторонам получить общий секретный ключ, используя незащищенный от прослушивания канал связи. Полученный ключ используется для шифрования дальнейшего обмена с помощью алгоритмов симметричного шифрования.

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

Схема Эль-Гамаля (Elgamal) - криптосистема с открытым ключом, основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема Эль-Гамаля лежит в основе бывших стандартов электронной цифровой подписи в США(DSA) и России (ГОСТ Р 34.10-94).

Схема была предложена Тахером Эль-Гамалем в 1985 году. Эль-Гамаль разработал один из вариантов алгоритма Диффи-Хеллмана. Он усовершенствовал систему Диффи-Хеллмана и получил два алгоритма, которые использовались для шифрования и для обеспечения аутентификации. В отличие от RSA алгоритм Эль-Гамаля не был запатентован и, поэтому, стал более дешевой альтернативой, так как не требовалась оплата взносов за лицензию. Считается, что алгоритм попадает под действие патента Диффи-Хеллмана.

Задание 1. Система с открытым ключом Диффи-Хелмана

защита информация телекоммуникационный криптография

Рисунок 1 - схема обмена ключами в системе Диффи-Хелмана Сгенерировать секретные ключи для пяти абонентов A, B, C, D и Е по методу Диффи-Хеллмана (DH). Так как последние цифры студенческого билета 58, то i=5 и j=8. Значит по варианту исходные данные

Читайте также: