Криптосистемы на эллиптических кривых, шифрование информации

Введение

Проблема защиты информационных ресурсов в последнее время приобретает более актуальное значение, хоть и является одной из самых сложных задач. В первую очередь, это объясняется ускорением развития научно-технического прогресса, результатом которого являются новые технические или электронные средства, которые в свою очередь содержат в себе опасность возникновения каналов распространения информации.
Также одним из факторов, определяющим трудоемкость решения задач защиты информации, является расширение круга пользователей, которые имеют непосредственный доступ к ресурсам компьютерной системы и массивам данных, которые находятся в ней.
Для решения этой проблемы необходима система мер, главной целью которой является предупреждение от несанкционированного доступа, вследствие которого может быть потеря, модификация или отток информации.
Проведенный анализ литературы [1-4] показал, что на сегодня среди многих организационных, программных и системных мер самым популярным методом защиты информации от подобного рода проблем являются криптографические системы или криптосистемы, которые обеспечивают целостность и секретность информации, авторизацию, электронные платежи и т.д.
Отметим, что криптография – это область прикладной математики, основной задачей которой является защита цифровой информации от несанкционированного доступа. Защита достигается путем преобразования исходного набора данных в вид, из которого получение исходной информации невозможно или труднодостижимо.


1. Принципы эллиптической криптографии

Эллиптическая криптография - это раздел криптографии, использующий эллиптические кривые с параметрами, определенными над конечными полями для реализации схем шифрования. Главным направлением применения эллиптических кривых в криптографических схемах являются системы с открытым ключом. Ключевым математическим объектом эллиптической криптографии является эллиптическая кривая.
Эллиптической кривой E [5], определенной над конечным полем K, называется кривая, описана уравнением Вейерштрасса:

где {a1 , a2 , a3 , a4 , a5 , a6 }K, Δ 0.
Δ называется дискриминантом Е и определяется как:

Если конечное поле K является простым - GF (p), E трансформируется в кривую, описывается следующим уравнением:

где a, bK.
Рассмотрим арифметику над точками эллиптической кривой. Пусть E - эллиптическая кривая, определенная над полем K и P, Q ∈ E - точки эллиптической кривой. Сумма точек P и Q графически определяется следующим способом [6].
1. Провести прямую через точки P и Q.
2. Отразить сечение данной прямой с эллиптической кривой относительно оси OY. Удвоение точки P графически определяется следующим образом.
1. Провести касательную к эллиптической кривой в точке P.
2. Пересечение данной касательной, запечатленной симметрично оси OY, называется удвоенной точкой P.
Для того, чтобы избежать известные атаки, основанные на проблеме дискретного логарифма в группе точек ЭК, необходимо, чтобы количество точек ЭК делилось на достаточно большое простое число n. Стандарт ANSI X9.62 требует n>2160

. Уравнение ЭК строится специфическим способом, используя случайные / псевдослучайные коэффициенты.
Основными параметрами при построении ЭК над полем GF (p) являются:
1. Размерность поля p, где p является простым числом.
2. Два элемента конечного поля a и b, определенные уравнением эллиптической кривой E, которая имеет следующий вид:

где
3. Два элемента поля GF (p) - xG и yG, которые определяют конечную точку G=(xG,yG) - генератор группы.
4. Порядок q точки G, где q>2160 и q>4p.
5. сомножитель h=#Eq, где #E означает порядок группы точек эллиптической кривой.

2. Методы шифрования в эллиптической криптографии

Наиболее популярными направлениями эллиптической криптографии, то есть сферами, в которых криптостойкость базируется на задаче дискретного логарифмирования для эллиптических кривых или ECDLP, является шифрование с открытым ключом и алгоритм электронно-цифровой подписи.
В данном разделе будут рассмотрены различные схемы обмена ключами. На сегодняшний день, существуют два вида использования шифрования с ключами - симметричный (существует единственный секретный ключ, должен быть передан между отправителем и получателем защищенным каналом) и асимметричный (есть пара ключей - частный и публичный, который может быть передан незащищенным каналом).
2.1 Шифрование с открытым ключом. Эллиптический вариант схемы обмена ключами Дэффи-Хэлмана

Протокол Диффи-Хеллмана - это метод обмена криптографическими ключами. Данный метод позволяет двум участникам, которые не имеют никаких предварительных данных друг о друге, получить общий секретный ключ, который будет использоваться для шифрования данных, которыми обмениваются стороны, с помощью незащищенного канала связи. Этот ключ можно использовать для шифрования следующих сеансов связи, использующих шифр с симметричным ключом.
Пусть существует эллиптическая кривая, обеспечивает достаточную криптостойкость (Не суперсингулярную, в которой генерирующая точка G = (x;y) имеет большой порядок, то есть число n, при котором nG= 0 является очень большим простым числом), определена параметрами a и b:

Обозначим сторону отправителя как A , Сторону получателя как B, тогда обмен ключами между сторонами A и B производится следующим образом:
1. Сторона А выбирает целое число PrivA<n. Данное число называется частным ключом участника, а точка эллиптической кривой PubA=PrivA×G называется публичным ключом.
2. Сторона В выбирает аналогично секретный ключ PrivB и вычисляет открытый ключ PubB=PrivB×G
3. Участник А генерирует секретный ключ K=kA×Pb, а участник В генерирует секретный ключ K=kB×PA.
Две формулы, полученные в п.3 дают один и тот же результат, поскольку:

Проблема, которая стоит перед сторонними наблюдателями, которые имеют намерение узнать секретный ключ, состоит в вычислении kA×kB×G по известным G, kA×G, kB×G, но не зная при этом kA и kB. Это и является проблемой Дэффи-Хэлмана на эллиптических кривых.
2.2 Протокол Месси-Омура (Massey-Omura)

Криптосистема Месси-Омура [7] была предложена в 1978 году Джеймсом Месси и Джимом К