Шифр ЭльГамаля

Шифр ЭльГамаля

Шифр ЭльГамаля. Он использует схему на основе возведения в степень по модулю большого простого числа. Для этого задается большое простое число р. Сообщения представляются целыми числами С из интервала (1, р). Оригинальный протокол передачи сообщения С выглядит следующим образом.

Отправитель сообщения А и получатель В знают лишь р. А генерирует случайное число X из интервала (1,р). В генерирует случайное число Y из того же интервала.

Криптосистема ЭльГамаля обеспечивает большую степень за щиты, чем алгоритм RSA. Этот эффект достигается при том же N, что позволяет почти на порядок увеличить скорость шифрования и расшифровывания. Криптостойкость системы ЭльГамаля основана на том, что можно легко вычислить степень целого числа, т. е. произвести умножение его самого на себя любое число раз так же, как и при операциях с обычными числами. Однако трудно найти показатель степени, в которую нужно возвести заданное число, чтобы получить другое, тоже заданное. В общем случае эта задача дискретного логарифмирования кажется более трудной, чем разложение больших чисел на простые сомножители, на основании чего можно предположить, что сложности вскрытия систем RSA и ЭльГамаля будут сходными.

С точки зрения практической реализации, как программным, так и аппаратным способом ощутимой разницы между этими двумя стандартами нет. Однако в криптостойкости они заметно различаются. Если рассматривать задачу разложения произвольного целого числа длиной в 512 бит на простые множители и задачу логарифмирования целых чисел по 512 бит, вторая задача, по оценкам математиков, несравненно сложнее первой. Однако есть одна особенность. Если в системе, построенной с помощью алгоритма RSA, криптоаналитику удалось разложить открытый ключ п одного из абонентов на два простых числа, то возможность злоупотреблений ограничивается только этим конкретным пользователем. В системе, построенной с помощью алгоритма ЭльГаматя, угрозе раскрытия подвергнутся все абоненты криптографической сети. Кроме того, появились возможности существенно усовершенствовать методы дискретного логарифмирования для отдельных специальных простых чисел.

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

Шифр ЭльГамаля

Яндекс.Метрика