diff options
Diffstat (limited to 'include/libecc/nn')
| -rw-r--r-- | include/libecc/nn/nn.h | 96 | ||||
| -rw-r--r-- | include/libecc/nn/nn_add.h | 32 | ||||
| -rw-r--r-- | include/libecc/nn/nn_config.h | 220 | ||||
| -rw-r--r-- | include/libecc/nn/nn_div.h | 43 | ||||
| -rw-r--r-- | include/libecc/nn/nn_div_public.h | 30 | ||||
| -rw-r--r-- | include/libecc/nn/nn_logical.h | 34 | ||||
| -rw-r--r-- | include/libecc/nn/nn_mod_pow.h | 23 | ||||
| -rw-r--r-- | include/libecc/nn/nn_modinv.h | 26 | ||||
| -rw-r--r-- | include/libecc/nn/nn_mul.h | 29 | ||||
| -rw-r--r-- | include/libecc/nn/nn_mul_public.h | 24 | ||||
| -rw-r--r-- | include/libecc/nn/nn_mul_redc1.h | 26 | ||||
| -rw-r--r-- | include/libecc/nn/nn_rand.h | 24 |
12 files changed, 607 insertions, 0 deletions
diff --git a/include/libecc/nn/nn.h b/include/libecc/nn/nn.h new file mode 100644 index 000000000000..dc437331111f --- /dev/null +++ b/include/libecc/nn/nn.h @@ -0,0 +1,96 @@ +/* + * Copyright (C) 2017 - This file is part of libecc project + * + * Authors: + * Ryad BENADJILA <ryadbenadjila@gmail.com> + * Arnaud EBALARD <arnaud.ebalard@ssi.gouv.fr> + * Jean-Pierre FLORI <jean-pierre.flori@ssi.gouv.fr> + * + * Contributors: + * Nicolas VIVET <nicolas.vivet@ssi.gouv.fr> + * Karim KHALFALLAH <karim.khalfallah@ssi.gouv.fr> + * + * This software is licensed under a dual BSD and GPL v2 license. + * See LICENSE file at the root folder of the project. + */ +#ifndef __NN_H__ +#define __NN_H__ + +#include <libecc/words/words.h> +#include <libecc/nn/nn_config.h> +#include <libecc/utils/utils.h> + +/* + * For a given amount of bytes (resp. bits), return the minimum number + * of words required to store that amount of bytes (respectively bits). + */ +#define BYTE_LEN_WORDS(nbytes) (((nbytes) + WORD_BYTES - 1) / WORD_BYTES) +#define BIT_LEN_WORDS(nbits) (((nbits) + WORD_BITS - 1) / WORD_BITS) + +/* + * For a given amount of bytes (resp. bits), return the first number of + * bytes (resp. bits) equal or above to that value which is a multiple + * of word bytes. + */ +#define BYTE_LEN_CEIL(nbytes) (BYTE_LEN_WORDS(nbytes) * WORD_BYTES) +#define BIT_LEN_CEIL(nbits) (BIT_LEN_WORDS(nbits) * WORD_BITS) + +/* + * Our nn type contains an array of words, which is of a fixed given storage + * size defined in nn_lib_ecc_config.h. + * + * Each word in this array is in local endianness whereas the words + * in the array are ordered in a little endian way with regard to their + * indices. That is: the word at index 0 in the array contains the least + * significant word of the nn. + * + * Except explicitly specified (some functions may provide automatic + * initialization of output params), initialization is usually required + * before nn can be used. + * + * After initialization, the 'wlen' attribute provides at each moment + * an upper bound on the position of last non-zero word in the array. + * All words after that point are always guaranteed to be 0 after any + * manipulation by a function of this module. + * Functions use this assumption to optimize operations by avoiding to + * process leading zeros. + * Nevertheless, some functions still access words past the 'wlen' index + * and return correct results only if these words are 0. + * + * Note that functions with parameters not explicitly marked as const may + * modify the value of the 'wlen' attribute if they see fit. + * And indeed most of them set the output 'wlen' attribute to the maximal + * possible value given the inputs 'wlen' attributes. + * The most notable exceptions are the logical functions whose result + * depends on the preset value of the output 'wlen' attribute. + */ +typedef struct { + word_t val[BIT_LEN_WORDS(NN_MAX_BIT_LEN)]; + word_t magic; + u8 wlen; +} nn; + +typedef nn *nn_t; +typedef const nn *nn_src_t; + +ATTRIBUTE_WARN_UNUSED_RET int nn_check_initialized(nn_src_t A); +ATTRIBUTE_WARN_UNUSED_RET int nn_is_initialized(nn_src_t A); +ATTRIBUTE_WARN_UNUSED_RET int nn_zero(nn_t A); +ATTRIBUTE_WARN_UNUSED_RET int nn_one(nn_t A); +ATTRIBUTE_WARN_UNUSED_RET int nn_set_word_value(nn_t A, word_t val); +void nn_uninit(nn_t A); +ATTRIBUTE_WARN_UNUSED_RET int nn_init(nn_t A, u16 len); +ATTRIBUTE_WARN_UNUSED_RET int nn_init_from_buf(nn_t A, const u8 *buf, u16 buflen); +ATTRIBUTE_WARN_UNUSED_RET int nn_cnd_swap(int cnd, nn_t in1, nn_t in2); +ATTRIBUTE_WARN_UNUSED_RET int nn_set_wlen(nn_t A, u8 new_wlen); +ATTRIBUTE_WARN_UNUSED_RET int nn_iszero(nn_src_t A, int *iszero); +ATTRIBUTE_WARN_UNUSED_RET int nn_isone(nn_src_t A, int *isone); +ATTRIBUTE_WARN_UNUSED_RET int nn_isodd(nn_src_t A, int *isodd); +ATTRIBUTE_WARN_UNUSED_RET int nn_cmp_word(nn_src_t in, word_t w, int *cmp); +ATTRIBUTE_WARN_UNUSED_RET int nn_cmp(nn_src_t A, nn_src_t B, int *cmp); +ATTRIBUTE_WARN_UNUSED_RET int nn_copy(nn_t dst_nn, nn_src_t src_nn); +ATTRIBUTE_WARN_UNUSED_RET int nn_normalize(nn_t in1); +ATTRIBUTE_WARN_UNUSED_RET int nn_export_to_buf(u8 *buf, u16 buflen, nn_src_t in_nn); +ATTRIBUTE_WARN_UNUSED_RET int nn_tabselect(nn_t out, u8 idx, nn_src_t *tab, u8 tabsize); + +#endif /* __NN_H__ */ diff --git a/include/libecc/nn/nn_add.h b/include/libecc/nn/nn_add.h new file mode 100644 index 000000000000..3506f6647353 --- /dev/null +++ b/include/libecc/nn/nn_add.h @@ -0,0 +1,32 @@ +/* + * Copyright (C) 2017 - This file is part of libecc project + * + * Authors: + * Ryad BENADJILA <ryadbenadjila@gmail.com> + * Arnaud EBALARD <arnaud.ebalard@ssi.gouv.fr> + * Jean-Pierre FLORI <jean-pierre.flori@ssi.gouv.fr> + * + * Contributors: + * Nicolas VIVET <nicolas.vivet@ssi.gouv.fr> + * Karim KHALFALLAH <karim.khalfallah@ssi.gouv.fr> + * + * This software is licensed under a dual BSD and GPL v2 license. + * See LICENSE file at the root folder of the project. + */ +#ifndef __NN_ADD_H__ +#define __NN_ADD_H__ +#include <libecc/nn/nn.h> + +ATTRIBUTE_WARN_UNUSED_RET int nn_cnd_add(int cnd, nn_t out, nn_src_t in1, nn_src_t in2); +ATTRIBUTE_WARN_UNUSED_RET int nn_cnd_sub(int cnd, nn_t out, nn_src_t in1, nn_src_t in2); +ATTRIBUTE_WARN_UNUSED_RET int nn_add(nn_t out, nn_src_t in1, nn_src_t in2); +ATTRIBUTE_WARN_UNUSED_RET int nn_inc(nn_t out, nn_src_t in1); +ATTRIBUTE_WARN_UNUSED_RET int nn_sub(nn_t out, nn_src_t in1, nn_src_t in2); +ATTRIBUTE_WARN_UNUSED_RET int nn_dec(nn_t out, nn_src_t in1); +ATTRIBUTE_WARN_UNUSED_RET int nn_mod_add(nn_t out, nn_src_t in1, nn_src_t in2, nn_src_t p); +ATTRIBUTE_WARN_UNUSED_RET int nn_mod_inc(nn_t out, nn_src_t in1, nn_src_t p); +ATTRIBUTE_WARN_UNUSED_RET int nn_mod_sub(nn_t out, nn_src_t in1, nn_src_t in2, nn_src_t p); +ATTRIBUTE_WARN_UNUSED_RET int nn_mod_dec(nn_t out, nn_src_t in1, nn_src_t p); +ATTRIBUTE_WARN_UNUSED_RET int nn_mod_neg(nn_t out, nn_src_t in, nn_src_t p); + +#endif /* __NN_ADD_H__ */ diff --git a/include/libecc/nn/nn_config.h b/include/libecc/nn/nn_config.h new file mode 100644 index 000000000000..ace4c75113cc --- /dev/null +++ b/include/libecc/nn/nn_config.h @@ -0,0 +1,220 @@ +/* + * Copyright (C) 2017 - This file is part of libecc project + * + * Authors: + * Ryad BENADJILA <ryadbenadjila@gmail.com> + * Arnaud EBALARD <arnaud.ebalard@ssi.gouv.fr> + * Jean-Pierre FLORI <jean-pierre.flori@ssi.gouv.fr> + * + * Contributors: + * Nicolas VIVET <nicolas.vivet@ssi.gouv.fr> + * Karim KHALFALLAH <karim.khalfallah@ssi.gouv.fr> + * + * This software is licensed under a dual BSD and GPL v2 license. + * See LICENSE file at the root folder of the project. + */ +#ifndef __NN_CONFIG_H__ +#define __NN_CONFIG_H__ +#include <libecc/words/words.h> +/* + * We include the curves list to adapt the maximum NN size to P and Q + * (prime and order of the curve). + */ +#include <libecc/curves/curves_list.h> +/* + * We also include the hash layer to adapt the maximum NN size to the + * maximum digest size as we have to import full digests as NN when dealing + * with some signature algorithms. + * + */ +#include <libecc/hash/hash_algs.h> + +/* + * All the big num used in the lib are statically allocated. This constant + * must be defined (here or during build) to provide an upper limit on the + * size in bits of the numbers the instance of the lib you will build will + * handle. Note that this value does not prevent the declaration and use + * of smaller numbers. + * + * Rationale for the default value: the main purpose of the lirary is to + * support for an ECC implementation. ATM, a forseeable upper limit for the + * numbers that will be dealt with is 521 bits. + * + * However, the user is allowed to overload the maximum bit length of the + * numbers through the USER_NN_BIT_LEN macro definition (see below). A + * hard limit 'nn_max' for this size depends on the word size and verifies + * the following equation (with w being the word size): + * + * floor((nn_max + w - 1) / w) * 3 = 255 + * + * This equation is explained by elements given below, and by the fact that + * the length in words of our big numbers are encoded on an u8. This yields + * in max sizes of around 5300 bits for 64-bit words, around 2650 bits for + * 32-bit words, and around 1300 bits for 16-bit words. + * + * Among all the functions we have, some need to handle something which + * can be seen as a double, so we need twice the amount of bit above. + * This is typically the case when two numbers are multiplied. + * But then you usually want to divide this product by another number + * of the initial size which generically requires shifting by the + * original sized, whence the factor 3 below. + * + * Additionally, all numbers we handled are expected to have a length which + * is a multiple of the word size we support, i.e. 64/32/16 bits. Hence the + * rounding. + */ + +/* Macro to round a bit length size to a word size */ +#define BIT_LEN_ROUNDING(x, w) ((((x) + (w) - 1) / (w)) * (w)) + +/* + * Macro to round a bit length size of a NN value to a word size, and + * to a size compatible with the arithmetic operations of the library + * (usually 3 times the size of the input numbers, see explanations above). + */ +#define MAX_BIT_LEN_ROUNDING(x, w) (((((x) + (w) - 1) / (w)) * (w)) * 3) + +#ifndef USER_NN_BIT_LEN +/* + * The user has not defined a specific bit length: we can infer our maximum + * NN bit size from our curves. + */ +#ifndef NN_MAX_BIT_LEN +#if CURVES_MAX_P_BIT_LEN >= CURVES_MAX_CURVE_ORDER_BIT_LEN +#define NN_MAX_BIT_LEN MAX_BIT_LEN_ROUNDING(CURVES_MAX_P_BIT_LEN, WORD_BITS) +#define NN_MAX_BASE CURVES_MAX_P_BIT_LEN +#else +#define NN_MAX_BIT_LEN MAX_BIT_LEN_ROUNDING(CURVES_MAX_CURVE_ORDER_BIT_LEN, WORD_BITS) +#define NN_MAX_BASE CURVES_MAX_CURVE_ORDER_BIT_LEN +#endif +#endif +/****************/ +#else +/* + * If the USER_NN_BIT_LEN flag is defined by the user, we want to be sure that + * we can also handle our curves, and we also want to round the size to the + * words we have. + */ +#if CURVES_MAX_P_BIT_LEN >= CURVES_MAX_CURVE_ORDER_BIT_LEN +#if USER_NN_BIT_LEN >= CURVES_MAX_P_BIT_LEN +#define NN_MAX_BIT_LEN MAX_BIT_LEN_ROUNDING(USER_NN_BIT_LEN, WORD_BITS) +#define NN_MAX_BASE USER_NN_BIT_LEN +#else +#define NN_MAX_BIT_LEN MAX_BIT_LEN_ROUNDING(CURVES_MAX_P_BIT_LEN, WORD_BITS) +#define NN_MAX_BASE CURVES_MAX_P_BIT_LEN +#endif +#else +#if USER_NN_BIT_LEN >= CURVES_MAX_CURVE_ORDER_BIT_LEN +#define NN_MAX_BIT_LEN MAX_BIT_LEN_ROUNDING(USER_NN_BIT_LEN, WORD_BITS) +#define NN_MAX_BASE USER_NN_BIT_LEN +#else +#define NN_MAX_BIT_LEN MAX_BIT_LEN_ROUNDING(CURVES_MAX_CURVE_ORDER_BIT_LEN, WORD_BITS) +#define NN_MAX_BASE CURVES_MAX_CURVE_ORDER_BIT_LEN +#endif +#endif +#endif + +/* Now adjust the maximum length with our maximum digest size as we + * have to import full digests as big numbers in some signature algorithms. + * + * The division by 2 here is related to the fact that we usually import hash values + * without performing much NN operations on them (immediately reducing them modulo q), so + * it is safe to remove some additional space left for multiplications. + */ +#if NN_MAX_BIT_LEN < MAX_BIT_LEN_ROUNDING(((8 * MAX_DIGEST_SIZE) / 2), WORD_BITS) +#undef NN_MAX_BIT_LEN +#define NN_MAX_BIT_LEN MAX_BIT_LEN_ROUNDING(((8 * MAX_DIGEST_SIZE) / 2), WORD_BITS) +#undef NN_MAX_BASE +#define NN_MAX_BASE MAX_DIGEST_SIZE_BITS +#endif +/* + * NOTE: the only exception to the rule above (i.e. immediately reducing hash sized + * values modulo q) is when we use blinding and EdDSA and there might be not enough + * room for our computations. This is actually *specific to EdDSA 25519* as EdDSA 448 + * always uses SHAKE256 digest with 114 bytes hash output that has enough room for + * computation when compared to the 448-bit size order of the curve. + * + * This is kind of ugly to have this specific case here, but + * being too conservative always using the maximum size adapated to MAX_DIGEST_SIZE + * sacrifices *ALL* the sognature performance only for the specific case of EdDSA 25519! + * + */ +#if defined(WITH_SIG_EDDSA25519) && defined(USE_SIG_BLINDING) +#if NN_MAX_BIT_LEN < MAX_BIT_LEN_ROUNDING((8 * SHA512_DIGEST_SIZE), WORD_BITS) +#undef NN_MAX_BIT_LEN +#define NN_MAX_BIT_LEN MAX_BIT_LEN_ROUNDING((8 * SHA512_DIGEST_SIZE), WORD_BITS) +#undef NN_MAX_BASE +#define NN_MAX_BASE MAX_DIGEST_SIZE_BITS +#endif +#endif /* defined(WITH_SIG_EDDSA25519) && defined(USE_SIG_BLINDING) */ + +/************/ +/* NN maximum internal lengths to be "safe" in our computations */ +#define NN_MAX_BYTE_LEN (NN_MAX_BIT_LEN / 8) +#define NN_MAX_WORD_LEN (NN_MAX_BYTE_LEN / WORD_BYTES) +/* Usable maximum sizes, to be used by the end user to be "safe" in + * all the computations. + */ +#define NN_USABLE_MAX_BIT_LEN (NN_MAX_BASE) +#define NN_USABLE_MAX_BYTE_LEN ((BIT_LEN_ROUNDING(NN_USABLE_MAX_BIT_LEN, 8)) / 8) +#define NN_USABLE_MAX_WORD_LEN ((BIT_LEN_ROUNDING(NN_USABLE_MAX_BIT_LEN, WORD_BITS)) / WORD_BITS) + +/* Sanity checks */ +#if (NN_USABLE_MAX_BIT_LEN > NN_MAX_BIT_LEN) || (NN_USABLE_MAX_BYTE_LEN > NN_MAX_BYTE_LEN) || (NN_USABLE_MAX_WORD_LEN > NN_MAX_WORD_LEN) +#error "usable maximum length > internal maximum length, this should not happen!" +#endif + +#if (NN_MAX_WORD_LEN > 255) +#error "nn.wlen is encoded on an u8. NN_MAX_WORD_LEN cannot be larger than 255!" +#endif + +/* Add a (somehow 'dirty' but working and useful!) way to detect when our .a + * library has been compiled with options (WORDSIZE and NN_MAX_BIT_LEN) + * inconsistent with the 'final' binary we want to compile linking to the .a + * archive. The 'magic' lies in the definition in nn.c of a function (symbol) + * in our .a archive, consisting in a concatenation of WORDSIZE and + * NN_MAX_BIT_LEN preprocessed values. On the other side, we force the use + * of this symbol in other NN .c modules, yielding in a compile time error + * if WORDSIZE or NN_MAX_BIT_LEN differ. + * Update: we also check here the consistency of using complete formulas + * or not. + */ +#ifdef NO_USE_COMPLETE_FORMULAS +#define _LIBECC_CONCATENATE(a, b, c, d, e) a##_##b##_##c##_##d##_##e +#define LIBECC_CONCATENATE(a, b, c, d, e) _LIBECC_CONCATENATE(a, b, c, d, e) +void LIBECC_CONCATENATE(nn_consistency_check_maxbitlen, NN_MAX_BASE, wordsize, + WORDSIZE, MAX_DIGEST_SIZE) (void); +#ifdef NN_CONSISTENCY_CHECK +ATTRIBUTE_USED void LIBECC_CONCATENATE(nn_consistency_check_maxbitlen, NN_MAX_BASE, + wordsize, WORDSIZE, MAX_DIGEST_SIZE) (void) { + return; +} +#else +ATTRIBUTE_USED static inline void nn_check_libconsistency(void) +{ + LIBECC_CONCATENATE(nn_consistency_check_maxbitlen, NN_MAX_BASE, wordsize, + WORDSIZE, MAX_DIGEST_SIZE) (); + return; +} +#endif +#else /* NO_USE_COMPLETE_FORMULAS */ +#define _LIBECC_CONCATENATE(a, b, c, d, e, f) a##_##b##_##c##_##d##_##e##_##f +#define LIBECC_CONCATENATE(a, b, c, d, e, f) _LIBECC_CONCATENATE(a, b, c, d, e, f) +void LIBECC_CONCATENATE(nn_consistency_check_maxbitlen, NN_MAX_BASE, wordsize, + WORDSIZE, complete_formulas, MAX_DIGEST_SIZE) (void); +#ifdef NN_CONSISTENCY_CHECK +ATTRIBUTE_USED void LIBECC_CONCATENATE(nn_consistency_check_maxbitlen, NN_MAX_BASE, + wordsize, WORDSIZE, complete_formulas, MAX_DIGEST_SIZE) (void) { + return; +} +#else +ATTRIBUTE_USED static inline void nn_check_libconsistency(void) +{ + LIBECC_CONCATENATE(nn_consistency_check_maxbitlen, NN_MAX_BASE, wordsize, + WORDSIZE, complete_formulas, MAX_DIGEST_SIZE) (); + return; +} +#endif +#endif /* NO_USE_COMPLETE_FORMULAS */ + +#endif /* __NN_CONFIG_H__ */ diff --git a/include/libecc/nn/nn_div.h b/include/libecc/nn/nn_div.h new file mode 100644 index 000000000000..0328d744d44c --- /dev/null +++ b/include/libecc/nn/nn_div.h @@ -0,0 +1,43 @@ +/* + * Copyright (C) 2017 - This file is part of libecc project + * + * Authors: + * Ryad BENADJILA <ryadbenadjila@gmail.com> + * Arnaud EBALARD <arnaud.ebalard@ssi.gouv.fr> + * Jean-Pierre FLORI <jean-pierre.flori@ssi.gouv.fr> + * + * Contributors: + * Nicolas VIVET <nicolas.vivet@ssi.gouv.fr> + * Karim KHALFALLAH <karim.khalfallah@ssi.gouv.fr> + * + * This software is licensed under a dual BSD and GPL v2 license. + * See LICENSE file at the root folder of the project. + */ +#ifndef __NN_DIV_H__ +#define __NN_DIV_H__ +#include <libecc/nn/nn.h> +#include <libecc/nn/nn_div_public.h> + +/* Compute quotient q and remainder r for given a and b such that a = q*b + r */ +/* ATTRIBUTE_WARN_UNUSED_RET int nn_divrem(nn_t q, nn_t r, nn_src_t a, nn_src_t b); (declared in public header) */ +ATTRIBUTE_WARN_UNUSED_RET int nn_divrem_notrim(nn_t q, nn_t r, nn_src_t a, nn_src_t b); +ATTRIBUTE_WARN_UNUSED_RET int nn_divrem_unshifted(nn_t q, nn_t r, nn_src_t a, nn_src_t b, word_t v, + bitcnt_t cnt); +ATTRIBUTE_WARN_UNUSED_RET int nn_divrem_normalized(nn_t q, nn_t r, nn_src_t a, nn_src_t b, word_t v); + +/* Compute r = a mod b */ +/* ATTRIBUTE_WARN_UNUSED_RET int nn_mod(nn_t r, nn_src_t a, nn_src_t b); (declared in public header) */ +ATTRIBUTE_WARN_UNUSED_RET int nn_mod_notrim(nn_t r, nn_src_t a, nn_src_t b); +ATTRIBUTE_WARN_UNUSED_RET int nn_mod_unshifted(nn_t r, nn_src_t a, nn_src_t b, word_t v, bitcnt_t cnt); +ATTRIBUTE_WARN_UNUSED_RET int nn_mod_normalized(nn_t r, nn_src_t a, nn_src_t b, word_t v); + +/* Compute floor(B^3/(d+1)) - B. */ +ATTRIBUTE_WARN_UNUSED_RET int wreciprocal(word_t dh, word_t dl, word_t *reciprocal); +ATTRIBUTE_WARN_UNUSED_RET int nn_compute_div_coefs(nn_t p_normalized, word_t *p_shift, + word_t *p_reciprocal, nn_src_t p_in); + +/* Compute gcd of a and b */ +/* ATTRIBUTE_WARN_UNUSED_RET int nn_gcd(nn_t d, nn_src_t a, nn_src_t b, int *sign); (declared in public header) */ +/* ATTRIBUTE_WARN_UNUSED_RET int nn_xgcd(nn_t g, nn_t u, nn_t v, nn_src_t a, nn_src_t b, int *sign); (declared in public header) */ + +#endif /* __NN_DIV_H__ */ diff --git a/include/libecc/nn/nn_div_public.h b/include/libecc/nn/nn_div_public.h new file mode 100644 index 000000000000..63f6705c9972 --- /dev/null +++ b/include/libecc/nn/nn_div_public.h @@ -0,0 +1,30 @@ +/* + * Copyright (C) 2017 - This file is part of libecc project + * + * Authors: + * Ryad BENADJILA <ryadbenadjila@gmail.com> + * Arnaud EBALARD <arnaud.ebalard@ssi.gouv.fr> + * Jean-Pierre FLORI <jean-pierre.flori@ssi.gouv.fr> + * + * Contributors: + * Nicolas VIVET <nicolas.vivet@ssi.gouv.fr> + * Karim KHALFALLAH <karim.khalfallah@ssi.gouv.fr> + * + * This software is licensed under a dual BSD and GPL v2 license. + * See LICENSE file at the root folder of the project. + */ +#ifndef __NN_DIV_PUBLIC_H__ +#define __NN_DIV_PUBLIC_H__ +#include <libecc/nn/nn.h> + +/* Compute quotient q and remainder r for given a and b such that a = q*b + r */ +ATTRIBUTE_WARN_UNUSED_RET int nn_divrem(nn_t q, nn_t r, nn_src_t a, nn_src_t b); + +/* Compute r = a mod b */ +ATTRIBUTE_WARN_UNUSED_RET int nn_mod(nn_t r, nn_src_t a, nn_src_t b); + +/* Compute gcd of a and b */ +ATTRIBUTE_WARN_UNUSED_RET int nn_gcd(nn_t d, nn_src_t a, nn_src_t b, int *sign); +ATTRIBUTE_WARN_UNUSED_RET int nn_xgcd(nn_t g, nn_t u, nn_t v, nn_src_t a, nn_src_t b, int *sign); + +#endif /* __NN_DIV_PUBLIC_H__ */ diff --git a/include/libecc/nn/nn_logical.h b/include/libecc/nn/nn_logical.h new file mode 100644 index 000000000000..c80c60c392b5 --- /dev/null +++ b/include/libecc/nn/nn_logical.h @@ -0,0 +1,34 @@ +/* + * Copyright (C) 2017 - This file is part of libecc project + * + * Authors: + * Ryad BENADJILA <ryadbenadjila@gmail.com> + * Arnaud EBALARD <arnaud.ebalard@ssi.gouv.fr> + * Jean-Pierre FLORI <jean-pierre.flori@ssi.gouv.fr> + * + * Contributors: + * Nicolas VIVET <nicolas.vivet@ssi.gouv.fr> + * Karim KHALFALLAH <karim.khalfallah@ssi.gouv.fr> + * + * This software is licensed under a dual BSD and GPL v2 license. + * See LICENSE file at the root folder of the project. + */ +#ifndef __LOGICAL_H__ +#define __LOGICAL_H__ +#include <libecc/nn/nn.h> + +ATTRIBUTE_WARN_UNUSED_RET int nn_rshift_fixedlen(nn_t out, nn_src_t in, bitcnt_t cnt); +ATTRIBUTE_WARN_UNUSED_RET int nn_rshift(nn_t out, nn_src_t in, bitcnt_t cnt); +ATTRIBUTE_WARN_UNUSED_RET int nn_lshift_fixedlen(nn_t out, nn_src_t in, bitcnt_t cnt); +ATTRIBUTE_WARN_UNUSED_RET int nn_lshift(nn_t out, nn_src_t in, bitcnt_t cnt); +ATTRIBUTE_WARN_UNUSED_RET int nn_rrot(nn_t out, nn_src_t in, bitcnt_t cnt, bitcnt_t bitlen); +ATTRIBUTE_WARN_UNUSED_RET int nn_lrot(nn_t out, nn_src_t in, bitcnt_t cnt, bitcnt_t bitlen); +ATTRIBUTE_WARN_UNUSED_RET int nn_xor(nn_t B, nn_src_t C, nn_src_t A); +ATTRIBUTE_WARN_UNUSED_RET int nn_or(nn_t B, nn_src_t C, nn_src_t A); +ATTRIBUTE_WARN_UNUSED_RET int nn_and(nn_t B, nn_src_t C, nn_src_t A); +ATTRIBUTE_WARN_UNUSED_RET int nn_not(nn_t B, nn_src_t A); +ATTRIBUTE_WARN_UNUSED_RET int nn_clz(nn_src_t A, bitcnt_t *lz); +ATTRIBUTE_WARN_UNUSED_RET int nn_bitlen(nn_src_t A, bitcnt_t *blen); +ATTRIBUTE_WARN_UNUSED_RET int nn_getbit(nn_src_t in, bitcnt_t bit, u8 *bitval); + +#endif /* __LOGICAL_H__ */ diff --git a/include/libecc/nn/nn_mod_pow.h b/include/libecc/nn/nn_mod_pow.h new file mode 100644 index 000000000000..28eec68edd02 --- /dev/null +++ b/include/libecc/nn/nn_mod_pow.h @@ -0,0 +1,23 @@ +/* + * Copyright (C) 2021 - This file is part of libecc project + * + * Authors: + * Ryad BENADJILA <ryadbenadjila@gmail.com> + * Arnaud EBALARD <arnaud.ebalard@ssi.gouv.fr> + * Jean-Pierre FLORI <jean-pierre.flori@ssi.gouv.fr> + * + * Contributors: + * Nicolas VIVET <nicolas.vivet@ssi.gouv.fr> + * Karim KHALFALLAH <karim.khalfallah@ssi.gouv.fr> + * + * This software is licensed under a dual BSD and GPL v2 license. + * See LICENSE file at the root folder of the project. + */ +#ifndef __NN_MOD_POW_H__ +#define __NN_MOD_POW_H__ +#include <libecc/nn/nn.h> + +ATTRIBUTE_WARN_UNUSED_RET int nn_mod_pow_redc(nn_t out, nn_src_t base, nn_src_t exp, nn_src_t mod, nn_src_t r, nn_src_t r_square, word_t mpinv); +ATTRIBUTE_WARN_UNUSED_RET int nn_mod_pow(nn_t out, nn_src_t base, nn_src_t exp, nn_src_t mod); + +#endif /* __NN_MOD_POW_H__ */ diff --git a/include/libecc/nn/nn_modinv.h b/include/libecc/nn/nn_modinv.h new file mode 100644 index 000000000000..f1df01abccae --- /dev/null +++ b/include/libecc/nn/nn_modinv.h @@ -0,0 +1,26 @@ +/* + * Copyright (C) 2017 - This file is part of libecc project + * + * Authors: + * Ryad BENADJILA <ryadbenadjila@gmail.com> + * Arnaud EBALARD <arnaud.ebalard@ssi.gouv.fr> + * Jean-Pierre FLORI <jean-pierre.flori@ssi.gouv.fr> + * + * Contributors: + * Nicolas VIVET <nicolas.vivet@ssi.gouv.fr> + * Karim KHALFALLAH <karim.khalfallah@ssi.gouv.fr> + * + * This software is licensed under a dual BSD and GPL v2 license. + * See LICENSE file at the root folder of the project. + */ +#ifndef __NN_MODINV_H__ +#define __NN_MODINV_H__ +#include <libecc/nn/nn.h> + +ATTRIBUTE_WARN_UNUSED_RET int nn_modinv(nn_t out, nn_src_t x, nn_src_t m); +ATTRIBUTE_WARN_UNUSED_RET int nn_modinv_2exp(nn_t out, nn_src_t in, bitcnt_t exp, int *in_isodd); +ATTRIBUTE_WARN_UNUSED_RET int nn_modinv_word(nn_t out, word_t w, nn_src_t m); +ATTRIBUTE_WARN_UNUSED_RET int nn_modinv_fermat(nn_t out, nn_src_t x, nn_src_t p); +ATTRIBUTE_WARN_UNUSED_RET int nn_modinv_fermat_redc(nn_t out, nn_src_t x, nn_src_t p, nn_src_t r, nn_src_t r_square, word_t mpinv); + +#endif /* __NN_MODINV_H__ */ diff --git a/include/libecc/nn/nn_mul.h b/include/libecc/nn/nn_mul.h new file mode 100644 index 000000000000..3fd12f038c10 --- /dev/null +++ b/include/libecc/nn/nn_mul.h @@ -0,0 +1,29 @@ +/* + * Copyright (C) 2017 - This file is part of libecc project + * + * Authors: + * Ryad BENADJILA <ryadbenadjila@gmail.com> + * Arnaud EBALARD <arnaud.ebalard@ssi.gouv.fr> + * Jean-Pierre FLORI <jean-pierre.flori@ssi.gouv.fr> + * + * Contributors: + * Nicolas VIVET <nicolas.vivet@ssi.gouv.fr> + * Karim KHALFALLAH <karim.khalfallah@ssi.gouv.fr> + * + * This software is licensed under a dual BSD and GPL v2 license. + * See LICENSE file at the root folder of the project. + */ +#ifndef __NN_MUL_H__ +#define __NN_MUL_H__ +#include <libecc/nn/nn.h> +#include <libecc/nn/nn_mul_public.h> + +ATTRIBUTE_WARN_UNUSED_RET int nn_mul_low(nn_t out, nn_src_t in1, nn_src_t in2, u8 wlimit); +ATTRIBUTE_WARN_UNUSED_RET int nn_sqr_low(nn_t out, nn_src_t in, u8 wlimit); +/* (declared in public header) +ATTRIBUTE_WARN_UNUSED_RET int nn_mul(nn_t out, nn_src_t in1, nn_src_t in2); +ATTRIBUTE_WARN_UNUSED_RET int nn_sqr(nn_t out, nn_src_t in); +ATTRIBUTE_WARN_UNUSED_RET int nn_mul_word(nn_t out, nn_src_t in, word_t w); +*/ + +#endif /* __NN_MUL_H__ */ diff --git a/include/libecc/nn/nn_mul_public.h b/include/libecc/nn/nn_mul_public.h new file mode 100644 index 000000000000..377da554aae7 --- /dev/null +++ b/include/libecc/nn/nn_mul_public.h @@ -0,0 +1,24 @@ +/* + * Copyright (C) 2017 - This file is part of libecc project + * + * Authors: + * Ryad BENADJILA <ryadbenadjila@gmail.com> + * Arnaud EBALARD <arnaud.ebalard@ssi.gouv.fr> + * Jean-Pierre FLORI <jean-pierre.flori@ssi.gouv.fr> + * + * Contributors: + * Nicolas VIVET <nicolas.vivet@ssi.gouv.fr> + * Karim KHALFALLAH <karim.khalfallah@ssi.gouv.fr> + * + * This software is licensed under a dual BSD and GPL v2 license. + * See LICENSE file at the root folder of the project. + */ +#ifndef __NN_MUL_PUBLIC_H__ +#define __NN_MUL_PUBLIC_H__ +#include <libecc/nn/nn.h> + +ATTRIBUTE_WARN_UNUSED_RET int nn_mul(nn_t out, nn_src_t in1, nn_src_t in2); +ATTRIBUTE_WARN_UNUSED_RET int nn_sqr(nn_t out, nn_src_t in); +ATTRIBUTE_WARN_UNUSED_RET int nn_mul_word(nn_t out, nn_src_t in, word_t w); + +#endif /* __NN_MUL_PUBLIC_H__ */ diff --git a/include/libecc/nn/nn_mul_redc1.h b/include/libecc/nn/nn_mul_redc1.h new file mode 100644 index 000000000000..931a2779f4ee --- /dev/null +++ b/include/libecc/nn/nn_mul_redc1.h @@ -0,0 +1,26 @@ +/* + * Copyright (C) 2017 - This file is part of libecc project + * + * Authors: + * Ryad BENADJILA <ryadbenadjila@gmail.com> + * Arnaud EBALARD <arnaud.ebalard@ssi.gouv.fr> + * Jean-Pierre FLORI <jean-pierre.flori@ssi.gouv.fr> + * + * Contributors: + * Nicolas VIVET <nicolas.vivet@ssi.gouv.fr> + * Karim KHALFALLAH <karim.khalfallah@ssi.gouv.fr> + * + * This software is licensed under a dual BSD and GPL v2 license. + * See LICENSE file at the root folder of the project. + */ +#ifndef __NN_MUL_REDC1_H__ +#define __NN_MUL_REDC1_H__ +#include <libecc/nn/nn.h> + +ATTRIBUTE_WARN_UNUSED_RET int nn_compute_redc1_coefs(nn_t r, nn_t r_square, nn_src_t p_in, + word_t *mpinv); +ATTRIBUTE_WARN_UNUSED_RET int nn_mul_redc1(nn_t out, nn_src_t in1, nn_src_t in2, nn_src_t p, + word_t mpinv); +ATTRIBUTE_WARN_UNUSED_RET int nn_mod_mul(nn_t out, nn_src_t in1, nn_src_t in2, nn_src_t p); + +#endif /* __NN_MUL_REDC1_H__ */ diff --git a/include/libecc/nn/nn_rand.h b/include/libecc/nn/nn_rand.h new file mode 100644 index 000000000000..e48813ee305d --- /dev/null +++ b/include/libecc/nn/nn_rand.h @@ -0,0 +1,24 @@ +/* + * Copyright (C) 2017 - This file is part of libecc project + * + * Authors: + * Ryad BENADJILA <ryadbenadjila@gmail.com> + * Arnaud EBALARD <arnaud.ebalard@ssi.gouv.fr> + * Jean-Pierre FLORI <jean-pierre.flori@ssi.gouv.fr> + * + * Contributors: + * Nicolas VIVET <nicolas.vivet@ssi.gouv.fr> + * Karim KHALFALLAH <karim.khalfallah@ssi.gouv.fr> + * + * This software is licensed under a dual BSD and GPL v2 license. + * See LICENSE file at the root folder of the project. + */ +#ifndef __NN_RAND_H__ +#define __NN_RAND_H__ +#include <libecc/nn/nn.h> + +ATTRIBUTE_WARN_UNUSED_RET int nn_get_random_len(nn_t out, u16 len); +ATTRIBUTE_WARN_UNUSED_RET int nn_get_random_maxlen(nn_t out, u16 max_len); +ATTRIBUTE_WARN_UNUSED_RET int nn_get_random_mod(nn_t out, nn_src_t q); + +#endif /* __NN_RAND_H__ */ |