RFC 6090 Fundamental Elliptic Curve Cryptography Algorithms

Internet Engineering Task Force (IETF)                         D. McGrew
Request for Comments: 6090                                 Cisco Systems
Category: Informational                                          K. Igoe
ISSN: 2070-1721                                                M. Salter
                                                National Security Agency
                                                           February 2011

Fundamental Elliptic Curve Cryptography Algorithms

Фундаментальные алгоритмы криптографии с эллиптическими кривыми

PDF

Аннотация

В этом документе описываются фундаментальные алгоритмы криптографии с эллиптическими кривыми (Elliptic Curve Cryptography или ECC), как они были определены в некоторых основополагающих документах 1997 г. и ранее. Эти описания могут быть полезны при реализации фундаментальных алгоритмов без использования каких-либо специализированных методов, разработанных позднее. Рассматриваются лишь эллиптические кривые с характеристикой больше 3, эти кривые применяются в наборе (Suite) B.

Статус документа

Документ не относится к категории Internet Standards Track и публикуется с информационными целями.

Документ является результатом работы IETF¹ и представляет согласованный взгляд сообщества IETF. Документ прошёл открытое обсуждение и был одобрен для публикации IESG². Не все документы, одобренные IESG, претендуют на статус стандартов Internet, см. раздел 2 в RFC 5741.

Информацию о текущем статусе документа, ошибках и способах обратной связи можно найти по ссылке http://www.rfc-editor.org/info/rfc6090.

Авторские права

Copyright (c) 2011. Авторские права принадлежат IETF Trust и лицам, указанным в качестве авторов документа. Все права защищены.

