Internet Research Task Force (IRTF) A. Langley
Request for Comments: 7748 Google
Category: Informational M. Hamburg
ISSN: 2070-1721 Rambus Cryptography Research
S. Turner
sn3rd
January 2016
Elliptic Curves for Security
Эллиптические кривые для безопасности
Аннотация
В этом документе заданы две эллиптические кривые над полем простых чисел, обеспечивающие очень высокий практический уровень безопасности в криптографических приложениях, включая защиту транспортного уровня (Transport Layer Security или TLS). Эти кривые предназначены для работы на уровне защиты ~128 и ~224 бита, соответственно, и генерируются детерминированно на основе списка требуемых параметров.
Статус документа
Документ не относится к категории Internet Standards Track и публикуется с информационными целями.
Документ является результатом работы IRTF1. IRTF публикует результаты исследований и разработок, связанных с Internet. Эти результаты могут оказаться не подходящими для внедрения. В данном RFC представлена согласованная точка зрения исследовательской группы Crypto Forum в составе IRTF. Документ был одобрен для публикации IRSG2 и не претендует на статус стандарта Internet (см. раздел 2 в RFC 5741).
Информацию о текущем статусе документа, ошибках и способах обратной связи можно найти по ссылке http://www.rfc-editor.org/info/rfc7748.
Авторские права
Copyright (c) 2016. Авторские права принадлежат IETF Trust и лицам, указанным в качестве авторов документа. Все права защищены.
К документу применимы права и ограничения, указанные в BCP 78 и IETF Trust Legal Provisions и относящиеся к документам IETF (http://trustee.ietf.org/license-info), на момент публикации данного документа. Прочтите упомянутые документы внимательно, поскольку они могут описывать ваши права и ограничения применительно к этому документу.
1. Введение
С момента начальной стандартизации криптографии с аналитическими кривыми (Elliptic Curve Cryptography или ECC) [RFC6090] в [SEC1] был достигнут существенный прогресс, связанный как с эффективностью, так и с безопасностью кривых и реализаций. Заметными примерами являются алгоритмы, защищённые от некоторых атак по побочным каналам, различные «особые» простые числа, позволяющие ускорить арифметические операции по модулю, и более широкий набор моделей кривых для выбора. В сообществе высказана обеспокоенность по поводу генерации и возможных недостатков кривых, заданных NIST [NIST].
Этот документ задаёт две эллиптические кривые (curve25519 и curve448), предлагаемые для реализаций с постоянным временем и не содержащим исключений скалярным умножением, устойчивым к широкому спектру атак по побочным каналам, включая атаки по времени и атаки на кэш. Это кривые Монтгомери (где v^2 = u^3 + A*u^2 + u), имеющие бирационально эквивалентные версии по Эдвардсу. Кривые Эдвардса поддерживают самые быстрые в настоящее время полные формулы операций для групп эллиптических кривых, в частности, кривую Эдвардса x^2 + y^2 = 1 + d*x^2*y^2 для простых чисел p = 3 mod 4 и скрученную кривую Эдвардса -x^2 + y^2 = 1 + d*x^2*y^2 при p = 1 mod 4. Также выполнены сопоставления между кривыми Монтгомери и эквивалентными (скрученными) кривыми Эдвардса.
В документе также описано применение этих кривых для согласования ключей по методу Диффи-Хеллмана.
2. Уровни требования
Ключевые слова необходимо (MUST), недопустимо (MUST NOT), требуется (REQUIRED), нужно (SHALL), не следует (SHALL NOT), следует (SHOULD), не нужно (SHOULD NOT), рекомендуется (RECOMMENDED), не рекомендуется (NOT RECOMMENDED), возможно (MAY), необязательно (OPTIONAL) в данном документе интерпретируются в соответствии с [RFC2119].
3. Обозначения
p
Простое число, задающее базовое поле.
GF(p)
Конечное поле с p элементами.
A
Элемент конечного поля GF(p), не равный -2 и 2.
d
Ненулевой элемент конечного поля GF(p), отличный от 1 для кривой Эдвардса и от -1 для скрученной кривой Эдвардса.
order
Порядок подгруппы prime-order.
P
Генерирующая точка над первичным порядком GF(p).
U(P)
Координата u точки P на эллиптической кривой Монтгомери.
V(P)
Координата v точки P на эллиптической кривой Монтгомери.
X(P)
Координата x точки P на (скрученной) эллиптической кривой Эдвардса.
Y(P)
Координата y точки P на (скрученной) эллиптической кривой Эдвардса.
u, v
Координаты на кривой Монтгомери.
x, y
Координаты на (скрученной) кривой Эдвардса.
4. Рекомендуемые кривые
4.1. Curve25519
Для уровня безопасности ~128 бит простое число 2^255 — 19 рекомендуется как обеспечивающее высокую производительность на широком спектре платформ. Между 2^250 и 2^521 существует немного простых чисел вида 2^c-s с малым значением s и другие значения не столь конкурентоспособны в части производительности. Указанное число конгруэнтно 1 mod 4 и процедура вывода из Приложения A ведёт к кривой Монтгомери v^2 = u^3 + A*u^2 + u, называемой curve25519:
p 2^255 - 19
A 486662
order 2^252 + 0x14def9dea2f79cd65812631a5cf5d3ed
cofactor 8
U(P) 9
V(P) 147816194475895447910205935684099868872646061346164752889648818
37755586237401
Базовая точка — u = 9, v = 14781619447589544791020593568409986887264606134616475288964881837755586237401.
Эта кривая бирационально эквивалентна скрученной кривой Эдвардса -x^2 + y^2 = 1 + d*x^2*y^2, называемой edwards25519, где:
p 2^255 - 19
d 370957059346694393431380835087545651895421138798432190163887855330
85940283555
order 2^252 + 0x14def9dea2f79cd65812631a5cf5d3ed
cofactor 8
X(P) 151122213495354007725011514095885315114540126930418572060461132
83949847762202
Y(P) 463168356949264781694283940034751631413079938662562256157830336
03165251855960
Бирациональное сопоставление имеет вид:
(u, v) = ((1+y)/(1-y), sqrt(-486664)*u/x)
(x, y) = (sqrt(-486664)*u/v, (u-1)/(u+1))
Определённая здесь кривая Монтгомери равна заданной в [curve25519], а эквивалентная скрученная кривая Эдвардса равна заданной в [ed25519].
4.2. Curve448
Для уровня безопасности ~224 бит простое число 2^448 — 2^224 — 1 рекомендуется как обеспечивающее высокую производительность на широком спектре платформ. Это простое число конгруэнтно 3 mod 4 и процедура вывода из Приложения A даёт показанную ниже кривую Монтгомери curve448.
p 2^448 - 2^224 - 1
A 156326
order 2^446 -
0x8335dc163bb124b65129c96fde933d8d723a70aadc873d6d54a7bb0d
cofactor 4
U(P) 5
V(P) 355293926785568175264127502063783334808976399387714271831880898
435169088786967410002932673765864550910142774147268105838985595290
606362
Эта кривая бирационально эквивалентна скрученной кривой Эдвардса x^2 + y^2 = 1 + d*x^2*y^2, где:
p 2^448 - 2^224 - 1
d 611975850744529176160423220965553317543219696871016626328968936415
087860042636474891785599283666020414768678979989378147065462815545
017
order 2^446 -
0x8335dc163bb124b65129c96fde933d8d723a70aadc873d6d54a7bb0d
cofactor 4
X(P) 345397493039729516374008604150537410266655260075183290216406970
281645695073672344430481787759340633221708391583424041788924124567
700732
Y(P) 363419362147803445274661903944002267176820680343659030140745099
590306164083365386343198191849338272965044442230921818680526749009
182718
Бирациональное сопоставление имеет вид:
(u, v) = ((y-1)/(y+1), sqrt(156324)*u/x)
(x, y) = (sqrt(156324)*u/v, (1+u)/(1-u))
Обе эти кривые 4-изогенны по отношению к кривой Эдвардса x^2 + y^2 = 1 + d*x^2*y^2 по имени edwards448, где:
p 2^448 - 2^224 - 1
d -39081
order 2^446 -
0x8335dc163bb124b65129c96fde933d8d723a70aadc873d6d54a7bb0d
cofactor 4
X(P) 224580040295924300187604334099896036246789641632564134246125461
686950415467406032909029192869357953282578032075146446173674602635
247710
Y(P) 298819210078481492676017930443930673437544040154080242095928241
372331506189835876003536878655418784733982303233503462500531545062
832660
4-изогенные сопоставления между кривыми Монтгомери и Эдвардса имеют вид:
(u, v) = (y^2/x^2, (2 - x^2 - y^2)*y/x^3)
(x, y) = (4*v*(u^2 - 1)/(u^4 - 2*u^2 + 4*v^2 + 1),
-(u^5 - 2*u^3 - 4*u*v^2 + u)/
(u^5 - 2*u^2*v^2 - 2*u^3 - 2*v^2 + u))
Заданная здесь кривая edwards448 называется также Goldilocks и эквивалентна одной из заданных в [goldilocks].
5. Функции X25519 и X448
Функции X25519 и X448 выполняют скалярное перемножение форм Монтгомери для указанных выше кривых (это применяется в реализации DH). Функции принимают в качестве входных данных скаляр и u-координату, давая в результате u-координату. Хотя внутри функций выполняются операции с целыми числами, на входе они получают строки размером 32 (X25519) или 56 (X448) байтов и спецификация задаёт кодирование таких строк.
Координаты u являются элементами базового поля GF(2^255 — 19) или GF(2^448 — 2^224 — 1) и кодируются как массив байтов u в таком порядке, что u[0] + 256*u[1] + 256^2*u[2] + … + 256^(n-1)*u[n-1] конгруэнтно значению по модулю p, а u[n-1] является минимальным. При получении такого массива реализация X25519 (но не X448) должна маскировать старший бит финального байта для совместимости с форматами точек, резервирующими бит знака для других протоколов, и повышения стойкости к получению оттисков реализаций (fingerprint).
Реализации должны воспринимать неканонические значения и обрабатывать их путём сокращения по модулю простого числа поля. Неканоническими являются значения от 2^255 — 19 до 2^255 — 1 для X25519 и от 2^448 — 2^224 — 1 до 2^448 — 1 для X448.
Ниже представлена реализация функций на языке Python, но она не обеспечивает высокой производительности и предотвращения побочных каналов. Параметр bits имеет значение 255 для X25519 и 448 для X448:
<CODE BEGINS>
def decodeLittleEndian(b, bits):
return sum([b[i] << 8*i for i in range((bits+7)/8)])
def decodeUCoordinate(u, bits):
u_list = [ord(b) for b in u]
# Ignore any unused bits.
if bits % 8:
u_list[-1] &= (1<<(bits%8))-1
return decodeLittleEndian(u_list, bits)
def encodeUCoordinate(u, bits):
u = u % p
return ''.join([chr((u >> 8*i) & 0xff)
for i in range((bits+7)/8)])
<CODE ENDS>
Скаляры считаются случайно сгенерированными байтами. Для X25519 при декодировании 32 случайных байтов в целочисленный скаляр сбрасываются (0) три младших бита первого байта и старший бит последнего, устанавливается (1) второй по старшинству бит последнего байта и результат декодируется как little-endian. Это означает, что полученное целое число имеет вид 2^254 плюс восемь значений из диапазона 0 — 2^251 — 1 (включительно). Для X448 сбрасываются (0) два младших бита первого байта и устанавливается (1) старший бит последнего байта. Результатом будет целое число в форме 2^447 плюс четыре значения из диапазона 0 — 2^445 — 1 (включительно).
<CODE BEGINS>
def decodeScalar25519(k):
k_list = [ord(b) for b in k]
k_list[0] &= 248
k_list[31] &= 127
k_list[31] |= 64
return decodeLittleEndian(k_list, 255)
def decodeScalar448(k):
k_list = [ord(b) for b in k]
k_list[0] &= 252
k_list[55] |= 128
return decodeLittleEndian(k_list, 448)
<CODE ENDS>
Для реализации функций X25519(k, u) и X448(k, u), где k — скаляр, u — u-координата, сначала декодируются k и u, затем выполняется показанная ниже процедура, взятая из [curve25519] и основанная на формулах из [montgomery]. Все расчёты выполняются в GF(p), т. е. по модулю p. Константа a24 имеет значение (486662 — 2) / 4 = 121665 для curve25519/X25519 и (156326 — 2) / 4 = 39081 для curve448/X448.
x_1 = u x_2 = 1 z_2 = 0 x_3 = u z_3 = 1 swap = 0
От t = bits-1 с уменьшением до 0 выполняются операции:
k_t = (k >> t) & 1
swap ^= k_t
// Условная перестановка, см. ниже.
(x_2, x_3) = cswap(swap, x_2, x_3)
(z_2, z_3) = cswap(swap, z_2, z_3)
swap = k_t
A = x_2 + z_2
AA = A^2
B = x_2 - z_2
BB = B^2
E = AA - BB
C = x_3 + z_3
D = x_3 - z_3
DA = D * A
CB = C * B
x_3 = (DA + CB)^2
z_3 = x_1 * (DA - CB)^2
x_2 = AA * BB
z_2 = E * (AA + a24 * E)
// Условная перестановка, см. ниже.
(x_2, x_3) = cswap(swap, x_2, x_3)
(z_2, z_3) = cswap(swap, z_2, z_3)
Return x_2 * (z_2^(p - 2))
Отметим, что эти формулы несколько отличаются от исходной статьи Монтгомери. Реализации могут применять любые корректные формулы.
Далее кодируется полученное значение как 32 или 56 байтов с порядком little-endian. Для X25519 неиспользуемый старший бит должен быть сброшен (0).
Для функции cswap следует обеспечить постоянное время выполнения (независимо от аргумента swap), например, как показано ниже.
cswap(swap, x_2, x_3):
dummy = mask(swap) AND (x_2 XOR x_3)
x_2 = x_2 XOR dummy
x_3 = x_3 XOR dummy
Return (x_2, x_3)
Здесь mask(swap) — слово, содержащее только 1 или только 0, с таким же размером, как x_2 и x_3, рассчитанное, например, как mask(swap) = 0 — swap.
5.1. Побочные каналы
Функции X25519 и X448 разработаны для упрощения быстрых реализаций с постоянным временем выполнения. Приведённая выше процедура обеспечивает для всех значений секретного ключа выполнение одинаковой последовательности операций, что устраняет базовый источник утечек по побочному каналу. Однако само по себе это не предотвращает использование побочных каналов. Важно, чтобы последовательность операций доступа к памяти и переходов не зависела от значений какого-либо из битов k. Также важно, чтобы применяемые арифметические операции не допускали утечки информации о целых числах по модулю p, например, из-за возможности отличить b*c от c*c. В некоторых архитектурах даже примитивы машинных инструкций, такие как деление с одним словом, могут выполняться за разное время в зависимости от входных данных.
Атаки по побочным каналам активно исследуются и разработчикам нужно внимательно следить за результатами таких исследований.
5.2. Тестовые векторы
Представлены два типа тестов. Сначала дана пара тестовых векторов для каждой функции, включая вывод для входных данных, указанных 64 или 112 шестнадцатеричными цифрами, которые перед обработкой нужно декодировать в строки из 32 или 56 байтов.
X25519:
Входной скаляр
a546e36bf0527c9d3b16154b82465edd62144c0ac1fc5a18506a2244ba449ac4
Входной скаляр как десятичное число
31029842492115040904895560451863089656
472772604678260265531221036453811406496
Входная u-координата
e6db6867583030db3594c1a424b15f7c726624ec26b3353b10a903a6d0ab1c4c
Входная u-координата как десятичное число
34426434033919594451155107781188821651
316167215306631574996226621102155684838
Выходная u-координата
c3da55379de9c6908e94ea4df28d084f32eccf03491c71f754b4075577a28552
Входной скаляр
4b66e9d4d1b4673c5ad22691957d6af5c11b6421e0ea01d42ca4169e7918ba0d
Входной скаляр как десятичное число
35156891815674817266734212754503633747
128614016119564763269015315466259359304
Входная u-координата
e5210f12786811d3f4b7959d0538ae2c31dbe7106fc03c3efc4cd549c715a493
Входная u-координата как десятичное число
88838573511839298940907593866106493194
17338800022198945255395922347792736741
Выходная u-координата
95cbde9476e8907d7aade45cb4b873f88b595a68799fa152e6f8f7647aac7957
X448:
Входной скаляр
3d262fddf9ec8e88495266fea19a34d28882acef045104d0d1aae121
700a779c984c24f8cdd78fbff44943eba368f54b29259a4f1c600ad3
Входной скаляр как десятичное число
599189175373896402783756016145213256157230856
085026129926891459468622403380588640249457727
683869421921443004045221642549886377526240828
Входная u-координата
06fce640fa3487bfda5f6cf2d5263f8aad88334cbd07437f020f08f9
814dc031ddbdc38c19c6da2583fa5429db94ada18aa7a7fb4ef8a086
Входная u-координата как десятичное число
382239910814107330116229961234899377031416365
240571325148346555922438025162094455820962429
142971339584360034337310079791515452463053830
Выходная u-координата
ce3e4ff95a60dc6697da1db1d85e6afbdf79b50a2412d7546d5f239f
e14fbaadeb445fc66a01b0779d98223961111e21766282f73dd96b6f
Входной скаляр
203d494428b8399352665ddca42f9de8fef600908e0d461cb021f8c5
38345dd77c3e4806e25f46d3315c44e0a5b4371282dd2c8d5be3095f
Входной скаляр как десятичное число
633254335906970592779259481534862372382525155
252028961056404001332122152890562527156973881
968934311400345568203929409663925541994577184
Входная u-координата
0fbcc2f993cd56d3305b0b7d9e55d4c1a8fb5dbb52f8e9a1e9b6201b
165d015894e56c4d3570bee52fe205e28a78b91cdfbde71ce8d157db
Входная u-координата как десятичное число
622761797758325444462922068431234180649590390
024811299761625153767228042600197997696167956
134770744996690267634159427999832340166786063
Выходная u-координата
884a02576239ff7a2f2f63b2db6a9ff37047ac13568e1e30fe63c4a7
ad1b3ee3a5700df34321d62077e63633c575c1c954514e99da7c179d
Второй тип тестовых векторов содержит результат вызова рассматриваемой функции указанное число раз. Исходно устанавливаются показанные ниже значения k и u.
X25519:
0900000000000000000000000000000000000000000000000000000000000000
X448:
05000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000
Для каждой итерации в k помещается результат функции, а в u — прежнее значение k. Финальный результат будет в k.
X25519:
После 1 итерации
422c8e7a6227d7bca1350b3e2bb7279f7897b87bb6854b783c60e80311ae3079
После 1000 итераций
684cf59ba83309552800ef566f2f4d3c1c3887c49360e3875f2eb94d99532c51
После 1000000 итераций
7c3911e0ab2586fd864497297e575e6f3bc601c0883c30df5f4dd2d24f665424
X448:
После 1 итерации
3f482c8a9f19b01e6c46ee9711d9dc14fd4bf67af30765c2ae2b846a
4d23a8cd0db897086239492caf350b51f833868b9bc2b3bca9cf4113
После 1000 итераций
aa3b4749d55b9daf1e5b00288826c467274ce3ebbdd5c17b975e09d4
af6c67cf10d087202db88286e2b79fceea3ec353ef54faa26e219f38
После 1000000 итераций
077f453681caca3693198420bbe515cae0002472519b3e67661a7e89
cab94695c8f4bcd66e61b9b9c946da8d524de3d69bd9d9d66b997e37
6. Обмен Диффи-Хеллмана
6.1. Curve25519
Ниже описано применение функции X25519 в протоколе Диффи-Хеллмана с эллиптической кривой (Elliptic Curve Diffie-Hellman или ECDH).
Алиса генерирует 32-байтовое случайное число в виде a[0] — a[31] и передаёт Бобу K_A = X25519(a, 9), где 9 — координата u базовой точки, представленная байтом со значением 9, за которым следует 31 байт нулей. Боб таким же способом генерирует 32 случайных байта b[0] — b[31], вычисляет K_B = X25519(b, 9) и передаёт значение Алисе. Используя созданное и полученное значение, Алиса рассчитывает X25519(a, K_B), а Боб — X25519(b, K_A). В результате у обоих будет общее значение K = X25519(a, X25519(b, 9)) = X25519(b, X25519(a, 9)), служащее секретом. Оба участника могут (без утечки K) убедиться, что K не содержит только нули и прервать процесс при нулевом значении (см. ниже). Затем Алиса и Боб используют функцию вывода симметричного ключа, включающую K, K_A, K_B.
Проверка отличия значения от нуля обусловлена тем, что функция X25519 выдаёт такое значение при входных данных, соответствующих точке с малым порядком, где порядок служит делителем сомножителя кривой (см. раздел 7). Проверку можно выполнить с помощью операции OR для всех байтов, что устраняет стандартные для программных реализаций побочные каналы. Результат проверки должен быть ненулевым.
Тестовые векторы
Секретный ключ Алисы a
77076d0a7318a57d3c16c17251b26645df4c2f87ebc0992ab177fba51db92c2a
Открытый ключ Алисы X25519(a, 9)
8520f0098930a754748b7ddcb43ef75a0dbf3a0d26381af4eba4a98eaa9b4e6a
Секретный ключ Боба b
5dab087e624a8a4b79e17f8b83800ee66f3bb1292618b6fd1c2f8b27ff88e0eb
Открытый ключ Боба X25519(b, 9)
de9edb7d7b7dc1b4d35b61c2ece435373f8343c85b78674dadfc7e146f882b4f
Общий секрет K
4a5d9d5ba4ce2de1728e3bf480350f25e07e21c947d19e3376f09b3c1e161742
6.2. Curve448
Функцию X448 можно применять протоколе ECDH похожим на использование X25519 способом. Единственным отличием является то, что Алиса и Боб генерируют 56 случайных байтов (а не 32) и рассчитывают K_A = X448(a, 5) и K_B = X448(b, 5), где 5 — координата u базовой точки, представленная байтом со значением 5 и 55 байтами нулей.
Как и в случае X25519, стороны могут проверить полученный секрет K без утечки его значения и прервать процесс при нулевом K.
Тестовый вектор
Секретный ключ Алисы a
9a8f4925d1519f5775cf46b04b5800d4ee9ee8bae8bc5565d498c28d
d9c9baf574a9419744897391006382a6f127ab1d9ac2d8c0a598726b
Открытый ключ Алисы X448(a, 5)
9b08f7cc31b7e3e67d22d5aea121074a273bd2b83de09c63faa73d2c
22c5d9bbc836647241d953d40c5b12da88120d53177f80e532c41fa0
Секретный ключ Боба b
1c306a7ac2a0e2e0990b294470cba339e6453772b075811d8fad0d1d
6927c120bb5ee8972b0d3e21374c9c921b09d1b0366f10b65173992d
Открытый ключ Боба X448(b, 5)
3eb7a829b0cd20f5bcfc0b599b6feccf6da4627107bdb0d4f345b430
27d8b972fc3e34fb4232a13ca706dcb57aec3dae07bdc1c67bf33609
Общий секрет K
07fff4181ac6cc95ec1c16a94a0f74d12da232ce40a77552281d282b
b60c0b56fd2464c335543936521c24403085d59a449a5037514a879d
7. Вопросы безопасности
Уровень безопасности (число «операций» требуемых для атаки на примитив методом перебора — brute-force) для кривой curve25519 несколько ниже стандартного 128-битового уровня. Это допустимо, поскольку стандартные уровни безопасности определяются в основном более простыми симметричными примитивами, где уровень безопасности, естественно является степенью 2. Для асимметричных примитивов жёсткое требование уровня безопасности в виде степени 2 требует компромиссов в других частях, которые здесь отвергаются. Кроме того, сравнение уровней безопасности для разнотипных примитивов может вводить в заблуждение в рамках распространённых моделей угроз, где одновременно может подвергаться атакам несколько целей [bruteforce].
Уровень безопасности curve448 около 224 битов — это компромисс между производительностью и паранойей. Большие квантовые компьютеры, если они будут созданы, смогут взломать как curve25519, так и curve448, а разумная оценка возможностей классических компьютеров позволяет считать curve25519 совершенно безопасной. Однако в некоторых решениях требования к производительности снижены в соответствии с желанием застраховаться от более эффективного анализа эллиптических кривых, поэтому предусмотрена также кривая curve448.
Разработчикам протоколов с использованием DH на основе эллиптических кривых, заданных в этом документе, недопустимо предполагать «совместное поведение», которое означает, в частности, что в создании общего ключа применяются секретные ключи обеих сторон. Поскольку кривые curve25519 и curve448 имеют сомножитель (cofactor) 8 и 4 (соответственно), входная точка с небольшим порядком исключит любое влияние использования секретного ключа второй стороны. Такую ситуацию можно обнаружить проверкой ненулевого значения общего ключа, которую реализации могут выполнять в соответствии с разделом 6. Однако многие имеющиеся реализации не делают этого.
Разработчикам, применяющим эти кривые, следует понимать, что для каждого открытого ключа существует несколько эквивалентных открытых ключей, которые можно вычислить, и эти ключи дадут такой же секрет. Таким образом, применение открытого ключа в качестве идентификатора и знание общего секрета как подтверждение владения (без включения открытых ключей в создание секрета) могут приводить к скрытым уязвимостям.
Разработчикам следует понимать, что реализации этих кривых могут не использовать «лестницу Монтгомери» (ladder), как указано в этом документе, а взамен применять базовые библиотеки эллиптических кривых. Такие реализации могут отвергать точки на скручивании (изгибе) и неминимальные элементы поля. Хотя это и не рекомендуется, такие реализации будут совместимы с заданной здесь лестницей Монтгомери, но их можно тривиально отличить. Например, отправка неканонического значения или точки на изгибе может привести к тому, что такая реализация создаст заметную ошибку, в то время, как соответствующие этому документу реализации будут успешно создавать общий ключ.
8. Литература
8.1. Нормативные документы
[RFC2119] Bradner, S., «Key words for use in RFCs to Indicate Requirement Levels», BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <http://www.rfc-editor.org/info/rfc2119>.
8.2. Дополнительная литература
[brainpool] ECC Brainpool, «ECC Brainpool Standard Curves and Curve Generation», October 2005, <http://www.ecc-brainpool.org/download/Domain-parameters.pdf>.
[bruteforce] Bernstein, D., «Understanding brute force», April 2005, <http://cr.yp.to/snuffle/bruteforce-20050425.pdf>.
[curve25519] Bernstein, D., «Curve25519: new Diffie-Hellman speed records», 2006, <http://www.iacr.org/cryptodb/archive/2006/PKC/3351/3351.pdf>.
[ed25519] Bernstein, D., Duif, N., Lange, T., Schwabe, P., and B. Yang, «High-Speed High-Security Signatures», 2011, <http://link.springer.com/chapter/10.1007/978-3-642-23951-9_9>.
[goldilocks] Hamburg, M., «Ed448-Goldilocks, a new elliptic curve», 2015, <http://eprint.iacr.org/2015/625.pdf>.
[montgomery] Montgomery, P., «Speeding the Pollard and Elliptic Curve Methods of Factorization», January 1987, <http://www.ams.org/journals/mcom/1987-48-177/S0025-5718-1987-0866113-7/S0025-5718-1987-0866113-7.pdf>.
[NIST] National Institute of Standards, «Recommended Elliptic Curves for Federal Government Use», July 1999, <http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf>.
[reducing] Menezes, A., Okamoto, T., and S. Vanstone, «Reducing elliptic curve logarithms to logarithms in a finite field», DOI 10.1109/18.259647, 1993, <http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=259647>.
[RFC6090] McGrew, D., Igoe, K., and M. Salter, «Fundamental Elliptic Curve Cryptography Algorithms», RFC 6090, DOI 10.17487/RFC6090, February 2011, <http://www.rfc-editor.org/info/rfc6090>.
[safecurves] Bernstein, D. and T. Lange, «SafeCurves: choosing safe curves for elliptic-curve cryptography», Oct 2013, <http://safecurves.cr.yp.to/>.
[satoh] Satoh, T. and K. Araki, «Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves», 1998.
[SEC1] Certicom Research, «SEC 1: Elliptic Curve Cryptography», September 2000, <http://www.secg.org/sec1-v2.pdf>.
[semaev] Semaev, I., «Evaluation of discrete logarithms on some elliptic curves», 1998, <http://www.ams.org/journals/mcom/1998-67-221/S0025-5718-98-00887-4/S0025-5718-98-00887-4.pdf>.
[smart] Smart, N., «The Discrete Logarithm Problem on Elliptic Curves of Trace One», 1999, <http://www.hpl.hp.com/techreports/97/HPL-97-128.pdf>.
Приложение A. Детерминированная генерация
В этом приложении описывается процедура, использованная для генерации описанных выше кривых. В частности, задан способ генерации параметра A кривой Монтгомери y^2 = x^3 + A*x^2 + x. Процедура должна быть как можно более объективной, чтобы было ясно, что никакие неблагоприятные факторы не повлияли на выбор кривой. Входными данными процесса является простое число p, определяющее базовое поле. Размер p определяет объем работы, требуемой для вычисления дискретного логарифма в группе эллиптической кривой и выбор точного значения p зависит от многих деталей реализации. Производительность для кривой будет зависеть в основном от операций в GF(p), поэтому важно тщательно выбирать значение, которое позволит легко выполнять сокращение в целевой архитектуре. Документ не пытается сформулировать эти соображения.
Значение (A-2)/4 применяется в нескольких арифметических формулах эллиптической кривой. Для простоты и производительности целесообразно выбирать эту константу небольшой, т. е. выбрать A так, чтобы значение (A-2) было небольшим целым числом, кратным 4.
Для каждой кривой на конкретном уровне безопасности имеется ряд условий.
-
Следу Фробениуса недопустимо находиться в {0, 1}, чтобы исключить атаки, описанные в [smart], [satoh] и [semaev], а также в [brainpool] и [safecurves].
-
Степень MOV Degree [reducing] — степень вложения должна быть больше (order — 1) / 100, как в [brainpool] и [safecurves].
-
Дискриминант CM — дискриминант D должен быть больше 2^100, как в [safecurves].
A.1. p = 1 mod 4
Для простых чисел, конгруэнтных 1 mod 4, минимальными сомножителями кривой и её скручивания (изгиба) являются {4, 8} или {8, 4}. Здесь выбран второй вариант, чтобы любым алгоритмам, учитывающим сомножитель, не приходилось проверять точки на изгибе, поскольку сомножитель изгиба окажется меньшим из двух.
Для генерации кривой Монтгомери находится минимальное положительное значение A такое, что A > 2 и (A-2) делится на 4 при желаемых сомножителях. Функция find1Mod4 в сценарии Sage возвращает значение для данного p.
<CODE BEGINS>
def findCurve(prime, curveCofactor, twistCofactor):
F = GF(prime)
for A in xrange(3, int(1e9)):
if (A-2) % 4 != 0:
continue
try:
E = EllipticCurve(F, [0, A, 0, 1, 0])
except:
continue
groupOrder = E.order()
twistOrder = 2*(prime+1)-groupOrder
if (groupOrder % curveCofactor == 0 and
is_prime(groupOrder // curveCofactor) and
twistOrder % twistCofactor == 0 and
is_prime(twistOrder // twistCofactor)):
return A
def find1Mod4(prime):
assert((prime % 4) == 1)
return findCurve(prime, 8, 4)
<CODE ENDS>
A.2. p = 3 mod 4
Для простого числа p, конгруэнтного 3 mod 4, сомножители кривой и скручивания могут иметь значение 4 и оно будет минимальным. Таким образом, выбирается кривая с такими сомножителями и минимальным положительным значением A таким, что A > 2 и (A-2) делится на 4. Функция find3Mod4 в приведённом ниже сценарии Sage возвращает такое значение для данного p
<CODE BEGINS>
def find3Mod4(prime):
assert((prime % 4) == 3)
return findCurve(prime, 4, 4)
<CODE ENDS>
A.3. Базовая точка
Базовой точкой кривой является точка с минимальным положительным значением u, находящаяся в корректной подгруппе. Функция findBasepoint в приведённом ниже сценарии Sage возвращает это значение для данных p и A
<CODE BEGINS>
def findBasepoint(prime, A):
F = GF(prime)
E = EllipticCurve(F, [0, A, 0, 1, 0])
for uInt in range(1, 1e3):
u = F(uInt)
v2 = u^3 + A*u^2 + u
if not v2.is_square():
continue
v = v2.sqrt()
point = E(u, v)
pointOrder = point.order()
if pointOrder > 8 and pointOrder.is_prime():
return point
<CODE ENDS>
Благодарности
Этот документ является результатом объединения draft-black-rpgecc-01 и draft-turner-thecurve25519function-01. Benjamin Black, Joppe W. Bos, Craig Costello, Patrick Longa, Michael Naehrig, Watson Ladd, Rich Salz подготовили большую часть текста и рисунков, но не указаны в числе авторов этого документа.
Авторы благодарны Tanja Lange, Rene Struik, Rich Salz, Ilari Liusvaara, Deirdre Connolly, Simon Josefsson, Stephen Farrell, Georg Nestmann, Trevor Perrin, John Mattsson за их рецензии и вклад.
Функция X25519 разработана Daniel J. Bernstein в [curve25519].
Адреса авторов
Adam Langley
345 Spear Street
San Francisco, CA 94105
United States
Email: agl@google.com
Mike Hamburg
Rambus Cryptography Research
425 Market Street, 11th Floor
San Francisco, CA 94105
United States
Email: mike@shiftleft.org
Sean Turner
sn3rd
Email: sean@sn3rd.com
Перевод на русский язык
Николай Малых
1Internet Research Task Force — комиссия по исследованиям Internet.
2Internet Research Steering Group — руководящая группа по исследовательским разработкам Internet.