2
0

ecp_nistputil.c 9.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226
  1. /*
  2. * Copyright 2011-2021 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. /* Copyright 2011 Google Inc.
  10. *
  11. * Licensed under the Apache License, Version 2.0 (the "License");
  12. *
  13. * you may not use this file except in compliance with the License.
  14. * You may obtain a copy of the License at
  15. *
  16. * http://www.apache.org/licenses/LICENSE-2.0
  17. *
  18. * Unless required by applicable law or agreed to in writing, software
  19. * distributed under the License is distributed on an "AS IS" BASIS,
  20. * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  21. * See the License for the specific language governing permissions and
  22. * limitations under the License.
  23. */
  24. /*
  25. * ECDSA low level APIs are deprecated for public use, but still ok for
  26. * internal use.
  27. */
  28. #include "internal/deprecated.h"
  29. #include <openssl/opensslconf.h>
  30. /*
  31. * Common utility functions for ecp_nistp224.c, ecp_nistp256.c, ecp_nistp521.c.
  32. */
  33. #include <stddef.h>
  34. #include "ec_local.h"
  35. /*
  36. * Convert an array of points into affine coordinates. (If the point at
  37. * infinity is found (Z = 0), it remains unchanged.) This function is
  38. * essentially an equivalent to EC_POINTs_make_affine(), but works with the
  39. * internal representation of points as used by ecp_nistp###.c rather than
  40. * with (BIGNUM-based) EC_POINT data structures. point_array is the
  41. * input/output buffer ('num' points in projective form, i.e. three
  42. * coordinates each), based on an internal representation of field elements
  43. * of size 'felem_size'. tmp_felems needs to point to a temporary array of
  44. * 'num'+1 field elements for storage of intermediate values.
  45. */
  46. void
  47. ossl_ec_GFp_nistp_points_make_affine_internal(size_t num, void *point_array,
  48. size_t felem_size,
  49. void *tmp_felems,
  50. void (*felem_one) (void *out),
  51. int (*felem_is_zero) (const void
  52. *in),
  53. void (*felem_assign) (void *out,
  54. const void
  55. *in),
  56. void (*felem_square) (void *out,
  57. const void
  58. *in),
  59. void (*felem_mul) (void *out,
  60. const void
  61. *in1,
  62. const void
  63. *in2),
  64. void (*felem_inv) (void *out,
  65. const void
  66. *in),
  67. void (*felem_contract) (void
  68. *out,
  69. const
  70. void
  71. *in))
  72. {
  73. int i = 0;
  74. #define tmp_felem(I) (&((char *)tmp_felems)[(I) * felem_size])
  75. #define X(I) (&((char *)point_array)[3*(I) * felem_size])
  76. #define Y(I) (&((char *)point_array)[(3*(I) + 1) * felem_size])
  77. #define Z(I) (&((char *)point_array)[(3*(I) + 2) * felem_size])
  78. if (!felem_is_zero(Z(0)))
  79. felem_assign(tmp_felem(0), Z(0));
  80. else
  81. felem_one(tmp_felem(0));
  82. for (i = 1; i < (int)num; i++) {
  83. if (!felem_is_zero(Z(i)))
  84. felem_mul(tmp_felem(i), tmp_felem(i - 1), Z(i));
  85. else
  86. felem_assign(tmp_felem(i), tmp_felem(i - 1));
  87. }
  88. /*
  89. * Now each tmp_felem(i) is the product of Z(0) .. Z(i), skipping any
  90. * zero-valued factors: if Z(i) = 0, we essentially pretend that Z(i) = 1
  91. */
  92. felem_inv(tmp_felem(num - 1), tmp_felem(num - 1));
  93. for (i = num - 1; i >= 0; i--) {
  94. if (i > 0)
  95. /*
  96. * tmp_felem(i-1) is the product of Z(0) .. Z(i-1), tmp_felem(i)
  97. * is the inverse of the product of Z(0) .. Z(i)
  98. */
  99. /* 1/Z(i) */
  100. felem_mul(tmp_felem(num), tmp_felem(i - 1), tmp_felem(i));
  101. else
  102. felem_assign(tmp_felem(num), tmp_felem(0)); /* 1/Z(0) */
  103. if (!felem_is_zero(Z(i))) {
  104. if (i > 0)
  105. /*
  106. * For next iteration, replace tmp_felem(i-1) by its inverse
  107. */
  108. felem_mul(tmp_felem(i - 1), tmp_felem(i), Z(i));
  109. /*
  110. * Convert point (X, Y, Z) into affine form (X/(Z^2), Y/(Z^3), 1)
  111. */
  112. felem_square(Z(i), tmp_felem(num)); /* 1/(Z^2) */
  113. felem_mul(X(i), X(i), Z(i)); /* X/(Z^2) */
  114. felem_mul(Z(i), Z(i), tmp_felem(num)); /* 1/(Z^3) */
  115. felem_mul(Y(i), Y(i), Z(i)); /* Y/(Z^3) */
  116. felem_contract(X(i), X(i));
  117. felem_contract(Y(i), Y(i));
  118. felem_one(Z(i));
  119. } else {
  120. if (i > 0)
  121. /*
  122. * For next iteration, replace tmp_felem(i-1) by its inverse
  123. */
  124. felem_assign(tmp_felem(i - 1), tmp_felem(i));
  125. }
  126. }
  127. }
  128. /*-
  129. * This function looks at 5+1 scalar bits (5 current, 1 adjacent less
  130. * significant bit), and recodes them into a signed digit for use in fast point
  131. * multiplication: the use of signed rather than unsigned digits means that
  132. * fewer points need to be precomputed, given that point inversion is easy
  133. * (a precomputed point dP makes -dP available as well).
  134. *
  135. * BACKGROUND:
  136. *
  137. * Signed digits for multiplication were introduced by Booth ("A signed binary
  138. * multiplication technique", Quart. Journ. Mech. and Applied Math., vol. IV,
  139. * pt. 2 (1951), pp. 236-240), in that case for multiplication of integers.
  140. * Booth's original encoding did not generally improve the density of nonzero
  141. * digits over the binary representation, and was merely meant to simplify the
  142. * handling of signed factors given in two's complement; but it has since been
  143. * shown to be the basis of various signed-digit representations that do have
  144. * further advantages, including the wNAF, using the following general approach:
  145. *
  146. * (1) Given a binary representation
  147. *
  148. * b_k ... b_2 b_1 b_0,
  149. *
  150. * of a nonnegative integer (b_k in {0, 1}), rewrite it in digits 0, 1, -1
  151. * by using bit-wise subtraction as follows:
  152. *
  153. * b_k b_(k-1) ... b_2 b_1 b_0
  154. * - b_k ... b_3 b_2 b_1 b_0
  155. * -----------------------------------------
  156. * s_(k+1) s_k ... s_3 s_2 s_1 s_0
  157. *
  158. * A left-shift followed by subtraction of the original value yields a new
  159. * representation of the same value, using signed bits s_i = b_(i-1) - b_i.
  160. * This representation from Booth's paper has since appeared in the
  161. * literature under a variety of different names including "reversed binary
  162. * form", "alternating greedy expansion", "mutual opposite form", and
  163. * "sign-alternating {+-1}-representation".
  164. *
  165. * An interesting property is that among the nonzero bits, values 1 and -1
  166. * strictly alternate.
  167. *
  168. * (2) Various window schemes can be applied to the Booth representation of
  169. * integers: for example, right-to-left sliding windows yield the wNAF
  170. * (a signed-digit encoding independently discovered by various researchers
  171. * in the 1990s), and left-to-right sliding windows yield a left-to-right
  172. * equivalent of the wNAF (independently discovered by various researchers
  173. * around 2004).
  174. *
  175. * To prevent leaking information through side channels in point multiplication,
  176. * we need to recode the given integer into a regular pattern: sliding windows
  177. * as in wNAFs won't do, we need their fixed-window equivalent -- which is a few
  178. * decades older: we'll be using the so-called "modified Booth encoding" due to
  179. * MacSorley ("High-speed arithmetic in binary computers", Proc. IRE, vol. 49
  180. * (1961), pp. 67-91), in a radix-2^5 setting. That is, we always combine five
  181. * signed bits into a signed digit:
  182. *
  183. * s_(5j + 4) s_(5j + 3) s_(5j + 2) s_(5j + 1) s_(5j)
  184. *
  185. * The sign-alternating property implies that the resulting digit values are
  186. * integers from -16 to 16.
  187. *
  188. * Of course, we don't actually need to compute the signed digits s_i as an
  189. * intermediate step (that's just a nice way to see how this scheme relates
  190. * to the wNAF): a direct computation obtains the recoded digit from the
  191. * six bits b_(5j + 4) ... b_(5j - 1).
  192. *
  193. * This function takes those six bits as an integer (0 .. 63), writing the
  194. * recoded digit to *sign (0 for positive, 1 for negative) and *digit (absolute
  195. * value, in the range 0 .. 16). Note that this integer essentially provides
  196. * the input bits "shifted to the left" by one position: for example, the input
  197. * to compute the least significant recoded digit, given that there's no bit
  198. * b_-1, has to be b_4 b_3 b_2 b_1 b_0 0.
  199. *
  200. */
  201. void ossl_ec_GFp_nistp_recode_scalar_bits(unsigned char *sign,
  202. unsigned char *digit, unsigned char in)
  203. {
  204. unsigned char s, d;
  205. s = ~((in >> 5) - 1); /* sets all bits to MSB(in), 'in' seen as
  206. * 6-bit value */
  207. d = (1 << 6) - in - 1;
  208. d = (d & s) | (in & ~s);
  209. d = (d >> 1) + (d & 1);
  210. *sign = s & 1;
  211. *digit = d;
  212. }