26. Криптография на эллиптических кривых. Основные принципы и свойства.

Представление блоков информации в криптографических алгоритмах не только в виде чисел (или элементов конечных полей), но и в виде иных алгебраических объектов большей сложности. Одним из весьма подходящих типов таких объектов являются точки эллиптических кривых. 

Эллиптические кривые - это кривые вида

y²=x³+ax+b

Суть применения эллиптических кривых в криптографии сводится к тому, что группа чисел по простому модулю (как было в криптосистеме Диффи-Хеллмана) заменяется группой решений уравнения y²=x³+ax+b. Осталось лишь указать, как складывать друг с другом решения такого уравнения.

На плоскости это делается так, как показано на рисунке выше. Чтобы сложить две точки на эллиптической кривой, нужно провести через них прямую. Она пересечет кривую в третьей точке. Эту третью точку мы будем считать суммой первых двух со знаком минус; чтобы получить собственно сумму, отразим полученную точку относительно оси X. Можно проверить, что такое сложение будет ассоциативным.

Преимущество шифров, основанных на эллиптических кривых в том, что в них можно использовать меньшие по величине простые числа, чем в классических системах с открытым ключом.

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