К документу применимы права и ограничения, указанные в BCP 78 и IETF Trust Legal Provisions и относящиеся к документам IETF (http://trustee.ietf.org/license-info), на момент публикации данного документа. Прочтите упомянутые документы внимательно, поскольку они могут описывать ваши права и ограничения применительно к этому документу. Компоненты кода, извлекаемые из этого документа, должны включать текст Simplified BSD License, как указано в параграфе 4.e Trust Legal Provisions и предоставляться без каких-либо гарантий, как указано в Simplified BSD License.

1. Введение

ECC — это технология с открытым ключом, обеспечивающая преимущества в производительности при более высоком уровне безопасности. Она включает основанные на эллиптических кривых протокол обмена ключами Диффи-Хеллмана (Diffie-Hellman или DH) [DH1976] и алгоритм подписи ElGamal [E1985]. Внедрение ECC шло медленней, чем ожидалось, возможно, из-за отсутствия свободно доступных нормативных документов и неопределённости в части прав интеллектуальной собственности.

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

Имеется несколько стандартов, задающих или включающих алгоритмы ECC, таких как протокол обмена ключами (Internet Key Exchange или IKE), ANSI X9.62, IEEE P1363. Описываемые здесь алгоритмы могут взаимодействовать с некоторыми из алгоритмов, заданных в этих стандартах, при выборе подходящих параметров и опций (см. раздел 7).

Параграфы 2.1 — 2.3 этого документа описывают терминологию и обозначения из модульной арифметики, теории групп и теории конечных полей, соответственно. В разделе 3 определены группы, основанные на эллиптических кривых над конечным полем с характеристикой больше 3. В разделе 4 представлен фундаментальный алгоритм ECDH (Elliptic Curve Diffie-Hellman), а в разделе 5 — метод подписи ElGamal с эллиптической кривой. В разделе 6 описано представление целых чисел строками октетов. Разделы 2 — 6 (включительно) содержат нормативный текст, задающий нормы для реализаций в соответствии с данной спецификацией, а остальные разделы являются лишь информационными. В разделе 7 обсуждаются вопросы функциональной совместимости, в разделе 8 — проверка реализации. Раздел 9 посвящён вопросам интеллектуальной собственности, раздел 10 — вопросам безопасности. В Приложении B описывается генерация случайных чисел, а в остальных приложениях содержатся уточняющие детали.

1.1. Уровни требований

Ключевые слова необходимо (MUST), недопустимо (MUST NOT), требуется (REQUIRED), нужно (SHALL), не нужно (SHALL NOT), следует (SHOULD), не следует (SHOULD NOT), рекомендуется (RECOMMENDED), возможно (MAY), необязательно (OPTIONAL) в данном документе должны интерпретироваться в соответствии с Приложением A.

2. Математические основы

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

2.1. Арифметические операции по модулю

В этом параграфе дан обзор арифметических операций по модулю. Целые числа x и y называют конгруэнтными по модулю n, если значение x — y кратно n.

Целые числа x и y взаимно просты, если их наибольший общий делитель равняется 1. В этом случае не существует третьего числа z > 1, являющегося делителем для x и y.

Множество Zq = { 0, 1, 2, …, q-1 } замкнуто для операций сложения, вычитания, умножения и обращения по модулю, описанных ниже.

Для каждой пары целых чисел a и b из Zq сумма a + b mod q равна a + b, если a + b < q, и a + b — q в ином случае.

Для каждой пары целых чисел a и b из Zq разность a — b mod q равна a — b, если a — b >= 0, и a — b + q в ином случае.

Для каждой пары целых чисел a и b из Zq произведение a * b mod q равно остатку от деления a * b на q.

Для каждого целого числа x из Zq, которое является взаимно простым с q, обращение x по модулю q обозначается как 1/x mod q и может быть вычислено с использованием расширенного алгоритма Евклида (см., например, параграф 4.5.2 в [K1981v2]).

Алгоритмы для этих операций хорошо известны и описаны, например, в разделе 4 [K1981v2].

2.2. Групповые операции

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

Группой является набор элементов G с операцией, которая принимает два элемента G и возвращает третий элемент G. Операция обозначается как *, а её применение — a * b для любой пары элементов a и b из группы G. Операция является ассоциативной для всех a, b и c из G, т. е. a * (b * c) = (a * b) * c. Применение групповой операции к элементу a N-1 раз обозначается как a^N для любого элемента группы G и любого положительного целого числа N, т. е. a^2 = a * a, a^3 = a * a * a и т. д. Ассоциативность групповой операции гарантирует однозначность вычисления a^n — любая группировка элементов даёт одинаковый результат.

В приведённом выше определении групповой операции используется мультипликативная запись. Иногда применяется другой вариант, называемый аддитивной записью, где вместо a * b используется a + b, а вместо a^N — Na³. В мультипликативной нотации a^N называется возведением в степень, а в аддитивной — скалярным умножением. В этом документе применяется мультипликативная нотация, в Приложении E приведено сопоставление двух нотаций.

В каждой группе имеется специальный элемент, называемый нейтральным (identity) и обозначаемый e. Для каждого a из группы G выполняется равенство e * a = a * e = a. По соглашению a^0 является нейтральным элементом, а a^1 совпадает с a для любого a из группы G⁴.

У каждого элемента a есть уникальный обратный элемент b, такой, что a * b = b * a = e. Величина, обратная a, обозначается в мультипликативной нотации как a^-1 (в аддитивной это будет -a.)

Для каждого положительного целого X принимается a^(-X) = (a^-1)^(X). В соответствии с этим соглашением возведение в степень происходит ожидаемым образом:

      a^(X+Y) = (a^X)*(a^Y)
      (a^X)^Y = a^(XY) = (a^Y)^X.

В криптографических приложениях обычно используются конечные группы (группы с конечным числом элементов) и для такой группы число её элементов называется порядком группы. Говорят, что элемент группы a имеет конечный порядок, если a^X = e для некого положительного целого X и порядок a равен наименьшему из таких X. Если такого X не существует, говорят, что a имеет бесконечный порядок. Все элементы конечной группы имеют конечный порядок и порядок элемента всегда является делителем порядка группы. Если элемент группы a имеет порядок R, для любых целых чисел X и Y выполняются условия

      a^X = a^(X mod R),
      a^X = a^Y тогда и только тогда, когда X конгруэнтно Y mod R

Множество H = { a, a^2, a^3, … , a^R=e } образует подгруппу G, называемую циклической подгруппой, порождённой a, а элемент a называют генератором H.

Обычно в группе имеется несколько элементов, порождающих H. Любой элемент группы вида a^M при M взаимно простом с R также является генератором H. Отметим, что a^M = a^(M mod R) для любого неотрицательного целого M⁵.

Для элемента a порядка R и целого числа i из диапазона 1 — R-1 (включительно) элемент a^i можно вычислить методом возведения в квадрат и умножения, описанным в параграфе 2.1 [M1983] (см. также параграф 4.6.3 в книге [K1981v2]), или иным методом.

2.3. Конечное поле Fp

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

Для простого числа p множество Zp с операциями сложения, вычитания, умножения и деления является конечным полем с характеристикой p. Для каждого ненулевого элемента x из поля Zp имеется обратное значение 1/x. Существует взаимно однозначное соответствие между целыми числами от 0 до p-1 (включительно) и элементами поля. Поле Zp иногда обозначается как Fp или GF(p).

Уравнения, включающие элементы поля, не содержат явной операции mod p, но она предполагается неявно. Например, утверждение о принадлежности x, y, z полю Fp и

      z = x + y

эквивалентно утверждению принадлежности x, y, z множеству

   { 0, 1, ..., p-1 } и
      z = x + y mod p.

3. Группы эллиптических кривых

В этом документе рассматриваются только эллиптические кривые над полями с характеристикой больше 3, эти кривые применяются в Suite B [SuiteB]. Для других полей определение группы эллиптических кривых будет иным.

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

      y^2 = x^3 + a*x + b,

где x, y, a, b — элементы поля Fp [M1985], а дискриминант отличен от 0 (см. параграф 3.3.1). Точкой эллиптической кривой является пара (x,y) значений из Fp, удовлетворяющих этому уравнению, или особая точка (@,@), представляющая нейтральный элемент (точка на бесконечности). Порядок группы эллиптической кривой — это число разных точек кривой.

Две точки эллиптической кривой (x1,y1) и (x2,y2) равны (совпадают), если x1=x2 и y1=y2 или обе точки находятся на бесконечности. Точкой, обратной (x1,y1) является (x1,-y1). Точка на бесконечности является обратной для себя.

Групповая операция, связанная с группой эллиптической кривой описана в [BC1989]. Произвольной паре точек P и Q с координатами (x1,y1) и (x2,y2) групповая операция назначает третью точку P*Q с координатами (x3,y3). Расчёт координат показан ниже

      (x3,y3) = (@,@), если P не равна Q, но x1 = x2.

      x3 = ((y2-y1)/(x2-x1))^2 - x1 - x2 
      y3 = (x1-x3)*(y2-y1)/(x2-x1) — y1, если P не равна Q и x1 не равно x2.

      (x3,y3) = (@,@), если P равна Q и y1 = 0.

      x3 = ((3*x1^2 + a)/(2*y1))^2 - 2*x1 
      y3 = (x1-x3)*(3*x1^2 + a)/(2*y1) — y1, если P = Q, а y1 не равно 0.

В приведённых выше выражениях a, x1, x2, x3, y1, y2, y3 — элементы поля Fp. При расчёте x3 и y3 на практике правая часть всегда должна сокращаться по модулю p. Псевдокод групповой операции приведён в Приложении F.1.

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

3.1. Однородные координаты

Другим вариантом реализации групповой операции является использование однородных координат [K1987] (см. также [KMOV1991]). Обычно этот метод более эффективен, поскольку не требует операции обращения по модулю.

Точка эллиптической кривой (x,y), отличная от (@,@), эквивалентна точке (X,Y,Z) в однородных координатах, если x=X/Z mod p и y=Y/Z mod p.

Пусть P1=(X1,Y1,Z1) и P2=(X2,Y2,Z2) — точки на эллиптической кривой, не равные (@,@), причём P1 не равно P2 и не равно P2^-1. Тогда произведение P3=(X3,Y3,Z3) = P1 * P2 определяется выражениями

      X3 = v * (Z2 * (Z1 * u^2 - 2 * X1 * v^2) - v^3) mod p
      Y3 = Z2 * (3 * X1 * u * v^2 - Y1 * v^3 - Z1 * u^3) + u * v^3 mod p
      Z3 = v^3 * Z1 * Z2 mod p

где u = Y2 * Z1 — Y1 * Z2 mod p и v = X2 * Z1 — X1 * Z2 mod p.

При P1 = P2 условие (X1/Z1, Y1/Z1) = (X2/Z2, Y2/Z2) верно тогда и только тогда, когда u = 0 и v = 0.

Произведение P3=(X3,Y3,Z3) = P1 * P1 определяется выражением

      X3 = 2 * Y1 * Z1 * (w^2 - 8 * X1 * Y1^2 * Z1) mod p
      Y3 = 4 * Y1^2 * Z1 * (3 * w * X1 - 2 * Y1^2 * Z1) - w^3 mod p
      Z3 = 8 * (Y1 * Z1)^3 mod p

где w = 3 * X1^2 + a * Z1^2 mod p. В этих выражениях a, u, v, w, X1, X2, X3, Y1, Y2, Y3, Z1, Z2, Z3 — целые числа из множества Fp. Псевдокод для групповой операции в однородных координатах приведён в Приложении F.2.

При преобразовании аффинных координат в однородные удобно установить Z = 1, при обратном преобразовании необходимо выполнить обращение по модулю, чтобы получить 1/Z mod p.

3.2. Другие координаты

Описаны и другие системы координат, часть которых представлена в [CC1986], включая координаты Якоби.

3.3. Параметры ECC

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

простое число p, указывающее порядок поля Fp;

значение a из уравнения кривой;

значение b из уравнения кривой;

генератор g из подгруппы;

порядок n подгруппы, генерируемой g.

Пример набора параметров ECC приведён в Приложении D. Генерация параметров выходит за рамки этого документа.

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

3.3.1. Дискриминант

Для каждой эллиптической группы дискриминант -16*(4*a^3 + 27*b^2) должен быть отличен от 0 по модулю p [S1986], что требует

      4*a^3 + 27*b^2 != 0 mod p.

3.3.2. Безопасность

Безопасность сильно зависит от выбора параметров и здесь приведены нормативные рекомендации по приемлемым вариантам. В разделе 10 содержится дополнительная информация.

Порядок группы, порождённой g, должен быть кратным большому целому числу, чтобы исключить простое решение задачи дискретного логарифмирования [K1987]. При некоторых вариантах параметров задача дискретного логарифмирования значительно упрощается. К таким наборам относятся параметры, для которых b = 0 и p = 3 (mod 4), а также a = 0 и p = 2 (mod 3) [MOV1993]. Такие параметры не подходят для криптографии и их не следует применять.

4. Метод Диффи-Хеллмана с эллиптической кривой (ECDH)

Протокол обмена ключами по методу Диффи-Хеллмана [DH1976] позволяет двум сторонам согласовать секретный ключ по незащищённому каналу связи. Метод исходно задан в терминах операций мультипликативной группы поля с большой простой характеристикой. Мэсси (Massey) [M1983] отметил, что метод можно легко обобщить для произвольной циклической группы. Миллер (Miller) [M1985] и Коблиц (Koblitz) [K1987] проанализировали протокол DH для группы эллиптических кривых. Здесь DH описывается в соответствии с первой ссылкой.

Пусть G — группа, g — её генератор, а t указывает порядок G. Протокол DH работает следующим образом. Сторона A выбирает случайный показатель степени j из интервала 1 — t-1 (включительно) с однородным распределением, вычисляет g^j и передаёт это значение стороне B. Сторона B выбирает случайный показатель степени k из интервала 1 — t-1 (включительно) с однородным распределением, вычисляет g^k и передаёт это значение стороне A. Затем каждая сторона может вычислить значение g^(j*k) — A рассчитывает (g^k)^j, а B — (g^j)^k.

Генерация случайных значений описана в Приложении B.

4.1. Типы данных

С каждым запуском протокола ECDH связывается конкретный набор параметров (см. параграф 3.3), открытые ключи g^j и g^k, а также общий секрет g^(j*k) являются элементами циклической подгруппы, связанной с этим набором.

Секретный ключ ECDH z является целым числом в Zt, где t — порядок подгруппы.

4.2. Компактное представление

Как указано в последнем абзаце [M1985], координата x значения общего секрета g^(j*k) является подходящим представлением точки, если возведение в степень используется как необратимая функция. В протоколе ECDH после расчёта элемента g^(j*k) координата x этого значения может служить общим секретом. Это называется здесь компактным выводом.

В соответствии с [M1985] при использовании в ECDH компактного вывода требуется передать лишь координату x, а не обе координаты, как в обычном аффинном представлении. Здесь это называется компактным представлением, а его математическое обоснование представлено в Приложении C.

ECDH можно применять с компактным выводом или без него. Обе стороны при конкретном запуске протокола ECDH должны применять один метод. ECDH можно использовать с компактным представлением или без такового. При использовании компактного представления в конкретном запуске ECDH должен применяться компактный вывод.

5. Подписи ElGamal с эллиптической кривой

5.1. Основы

Алгоритм цифровой подписи ElGamal представлен в 1984 г. [E1984a] [E1984b] [E1985] и основан на задаче дискретного логарифмирования. Исходно была задана мультипликативная группа целых чисел по модулю большого простого числа. Алгоритм легко расширить на другие конечные группы, такие как мультипликативная группа конечного поля GF(2^w) [AMV1990] или группа эллиптических кривых [A1992]. Подпись ElGamal состоит из пары компонентов. Существует множество возможных обобщений метода подписи ElGamal, полученных перестановками в уравнении второго компонента [HMP1994], [HP1994], [NR1994], [A1992], [AMV1990]. Эти обобщения не зависят от используемой математической группы и были описаны для мультипликативной группы с простым модулем, мультипликативной группы GF(2^w) и групп эллиптических кривых [HMP1994] [NR1994] [AMV1990] [A1992].

Алгоритм цифровой подписи (Digital Signature Algorithm или DSA) [FIPS186] является важным вариантом ElGamal.

5.2. Хэш-функции

Подписи ElGamal во всех вариантах алгоритма [HMP1994] должны использовать стойкую к коллизиям хэш-функцию, чтобы можно было подписывать сообщения произвольной длины и избегать атак с экзистенциальной подделкой (см. параграф 10.4). Обозначим хэш-функцию h(), её входными данными будем считать строку произвольной длины, а выходными — неотрицательное целое число.

Пусть H() — хэш-функция, дающая на выходе строку битов фиксированного размера. Для использования H в подписи ElGamal задаётся сопоставление результата функции с неотрицательным целым числом, реализующее вышеупомянутую функцию h(). При заданной строке битов m функция h(m) вычисляется следующим образом:

1. Вычисляется эквивалентное значение H(m) в виде строки битов фиксированного размера.

2. Битовая строка преобразуется в целое число i с принятием начального (слева) бита в качестве старшего бита i, а конечного (справа) — в качестве младшего.

5.3. Подписи KT-IV

Кояма (Koyama) и Цуруока (Tsuruoka) описали метод подписи, основанный на эллиптической кривой ElGamal, где первым компонентом подписи является x-координата точки эллиптической кривой, сокращённая по модулю q [KT1994]. В этом разделе описывается данный метод под названием KT-IV.

Алгоритм использует группу эллиптических кривых, как описано в параграфе 3.3, с порядком поля p (простое число) и параметрами уравнения кривой a и b. Генератор обозначается как alpha, а его порядок — как q. Исключительные ситуации проверяются в соответствии с [FIPS186].

5.3.1. Генерация ключевых пар

Секретный ключ z — это целое число от 1 до q-1 (включительно), генерируемое случайно с однородным распределением (см. Приложение B). Открытый ключ — это элемент группы Y = alpha^z. Каждому открытому ключу соответствует определённый набор параметров, как указано в параграфе 3.3.

5.3.2. Создание подписи

Расчёт подписи KT-IV для сообщения m с использованием секретного ключа z выполняется, как показано ниже.

1. Выбирается случайное целое число k (равномерное распределение) из интервала 1 — q-1 (включительно).

2. Вычисляется значение R = (r_x, r_y) = alpha^k.

3. Вычисляется значение s1 = r_x mod q.

4. Проверяется условие h(m) + z * s1 = 0 mod q и при его выполнении должно генерироваться новое значение k, а подпись должна создаваться заново. Как вариант, можно проверить условие s1 = 0 и при его выполнении следует генерировать новое значение k и заново рассчитывать подпись. Крайне маловероятно, что s1 = 0 или h(m) + z * s1 = 0 mod q, если подписи созданы корректно.

5. Вычисляется значение s2 = k/(h(m) + z*s1) mod q.

Подписью является упорядоченная пара (s1, s2), где оба элемента — неотрицательные целые числа.

5.3.3. Проверка подписи

Для данного сообщения m, генератора g, порядка группы q, открытого ключа Y и подписи (s1, s2) проверка имеет вид:

1. если не выполняется любое из условий 0 < s1 < q и 0 < s2 < q, проверка считается не пройденной и подпись нужно отклонить;

2. вычисляются неотрицательные целые числа u1 u2

             u1 = h(m) * s2 mod q
             u2 = s1 * s2 mod q

3. рассчитывается точка эллиптической кривой R’ = alpha^u1 * Y^u2;

4. если значение координаты x точки R’ по модулю q равно s1, подпись считается верной, в ином случае — нет.

5.4. Подписи KT-I

Хорстер (Horster), Михельс (Michels) и Петерсен (Petersen) классифицировали разные методы подписи ElGamal, показали их эквивалентность и преобразование подписей одного типа в другой [HMP1994]. По их терминологии метод из параграфа 5.3 и [KT1994] относится к типу IV, который получил обозначение KT-IV. Метод подписи KT типа I имеет второй компонент, рассчитываемый так же, как в алгоритме DSA. Здесь описан этот метод под названием KT-I.

5.4.1. Генерация ключевых пар

Ключевые пары и их генерация в точности соответствуют описанию в параграфе 5.3.1.

5.4.2. Создание подписи

Расчёт подписи KT-I для сообщения m с использованием секретного ключа z показан ниже.

1. Берётся случайное целое число k от 1 до q-1, включительно (однородное распределение, см. Приложение B).

2. Рассчитывается R = (r_x, r_y) = alpha^k.

3. Рассчитывается s1 = r_x mod q.

4. Рассчитывается s2 = (h(m) + z*s1)/k mod q.

5. Как вариант, можно проверить условия s1 = 0 и s2 = 0, а при выполнении любого из них, следует выбрать новое значение k и пересчитать подпись (крайне маловероятно при корректном создании подписи).

Подпись — это упорядоченная пара (s1, s2), оба компонента которой являются неотрицательными целыми числами.

5.4.3. Проверка подписи

Для сообщения m, открытого ключа Y и подписи (s1, s2) проверка показана ниже.

1. Проверяются условия 0 < s1 < q и 0 < s2 < q. При нарушении любого из них подпись нужно отвергнуть.

2. Рассчитывается s2_inv = 1/s2 mod q.

3. Рассчитываются неотрицательные целые числа u1 и u2

             u1 = h(m) * s2_inv mod q
             u2 = s1 * s2_inv mod q

4. Рассчитывается точка эллиптической кривой R’ = alpha^u1 * Y^u2.

5. Если значение x-координаты R’ по модулю q равно s1, подпись считается верной, в противном случае нет.

5.5. Преобразование подписей KT-IV в подписи KT-I

Подпись KT-IV для сообщения m и открытого ключа Y легко преобразовать в подпись KT-I для того же сообщения и открытого ключа. Если (s1, s2) — подпись KT-IV для сообщения m, подписью KT-I будет (s1, 1/s2 mod q) [HMP1994]. При преобразовании применяется лишь открытая информация и его может выполнить создатель KT-IV, проверяющий или любая другая сторона. Реализации могут использовать этот метод для расчёта подписей KT-I.

5.6. Обоснование

Этот параграф не является нормативным и включён лишь для информации.

В [HMP1994] представлено множество обобщений для подписей ElGamal. Уравнение (5) в этом документе задаёт

      A = x_A * B + k * C (mod q)

где x_A — секретный ключ, k — общий секрет, A, B и C определяются типом уравнения, как показано в таблице 1 [HMP1994]. DSA [FIPS186] — это метод подписи EG-I.1 (это KT-I) с A = m, B = -r, C = s (используются обозначения из [HMP1994], где первый компонент подписи — r, а второй — s; в KT-I и KT-IV эти компоненты обозначаются s1 и s2, соответственно; секретный ключ x_A соответствует секретному ключу z). Уравнение подписи имеет вид

      m = -r * z + s * k (mod q)

Метод подписи [KT1994] и метод из параграфа 5.3 — это EG-IV.1 с A = m * s, B = -r * s, C = 1 с уравнением подписи

      m * s = -r * s * z + k (mod q)

Функции f и g из таблицы 1 в [HMP1994] являются простым умножением, как описано под заголовком Fifth generalization.

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

Nyberg и Rueppel [NR1994] изучили множество методов подписи ElGamal и определили «строгую эквивалентность»:

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

Подписи KT-I и KT-IV, очевидно, являются строго эквивалентными.

Действительная подпись с s2=0 ведёт к утечке секретного ключа, поскольку в этом случае z = -h(m) / s1 mod q. Здесь этот исключительный случай проверен в соответствии с [FIPS186] для s1=0. Проверка s2=0 предложена Rivest [R1992] и рассмотрена в [BS1992].

В [KT1994] применяется «положительное целое число q’ не больше q» для расчёта компонента подписи s1 по x-координате r_x точки эллиптической кривой R = (r_x, r_y). Значение q’ применяется также при проверке подписи, когда сравнивается координата x расчётной точки эллиптической кривой со значением s1. Здесь предполагается q’ = q.

6. Преобразования между Integer и Octet String

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

6.1. Преобразование строки октетов в целое число

Пусть для строки октетов S, преобразуемой в целое число x, S1, …, Sk — октеты S от первого к последнему. Тогда x определяется уравнением

                          k
                    x =  SUM  2^(8(k-i)) Si 
                        i = 1

Иными словами, первый октет S будет старшим в целом числе, а последний — младшим, 0 <= x < 2^(8*k).

6.2. Преобразование целого числа в строку октетов

Целое число y преобразуется в строку октетов S размером k, как показано ниже.

                          k
                    y =  SUM  2^(8(k-i)) Si 
                        i = 1

Здесь S1, …, Sk — октеты S от первого к последнему. Преобразование не будет работать при y >= 2^(8*k)⁷.

Иными словами, первый октет S содержит старшие биты целого числа, последний — младшие.

7. Функциональная совместимость

Описанные здесь алгоритмы функционально совместимы с некоторыми другими спецификациями ECC. Далее эти вопросы рассматриваются более подробно.

7.1. ECDH

Раздел 4 можно использовать с протоколом IKE версии 2 [RFC2409] или 2 [RFC5996]. Эти алгоритмы совместимы с группами ECP из [RFC5903], [RFC5114], [RFC2409] и [RFC2412]. Определения групп применяются в протоколе для представления ключа с аффинными координатами. В [RFC5903] используется компактный вывод из параграфа 4.2, а в [RFC4753] (отменен RFC 5903) не используется. Ни в одном из этих RFC не применяется компактное представление. Отметим, что некоторые группы указывают отрицательные значения параметра кривой a, эти значения интерпретируются по модулю порядка поля. Например, параметр a = -3 эквивалентен p — 3, где p — порядок поля. Тестовые варианты из раздела 8 в [RFC5903] могут служить для проверки реализации, в них применяется мультипликативная запись, как и здесь. Содержимое (payload) KEi и KEr эквивалентно g^j и g^k, соответственно, с 64-битовым представлением данных.

Алгоритмы из раздела 4 можно применять для совместимости со стандартами IEEE [P1363] и ANSI [X9.62] для ECDH на основе полей с характеристикой больше 3. IEEE P1363 ECDH будет совместим с этим документом при указанном ниже выборе параметров:

простые кривые с сомножителем 1;

ECSVDP-DH (Elliptic Curve Secret Value Derivation Primitive с DH);

функция KDF должна быть функцией отождествления (identity), что эквивалентно пропуску этапа KDF и непосредственному выводу общего секрета.

7.2. KT-I и ECDSA

Алгоритм DSA основан на задаче дискретного логарифмирования над мультипликативной подгруппой конечного поля с большим простым порядком [DSA1991] [FIPS186]. Алгоритм ECDSA (Elliptic Curve Digital Signature Algorithm) [P1363] [X9.62] — это версия DSA с эллиптической кривой.

Метод KT-I математически и функционально эквивалентен ECDSA и может функционально совместим со стандартами IEEE [P1363] и ANSI [X9.62] для ECDSA на основе полей с характеристикой больше 3. Подписи KT-I могут быть проверены с помощью механизма верификации ECDSA, а подписи ECDSA — с помощью алгоритма верификации KT-I (см. параграф 10.4)8.

8. Проверка реализации

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

В тесте с известным ответом (known answer test или KAT) применяется фиксированный набор входных данных для проверки алгоритма. Вывод алгоритма сравнивается с ожидаемым значением, которое тоже фиксировано. KAT для ECDH и KT-I описаны в последующих параграфах.

Тест на согласованность генерирует входные данные для одного тестируемого алгоритма с использованием другого тестируемого алгоритма, затем проверяет вывод первого алгоритма. Алгоритм создания подписи может быть проверен на согласованность с алгоритмом проверки подписи. Реализации KT-I следует тестировать таким способом. Процессы создания подписи в них недетерминированы, поэтому их нельзя проверить с помощью KAT. Алгоритмы проверки подписи являются детерминированными и их следует тестировать с помощью KAT. Такая комбинация тестов охватывает все операции, включая генерацию ключевых пар. Тестирование на согласованность следует применять также для ECDH.

8.1. ECDH

Реализацию ECDH можно проверить с помощью KAT из [RFC5903] или [RFC5114]. Сопоставление обозначений данного документа и RFC 5903 приведено в таблице (см. параграф 3.3 и раздел 4, генератор g в аффинных координатах имеет вид (gx, gy)).

ECDH	RFC 5903
порядок p поля Fp	p
коэффициент кривой a	-3
коэффициент кривой b	b
генератор g	g=(gx, gy)
секретные ключи j и k	i и r
открытые ключи g^j, g^k	g^i = (gix, giy) и g^r = (grx, gry)

Ниже приведено сопоставление обозначений данного документа и RFC 5114.

ECDH	RFC 5114
порядок p поля Fp	p
коэффициент кривой a	a
коэффициент кривой b	b
генератор g	g=(gx, gy)
порядок группы n	n
секретные ключи j и k	dA и dB
открытые ключи g^j, g^k	g^(dA) = (x_qA, y_qA) и g^(dB) = (x_qB, y_qB)
общий секрет g^(j*k)	g^(dA*dB) = (x_Z, y_Z)

8.2. KT-I

Реализацию KT-I можно проверить с помощью KAT из [RFC4754]. Сопоставление обозначений данного документа и RFC 4754 приведено в таблице.

 

KT-I	RFC 4754
порядок p поля Fp	p
коэффициент кривой a	-3
коэффициент кривой b	b
генератор alpha	g
порядок группы q	q
секретный ключ z	w
открытый ключ Y	g^w = (gwx,gwy)
случайное значение k	эфемерный случайный ключ k
s1	r
s2	s
s2_inv	sinv
u1	u = h*sinv mod q
u2	v = r*sinv mod q

9. Интеллектуальная собственность

Опасения по поводу интеллектуальной собственности замедлили внедрение ECC, поскольку в последние годы был запатентован ряд оптимизаций и специализированных алгоритмов.

Все нормативные ссылки на ECDH (в соответствии с разделом 4) были опубликованы не позднее 1989 г., а для KT-I — не позднее мая 1994 г. Весь нормативный текст для этих алгоритмах основан на соответствующих документах.

9.1. Отказ от ответственности

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

Правила и процедуры IETF в части интеллектуальной собственности и патентов приведены в [RFC3979], [RFC4879] и https://datatracker.ietf.org/ipr/about/.

10. Вопросы безопасности

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

Метод Полига-Хеллмана (Pohlig-Hellman) относится к категории «разделяй и властвуй» (divide-and-conquer) [PH1978]. Если порядок группы n можно разложить на сомножители

      n = q1 * q2 * ... * qz,

задачу дискретного логарифмирования над группой можно решить путём независимого решения задач дискретного логарифмирования над группами порядка q1, q2, …, qz с последующим объединением результатов на основе китайской теоремы об остатках. Суммарные расчётные издержки определяются в основном издержками дискретного логарифмирования в подгруппе с наибольшим порядком.

Алгоритм Шенкса (Shanks) [K1981v3] позволяет рассчитать дискретный логарифм в группе порядка n, используя O(sqrt(n)) операций и O(sqrt(n)) памяти. Алгоритм Ро Полларда (Pollard rho) [P1978] позволяет рассчитать дискретный логарифм в группе порядка n, используя O(sqrt(n)) операций с незначительным объёмом памяти, и может быть эффективно реализован параллельно [VW1994].

Лябда-алгоритм Полларда [P1978] позволяет решить задачу дискретного логарифмирования с использованием O(sqrt(w)) операций и O(log(w)) памяти, когда известно, что показатель степени лежит в интервале шириной w.

Описанные выше алгоритмы работают в любой группе. Имеются специализированные алгоритмы, предназначенные для групп эллиптических кривых. Субэкспоненциальные алгоритмы для базовых групп эллиптических кривых не известны, однако имеются методы, нацеленные на особые группы эллиптических кривых [MOV1993] [FR1994].

10.1. Подгруппы

Группа, состоящая из непустого набора элементов S с соответствующей групповой операцией *, является подгруппой группы с набором элементов G, если эта группа имеет ту же групповую операцию и S является подмножеством G. Для каждого уравнения эллиптической кривой существует группа эллиптических кривых с таким же порядком, как у эллиптической кривой, т. е. группа, содержащая все точки на кривой.

Порядок m эллиптической кривой делится на порядок n связанной с генератором группы, т. е. для каждой группы эллиптических кривых m = n * c для некого числа c, называемого сомножителем (cofactor) [P1363]. Каждый набор параметров ECC (см. параграф 3.3) связан с определенным сомножителем.

Можно и желательно использовать сомножитель 1.

10.2. Метод Диффи-Хеллмана

Отметим, что описанный в разделе 4 протокол обмена ключами не защищён от активных атак. Сторона A должна применять тот или иной метод, обеспечивающий получение (g^k) от фактической стороны B, а не от атакующего. То же самое должна сделать и сторона B для (g^j).

Аутентификации общего секрета g^(j*k) недостаточно, поскольку это не защищает от атак, манипулирующих открытыми ключами. Вместо этого следует напрямую проверять подлинность значений g^x и g^y в процессе обмена. Эта стратегия применяется протоколами на основе метода Диффи-Хеллмана с аутентификацией конечных элементов (сущностей) для защиты от активных атак, такими как OAKLEY [RFC2412] и IKE [RFC2409] [RFC4306] [RFC5996].

Когда сомножитель группы не равен 1, против ECDH возможен ряд атак (см. [VW1996], [AV1996], [LL1997]).

10.3. Представление группы и безопасность

Групповая операция эллиптической кривой не включает явно параметр b из уравнения кривой. Это позволяет злоумышленнику узнать секретный ключ ECDH, передав поддельный открытый ключ [BMM2000]. Злоумышленник может создать группу эллиптических кривых G’, имеющую параметры, идентичные параметрам группы G, применяемой в протоколе ECDH, за исключением различия в b. Затем атакующий может представить точку из G’ для протокола ECDH, использующего группу G, и получить информацию из того факта, что групповые операции с секретным ключом атакуемого устройства используют G’ вместо G. Такая атака позволяет получить информацию о секретном ключе ECDH, связанном со статическим открытым ключом, т. е. с открытым ключом неоднократно использованным при работе протокола. Однако это не даст полезных для злоумышленника сведений в случае эфемерных ключей.

Такие атаки предотвращаются, если реализация ECDH не считает, что каждая пара координат в Zp фактически является точкой соответствующей эллиптической кривой.

Эти соображения применимы и к использованию ECDH с компактным представлением (Приложение C).

10.4. Подписи

Параметры эллиптической кривой следует использовать лишь при их получении из доверенного источника, иначе становятся возможными некоторые атаки [AV1996] [V1996].

Если в подписи ElGamal не применяется хэш-функция, система становится уязвимой для экзистенциальных подделок, когда не знающий секретного ключа злоумышленник может создавать действительные подписи для соответствующего открытого ключа, но не может создать подпись для сообщения по своему выбору (см. например, [E1985]). Использование стойких к коллизиям хэш-функций устраняет эту уязвимость.

Для применения в подписях KT в принципе подходит любая хэш-функция, стойкая к коллизиям. Для обеспечения функциональной совместимости принимаются в качестве H (параграф 5.2) указанные ниже хэш-функции:

SHA-256 с 256-битовым выводом;

SHA-384 с 384-битовым выводом;

SHA-512 с 512-битовым выводом.

Все эти функции определены в [FIPS180-2].

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

11. Благодарности

Авторы признательны создателям криптографии на основе эллиптических кривых, чья работа сделала возможным этот документ, а также всем рецензентам, предоставившим ценные конструктивные отзывы. Отдельная благодарность Howard Pinder, Andrey Jivsov, Alfred Hoenes (за алгоритмы из Приложения F), Dan Harkins и Tina Tsou.

12. Литература

12.1. Нормативные документы

[AMV1990] Agnew, G., Mullin, R., and S. Vanstone, «Improved Digital Signature Scheme based on Discrete Exponentiation», Electronics Letters Vol. 26, No. 14, July, 1990.

[BC1989] Bender, A. and G. Castagnoli, «On the Implementation of Elliptic Curve Cryptosystems», Advances in Cryptology — CRYPTO ’89 Proceedings, Springer Lecture Notes in Computer Science (LNCS), volume 435, 1989.

[CC1986] Chudnovsky, D. and G. Chudnovsky, «Sequences of numbers generated by addition in formal groups and new primality and factorization tests», Advances in Applied Mathematics, Volume 7, Issue 4, December 1986.

[D1966] Deskins, W., «Abstract Algebra», MacMillan Company New York, 1966.

[DH1976] Diffie, W. and M. Hellman, «New Directions in Cryptography», IEEE Transactions in Information Theory IT-22, pp. 644-654, 1976.

[FR1994] Frey, G. and H. Ruck, «A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves.», Mathematics of Computation Vol. 62, No. 206, pp. 865-874, 1994.

[HMP1994] Horster, P., Michels, M., and H. Petersen, «Meta-ElGamal signature schemes», University of Technology Chemnitz-Zwickau Department of Computer Science, Technical Report TR-94-5, May 1994.

[K1981v2] Knuth, D., «The Art of Computer Programming, Vol. 2: Seminumerical Algorithms», Addison Wesley , 1981.

[K1987] Koblitz, N., «Elliptic Curve Cryptosystems», Mathematics of Computation, Vol. 48, 1987, pp. 203-209, 1987.

[KT1994] Koyama, K. and Y. Tsuruoka, «Digital signature system based on elliptic curve and signer device and verifier device for said system», Japanese Unexamined Patent Application Publication H6-43809, February 18, 1994.

[M1983] Massey, J., «Logarithms in finite cyclic groups — cryptographic issues», Proceedings of the 4th Symposium on Information Theory, 1983.

[M1985] Miller, V., «Use of elliptic curves in cryptography», Advances in Cryptology — CRYPTO ’85 Proceedings, Springer Lecture Notes in Computer Science (LNCS), volume 218, 1985.

[MOV1993] Menezes, A., Vanstone, S., and T. Okamoto, «Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field», IEEE Transactions on Information Theory Vol. 39, No. 5, pp. 1639-1646, September, 1993.

[R1993] RSA Laboratories, «PKCS#1: RSA Encryption Standard», Technical Note version 1.5, 1993.

[S1986] Silverman, J., «The Arithmetic of Elliptic Curves», Springer-Verlag, New York, 1986.

12.2. Дополнительная литература

[A1992] Anderson, J., «Response to the proposed DSS», Communications of the ACM, v. 35, n. 7, p. 50-52, July 1992.

[AV1996] Anderson, R. and S. Vaudenay, «Minding Your P’s and Q’s», Advances in Cryptology — ASIACRYPT ’96 Proceedings, Springer Lecture Notes in Computer Science (LNCS), volume 1163, 1996.

[BMM2000] Biehl, I., Meyer, B., and V. Muller, «Differential fault analysis on elliptic curve cryptosystems», Advances in Cryptology — CRYPTO 2000 Proceedings, Springer Lecture Notes in Computer Science (LNCS), volume 1880, 2000.

[BS1992] Branstad, D. and M. Smid, «Response to Comments on the NIST Proposed Digital Signature Standard», Advances in Cryptology — CRYPTO ’92 Proceedings, Springer Lecture Notes in Computer Science (LNCS), volume 740, August 1992.

[DSA1991] U.S. National Institute of Standards and Technology, «DIGITAL SIGNATURE STANDARD», Federal Register, Vol. 56, August 1991.

[E1984a] ElGamal, T., «Cryptography and logarithms over finite fields», Stanford University, UMI Order No. DA 8420519, 1984.

[E1984b] ElGamal, T., «Cryptography and logarithms over finite fields», Advances in Cryptology — CRYPTO ’84 Proceedings, Springer Lecture Notes in Computer Science (LNCS), volume 196, 1984.

[E1985] ElGamal, T., «A public key cryptosystem and a signature scheme based on discrete logarithms», IEEE Transactions on Information Theory, Vol. 30, No. 4, pp. 469-472, 1985.

[FIPS180-2] U.S. National Institute of Standards and Technology, «SECURE HASH STANDARD», Federal Information Processing Standard (FIPS) 180-2, August 2002.

[FIPS186] U.S. National Institute of Standards and Technology, «DIGITAL SIGNATURE STANDARD», Federal Information Processing Standard FIPS-186, May 1994.

[HP1994] Horster, P. and H. Petersen, «Verallgemeinerte ElGamal-Signaturen», Proceedings der Fachtagung SIS ’94, Verlag der Fachvereine, Zurich, 1994.

[K1981v3] Knuth, D., «The Art of Computer Programming, Vol. 3: Sorting and Searching», Addison Wesley, 1981.

[KMOV1991] Koyama, K., Maurer, U., Vanstone, S., and T. Okamoto, «New Public-Key Schemes Based on Elliptic Curves over the Ring Zn», Advances in Cryptology — CRYPTO ’91 Proceedings, Springer Lecture Notes in Computer Science (LNCS), volume 576, 1991.

[L1969] Lehmer, D., «Computer technology applied to the theory of numbers», M.A.A. Studies in Mathematics, 180-2, 1969.

[LL1997] Lim, C. and P. Lee, «A Key Recovery Attack on Discrete Log-based Schemes Using a Prime Order Subgroup», Advances in Cryptology — CRYPTO ’97 Proceedings, Springer Lecture Notes in Computer Science (LNCS), volume 1294, 1997.

[NR1994] Nyberg, K. and R. Rueppel, «Message Recovery for Signature Schemes Based on the Discrete Logarithm Problem», Advances in Cryptology — EUROCRYPT ’94 Proceedings, Springer Lecture Notes in Computer Science (LNCS), volume 950, May 1994.

[P1363] «Standard Specifications for Public Key Cryptography», Institute of Electric and Electronic Engineers (IEEE), P1363, 2000.

[P1978] Pollard, J., «Monte Carlo methods for index computation mod p», Mathematics of Computation, Vol. 32, 1978.

[PH1978] Pohlig, S. and M. Hellman, «An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance», IEEE Transactions on Information Theory, Vol. 24, pp. 106-110, 1978.

[R1988] Rose, H., «A Course in Number Theory», Oxford University Press, 1988.

[R1992] Rivest, R., «Response to the proposed DSS», Communications of the ACM, v. 35, n. 7, p. 41-47, July 1992.

[RFC2119] Bradner, S., «Key words for use in RFCs to Indicate Requirement Levels», BCP 14, RFC 2119, March 1997.

[RFC2409] Harkins, D. and D. Carrel, «The Internet Key Exchange (IKE)», RFC 2409, November 1998.

[RFC2412] Orman, H., «The OAKLEY Key Determination Protocol», RFC 2412, November 1998.

[RFC3979] Bradner, S., «Intellectual Property Rights in IETF Technology», BCP 79, RFC 3979, March 2005.

[RFC4086] Eastlake, D., Schiller, J., and S. Crocker, «Randomness Requirements for Security», BCP 106, RFC 4086, June 2005.

[RFC4306] Kaufman, C., «Internet Key Exchange (IKEv2) Protocol», RFC 4306, December 2005.

[RFC4753] Fu, D. and J. Solinas, «ECP Groups For IKE and IKEv2», RFC 4753, January 2007.

[RFC4754] Fu, D. and J. Solinas, «IKE and IKEv2 Authentication Using the Elliptic Curve Digital Signature Algorithm (ECDSA)», RFC 4754, January 2007.

[RFC4879] Narten, T., «Clarification of the Third Party Disclosure Procedure in RFC 3979», BCP 79, RFC 4879, April 2007.

[RFC5114] Lepinski, M. and S. Kent, «Additional Diffie-Hellman Groups for Use with IETF Standards», RFC 5114, January 2008.

[RFC5903] Fu, D. and J. Solinas, «Elliptic Curve Groups modulo a Prime (ECP Groups) for IKE and IKEv2», RFC 5903, June 2010.

[RFC5996] Kaufman, C., Hoffman, P., Nir, Y., and P. Eronen, «Internet Key Exchange Protocol Version 2 (IKEv2)», RFC 5996, September 2010.

[SuiteB] U. S. National Security Agency (NSA), «NSA Suite B Cryptography», <http://www.nsa.gov/ia/programs/suiteb_cryptography/index.shtml>.

[V1996] Vaudenay, S., «Hidden Collisions on DSS», Advances in Cryptology — CRYPTO ’96 Proceedings, Springer Lecture Notes in Computer Science (LNCS), volume 1109, 1996.

[VW1994] van Oorschot, P. and M. Wiener, «Parallel Collision Search with Application to Hash Functions and Discrete Logarithms», Proceedings of the 2nd ACM Conference on Computer and communications security, pp. 210-218, 1994.

[VW1996] van Oorschot, P. and M. Wiener, «On Diffie-Hellman key agreement with short exponents», Advances in Cryptology — EUROCRYPT ’96 Proceedings, Springer Lecture Notes in Computer Science (LNCS), volume 1070, 1996.

[X9.62] «Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)», American National Standards Institute (ANSI) X9.62.

