Применение эллиптических кривых в криптографии кратко

Обновлено: 06.07.2024

Недавно произошло два знаменательных для отечественного компьютерного сообщества события: принятие нового российского стандарта на электронную подпись и Закона об электронной подписи. Теоретически, новый закон призван уравнять в правах электронную подпись под электронным документом и собственноручную подпись под документом бумажным. Вот только осталось принять Закон об электронном документе.

Немного математики

Алгоритмы цифровой подписи.

На сегодняшний день придумано и реализовано не так много алгоритмов цифровой подписи:

алгоритм подписи Ривеста-Шамира-Адельмана (RSA);
алгоритм Шнорра;
алгоритм DSA, являющийся федеральным стандартом на цифровую подпись в США;
алгоритм Эль-Гамаля, на котором построен "старый" российский стандарт на цифровую подпись ГОСТ Р 34.10-94.

Выбираем рабочее поле; рекомендуется выбрать поле порядка p = 2 512 . Выбираем секретный ключ x длиной 256 бит. Открытым ключом подписи будем считать пару чисел a и Y, где

Y = a x (mod p),1 h = Y r r s (mod p)

Числа a и p не являются параметрами алгоритма и должны быть известны всем участникам обмена. Они не секретны; обычно криптографические программы содержат эти числа внутри себя. При организации центров сертификации, параметры генерации открытого ключа могут выдаваться в центре вместе с рекомендованным программным обеспечением или быть частью открытого ключа центра сертификации.

Y = g x (mod p)

Оригинальный метод отображений применим для любого числового поля GF(p n ). ГОСТ 34.11-94 предполагает использование p порядка 2 512 , тогда сложность задачи дискретного логарифмирования имеет порядок 2 180 .

Утверждается, что алгоритм Копперсмита эффективен в полях GF(2 k ), где k 2 = ax 3 + bx + c

Можно наложить ограничения на множество значений переменных х, y, и коэффициентов a, b, c. Ограничивая область определения уравнения значимым для приложений числовым множеством (полем) мы получим эллиптическую кривую, заданную над рассматриваемым полем. На рис. 2 изображен общий вид эллиптической кривой, определенной на множестве действительных чисел.

В приложении к криптографии (и в новом стандарте на цифровую подпись) эллиптическая кривая над конечным простым полем GF(p) определяется как множество пар (x,y), таких что x,y Б?? GF(p), удовлетворяющих уравнению:

y 2 = x 3 +ax +b (mod p), a, b Б?? GF(p)

где р – порядок поля, над которым определена кривая. Если в схеме Эль-Гамаля рекомендуется использовать число р порядка 2 512 , то в случае эллиптической кривой достаточно взять p > 2 255 .

P = Q + Q + Q + . + Q = kQ

Если для некоторой точки P существует такое число k, что kP = 0, это число называют порядком точки P.

Заключение

Остается ответить на вопрос: зачем нужны эллиптические кривые? Помимо нетехнических причин, для принятия стандарта 34.10-2001 есть и причины, связанные с развитием вычислительной техники и криптоанализа.

Казалось бы, при резком падении стоимости оперативной памяти и удешевлении и увеличении пропускной способности каналов связи, зачем стараться сохранить короткие ключи? Это связано, в первую очередь, с массовым распространением мобильных устройств и Internet-технологий, с использованием смарт-карт и аутентификационных токенов. Память смарт-карты или SIM-карты является ресурсом дефицитным, к тому же, переход на выпуск смарт-карт с увеличенной памятью, приведет к потере совместимости с ранее выпущенными устройствами. Видимо, подобными технологическими соображениями и руководствовались американские специалисты, когда в 1999 году принимали вариант алгоритма DSA с использованием эллиптических кривых в качестве стандарта ANSI X9.62 ECDSA. В 2000 году алгоритм ECDSA был принят в качестве федерального стандарта и стандарта IEEE. А началось все годом ранее, в 1998 году, когда алгоритм ECDSA был принят в качестве стандарта ISO. России тоже пришлось спешить вслед за модой. Для детального знакомства с ECDSA и ГОСТ 34.10-2001 можно рекомендовать работы 5.

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

