Читать онлайн «Применение эллиптических кривых в криптографии: Методические указания к выполнению лабораторных работ»

Федеральное агентство по образованию Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева ПРИМЕНЕНИЕ ЭЛЛИПТИЧЕСКИХ КРИВЫХ В КРИПТОГРАФИИ Жданов О. Н . Чалкин Т. А. Содержание 1. Основные факты 2. Криптосистемы на эллиптических кривых 3. Алгоритм цифровой подписи на эллиптических кривых 4. Варианты заданий лабораторной работы 5. Приложение 1. Стандарт электронной цифровой подписи Приложение2. Закон Российской Федерации о цифровой подписи  ЭЛЛИПТИЧЕСКИЕ КРИВЫЕ В последние два десятилетия все большее применение в криптографии находит од- на из областей теории чисел и алгебраической геометрии – теория эллиптических кривых над конечными полями. Основная причина этого состоит в том, что эллиптические кривые над конечными полями доставляют неисчерпаемый источник конечных абелевых групп, которые (даже если они велики) удобны для вычислений и обладают богатой структурой. Во многих отношениях эллиптические кривые – естественный аналог мультипликативных групп полей, но более удобный, так как существует бóльшая свобода в выборе эллиптиче- ской кривой, чем в выборе конечного поля. Начнем с изложения основных определений и свойств эллиптических кривых. Мы ограничимся минимальным числом основных фактов, необходимых для понимания при- ложений к криптографии, уделяя больше внимания примерам и конкретным описаниям и меньше заботясь о доказательствах и общности. Более систематическое изложение этих вопросов можно найти в литературе (см. список). § 1. Основные факты В этом параграфе мы предполагаем, что K – поле: либо поле R вещественных чи- сел, либо поле Q рациональных чисел, либо поле C комплексных чисел, либо поле E q из q = p r элементов. Напомним, что характеристикой поля K называется такое натуральное число p = char K , что p ⋅ 1 = 0 , где 1 и 0 – единичный и нулевой элементы K соответст- венно. Определение. Пусть K – поле характеристики, отличной от 2 и 3, и x 3 + ax + b (где a, b ∈ K ) – кубический многочлен без кратных корней. Эллиптическая кривая над K – это множество точек ( x, y ) (где x, y ∈ K ), удовлетворявших уравнению y 2 = x 3 + ax + b, (1) вместе с единственным элементом, обозначаемым O и называемым «точка в бесконечно- сти» (о ней подробнее будет сказано ниже). Если K – поле характеристики 2, то эллиптическая кривая над K – это множество точек, удовлетворяющих уравнению либо типа y 2 + cy = x 3 + ax + b , (2а) либо типа y 2 + xy = x 3 + ax 2 + b (2б) (здесь кубические многочлены в правых частях могут иметь кратные корни), вместе с «точкой в бесконечности» О. Если К – поле характеристики 3, то эллиптическая кривая над К – это множество точек, удовлетворяющих уравнению y 2 = x 3 + ax 2 + bx + c (3) (где кубический многочлен справа не имеет кратных корней), вместе с «точкой в беско- нечности» О.