Приложение A. Уровни требований

Определения ключевых слов заимствованы из [RFC2119] и широко применяются в стандартах Internet. Они приведены здесь, чтобы избежать ссылок на нормативные документы, опубликованные после 1994 г.

1. MUST — необходимо, должно

   Это слово, а также термины требуется (REQUIRED) и нужно (SHALL) используется для требований, которые являются абсолютно необходимыми в данной спецификации.

2. MUST NOT — недопустимо

   Эта фраза или слова SHALL NOT (не позволяется) означают абсолютный запрет в рамках спецификации.

3. SHOULD — следует

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

4. SHOULD NOT — не следует

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

5. MAY — возможно

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

Приложение B. Генерация случайных чисел

Легко сгенерировать простое число с однородным случайным распределением из интервала от 0 до (2^t)-1, включительно, при некотором положительном целом значении t. Генерируется строка случайных битов размером t, которая затем преобразуется в неотрицательное целое число трактовкой каждого бита как коэффициента в разложении целого числа на степени 2.

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

1. Генерируется случайный кандидат c из набора с однородным распределением, включающего все целые числа со свойством P (и некоторые другие числа, которых желательно иметь не слишком много).

2. Если c обладает свойством P, возвращается значение c. В ином случае повторяется п. 1.

Например, для генерации чисел от 1 до n-1, включительно, генерируются числа от 0 до (2^t)-1, включительно, с выбором первого значения из нужного интервала.

