ЭЦП Эль-Гамаля

Posted by key under c/c++, Безопасность

Boltina

Доброго времени суток, возникла проблема в реализации эцп на с++, подключил большие числа и тд и тп, тестируя заметил что иногда программа выдаёт результат как будто подпись не изменена, хотя на самом деле я её изменил.

Посчитав на калькуляторе понял что вроде программа то работает верно, что тогда не так… не понимаю.

Отправитель работает с числами: P-простое, G-целое, X — секретный ключ, Y — открытый ключ, m — результат хеширования, K-целое(k и p-1 взаимно простые) и тд… в результате отправляется <сообщение, r,s> (r и s ключи полученные по формулам)

Получатель: хеширует сообщение по тем же правилам, получая такое же m (если не было изменений) проверяет следующее равенство: Y^r * r^s (mod P) = G^m (mod P). Если данное равенство верно, то подпись не была изменена.

Собственно проблема: начальные r = 11, s = 11; меняем и даём получателю r= 114 s = 11;
Также m = 4, G = 7, P=13, Y = 5;

Проверка при обычном ключе: a = 5^11 * 11^11 (mod 13) = ( 5^11(mod 13) * 11^11 (mod 13))(mod 13) =8*6(mod 13)
a = 48(mod 13) = 9
b = 7^4(mod 13)=9
Проверка при измененном ключе:
a = 5^114 * 114^11 (mod 13) = (5^114(mod 13)*114^11 (mod 13))(mod 13) =12*4(mod 13)=48(mod 13)
b — остался таким же.

Помогите мне разобраться, почему при r = 11, s = 11: a = 9. И при неправильном ключе r= 114 s = 11: a = 9;
Получается ключ не был изменён, а это не так. Где я ошибаюсь?

Streletz

Смотрите описания алгоритма и сверяйте с ним свою реализацию. Возможно, где-то ошиблись.
В помощь:
Схема Эль-Гамаля

Здесь уже нужно смотреть исходный код. В том числе, в режиме отладки.

Вообще у Вас в качестве исходных данных используются очень маленькие числа. Более того r и s при этом одинаковые.
В своё время коллега по форуму уже делал реализацию алгоритма Эль-Гамаля на C++ (правда, в режиме шифрования). Возможно, это как-то поможет.

Boltina

О как, обратил внимание(благодаря Вам) на r s и их величину: чёт совсем не углядел
«Проверяется выполнимость условий: ~0<r<p и ~0<s<p-1. Если хотя бы одно из них не выполняется,то подпись считается неверной.» И только потом идёт проверка на равенство выражений…

А я исправляя r на 114 явно нарушал это условие, и не проверял его.
Видимо проблема в этом=) Спасибо)

тема на форуме

Случайные статьи

• Масштабирование графика (TChart)
• Рассылка. Выпуск 209
• Fortress 2. Конкурс. Создание лучшего бота
• Перебор и проверка значения компонентов
• Как найти все подпапки скрытой папки.
• Как создать vpn-подключение средствами ras?
• WMI. Получить DeviceID, PNPDeviceID по букве тома
• Отображать элемент поверх курсора
• Как удалить все тэги?
• Как наиболее быстро и грамотно сортировать массивы строк?