За последние десятилетия достигнуты существенные успехи в исследовании алгоритмов дискретного логарифмирования в простых полях и в полях многочленов. Метод дискретного логарифмирования Копперсмита сегодня является лучшим по скорости, но для группы точек эллиптической кривой он не применим. На сегодняшний день не построено методов вычисления кратности точки эллиптической кривой, имеющих, хотя бы, субюэкпоненциальную оценку сложности. n

Литература

Глеб Семенов (semenov@jet.msk.su) – специалист по безопасности компании Jet Infosystems.

Алгоритмы шифрования

Симметричные алгоритмы

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

Криптоанализ

Универсальный метод вскрытия любого шифра – прямой перебор множества всех возможных ключей, позволяющий получить оценку сверху для стойкости алгоритма шифрования. Вероятность подбора ключа при таком подходе – величина, прямо пропорциональная количеству всех ключей алгоритма. Криптоанализ ставит своей задачей в разных условиях (только по шифротексту или по известному открытому тексту) получить дополнительные сведения о ключе шифрования, чтобы значительно уменьшить диапазон вероятных ключей. В некоторых случаях существуют алгоритмы, которые позволяют настолько сузить множество возможных ключей, что перебор их почти не потребует времени.

Высокая стойкость криптоалгоритма, однако не гарантирует, что спустя некоторое время не будет найден новый метод криптоанализа, который понизит первоначальную оценку стойкости алгоритма. Так, для DES первоначальная оценка стойкости равнялась числу возможных вариантов ключей и была равна 2 55 операций шифрования, а через полтора десятилетия был найден алгоритм, снизивший эту оценку до 2 47 операций.

Криптоанализу, как и криптографии, уже несколько столетий. Наиболее простые алгоритмы – статистический и аналитический – давно известны. Статистический криптоанализ использует статистические методы для получения дополнительной информации о ключе, а аналитический – занимается математическим изучением алгоритма шифрования. Каждый новый метод криптоанализа добавляет новые требования к алгоритмам шифрования. Так, статистический метод, в котором по распределению символов в шифротексте выдвигаются гипотезы о ключе шифрования, породил требование равномерного распределения символов в шифротексте.

В число современных методов криптоанализа блочных шифров входят разностные (дифференциальные) алгоритмы. Первоначально они применялись для DES, но в силу своей универсальности стали использоваться и для других блочных шифров. Суть разностного анализа в следующем. Берутся два варианта открытого текста, отличающиеся, скажем, только в одном разряде, и анализируется разность зашифрованных текстов. Оказалось, что в DES и некоторых других алгоритмах распределение разностей соответствующих шифротекстов было не равномерным: определенные разности встречались чаще других. Если этот прием использовать для алгоритма DES с 15 циклами шифрования (для DES полное шифрование предусматривает 16 циклов), то, считая известными разности шифротекстов по 15 циклам, по известным шифротекстам после 16 циклов можно сделать определенные предположения о ключе, который использовался на последней, шестнадцатой итерации. Чаще всего выводы о ключе последней итерации будут неверными, но в большом массиве вариантов истинный цикловой ключ встречается чуть чаще, чем все остальные, что позволяет его выделить. Таким способом удается установить 48 разрядов из 56 разрядов ключа, используемого на последнем цикле, после чего определение остальных 8 разрядов не составит проблемы.

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

Шифрование

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

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

Асимметричные криптоалгоритмы

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

Криптоанализ

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

Суть технологии асимметричного шифрования заключается в том, чтобы построить такой алгоритм, вычисление которого со знанием некоторого секрета имело бы полиномиальную сложность, а без этого знания – экспоненциальную. Увеличивая число разрядов, можно добиться того, что решение задачи на современных вычислительных устройствах без знания секрета потребует несколько сотен или даже тысяч лет, а знание секрета позволяет решить эту же задачу достаточно быстро.

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

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

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

Шифрование

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

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

Еще одно перспективное направление – использование сложных алгоритмических теоретико-групповых задач для групп различной природы, например, для группы кодовых слов. В этой группе задача проверки эквивалентности слов становится труднорешаемой. При добавлении новых соотношений (и уменьшении тем самым мощности группы) задача эквивалентности значительно упрощается.

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