Рекомендации по генерации случайных строк битов приведены в [RFC4086].

Приложение C. Почему работает компактное представление

В аффинном представлении координата x точки P^i не зависит от координаты y точки P при любом неотрицательном показателе i и любой точке P. Рассмотрим это. Когда дана лишь x-координата точки P, невозможно точно определить координату y, но значение y будет решением уравнения кривой

      y^2 = x^3 + a*x + b (mod p)

Существует не более двух решений этого уравнения — y = w и y = -w mod p, а точкой P должна быть Q=(x,w) или Q^-1=(x,-w). Таким образом, P^n эквивалентна Q^n или (Q^-1)^n = (Q^n)^-1. Эти значения имеют ту же координату x. Таким образом, x-координату точки P^i можно рассчитать по координате x точки P путём вычисления одного из возможных значений координаты y точки P, возведения P в степень i и игнорирования y-координаты результата.

В общем случае можно вычислить квадратный корень по модулю p, используя метод Шенка (Shank) [K1981v2]. Имеется простой метод для некоторых значений p. При p = 3 (mod 4) квадратный корень из z mod p равен w и -w mod p, где

      w = z ^ ((p+1)/4) (mod p)

Это отмечено Лемером (Lehmer) [L1969]. Когда p удовлетворяет этому свойству, y можно вычислить по уравнению кривой и y = w или y = -w mod p, где

      w = (x^3 + a*x + b)^((p+1)/4) (mod p)

