bn_shift.c 4.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216
  1. /*
  2. * Copyright 1995-2020 The OpenSSL Project Authors. All Rights Reserved.
  3. *
  4. * Licensed under the Apache License 2.0 (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 <assert.h>
  10. #include "internal/cryptlib.h"
  11. #include "bn_local.h"
  12. int BN_lshift1(BIGNUM *r, const BIGNUM *a)
  13. {
  14. register BN_ULONG *ap, *rp, t, c;
  15. int i;
  16. bn_check_top(r);
  17. bn_check_top(a);
  18. if (r != a) {
  19. r->neg = a->neg;
  20. if (bn_wexpand(r, a->top + 1) == NULL)
  21. return 0;
  22. r->top = a->top;
  23. } else {
  24. if (bn_wexpand(r, a->top + 1) == NULL)
  25. return 0;
  26. }
  27. ap = a->d;
  28. rp = r->d;
  29. c = 0;
  30. for (i = 0; i < a->top; i++) {
  31. t = *(ap++);
  32. *(rp++) = ((t << 1) | c) & BN_MASK2;
  33. c = t >> (BN_BITS2 - 1);
  34. }
  35. *rp = c;
  36. r->top += c;
  37. bn_check_top(r);
  38. return 1;
  39. }
  40. int BN_rshift1(BIGNUM *r, const BIGNUM *a)
  41. {
  42. BN_ULONG *ap, *rp, t, c;
  43. int i;
  44. bn_check_top(r);
  45. bn_check_top(a);
  46. if (BN_is_zero(a)) {
  47. BN_zero(r);
  48. return 1;
  49. }
  50. i = a->top;
  51. ap = a->d;
  52. if (a != r) {
  53. if (bn_wexpand(r, i) == NULL)
  54. return 0;
  55. r->neg = a->neg;
  56. }
  57. rp = r->d;
  58. r->top = i;
  59. t = ap[--i];
  60. rp[i] = t >> 1;
  61. c = t << (BN_BITS2 - 1);
  62. r->top -= (t == 1);
  63. while (i > 0) {
  64. t = ap[--i];
  65. rp[i] = ((t >> 1) & BN_MASK2) | c;
  66. c = t << (BN_BITS2 - 1);
  67. }
  68. if (!r->top)
  69. r->neg = 0; /* don't allow negative zero */
  70. bn_check_top(r);
  71. return 1;
  72. }
  73. int BN_lshift(BIGNUM *r, const BIGNUM *a, int n)
  74. {
  75. int ret;
  76. if (n < 0) {
  77. ERR_raise(ERR_LIB_BN, BN_R_INVALID_SHIFT);
  78. return 0;
  79. }
  80. ret = bn_lshift_fixed_top(r, a, n);
  81. bn_correct_top(r);
  82. bn_check_top(r);
  83. return ret;
  84. }
  85. /*
  86. * In respect to shift factor the execution time is invariant of
  87. * |n % BN_BITS2|, but not |n / BN_BITS2|. Or in other words pre-condition
  88. * for constant-time-ness is |n < BN_BITS2| or |n / BN_BITS2| being
  89. * non-secret.
  90. */
  91. int bn_lshift_fixed_top(BIGNUM *r, const BIGNUM *a, int n)
  92. {
  93. int i, nw;
  94. unsigned int lb, rb;
  95. BN_ULONG *t, *f;
  96. BN_ULONG l, m, rmask = 0;
  97. assert(n >= 0);
  98. bn_check_top(r);
  99. bn_check_top(a);
  100. nw = n / BN_BITS2;
  101. if (bn_wexpand(r, a->top + nw + 1) == NULL)
  102. return 0;
  103. if (a->top != 0) {
  104. lb = (unsigned int)n % BN_BITS2;
  105. rb = BN_BITS2 - lb;
  106. rb %= BN_BITS2; /* say no to undefined behaviour */
  107. rmask = (BN_ULONG)0 - rb; /* rmask = 0 - (rb != 0) */
  108. rmask |= rmask >> 8;
  109. f = &(a->d[0]);
  110. t = &(r->d[nw]);
  111. l = f[a->top - 1];
  112. t[a->top] = (l >> rb) & rmask;
  113. for (i = a->top - 1; i > 0; i--) {
  114. m = l << lb;
  115. l = f[i - 1];
  116. t[i] = (m | ((l >> rb) & rmask)) & BN_MASK2;
  117. }
  118. t[0] = (l << lb) & BN_MASK2;
  119. } else {
  120. /* shouldn't happen, but formally required */
  121. r->d[nw] = 0;
  122. }
  123. if (nw != 0)
  124. memset(r->d, 0, sizeof(*t) * nw);
  125. r->neg = a->neg;
  126. r->top = a->top + nw + 1;
  127. r->flags |= BN_FLG_FIXED_TOP;
  128. return 1;
  129. }
  130. int BN_rshift(BIGNUM *r, const BIGNUM *a, int n)
  131. {
  132. int ret = 0;
  133. if (n < 0) {
  134. ERR_raise(ERR_LIB_BN, BN_R_INVALID_SHIFT);
  135. return 0;
  136. }
  137. bn_check_top(r);
  138. bn_check_top(a);
  139. ret = bn_rshift_fixed_top(r, a, n);
  140. bn_correct_top(r);
  141. bn_check_top(r);
  142. return ret;
  143. }
  144. /*
  145. * In respect to shift factor the execution time is invariant of
  146. * |n % BN_BITS2|, but not |n / BN_BITS2|. Or in other words pre-condition
  147. * for constant-time-ness for sufficiently[!] zero-padded inputs is
  148. * |n < BN_BITS2| or |n / BN_BITS2| being non-secret.
  149. */
  150. int bn_rshift_fixed_top(BIGNUM *r, const BIGNUM *a, int n)
  151. {
  152. int i, top, nw;
  153. unsigned int lb, rb;
  154. BN_ULONG *t, *f;
  155. BN_ULONG l, m, mask;
  156. assert(n >= 0);
  157. nw = n / BN_BITS2;
  158. if (nw >= a->top) {
  159. /* shouldn't happen, but formally required */
  160. BN_zero(r);
  161. return 1;
  162. }
  163. rb = (unsigned int)n % BN_BITS2;
  164. lb = BN_BITS2 - rb;
  165. lb %= BN_BITS2; /* say no to undefined behaviour */
  166. mask = (BN_ULONG)0 - lb; /* mask = 0 - (lb != 0) */
  167. mask |= mask >> 8;
  168. top = a->top - nw;
  169. if (r != a && bn_wexpand(r, top) == NULL)
  170. return 0;
  171. t = &(r->d[0]);
  172. f = &(a->d[nw]);
  173. l = f[0];
  174. for (i = 0; i < top - 1; i++) {
  175. m = f[i + 1];
  176. t[i] = (l >> rb) | ((m << lb) & mask);
  177. l = m;
  178. }
  179. t[i] = l >> rb;
  180. r->neg = a->neg;
  181. r->top = top;
  182. r->flags |= BN_FLG_FIXED_TOP;
  183. return 1;
  184. }