Тенденции развития асимметричного шифрования значительно отличаются от направлений совершенствования симметричной криптографии. Если в совершенствовании симметричных шифров преобладает тенденция составления алгоритма из набора примитивных операций, то асимметричное шифрование требует значительных доказательных и вычислительных затрат как при составлении алгоритма, так и при его анализе и вскрытии. Если симметричное шифрование является соревнованием технических средств, то асимметричное – математических аппаратов.

Аннотация: Рассматривается криптография с использованием эллиптических кривых. Описаны математические понятия, связанные с эллиптическими кривыми, в частности задача дискретного логарифмирования на эллиптической кривой. Дано описание аналога алгоритма Диффи-Хеллмана на эллиптических кривых, алгоритма цифровой подписи на эллиптических кривых и алгоритма шифрования с открытым ключом получателя на эллиптических кривых.

Математические понятия

Преимущество подхода на основе эллиптических кривых в сравнении с задачей факторизации числа , используемой в RSA , или задачей целочисленного логарифмирования, применяемой в алгоритме Диффи-Хеллмана и в DSS , заключается в том, что в данном случае обеспечивается эквивалентная защита при меньшей длине ключа .

В общем случае уравнение эллиптической кривой Е имеет вид:

y 2 + axy + by = x 3 + cx 2 + dx + e

В качестве примера рассмотрим эллиптическую кривую Е , уравнение которой имеет вид:

На этой кривой лежат только четыре точки, координаты которых являются целыми числами. Это точки

А (0, 0), В (1, -1), С (1, 0) и D (0, -1)

Для определения операции сложения для точек на эллиптической кривой сделаем следующие предположения:

$0 \in Е$

На плоскости существует бесконечно удаленная точка , в которой сходятся все вертикальные прямые.
Будем считать, что касательная к кривой пересекает точку касания два раза.
Если три точки эллиптической кривой лежат на прямой линии, то их сумма есть 0 .

Введем следующие правила сложения точек на эллиптической кривой :

Точка 0 выступает в роли нулевого элемента . Так, 0 = -0 и для любой точки Р на эллиптической кривой Р + 0 = Р .
Вертикальная линия пересекает кривую в двух точках с одной и той же координатой х - скажем, S = (x, y) и T = (x, -y) . Эта прямая пересекает кривую и в бесконечно удаленной точке. Поэтому Р₁ + Р₂ + 0 = 0 и Р₁ = -Р₂ .
Чтобы сложить две точки P и Q (см. рисунок 11.2) с разными координатами х , следует провести через эти точки прямую и найти точку пересечения ее с эллиптической кривой . Если прямая не является касательной к кривой в точках P или Q , то существует только одна такая точка, обозначим ее S . Согласно нашему предположению

Если прямая является касательной к кривой в какой-либо из точек P или Q , то в этом случае следует положить S = P или S = Q соответственно.

Чтобы удвоить точку Q , следует провести касательную в точке Q и найти другую точку пересечения S с эллиптической кривой . Тогда Q + Q = 2 x Q = -S .

Введенная таким образом операция сложения подчиняется всем обычным правилам сложения, в частности коммутативному и ассоциативному законам. Умножение точки Р эллиптической кривой на положительное число k определяется как сумма k точек Р .

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

$y^<2> \equiv x^ + ax + b (mod\ p)$

$4a^<3> Такую кривую будем обозначать Ep (a,b) . При этом числа а и b должны быть меньше р и должны удовлетворять условию + 27b^ (mod\ p) \ne 0$
. Множество точек на эллиптической кривой вычисляется следующим образом.

Для каждого такого значения х , что 0 , вычисляется x 3 + ax + b (mod p) .
Для каждого из полученных на предыдущем шаге значений выясняется, имеет ли это значение квадратный корень по модулю р . Если нет, то в E_p (a,b) нет точек с этим значением х . Если корень существует, имеется два значения y , соответствующих операции извлечения квадратного корня (исключением является случай, когда единственным значением оказывается y = 0 ). Эти значения (x,y) и будут точками E_p (a,b) .

Множество точек E_p (a,b) обладает следующими свойствами:

$P \ne Q$

