|
3.4. Формирование ключей алгоритма Эль-Гамаля
Схема Эль-Гамаля (Elgamal) — криптосистема с открытым ключом, основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема Эль-Гамаля лежит в основе бывших стандартов электронной цифровой подписи в США (DSA) и России (ГОСТ Р 34.10-94).
Схема была предложена Тахером Эль-Гамалем в 1985 году. Эль-Гамаль разработал один из вариантов алгоритма Диффи-Хеллмана. Он усовершенствовал систему Диффи-Хеллмана и получил два алгоритма, которые использовались для шифрования и для обеспечения аутентификации. В отличие от RSA алгоритм Эль-Гамаля не был запатентован и, поэтому, стал более дешевой альтернативой, так как не требовалась оплата взносов за лицензию. Считается, что алгоритм попадает под действие патента Диффи-Хеллмана.
Секретным ключом может являться любое натуральное число x. Для определения открытого ключа вычисляется число у по формуле (3.1):
у = 𝑔𝑥(𝑚𝑜𝑑 𝑝) (3.1)
Группа чисел (p,g,y) – открытый ключ.
Шифрование
Сообщение в этой системе представляется как элемент m. Для его шифрования поступают следующим образом:
1. Генерируют случайный ключ k – взаимнопростой с p – 1,
что 1 ≤ k ≤ p – 1;
2. Вычисляют 𝐶1 = 𝑔𝑘(𝑚𝑜𝑑 𝑝);
3. Находят С2 = 𝑚×𝑦𝑘(𝑚𝑜𝑑 𝑝);
4. Выдают получившийся шифротекст в виде пары С = (C1,С2).
Заметим, что при каждом шифровании применяется свой кратковременный ключ. Поэтому, шифруя одно сообщение дважды, мы получаем разные шифротексты.
Дешифрование
Чтобы расшифровать пару данных С = (C1,C2), производят следующие преобразования:
(𝐶2/𝐶1𝑥)(𝑚𝑜𝑑 𝑝) = ((𝑚×𝑦𝑘)/𝑔𝑘𝑥) (𝑚𝑜𝑑 𝑝)= (𝑚×𝑔𝑘𝑥)/𝑔𝑘𝑥 =𝑚. (3.2)
Формула (3.2) является доказательством того, что преобразование является верным.
Достоинства системы Эль-Гамаль:
1. Каждый пользователь системы должен выбрать случайное число и сделать не сложное вычисление, которая требует, чтобы каждый пользователь системы находил два больших простых числа, что является сложной вычислительной задачей.
2. Каждый раз при шифровании используем свой кратковременный ключ.
3. При заданном уровне стойкости алгоритма целые числа, участвующие в вычислениях, имеют запись на 25% короче, что уменьшает сложность вычислений почти в два раза и позволяет заметно сократить объем используемой памяти (рисунок 3.1).
Рисунок 3.1
Схема шифрования
Так как в схему Эль-Гамаля вводится случайная величина k, то шифр Эль-Гамаля можно назвать шифром многозначной замены. Из-за случайности выбора числа k такую схему еще называют схемой вероятностного шифрования. Вероятностный характер шифрования является преимуществом для схемы Эль-Гамаля, так как у схем вероятностного шифрования наблюдается большая стойкость по сравнению со схемами с определенным процессом шифрования. Недостатком схемы шифрования Эль-Гамаля является удвоение длины зашифрованного текста по сравнению с начальным текстом. Для схемы вероятностного шифрования само сообщение M и ключ не определяют шифротекст однозначно. В схеме Эль-Гамаля необходимо использовать различные значения случайной величины k для шифровки различных сообщений M и M'. Если использовать одинаковые k, то для соответствующих шифротекстов (a,b) и (a',b') выполняется соотношение b(b')-1=M(M')-1 b(b')-1=M(M')-1. Из этого выражения можно легко вычислить M', если известно M.
Цифровая подпись служит для того чтобы можно было установить изменения данных и чтобы установить подлинность подписавшейся стороны. Получатель подписанного сообщения может использовать цифровую подпись для доказательства третьей стороне того, что подпись действительно сделана отправляющей стороной. При работе в режиме подписи предполагается наличие фиксированной хеш-функции h(.), значения которой лежат в интервале (1, p-1) (рисунок 3.1).
Рисунок 3.2
Для подписи сообщения M выполняются следующие операции:
Вычисляется дайджест сообщения M:m=h(M).(Хеш функция может быть любая).
Выбирается случайное число 1k mod p.
Вычисляется число s=(m-xr)k-1, где k в степени минус 1 это мультипликативное обратное.
Подписью сообщения M является пара (r,s).
Таблица 3.1
Сравнение некоторых алгоритмов:
Алгоритм
|
Ключ
|
Назначение
|
Криптостойкость, MIPS
|
Примечания
|
RSA
|
До 4096 бит
|
Шифрование и подпись
|
2,7•1028 для ключа 1300 бит
|
Основан на трудности задачи факторизации больших чисел; один из первых асимметричных алгоритмов. Включен во многие стандарты
|
ElGamal
|
До 4096 бит
|
Шифрование и подпись
|
При одинаковой длине ключа криптостойкость равная RSA, т.е. 2,7•1028 для ключа 1300 бит
|
Основан на трудной задаче вычисления дискретных логарифмов в конечном поле; позволяет быстро генерировать ключи без снижения стойкости. Используется в алгоритме цифровой подписи DSA-стандарта DSS
|
DSA
|
До 1024 бит
|
Только подпись
|
|
Основан на трудности задачи дискретного логарифмирования в конечном поле; принят в качестве гос. стандарта США; применяется для секретных и несекретных коммуникаций; разработчиком является АНБ.
|
ECDSA
|
До 4096 бит
|
Шифрование и подпись
|
Криптостойкость и скорость работы выше, чем у RSA
|
Современное направление. Разрабатывается многими ведущими математиками
|
Криптостойкость определяется сложностью нахождения индекса, свя- зывающего два элемента группы точек на кривой. При этом алгоритм явля- ется стойким, если в разложении порядка группы на простые множители встречается большой простой делитель. Поэтому при оценивании сложно- сти анализа криптоалгоритмов важным является вычисление порядка груп- пы с последующим разложением его на простые множители.
Если сравнить сложность факторизации целых чисел в задаче дискретного логарифмирования и в системах, основанных на ЭК, то последние выглядят предпочтительнее. Например, сложность задачи на ЭК при разрядности p в 128 бит соответствует задаче разложения чисел и дискретного логарифмирования с разрядностью 512 бит. Выигрыш в стойкости особенно заметен при больших размерах ключа. Данное обстоятельство позволяет использовать криптографические конструкции подобного типа для построения криптографических протоколов различного назначения.
Сложность нахождения индекса в зависимости от исходного поля и степени расширения поля, куда отображается группа кривых, представлена в табл. 2.
Таблица 3.2
Трудоемкость дискретного логарифма на ЭК по времени
Исходное
поле p=2n
|
Сложность нахождения индекса
|
Поле
p = 22n
|
Сложность нахождения индекса
|
Поле
p = 24 n
|
Сложность нахождения индекса
|
2100
|
1015
|
22 100
|
1017
|
24 100
|
1025
|
2200
|
1030
|
22 200
|
1025
|
24 200
|
1038
|
2300
|
1045
|
22 300
|
1032
|
24 300
|
1045
|
Из табл. 2 видно, что степень расширения l = 2 обеспечивает сравни- мую сложность при малых размерах ключа.
Do'stlaringiz bilan baham: |
