алгоритм ЭльГамаля
Криптографы постоянно вели поиски эффективных систем открытого шифрования, и ЭльГамаль предложил следующую схему на основе возведения в степень по модулю большого простого числа. Для этого задается большое простое число Р. Сообщения представляются целыми числами S из интервала (1, Р). Оригинальный протокол передачи сообщения S выглядит в варианте Шамира, одного из авторов RSA, так:
1. Отправитель А и получатель В знают лишь Р. А генерирует случайное число Х из интервала (1, Р) и В тоже генерирует случайное число Y из того же интервала.
2. А шифрует сообщение: S1 = SX (mod Р) и посылает В.
3. В шифрует его своим ключом: S2 = S1Y (mod Р) и посылает S2 к А.
4. А "снимает" свой ключ: S3 = S2 (1/X) (mod Р) и возвращает S3 к В.
5. Получатель В расшифровывает сообщение: S = S3 (1/Y) (mod Р).
В системе ЭльГамаля большая степень защиты, чем у алгоритма RSA достигается с тем же по размеру N, что позволяет почти на порядок увеличить скорость шифрования и расшифрования. Криптостойкость системы ЭльГамаля основана на том, что можно легко вычислить степень целого числа, то есть произвести умножение его самого на себя любое число раз так же, как и при операциях с обычными числами. Однако трудно найти показатель степени, в которую нужно возвести заданное число, чтобы получить другое, тоже заданное. В общем случае эта задача дискретного логарифмирования кажется более трудной, чем разложение больших чисел на простые сомножители, на основании чего можно предположить, что сложности вскрытия систем RSA и ЭльГамаля будут сходными.
предыдущая тема следующая