ec.h - Man Page
Эллиптические кривые
Synopsis
#include 'bee2/math/qr.h'
Классы
struct ec_o
Описание эллиптической кривой
Определения типов
typedef bool_t(* ec_froma_i) (word b[], const word a[], const struct ec_o *ec, void *stack)
Импорт из аффинной точки
typedef bool_t(* ec_toa_i) (word b[], const word a[], const struct ec_o *ec, void *stack)
Экспорт в аффинную точку
typedef void(* ec_neg_i) (word b[], const word a[], const struct ec_o *ec, void *stack)
Обратная точка
typedef void(* ec_add_i) (word c[], const word a[], const word b[], const struct ec_o *ec, void *stack)
Сложение точек
typedef void(* ec_adda_i) (word c[], const word a[], const word b[], const struct ec_o *ec, void *stack)
Сложение с аффинной точкой
typedef void(* ec_sub_i) (word c[], const word a[], const word b[], const struct ec_o *ec, void *stack)
Вычитание точек
typedef void(* ec_suba_i) (word c[], const word a[], const word b[], const struct ec_o *ec, void *stack)
Вычитание аффинной точки
typedef void(* ec_dbl_i) (word b[], const word a[], const struct ec_o *ec, void *stack)
Удвоение точки
typedef void(* ec_dbla_i) (word b[], const word a[], const struct ec_o *ec, void *stack)
Удвоение аффинной точки
typedef void(* ec_tpl_i) (word b[], const word a[], const struct ec_o *ec, void *stack)
Утроение точки
typedef struct ec_o ec_o
Описание эллиптической кривой
Функции
bool_t ecIsOperable (const ec_o *ec)
Описание эллиптической кривой работоспособно?
bool_t ecIsOperable2 (const ec_o *ec)
Описание отдельной эллиптической кривой работоспособно?
bool_t ecCreateGroup (ec_o *ec, const octet xbase[], const octet ybase[], const octet order[], size_t order_len, u32 cofactor, void *stack)
Создание группы точек эллиптической кривой
bool_t ecIsOperableGroup (const ec_o *ec)
Группа точек эллиптической кривой работоспособна?
bool_t ecMulA (word b[], const word a[], const ec_o *ec, const word d[], size_t m, void *stack)
Кратная точка
bool_t ecHasOrderA (const word a[], const ec_o *ec, const word q[], size_t m, void *stack)
Имеет порядок?
bool_t ecAddMulA (word b[], const ec_o *ec, void *stack, size_t k,...)
Сумма кратных точек
Подробное описание
Определяются вычисления на эллиптических кривых над конечными полями. Поле представляется как кольцо вычетов с помощью структуры типа qr_o (см. заголовочный файл qr.h). Описание кривой соответствует соглашениям ANSI X 9.62 (ECDSA) и последующих стандартов.
Эллиптическая кривая описывается структурой типа ec_o. Пусть ec -- указатель на такую структуру. Тогда ec->f указывает на описание базового поля, ec->A и ec->B --- коэффициенты из базового поля, которые определяют уравнение эллиптической кривой.
В описание ec->f базового поля включается функции арифметики в этом поле. Описание должно быть настроено вызывающей программой (см. описание qrCreate() в qr.h).
Используется внутреннее (для ec->f) представление элементов базового поля. Импорт элементов базового поля из строк октетов выполняется с помощью функции ec->f->from(), экспорт -- с помощью функции ec->f->to(). Можно также использовать макросы qrFrom, qrTo (см. заголовочный файл qr.h).
Точка эллиптической кривой задается ec->d координатами из базового поля. Каждая координата представляется ec->f->n машинными словами. Координаты записываются друг за другом и в целом образуют массив pt из ec->d * ec->f->n машинных слов. Первые три координаты именованные: X, Y, Z. Макросы ecX, ecY, ecZ поддерживают извлечение именованных координат из буфера pt.
Точки с двумя координатами называются аффинными, а точки pt = (X : Y : Z :...) с тремя и более координатами -- проективными. Бесконечно удаленную точку O нельзя представить аффинной, но можно проективной: точке O соответствует точка pt, у которой Z == 0. Макросы ecSetO, ecIsO выполняют присваивание pt = O и проверку pt == O.
Для организации вычислений требуется, чтобы среди точек эллиптической кривой имелась бесконечно удаленная. Поэтому должны обязательно использоваться проективные координаты (проективные точки). Размерность ec->d >= 3.
Проективную точку можно построить по аффинной точке (x, y) с помощью функции интерфейса ec_froma_i. Как правило, построение состоит в присваиваниях
X <- x, Y <- y, Z <- ec->f->unity,....
Обратно, проективную точку можно преобразовать в аффинную с помощью функции интерфейса ec_toa_i (при преобразовании бесконечно удаленной точки функция возвращает соответствующий признак).
Описание ec может быть использовано для организации вычислений в аффинных координатах, несмотря на заданные этим описанием проективные.
Прим.
Если используется ec->d == 3, то Z-координата точки pt всегда равняется единице для pt != O и нулю для pt == O, то вычисления на кривой фактически ведутся в аффинных координатах.
В структуре типа ec_o предусмотрены поля для описания циклической группы точек эллиптической кривой. Эта группа задается образующим ec->base. Образующий представляется аффинной точкой, т.е. задается 2 * ec->f->n машинными словами. Порядок циклической группы ec->order задается 2 * ec->f->n + 1 машинным словом. Кофактор -- отношение числа всех ec->f-рациональных точек к ec->order -- задается одним машинным словом ec->cofactor.
Если работа с группой точек не предусматривается, то поля base, order и cofactor могут не задаваться.
По адресу ec->params могут размещаться дополнительные данные, например, определенные кратные базовой точки, с помощью которых можно ускорить криптографические вычисления на эллиптической кривой.
Описание ec эллиптической кривой включает указатели на функции арифметики в группе точек этой кривой. Функцию интерфейса ec_tpl_i можно не поддерживать. Указатель на неподдерживаемую функцию должен быть нулевым.
Описание кольца организовано как объект, и можно применять функции, описанные в заголовочном файле obj.h.
Эллиптическая кривая должна создаваться специальной функцией ecCreate(), которая является аналогом конструктора. В эту функцию должен передаваться указатель ec на структуру типа ec_o. По этому указателю будет размещаться описание (состояние) кривой. По адресу ec может быть зарезервировано больше памяти, чем sizeof(ec_o). Дело в том, что коэффициенты A, B, порядок order, базовая точка base могут размещаться в поле descr открытого размера. Функция ecCreate() должна сопровождаться функцией ecCreate_keep(), которая поддерживает расчет длины состояния (в октетах).
Функция ecCreate_keep() должна оценивать длину состояния сверху. Оценка может быть неточной. Точная длина состояния фиксируется при непосредственном выполнении ecCreate() и сохраняется в поле keep описания кривой.
В функцию ecCreate() должен передаваться указатель на память для стека. Функция ecCreate() должна сопровождаться функцией ecCreate_deep(), которая выполняет расчет глубины стека. При расчете глубины следует предполагать, что в ecCreate() явно или неявно вызываются все функции интерфейсов кривой. Получив результат работы ecCreate_deep(), внешние программы могут определить, сколько вспомогательной памяти потребуется при всевозможных способах работы с функциями арифметики на кривой.
Оценка глубины стека, определяемая функцией ecCreate_deep(), может быть неточной. Точная глубина фиксируется при непосредственном выполнении ecCreate() и сохраняется в поле deep описания кривой.
В функцию ecCreate() могут не передаваться параметры base, order и cofactor, определяющие строение группы точек, хотя буферы для base и order могут подготавливаться в ecCreate(). Параметры могут устанавливаться позднее с помощью функции ecCreateGroup().
Предусловие
Все указатели действительны.
Буферы точек кривой не пересекаются с буферами, поддерживающими описание эллиптической кривой.
Типы
typedef void(* ec_add_i) (word c[], const word a[], const word b[], const struct ec_o *ec, void *stack)
На эллиптической кривой ec определяется сумма [ec->d * ec->f->n]c точек [ec->d * ec->f->n]a и [ec->d * ec->f->n]b:
c <- a + b.
Предусловие
Описание ec работоспособно.
Буфер с либо не пересекается с каждым из буферов a и b, либо совпадает с некоторым из них.
Координаты a и b лежат в базовом поле.
Ожидается
Описание ec корректно.
Ожидается
Точки a и b лежат на кривой.
- Аргументы
c сумма
a первое слагаемое
b второе слагаемое
ec описание эллиптической кривой
stack вспомогательная память
typedef void(* ec_adda_i) (word c[], const word a[], const word b[], const struct ec_o *ec, void *stack)
На эллиптической кривой ec определяется сумма [ec->d * ec->f->n]c проективной точки [ec->d * ec->f->n]a и аффинной точки [2 * ec->f->n]b:
c <- a + b.
Предусловие
Описание ec работоспособно.
Буфер с либо не пересекается с каждым из буферов a и b, либо указатель c совпадает с некоторым из указателей a или b.
Координаты a и b лежат в базовом поле.
Ожидается
Описание ec корректно.
Ожидается
Точки a и b лежат на кривой.
- Аргументы
c сумма
a первое слагаемое
b второе слагаемое
ec описание эллиптической кривой
stack вспомогательная память
typedef void(* ec_dbl_i) (word b[], const word a[], const struct ec_o *ec, void *stack)
На эллиптической кривой ec определяется точка [ec->d * ec->f->n]b, полученная удвоением точки [ec->d * ec->f->n]a:
b <- 2 a.
Предусловие
Описание ec работоспособно.
Буфер b либо не пересекается, либо совпадает с буфером a.
Координаты a лежат в базовом поле.
Ожидается
Описание ec корректно.
Ожидается
Точка a лежит на кривой.
- Аргументы
b удвоенная точка
a первоначальная точка
ec описание эллиптической кривой
stack вспомогательная память
typedef void(* ec_dbla_i) (word b[], const word a[], const struct ec_o *ec, void *stack)
На эллиптической кривой ec определяется проективная точка [ec->d * ec->f->n]b, полученная удвоением аффинной точки [2 * ec->f->n]a:
b <- 2 a.
Предусловие
Описание ec работоспособно.
Буферы a и b либо не пересекаются, либо указатели a и b совпадают.
Координаты a лежат в базовом поле.
Ожидается
Описание ec корректно.
Ожидается
Точка a лежит на кривой.
- Аргументы
b удвоенная точка
a первоначальная точка
ec описание эллиптической кривой
stack вспомогательная память
typedef bool_t(* ec_froma_i) (word b[], const word a[], const struct ec_o *ec, void *stack)
По аффинной точке [2 * ec->f->n]a эллиптической кривой ec строится точка [ec->d * ec->f->n]b.
Предусловие
Описание ec работоспособно.
Буферы a и b либо не пересекаются, либо указатели a и b совпадают.
Координаты a лежат в базовом поле.
Ожидается
Описание ec корректно.
Ожидается
Точка a лежит на кривой.
- Возвращает
TRUE, если преобразование успешно выполнено, и FALSE в противном случае.
- Аргументы
b выходная точка
a аффинная точка
ec описание эллиптической кривой
stack вспомогательная память
typedef void(* ec_neg_i) (word b[], const word a[], const struct ec_o *ec, void *stack)
На эллиптической кривой ec определяется точка [ec->d * ec->f->n]b, обратная к точке [ec->d * ec->f->n]a:
b <- -a.
Предусловие
Описание ec работоспособно.
Буфер b либо не пересекается, либо совпадает с буфером a.
Координаты a лежат в базовом поле.
Ожидается
Описание ec корректно.
Ожидается
Точка a лежит на кривой.
- Аргументы
b обратная точка
a обращаемая точка
ec описание эллиптической кривой
stack вспомогательная память
typedef struct ec_o ec_o
Описывается эллиптическая кривая, правила представления ее элементов, группа точек и функции, реализующие операции в группе.
Прим.
В таблицу указателей описания кривой как объекта входят поля f, A, B, base, order, params. Поле f является указателем на объект.
typedef void(* ec_sub_i) (word c[], const word a[], const word b[], const struct ec_o *ec, void *stack)
На эллиптической кривой ec определяется разность [ec->d * ec->f->n]c точек [ec->d * ec->f->n]a и [ec->d * ec->f->n]b:
c <- a - b.
Предусловие
Описание ec работоспособно.
Буфер с либо не пересекается с каждым из буферов a и b, либо совпадает с некоторым из них.
Координаты a и b лежат в базовом поле.
Ожидается
Описание ec корректно.
Ожидается
Точки a и b лежат на кривой.
- Аргументы
c разность
a уменьшаемое
b вычитаемое
ec описание эллиптической кривой
stack вспомогательная память
typedef void(* ec_suba_i) (word c[], const word a[], const word b[], const struct ec_o *ec, void *stack)
На эллиптической кривой ec определяется разность [ec->d * ec->f->n]c проективной точки [ec->d * ec->f->n]a и аффинной точки [2 * ec->f->n]b:
c <- a - b.
Предусловие
Описание ec работоспособно.
Буфер с либо не пересекается с каждым из буферов a и b, либо указатель c совпадает с некоторым из указателей a или b.
Координаты a и b лежат в базовом поле.
Ожидается
Описание ec корректно.
Ожидается
Точки a и b лежат на кривой.
- Аргументы
c разность
a уменьшаемое
b вычитаемое
ec описание эллиптической кривой
stack вспомогательная память
typedef bool_t(* ec_toa_i) (word b[], const word a[], const struct ec_o *ec, void *stack)
По точке [ec->d * ec->f->n]a эллиптической кривой ec строится аффинная точка [2 * ec->f->n]b.
Предусловие
Описание ec работоспособно.
Буферы a и b либо не пересекаются, либо указатели a и b совпадают.
Координаты a лежат в базовом поле.
Ожидается
Описание ec корректно.
Ожидается
Точка a лежит на кривой.
- Возвращает
TRUE, если аффинная точка построена, и FALSE, если точке a соответствует бесконечно удаленная точка.
- Аргументы
b аффинная точка
a входная точка
ec описание эллиптической кривой
stack вспомогательная память
typedef void(* ec_tpl_i) (word b[], const word a[], const struct ec_o *ec, void *stack)
На эллиптической кривой ec определяется точка [ec->d * ec->f->n]b, полученная утроением точки [ec->d * ec->f->n]a:
b <- 3 a.
Предусловие
Описание ec работоспособно.
Буфер b либо не пересекается, либо совпадает с буфером a.
Координаты a лежат в базовом поле.
Ожидается
Описание ec корректно.
Ожидается
Точка a лежит на кривой.
- Аргументы
b утроенная точка
a первоначальная точка
ec описание эллиптической кривой
stack вспомогательная память
Функции
bool_t ecAddMulA (word b[], const ec_o * ec, void * stack, size_t k, ...)
Определяется точка [2n]b эллиптической кривой ec, которая является суммой [m[i]]d[i]-кратных точек [2n]a[i], i = 1, 2,.., k:
b <- d[1] a[1] + d[2] a[2] + ... + d[k] a[k].
Тройки a[i], d[i], m[i] передаются как дополнительные параметры типов const word[], const word[], size_t соответственно.
Предусловие
Описание ec работоспособно.
k > 0.
Координаты точек a[1], a[2],..., a[k] лежат в базовом поле.
Ожидается
Описание ec корректно.
Ожидается
Точки a[1], a[2],..., a[k] лежат на ec.
- Возвращает
TRUE, если полученная точка является аффинной, и FALSE в противном случае (b == O).
- Схема расчета глубины stack
ecAddMulA_deep(ec->f->n, ec->d, ec->deep, m[1], ..., m[k]).
- Аргументы
b кратная точка
ec описание кривой
stack вспомогательная память
k число троек (a[i], d[i], m[i])
... тройки (a[i], d[i], m[i])
bool_t ecCreateGroup (ec_o * ec, const octet xbase[], const octet ybase[], const octet order[], size_t order_len, u32 cofactor, void * stack)
В описание ec эллиптической кривой добавляется описание группы, порожденной точкой ([ec->f->no]xbase, [ec->f->no]ybase). Группа имеет порядок [order_len]order и ее кофактор равняется cofactor.
Предусловие
Описание ec работоспособно.
Буферы [2 * ec->f->n]ec->base, [ec->f->n + 1]ec->order корректны.
Ожидается [FALSE]
Число [octet_len]octet укладывается в ec->f->n + 1 машинных слов.
Ожидается [FALSE]
cofactor != 0 && cofactor укладывается в машинное слово.
Ожидается
Описание ec корректно.
- Возвращает
TRUE, если описание группы успешно задано, и FALSE в противном случае.
Прим.
Любой из указателей xbase, ybase может быть нулевым. При нулевом указателе соответствующая координата базовой точки устанавливается равной нулю.
- Схема расчета глубины stack
ecCreateGroup_deep(f_deep).
- Аргументы
ec описание кривой
xbase x-координата базовой точки
ybase y-координата базовой точки
order порядок группы точек
order_len длина order
cofactor кофактор группы точек
stack вспомогательная память
bool_t ecHasOrderA (const word a[], const ec_o * ec, const word q[], size_t m, void * stack)
Проверяется, что аффинная точка [2 * ec->f->n]a имеет порядок [m]q в группе точек кривой ec.
Предусловие
Описание ec работоспособно.
Координаты a лежат в базовом поле.
q > 0.
Ожидается
Описание ec корректно.
Ожидается
Точка a лежит на ec.
Ожидается
Число q -- простое. Если q -- составное, то точка порядка q1 | q может быть ошибочно признана точкой порядка q.
Возвращает
Признак успеха проверки.
- Схема расчета глубины stack
ecpHasOrderA_deep(ec->f->n, ec->d, ec->f->deep, m).
- Аргументы
a точка
ec описание кривой
q порядок
m длина q в машинных словах
stack вспомогательная память
bool_t ecIsOperable (const ec_o * ec)
Проверяется работоспособность описания ec эллиптической кривой. Проверяются следующие условия:
- объект ec работоспособен;
- objKeep(ec) >= sizeof(ec_o);
- objPCount(ec) == 6 && objOCount(ec) == 1;
- ec->d >= 3;
- qrIsOperable(ec->f) == TRUE;
- буферы [ec->n]ec->A, [ec->n]ec->B корректны;
- указатели ec->froma, r->toa, ..., r->dbla корректны;
- ec->deep >= ec->f->deep.
Возвращает
Признак корректности.
Прим.
Поля ec->base, ec->order и ec->cofactor, описывающие группу точек, не контролируются.
- Аргументы
ec описание кривой
bool_t ecIsOperable2 (const ec_o * ec)
Проверяется работоспособность описания ec эллиптической кривой без учета ссылочного описания базового поля. Проверяются следующие условия:
- объект ec работоспособен;
- objKeep(ec) >= sizeof(ec_o);
- objPCount(ec) == 6 && objOCount(ec) == 1;
- ec->d >= 3;
- буферы [ec->n]ec->A, [ec->n]ec->B корректны;
- указатели ec->froma, r->toa, ..., r->dbla корректны.
Возвращает
Признак корректности.
Прим.
Поля ec->base, ec->order и ec->cofactor, описывающие группу точек, не контролируются.
- Аргументы
ec описание кривой
bool_t ecIsOperableGroup (const ec_o * ec)
Проверяется работоспособность описания группы точек эллиптической кривой ec. Проверяются следующие условия:
- буферы [ec->n + 1]ec->order, [2 * ec->n]ec->base корректны;
- ec->order != 0;
- cofactor != 0.
Предусловие
Описание ec работоспособно.
Возвращает
Признак корректности.
- Аргументы
ec описание кривой
bool_t ecMulA (word b[], const word a[], const ec_o * ec, const word d[], size_t m, void * stack)
Определяется аффинная точка [2 * ec->f->n]b эллиптической кривой ec, которая является [m]d-кратной аффинной точки [2 * ec->f->n]a:
b <- d a.
Предусловие
Описание ec работоспособно.
Координаты a лежат в базовом поле.
Ожидается
Описание ec корректно.
Ожидается
Точка a лежит на ec.
- Возвращает
TRUE, если кратная точка является аффинной, и FALSE в противном случае (b == O).
- Схема расчета глубины stack
ecpMulA_deep(ec->f->n, ec->d, ec->f->deep, m).
- Аргументы
b кратная точка
a базовая точка
ec описание кривой
d кратность
m длина d в машинных словах
stack вспомогательная память
Автор
Автоматически создано Doxygen для Библиотека Bee2 из исходного текста.