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

Данная система является альтернативой алгоритму 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 ; Просмотров: 4273 ; Нарушение авторских прав? ;

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

Открытое сообщение символ А Б Р А М О В
Код символа
Шифрограмма, С = Т 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.

Читайте также:  Что такое break в паскале

Открытый ключ представляет собой не сверхвозрастающую (нормальную) последовательность. Он формируется на основе закрытого ключа и, как принято считать, не позволяет легко решить задачу об укладке ранца. Для его получения все значения закрытого ключа умножаются на число 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 г.

Пример вычислений по алгоритму

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

Каждый абонент выбирает секретное число Х и вычисляет соответствующее ему открытое число Y . Пусть выбраны

Затем пользователи обмениваются открытыми ключами Y1 и Y2 . После этого каждый из пользователей может вычислить общий секретный ключ:

Теперь они имеют общий ключ 6 , который не передавался по каналу связи.

Вопросы практического использования алгоритма Диффи-Хеллмана

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

должны быть различными и состоять из целых положительных значений в диапазоне от 1 до Р-1 с некоторыми перестановками. Только в этом случае для любого целого Y и значения A можно найти единственную экспоненту Х , такую, что

При произвольно заданном Р задача выбора параметра А может оказаться трудной задачей, связанной с разложением на простые множители числа Р-1 . На практике можно использовать следующий подход, рекомендуемый специалистами. Простое число Р выбирается таким, чтобы выполнялось равенство Р = 2q + l , где q — также простое число. Тогда в качестве А можно взять любое число, для которого справедливы неравенства

Читайте также:  Russkaya klaviatura dlya android

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

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

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

Основные сведения

Асимметричный алгоритм , предложенный в 1985 году Эль-Гамалем (T. ElGamal), универсален. Он может быть использован для решения всех трех основных задач: для шифрования данных, для формирования цифровой подписи и для согласования общего ключа. Кроме того, возможны модификации алгоритма для схем проверки пароля, доказательства идентичности сообщения и другие варианты. Безопасность этого алгоритма, так же как и алгоритма Диффи-Хеллмана , основана на трудности вычисления дискретных логарифмов . Этот алгоритм фактически использует схему Диффи-Хеллмана, чтобы сформировать общий секретный ключ для абонентов, передающих друг другу сообщение, и затем сообщение шифруется путем умножения его на этот ключ.

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

Затем каждый абонент группы выбирает свое секретное число Хi, 1 , и вычисляет соответствующее ему открытое число . Таким образом, каждый пользователь может сгенерировать закрытый ключ Хi и открытый ключ Yi .

Информация о необходимых параметрах системы сведена в следующую таблицу.

Общие параметры Открытый ключ Закрытый ключ
Пользователь 1 Р, А Y1 Х1
Пользователь i Yi Хi

Шифрование

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

  1. Первый пользователь выбирает случайное число k , взаимно простое с Р-1 , и вычисляет числа

Если злоумышленник узнает или перехватит Р, А, Y2, r, e , то он не сможет по ним раскрыть m . Это связано с тем, что противник не знает параметр k , выбранный первым пользователем для шифрования сообщения m . Вычислить каким-либо образом число k практически невозможно, так как это задача дискретного логарифмирования. Следовательно, злоумышленник не может вычислить и значение m , так как m было умножено на неизвестное ему число. Противник также не может воспроизвести действия законного получателя сообщения (второго абонента), так как ему не известен закрытый ключ Х2 (вычисление Х2 на основании Y2 — также задача дискретного логарифмирования).

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