ecp_internal.h

00001 /**
00002  * \file ecp_internal.h
00003  *
00004  * \brief Function declarations for alternative implementation of elliptic curve
00005  * point arithmetic.
00006  *
00007  *  Copyright (C) 2016, ARM Limited, All Rights Reserved
00008  *  SPDX-License-Identifier: Apache-2.0
00009  *
00010  *  Licensed under the Apache License, Version 2.0 (the "License"); you may
00011  *  not use this file except in compliance with the License.
00012  *  You may obtain a copy of the License at
00013  *
00014  *  http://www.apache.org/licenses/LICENSE-2.0
00015  *
00016  *  Unless required by applicable law or agreed to in writing, software
00017  *  distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
00018  *  WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00019  *  See the License for the specific language governing permissions and
00020  *  limitations under the License.
00021  *
00022  *  This file is part of mbed TLS (https://tls.mbed.org)
00023  */
00024 
00025 /*
00026  * References:
00027  *
00028  * [1] BERNSTEIN, Daniel J. Curve25519: new Diffie-Hellman speed records.
00029  *     <http://cr.yp.to/ecdh/curve25519-20060209.pdf>
00030  *
00031  * [2] CORON, Jean-S'ebastien. Resistance against differential power analysis
00032  *     for elliptic curve cryptosystems. In : Cryptographic Hardware and
00033  *     Embedded Systems. Springer Berlin Heidelberg, 1999. p. 292-302.
00034  *     <http://link.springer.com/chapter/10.1007/3-540-48059-5_25>
00035  *
00036  * [3] HEDABOU, Mustapha, PINEL, Pierre, et B'EN'ETEAU, Lucien. A comb method to
00037  *     render ECC resistant against Side Channel Attacks. IACR Cryptology
00038  *     ePrint Archive, 2004, vol. 2004, p. 342.
00039  *     <http://eprint.iacr.org/2004/342.pdf>
00040  *
00041  * [4] Certicom Research. SEC 2: Recommended Elliptic Curve Domain Parameters.
00042  *     <http://www.secg.org/sec2-v2.pdf>
00043  *
00044  * [5] HANKERSON, Darrel, MENEZES, Alfred J., VANSTONE, Scott. Guide to Elliptic
00045  *     Curve Cryptography.
00046  *
00047  * [6] Digital Signature Standard (DSS), FIPS 186-4.
00048  *     <http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf>
00049  *
00050  * [7] Elliptic Curve Cryptography (ECC) Cipher Suites for Transport Layer 
00051  *     Security (TLS), RFC 4492.
00052  *     <https://tools.ietf.org/search/rfc4492>
00053  *
00054  * [8] <http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html>
00055  *
00056  * [9] COHEN, Henri. A Course in Computational Algebraic Number Theory.
00057  *     Springer Science & Business Media, 1 Aug 2000
00058  */
00059 
00060 #ifndef MBEDTLS_ECP_INTERNAL_H
00061 #define MBEDTLS_ECP_INTERNAL_H
00062 
00063 #if defined(MBEDTLS_ECP_INTERNAL_ALT)
00064 
00065 /**
00066  * \brief           Indicate if the Elliptic Curve Point module extension can
00067  *                  handle the group.
00068  *
00069  * \param grp       The pointer to the elliptic curve group that will be the
00070  *                  basis of the cryptographic computations.
00071  *
00072  * \return          Non-zero if successful.
00073  */
00074 unsigned char mbedtls_internal_ecp_grp_capable( const mbedtls_ecp_group *grp );
00075 
00076 /**
00077  * \brief           Initialise the Elliptic Curve Point module extension.
00078  *
00079  *                  If mbedtls_internal_ecp_grp_capable returns true for a
00080  *                  group, this function has to be able to initialise the
00081  *                  module for it.
00082  *
00083  *                  This module can be a driver to a crypto hardware
00084  *                  accelerator, for which this could be an initialise function.
00085  *
00086  * \param grp       The pointer to the group the module needs to be
00087  *                  initialised for.
00088  *
00089  * \return          0 if successful.
00090  */
00091 int mbedtls_internal_ecp_init( const mbedtls_ecp_group *grp );
00092 
00093 /**
00094  * \brief           Frees and deallocates the Elliptic Curve Point module
00095  *                  extension.
00096  *
00097  * \param grp       The pointer to the group the module was initialised for.
00098  */
00099 void mbedtls_internal_ecp_free( const mbedtls_ecp_group *grp );
00100 
00101 #if defined(ECP_SHORTWEIERSTRASS)
00102 
00103 #if defined(MBEDTLS_ECP_RANDOMIZE_JAC_ALT)
00104 /**
00105  * \brief           Randomize jacobian coordinates:
00106  *                  (X, Y, Z) -> (l^2 X, l^3 Y, l Z) for random l.
00107  *
00108  * \param grp       Pointer to the group representing the curve.
00109  *
00110  * \param pt        The point on the curve to be randomised, given with Jacobian
00111  *                  coordinates.
00112  *
00113  * \param f_rng     A function pointer to the random number generator.
00114  *
00115  * \param p_rng     A pointer to the random number generator state.
00116  *
00117  * \return          0 if successful.
00118  */
00119 int mbedtls_internal_ecp_randomize_jac( const mbedtls_ecp_group *grp,
00120         mbedtls_ecp_point *pt, int (*f_rng)(void *, unsigned char *, size_t),
00121         void *p_rng );
00122 #endif
00123 
00124 #if defined(MBEDTLS_ECP_ADD_MIXED_ALT)
00125 /**
00126  * \brief           Addition: R = P + Q, mixed affine-Jacobian coordinates.
00127  *
00128  *                  The coordinates of Q must be normalized (= affine),
00129  *                  but those of P don't need to. R is not normalized.
00130  *
00131  *                  This function is used only as a subrutine of
00132  *                  ecp_mul_comb().
00133  *
00134  *                  Special cases: (1) P or Q is zero, (2) R is zero,
00135  *                      (3) P == Q.
00136  *                  None of these cases can happen as intermediate step in
00137  *                  ecp_mul_comb():
00138  *                      - at each step, P, Q and R are multiples of the base
00139  *                      point, the factor being less than its order, so none of
00140  *                      them is zero;
00141  *                      - Q is an odd multiple of the base point, P an even
00142  *                      multiple, due to the choice of precomputed points in the
00143  *                      modified comb method.
00144  *                  So branches for these cases do not leak secret information.
00145  *
00146  *                  We accept Q->Z being unset (saving memory in tables) as
00147  *                  meaning 1.
00148  *
00149  *                  Cost in field operations if done by [5] 3.22:
00150  *                      1A := 8M + 3S
00151  *
00152  * \param grp       Pointer to the group representing the curve.
00153  *
00154  * \param R         Pointer to a point structure to hold the result.
00155  *
00156  * \param P         Pointer to the first summand, given with Jacobian
00157  *                  coordinates
00158  *
00159  * \param Q         Pointer to the second summand, given with affine
00160  *                  coordinates.
00161  *
00162  * \return          0 if successful.
00163  */
00164 int mbedtls_internal_ecp_add_mixed( const mbedtls_ecp_group *grp,
00165         mbedtls_ecp_point *R, const mbedtls_ecp_point *P,
00166         const mbedtls_ecp_point *Q );
00167 #endif
00168 
00169 /**
00170  * \brief           Point doubling R = 2 P, Jacobian coordinates.
00171  *
00172  *                  Cost:   1D := 3M + 4S    (A ==  0)
00173  *                          4M + 4S          (A == -3)
00174  *                          3M + 6S + 1a     otherwise
00175  *                  when the implementation is based on the "dbl-1998-cmo-2"
00176  *                  doubling formulas in [8] and standard optimizations are
00177  *                  applied when curve parameter A is one of { 0, -3 }.
00178  *
00179  * \param grp       Pointer to the group representing the curve.
00180  *
00181  * \param R         Pointer to a point structure to hold the result.
00182  *
00183  * \param P         Pointer to the point that has to be doubled, given with
00184  *                  Jacobian coordinates.
00185  *
00186  * \return          0 if successful.
00187  */
00188 #if defined(MBEDTLS_ECP_DOUBLE_JAC_ALT)
00189 int mbedtls_internal_ecp_double_jac( const mbedtls_ecp_group *grp,
00190         mbedtls_ecp_point *R, const mbedtls_ecp_point *P );
00191 #endif
00192 
00193 /**
00194  * \brief           Normalize jacobian coordinates of an array of (pointers to)
00195  *                  points.
00196  *
00197  *                  Using Montgomery's trick to perform only one inversion mod P
00198  *                  the cost is:
00199  *                      1N(t) := 1I + (6t - 3)M + 1S
00200  *                  (See for example Algorithm 10.3.4. in [9])
00201  *
00202  *                  This function is used only as a subrutine of
00203  *                  ecp_mul_comb().
00204  *
00205  *                  Warning: fails (returning an error) if one of the points is
00206  *                  zero!
00207  *                  This should never happen, see choice of w in ecp_mul_comb().
00208  *
00209  * \param grp       Pointer to the group representing the curve.
00210  *
00211  * \param T         Array of pointers to the points to normalise.
00212  *
00213  * \param t_len     Number of elements in the array.
00214  *
00215  * \return          0 if successful,
00216  *                      an error if one of the points is zero.
00217  */
00218 #if defined(MBEDTLS_ECP_NORMALIZE_JAC_MANY_ALT)
00219 int mbedtls_internal_ecp_normalize_jac_many( const mbedtls_ecp_group *grp,
00220         mbedtls_ecp_point *T[], size_t t_len );
00221 #endif
00222 
00223 /**
00224  * \brief           Normalize jacobian coordinates so that Z == 0 || Z == 1.
00225  *
00226  *                  Cost in field operations if done by [5] 3.2.1:
00227  *                      1N := 1I + 3M + 1S
00228  *
00229  * \param grp       Pointer to the group representing the curve.
00230  *
00231  * \param pt        pointer to the point to be normalised. This is an
00232  *                  input/output parameter.
00233  *
00234  * \return          0 if successful.
00235  */
00236 #if defined(MBEDTLS_ECP_NORMALIZE_JAC_ALT)
00237 int mbedtls_internal_ecp_normalize_jac( const mbedtls_ecp_group *grp,
00238         mbedtls_ecp_point *pt );
00239 #endif
00240 
00241 #endif /* ECP_SHORTWEIERSTRASS */
00242 
00243 #if defined(ECP_MONTGOMERY)
00244 
00245 #if defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT)
00246 int mbedtls_internal_ecp_double_add_mxz( const mbedtls_ecp_group *grp,
00247         mbedtls_ecp_point *R, mbedtls_ecp_point *S, const mbedtls_ecp_point *P,
00248         const mbedtls_ecp_point *Q, const mbedtls_mpi *d );
00249 #endif
00250 
00251 /**
00252  * \brief           Randomize projective x/z coordinates:
00253  *                      (X, Z) -> (l X, l Z) for random l
00254  *
00255  * \param grp       pointer to the group representing the curve
00256  *
00257  * \param P         the point on the curve to be randomised given with
00258  *                  projective coordinates. This is an input/output parameter.
00259  *
00260  * \param f_rng     a function pointer to the random number generator
00261  *
00262  * \param p_rng     a pointer to the random number generator state
00263  *
00264  * \return          0 if successful
00265  */
00266 #if defined(MBEDTLS_ECP_RANDOMIZE_MXZ_ALT)
00267 int mbedtls_internal_ecp_randomize_mxz( const mbedtls_ecp_group *grp,
00268         mbedtls_ecp_point *P, int (*f_rng)(void *, unsigned char *, size_t),
00269         void *p_rng );
00270 #endif
00271 
00272 /**
00273  * \brief           Normalize Montgomery x/z coordinates: X = X/Z, Z = 1.
00274  *
00275  * \param grp       pointer to the group representing the curve
00276  *
00277  * \param P         pointer to the point to be normalised. This is an
00278  *                  input/output parameter.
00279  *
00280  * \return          0 if successful
00281  */
00282 #if defined(MBEDTLS_ECP_NORMALIZE_MXZ_ALT)
00283 int mbedtls_internal_ecp_normalize_mxz( const mbedtls_ecp_group *grp,
00284         mbedtls_ecp_point *P );
00285 #endif
00286 
00287 #endif /* ECP_MONTGOMERY */
00288 
00289 #endif /* MBEDTLS_ECP_INTERNAL_ALT */
00290 
00291 #endif /* ecp_internal.h */
00292