Анализ реализации алгоритма Эль-Гамаля

Проблема дискретного логарифма состоит в том, что, зная основание степени и получившийся после возведения результат по модулю простого чис­ла, невозможно за полиномиальное время определить, в какую именно степень было возведено основание. Однако из-за сложности определения чисел х и у "в чистом виде" у него не оказывается возможности вычислить значение k, которое ему так необходимо для прочтения шифровки. Относительно числа р криптоанализ выдвигает следующее требование. Число (р-1) должно содержать в разложении на множители большой простой делитель.При выборе х и у получателем и отправителем соответственно, естественно, должно выполняться требование к их информационной емкости. Для генерации этих чисел должен использоваться криптостойкий генератор псевдослучайных чисел (КГПСЧ). В противном случае злоумышленник просто определит х или у полным перебором.

35.На чем основана криптостойкость алгоритма Эль-Гамаля?

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

36. Математические понятия эллиптической криптографии.

Эллиптическая криптография — раздел криптографии, который изучает асимметричные криптосистемы, основанные на эллиптических кривых над конечными полями. Основное преимущество эллиптической криптографии заключается в том, что на сегодняшний день неизвестно субэкспоненциальных алгоритмов для решения задачи дискретного логарифмирования в группах точек эллиптических кривых.Преимущество подхода на основе эллиптических кривых в сравнении с задачей факторизации числа, используемой в RSA, или задачей целочисленного логарифмирования, применяемой в алгоритме Диффи-Хеллмана и в DSS, заключается в том, что в данном случае обеспечивается эквивалентная защита при меньшей длине ключа. В общем случае уравнение эллиптической кривой Е имеет вид: y² + axy + by = x³ + cx² + dx + e В качестве примера рассмотрим эллиптическую кривую Е, уравнение которой имеет вид: y² + y = x³ - x².На этой кривой лежат только четыре точки, координаты которых являются целыми числами. Это точки: А (0, 0); В (1, -1); С (1, 0);D (0, -1). В криптографии с использованием эллиптических кривых все значения вычисляются по модулю р, где р является простым числом. Элементами данной эллиптической кривой являются пары неотрицательных целых чисел a, b которые меньше р и удовлетворяют частному виду эллиптической кривой: y² ≡ x³ + ax + b (mod p) Общее параметры эллиптической кривой: 1 Размер поля р, которое обозначает базовое конечное поле F(p), где р>3 должно быть простым числом. 2 Параметры a, b эллиптической кривой, которые определяют уравнение кривой E_p(a,b), что определяются y² = x³ + ax + b. 3. Б азовая точка G=(x_G,y_G) порядка n с координатами x_G,y_G. Порядок n базовой точки G 4. Число точек эллиптичсекой кривой E_p называют порядком E_p и обозначают как #E_p. 5. Порядок кривой определяется согласно теоремы Хасе. Кофактор h взаимосвязи порядка кривой #E_p и порядка базовой точки n, при этом h= #E_p /n.

Дата добавления: 2015-12-01