1 /* 2 * Copyright (C) 2017 - This file is part of libecc project 3 * 4 * Authors: 5 * Ryad BENADJILA <ryadbenadjila@gmail.com> 6 * Arnaud EBALARD <arnaud.ebalard@ssi.gouv.fr> 7 * Jean-Pierre FLORI <jean-pierre.flori@ssi.gouv.fr> 8 * 9 * Contributors: 10 * Nicolas VIVET <nicolas.vivet@ssi.gouv.fr> 11 * Karim KHALFALLAH <karim.khalfallah@ssi.gouv.fr> 12 * 13 * This software is licensed under a dual BSD and GPL v2 license. 14 * See LICENSE file at the root folder of the project. 15 */ 16 #include <libecc/fp/fp_mul.h> 17 #include <libecc/fp/fp_pow.h> 18 #include <libecc/nn/nn_add.h> 19 #include <libecc/nn/nn_mul_public.h> 20 #include <libecc/nn/nn_modinv.h> 21 /* Include the "internal" header as we use non public API here */ 22 #include "../nn/nn_div.h" 23 24 /* 25 * Compute out = in1 * in2 mod p. 'out' parameter must have been initialized 26 * by the caller. Returns 0 on success, -1 on error. 27 * 28 * Aliasing is supported. 29 */ 30 int fp_mul(fp_t out, fp_src_t in1, fp_src_t in2) 31 { 32 int ret; 33 34 ret = fp_check_initialized(in1); EG(ret, err); 35 ret = fp_check_initialized(in2); EG(ret, err); 36 ret = fp_check_initialized(out); EG(ret, err); 37 38 MUST_HAVE(out->ctx == in1->ctx, ret, err); 39 MUST_HAVE(out->ctx == in2->ctx, ret, err); 40 41 ret = nn_mul(&(out->fp_val), &(in1->fp_val), &(in2->fp_val)); EG(ret, err); 42 ret = nn_mod_unshifted(&(out->fp_val), &(out->fp_val), &(in1->ctx->p_normalized), 43 in1->ctx->p_reciprocal, in1->ctx->p_shift); 44 45 err: 46 return ret; 47 } 48 49 /* 50 * Compute out = in * in mod p. 'out' parameter must have been initialized 51 * by the caller. Returns 0 on success, -1 on error. 52 * 53 * Aliasing is supported. 54 */ 55 int fp_sqr(fp_t out, fp_src_t in) 56 { 57 return fp_mul(out, in, in); 58 } 59 60 /* We use Fermat's little theorem for our inversion in Fp: 61 * x^(p-1) = 1 mod (p) means that x^(p-2) mod(p) is the modular 62 * inverse of x mod (p) 63 * 64 * Aliasing is supported. 65 */ 66 int fp_inv(fp_t out, fp_src_t in) 67 { 68 /* Use our lower layer Fermat modular inversion with precomputed 69 * Montgomery coefficients. 70 */ 71 int ret; 72 73 ret = fp_check_initialized(in); EG(ret, err); 74 ret = fp_check_initialized(out); EG(ret, err); 75 76 MUST_HAVE(out->ctx == in->ctx, ret, err); 77 78 /* We can use the Fermat inversion as p is surely prime here */ 79 ret = nn_modinv_fermat_redc(&(out->fp_val), &(in->fp_val), &(in->ctx->p), &(in->ctx->r), &(in->ctx->r_square), in->ctx->mpinv); 80 81 err: 82 return ret; 83 } 84 85 /* 86 * Compute out = w^-1 mod p. 'out' parameter must have been initialized 87 * by the caller. Returns 0 on success, -1 on error. 88 */ 89 int fp_inv_word(fp_t out, word_t w) 90 { 91 int ret; 92 93 ret = fp_check_initialized(out); EG(ret, err); 94 95 ret = nn_modinv_word(&(out->fp_val), w, &(out->ctx->p)); 96 97 err: 98 return ret; 99 } 100 101 /* 102 * Compute out such that num = out * den mod p. 'out' parameter must have been initialized 103 * by the caller. Returns 0 on success, -1 on error. 104 * 105 * Aliasing is supported. 106 */ 107 int fp_div(fp_t out, fp_src_t num, fp_src_t den) 108 { 109 int ret; 110 111 ret = fp_check_initialized(num); EG(ret, err); 112 ret = fp_check_initialized(den); EG(ret, err); 113 ret = fp_check_initialized(out); EG(ret, err); 114 115 MUST_HAVE(out->ctx == num->ctx, ret, err); 116 MUST_HAVE(out->ctx == den->ctx, ret, err); 117 118 if(out == num){ 119 /* Handle aliasing of out and num */ 120 fp _num; 121 _num.magic = WORD(0); 122 123 ret = fp_copy(&_num, num); EG(ret, err1); 124 ret = fp_inv(out, den); EG(ret, err1); 125 ret = fp_mul(out, &_num, out); 126 127 err1: 128 fp_uninit(&_num); 129 EG(ret, err); 130 } 131 else{ 132 ret = fp_inv(out, den); EG(ret, err); 133 ret = fp_mul(out, num, out); 134 } 135 136 err: 137 return ret; 138 } 139