1ec.h(3) Library Functions Manual ec.h(3)
2
6 ec.h - Эллиптические кривые
7
10 #include 'bee2/math/qr.h'
11 Классы
14 struct ec_o
15 Описание эллиптической кривой
16 Определения типов
18 typedef bool_t(* ec_froma_i) (word b[], const word a[], const struct
19 ec_o *ec, void *stack)
20 Импорт из аффинной точки
21 typedef bool_t(* ec_toa_i) (word b[], const word a[], const struct ec_o
22 *ec, void *stack)
23 Экспорт в аффинную точку
24 typedef void(* ec_neg_i) (word b[], const word a[], const struct ec_o
25 *ec, void *stack)
26 Обратная точка
27 typedef void(* ec_add_i) (word c[], const word a[], const word b[],
28 const struct ec_o *ec, void *stack)
29 Сложение точек
30 typedef void(* ec_adda_i) (word c[], const word a[], const word b[],
31 const struct ec_o *ec, void *stack)
32 Сложение с аффинной точкой
33 typedef void(* ec_sub_i) (word c[], const word a[], const word b[],
34 const struct ec_o *ec, void *stack)
35 Вычитание точек
36 typedef void(* ec_suba_i) (word c[], const word a[], const word b[],
37 const struct ec_o *ec, void *stack)
38 Вычитание аффинной точки
39 typedef void(* ec_dbl_i) (word b[], const word a[], const struct ec_o
40 *ec, void *stack)
41 Удвоение точки
42 typedef void(* ec_dbla_i) (word b[], const word a[], const struct ec_o
43 *ec, void *stack)
44 Удвоение аффинной точки
45 typedef void(* ec_tpl_i) (word b[], const word a[], const struct ec_o
46 *ec, void *stack)
47 Утроение точки
48 typedef struct ec_o ec_o
49 Описание эллиптической кривой
50 Функции
52 bool_t ecIsOperable (const ec_o *ec)
53 Описание эллиптической кривой работоспособно?
54 bool_t ecIsOperable2 (const ec_o *ec)
55 Описание отдельной эллиптической кривой работоспособно?
56 bool_t ecCreateGroup (ec_o *ec, const octet xbase[], const octet
57 ybase[], const octet order[], size_t order_len, u32 cofactor, void
58 *stack)
59 Создание группы точек эллиптической кривой
60 bool_t ecIsOperableGroup (const ec_o *ec)
61 Группа точек эллиптической кривой работоспособна?
62 bool_t ecMulA (word b[], const word a[], const ec_o *ec, const word
63 d[], size_t m, void *stack)
64 Кратная точка
65 bool_t ecHasOrderA (const word a[], const ec_o *ec, const word q[],
66 size_t m, void *stack)
67 Имеет порядок?
68 bool_t ecAddMulA (word b[], const ec_o *ec, void *stack, size_t k,...)
69 Сумма кратных точек
70
72 Определяются вычисления на эллиптических кривых над конечными полями.
73 Поле представляется как кольцо вычетов с помощью структуры типа qr_o
74 (см. заголовочный файл qr.h). Описание кривой соответствует соглашениям
75 ANSI X 9.62 (ECDSA) и последующих стандартов.
76 Эллиптическая кривая описывается структурой типа ec_o. Пусть ec --
78 указатель на такую структуру. Тогда ec->f указывает на описание
79 базового поля, ec->A и ec->B --- коэффициенты из базового поля, которые
80 определяют уравнение эллиптической кривой.
81 В описание ec->f базового поля включается функции арифметики в этом
83 поле. Описание должно быть настроено вызывающей программой (см.
84 описание qrCreate() в qr.h).
85 Используется внутреннее (для ec->f) представление элементов базового
87 поля. Импорт элементов базового поля из строк октетов выполняется с
88 помощью функции ec->f->from(), экспорт -- с помощью функции
89 ec->f->to(). Можно также использовать макросы qrFrom, qrTo (см.
90 заголовочный файл qr.h).
91 Точка эллиптической кривой задается ec->d координатами из базового
93 поля. Каждая координата представляется ec->f->n машинными словами.
94 Координаты записываются друг за другом и в целом образуют массив pt из
95 ec->d * ec->f->n машинных слов. Первые три координаты именованные: X,
96 Y, Z. Макросы ecX, ecY, ecZ поддерживают извлечение именованных
97 координат из буфера pt.
98 Точки с двумя координатами называются аффинными, а точки pt = (X : Y :
100 Z :...) с тремя и более координатами -- проективными. Бесконечно
101 удаленную точку O нельзя представить аффинной, но можно проективной:
102 точке O соответствует точка pt, у которой Z == 0. Макросы ecSetO, ecIsO
103 выполняют присваивание pt = O и проверку pt == O.
104 Для организации вычислений требуется, чтобы среди точек эллиптической
106 кривой имелась бесконечно удаленная. Поэтому должны обязательно
107 использоваться проективные координаты (проективные точки). Размерность
108 ec->d >= 3.
109 Проективную точку можно построить по аффинной точке (x, y) с помощью
111 функции интерфейса ec_froma_i. Как правило, построение состоит в
112 присваиваниях
113 X <- x, Y <- y, Z <- ec->f->unity,....
115 Обратно, проективную точку можно преобразовать в аффинную с помощью
118 функции интерфейса ec_toa_i (при преобразовании бесконечно удаленной
119 точки функция возвращает соответствующий признак).
120 Описание ec может быть использовано для организации вычислений в
122 аффинных координатах, несмотря на заданные этим описанием проективные.
123 Прим.
125 Если используется ec->d == 3, то Z-координата точки pt всегда
126 равняется единице для pt != O и нулю для pt == O, то вычисления на
127 кривой фактически ведутся в аффинных координатах.
128 В структуре типа ec_o предусмотрены поля для описания циклической
130 группы точек эллиптической кривой. Эта группа задается образующим
131 ec->base. Образующий представляется аффинной точкой, т.е. задается 2 *
132 ec->f->n машинными словами. Порядок циклической группы ec->order
133 задается 2 * ec->f->n + 1 машинным словом. Кофактор -- отношение числа
134 всех ec->f-рациональных точек к ec->order -- задается одним машинным
135 словом ec->cofactor.
136 Если работа с группой точек не предусматривается, то поля base, order и
138 cofactor могут не задаваться.
139 По адресу ec->params могут размещаться дополнительные данные, например,
141 определенные кратные базовой точки, с помощью которых можно ускорить
142 криптографические вычисления на эллиптической кривой.
143 Описание ec эллиптической кривой включает указатели на функции
145 арифметики в группе точек этой кривой. Функцию интерфейса ec_tpl_i
146 можно не поддерживать. Указатель на неподдерживаемую функцию должен
147 быть нулевым.
148 Описание кольца организовано как объект, и можно применять функции,
150 описанные в заголовочном файле obj.h.
151 Эллиптическая кривая должна создаваться специальной функцией
153 ecCreate(), которая является аналогом конструктора. В эту функцию
154 должен передаваться указатель ec на структуру типа ec_o. По этому
155 указателю будет размещаться описание (состояние) кривой. По адресу ec
156 может быть зарезервировано больше памяти, чем sizeof(ec_o). Дело в том,
157 что коэффициенты A, B, порядок order, базовая точка base могут
158 размещаться в поле descr открытого размера. Функция ecCreate() должна
159 сопровождаться функцией ecCreate_keep(), которая поддерживает расчет
160 длины состояния (в октетах).
161 Функция ecCreate_keep() должна оценивать длину состояния сверху. Оценка
163 может быть неточной. Точная длина состояния фиксируется при
164 непосредственном выполнении ecCreate() и сохраняется в поле keep
165 описания кривой.
166 В функцию ecCreate() должен передаваться указатель на память для стека.
168 Функция ecCreate() должна сопровождаться функцией ecCreate_deep(),
169 которая выполняет расчет глубины стека. При расчете глубины следует
170 предполагать, что в ecCreate() явно или неявно вызываются все функции
171 интерфейсов кривой. Получив результат работы ecCreate_deep(), внешние
172 программы могут определить, сколько вспомогательной памяти потребуется
173 при всевозможных способах работы с функциями арифметики на кривой.
174 Оценка глубины стека, определяемая функцией ecCreate_deep(), может быть
176 неточной. Точная глубина фиксируется при непосредственном выполнении
177 ecCreate() и сохраняется в поле deep описания кривой.
178 В функцию ecCreate() могут не передаваться параметры base, order и
180 cofactor, определяющие строение группы точек, хотя буферы для base и
181 order могут подготавливаться в ecCreate(). Параметры могут
182 устанавливаться позднее с помощью функции ecCreateGroup().
183 Предусловие
185 Все указатели действительны.
186 Буферы точек кривой не пересекаются с буферами, поддерживающими
188 описание эллиптической кривой.
189
191 typedef void(* ec_add_i) (word c[], const word a[], const word b[], const
192 struct ec_o *ec, void *stack)
193 На эллиптической кривой ec определяется сумма [ec->d * ec->f->n]c точек
194 [ec->d * ec->f->n]a и [ec->d * ec->f->n]b:
195 c <- a + b.
197 Предусловие
200 Описание ec работоспособно.
201 Буфер с либо не пересекается с каждым из буферов a и b, либо
203 совпадает с некоторым из них.
204 Координаты a и b лежат в базовом поле.
206 Ожидается
208 Описание ec корректно.
209 Ожидается
211 Точки a и b лежат на кривой.
212 Аргументы
214 c сумма
215 a первое слагаемое
216 b второе слагаемое
217 ec описание эллиптической кривой
218 stack вспомогательная память
219 typedef void(* ec_adda_i) (word c[], const word a[], const word b[], const
221 struct ec_o *ec, void *stack)
222 На эллиптической кривой ec определяется сумма [ec->d * ec->f->n]c
223 проективной точки [ec->d * ec->f->n]a и аффинной точки [2 * ec->f->n]b:
224 c <- a + b.
226 Предусловие
229 Описание ec работоспособно.
230 Буфер с либо не пересекается с каждым из буферов a и b, либо
232 указатель c совпадает с некоторым из указателей a или b.
233 Координаты a и b лежат в базовом поле.
235 Ожидается
237 Описание ec корректно.
238 Ожидается
240 Точки a и b лежат на кривой.
241 Аргументы
243 c сумма
244 a первое слагаемое
245 b второе слагаемое
246 ec описание эллиптической кривой
247 stack вспомогательная память
248 typedef void(* ec_dbl_i) (word b[], const word a[], const struct ec_o *ec,
250 void *stack)
251 На эллиптической кривой ec определяется точка [ec->d * ec->f->n]b,
252 полученная удвоением точки [ec->d * ec->f->n]a:
253 b <- 2 a.
255 Предусловие
258 Описание ec работоспособно.
259 Буфер b либо не пересекается, либо совпадает с буфером a.
261 Координаты a лежат в базовом поле.
263 Ожидается
265 Описание ec корректно.
266 Ожидается
268 Точка a лежит на кривой.
269 Аргументы
271 b удвоенная точка
272 a первоначальная точка
273 ec описание эллиптической кривой
274 stack вспомогательная память
275 typedef void(* ec_dbla_i) (word b[], const word a[], const struct ec_o *ec,
277 void *stack)
278 На эллиптической кривой ec определяется проективная точка [ec->d *
279 ec->f->n]b, полученная удвоением аффинной точки [2 * ec->f->n]a:
280 b <- 2 a.
282 Предусловие
285 Описание ec работоспособно.
286 Буферы a и b либо не пересекаются, либо указатели a и b совпадают.
288 Координаты a лежат в базовом поле.
290 Ожидается
292 Описание ec корректно.
293 Ожидается
295 Точка a лежит на кривой.
296 Аргументы
298 b удвоенная точка
299 a первоначальная точка
300 ec описание эллиптической кривой
301 stack вспомогательная память
302 typedef bool_t(* ec_froma_i) (word b[], const word a[], const struct ec_o
304 *ec, void *stack)
305 По аффинной точке [2 * ec->f->n]a эллиптической кривой ec строится
306 точка [ec->d * ec->f->n]b.
307 Предусловие
309 Описание ec работоспособно.
310 Буферы a и b либо не пересекаются, либо указатели a и b совпадают.
312 Координаты a лежат в базовом поле.
314 Ожидается
316 Описание ec корректно.
317 Ожидается
319 Точка a лежит на кривой.
320 Возвращает
322 TRUE, если преобразование успешно выполнено, и FALSE в противном
323 случае.
324 Аргументы
326 b выходная точка
327 a аффинная точка
328 ec описание эллиптической кривой
329 stack вспомогательная память
330 typedef void(* ec_neg_i) (word b[], const word a[], const struct ec_o *ec,
332 void *stack)
333 На эллиптической кривой ec определяется точка [ec->d * ec->f->n]b,
334 обратная к точке [ec->d * ec->f->n]a:
335 b <- -a.
337 Предусловие
340 Описание ec работоспособно.
341 Буфер b либо не пересекается, либо совпадает с буфером a.
343 Координаты a лежат в базовом поле.
345 Ожидается
347 Описание ec корректно.
348 Ожидается
350 Точка a лежит на кривой.
351 Аргументы
353 b обратная точка
354 a обращаемая точка
355 ec описание эллиптической кривой
356 stack вспомогательная память
357 typedef struct ec_o ec_o
359 Описывается эллиптическая кривая, правила представления ее элементов,
360 группа точек и функции, реализующие операции в группе.
361 Прим.
363 В таблицу указателей описания кривой как объекта входят поля f, A,
364 B, base, order, params. Поле f является указателем на объект.
365 typedef void(* ec_sub_i) (word c[], const word a[], const word b[], const
367 struct ec_o *ec, void *stack)
368 На эллиптической кривой ec определяется разность [ec->d * ec->f->n]c
369 точек [ec->d * ec->f->n]a и [ec->d * ec->f->n]b:
370 c <- a - b.
372 Предусловие
375 Описание ec работоспособно.
376 Буфер с либо не пересекается с каждым из буферов a и b, либо
378 совпадает с некоторым из них.
379 Координаты a и b лежат в базовом поле.
381 Ожидается
383 Описание ec корректно.
384 Ожидается
386 Точки a и b лежат на кривой.
387 Аргументы
389 c разность
390 a уменьшаемое
391 b вычитаемое
392 ec описание эллиптической кривой
393 stack вспомогательная память
394 typedef void(* ec_suba_i) (word c[], const word a[], const word b[], const
396 struct ec_o *ec, void *stack)
397 На эллиптической кривой ec определяется разность [ec->d * ec->f->n]c
398 проективной точки [ec->d * ec->f->n]a и аффинной точки [2 * ec->f->n]b:
399 c <- a - b.
401 Предусловие
404 Описание ec работоспособно.
405 Буфер с либо не пересекается с каждым из буферов a и b, либо
407 указатель c совпадает с некоторым из указателей a или b.
408 Координаты a и b лежат в базовом поле.
410 Ожидается
412 Описание ec корректно.
413 Ожидается
415 Точки a и b лежат на кривой.
416 Аргументы
418 c разность
419 a уменьшаемое
420 b вычитаемое
421 ec описание эллиптической кривой
422 stack вспомогательная память
423 typedef bool_t(* ec_toa_i) (word b[], const word a[], const struct ec_o
425 *ec, void *stack)
426 По точке [ec->d * ec->f->n]a эллиптической кривой ec строится аффинная
427 точка [2 * ec->f->n]b.
428 Предусловие
430 Описание ec работоспособно.
431 Буферы a и b либо не пересекаются, либо указатели a и b совпадают.
433 Координаты a лежат в базовом поле.
435 Ожидается
437 Описание ec корректно.
438 Ожидается
440 Точка a лежит на кривой.
441 Возвращает
443 TRUE, если аффинная точка построена, и FALSE, если точке a
444 соответствует бесконечно удаленная точка.
445 Аргументы
447 b аффинная точка
448 a входная точка
449 ec описание эллиптической кривой
450 stack вспомогательная память
451 typedef void(* ec_tpl_i) (word b[], const word a[], const struct ec_o *ec,
453 void *stack)
454 На эллиптической кривой ec определяется точка [ec->d * ec->f->n]b,
455 полученная утроением точки [ec->d * ec->f->n]a:
456 b <- 3 a.
458 Предусловие
461 Описание ec работоспособно.
462 Буфер b либо не пересекается, либо совпадает с буфером a.
464 Координаты a лежат в базовом поле.
466 Ожидается
468 Описание ec корректно.
469 Ожидается
471 Точка a лежит на кривой.
472 Аргументы
474 b утроенная точка
475 a первоначальная точка
476 ec описание эллиптической кривой
477 stack вспомогательная память
478
480 bool_t ecAddMulA (word b[], const ec_o * ec, void * stack, size_t k, ...)
481 Определяется точка [2n]b эллиптической кривой ec, которая является
482 суммой [m[i]]d[i]-кратных точек [2n]a[i], i = 1, 2,.., k:
483 b <- d[1] a[1] + d[2] a[2] + ... + d[k] a[k].
485 Тройки a[i], d[i], m[i] передаются как дополнительные параметры типов
488 const word[], const word[], size_t соответственно.
489 Предусловие
491 Описание ec работоспособно.
492 k > 0.
494 Координаты точек a[1], a[2],..., a[k] лежат в базовом поле.
496 Ожидается
498 Описание ec корректно.
499 Ожидается
501 Точки a[1], a[2],..., a[k] лежат на ec.
502 Возвращает
504 TRUE, если полученная точка является аффинной, и FALSE в противном
505 случае (b == O).
506 Схема расчета глубины stack
508 ecAddMulA_deep(ec->f->n, ec->d, ec->deep, m[1], ..., m[k]).
509 Аргументы
511 b кратная точка
512 ec описание кривой
513 stack вспомогательная память
514 k число троек (a[i], d[i], m[i])
515 ... тройки (a[i], d[i], m[i])
516 bool_t ecCreateGroup (ec_o * ec, const octet xbase[], const octet ybase[],
518 const octet order[], size_t order_len, u32 cofactor, void * stack)
519 В описание ec эллиптической кривой добавляется описание группы,
520 порожденной точкой ([ec->f->no]xbase, [ec->f->no]ybase). Группа имеет
521 порядок [order_len]order и ее кофактор равняется cofactor.
522 Предусловие
524 Описание ec работоспособно.
525 Буферы [2 * ec->f->n]ec->base, [ec->f->n + 1]ec->order корректны.
527 Ожидается [FALSE]
529 Число [octet_len]octet укладывается в ec->f->n + 1 машинных слов.
530 Ожидается [FALSE]
532 cofactor != 0 && cofactor укладывается в машинное слово.
533 Ожидается
535 Описание ec корректно.
536 Возвращает
538 TRUE, если описание группы успешно задано, и FALSE в противном
539 случае.
540 Прим.
542 Любой из указателей xbase, ybase может быть нулевым. При нулевом
543 указателе соответствующая координата базовой точки устанавливается
544 равной нулю.
545 Схема расчета глубины stack
547 ecCreateGroup_deep(f_deep).
548 Аргументы
550 ec описание кривой
551 xbase x-координата базовой точки
552 ybase y-координата базовой точки
553 order порядок группы точек
554 order_len длина order
555 cofactor кофактор группы точек
556 stack вспомогательная память
557 bool_t ecHasOrderA (const word a[], const ec_o * ec, const word q[], size_t
559 m, void * stack)
560 Проверяется, что аффинная точка [2 * ec->f->n]a имеет порядок [m]q в
561 группе точек кривой ec.
562 Предусловие
564 Описание ec работоспособно.
565 Координаты a лежат в базовом поле.
567 q > 0.
569 Ожидается
571 Описание ec корректно.
572 Ожидается
574 Точка a лежит на ec.
575 Ожидается
577 Число q -- простое. Если q -- составное, то точка порядка q1 | q
578 может быть ошибочно признана точкой порядка q.
579 Возвращает
581 Признак успеха проверки.
582 Схема расчета глубины stack
584 ecpHasOrderA_deep(ec->f->n, ec->d, ec->f->deep, m).
585 Аргументы
587 a точка
588 ec описание кривой
589 q порядок
590 m длина q в машинных словах
591 stack вспомогательная память
592 bool_t ecIsOperable (const ec_o * ec)
594 Проверяется работоспособность описания ec эллиптической кривой.
595 Проверяются следующие условия:
596 • объект ec работоспособен;
598 • objKeep(ec) >= sizeof(ec_o);
600 • objPCount(ec) == 6 && objOCount(ec) == 1;
602 • ec->d >= 3;
604 • qrIsOperable(ec->f) == TRUE;
606 • буферы [ec->n]ec->A, [ec->n]ec->B корректны;
608 • указатели ec->froma, r->toa, ..., r->dbla корректны;
610 • ec->deep >= ec->f->deep.
612 Возвращает
614 Признак корректности.
615 Прим.
617 Поля ec->base, ec->order и ec->cofactor, описывающие группу точек,
618 не контролируются.
619 Аргументы
621 ec описание кривой
622 bool_t ecIsOperable2 (const ec_o * ec)
624 Проверяется работоспособность описания ec эллиптической кривой без
625 учета ссылочного описания базового поля. Проверяются следующие условия:
626 • объект ec работоспособен;
628 • objKeep(ec) >= sizeof(ec_o);
630 • objPCount(ec) == 6 && objOCount(ec) == 1;
632 • ec->d >= 3;
634 • буферы [ec->n]ec->A, [ec->n]ec->B корректны;
636 • указатели ec->froma, r->toa, ..., r->dbla корректны.
638 Возвращает
640 Признак корректности.
641 Прим.
643 Поля ec->base, ec->order и ec->cofactor, описывающие группу точек,
644 не контролируются.
645 Аргументы
647 ec описание кривой
648 bool_t ecIsOperableGroup (const ec_o * ec)
650 Проверяется работоспособность описания группы точек эллиптической
651 кривой ec. Проверяются следующие условия:
652 • буферы [ec->n + 1]ec->order, [2 * ec->n]ec->base корректны;
654 • ec->order != 0;
656 • cofactor != 0.
658 Предусловие
660 Описание ec работоспособно.
661 Возвращает
663 Признак корректности.
664 Аргументы
666 ec описание кривой
667 bool_t ecMulA (word b[], const word a[], const ec_o * ec, const word d[],
669 size_t m, void * stack)
670 Определяется аффинная точка [2 * ec->f->n]b эллиптической кривой ec,
671 которая является [m]d-кратной аффинной точки [2 * ec->f->n]a:
672 b <- d a.
674 Предусловие
677 Описание ec работоспособно.
678 Координаты a лежат в базовом поле.
680 Ожидается
682 Описание ec корректно.
683 Ожидается
685 Точка a лежит на ec.
686 Возвращает
688 TRUE, если кратная точка является аффинной, и FALSE в противном
689 случае (b == O).
690 Схема расчета глубины stack
692 ecpMulA_deep(ec->f->n, ec->d, ec->f->deep, m).
693 Аргументы
695 b кратная точка
696 a базовая точка
697 ec описание кривой
698 d кратность
699 m длина d в машинных словах
700 stack вспомогательная память
701
703 Автоматически создано Doxygen для Библиотека Bee2 из исходного текста.
704Библиотека Bee2 Пт 23 Июн 2023 ec.h(3)