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/nn/nn_add.h> 17 #include <libecc/nn/nn.h> 18 /* Use internal API header */ 19 #include "nn_mul.h" 20 21 /* 22 * Compute out = (in1 * in2) & (2^(WORD_BYTES * wlimits) - 1). 23 * 24 * The function is constant time for all sets of parameters of given 25 * lengths. 26 * 27 * Implementation: while most generic library implement some advanced 28 * algorithm (Karatsuba, Toom-Cook, or FFT based algorithms) 29 * which provide a performance advantage for large numbers, the code 30 * below is mainly oriented towards simplicity and readibility. It is 31 * a direct writing of the naive multiplication algorithm one has 32 * learned in school. 33 * 34 * Portability: in order for the code to be portable, all word by 35 * word multiplication are actually performed by an helper macro 36 * on half words. 37 * 38 * Note: 'out' is initialized by the function (caller can omit it) 39 * 40 * Internal use only. Check on input nn left to the caller. 41 * 42 * The function returns 0 on succes, -1 on error. 43 */ 44 ATTRIBUTE_WARN_UNUSED_RET static int _nn_mul_low(nn_t out, nn_src_t in1, nn_src_t in2, 45 u8 wlimit) 46 { 47 word_t carry, prod_high, prod_low; 48 u8 i, j, pos; 49 int ret; 50 51 /* We have to check that wlimit does not exceed our NN_MAX_WORD_LEN */ 52 MUST_HAVE(((wlimit * WORD_BYTES) <= NN_MAX_BYTE_LEN), ret, err); 53 54 ret = nn_init(out, (u16)(wlimit * WORD_BYTES)); EG(ret, err); 55 56 for (i = 0; i < in1->wlen; i++) { 57 carry = 0; 58 pos = 0; 59 60 for (j = 0; j < in2->wlen; j++) { 61 pos = (u8)(i + j); 62 63 /* 64 * size of the result provided by the caller may not 65 * be large enough for what multiplication may 66 * generate. 67 */ 68 if (pos >= wlimit) { 69 continue; 70 } 71 72 /* 73 * Compute the result of the multiplication of 74 * two words. 75 */ 76 WORD_MUL(prod_high, prod_low, 77 in1->val[i], in2->val[j]); 78 /* 79 * And add previous carry. 80 */ 81 prod_low = (word_t)(prod_low + carry); 82 prod_high = (word_t)(prod_high + (prod_low < carry)); 83 84 /* 85 * Add computed word to what we can currently 86 * find at current position in result. 87 */ 88 out->val[pos] = (word_t)(out->val[pos] + prod_low); 89 carry = (word_t)(prod_high + (out->val[pos] < prod_low)); 90 } 91 92 /* 93 * What remains in acc_high at end of previous loop should 94 * be added to next word after pos in result. 95 */ 96 if ((pos + 1) < wlimit) { 97 out->val[pos + 1] = (word_t)(out->val[pos + 1] + carry); 98 } 99 } 100 101 err: 102 return ret; 103 } 104 105 /* Aliased version. Internal use only. Check on input nn left to the caller */ 106 ATTRIBUTE_WARN_UNUSED_RET static int _nn_mul_low_aliased(nn_t out, nn_src_t in1, nn_src_t in2, 107 u8 wlimit) 108 { 109 nn out_cpy; 110 int ret; 111 out_cpy.magic = WORD(0); 112 113 ret = _nn_mul_low(&out_cpy, in1, in2, wlimit); EG(ret, err); 114 ret = nn_init(out, out_cpy.wlen); EG(ret, err); 115 ret = nn_copy(out, &out_cpy); 116 117 err: 118 nn_uninit(&out_cpy); 119 120 return ret; 121 } 122 123 /* Public version supporting aliasing. */ 124 int nn_mul_low(nn_t out, nn_src_t in1, nn_src_t in2, u8 wlimit) 125 { 126 int ret; 127 128 ret = nn_check_initialized(in1); EG(ret, err); 129 ret = nn_check_initialized(in2); EG(ret, err); 130 131 /* Handle output aliasing */ 132 if ((out == in1) || (out == in2)) { 133 ret = _nn_mul_low_aliased(out, in1, in2, wlimit); 134 } else { 135 ret = _nn_mul_low(out, in1, in2, wlimit); 136 } 137 138 err: 139 return ret; 140 } 141 142 /* 143 * Compute out = in1 * in2. 'out' is initialized by the function. 144 * The function returns 0 on success, -1 on error. 145 * 146 * Aliasing supported. 147 */ 148 int nn_mul(nn_t out, nn_src_t in1, nn_src_t in2) 149 { 150 int ret; 151 152 ret = nn_check_initialized(in1); EG(ret, err); 153 ret = nn_check_initialized(in2); EG(ret, err); 154 ret = nn_mul_low(out, in1, in2, (u8)(in1->wlen + in2->wlen)); 155 156 err: 157 return ret; 158 } 159 160 int nn_sqr_low(nn_t out, nn_src_t in, u8 wlimit) 161 { 162 return nn_mul_low(out, in, in, wlimit); 163 } 164 165 /* 166 * Compute out = in * in. 'out' is initialized by the function. 167 * The function returns 0 on success, -1 on error. 168 * 169 * Aliasing supported. 170 */ 171 int nn_sqr(nn_t out, nn_src_t in) 172 { 173 return nn_mul(out, in, in); 174 } 175 176 /* 177 * Multiply a multiprecision number by a word, i.e. out = in * w. The function 178 * returns 0 on success, -1 on error. 179 * 180 * Aliasing supported. 181 */ 182 int nn_mul_word(nn_t out, nn_src_t in, word_t w) 183 { 184 nn w_nn; 185 int ret; 186 w_nn.magic = WORD(0); 187 188 ret = nn_check_initialized(in); EG(ret, err); 189 ret = nn_init(&w_nn, WORD_BYTES); EG(ret, err); 190 w_nn.val[0] = w; 191 ret = nn_mul(out, in, &w_nn); 192 193 err: 194 nn_uninit(&w_nn); 195 196 return ret; 197 } 198