bn_intern.c 5.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195
  1. /*
  2. * Copyright 2014-2016 The OpenSSL Project Authors. All Rights Reserved.
  3. *
  4. * Licensed under the OpenSSL license (the "License"). You may not use
  5. * this file except in compliance with the License. You can obtain a copy
  6. * in the file LICENSE in the source distribution or at
  7. * https://www.openssl.org/source/license.html
  8. */
  9. #include "internal/cryptlib.h"
  10. #include "bn_lcl.h"
  11. /*
  12. * Determine the modified width-(w+1) Non-Adjacent Form (wNAF) of 'scalar'.
  13. * This is an array r[] of values that are either zero or odd with an
  14. * absolute value less than 2^w satisfying
  15. * scalar = \sum_j r[j]*2^j
  16. * where at most one of any w+1 consecutive digits is non-zero
  17. * with the exception that the most significant digit may be only
  18. * w-1 zeros away from that next non-zero digit.
  19. */
  20. signed char *bn_compute_wNAF(const BIGNUM *scalar, int w, size_t *ret_len)
  21. {
  22. int window_val;
  23. signed char *r = NULL;
  24. int sign = 1;
  25. int bit, next_bit, mask;
  26. size_t len = 0, j;
  27. if (BN_is_zero(scalar)) {
  28. r = OPENSSL_malloc(1);
  29. if (r == NULL) {
  30. BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE);
  31. goto err;
  32. }
  33. r[0] = 0;
  34. *ret_len = 1;
  35. return r;
  36. }
  37. if (w <= 0 || w > 7) { /* 'signed char' can represent integers with
  38. * absolute values less than 2^7 */
  39. BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
  40. goto err;
  41. }
  42. bit = 1 << w; /* at most 128 */
  43. next_bit = bit << 1; /* at most 256 */
  44. mask = next_bit - 1; /* at most 255 */
  45. if (BN_is_negative(scalar)) {
  46. sign = -1;
  47. }
  48. if (scalar->d == NULL || scalar->top == 0) {
  49. BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
  50. goto err;
  51. }
  52. len = BN_num_bits(scalar);
  53. r = OPENSSL_malloc(len + 1); /*
  54. * Modified wNAF may be one digit longer than binary representation
  55. * (*ret_len will be set to the actual length, i.e. at most
  56. * BN_num_bits(scalar) + 1)
  57. */
  58. if (r == NULL) {
  59. BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE);
  60. goto err;
  61. }
  62. window_val = scalar->d[0] & mask;
  63. j = 0;
  64. while ((window_val != 0) || (j + w + 1 < len)) { /* if j+w+1 >= len,
  65. * window_val will not
  66. * increase */
  67. int digit = 0;
  68. /* 0 <= window_val <= 2^(w+1) */
  69. if (window_val & 1) {
  70. /* 0 < window_val < 2^(w+1) */
  71. if (window_val & bit) {
  72. digit = window_val - next_bit; /* -2^w < digit < 0 */
  73. #if 1 /* modified wNAF */
  74. if (j + w + 1 >= len) {
  75. /*
  76. * Special case for generating modified wNAFs:
  77. * no new bits will be added into window_val,
  78. * so using a positive digit here will decrease
  79. * the total length of the representation
  80. */
  81. digit = window_val & (mask >> 1); /* 0 < digit < 2^w */
  82. }
  83. #endif
  84. } else {
  85. digit = window_val; /* 0 < digit < 2^w */
  86. }
  87. if (digit <= -bit || digit >= bit || !(digit & 1)) {
  88. BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
  89. goto err;
  90. }
  91. window_val -= digit;
  92. /*
  93. * now window_val is 0 or 2^(w+1) in standard wNAF generation;
  94. * for modified window NAFs, it may also be 2^w
  95. */
  96. if (window_val != 0 && window_val != next_bit
  97. && window_val != bit) {
  98. BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
  99. goto err;
  100. }
  101. }
  102. r[j++] = sign * digit;
  103. window_val >>= 1;
  104. window_val += bit * BN_is_bit_set(scalar, j + w);
  105. if (window_val > next_bit) {
  106. BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
  107. goto err;
  108. }
  109. }
  110. if (j > len + 1) {
  111. BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
  112. goto err;
  113. }
  114. *ret_len = j;
  115. return r;
  116. err:
  117. OPENSSL_free(r);
  118. return NULL;
  119. }
  120. int bn_get_top(const BIGNUM *a)
  121. {
  122. return a->top;
  123. }
  124. int bn_get_dmax(const BIGNUM *a)
  125. {
  126. return a->dmax;
  127. }
  128. void bn_set_all_zero(BIGNUM *a)
  129. {
  130. int i;
  131. for (i = a->top; i < a->dmax; i++)
  132. a->d[i] = 0;
  133. }
  134. int bn_copy_words(BN_ULONG *out, const BIGNUM *in, int size)
  135. {
  136. if (in->top > size)
  137. return 0;
  138. memset(out, 0, sizeof(*out) * size);
  139. if (in->d != NULL)
  140. memcpy(out, in->d, sizeof(*out) * in->top);
  141. return 1;
  142. }
  143. BN_ULONG *bn_get_words(const BIGNUM *a)
  144. {
  145. return a->d;
  146. }
  147. void bn_set_static_words(BIGNUM *a, BN_ULONG *words, int size)
  148. {
  149. a->d = words;
  150. a->dmax = a->top = size;
  151. a->neg = 0;
  152. a->flags |= BN_FLG_STATIC_DATA;
  153. bn_correct_top(a);
  154. }
  155. int bn_set_words(BIGNUM *a, BN_ULONG *words, int num_words)
  156. {
  157. if (bn_wexpand(a, num_words) == NULL) {
  158. BNerr(BN_F_BN_SET_WORDS, ERR_R_MALLOC_FAILURE);
  159. return 0;
  160. }
  161. memcpy(a->d, words, sizeof(BN_ULONG) * num_words);
  162. a->top = num_words;
  163. bn_correct_top(a);
  164. return 1;
  165. }