Квадратные корни по модулю p существуют только для квадратичного остатка по модулю p [R1988], если z не является квадратичным остатком, не существует числа w, такого, что w^2 = z (mod p). Простым способом проверки того, что z является квадратичным остатком после вычисления w, является проверка равенства w * w = z (mod p). Если это не выполняется для приведённого выше уравнения, значение x не является действительной x-координатой действительной точки эллиптической кривой. Это важно при использовании ECDH с компактным выводом (см. параграф 10.3).

Для простых чисел, используемых в кривых P-256, P-384, P-521 из [RFC5903], выполняется условие p = 3 (mod 4).

Приложение D. Пример набора параметров ECC

Для конкретности вспомним эллиптическую кривую, заданную Солинасом (Solinas) и Фу (Fu) в [RFC5903] и называемую P-256, которая, как полагают, обеспечивает уровень безопасности в 128 битов. Используя нотацию параграфа 3.3 и представление генератора в аффинных координатах g=(gx,gy), где значения gx и gy относятся к Fp, получим

   p: FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
   a: - 3
   b: 5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
   n: FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551
   gx: 6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296
   gy: 4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5

Отметим, что p можно представить в виде p = 2^(256)-2^(224)+2^(192)+2^(96)-1.

Приложение E. Аддитивная и мультипликативная нотация

