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_logical.h>
17 #include <libecc/nn/nn.h>
18
19 /*
20 * nn_lshift_fixedlen: left logical shift in N, i.e. compute out = (in << cnt).
21 *
22 * Aliasing is possible for 'in' and 'out', i.e. x <<= cnt can be computed
23 * using nn_lshift_fixedlen(x, x, cnt).
24 *
25 * The function supports 'in' and 'out' parameters of differents sizes.
26 *
27 * The operation time of the function depends on the size of 'in' and
28 * 'out' parameters and the value of 'cnt'. It does not depend on the
29 * value of 'in'.
30 *
31 * It is to be noted that the function uses out->wlen as the
32 * upper limit for its work, i.e. bits shifted above out->wlen
33 * are lost (the NN size of the output is not modified).
34 *
35 * The function returns 0 on sucess, -1 on error.
36 *
37 * Aliasing supported.
38 */
nn_lshift_fixedlen(nn_t out,nn_src_t in,bitcnt_t cnt)39 int nn_lshift_fixedlen(nn_t out, nn_src_t in, bitcnt_t cnt)
40 {
41 int ipos, opos, dec, ret;
42 bitcnt_t lshift, hshift;
43 u8 owlen, iwlen;
44
45 ret = nn_check_initialized(in); EG(ret, err);
46 ret = nn_check_initialized(out); EG(ret, err);
47 owlen = out->wlen;
48 iwlen = in->wlen;
49
50 dec = cnt / WORD_BITS;
51 hshift = cnt % WORD_BITS;
52 lshift = (bitcnt_t)(WORD_BITS - hshift);
53
54 for (opos = owlen - 1; opos >= 0; opos--) {
55 word_t hipart = 0, lopart = 0;
56
57 ipos = opos - dec - 1;
58 if ((ipos >= 0) && (ipos < iwlen)) {
59 lopart = WRSHIFT(in->val[ipos], lshift);
60 }
61
62 ipos = opos - dec;
63 if ((ipos >= 0) && (ipos < iwlen)) {
64 hipart = WLSHIFT(in->val[ipos], hshift);
65 }
66
67 out->val[opos] = hipart | lopart;
68 }
69
70 err:
71 return ret;
72 }
73
74 /*
75 * nn_lshift: left logical shift in N, i.e. compute out = (in << cnt).
76 *
77 * Aliasing is possible for 'in' and 'out', i.e. x <<= cnt can be computed
78 * using nn_lshift(x, x, cnt).
79 *
80 * The function supports 'in' and 'out' parameters of differents sizes.
81 *
82 * The operation time of the function depends on the size of 'in' and
83 * 'out' parameters and the value of 'cnt'. It does not depend on the
84 * value of 'in'.
85 *
86 * It is to be noted that the function computes the output bit length
87 * depending on the shift count and the input length, i.e. out bit length
88 * will be roughly in bit length plus cnt, maxed to NN_MAX_BIT_LEN.
89 *
90 * The function returns 0 on success, -1 on error.
91 *
92 * Aliasing supported.
93 */
nn_lshift(nn_t out,nn_src_t in,bitcnt_t cnt)94 int nn_lshift(nn_t out, nn_src_t in, bitcnt_t cnt)
95 {
96 bitcnt_t lshift, hshift, blen;
97 int ipos, opos, dec, ret;
98 u8 owlen, iwlen;
99
100 ret = nn_check_initialized(in); EG(ret, err);
101 iwlen = in->wlen;
102
103 /* Initialize output if no aliasing is used */
104 if (out != in) {
105 ret = nn_init(out, 0); EG(ret, err);
106 }
107
108 /* Adapt output length accordingly */
109 ret = nn_bitlen(in, &blen); EG(ret, err);
110 owlen = (u8)LOCAL_MIN(BIT_LEN_WORDS(cnt + blen),
111 BIT_LEN_WORDS(NN_MAX_BIT_LEN));
112 out->wlen = owlen;
113
114 dec = cnt / WORD_BITS;
115 hshift = cnt % WORD_BITS;
116 lshift = (bitcnt_t)(WORD_BITS - hshift);
117
118 for (opos = owlen - 1; opos >= 0; opos--) {
119 word_t hipart = 0, lopart = 0;
120
121 ipos = opos - dec - 1;
122 if ((ipos >= 0) && (ipos < iwlen)) {
123 lopart = WRSHIFT(in->val[ipos], lshift);
124 }
125
126 ipos = opos - dec;
127 if ((ipos >= 0) && (ipos < iwlen)) {
128 hipart = WLSHIFT(in->val[ipos], hshift);
129 }
130
131 out->val[opos] = hipart | lopart;
132 }
133
134 err:
135 return ret;
136 }
137
138 /*
139 * nn_rshift_fixedlen: right logical shift in N, i.e. compute out = (in >> cnt).
140 *
141 * Aliasing is possible for 'in' and 'out', i.e. x >>= cnt can be computed
142 * using nn_rshift_fixedlen(x, x, cnt).
143 *
144 * The function supports 'in' and 'out' parameters of differents sizes.
145 *
146 * The operation time of the function depends on the size of 'in' and
147 * 'out' parameters and the value of 'cnt'. It does not depend on the
148 * value of 'in'.
149 * It is to be noted that the function uses out->wlen as the
150 * upper limit for its work, which means zeroes are shifted in while
151 * keeping the same NN output size.
152 *
153 * The function returns 0 on success, -1 on error.
154 *
155 * Aliasing supported.
156 */
nn_rshift_fixedlen(nn_t out,nn_src_t in,bitcnt_t cnt)157 int nn_rshift_fixedlen(nn_t out, nn_src_t in, bitcnt_t cnt)
158 {
159 int ipos, opos, dec, ret;
160 bitcnt_t lshift, hshift;
161 u8 owlen, iwlen;
162
163 ret = nn_check_initialized(in); EG(ret, err);
164 ret = nn_check_initialized(out); EG(ret, err);
165 owlen = out->wlen;
166 iwlen = in->wlen;
167
168 dec = cnt / WORD_BITS;
169 lshift = cnt % WORD_BITS;
170 hshift = (bitcnt_t)(WORD_BITS - lshift);
171
172 for (opos = 0; opos < owlen; opos++) {
173 word_t hipart = 0, lopart = 0;
174
175 ipos = opos + dec;
176 if ((ipos >= 0) && (ipos < iwlen)) {
177 lopart = WRSHIFT(in->val[ipos], lshift);
178 }
179
180 ipos = opos + dec + 1;
181 if ((ipos >= 0) && (ipos < iwlen)) {
182 hipart = WLSHIFT(in->val[ipos], hshift);
183 }
184
185 out->val[opos] = hipart | lopart;
186 }
187
188 err:
189 return ret;
190 }
191
192 /*
193 * nn_rshift: right logical shift in N, i.e. compute out = (in >> cnt).
194 *
195 * Aliasing is possible for 'in' and 'out', i.e. x >>= cnt can be computed
196 * using nn_rshift_fixedlen(x, x, cnt).
197 *
198 * The function supports 'in' and 'out' parameters of differents sizes.
199 *
200 * The operation time of the function depends on the size of 'in' and
201 * 'out' parameters and the value of 'cnt'. It does not depend on the
202 * value of 'in'.
203 * It is to be noted that the function adapts the output size to
204 * the input size and the shift bit count, i.e. out bit lenth is roughly
205 * equal to input bit length minus cnt.
206 *
207 * The function returns 0 on success, -1 on error.
208 *
209 * Aliasing supported.
210 */
nn_rshift(nn_t out,nn_src_t in,bitcnt_t cnt)211 int nn_rshift(nn_t out, nn_src_t in, bitcnt_t cnt)
212 {
213 int ipos, opos, dec, ret;
214 bitcnt_t lshift, hshift;
215 u8 owlen, iwlen;
216 bitcnt_t blen;
217
218 ret = nn_check_initialized(in); EG(ret, err);
219 iwlen = in->wlen;
220 /* Initialize output if no aliasing is used */
221 if (out != in) {
222 ret = nn_init(out, 0); EG(ret, err);
223 }
224
225 dec = cnt / WORD_BITS;
226 lshift = cnt % WORD_BITS;
227 hshift = (bitcnt_t)(WORD_BITS - lshift);
228
229 /* Adapt output length accordingly */
230 ret = nn_bitlen(in, &blen); EG(ret, err);
231 if (cnt > blen) {
232 owlen = 0;
233 } else {
234 owlen = (u8)BIT_LEN_WORDS(blen - cnt);
235 }
236 /* Adapt output length in out */
237 out->wlen = owlen;
238
239 for (opos = 0; opos < owlen; opos++) {
240 word_t hipart = 0, lopart = 0;
241
242 ipos = opos + dec;
243 if ((ipos >= 0) && (ipos < iwlen)) {
244 lopart = WRSHIFT(in->val[ipos], lshift);
245 }
246
247 ipos = opos + dec + 1;
248 if ((ipos >= 0) && (ipos < iwlen)) {
249 hipart = WLSHIFT(in->val[ipos], hshift);
250 }
251
252 out->val[opos] = hipart | lopart;
253 }
254
255 /*
256 * Zero the output upper part now that we don't need it anymore
257 * NB: as we cannot use our normalize helper here (since a consistency
258 * check is done on wlen and upper part), we have to do this manually
259 */
260 for (opos = owlen; opos < NN_MAX_WORD_LEN; opos++) {
261 out->val[opos] = 0;
262 }
263
264 err:
265 return ret;
266 }
267
268 /*
269 * This function right rotates the input NN value by the value 'cnt' on the
270 * bitlen basis. The function does it in the following way; right rotation
271 * of x by cnt is "simply": (x >> cnt) ^ (x << (bitlen - cnt))
272 *
273 * The function returns 0 on success, -1 on error.
274 *
275 * Aliasing supported.
276 */
nn_rrot(nn_t out,nn_src_t in,bitcnt_t cnt,bitcnt_t bitlen)277 int nn_rrot(nn_t out, nn_src_t in, bitcnt_t cnt, bitcnt_t bitlen)
278 {
279 u8 owlen = (u8)BIT_LEN_WORDS(bitlen);
280 int ret;
281 nn tmp;
282 tmp.magic = WORD(0);
283
284 MUST_HAVE((bitlen <= NN_MAX_BIT_LEN), ret, err);
285 MUST_HAVE((cnt < bitlen), ret, err);
286
287 ret = nn_check_initialized(in); EG(ret, err);
288 ret = nn_init(&tmp, 0); EG(ret, err);
289 ret = nn_lshift(&tmp, in, (bitcnt_t)(bitlen - cnt)); EG(ret, err);
290 ret = nn_set_wlen(&tmp, owlen); EG(ret, err);
291 ret = nn_rshift(out, in, cnt); EG(ret, err);
292 ret = nn_set_wlen(out, owlen); EG(ret, err);
293 ret = nn_xor(out, out, &tmp); EG(ret, err);
294
295 /* Mask the last word if necessary */
296 if (((bitlen % WORD_BITS) != 0) && (out->wlen > 0)) {
297 /* shift operation below is ok (less than WORD_BITS) */
298 word_t mask = (word_t)(((word_t)(WORD(1) << (bitlen % WORD_BITS))) - 1);
299 out->val[out->wlen - 1] &= mask;
300 }
301
302 err:
303 nn_uninit(&tmp);
304
305 return ret;
306 }
307
308 /*
309 * This function left rotates the input NN value by the value 'cnt' on the
310 * bitlen basis. The function does it in the following way; Left rotation
311 * of x by cnt is "simply": (x << cnt) ^ (x >> (bitlen - cnt))
312 *
313 * The function returns 0 on success, -1 on error.
314 *
315 * Aliasing supported.
316 */
nn_lrot(nn_t out,nn_src_t in,bitcnt_t cnt,bitcnt_t bitlen)317 int nn_lrot(nn_t out, nn_src_t in, bitcnt_t cnt, bitcnt_t bitlen)
318 {
319 u8 owlen = (u8)BIT_LEN_WORDS(bitlen);
320 int ret;
321 nn tmp;
322 tmp.magic = WORD(0);
323
324 MUST_HAVE(!(bitlen > NN_MAX_BIT_LEN), ret, err);
325 MUST_HAVE(!(cnt >= bitlen), ret, err);
326
327 ret = nn_check_initialized(in); EG(ret, err);
328 ret = nn_init(&tmp, 0); EG(ret, err);
329 ret = nn_lshift(&tmp, in, cnt); EG(ret, err);
330 ret = nn_set_wlen(&tmp, owlen); EG(ret, err);
331 ret = nn_rshift(out, in, (bitcnt_t)(bitlen - cnt)); EG(ret, err);
332 ret = nn_set_wlen(out, owlen); EG(ret, err);
333 ret = nn_xor(out, out, &tmp); EG(ret, err);
334
335 /* Mask the last word if necessary */
336 if (((bitlen % WORD_BITS) != 0) && (out->wlen > 0)) {
337 word_t mask = (word_t)(((word_t)(WORD(1) << (bitlen % WORD_BITS))) - 1);
338 out->val[out->wlen - 1] &= mask;
339 }
340
341 err:
342 nn_uninit(&tmp);
343
344 return ret;
345 }
346
347 /*
348 * Compute XOR between B and C and put the result in A. B and C must be
349 * initialized. Aliasing is supported, i.e. A can be one of the parameter B or
350 * C. If aliasing is not used, A will be initialized by the function. Function
351 * execution time depends on the word length of larger parameter but not on its
352 * particular value.
353 *
354 * The function returns 0 on success, -1 on error.
355 *
356 * Aliasing supported.
357 */
nn_xor(nn_t A,nn_src_t B,nn_src_t C)358 int nn_xor(nn_t A, nn_src_t B, nn_src_t C)
359 {
360 int ret;
361 u8 i;
362
363 ret = nn_check_initialized(B); EG(ret, err);
364 ret = nn_check_initialized(C); EG(ret, err);
365
366 /* Initialize the output if no aliasing is used */
367 if ((A != B) && (A != C)) {
368 ret = nn_init(A, 0); EG(ret, err);
369 }
370
371 /* Set output wlen accordingly */
372 A->wlen = (C->wlen < B->wlen) ? B->wlen : C->wlen;
373
374 for (i = 0; i < A->wlen; i++) {
375 A->val[i] = (B->val[i] ^ C->val[i]);
376 }
377
378 err:
379 return ret;
380 }
381
382 /*
383 * Compute logical OR between B and C and put the result in A. B and C must be
384 * initialized. Aliasing is supported, i.e. A can be one of the parameter B or
385 * C. If aliasing is not used, A will be initialized by the function. Function
386 * execution time depends on the word length of larger parameter but not on its
387 * particular value.
388 *
389 * The function returns 0 on success, -1 on error.
390 *
391 * Aliasing supported.
392 */
nn_or(nn_t A,nn_src_t B,nn_src_t C)393 int nn_or(nn_t A, nn_src_t B, nn_src_t C)
394 {
395 int ret;
396 u8 i;
397
398 ret = nn_check_initialized(B); EG(ret, err);
399 ret = nn_check_initialized(C); EG(ret, err);
400
401 /* Initialize the output if no aliasing is used */
402 if ((A != B) && (A != C)) {
403 ret = nn_init(A, 0); EG(ret, err);
404 }
405
406 /* Set output wlen accordingly */
407 A->wlen = (C->wlen < B->wlen) ? B->wlen : C->wlen;
408
409 for (i = 0; i < A->wlen; i++) {
410 A->val[i] = (B->val[i] | C->val[i]);
411 }
412
413 err:
414 return ret;
415 }
416
417 /*
418 * Compute logical AND between B and C and put the result in A. B and C must be
419 * initialized. Aliasing is supported, i.e. A can be one of the parameter B or
420 * C. If aliasing is not used, A will be initialized by the function. Function
421 * execution time depends on the word length of larger parameter but not on its
422 * particular value.
423 *
424 * The function returns 0 on success, -1 on error.
425 *
426 * Aliasing supported.
427 */
nn_and(nn_t A,nn_src_t B,nn_src_t C)428 int nn_and(nn_t A, nn_src_t B, nn_src_t C)
429 {
430 int ret;
431 u8 i;
432
433 ret = nn_check_initialized(B); EG(ret, err);
434 ret = nn_check_initialized(C); EG(ret, err);
435
436 /* Initialize the output if no aliasing is used */
437 if ((A != B) && (A != C)) {
438 ret = nn_init(A, 0); EG(ret, err);
439 }
440
441 /* Set output wlen accordingly */
442 A->wlen = (C->wlen < B->wlen) ? B->wlen : C->wlen;
443
444 for (i = 0; i < A->wlen; i++) {
445 A->val[i] = (B->val[i] & C->val[i]);
446 }
447
448 err:
449 return ret;
450 }
451
452 /*
453 * Compute logical NOT of B and put the result in A. B must be initialized.
454 * Aliasing is supported. If aliasing is not used, A will be initialized by
455 * the function.
456 *
457 * The function returns 0 on success, -1 on error.
458 *
459 * Aliasing supported.
460 */
nn_not(nn_t A,nn_src_t B)461 int nn_not(nn_t A, nn_src_t B)
462 {
463 int ret;
464 u8 i;
465
466 ret = nn_check_initialized(B); EG(ret, err);
467
468 /* Initialize the output if no aliasing is used */
469 if (A != B) {
470 ret = nn_init(A, 0); EG(ret, err);
471 }
472
473 /* Set output wlen accordingly */
474 A->wlen = B->wlen;
475
476 for (i = 0; i < A->wlen; i++) {
477 A->val[i] = (word_t)(~(B->val[i]));
478 }
479
480 err:
481 return ret;
482 }
483
484 /* Count leading zeros of a word. This is constant time */
wclz(word_t A)485 ATTRIBUTE_WARN_UNUSED_RET static u8 wclz(word_t A)
486 {
487 u8 cnt = WORD_BITS, over = 0;
488 int i;
489
490 for (i = (WORD_BITS - 1); i >= 0; i--) {
491 /* i is less than WORD_BITS so shift operations below are ok */
492 u8 mask = (u8)(((A & (WORD(1) << i)) >> i) & 0x1);
493 over |= mask;
494 cnt = (u8)(cnt - over);
495 }
496
497 return cnt;
498 }
499
500 /*
501 * Count leading zeros of an initialized nn. This is NOT constant time. The
502 * function returns 0 on success, -1 on error. On success, the number of
503 * leading zeroes is available in 'lz'. 'lz' is not meaningful on error.
504 */
nn_clz(nn_src_t in,bitcnt_t * lz)505 int nn_clz(nn_src_t in, bitcnt_t *lz)
506 {
507 bitcnt_t cnt = 0;
508 int ret;
509 u8 i;
510
511 /* Sanity check */
512 MUST_HAVE((lz != NULL), ret, err);
513 ret = nn_check_initialized(in); EG(ret, err);
514
515 for (i = in->wlen; i > 0; i--) {
516 if (in->val[i - 1] == 0) {
517 cnt = (bitcnt_t)(cnt + WORD_BITS);
518 } else {
519 cnt = (bitcnt_t)(cnt + wclz(in->val[i - 1]));
520 break;
521 }
522 }
523 *lz = cnt;
524
525 err:
526 return ret;
527 }
528
529 /*
530 * Compute bit length of given nn. This is NOT constant-time. The
531 * function returns 0 on success, -1 on error. On success, the bit length
532 * of 'in' is available in 'blen'. 'blen' is not meaningful on error.
533 */
nn_bitlen(nn_src_t in,bitcnt_t * blen)534 int nn_bitlen(nn_src_t in, bitcnt_t *blen)
535 {
536 bitcnt_t _blen = 0;
537 int ret;
538 u8 i;
539
540 /* Sanity check */
541 MUST_HAVE((blen != NULL), ret, err);
542 ret = nn_check_initialized(in); EG(ret, err);
543
544 for (i = in->wlen; i > 0; i--) {
545 if (in->val[i - 1] != 0) {
546 _blen = (bitcnt_t)((i * WORD_BITS) - wclz(in->val[i - 1]));
547 break;
548 }
549 }
550 (*blen) = _blen;
551
552 err:
553 return ret;
554 }
555
556 /*
557 * On success (return value is 0), the function provides via 'bitval' the value
558 * of the bit at position 'bit' in 'in' nn. 'bitval' in not meaningful error
559 * (when return value is -1).
560 */
nn_getbit(nn_src_t in,bitcnt_t bit,u8 * bitval)561 int nn_getbit(nn_src_t in, bitcnt_t bit, u8 *bitval)
562 {
563 bitcnt_t widx = bit / WORD_BITS;
564 u8 bidx = bit % WORD_BITS;
565 int ret;
566
567 /* Sanity check */
568 MUST_HAVE((bitval != NULL), ret, err);
569 ret = nn_check_initialized(in); EG(ret, err);
570 MUST_HAVE((bit < NN_MAX_BIT_LEN), ret, err);
571
572 /* bidx is less than WORD_BITS so shift operations below are ok */
573 (*bitval) = (u8)((((in->val[widx]) & (WORD(1) << bidx)) >> bidx) & 0x1);
574
575 err:
576 return ret;
577 }
578