1. Шифр Эль Гамаля На C++
2. Алгоритм Эль Гамаля

Читать тему: Алгоритм цифровой подписи Эль Гамаля (egsa) на сайте Лекция.Орг. Схема Эль-Гамаля — криптосистема с открытым ключом, основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема Эль-Гамаля лежит в основе бывших стандартов электронной цифровой.

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

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

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

Теоретические основы асимметричного шифрования Алгоритмы шифрования с открытым ключом основаны на использовании однонаправленных функций. Эти функции обладают следующим свойством: при заданном значении аргумента х относительно просто вычислить значение функции y = f(x), однако нахождение x, соответствующего заданному значению у, чрезвычайно трудно, точнее, связано с чрезмерно большим объемом вычислений, которые невозможно реализовать за обозримый промежуток времени. Примером однонаправленной функции может послужить следующая степенная функция. Y = f(x) = A xmod(n), где x и N – чрезмерно большие числа, а A – произвольное число из интервала 2, N – 2. При заданном значении х относительно просто вычислить значение у, тогда как для вычисления значения x = f -1(x) потребуется очень большой объем вычислений.

Шифр Эль Гамаля На C++

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

Общая схема шифрования с открытым ключом Пусть К — пространство ключей; m – открытый текст; с – шифртекст; e – ключ зашифрования; d – ключ расшифрования; E e — функция зашифрования для произвольного ключа e ϵ K; D d — функция расшифрования для произвольного ключа d ϵ K. Тогда зашифрование и расшифрование будут происходить по следующим формулам соответственно. Рисунок 1: Общая схема открытого шифрования Для того, чтобы гарантировать надежную защиту информации, к криптосистемам с открытым ключом предъявляются два важных и очевидных требования. Преобразование исходного текста должно быть условно необратимым и исключать его восстановление на основе открытого ключа. Определение закрытого ключа на основе открытого также должно быть невозможным на современном технологическом уровне.

Криптографические схемы с открытым ключом Наиболее известными криптосистемами с открытым ключом являются:. RSA. Используется задача факторизации (вычисления простых сомножителей) большого целого числа. Построен на основе перемножения двух простых чисел большой разрядности. Схема Эль-Гамаля (ELGamal). Основана на задаче дискретного логарифмирования в конечном поле.

Ранцевая криптосистема Меркля-Хеллмана. Основана на задаче об укладке ранца. Алгоритм шифрования RSA Криптосистема RSA разработана в 1977 году и названа в честь ее разработчиков: Rivest, Shamir и Adleman.

Вначале получатель шифртекстов создает пары ключей: открытого и секретного. Данный этап состоит из следующих операций:.

выбираются два достаточно больших простых числа p и q вычисляется их произведение n = p.q, называемое модулем;. выбирается целое число e, такое что e. Рисунок 2: Схема RSA Отправитель В создает зашифрованный текст С, возводя сообщение M в степень e и беря это значение по модулю n: C = M emod(n), где e и n – открытый (public) ключ лица А.Затем лицо В посылает С (зашифрованный текст) лицу А. Чтобы расшифровать полученный текст, А возводит полученный зашифрованный текст C в степень d и берет получившееся значение по модулю n: M = C d(mod n), где d и n – секретный (private) ключ лица А. Значение d вычисляется при помощи.

В настоящее время Лаборатория RSA рекомендует для обычных задач ключи размером 1024 бита, а для особо важных задач – 2048 бит. Алгоритм шифрования Эль-Гамаля Схема была предложена Тахером Эль-Гамалем в 1985 году. Алгоритм Эль-Гамаля базируется на трудности вычисления дискретного логарифма. Первый этап алгоритма Эль-Гамаля заключается в генерации ключей. Этот этап включает следующую последовательность действий:. Генерируется случайное простое число p длины n бит. Выбирается произвольное целое число a, являющееся по модулю p.

Выбирается случайное число x из интервала (1,p), взаимно простое с p-1. Вычисляется y = a x(mod p). Открытым ключом является тройка (a, p,y), закрытым ключом — число x. Второй этап алгоритма включает шифрование. Сообщение М шифруется следующим образом:. Выбирается случайное секретное число k, взаимно простое с p − 1. Вычисляется γ = a k(mod p), δ = M.

y k(mod p), где M — исходное сообщение. Пара чисел (γ,δ) является шифртекстом. Нетрудно заметить, что длина шифртекста в схеме Эль-Гамаля длиннее исходного сообщения M вдвое. Заключительный этап схемы Эль-Гамаля – это расшифрование.

Алгоритм Эль Гамаля

Зная закрытый ключ x и учитывая тот факт, что M = (δ. γ p-1-x)(mod p), исходное сообщение M можно вычислить из шифртекста (γ,δ) по формуле: M = γ -x. δ (mod p) На рисунке 3 приведена схема работы алгоритма шифрования Эль-Гамаля. Рисунок 3: Схема алгоритма Эль-Гамаля Ввиду того, что число k является произвольным, то такую схему еще называют схемой вероятностного шифрования. Вероятностный характер шифрования является преимуществом для схемы Эль-Гамаля, т.к.

У схем вероятностного шифрования наблюдается большая стойкость по сравнению со схемами с определенным процессом шифрования. Недостатком схемы шифрования Эль-Гамаля является удвоение длины зашифрованного текста по сравнению с начальным текстом. Для схемы вероятностного шифрования само сообщение M и ключ не определяют шифртекст однозначно. В схеме Эль-Гамаля необходимо использовать различные значения случайной величины k для шифровки различных сообщений M и M'. Если использовать одинаковые k, то для соответствующих шифртекстов (γ,δ) и (γ',δ') выполняется соотношение δ. (δ') -1 = M.

(M') -1(mod p). Из этого выражения можно легко вычислить M, если известно M'. Ранцевая криптосистема Меркла-Хеллмана В 1978 г. Меркль и Хеллман предложили использовать задачу об укладке рюкзака (ранца) для асимметричного шифрования.

Она формулируется следующим образом: дано множество предметов различного веса. Спрашивается, можно ли положить некоторые из этих предметов в ранец так, чтобы его вес стал равен определенному значению? Более формально задача формулируется так: дан набор значений M 1, M 2., М n и суммарное значение S; требуется вычислить значения b i такие, что S = b 1М 1 + b 2М 2 +. + b nМ n, где n – количество предметов; b i - бинарный множитель. Значение b i = 1 означает, что предмет i кладут в рюкзак, b i = 0 - не кладут.

Например, веса предметов имеют значения 1, 5, 6, 11, 14, 20, 32 и 43. При этом можно упаковать рюкзак так, чтобы его вес стал равен 22, использовав предметы весом 5, 6 и 11. Невозможно упаковать рюкзак так, чтобы его вес стал равен 24.

В основе алгоритма, предложенного Мерклом и Хеллманом, лежит идея шифрования сообщения на основе решения серии задач укладки ранца. Предметы из кучи выбираются с помощью блока открытого текста, длина которого (в битах) равна количеству предметов в куче. При этом биты открытого текста соответствуют значениям b, a текст является полученным суммарным весом. Пример шифрограммы, полученной с помощью задачи об укладке ранца, показан на рисунке 4. Рисунок 4: Пример шифрования на основе задачи об укладке ранца Суть использования данного подхода для шифрования состоит в том, что на самом деле существуют две различные задачи укладки ранца - одна из них решается легко и характеризуется линейным ростом трудоемкости, а другая, как принято считать, нет.

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

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

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

Он формируется на основе закрытого ключа и, как принято считать, не позволяет легко решить задачу об укладке ранца. Для его получения все значения закрытого ключа умножаются на число n по модулю m. Значение модуля m должно быть больше суммы всех чисел последовательности. Множитель n должен быть взаимно простым числом с модулем m. Для шифрования сообщение сначала разбивается на блоки, по размерам равные числу элементов последовательности в рюкзаке. Затем, считая, что единица указывает на присутствие элемента последовательности в рюкзаке, а ноль — на его отсутствие, вычисляются полные веса рюкзаков – по одному рюкзаку для каждого блока сообщения.

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