Р + 0 = Р
Если Р = (x,y) , то Р + (x,-y) = 0 . Точка (x,-y) является отрицательным значением точки Р и обозначается -Р . Заметим, что (x,-y) лежит на эллиптической кривой и принадлежит E_p (a,b) .
Если Р = (x₁,y₁) и Q = (x₂,y₂) , где , то P + Q = (x₃,y₃) определяется по следующим формулам:

$x_ \equiv \lambda^ - x_ - x_ (mod\ p)\\ y_ \equiv\lambda(x_ - x_) - y_ (mod\ p)$

$\lambda = \left\< \begin &(y_ - y_)/(x_ - x_), &если\ P \ne Q \\ &(3x_^ + a)/2y_, &если\ P = Q \end \right.$

Число есть угловой коэффициент секущей, проведенной через точки P = (x₁, y₁) и Q = (x₂, y₂) . При P = Q секущая превращается в касательную, чем и объясняется наличие двух формул для вычисления

Задача, которую должен решить в этом случае атакующий, есть своего рода задача "дискретного логарифмирования на эллиптической кривой" , и формулируется она следующим образом. Даны точки P и Q на эллиптической кривой E_p (a,b) . Необходимо найти коэффициент k такой, что

Относительно легко вычислить P по данным k и Q , но довольно трудно вычислить k , зная P и Q .

Рассмотрим три способа использования эллиптических кривых в криптографии.

Эллиптические шифровании кривых и алгоритмы подписи

Криптография на эллиптических кривых, называемых ECC. Создание алгоритма публичного шифрования, также асимметричное шифрование. RSA и аналогичные. Признано при заданных ключевых длины наиболее безопасных алгоритмов шифрования. Широкий диапазон применения, три основные технические TLS, PGP, SSH использует его, особенно в BTC в валюту представляет.

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

Временно эллиптическая кривая может быть просто понимать как:

а и б определяют различную форму кривой в системе координат. Например:

При Ь = 1, значение от -3 до 2, форма кривой выглядит следующим образом:

Специальная кривая: при а = Ь = 0, когда (слева), или = -3, Ь = 2, когда (справа), два не стандартной кривой.

Закрыто:Если а и Ь являются членами группы, то а + Ь является также членом группы.
Сочетание:(a+b)+c=a+(b+c)
единица: юань:Существует ровно одно значение может гарантировать + 0 = 0 + а = набор вверх, который мы называем единичный элемент
Inverse:Каждый член имеет ряд противоположное: при любом значении а, что должно быть Ь а + Ь = 0

Такая группа, которую мы называем абелева группа. Далее следует также абелева коммутативной A + B = B + A

Мы знаем, в добавлении целого числа в диапазоне от (Z +) является абелевой группой

Закрыто: а, б принадлежат целые числа, а + Ь также является целым числом, принадлежащих к
Сочетание: (а + б) + с = а + (Ь + с)
Единица Юань: 0 значение является единичным элементом
Обратное: а обратный элемент -a

Поэтому (Z +) является абелевой группой.

При одинаковой точке Р к добавляются, обозначается К.П., такие как: Р + Р + Р = 2P + P = 3P, как показано ниже:

Эллиптической кривой Е
Точка G (точка) на эллиптической кривой Е
Точка XG (х раз G) на эллиптической кривой Е

Она должна объяснить, Ruoguo точку Р на эллиптической кривой, существует минимальное положительное целое число п такое, что умножение пР = 0 (Бесконечный происхождения), то п есть порядок Р, когда п отсутствует, то Р представляет собой бесконечный порядок ,

То есть, когда заданная точка P, мы ищем известное число х XG очень просто, но обратный известен XG очень трудно найти х, дискретные степени может гарантировать безопасность криптографии на эллиптических кривых.

Мы знаем, что эллиптическая кривая непрерывна, она не подходит для шифрования, мы должны эллиптических кривых, определенных над конечным полем, и поместить его в дискретных точках.

Конечные поля Рр относится к арифметической операции для заданного набора целых чисел простого числа P, P элементы 0,1,2,3 . Р-1, состоящий из композиции, определенная.

Например, когда эллиптическая кривая находится конечное поле Р 23 Когда на, не забудьте сделать следующее:

