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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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