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 */
_nn_mul_low(nn_t out,nn_src_t in1,nn_src_t in2,u8 wlimit)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 */
_nn_mul_low_aliased(nn_t out,nn_src_t in1,nn_src_t in2,u8 wlimit)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. */
nn_mul_low(nn_t out,nn_src_t in1,nn_src_t in2,u8 wlimit)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 */
nn_mul(nn_t out,nn_src_t in1,nn_src_t in2)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
nn_sqr_low(nn_t out,nn_src_t in,u8 wlimit)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 */
nn_sqr(nn_t out,nn_src_t in)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 */
nn_mul_word(nn_t out,nn_src_t in,word_t w)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