nn_add.c
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 19 /* 20 * This module provides conditional addition and subtraction functions between 21 * two nn: 22 * 23 * o out = in1 +/- in2 if cnd is not zero. 24 * o out = in1 if cnd is zero. 25 * 26 * The time taken by the operation does not depend on cnd value, i.e. it is 27 * constant time for that specific factor, nor on the values of in1 and in2. 28 * It still depends on the maximal length of in1 and in2. 29 * 30 * Common addition and subtraction functions are derived from those conditional 31 * versions. 32 */ 33 34 /* 35 * Conditionally adds 'in2' to 'in1' according to "cnd", storing the result 36 * in "out" and returning the carry in 'carry' parameter on success. This 37 * is the lowest level function for conditional addition. The function 38 * returns 0 on success, -1 on error. 39 * 40 * Note that unlike "usual" addition, the function is *in general* not 41 * commutative, i.e. "_nn_cnd_add(cnd, out, in1, in2)" is not equivalent 42 * to "_nn_cnd_add(cnd, out, in2, in1)". It is commutative though if "cnd" 43 * is not zero or 'in1' == 'in2'. 44 * 45 * Aliasing of inputs and output is possible. "out" is initialized if needed, 46 * that is if not aliased to 'in1' or 'in2'. The length of "out" is set to 47 * the maximal length of 'in1' and 'in2'. Note that both 'in1' and 'in2' will 48 * be read to this maximal length. As our memory managment model assumes that 49 * storage arrays only contains zeros past the "wlen" index, correct results 50 * will be produced. The length of 'out' is not normalized on return. 51 * 52 * The runtime of this function should not depend on: 53 * o the value of "cnd", 54 * o the data stored in 'in1' and 'in2'. 55 * It depends on: 56 * o the maximal length of 'in1' and 'in2'. 57 * 58 * This function is for internal use only. 59 */ 60 ATTRIBUTE_WARN_UNUSED_RET static int _nn_cnd_add(int cnd, nn_t out, nn_src_t in1, nn_src_t in2, 61 word_t *carry) 62 { 63 word_t tmp, carry1, carry2, _carry = WORD(0); 64 word_t mask = WORD_MASK_IFNOTZERO(cnd); 65 u8 i, loop_wlen; 66 int ret; 67 68 MUST_HAVE((carry != NULL), ret, err); 69 ret = nn_check_initialized(in1); EG(ret, err); 70 ret = nn_check_initialized(in2); EG(ret, err); 71 72 /* Handle aliasing */ 73 loop_wlen = LOCAL_MAX(in1->wlen, in2->wlen); 74 if ((out != in1) && (out != in2)) { 75 ret = nn_init(out, (u16)(loop_wlen * WORD_BYTES)); EG(ret, err); 76 } else { 77 ret = nn_set_wlen(out, loop_wlen); EG(ret, err); 78 } 79 80 /* Perform addition one word at a time, propagating the carry. */ 81 for (i = 0; i < loop_wlen; i++) { 82 tmp = (word_t)(in1->val[i] + (in2->val[i] & mask)); 83 carry1 = (word_t)(tmp < in1->val[i]); 84 out->val[i] = (word_t)(tmp + _carry); 85 carry2 = (word_t)(out->val[i] < tmp); 86 /* There is at most one carry going out. */ 87 _carry = (word_t)(carry1 | carry2); 88 } 89 90 (*carry) = _carry; 91 92 err: 93 return ret; 94 } 95 96 /* 97 * Conditionally adds 'in2' to 'in1' according to "cnd", storing the result 98 * in "out", including the potential carry overflowing past the maximal 99 * length of 'in1' and 'in2'. It is user responsibility to ensure that the 100 * resulting nn will not be higher than what can be supported. This is 101 * for instance guaranteed if both in1->wlen and in2->wlen are less than 102 * NN_MAX_WORD_LEN. Otherwise the function will error out which could leak 103 * information. 104 * 105 * Note that the length of the output depends the lengths of the inputs, 106 * but also on their values. 107 * It is the user responsibility to use this function carefully when 108 * constant time of an algorithm using this function is seeked. 109 * This choice was preferred above unconditionally increasing 110 * the length of the output by one, to ease the management of length 111 * explosion when multiple additions are performed. 112 * For finer carry propagation and length control the internal "_nn_cnd_add" 113 * function can be used. 114 * 115 * See "_nn_cnd_add" documentation above for further details. 116 * 117 * The function returns 0 on success, -1 on error. 118 */ 119 int nn_cnd_add(int cnd, nn_t out, nn_src_t in1, nn_src_t in2) 120 { 121 word_t carry; 122 int ret; 123 124 ret = _nn_cnd_add(cnd, out, in1, in2, &carry); EG(ret, err); 125 126 /* We cannot allow a non-zero carry if out->wlen is at its limit */ 127 MUST_HAVE(((out->wlen != NN_MAX_WORD_LEN) || (!carry)), ret, err); 128 129 if (out->wlen != NN_MAX_WORD_LEN) { 130 /* 131 * To maintain constant time, we perform carry addition in all 132 * cases. If carry is 0, no change is performed in practice, 133 * neither to 'out' value, nor to its length. 134 * Note that the length of the output can vary and make 135 * the time taken by further operations on it also vary. 136 */ 137 out->val[out->wlen] = carry; 138 out->wlen = (u8)(out->wlen + carry); 139 } 140 141 err: 142 return ret; 143 } 144 145 /* 146 * Unconditionally adds 'in2' to 'in1', storing the result in "out", 147 * including the potential carry overflowing past the maximal length of 148 * 'in1' and 'in2'. The function returns 0 on success, -1 on error. 149 * 150 * Note that the length of the output depends the lengths of the inputs, 151 * but also on their values. 152 * It is the user responsibility to use this function carefully when 153 * constant time of an algorithm using this function is seeked. 154 * 155 * See "_nn_cnd_add" documentation for further details. 156 * 157 */ 158 int nn_add(nn_t out, nn_src_t in1, nn_src_t in2) 159 { 160 return nn_cnd_add(1, out, in1, in2); 161 } 162 163 /* 164 * Compute out = in1 + w where 'in1' is an initialized nn and 'w' a word. It is 165 * caller responsibility to ensure that the result will fit in a nn (This is 166 * for instance guaranteed if 'in1' wlen is less than NN_MAX_WORD_LEN). The 167 * function returns 0 on succes, -1 on error. 168 * 169 * The result is stored in 'out' parameter. 'out' is initialized if needed (i.e. 170 * in case aliasing is not used) and is not normalized on return. 171 * 172 * Note that the length of the output depends the lengths of the inputs, 173 * but also on their values. 174 * It is the user responsibility to use this function carefully when 175 * constant time of an algorithm using this function is seeked. 176 * 177 * This function is for internal use only. 178 */ 179 ATTRIBUTE_WARN_UNUSED_RET static int nn_add_word(nn_t out, nn_src_t in1, word_t w) 180 { 181 word_t carry, tmp; 182 u8 i, n_wlen; 183 int ret; 184 185 ret = nn_check_initialized(in1); EG(ret, err); 186 187 /* Handle aliasing */ 188 n_wlen = in1->wlen; 189 if (out != in1) { 190 ret = nn_init(out, (u16)(n_wlen * WORD_BYTES)); EG(ret, err); 191 } else { 192 ret = nn_set_wlen(out, n_wlen); EG(ret, err); 193 } 194 195 /* No matter its value, propagate the carry. */ 196 carry = w; 197 for (i = 0; i < n_wlen; i++) { 198 tmp = (word_t)(in1->val[i] + carry); 199 carry = (word_t)(tmp < in1->val[i]); 200 out->val[i] = tmp; 201 } 202 203 MUST_HAVE(((out->wlen != NN_MAX_WORD_LEN) || (!carry)), ret, err); 204 if (out->wlen != NN_MAX_WORD_LEN) { 205 /* 206 * To maintain constant time, we perform carry addition in all 207 * cases. If carry is 0, no change is performed in practice, 208 * neither to 'out' value, nor to its length. 209 * Note that the length of the output can vary and make 210 * the time taken by further operations on it will vary. 211 */ 212 out->val[out->wlen] = carry; 213 out->wlen = (u8)(out->wlen + carry); 214 } 215 216 err: 217 return ret; 218 } 219 220 /* 221 * Compute out = in1 + 1. Aliasing is supported i.e. nn_inc(in1, in1) works as 222 * expected and provides in1++. It is caller responsibility to ensure that the 223 * result will fit in a nn (This is for instance guaranteed if 'in1' wlen is 224 * less than NN_MAX_WORD_LEN). The function returns 0 on success, -1 on error. 225 * 226 * Note that the length of the output depends the lengths of the inputs, 227 * but also on their values. 228 * It is the user responsibility to use this function carefully when 229 * constant time of an algorithm using this function is seeked. 230 */ 231 int nn_inc(nn_t out, nn_src_t in1) 232 { 233 return nn_add_word(out, in1, WORD(1)); 234 } 235 236 /* 237 * Conditionally subtracts 'in2' from 'in1' according to "cnd", 238 * storing the result in "out": 239 * o out = in1 - in2 if cnd is not zero. 240 * o out = in1 if cnd is zero. 241 * 242 * 'in1' and 'in2' must point to initialized nn, such that the value of 'in1' 243 * is larger than 'in2'. Aliasing is supported, i.e. 'out' can point to the 244 * same nn as 'in1' or 'in2'. If aliasing is not used, 'out' is initialized by 245 * the function. The length of 'out' is set to the length of 'in1' 246 * and is not normalized on return. 247 * 248 * The function returns 0 on success, -1 on error. 249 */ 250 int nn_cnd_sub(int cnd, nn_t out, nn_src_t in1, nn_src_t in2) 251 { 252 word_t tmp, borrow1, borrow2, borrow = WORD(0); 253 word_t mask = WORD_MASK_IFNOTZERO(cnd); 254 u8 loop_wlen, i; 255 int ret; 256 257 ret = nn_check_initialized(in1); EG(ret, err); 258 ret = nn_check_initialized(in2); EG(ret, err); 259 260 /* Handle aliasing */ 261 loop_wlen = LOCAL_MAX(in1->wlen, in2->wlen); 262 if ((out != in1) && (out != in2)) { 263 ret = nn_init(out, (u16)(loop_wlen * WORD_BYTES)); EG(ret, err); 264 } else { 265 ret = nn_set_wlen(out, in1->wlen); EG(ret, err); 266 } 267 268 /* Perform subtraction one word at a time, propagating the borrow. */ 269 for (i = 0; i < loop_wlen; i++) { 270 tmp = (word_t)(in1->val[i] - (in2->val[i] & mask)); 271 borrow1 = (word_t)(tmp > in1->val[i]); 272 out->val[i] = (word_t)(tmp - borrow); 273 borrow2 = (word_t)(out->val[i] > tmp); 274 /* There is at most one borrow going out. */ 275 borrow = (word_t)(borrow1 | borrow2); 276 } 277 278 /* We only support the in1 >= in2 case */ 279 ret = (borrow != WORD(0)) ? -1 : 0; 280 281 err: 282 return ret; 283 } 284 285 /* Same as the one above, but the subtraction is performed unconditionally. */ 286 int nn_sub(nn_t out, nn_src_t in1, nn_src_t in2) 287 { 288 return nn_cnd_sub(1, out, in1, in2); 289 } 290 291 /* 292 * Compute out = in1 - 1 where in1 is a *positive* integer. Aliasing is 293 * supported i.e. nn_dec(A, A) works as expected and provides A -= 1. 294 * The function returns 0 on success, -1 on error. 295 */ 296 int nn_dec(nn_t out, nn_src_t in1) 297 { 298 const word_t w = WORD(1); 299 word_t tmp, borrow; 300 u8 n_wlen, i; 301 int ret; 302 303 ret = nn_check_initialized(in1); EG(ret, err); 304 n_wlen = in1->wlen; 305 ret = nn_set_wlen(out, n_wlen); EG(ret, err); 306 307 /* Perform subtraction w/ provided word and propagate the borrow */ 308 borrow = w; 309 for (i = 0; i < n_wlen; i++) { 310 tmp = (word_t)(in1->val[i] - borrow); 311 borrow = (word_t)(tmp > in1->val[i]); 312 out->val[i] = tmp; 313 } 314 315 ret = (borrow != WORD(0)) ? -1 : 0; 316 317 err: 318 return ret; 319 } 320 321 /* 322 * The following functions handle modular arithmetic. Our outputs sizes do not 323 * need a "normalization" since everything will be bounded by the modular number 324 * size. 325 * 326 * Warning: the following functions are only useful when the inputs are < p, 327 * i.e. we suppose that the input are already reduced modulo p. These primitives 328 * are mostly useful for the Fp layer. Even though they give results when 329 * applied to inputs >= p, there is no guarantee that the result is indeed < p 330 * or correct whatsoever. 331 */ 332 333 /* 334 * Compute out = in1 + in2 mod p. The function returns 0 on success, -1 on 335 * error. 336 * 337 * Aliasing not fully supported, for internal use only. 338 */ 339 static int _nn_mod_add(nn_t out, nn_src_t in1, nn_src_t in2, nn_src_t p) 340 { 341 int ret, larger, cmp; 342 343 ret = nn_check_initialized(in1); EG(ret, err); 344 ret = nn_check_initialized(in2); EG(ret, err); 345 ret = nn_check_initialized(p); EG(ret, err); 346 MUST_HAVE((p->wlen < NN_MAX_WORD_LEN), ret, err); /* otherwise carry could overflow */ 347 SHOULD_HAVE((!nn_cmp(in1, p, &cmp)) && (cmp < 0), ret, err); /* a SHOULD_HAVE as documented above */ 348 SHOULD_HAVE((!nn_cmp(in2, p, &cmp)) && (cmp < 0), ret, err); /* a SHOULD_HAVE as documented above */ 349 350 ret = nn_add(out, in1, in2); EG(ret, err); 351 /* 352 * If previous addition extends out->wlen, this may have an effect on 353 * computation time of functions below. For that reason, we always 354 * normalize out->wlen to p->wlen + 1. Its length is set to that of 355 * p after the computations. 356 * 357 * We could also use _nn_cnd_add to catch the carry and deal 358 * with p's of size NN_MAX_WORD_LEN. 359 * It is still painful because we have no constraint on the lengths 360 * of in1 and in2 so getting a carry out does not necessarily mean 361 * that the sum is larger than p... 362 */ 363 ret = nn_set_wlen(out, (u8)(p->wlen + 1)); EG(ret, err); 364 ret = nn_cmp(out, p, &cmp); EG(ret, err); 365 larger = (cmp >= 0); 366 ret = nn_cnd_sub(larger, out, out, p); EG(ret, err); 367 ret = nn_set_wlen(out, p->wlen); 368 369 err: 370 return ret; 371 } 372 373 /* 374 * Compute out = in1 + in2 mod p. The function returns 0 on success, -1 on 375 * error. 376 * 377 * Aliasing is supported. 378 */ 379 int nn_mod_add(nn_t out, nn_src_t in1, nn_src_t in2, nn_src_t p) 380 { 381 int ret; 382 383 if(out == p){ 384 nn p_cpy; 385 p_cpy.magic = WORD(0); 386 387 ret = nn_copy(&p_cpy, p); EG(ret, err1); 388 ret = _nn_mod_add(out, in1, in2, &p_cpy); 389 390 err1: 391 nn_uninit(&p_cpy); 392 EG(ret, err); 393 } 394 else{ 395 ret = _nn_mod_add(out, in1, in2, p); 396 } 397 398 err: 399 return ret; 400 } 401 402 /* 403 * Compute out = in1 + 1 mod p. The function returns 0 on success, -1 on error. 404 * 405 * Aliasing not fully supported, for internal use only. 406 */ 407 static int _nn_mod_inc(nn_t out, nn_src_t in1, nn_src_t p) 408 { 409 int larger, ret, cmp; 410 411 ret = nn_check_initialized(in1); EG(ret, err); 412 ret = nn_check_initialized(p); EG(ret, err); 413 MUST_HAVE((p->wlen < NN_MAX_WORD_LEN), ret, err); /* otherwise carry could overflow */ 414 SHOULD_HAVE((!nn_cmp(in1, p, &cmp)) && (cmp < 0), ret, err); /* a SHOULD_HAVE as documented above */ 415 416 ret = nn_inc(out, in1); EG(ret, err); 417 ret = nn_set_wlen(out, (u8)(p->wlen + 1)); EG(ret, err); /* see comment in nn_mod_add() */ 418 ret = nn_cmp(out, p, &cmp); EG(ret, err); 419 larger = (cmp >= 0); 420 ret = nn_cnd_sub(larger, out, out, p); EG(ret, err); 421 ret = nn_set_wlen(out, p->wlen); 422 423 err: 424 return ret; 425 } 426 427 /* 428 * Compute out = in1 + 1 mod p. The function returns 0 on success, -1 on error. 429 * 430 * Aliasing supported. 431 */ 432 int nn_mod_inc(nn_t out, nn_src_t in1, nn_src_t p) 433 { 434 int ret; 435 436 if(out == p){ 437 nn p_cpy; 438 p_cpy.magic = WORD(0); 439 440 ret = nn_copy(&p_cpy, p); EG(ret, err1); 441 ret = _nn_mod_inc(out, in1, &p_cpy); 442 443 err1: 444 nn_uninit(&p_cpy); 445 EG(ret, err); 446 } 447 else{ 448 ret = _nn_mod_inc(out, in1, p); 449 } 450 451 err: 452 return ret; 453 454 } 455 456 /* 457 * Compute out = in1 - in2 mod p. The function returns 0 on success, -1 on 458 * error. 459 * 460 * Aliasing not supported, for internal use only. 461 */ 462 static int _nn_mod_sub(nn_t out, nn_src_t in1, nn_src_t in2, nn_src_t p) 463 { 464 int smaller, ret, cmp; 465 nn_src_t in2_; 466 nn in2_cpy; 467 in2_cpy.magic = WORD(0); 468 469 ret = nn_check_initialized(in1); EG(ret, err); 470 ret = nn_check_initialized(in2); EG(ret, err); 471 ret = nn_check_initialized(p); EG(ret, err); 472 MUST_HAVE((p->wlen < NN_MAX_WORD_LEN), ret, err); /* otherwise carry could overflow */ 473 SHOULD_HAVE((!nn_cmp(in1, p, &cmp)) && (cmp < 0), ret, err); /* a SHOULD_HAVE as documented above */ 474 SHOULD_HAVE((!nn_cmp(in2, p, &cmp)) && (cmp < 0), ret, err); /* a SHOULD_HAVE as documented above */ 475 476 /* Handle the case where in2 and out are aliased */ 477 if (in2 == out) { 478 ret = nn_copy(&in2_cpy, in2); EG(ret, err); 479 in2_ = &in2_cpy; 480 } else { 481 ret = nn_init(&in2_cpy, 0); EG(ret, err); 482 in2_ = in2; 483 } 484 485 /* The below trick is used to avoid handling of "negative" numbers. */ 486 ret = nn_cmp(in1, in2_, &cmp); EG(ret, err); 487 smaller = (cmp < 0); 488 ret = nn_cnd_add(smaller, out, in1, p); EG(ret, err); 489 ret = nn_set_wlen(out, (u8)(p->wlen + 1)); EG(ret, err);/* See Comment in nn_mod_add() */ 490 ret = nn_sub(out, out, in2_); EG(ret, err); 491 ret = nn_set_wlen(out, p->wlen); 492 493 err: 494 nn_uninit(&in2_cpy); 495 496 return ret; 497 } 498 499 /* 500 * Compute out = in1 - in2 mod p. The function returns 0 on success, -1 on 501 * error. 502 * 503 * Aliasing supported. 504 */ 505 int nn_mod_sub(nn_t out, nn_src_t in1, nn_src_t in2, nn_src_t p) 506 { 507 int ret; 508 509 if(out == p){ 510 nn p_cpy; 511 p_cpy.magic = WORD(0); 512 513 ret = nn_copy(&p_cpy, p); EG(ret, err1); 514 ret = _nn_mod_sub(out, in1, in2, &p_cpy); 515 516 err1: 517 nn_uninit(&p_cpy); 518 EG(ret, err); 519 } 520 else{ 521 ret = _nn_mod_sub(out, in1, in2, p); 522 } 523 524 err: 525 return ret; 526 } 527 528 /* 529 * Compute out = in1 - 1 mod p. The function returns 0 on success, -1 on error 530 * 531 * Aliasing not supported, for internal use only. 532 */ 533 static int _nn_mod_dec(nn_t out, nn_src_t in1, nn_src_t p) 534 { 535 int ret, iszero, cmp; 536 537 ret = nn_check_initialized(in1); EG(ret, err); 538 ret = nn_check_initialized(p); EG(ret, err); 539 MUST_HAVE((p->wlen < NN_MAX_WORD_LEN), ret, err); /* otherwise carry could overflow */ 540 FORCE_USED_VAR(cmp); /* nop to silence possible warning with macro below */ 541 SHOULD_HAVE((!nn_cmp(in1, p, &cmp)) && (cmp < 0), ret, err); /* a SHOULD_HAVE; Documented above */ 542 543 /* The below trick is used to avoid handling of "negative" numbers. */ 544 ret = nn_iszero(in1, &iszero); EG(ret, err); 545 ret = nn_cnd_add(iszero, out, in1, p); EG(ret, err); 546 ret = nn_set_wlen(out, (u8)(p->wlen + 1)); EG(ret, err); /* See Comment in nn_mod_add() */ 547 ret = nn_dec(out, out); EG(ret, err); 548 ret = nn_set_wlen(out, p->wlen); 549 550 err: 551 return ret; 552 } 553 554 /* 555 * Compute out = in1 - 1 mod p. The function returns 0 on success, -1 on error 556 * 557 * Aliasing supported. 558 */ 559 int nn_mod_dec(nn_t out, nn_src_t in1, nn_src_t p) 560 { 561 int ret; 562 563 if(out == p){ 564 nn p_cpy; 565 p_cpy.magic = WORD(0); 566 567 ret = nn_copy(&p_cpy, p); EG(ret, err1); 568 ret = _nn_mod_dec(out, in1, &p_cpy); 569 570 err1: 571 nn_uninit(&p_cpy); 572 EG(ret, err); 573 } 574 else{ 575 ret = _nn_mod_dec(out, in1, p); 576 } 577 578 err: 579 return ret; 580 } 581 582 /* 583 * Compute out = -in mod p. The function returns 0 on success, -1 on error. 584 * Because we only support positive integers, we compute 585 * out = p - in (except when value is 0). 586 * 587 * We suppose that in is already reduced modulo p. 588 * 589 * Aliasing is supported. 590 * 591 */ 592 int nn_mod_neg(nn_t out, nn_src_t in, nn_src_t p) 593 { 594 int ret, cmp, iszero; 595 596 FORCE_USED_VAR(cmp); 597 598 ret = nn_check_initialized(in); EG(ret, err); 599 ret = nn_check_initialized(p); EG(ret, err); 600 601 SHOULD_HAVE((!nn_cmp(in, p, &cmp)) && (cmp < 0), ret, err); /* a SHOULD_HAVE; Documented above */ 602 603 ret = nn_iszero(in, &iszero); EG(ret, err); 604 if (iszero) { 605 ret = nn_init(out, 0); EG(ret, err); 606 ret = nn_zero(out); EG(ret, err); 607 } else { 608 ret = nn_sub(out, p, in); EG(ret, err); 609 } 610 611 err: 612 return ret; 613 }