ecp_internal.h 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292
  1. /**
  2. * \file ecp_internal.h
  3. *
  4. * \brief Function declarations for alternative implementation of elliptic curve
  5. * point arithmetic.
  6. *
  7. * Copyright (C) 2016, ARM Limited, All Rights Reserved
  8. * SPDX-License-Identifier: Apache-2.0
  9. *
  10. * Licensed under the Apache License, Version 2.0 (the "License"); you may
  11. * not use this file except in compliance with the License.
  12. * You may obtain a copy of the License at
  13. *
  14. * http://www.apache.org/licenses/LICENSE-2.0
  15. *
  16. * Unless required by applicable law or agreed to in writing, software
  17. * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
  18. * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  19. * See the License for the specific language governing permissions and
  20. * limitations under the License.
  21. *
  22. * This file is part of mbed TLS (https://tls.mbed.org)
  23. */
  24. /*
  25. * References:
  26. *
  27. * [1] BERNSTEIN, Daniel J. Curve25519: new Diffie-Hellman speed records.
  28. * <http://cr.yp.to/ecdh/curve25519-20060209.pdf>
  29. *
  30. * [2] CORON, Jean-S'ebastien. Resistance against differential power analysis
  31. * for elliptic curve cryptosystems. In : Cryptographic Hardware and
  32. * Embedded Systems. Springer Berlin Heidelberg, 1999. p. 292-302.
  33. * <http://link.springer.com/chapter/10.1007/3-540-48059-5_25>
  34. *
  35. * [3] HEDABOU, Mustapha, PINEL, Pierre, et B'EN'ETEAU, Lucien. A comb method to
  36. * render ECC resistant against Side Channel Attacks. IACR Cryptology
  37. * ePrint Archive, 2004, vol. 2004, p. 342.
  38. * <http://eprint.iacr.org/2004/342.pdf>
  39. *
  40. * [4] Certicom Research. SEC 2: Recommended Elliptic Curve Domain Parameters.
  41. * <http://www.secg.org/sec2-v2.pdf>
  42. *
  43. * [5] HANKERSON, Darrel, MENEZES, Alfred J., VANSTONE, Scott. Guide to Elliptic
  44. * Curve Cryptography.
  45. *
  46. * [6] Digital Signature Standard (DSS), FIPS 186-4.
  47. * <http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf>
  48. *
  49. * [7] Elliptic Curve Cryptography (ECC) Cipher Suites for Transport Layer
  50. * Security (TLS), RFC 4492.
  51. * <https://tools.ietf.org/search/rfc4492>
  52. *
  53. * [8] <http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html>
  54. *
  55. * [9] COHEN, Henri. A Course in Computational Algebraic Number Theory.
  56. * Springer Science & Business Media, 1 Aug 2000
  57. */
  58. #ifndef MBEDTLS_ECP_INTERNAL_H
  59. #define MBEDTLS_ECP_INTERNAL_H
  60. #if defined(MBEDTLS_ECP_INTERNAL_ALT)
  61. /**
  62. * \brief Indicate if the Elliptic Curve Point module extension can
  63. * handle the group.
  64. *
  65. * \param grp The pointer to the elliptic curve group that will be the
  66. * basis of the cryptographic computations.
  67. *
  68. * \return Non-zero if successful.
  69. */
  70. unsigned char mbedtls_internal_ecp_grp_capable( const mbedtls_ecp_group *grp );
  71. /**
  72. * \brief Initialise the Elliptic Curve Point module extension.
  73. *
  74. * If mbedtls_internal_ecp_grp_capable returns true for a
  75. * group, this function has to be able to initialise the
  76. * module for it.
  77. *
  78. * This module can be a driver to a crypto hardware
  79. * accelerator, for which this could be an initialise function.
  80. *
  81. * \param grp The pointer to the group the module needs to be
  82. * initialised for.
  83. *
  84. * \return 0 if successful.
  85. */
  86. int mbedtls_internal_ecp_init( const mbedtls_ecp_group *grp );
  87. /**
  88. * \brief Frees and deallocates the Elliptic Curve Point module
  89. * extension.
  90. *
  91. * \param grp The pointer to the group the module was initialised for.
  92. */
  93. void mbedtls_internal_ecp_free( const mbedtls_ecp_group *grp );
  94. #if defined(ECP_SHORTWEIERSTRASS)
  95. #if defined(MBEDTLS_ECP_RANDOMIZE_JAC_ALT)
  96. /**
  97. * \brief Randomize jacobian coordinates:
  98. * (X, Y, Z) -> (l^2 X, l^3 Y, l Z) for random l.
  99. *
  100. * \param grp Pointer to the group representing the curve.
  101. *
  102. * \param pt The point on the curve to be randomised, given with Jacobian
  103. * coordinates.
  104. *
  105. * \param f_rng A function pointer to the random number generator.
  106. *
  107. * \param p_rng A pointer to the random number generator state.
  108. *
  109. * \return 0 if successful.
  110. */
  111. int mbedtls_internal_ecp_randomize_jac( const mbedtls_ecp_group *grp,
  112. mbedtls_ecp_point *pt, int (*f_rng)(void *, unsigned char *, size_t),
  113. void *p_rng );
  114. #endif
  115. #if defined(MBEDTLS_ECP_ADD_MIXED_ALT)
  116. /**
  117. * \brief Addition: R = P + Q, mixed affine-Jacobian coordinates.
  118. *
  119. * The coordinates of Q must be normalized (= affine),
  120. * but those of P don't need to. R is not normalized.
  121. *
  122. * This function is used only as a subrutine of
  123. * ecp_mul_comb().
  124. *
  125. * Special cases: (1) P or Q is zero, (2) R is zero,
  126. * (3) P == Q.
  127. * None of these cases can happen as intermediate step in
  128. * ecp_mul_comb():
  129. * - at each step, P, Q and R are multiples of the base
  130. * point, the factor being less than its order, so none of
  131. * them is zero;
  132. * - Q is an odd multiple of the base point, P an even
  133. * multiple, due to the choice of precomputed points in the
  134. * modified comb method.
  135. * So branches for these cases do not leak secret information.
  136. *
  137. * We accept Q->Z being unset (saving memory in tables) as
  138. * meaning 1.
  139. *
  140. * Cost in field operations if done by [5] 3.22:
  141. * 1A := 8M + 3S
  142. *
  143. * \param grp Pointer to the group representing the curve.
  144. *
  145. * \param R Pointer to a point structure to hold the result.
  146. *
  147. * \param P Pointer to the first summand, given with Jacobian
  148. * coordinates
  149. *
  150. * \param Q Pointer to the second summand, given with affine
  151. * coordinates.
  152. *
  153. * \return 0 if successful.
  154. */
  155. int mbedtls_internal_ecp_add_mixed( const mbedtls_ecp_group *grp,
  156. mbedtls_ecp_point *R, const mbedtls_ecp_point *P,
  157. const mbedtls_ecp_point *Q );
  158. #endif
  159. /**
  160. * \brief Point doubling R = 2 P, Jacobian coordinates.
  161. *
  162. * Cost: 1D := 3M + 4S (A == 0)
  163. * 4M + 4S (A == -3)
  164. * 3M + 6S + 1a otherwise
  165. * when the implementation is based on the "dbl-1998-cmo-2"
  166. * doubling formulas in [8] and standard optimizations are
  167. * applied when curve parameter A is one of { 0, -3 }.
  168. *
  169. * \param grp Pointer to the group representing the curve.
  170. *
  171. * \param R Pointer to a point structure to hold the result.
  172. *
  173. * \param P Pointer to the point that has to be doubled, given with
  174. * Jacobian coordinates.
  175. *
  176. * \return 0 if successful.
  177. */
  178. #if defined(MBEDTLS_ECP_DOUBLE_JAC_ALT)
  179. int mbedtls_internal_ecp_double_jac( const mbedtls_ecp_group *grp,
  180. mbedtls_ecp_point *R, const mbedtls_ecp_point *P );
  181. #endif
  182. /**
  183. * \brief Normalize jacobian coordinates of an array of (pointers to)
  184. * points.
  185. *
  186. * Using Montgomery's trick to perform only one inversion mod P
  187. * the cost is:
  188. * 1N(t) := 1I + (6t - 3)M + 1S
  189. * (See for example Algorithm 10.3.4. in [9])
  190. *
  191. * This function is used only as a subrutine of
  192. * ecp_mul_comb().
  193. *
  194. * Warning: fails (returning an error) if one of the points is
  195. * zero!
  196. * This should never happen, see choice of w in ecp_mul_comb().
  197. *
  198. * \param grp Pointer to the group representing the curve.
  199. *
  200. * \param T Array of pointers to the points to normalise.
  201. *
  202. * \param t_len Number of elements in the array.
  203. *
  204. * \return 0 if successful,
  205. * an error if one of the points is zero.
  206. */
  207. #if defined(MBEDTLS_ECP_NORMALIZE_JAC_MANY_ALT)
  208. int mbedtls_internal_ecp_normalize_jac_many( const mbedtls_ecp_group *grp,
  209. mbedtls_ecp_point *T[], size_t t_len );
  210. #endif
  211. /**
  212. * \brief Normalize jacobian coordinates so that Z == 0 || Z == 1.
  213. *
  214. * Cost in field operations if done by [5] 3.2.1:
  215. * 1N := 1I + 3M + 1S
  216. *
  217. * \param grp Pointer to the group representing the curve.
  218. *
  219. * \param pt pointer to the point to be normalised. This is an
  220. * input/output parameter.
  221. *
  222. * \return 0 if successful.
  223. */
  224. #if defined(MBEDTLS_ECP_NORMALIZE_JAC_ALT)
  225. int mbedtls_internal_ecp_normalize_jac( const mbedtls_ecp_group *grp,
  226. mbedtls_ecp_point *pt );
  227. #endif
  228. #endif /* ECP_SHORTWEIERSTRASS */
  229. #if defined(ECP_MONTGOMERY)
  230. #if defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT)
  231. int mbedtls_internal_ecp_double_add_mxz( const mbedtls_ecp_group *grp,
  232. mbedtls_ecp_point *R, mbedtls_ecp_point *S, const mbedtls_ecp_point *P,
  233. const mbedtls_ecp_point *Q, const mbedtls_mpi *d );
  234. #endif
  235. /**
  236. * \brief Randomize projective x/z coordinates:
  237. * (X, Z) -> (l X, l Z) for random l
  238. *
  239. * \param grp pointer to the group representing the curve
  240. *
  241. * \param P the point on the curve to be randomised given with
  242. * projective coordinates. This is an input/output parameter.
  243. *
  244. * \param f_rng a function pointer to the random number generator
  245. *
  246. * \param p_rng a pointer to the random number generator state
  247. *
  248. * \return 0 if successful
  249. */
  250. #if defined(MBEDTLS_ECP_RANDOMIZE_MXZ_ALT)
  251. int mbedtls_internal_ecp_randomize_mxz( const mbedtls_ecp_group *grp,
  252. mbedtls_ecp_point *P, int (*f_rng)(void *, unsigned char *, size_t),
  253. void *p_rng );
  254. #endif
  255. /**
  256. * \brief Normalize Montgomery x/z coordinates: X = X/Z, Z = 1.
  257. *
  258. * \param grp pointer to the group representing the curve
  259. *
  260. * \param P pointer to the point to be normalised. This is an
  261. * input/output parameter.
  262. *
  263. * \return 0 if successful
  264. */
  265. #if defined(MBEDTLS_ECP_NORMALIZE_MXZ_ALT)
  266. int mbedtls_internal_ecp_normalize_mxz( const mbedtls_ecp_group *grp,
  267. mbedtls_ecp_point *P );
  268. #endif
  269. #endif /* ECP_MONTGOMERY */
  270. #endif /* MBEDTLS_ECP_INTERNAL_ALT */
  271. #endif /* ecp_internal.h */