В ранних публикациях по криптографии с эллиптическими кривыми применялась мультипликативная нотация, а в большинстве современных принята аддитивная. В этом приложении дано сопоставление этих вариантов. Здесь a и b — элементы группы эллиптических кривых, а N — целое число.

 

Мультипликативная нотация	Аддитивная нотация
умножение	сложение
a * b	a + b
возведение в квадрат	удвоение
a * a = a^2	a + a = 2a
возведение в степень	скалярное умножение
a^N = a * a * … * a	Na = a + a + … + a
обращение	обращение
a^-1	-a

Приложение F. Алгоритмы

В этом приложении представлено описание групповой операции эллиптической кривой в форме псевдокода. Текст после символов // является комментарием, а не инструкциями.

F.1. Аффинные координаты

Произвольной паре точек эллиптической кривой P и Q, заданных аффинными координатами P=(x1,y1) и Q=(x2,y2), групповая операция назначает третью точку R = P*Q с координатами (x3,y3). Расчёт этих координат показан ниже.

     if P is (@,@)
        R = Q
     else if Q is (@,@)
        R = P
     else if P не равно Q и x1 равно x2
        R = (@,@)
     else if P не равно Q и x1 не равно x2
        x3 = ((y2-y1)/(x2-x1))^2 - x1 - x2 mod p and
        y3 = (x1-x3)*(y2-y1)/(x2-x1) - y1 mod p
     else if P рано Q и y1 равно 0
        R = (@,@)
     else    // P равно Q и y1 не равно 0
        x3 = ((3*x1^2 + a)/(2*y1))^2 - 2*x1 mod p and
        y3 = (x1-x3)*(3*x1^2 + a)/(2*y1) - y1 mod p9

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