Является ли будет иметь в виду, равной 23, разделенной на оставшейся, что для значений слева и справа, когда изображение, показанное на фиг функции:

Если точка P (3,10) мы знаем, что кривая, 2P, 3P . результат суммирования по правилам, как показано ниже:

Когда мы знаем, Р (3,10), Q (9,7), ищет -P, P + Q, когда 2P, процесс расчета выглядит следующим образом:

Рассмотрим K = Kg, в котором K, G представляет собой точку на эллиптической кривой Ep (а, б), п является порядок G (NG = O∞), к меньше целого числа п. Данные к и G, в соответствии с правилом сложения, но, в свою очередь, легко вычислить K для заданного K и G, очень трудно найти к. Поскольку ECC в принципе практического использования сделал значительный р, п достаточно велико, то необходимо индивидуально рассчитывается решение п точек приведены в таблице не представляется возможным. В котором G является базовой точкой, к является секретным ключом, K является открытым ключом.

Процесс шифрования выглядит следующим образом:

Алиса выбрал эллиптические кривые Е, эллиптические кривой и принимать выбранную точку Е29 (4,20) предполагаются в качестве базовой точки G, точка О (13,23), порядок базовой точки G н = 37
Алиса выбирает секретный ключ к (к hG/s + xK/s = hG/s + x(kG)/s = (h+xk)G/s = r(h+xk)G / (h+kx) = rG

Эллиптическая криптография — раздел криптографии, который изучает асимметричные криптосистемы, основанные на эллиптических кривых над конечными полями. Основное преимущество эллиптической криптографии заключается в том, что на сегодняшний день не существует субэкспоненциальных алгоритмов решения задачи дискретного логарифмирования. Использование эллиптических кривых для создания криптосистем было независимо предложено Нилом Коблицем (англ.) и Виктором Миллером (англ.) в 1985 году. [1]

Содержание

Введение

Асимметричная криптография основана на сложности решения некоторых математических задач. Ранние криптосистемы с открытым ключом, такие как алгоритм RSA, безопасны благодаря тому, что сложно разложить составное число на простые множители. При использовании алгоритмов на эллиптических кривых полагается, что не существует субэкспоненциальных алгоритмов для решения задачи дискретного логарифмирования в группах их точек. При этом порядок группы точек эллиптической кривой определяет сложность задачи. Считается, что для достижения такого же уровня безопасности как и в RSA требуются группы меньших порядков, что уменьшает затраты на хранение и передачу информации. Например, на конференции RSA 2005 Агентство национальной безопасности объявила о создании “Suite B”, в котором используются исключительно алгоритмы эллиптической криптографии, причём для защиты информации классифицируемой до “Top Secret” используются всего лишь 384-битные ключи.

Эллиптические кривые над конечными полями

Эллиптической кривой называется множество точек , удовлетворяющих уравнению:

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

В криптографии эллиптические кривые рассматриваются над двумя типами конечных полей: простыми полями нечётной характеристики (_p" width="" height="" />
, где — простое число) и полями характеристики 2 ().

Эллиптические кривые над полями нечётной характеристики

Над полем _p" width="" height="" />
характеристики уравнение эллиптической кривой E можно привести к виду:

$E:\quad y^2 = x^3 + Ax + B \pmod p,$

где _p" width="" height="" />
— константы, удовлетворяющие .

Группой точек эллиптической кривой E над полем _p" width="" height="" />
называется множество пар , лежащих на E, объединённое с нулевым элементом " width="" height="" />
:

$E(\mathbb _p) = \mathcal \cup \left\< (x, y) \in \mathbb_p \times \mathbb_p | y^2 \equiv x^3 + Ax + B \pmod p \right\>.$

Следует отметить, что в _p" width="" height="" />
у каждого ненулевого элемента есть либо два квадратных корня, либо нет ни одного, поэтому точки эллиптической кривой разбиваются на пары вида и .

Пример

Рассмотрим эллиптическую кривую над полем _5" width="" height="" />
. На этой кривой в частности лежит точка , так как .

Теорема Хассе

Теорема Хассе об эллиптических кривых утверждает, что количество точек на эллиптической кривой близко к размеру конечного поля:

$(\sqrt p - 1)^2 \leqslant |E(\mathbb<Z> _p)| \leqslant (\sqrt p + 1)^2,$

Эллиптические кривые над полями характеристики 2

Над полем характеристики 2 рассматривают два вида эллиптических кривых:

Особое удобство суперсингулярных эллиптических кривых в том, что для них легко вычислить порядок, в то время как вычисление порядка несуперсингулярных кривых вызывает трудности. Суперсингулярные кривые особенно удобны для создания самодельной ЕСС-криптосистемы. Для их использования можно обойтись без трудоёмкой процедуры вычисления порядка.

Проективные координаты

Для вычисления суммы пары точек на эллиптической кривой требуется не только несколько операций сложения и умножения в _q" width="" height="" />
, но и операция обращения, то есть для заданного _q" width="" height="" />
нахождение такого _q" width="" height="" />
, что , которая на один-два порядка медленнее, чем умножение. К счастью, точки на эллиптической кривой могут быть представлены в различных системах координат, которые не требуют использования обращения при сложении точек:

Важно отметить, что могут существовать различные именования — например, IEEE P1363-2000 называет проективными координатами то, что обычно называют координатами Якоби.

Реализация шифрования

Конкретные реализации алгоритмов шифрования на эллиптической кривой описаны ниже. Здесь мы рассмотрим общие принципы эллиптической криптографии.

Набор параметров

Для использования эллиптической криптографии все участники должны согласовать все параметры, определяющие эллиптическую кривую, т.е. набор параметров криптографического протокола. Эллиптическая кривая определяется константами и из уравнения (2). Абелева подгруппа точек является циклической и задается одной порождающей точкой G. При этом кофактор " width="" height="" />
, где n — порядок точки G, должен быть небольшим (, желательно даже ).

Итак, для поля характеристики 2 набор параметров: , а для конечного поля _p" width="" height="" />
, где , набор параметров: .

Существует несколько рекомендованных наборов параметров:

Для создания собственного набора параметров необходимо:

Выбрать набор параметров.
Найти эллиптическую кривую, удовлетворяющую этому набору параметров.

Для нахождения кривой для заданного набора параметров используются два метода:

Выбрать случайную кривую, затем воспользоваться алгоритмом подсчета точек. [4][5]
Выбрать точки, после чего построить кривую по этим точкам, используя технику умножения.

Быстрая редукция (NIST-кривые)

Деление по модулю p (которое необходимо для операций сложения и умножения) могут выполняться быстрее, если в качестве p выбрать простое число близкое к степени числа 2. В частности, в роли p может выступать простое число Мерсенна. Например, хорошим выбором являются - 1" width="" height="" />
или - 2^ - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1" width="" height="" />
. Национальный институт стандартов и технологий (NIST) рекомендует использовать подобные простые числа в качестве p.

Ещё одним преимуществом кривых, рекомендованных NIST, является выбор значения , что ускоряет операцию сложения в координатах Якоби.

Эллиптические кривые, рекомендованные NIST

NIST рекомендует 15 эллиптических кривых. В частности, FIPS 186-3 рекомендует 10 конечных полей. Некоторые из них:

Причем для каждого конечного поля рекомендуется одна эллиптическая кривая. Эти конечные поля и эллиптические кривые выбраны из-за высокого уровня безопасности и эффективности программной реализации.

Размер ключа

Самые сложные схемы на эллиптических кривых, публично взломанные к настоящему времени, содержали 112-битный ключ для конечного простого поля и 109-битный ключ для конечного поля характеристики 2. В июле 2009 года, кластер из более чем 200 Sony Playstation 3 за 3.5 месяца нашел 109-битный ключ. Ключ над полем характеристики 2 был найден в апреле 2004 года, с использованием 2600 компьютеров, в течение 17 месяцев.

Приложения

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

ECDH алгоритм, основывающийся на алгоритме Диффи — Хеллмана.
ECMQV алгоритм, основывающийся на MQV, протоколе распределения ключей Менезеса-Кью-Венстоуна.

Необходимо отметить, что безопасность таких систем цифровой подписи опирается не только на криптостойкость алгоритмов шифрования, но и на криптостойкость используемых криптографических хэш-функций и генераторов случайных чисел.

Читайте также: