Шифрование-дешифрование (второй вариант)
Шифрование
•Пользователь В выполняет следующие шаги для шифрования сообщения М, предназначенного пользователю А:
•получает открытый ключ A;
•представляет сообщение М в виде цепочки чисел , каждое из
|
которых не превосходит p −1 ; |
|
|
|
• |
выбирает случайное число k такое, что 1≤ k ≤ p −2 |
|
; |
|
• |
вычисляет γ =αk mod p , |
δ = Mi (αa )−k mod p |
|
; |
• |
посылает криптограмму |
C =(γ, δ) пользователю А. |
||
Дешифрование |
|
|
|
|
• |
используя свой закрытый ключ, вычисляет γa modp |
; |
||
• |
восстанавливает сообщение Mi =γa δ modp . |
|
|
|
• |
Действительно, γa δ =αak Mi (αa )−k mod p = Mi |
. |
|
|
Первый вариант имеет меньшую сложность шифрования, второй – меньшую сложность дешифрования, из-за отсутствия операции обращения элемента по модулю
Преимущество КС Эль-Гамаля состоит также и в том, что тогда все пользователи в сети могут выбирать одинаковыеα и p, что невозможно для КС РША. Кроме того, как будет показано далее, эта схема может быть естественным образом распространена на случай эллиптическихкривых.
Существеннымнедостаткомсхемыявляетсято, чтодлина криптограммывнейв 2 разабольшедлинысообщения.
СтойкостьКСЭль-Гамаля
Проблемавосстановлениясообщения M позаданным p α ,αa, δ и γ принеизвестном a эквивалентнарешениюзадачи Диффи–Хеллмана.
Яснотакже, чтоеслибудетрешена проблеманахождения дискретного логарифма, то криптосистема Эль-Гамаля будет вскрыта. При выборе p с разрядностью 768 бит (для повышенной стойкости – до 1024 бит), стойкость КС Эль-Гамаля будет такой же, как и у КС РША при выборе в последнейтехжепараметровдлямодуля.
Важно отметить, |
что для |
шифрования различных |
сообщений |
|||||
Mi , M j необходимо |
использовать |
различные значения |
чисел k, |
|||||
поскольку в противном случае |
δ1 |
= |
Mi, |
и тогда сообщение |
M |
j |
может |
|
|
||||||||
|
|
δ2 |
M j |
|
|
|||
быть легко найдено, если известносообщение Mi . |
|
|
|
|||||
Распределение ключей с использованием
однонаправленных функций. Способ ДиффиХеллмана
|
|
|
|
|
|
В |
|
|
|
|
|
|
|
|
|
|
А |
|
yA |
|
|
|
|
|
|
|
yB |
|
|
|
|
|
|
|
xA , 1 ≤ xA ≤ p −1, p - |
||||
|
|
|
|||||
А генерирует большое случайное число |
|||||||
простое число. |
вычисляет уА =αx A (mod p) . |
||||||
xA сохраняется в секрете. |
|||||||
В: генерирует хB , вычисляет число yB .
А, приняв от В yB , вычисляет
KA = ( yB )x A mod p = (αxB )x A mod p =αxB x A mod p .
В, приняв от А yA , вычисляет
KB = ( yA )xB mod p = (αx A )x B mod p =αx A xB mod p .
Видим, что KA = KB = K .
Далее ключ K может быть использован в симметричной системе
шифрования.
СтойкостьКСДиффи–Хеллмана
Если злоумышленник умеет в обозримое время вычислять дискретный логарифм, то он может найти и секретный ключ A или B, поскольку x =logα CA mod p .
Однако поскольку задача дискретного логарифмирования является трудной, данныйспособприбольшихвеличинах p нереализуем. Вместе с тем стойкость КС Диффи–Хеллмана не эквивалентна задаче факторизации, а соответствует так называемой проблеме Диффи– Хеллмана, котораяформулируетсяследующимобразом: зная p, α, αx mod p ,αy mod p нужно найти αxy mod p . (Впрочем, последняя задача по сложности несущественно уступает задаче дискретного логарифмирования.)
Важно отметить, что метод распределения ключей Диффи– Хеллмана может быть полностью скомпрометирован активными злоумышленниками, выдающими себя за пользователей A или B. Если этот факт подмены (или имитации) величин CA, CB не будет обнаружен, то вырабатывается совместный ключ не между A и B, а междузлоумышленникомиоднимизпользователей.
Таким образом, для КС Диффи–Хеллмана, так же как и для всех КС ОК, необходимо обеспечивать подлинность открытых данных (т. е. обеспечить решение задач аутентификации).
КС Эль-Гамаля
Это некоторая модификация КС РША, стойкость которой не связана непосредственно с проблемой факторизации. Она широко используется в стандартах цифровой подписи и допускает естественное обобщение на случай КС, построенных на основе использования эллиптических кривых, что будет рассмотрено далее.