Из уравнения кривой следует, что для данной точки кривой P = (x,y), отличной от точки на бесконечности, (x,-y) тоже является точкой кривой, а третий и четвёртый случаи показывают, что это обращение P, т. е. P^-1.

Отметим, что пятый и шестой случаи называют возведением точки в квадрат (point squaring).

F.2. Однородные координаты

Точка эллиптической кривой (x,y), отличная от точки на бесконечности (@,@), эквивалентна точке (X,Y,Z) в однородных координатах (X, Y, Z относятся к Fp и все три одновременно не равны 0) всякий раз, когда x=X/Z и y=Y/Z. «Однородные координаты» означают, что два триплета (X,Y,Z) и (X’,Y’,Z’) считаются «равными» (представляющими одну точку) если в Fp имеется отличное от 0 значение s, такое, что X’=s*X, Y’=s*Y, Z’=s*Z. Точка на бесконечности (@,@) считается эквивалентом (0,1,0), т. е. может быть представлена любым триплетом (0,Y,0) с отличным от 0 Y из Fp.

Пусть точки P1=(X1,Y1,Z1) и P2=(X2,Y2,Z2) относятся к эллиптической кривой, u = Y2 * Z1 — Y1 * Z2, v = X2 * Z1 — X1 * Z2.

Точки P1 и P2 эквивалентны тогда и только тогда, когда u и v равны 0. В ином случае, если P1 или P2 является точкой на бесконечности, v = 0, а u не равно 0 (обратное не верно).

