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