No Image

Шифр эль гамаля пример

СОДЕРЖАНИЕ
0 просмотров
22 января 2020

Данная система является альтернативой алгоритму RSA и при равном значении ключа обеспечивает ту же криптостойкость. Эль-Гамаль (Taher Elgamal) усовершенствовал алгоритм Диффи-Хеллмана и получил алгоритмы для шифрования и для обеспечения аутентификации. Алгоритм основан на проблеме поиска дискретного логарифма. Если возводить целое число в степень достаточно легко, то восстановить целочисленный аргумент по значению (то есть найти логарифм) довольно трудно.

Для генерации пары ключей сначала выбирается простое число p и два случайных числа, g и x, оба меньше p. Затем вычисляется

Открытым ключом являются y, g и p. Величины g, и p можно сделать общими для группы пользователей. Закрытым ключом является x.

Для шифрования сообщения M сначала выбирается случайное число k,

взаимно простое с (p – 1). Затем вычисляются

Пара (a, b) является шифротекстом. Получаемый шифротекст в два раза длиннее открытого текста. Для дешифрирования (a, b) вычисляется

Так как a xg kx (mod p) и b/a xy k M/a xg xk M/ g kx = M (mod p), то все действительно так и получается. Или иначе:

a x mod p = y k mod p (g k mod p) x mod p = (g x mod p) k mod p.

Каждая подпись или шифрование алгоритмом ELGamal требует нового значения k, и это значение должно быть выбрано случайным образом. Если когда-нибудь злоумышленник раскроет k, он сможет раскрыть закрытый ключ x. Если злоумышленник когда-нибудь сможет получить два сообщения, подписанные или зашифрованные с помощью одного и того же k, то он сможет раскрыть x, даже не зная значение k.

Рассмотрим алгоритм криптосистемы Эль-Гамаля.

Выбираем открытый ключ p и g:

p простое число (может быть общим для группы пользователей),

выбираем случайное k, которое взаимно простое с p–1;

Приведем пример использования метода Эль-Гамаля для шифрования сообщения 2, 5, 7. Для простоты вычислений будем использовать маленькие числа (на практике используются числа существенно большие).

1. Выберем простое число p=19; g=5 (g x mod p=5 11 mod 19=6.

3. Шифруем сообщение a=g k mod p=5 13 mod 19=17,

4. Дешифрование сообщения

Необходимо отметить, что операции возведения в степень больших чисел достаточно трудоемки для современных процессоров, даже если они производятся по оптимизированным по времени алгоритмам. Так быстродействие RSA в тысячу раз ниже, чем у DES или ГОСТ 28147-89. Поэтому обычно весь текст сообщения кодируется обычным блочным шифром (симметричным алгоритмом), намного более быстрым, но с использованием ключа сеанса, а вот сам ключ сеанса шифруется как раз асимметричным алгоритмом с помощью открытого ключа получателя и помещается в начало файла. Такой механизм называют цифровым конвертом.

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

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

| следующая лекция ==>
Алгоритм RSA | Шифрование с использованием эллиптических кривых

Дата добавления: 2014-01-15 ; Просмотров: 4216 ; Нарушение авторских прав? ;

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

Открытое сообщение символ А Б Р А М О В
Код символа
Шифрограмма, С = Т 5 mod 91
Открытое сообщение, Т = С 29 mod 91

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

В заключении следует отметить стойкость данного алгоритма. В 2003 г. Ади Шамир и Эран Тромер разработали схему устройства TWIRL, которое при стоимости $ 10 000 может дешифровать 512-битный ключ за 10 минут, а при стоимости $ 10 000 000 – 1024-битный ключ меньше, чем за год. В настоящее время Лаборатория RSA рекомендует использовать ключи размером 2048 битов.

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

Процедура создания ключей

№ п/п Описание операции Пример
Выбираются простое число p и два любых случайных числа g и x меньше p. p=23, g=3, x=5
Вычисляется y = g x mod p y = 3 5 mod 23 = 243 mod 23 = 13
Открытый ключ – y, g и p. Причем g и p можно сделать общими для группы пользователей. Закрытый ключ – x.

Перед шифрованием вначале выбирается k взаимно простое с p-1, после чего шифрограмма генерируется по следующим формулам

a = g k mod p, (10)

b = (y k mod p) Å T, (11)

где a, b – зашифрованное сообщение.

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

T = (a x mod p) Å b. (12)

Пример шифрования и дешифрования по алгоритму Эль-Гамаля при k=7 приведен в таблице. Первая часть шифрованного сообщения – a = 37 mod 23 = 2.

Пример шифрования по алгоритму Эль-Гамаля

Открытое сообщение, символ А Б Р А М О В
Код символа
Вторая часть шифрограммы, b = (13 7 mod 23) Å T = 9 Å T
Открытое сообщение, T = (2 5 mod 23) Å b = 9 Å b

Алгоритм на основе задачи об укладке ранца [1]. Проблема укладки ранца формулируется следующим образом. Дано множество предметов различного веса. Спрашивается, можно ли положить некоторые из этих предметов в ранец так, чтобы его вес стал равен определенному значению? Более формально задача формулируется так: дан набор значений M1, M2, . Мn и суммарное значение S; требуется вычислить значения bi такие что

где n – количество предметов;

bi – бинарный множитель. Значение bi = 1 означает, что предмет i кладут в рюкзак, bi = 0 – не кладут.

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

Читайте также:  Типы наушников для телефона

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

Пример шифрования на основе задачи об укладке ранца

Открытый текст 1 1 1 0 0 1 0 0 0 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0
Рюкзак (ключ) 1 5 6 11 14 20 32 43 1 5 6 11 14 20 32 43 1 5 6 11 14 20 32 43
Шифрограмма 32 (1+5+6+20) 73 (5+11+14+43)

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

В качестве закрытого ключа (легкого для укладки ранца) используется сверхвозрастающая последовательность. Сверхвозрастающей называется последовательность, в которой каждый последующий член больше суммы всех предыдущих. Например, последовательность <2, 3, 6, 13, 27, 52, 105, 210>является сверхвозрастающей, а <1, 3, 4, 9, 15, 25, 48, 76>— нет.

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

Например, пусть полный вес рюкзака равен 270, а последовательность весов предметов равна <2, 3, 6, 13, 27, 52, 105, 210>. Самый большой вес – 210. Он меньше 270, поэтому предмет весом 210 кладут в рюкзак. Вычитают 210 из 270 и получают 60. Следующий наибольший вес последовательности равен 105. Он больше 60, поэтому предмет весом 105 в рюкзак не кладут. Следующий самый тяжелый предмет имеет вес 52. Он меньше 60, поэтому предмет весом 52 также кладут в рюкзак. Аналогично проходят процедуру укладки в рюкзак предметы весом 6 и 2. В результате полный вес уменьшится до 0. Если бы этот рюкзак был бы использован для дешифрования, то открытый текст, полученный из значения шифртекста 270, был бы равен 10100101.

Открытый ключ представляет собой не сверхвозрастающую (нормальную) последовательность. Он формируется на основе закрытого ключа и, как принято считать, не позволяет легко решить задачу об укладке ранца. Для его получения все значения закрытого ключа умножаются на число n по модулю m. Значение модуля m должно быть больше суммы всех чисел последовательности, например, 420 (2+3+6+13+27+52+105+210=418). Множитель n должен быть взаимно простым числом с модулем m, например, 31. Результат построения нормальной последовательности (открытого ключа) представлен в следующей таблице.

Пример получения открытого ключа

Закрытый ключ, ki
Открытый ключ, (ki*n) mod m = (ki*31) mod 420

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

В качестве примера возьмем открытое сообщение «АБРАМОВ», символы которого представим в бинарном виде в соответствии с табл. 3. Результат шифрования с помощью открытого ключа <62, 93, 186, 403, 417, 352, 315, 210>представлен в табл.18.

Пример шифрования

Открытое сообщение Сумма весов Шифрограмма (рюкзак), ci
Символ Bin-код
А 1100 0000 62+93
Б 1100 0001 62+93+210
Р 1101 0000 62+93+403
А 1100 0000 62+93
М 1100 1100 62+93+417+352
О 1100 1110 62+93+417+352+315
В 1100 0010 62+93+315

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

В нашем примере сверхвозрастающая последовательность равна <2, 3, 6, 13, 27, 52, 105, 210>, m = 420, n = 31. Значение n -1 равно 271 (31*271 mod 420 = 1).

Пример расшифрования

Шифрограмма (рюкзак), ci (ci*n -1 ) mod m = (ci*271) mod 420 Сумма весов Открытое сообщение
Bin-код Символ
2+3 1100 0000 А
2+3+210 1100 0001 Б
2+3+13 1101 0000 Р
2+3 1100 0000 А
2+3+27+52 1100 1100 М
2+3+27+52+105 1100 1110 О
2+3+105 1100 0010 В

В заключении следует отметить, что задача вскрытия данного способа шифрования успешно решена Шамиром и Циппелом в 1982 г.

Contents

Постановка задачи защиты информации

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

Читайте также:  1 Бит равен 8 байт таблица

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

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

Теоретические основы асимметричного шифрования

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

где x и N – чрезмерно большие числа, а A – произвольное число из интервала [2, N – 2]. При заданном значении х относительно просто вычислить значение у, тогда как для вычисления значения x = f -1 (x) потребуется очень большой объем вычислений.

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

Общая схема шифрования с открытым ключом

Пусть К — пространство ключей;

m – открытый текст;

e – ключ зашифрования;

d – ключ расшифрования;

Ee — функция зашифрования для произвольного ключа e ϵ K;

Dd — функция расшифрования для произвольного ключа d ϵ K.

Тогда зашифрование и расшифрование будут происходить по следующим формулам соответственно:

Ee является однонаправленной функцией, а d — лазейкой. Таким образом, зная e, невозможно определить соответствующий ключ расшифрования d.

На рисунке 1 представлена схема передачи информации лицом А лицу В. Отправитель А зашифровывает сообщение m с помощью открытого ключа e и передает получившийся шифртекст с по открытому (незащищенному) каналу получателю В. Получатель В, в свою очередь, расшифровывает полученный шифртекст с с помощью секретного ключа d и получает исходный текст m.

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

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

2. Определение закрытого ключа на основе открытого также должно быть невозможным на современном технологическом уровне.

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

Наиболее известными криптосистемами с открытым ключом являются:

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

Алгоритм шифрования RSA

Криптосистема RSA разработана в 1977 году и названа в честь ее разработчиков: Rivest, Shamir и Adleman.

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

  1. выбираются два достаточно больших простых числа p и q вычисляется их произведение n = p*q, называемое модулем;
  2. выбирается целое число e, такое что e M e mod(n) = C,

где С – получившийся шифртекст.

Расшифрование шифртекста С выполняется по формуле:

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

На рисунке 2 представлена схема передачи информации лицом В лицу А.

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

В настоящее время Лаборатория RSA рекомендует для обычных задач ключи размером 1024 бита, а для особо важных задач – 2048 бит.

Алгоритм шифрования Эль-Гамаля

Схема была предложена Тахером Эль-Гамалем в 1985 году. Алгоритм Эль-Гамаля базируется на трудности вычисления дискретного логарифма.

Первый этап алгоритма Эль-Гамаля заключается в генерации ключей. Этот этап включает следующую последовательность действий:

  1. Генерируется случайное простое число p длины n бит.
  2. Выбирается произвольное целое число a, являющееся первообразным (примитивным) корнем по модулю p.
  3. Выбирается случайное число x из интервала (1,p), взаимно простое с p-1.
  4. Вычисляется y = a x (mod p).

Открытым ключом является тройка (a, p ,y) , закрытым ключом — число x.

Второй этап алгоритма включает шифрование.

Сообщение М шифруется следующим образом:

  1. Выбирается случайное секретное число k, взаимно простое с p − 1.
  2. Вычисляется

γ = a k (mod p), δ = M * y k (mod p),

где M — исходное сообщение. Пара чисел (γ,δ) является шифртекстом.

Нетрудно заметить, что длина шифртекста в схеме Эль-Гамаля длиннее исходного сообщения M вдвое.

Заключительный этап схемы Эль-Гамаля – это расшифрование.

Зная закрытый ключ x и учитывая тот факт, что M = (δ * γ p-1-x )(mod p), исходное сообщение M можно вычислить из шифртекста (γ,δ) по формуле:

Читайте также:  Часы на ин 12б

M = γ -x * δ (mod p) На рисунке 3 приведена схема работы алгоритма шифрования Эль-Гамаля.

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

Если использовать одинаковые k, то для соответствующих шифртекстов (γ,δ) и (γ’,δ’) выполняется соотношение δ * (δ’) -1 = M * (M’) -1 (mod p). Из этого выражения можно легко вычислить M, если известно M’.

Ранцевая криптосистема Меркла-Хеллмана

В 1978 г. Меркль и Хеллман предложили использовать задачу об укладке рюкзака (ранца) для асимметричного шифрования. Она формулируется следующим образом: дано множество предметов различного веса. Спрашивается, можно ли положить некоторые из этих предметов в ранец так, чтобы его вес стал равен определенному значению? Более формально задача формулируется так: дан набор значений M1, M2, . Мn и суммарное значение S; требуется вычислить значения bi такие, что

где n – количество предметов; bi – бинарный множитель. Значение bi = 1 означает, что предмет i кладут в рюкзак, bi = 0 – не кладут.

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

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

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

В качестве закрытого ключа (легкого для укладки ранца) используется сверхвозрастающая последовательность.

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

Для расшифрования сообщения получатель должен сначала определить обратное число n -1 , такое что (n * n -1 )mod m = 1.

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

Практическое применение в современных технологиях

Алгоритм RSA используется для защиты программного обеспечения и в схемах цифровой подписи.Также он используется в открытой системе шифрования PGP и иных системах шифрования (к примеру, DarkCryptTC и формат xdc) в сочетании с симметричными алгоритмами.Из-за низкой скорости шифрования (около 30 кбит/с при 512 битном ключе на процессоре 2 ГГц), сообщения обычно шифруют с помощью более производительных симметричных алгоритмов со случайным ключом (сеансовый ключ), а с помощью RSA шифруют лишь этот ключ, таким образом реализуется гибридная криптосистема. Такой механизм имеет потенциальные уязвимости ввиду необходимости использовать криптостойкий генератор случайных чисел для формирования случайного сеансового ключа симметричного шифрования и эффективно противостоящий атакам на симметричный криптоалгоритм (в данное время широкое применение находят AES, IDEA, Serpent, Twofish).

Для криптосистемы RSA есть стандарт RFC 2437 – PKCS #1: RSA Cryptography Specifications Version 2.0.

Схема Эль-Гамаля используется в стандартах Электронной Цифровой Подписи [ЭЦП] DSS , ГОСТ Р34.10-94.

Глоссарий

Пример реализации алгоритма асимметричного шифрования RSA

Скачать исходный код данного приложения – [1]

Библиографический указатель

Перейти к списку литературы по разделу "Схемы открытого шифрования"

Комментировать
0 просмотров
Комментариев нет, будьте первым кто его оставит

Это интересно
Adblock detector