Произведение P3=(X3,Y3,Z3) = P1 * P2 определяется как

     if P1 - точка на бесконечности
        P3 = P2
     else if P2 - точка на бесконечности
        P3 = P1
     else if P1=-P2 как проективные точки1
        P3 = (0,1,0)
     else if P1 не равно P2
        X3 = v * (Z2 * (Z1 * u^2 - 2 * X1 * v^2) - v^3)
        Y3 = Z2 * (3 * X1 * u * v^2 - Y1 * v^3 - Z1 * u^3) + u * v^3
        Z3 = v^3 * Z1 * Z2
     else    // P2 равно P1, P3 = P1 * P1
         w = 3 * X1^2 + a * Z1^2
        X3 = 2 * Y1 * Z1 * (w^2 - 8 * X1 * Y1^2 * Z1)
        Y3 = 4 * Y1^2 * Z1 * (3 * w * X1 - 2 * Y1^2 * Z1) - w^3
        Z3 = 8 * (Y1 * Z1)^3

Таким образом, точка на бесконечности является нейтральным элементом и для P1=(X,Y,Z), не являющейся точкой на бесконечности, P2=(X,-Y,Z) представляет P1^-1.

Адреса авторов

David A. McGrew

Cisco Systems

510 McCarthy Blvd.

Milpitas, CA 95035

USA

Phone: (408) 525 8651

EMail: mcgrew@cisco.com

URI: http://www.mindspring.com/~dmcgrew/dam.htm

Kevin M. Igoe

National Security Agency

Commercial Solutions Center

United States of America

EMail: kmigoe@nsa.gov

Margaret Salter

National Security Agency

9800 Savage Rd.

Fort Meade, MD 20755-6709

USA

EMail: msalter@restarea.ncsc.mil

---

Перевод на русский язык

Николай Малых

nmalykh@protokols.ru

---