bee2-rs 0.2.3

/*
*******************************************************************************
\file gf2.h
\brief Binary fields
\project bee2 [cryptographic library]
\created 2012.04.17
\version 2015.02.01
\copyright The Bee2 authors
\license Licensed under the Apache License, Version 2.0 (see LICENSE.txt).
*******************************************************************************
*/

/*!
*******************************************************************************
\file gf2.h
\brief Двоичные поля
*******************************************************************************
*/

#ifndef __BEE2_GF2_H
#define __BEE2_GF2_H

#include "bee2/math/qr.h"

#ifdef __cplusplus
extern "C" {
#endif

/*!
*******************************************************************************
\file gf2.h

Реализованы операции в поле GF(2^m). Элементы поля интерпретируются как 
элементы кольца вычетов GF(2) / (p(x)), где p(x) --- неприводимый
многочлен степени m. Реализована поддержка трехчленов и пятичленов.

Элементы кольца кодируются строками из O_OF_B(m) октетов и задаются 
массивами из W_OF_B(m) машинных слов. При кодировании используются порядок 
"от младших к старшим". Перечисленные соглашения можно учитывать при 
планировании работы в поле.

Многочлен p(x) задается массивом size_t p[4]:
	p(x) = x^p[0] + x^p[1] + x^p[2] + x^p[3] + 1.
В частности, m == p[0] --- степень расширения поля.

При p[2] == 0 должно выполняться также p[3] == 0 и p(x) -- трехчлен.

При p[1] == 0 должно выполняться также p[2] == p[3] == 0 и поле f
описывается нормальным базисом (на будущее).

Для трехчленов и пятичленов p(x) должны выполняться ограничения,
заданные в функциях ppRedTrinomial(), ppRedPentanomial().

Поле создается с помощью функции gf2Create(). При создании поля 
анализируется p(x) и в зависимости от его вида выбирается одна 
из общих функций редукции ppRedTrinomial() или ppRedPentanomial().

Массив p, описывающий p(x), при создании поля фиксируется  
по адресу params (см. описание типа qr_o). При создании поля 
также формируется модуль mod. Модуль представляется либо n 
машинными словами (степень p(x) кратна B_PER_W), либо n + 1 словом 
(степень p(x) не кратна B_PER_W).  

Некоторые неприводимые многочлены из криптографических стандартов:
Belt, GCM:	x^128 + x^7 + x^2 + x + 1,
NIST163:	x^163 + x^7 + x^6 + x^3 + 1,
NIST233:	x^233 + x^74 + 1,
NIST283:	x^283 + x^12 + x^7 + x^5 + 1,
NIST409:	x^409 + x^87 + 1,
NIST571:	x^571 + x^10 + x^5 + x^2 + 1.

\pre Все указатели, передаваемые в функции, действительны.

\safe todo
*******************************************************************************
*/

/*
*******************************************************************************
Управление описанием поля
*******************************************************************************
*/

/*!	\brief Создание описания поля GF(2^m)

	По описанию p многочлена p(x) создается описание f поля 
	GF(2^m) = GF(2)/(p(x)). Подбирается оптимальное (с точки зрения 
	эффективности вычислений) описание поля.
	\expect p(x) -- неприводим.
	\return Признак успеха.
	\post Cтепень расширения m совпадает с p[0].
	\post f->n == W_OF_B(m) и f->no == O_OF_B(m).
	\keep{f} gf2Create_keep(m).
	\deep{stack} gf2Create_deep(m).
*/
bool_t gf2Create(
	qr_o* f,			/*!< [out] описание поля */
	const size_t p[4],	/*!< [in] описание p(x) */
	void* stack			/*!< [in] вспомогательная память */
);

size_t gf2Create_keep(size_t m);
size_t gf2Create_deep(size_t m);

/*!	\brief Описание поля GF(2^m) работоспособно?

	Проверяется работоспособность описания f поля GF(2^m). Проверяются
	следующие условия:
	-	qrIsOperable(f) == TRUE;
	-	указатель f->mod корректен;
	-	указатель f->params корректен;
	-	f->params указывает на массив [4]p;
	-	p[0] > p[1] >= p[2] >= p[3] >= 0;
	-	p[2] > 0 => предыдущие неравенства строгие (для пятичленов);
	-	последнее слово f->mod ненулевое;
	-	f->n == W_OF_B(m) (m == p[0]);
	-	f->no == O_OF_B(m).
	.
	\return Признак работоспособности.
	\remark Не проверяется согласованность f->mod и [4]p, а также 
	неприводимость f->mod.
*/
bool_t gf2IsOperable(
	const qr_o* f		/*!< [in] описание поля */
);

/*!	\brief Описание поля GF(2^m) корректно?

	Проверяется корректность описания f поля GF(2^m). Проверяются 
	следующие условия:
	-	gf2IsOperable(f) == TRUE;
	-	если p[1] > 0, то f->mod и массив [4]p описывают одинаковые многочлены;
	-	если p[1] > 0, то многочлен f->mod неприводим.
	.
	Здесь [4]p -- это массив по адресу f->params.
	\return Признак корректности.
	\deep{stack} gf2IsValid_deep(f->n).
*/
bool_t gf2IsValid(
	const qr_o* f,		/*!< [in] описание поля */
	void* stack			/*!< [in] вспомогательная память */
);

size_t gf2IsValid_deep(size_t n);

/*!	\brief Степень расширения поля GF(2^m)

	Определяется степень расширения m поля f = GF(2^m).
	\pre Описание f работоспособно.
	\return Степень расширения.
*/
size_t gf2Deg(
	const qr_o* f		/*!< [in] описание поля */
);

/*
*******************************************************************************
Псевдонимы

Для ускорения работы вместо обращения к функциям интерфейса qr_add_i, 
qr_sub_i, qr_neg_i идут прямые обращения к wwXor(), wwXor2(), wwCopy().
*******************************************************************************
*/

#define gf2IsIn(a, f)\
	(gf2Deg(f) % B_PER_W == 0 || wwCmp(a, (f)->mod, (f)->n) < 0)

#define gf2Add(c, a, b, f)\
	wwXor(c, a, b, (f)->n)

#define gf2Add2(b, a, f)\
	wwXor2(b, a, (f)->n)

#define gf2Sub(c, a, b, f)\
	wwXor(c, a, b, (f)->n)

#define gf2Sub2(b, a, f)\
	wwXor2(b, a, (f)->n)

#define gf2Neg(b, a, f)\
	wwCopy(b, a, (f)->n)

/*
*******************************************************************************
Дополнительные функции
*******************************************************************************
*/

/*!	\brief След элемента поля GF(2^m)

	В поле f = GF(2^m) определяется абсолютный след элемента [f->n]a:
	\code
		\tr(a) <- \sum {i = 0}^{m - 1} a^{2^i}.
	\endcode
	След совпадает либо с нулем, либо с единицей поля.
	\pre Описание f работоспособно.
	\pre Элемент a принадлежит f.
	\expect Описание f корректно.
	\return FALSE, если след равняется 0, и TRUE, если след равняется 1.
	\deep{stack} gf2Tr_deep(f->n, f->deep).
*/
bool_t gf2Tr(
	const word a[],			/*!< [in] элемент */
	const qr_o* f,			/*!< [in] описание поля */
	void* stack				/*!< [in] вспомогательная память */
);

size_t gf2Tr_deep(size_t n, size_t f_deep);

/*!	\brief Решение квадратного уравнения в поле GF(2^m)

	В поле f = GF(2^m) для заданных элементов [f->n]a, [f->n]b 
	определяется решение [n]x квадратного уравнения
	\code
		x^2 + a x + b == 0. 
	\endcode
	\pre Описание f работоспособно.
	\pre m -- нечетное.
	\pre Буфер x не пересекается с буферами a, b.
	\pre Элементы a и b принадлежат f.
	\expect Описание f корректно.
	\return TRUE, если решение есть, и FALSE в противном случае.
	\remark Если x -- решение, то и x + a -- решение.
	\deep{stack} gf2QSolve_deep(f->n, f->deep).
*/
bool_t gf2QSolve(
	word x[],					/*!< [out] решение */
	const word a[],				/*!< [in] коэффициент a */
	const word b[],				/*!< [in] коэффициент b */
	const qr_o* f,				/*!< [in] описание поля */
	void* stack					/*!< [in] вспомогательная память */
);

size_t gf2QSolve_deep(size_t n, size_t f_deep);

#ifdef __cplusplus
} /* extern "C" */
#endif

#endif /* __BEE2_GF2_H */