mbed TLS library
Dependents: HTTPClient-SSL WS_SERVER
polarssl/ecp.c@0:137634ff4186, 2015-06-11 (annotated)
- Committer:
- ansond
- Date:
- Thu Jun 11 03:27:03 2015 +0000
- Revision:
- 0:137634ff4186
initial commit
Who changed what in which revision?
User | Revision | Line number | New contents of line |
---|---|---|---|
ansond | 0:137634ff4186 | 1 | /* |
ansond | 0:137634ff4186 | 2 | * Elliptic curves over GF(p): generic functions |
ansond | 0:137634ff4186 | 3 | * |
ansond | 0:137634ff4186 | 4 | * Copyright (C) 2006-2014, ARM Limited, All Rights Reserved |
ansond | 0:137634ff4186 | 5 | * |
ansond | 0:137634ff4186 | 6 | * This file is part of mbed TLS (https://tls.mbed.org) |
ansond | 0:137634ff4186 | 7 | * |
ansond | 0:137634ff4186 | 8 | * This program is free software; you can redistribute it and/or modify |
ansond | 0:137634ff4186 | 9 | * it under the terms of the GNU General Public License as published by |
ansond | 0:137634ff4186 | 10 | * the Free Software Foundation; either version 2 of the License, or |
ansond | 0:137634ff4186 | 11 | * (at your option) any later version. |
ansond | 0:137634ff4186 | 12 | * |
ansond | 0:137634ff4186 | 13 | * This program is distributed in the hope that it will be useful, |
ansond | 0:137634ff4186 | 14 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
ansond | 0:137634ff4186 | 15 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
ansond | 0:137634ff4186 | 16 | * GNU General Public License for more details. |
ansond | 0:137634ff4186 | 17 | * |
ansond | 0:137634ff4186 | 18 | * You should have received a copy of the GNU General Public License along |
ansond | 0:137634ff4186 | 19 | * with this program; if not, write to the Free Software Foundation, Inc., |
ansond | 0:137634ff4186 | 20 | * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. |
ansond | 0:137634ff4186 | 21 | */ |
ansond | 0:137634ff4186 | 22 | |
ansond | 0:137634ff4186 | 23 | /* |
ansond | 0:137634ff4186 | 24 | * References: |
ansond | 0:137634ff4186 | 25 | * |
ansond | 0:137634ff4186 | 26 | * SEC1 http://www.secg.org/index.php?action=secg,docs_secg |
ansond | 0:137634ff4186 | 27 | * GECC = Guide to Elliptic Curve Cryptography - Hankerson, Menezes, Vanstone |
ansond | 0:137634ff4186 | 28 | * FIPS 186-3 http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf |
ansond | 0:137634ff4186 | 29 | * RFC 4492 for the related TLS structures and constants |
ansond | 0:137634ff4186 | 30 | * |
ansond | 0:137634ff4186 | 31 | * [M255] http://cr.yp.to/ecdh/curve25519-20060209.pdf |
ansond | 0:137634ff4186 | 32 | * |
ansond | 0:137634ff4186 | 33 | * [2] CORON, Jean-Sébastien. Resistance against differential power analysis |
ansond | 0:137634ff4186 | 34 | * for elliptic curve cryptosystems. In : Cryptographic Hardware and |
ansond | 0:137634ff4186 | 35 | * Embedded Systems. Springer Berlin Heidelberg, 1999. p. 292-302. |
ansond | 0:137634ff4186 | 36 | * <http://link.springer.com/chapter/10.1007/3-540-48059-5_25> |
ansond | 0:137634ff4186 | 37 | * |
ansond | 0:137634ff4186 | 38 | * [3] HEDABOU, Mustapha, PINEL, Pierre, et BÉNÉTEAU, Lucien. A comb method to |
ansond | 0:137634ff4186 | 39 | * render ECC resistant against Side Channel Attacks. IACR Cryptology |
ansond | 0:137634ff4186 | 40 | * ePrint Archive, 2004, vol. 2004, p. 342. |
ansond | 0:137634ff4186 | 41 | * <http://eprint.iacr.org/2004/342.pdf> |
ansond | 0:137634ff4186 | 42 | */ |
ansond | 0:137634ff4186 | 43 | |
ansond | 0:137634ff4186 | 44 | #if !defined(POLARSSL_CONFIG_FILE) |
ansond | 0:137634ff4186 | 45 | #include "polarssl/config.h" |
ansond | 0:137634ff4186 | 46 | #else |
ansond | 0:137634ff4186 | 47 | #include POLARSSL_CONFIG_FILE |
ansond | 0:137634ff4186 | 48 | #endif |
ansond | 0:137634ff4186 | 49 | |
ansond | 0:137634ff4186 | 50 | #if defined(POLARSSL_ECP_C) |
ansond | 0:137634ff4186 | 51 | |
ansond | 0:137634ff4186 | 52 | #include "polarssl/ecp.h" |
ansond | 0:137634ff4186 | 53 | |
ansond | 0:137634ff4186 | 54 | #include <string.h> |
ansond | 0:137634ff4186 | 55 | |
ansond | 0:137634ff4186 | 56 | #if defined(POLARSSL_PLATFORM_C) |
ansond | 0:137634ff4186 | 57 | #include "polarssl/platform.h" |
ansond | 0:137634ff4186 | 58 | #else |
ansond | 0:137634ff4186 | 59 | #include <stdlib.h> |
ansond | 0:137634ff4186 | 60 | #include <stdio.h> |
ansond | 0:137634ff4186 | 61 | #define polarssl_printf printf |
ansond | 0:137634ff4186 | 62 | #define polarssl_malloc malloc |
ansond | 0:137634ff4186 | 63 | #define polarssl_free free |
ansond | 0:137634ff4186 | 64 | #endif |
ansond | 0:137634ff4186 | 65 | |
ansond | 0:137634ff4186 | 66 | #if defined(_MSC_VER) && !defined strcasecmp && !defined(EFIX64) && \ |
ansond | 0:137634ff4186 | 67 | !defined(EFI32) |
ansond | 0:137634ff4186 | 68 | #define strcasecmp _stricmp |
ansond | 0:137634ff4186 | 69 | #endif |
ansond | 0:137634ff4186 | 70 | |
ansond | 0:137634ff4186 | 71 | #if defined(_MSC_VER) && !defined(inline) |
ansond | 0:137634ff4186 | 72 | #define inline _inline |
ansond | 0:137634ff4186 | 73 | #else |
ansond | 0:137634ff4186 | 74 | #if defined(__ARMCC_VERSION) && !defined(inline) |
ansond | 0:137634ff4186 | 75 | #define inline __inline |
ansond | 0:137634ff4186 | 76 | #endif /* __ARMCC_VERSION */ |
ansond | 0:137634ff4186 | 77 | #endif /*_MSC_VER */ |
ansond | 0:137634ff4186 | 78 | |
ansond | 0:137634ff4186 | 79 | /* Implementation that should never be optimized out by the compiler */ |
ansond | 0:137634ff4186 | 80 | static void polarssl_zeroize( void *v, size_t n ) { |
ansond | 0:137634ff4186 | 81 | volatile unsigned char *p = v; while( n-- ) *p++ = 0; |
ansond | 0:137634ff4186 | 82 | } |
ansond | 0:137634ff4186 | 83 | |
ansond | 0:137634ff4186 | 84 | #if defined(POLARSSL_SELF_TEST) |
ansond | 0:137634ff4186 | 85 | /* |
ansond | 0:137634ff4186 | 86 | * Counts of point addition and doubling, and field multiplications. |
ansond | 0:137634ff4186 | 87 | * Used to test resistance of point multiplication to simple timing attacks. |
ansond | 0:137634ff4186 | 88 | */ |
ansond | 0:137634ff4186 | 89 | static unsigned long add_count, dbl_count, mul_count; |
ansond | 0:137634ff4186 | 90 | #endif |
ansond | 0:137634ff4186 | 91 | |
ansond | 0:137634ff4186 | 92 | #if defined(POLARSSL_ECP_DP_SECP192R1_ENABLED) || \ |
ansond | 0:137634ff4186 | 93 | defined(POLARSSL_ECP_DP_SECP224R1_ENABLED) || \ |
ansond | 0:137634ff4186 | 94 | defined(POLARSSL_ECP_DP_SECP256R1_ENABLED) || \ |
ansond | 0:137634ff4186 | 95 | defined(POLARSSL_ECP_DP_SECP384R1_ENABLED) || \ |
ansond | 0:137634ff4186 | 96 | defined(POLARSSL_ECP_DP_SECP521R1_ENABLED) || \ |
ansond | 0:137634ff4186 | 97 | defined(POLARSSL_ECP_DP_BP256R1_ENABLED) || \ |
ansond | 0:137634ff4186 | 98 | defined(POLARSSL_ECP_DP_BP384R1_ENABLED) || \ |
ansond | 0:137634ff4186 | 99 | defined(POLARSSL_ECP_DP_BP512R1_ENABLED) || \ |
ansond | 0:137634ff4186 | 100 | defined(POLARSSL_ECP_DP_SECP192K1_ENABLED) || \ |
ansond | 0:137634ff4186 | 101 | defined(POLARSSL_ECP_DP_SECP224K1_ENABLED) || \ |
ansond | 0:137634ff4186 | 102 | defined(POLARSSL_ECP_DP_SECP256K1_ENABLED) |
ansond | 0:137634ff4186 | 103 | #define POLARSSL_ECP_SHORT_WEIERSTRASS |
ansond | 0:137634ff4186 | 104 | #endif |
ansond | 0:137634ff4186 | 105 | |
ansond | 0:137634ff4186 | 106 | #if defined(POLARSSL_ECP_DP_M221_ENABLED) || \ |
ansond | 0:137634ff4186 | 107 | defined(POLARSSL_ECP_DP_M255_ENABLED) || \ |
ansond | 0:137634ff4186 | 108 | defined(POLARSSL_ECP_DP_M383_ENABLED) || \ |
ansond | 0:137634ff4186 | 109 | defined(POLARSSL_ECP_DP_M511_ENABLED) |
ansond | 0:137634ff4186 | 110 | #define POLARSSL_ECP_MONTGOMERY |
ansond | 0:137634ff4186 | 111 | #endif |
ansond | 0:137634ff4186 | 112 | |
ansond | 0:137634ff4186 | 113 | /* |
ansond | 0:137634ff4186 | 114 | * Curve types: internal for now, might be exposed later |
ansond | 0:137634ff4186 | 115 | */ |
ansond | 0:137634ff4186 | 116 | typedef enum |
ansond | 0:137634ff4186 | 117 | { |
ansond | 0:137634ff4186 | 118 | POLARSSL_ECP_TYPE_NONE = 0, |
ansond | 0:137634ff4186 | 119 | POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS, /* y^2 = x^3 + a x + b */ |
ansond | 0:137634ff4186 | 120 | POLARSSL_ECP_TYPE_MONTGOMERY, /* y^2 = x^3 + a x^2 + x */ |
ansond | 0:137634ff4186 | 121 | } ecp_curve_type; |
ansond | 0:137634ff4186 | 122 | |
ansond | 0:137634ff4186 | 123 | /* |
ansond | 0:137634ff4186 | 124 | * List of supported curves: |
ansond | 0:137634ff4186 | 125 | * - internal ID |
ansond | 0:137634ff4186 | 126 | * - TLS NamedCurve ID (RFC 4492 sec. 5.1.1, RFC 7071 sec. 2) |
ansond | 0:137634ff4186 | 127 | * - size in bits |
ansond | 0:137634ff4186 | 128 | * - readable name |
ansond | 0:137634ff4186 | 129 | * |
ansond | 0:137634ff4186 | 130 | * Curves are listed in order: largest curves first, and for a given size, |
ansond | 0:137634ff4186 | 131 | * fastest curves first. This provides the default order for the SSL module. |
ansond | 0:137634ff4186 | 132 | */ |
ansond | 0:137634ff4186 | 133 | static const ecp_curve_info ecp_supported_curves[] = |
ansond | 0:137634ff4186 | 134 | { |
ansond | 0:137634ff4186 | 135 | #if defined(POLARSSL_ECP_DP_SECP521R1_ENABLED) |
ansond | 0:137634ff4186 | 136 | { POLARSSL_ECP_DP_SECP521R1, 25, 521, "secp521r1" }, |
ansond | 0:137634ff4186 | 137 | #endif |
ansond | 0:137634ff4186 | 138 | #if defined(POLARSSL_ECP_DP_BP512R1_ENABLED) |
ansond | 0:137634ff4186 | 139 | { POLARSSL_ECP_DP_BP512R1, 28, 512, "brainpoolP512r1" }, |
ansond | 0:137634ff4186 | 140 | #endif |
ansond | 0:137634ff4186 | 141 | #if defined(POLARSSL_ECP_DP_SECP384R1_ENABLED) |
ansond | 0:137634ff4186 | 142 | { POLARSSL_ECP_DP_SECP384R1, 24, 384, "secp384r1" }, |
ansond | 0:137634ff4186 | 143 | #endif |
ansond | 0:137634ff4186 | 144 | #if defined(POLARSSL_ECP_DP_BP384R1_ENABLED) |
ansond | 0:137634ff4186 | 145 | { POLARSSL_ECP_DP_BP384R1, 27, 384, "brainpoolP384r1" }, |
ansond | 0:137634ff4186 | 146 | #endif |
ansond | 0:137634ff4186 | 147 | #if defined(POLARSSL_ECP_DP_SECP256R1_ENABLED) |
ansond | 0:137634ff4186 | 148 | { POLARSSL_ECP_DP_SECP256R1, 23, 256, "secp256r1" }, |
ansond | 0:137634ff4186 | 149 | #endif |
ansond | 0:137634ff4186 | 150 | #if defined(POLARSSL_ECP_DP_SECP256K1_ENABLED) |
ansond | 0:137634ff4186 | 151 | { POLARSSL_ECP_DP_SECP256K1, 22, 256, "secp256k1" }, |
ansond | 0:137634ff4186 | 152 | #endif |
ansond | 0:137634ff4186 | 153 | #if defined(POLARSSL_ECP_DP_BP256R1_ENABLED) |
ansond | 0:137634ff4186 | 154 | { POLARSSL_ECP_DP_BP256R1, 26, 256, "brainpoolP256r1" }, |
ansond | 0:137634ff4186 | 155 | #endif |
ansond | 0:137634ff4186 | 156 | #if defined(POLARSSL_ECP_DP_SECP224R1_ENABLED) |
ansond | 0:137634ff4186 | 157 | { POLARSSL_ECP_DP_SECP224R1, 21, 224, "secp224r1" }, |
ansond | 0:137634ff4186 | 158 | #endif |
ansond | 0:137634ff4186 | 159 | #if defined(POLARSSL_ECP_DP_SECP224K1_ENABLED) |
ansond | 0:137634ff4186 | 160 | { POLARSSL_ECP_DP_SECP224K1, 20, 224, "secp224k1" }, |
ansond | 0:137634ff4186 | 161 | #endif |
ansond | 0:137634ff4186 | 162 | #if defined(POLARSSL_ECP_DP_SECP192R1_ENABLED) |
ansond | 0:137634ff4186 | 163 | { POLARSSL_ECP_DP_SECP192R1, 19, 192, "secp192r1" }, |
ansond | 0:137634ff4186 | 164 | #endif |
ansond | 0:137634ff4186 | 165 | #if defined(POLARSSL_ECP_DP_SECP192K1_ENABLED) |
ansond | 0:137634ff4186 | 166 | { POLARSSL_ECP_DP_SECP192K1, 18, 192, "secp192k1" }, |
ansond | 0:137634ff4186 | 167 | #endif |
ansond | 0:137634ff4186 | 168 | { POLARSSL_ECP_DP_NONE, 0, 0, NULL }, |
ansond | 0:137634ff4186 | 169 | }; |
ansond | 0:137634ff4186 | 170 | |
ansond | 0:137634ff4186 | 171 | #define ECP_NB_CURVES sizeof( ecp_supported_curves ) / \ |
ansond | 0:137634ff4186 | 172 | sizeof( ecp_supported_curves[0] ) |
ansond | 0:137634ff4186 | 173 | |
ansond | 0:137634ff4186 | 174 | static ecp_group_id ecp_supported_grp_id[ECP_NB_CURVES]; |
ansond | 0:137634ff4186 | 175 | |
ansond | 0:137634ff4186 | 176 | /* |
ansond | 0:137634ff4186 | 177 | * List of supported curves and associated info |
ansond | 0:137634ff4186 | 178 | */ |
ansond | 0:137634ff4186 | 179 | const ecp_curve_info *ecp_curve_list( void ) |
ansond | 0:137634ff4186 | 180 | { |
ansond | 0:137634ff4186 | 181 | return( ecp_supported_curves ); |
ansond | 0:137634ff4186 | 182 | } |
ansond | 0:137634ff4186 | 183 | |
ansond | 0:137634ff4186 | 184 | /* |
ansond | 0:137634ff4186 | 185 | * List of supported curves, group ID only |
ansond | 0:137634ff4186 | 186 | */ |
ansond | 0:137634ff4186 | 187 | const ecp_group_id *ecp_grp_id_list( void ) |
ansond | 0:137634ff4186 | 188 | { |
ansond | 0:137634ff4186 | 189 | static int init_done = 0; |
ansond | 0:137634ff4186 | 190 | |
ansond | 0:137634ff4186 | 191 | if( ! init_done ) |
ansond | 0:137634ff4186 | 192 | { |
ansond | 0:137634ff4186 | 193 | size_t i = 0; |
ansond | 0:137634ff4186 | 194 | const ecp_curve_info *curve_info; |
ansond | 0:137634ff4186 | 195 | |
ansond | 0:137634ff4186 | 196 | for( curve_info = ecp_curve_list(); |
ansond | 0:137634ff4186 | 197 | curve_info->grp_id != POLARSSL_ECP_DP_NONE; |
ansond | 0:137634ff4186 | 198 | curve_info++ ) |
ansond | 0:137634ff4186 | 199 | { |
ansond | 0:137634ff4186 | 200 | ecp_supported_grp_id[i++] = curve_info->grp_id; |
ansond | 0:137634ff4186 | 201 | } |
ansond | 0:137634ff4186 | 202 | ecp_supported_grp_id[i] = POLARSSL_ECP_DP_NONE; |
ansond | 0:137634ff4186 | 203 | |
ansond | 0:137634ff4186 | 204 | init_done = 1; |
ansond | 0:137634ff4186 | 205 | } |
ansond | 0:137634ff4186 | 206 | |
ansond | 0:137634ff4186 | 207 | return( ecp_supported_grp_id ); |
ansond | 0:137634ff4186 | 208 | } |
ansond | 0:137634ff4186 | 209 | |
ansond | 0:137634ff4186 | 210 | /* |
ansond | 0:137634ff4186 | 211 | * Get the curve info for the internal identifier |
ansond | 0:137634ff4186 | 212 | */ |
ansond | 0:137634ff4186 | 213 | const ecp_curve_info *ecp_curve_info_from_grp_id( ecp_group_id grp_id ) |
ansond | 0:137634ff4186 | 214 | { |
ansond | 0:137634ff4186 | 215 | const ecp_curve_info *curve_info; |
ansond | 0:137634ff4186 | 216 | |
ansond | 0:137634ff4186 | 217 | for( curve_info = ecp_curve_list(); |
ansond | 0:137634ff4186 | 218 | curve_info->grp_id != POLARSSL_ECP_DP_NONE; |
ansond | 0:137634ff4186 | 219 | curve_info++ ) |
ansond | 0:137634ff4186 | 220 | { |
ansond | 0:137634ff4186 | 221 | if( curve_info->grp_id == grp_id ) |
ansond | 0:137634ff4186 | 222 | return( curve_info ); |
ansond | 0:137634ff4186 | 223 | } |
ansond | 0:137634ff4186 | 224 | |
ansond | 0:137634ff4186 | 225 | return( NULL ); |
ansond | 0:137634ff4186 | 226 | } |
ansond | 0:137634ff4186 | 227 | |
ansond | 0:137634ff4186 | 228 | /* |
ansond | 0:137634ff4186 | 229 | * Get the curve info from the TLS identifier |
ansond | 0:137634ff4186 | 230 | */ |
ansond | 0:137634ff4186 | 231 | const ecp_curve_info *ecp_curve_info_from_tls_id( uint16_t tls_id ) |
ansond | 0:137634ff4186 | 232 | { |
ansond | 0:137634ff4186 | 233 | const ecp_curve_info *curve_info; |
ansond | 0:137634ff4186 | 234 | |
ansond | 0:137634ff4186 | 235 | for( curve_info = ecp_curve_list(); |
ansond | 0:137634ff4186 | 236 | curve_info->grp_id != POLARSSL_ECP_DP_NONE; |
ansond | 0:137634ff4186 | 237 | curve_info++ ) |
ansond | 0:137634ff4186 | 238 | { |
ansond | 0:137634ff4186 | 239 | if( curve_info->tls_id == tls_id ) |
ansond | 0:137634ff4186 | 240 | return( curve_info ); |
ansond | 0:137634ff4186 | 241 | } |
ansond | 0:137634ff4186 | 242 | |
ansond | 0:137634ff4186 | 243 | return( NULL ); |
ansond | 0:137634ff4186 | 244 | } |
ansond | 0:137634ff4186 | 245 | |
ansond | 0:137634ff4186 | 246 | /* |
ansond | 0:137634ff4186 | 247 | * Get the curve info from the name |
ansond | 0:137634ff4186 | 248 | */ |
ansond | 0:137634ff4186 | 249 | const ecp_curve_info *ecp_curve_info_from_name( const char *name ) |
ansond | 0:137634ff4186 | 250 | { |
ansond | 0:137634ff4186 | 251 | const ecp_curve_info *curve_info; |
ansond | 0:137634ff4186 | 252 | |
ansond | 0:137634ff4186 | 253 | for( curve_info = ecp_curve_list(); |
ansond | 0:137634ff4186 | 254 | curve_info->grp_id != POLARSSL_ECP_DP_NONE; |
ansond | 0:137634ff4186 | 255 | curve_info++ ) |
ansond | 0:137634ff4186 | 256 | { |
ansond | 0:137634ff4186 | 257 | if( strcasecmp( curve_info->name, name ) == 0 ) |
ansond | 0:137634ff4186 | 258 | return( curve_info ); |
ansond | 0:137634ff4186 | 259 | } |
ansond | 0:137634ff4186 | 260 | |
ansond | 0:137634ff4186 | 261 | return( NULL ); |
ansond | 0:137634ff4186 | 262 | } |
ansond | 0:137634ff4186 | 263 | |
ansond | 0:137634ff4186 | 264 | /* |
ansond | 0:137634ff4186 | 265 | * Get the type of a curve |
ansond | 0:137634ff4186 | 266 | */ |
ansond | 0:137634ff4186 | 267 | static inline ecp_curve_type ecp_get_type( const ecp_group *grp ) |
ansond | 0:137634ff4186 | 268 | { |
ansond | 0:137634ff4186 | 269 | if( grp->G.X.p == NULL ) |
ansond | 0:137634ff4186 | 270 | return( POLARSSL_ECP_TYPE_NONE ); |
ansond | 0:137634ff4186 | 271 | |
ansond | 0:137634ff4186 | 272 | if( grp->G.Y.p == NULL ) |
ansond | 0:137634ff4186 | 273 | return( POLARSSL_ECP_TYPE_MONTGOMERY ); |
ansond | 0:137634ff4186 | 274 | else |
ansond | 0:137634ff4186 | 275 | return( POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS ); |
ansond | 0:137634ff4186 | 276 | } |
ansond | 0:137634ff4186 | 277 | |
ansond | 0:137634ff4186 | 278 | /* |
ansond | 0:137634ff4186 | 279 | * Initialize (the components of) a point |
ansond | 0:137634ff4186 | 280 | */ |
ansond | 0:137634ff4186 | 281 | void ecp_point_init( ecp_point *pt ) |
ansond | 0:137634ff4186 | 282 | { |
ansond | 0:137634ff4186 | 283 | if( pt == NULL ) |
ansond | 0:137634ff4186 | 284 | return; |
ansond | 0:137634ff4186 | 285 | |
ansond | 0:137634ff4186 | 286 | mpi_init( &pt->X ); |
ansond | 0:137634ff4186 | 287 | mpi_init( &pt->Y ); |
ansond | 0:137634ff4186 | 288 | mpi_init( &pt->Z ); |
ansond | 0:137634ff4186 | 289 | } |
ansond | 0:137634ff4186 | 290 | |
ansond | 0:137634ff4186 | 291 | /* |
ansond | 0:137634ff4186 | 292 | * Initialize (the components of) a group |
ansond | 0:137634ff4186 | 293 | */ |
ansond | 0:137634ff4186 | 294 | void ecp_group_init( ecp_group *grp ) |
ansond | 0:137634ff4186 | 295 | { |
ansond | 0:137634ff4186 | 296 | if( grp == NULL ) |
ansond | 0:137634ff4186 | 297 | return; |
ansond | 0:137634ff4186 | 298 | |
ansond | 0:137634ff4186 | 299 | memset( grp, 0, sizeof( ecp_group ) ); |
ansond | 0:137634ff4186 | 300 | } |
ansond | 0:137634ff4186 | 301 | |
ansond | 0:137634ff4186 | 302 | /* |
ansond | 0:137634ff4186 | 303 | * Initialize (the components of) a key pair |
ansond | 0:137634ff4186 | 304 | */ |
ansond | 0:137634ff4186 | 305 | void ecp_keypair_init( ecp_keypair *key ) |
ansond | 0:137634ff4186 | 306 | { |
ansond | 0:137634ff4186 | 307 | if( key == NULL ) |
ansond | 0:137634ff4186 | 308 | return; |
ansond | 0:137634ff4186 | 309 | |
ansond | 0:137634ff4186 | 310 | ecp_group_init( &key->grp ); |
ansond | 0:137634ff4186 | 311 | mpi_init( &key->d ); |
ansond | 0:137634ff4186 | 312 | ecp_point_init( &key->Q ); |
ansond | 0:137634ff4186 | 313 | } |
ansond | 0:137634ff4186 | 314 | |
ansond | 0:137634ff4186 | 315 | /* |
ansond | 0:137634ff4186 | 316 | * Unallocate (the components of) a point |
ansond | 0:137634ff4186 | 317 | */ |
ansond | 0:137634ff4186 | 318 | void ecp_point_free( ecp_point *pt ) |
ansond | 0:137634ff4186 | 319 | { |
ansond | 0:137634ff4186 | 320 | if( pt == NULL ) |
ansond | 0:137634ff4186 | 321 | return; |
ansond | 0:137634ff4186 | 322 | |
ansond | 0:137634ff4186 | 323 | mpi_free( &( pt->X ) ); |
ansond | 0:137634ff4186 | 324 | mpi_free( &( pt->Y ) ); |
ansond | 0:137634ff4186 | 325 | mpi_free( &( pt->Z ) ); |
ansond | 0:137634ff4186 | 326 | } |
ansond | 0:137634ff4186 | 327 | |
ansond | 0:137634ff4186 | 328 | /* |
ansond | 0:137634ff4186 | 329 | * Unallocate (the components of) a group |
ansond | 0:137634ff4186 | 330 | */ |
ansond | 0:137634ff4186 | 331 | void ecp_group_free( ecp_group *grp ) |
ansond | 0:137634ff4186 | 332 | { |
ansond | 0:137634ff4186 | 333 | size_t i; |
ansond | 0:137634ff4186 | 334 | |
ansond | 0:137634ff4186 | 335 | if( grp == NULL ) |
ansond | 0:137634ff4186 | 336 | return; |
ansond | 0:137634ff4186 | 337 | |
ansond | 0:137634ff4186 | 338 | if( grp->h != 1 ) |
ansond | 0:137634ff4186 | 339 | { |
ansond | 0:137634ff4186 | 340 | mpi_free( &grp->P ); |
ansond | 0:137634ff4186 | 341 | mpi_free( &grp->A ); |
ansond | 0:137634ff4186 | 342 | mpi_free( &grp->B ); |
ansond | 0:137634ff4186 | 343 | ecp_point_free( &grp->G ); |
ansond | 0:137634ff4186 | 344 | mpi_free( &grp->N ); |
ansond | 0:137634ff4186 | 345 | } |
ansond | 0:137634ff4186 | 346 | |
ansond | 0:137634ff4186 | 347 | if( grp->T != NULL ) |
ansond | 0:137634ff4186 | 348 | { |
ansond | 0:137634ff4186 | 349 | for( i = 0; i < grp->T_size; i++ ) |
ansond | 0:137634ff4186 | 350 | ecp_point_free( &grp->T[i] ); |
ansond | 0:137634ff4186 | 351 | polarssl_free( grp->T ); |
ansond | 0:137634ff4186 | 352 | } |
ansond | 0:137634ff4186 | 353 | |
ansond | 0:137634ff4186 | 354 | polarssl_zeroize( grp, sizeof( ecp_group ) ); |
ansond | 0:137634ff4186 | 355 | } |
ansond | 0:137634ff4186 | 356 | |
ansond | 0:137634ff4186 | 357 | /* |
ansond | 0:137634ff4186 | 358 | * Unallocate (the components of) a key pair |
ansond | 0:137634ff4186 | 359 | */ |
ansond | 0:137634ff4186 | 360 | void ecp_keypair_free( ecp_keypair *key ) |
ansond | 0:137634ff4186 | 361 | { |
ansond | 0:137634ff4186 | 362 | if( key == NULL ) |
ansond | 0:137634ff4186 | 363 | return; |
ansond | 0:137634ff4186 | 364 | |
ansond | 0:137634ff4186 | 365 | ecp_group_free( &key->grp ); |
ansond | 0:137634ff4186 | 366 | mpi_free( &key->d ); |
ansond | 0:137634ff4186 | 367 | ecp_point_free( &key->Q ); |
ansond | 0:137634ff4186 | 368 | } |
ansond | 0:137634ff4186 | 369 | |
ansond | 0:137634ff4186 | 370 | /* |
ansond | 0:137634ff4186 | 371 | * Copy the contents of a point |
ansond | 0:137634ff4186 | 372 | */ |
ansond | 0:137634ff4186 | 373 | int ecp_copy( ecp_point *P, const ecp_point *Q ) |
ansond | 0:137634ff4186 | 374 | { |
ansond | 0:137634ff4186 | 375 | int ret; |
ansond | 0:137634ff4186 | 376 | |
ansond | 0:137634ff4186 | 377 | MPI_CHK( mpi_copy( &P->X, &Q->X ) ); |
ansond | 0:137634ff4186 | 378 | MPI_CHK( mpi_copy( &P->Y, &Q->Y ) ); |
ansond | 0:137634ff4186 | 379 | MPI_CHK( mpi_copy( &P->Z, &Q->Z ) ); |
ansond | 0:137634ff4186 | 380 | |
ansond | 0:137634ff4186 | 381 | cleanup: |
ansond | 0:137634ff4186 | 382 | return( ret ); |
ansond | 0:137634ff4186 | 383 | } |
ansond | 0:137634ff4186 | 384 | |
ansond | 0:137634ff4186 | 385 | /* |
ansond | 0:137634ff4186 | 386 | * Copy the contents of a group object |
ansond | 0:137634ff4186 | 387 | */ |
ansond | 0:137634ff4186 | 388 | int ecp_group_copy( ecp_group *dst, const ecp_group *src ) |
ansond | 0:137634ff4186 | 389 | { |
ansond | 0:137634ff4186 | 390 | return ecp_use_known_dp( dst, src->id ); |
ansond | 0:137634ff4186 | 391 | } |
ansond | 0:137634ff4186 | 392 | |
ansond | 0:137634ff4186 | 393 | /* |
ansond | 0:137634ff4186 | 394 | * Set point to zero |
ansond | 0:137634ff4186 | 395 | */ |
ansond | 0:137634ff4186 | 396 | int ecp_set_zero( ecp_point *pt ) |
ansond | 0:137634ff4186 | 397 | { |
ansond | 0:137634ff4186 | 398 | int ret; |
ansond | 0:137634ff4186 | 399 | |
ansond | 0:137634ff4186 | 400 | MPI_CHK( mpi_lset( &pt->X , 1 ) ); |
ansond | 0:137634ff4186 | 401 | MPI_CHK( mpi_lset( &pt->Y , 1 ) ); |
ansond | 0:137634ff4186 | 402 | MPI_CHK( mpi_lset( &pt->Z , 0 ) ); |
ansond | 0:137634ff4186 | 403 | |
ansond | 0:137634ff4186 | 404 | cleanup: |
ansond | 0:137634ff4186 | 405 | return( ret ); |
ansond | 0:137634ff4186 | 406 | } |
ansond | 0:137634ff4186 | 407 | |
ansond | 0:137634ff4186 | 408 | /* |
ansond | 0:137634ff4186 | 409 | * Tell if a point is zero |
ansond | 0:137634ff4186 | 410 | */ |
ansond | 0:137634ff4186 | 411 | int ecp_is_zero( ecp_point *pt ) |
ansond | 0:137634ff4186 | 412 | { |
ansond | 0:137634ff4186 | 413 | return( mpi_cmp_int( &pt->Z, 0 ) == 0 ); |
ansond | 0:137634ff4186 | 414 | } |
ansond | 0:137634ff4186 | 415 | |
ansond | 0:137634ff4186 | 416 | /* |
ansond | 0:137634ff4186 | 417 | * Import a non-zero point from ASCII strings |
ansond | 0:137634ff4186 | 418 | */ |
ansond | 0:137634ff4186 | 419 | int ecp_point_read_string( ecp_point *P, int radix, |
ansond | 0:137634ff4186 | 420 | const char *x, const char *y ) |
ansond | 0:137634ff4186 | 421 | { |
ansond | 0:137634ff4186 | 422 | int ret; |
ansond | 0:137634ff4186 | 423 | |
ansond | 0:137634ff4186 | 424 | MPI_CHK( mpi_read_string( &P->X, radix, x ) ); |
ansond | 0:137634ff4186 | 425 | MPI_CHK( mpi_read_string( &P->Y, radix, y ) ); |
ansond | 0:137634ff4186 | 426 | MPI_CHK( mpi_lset( &P->Z, 1 ) ); |
ansond | 0:137634ff4186 | 427 | |
ansond | 0:137634ff4186 | 428 | cleanup: |
ansond | 0:137634ff4186 | 429 | return( ret ); |
ansond | 0:137634ff4186 | 430 | } |
ansond | 0:137634ff4186 | 431 | |
ansond | 0:137634ff4186 | 432 | /* |
ansond | 0:137634ff4186 | 433 | * Export a point into unsigned binary data (SEC1 2.3.3) |
ansond | 0:137634ff4186 | 434 | */ |
ansond | 0:137634ff4186 | 435 | int ecp_point_write_binary( const ecp_group *grp, const ecp_point *P, |
ansond | 0:137634ff4186 | 436 | int format, size_t *olen, |
ansond | 0:137634ff4186 | 437 | unsigned char *buf, size_t buflen ) |
ansond | 0:137634ff4186 | 438 | { |
ansond | 0:137634ff4186 | 439 | int ret = 0; |
ansond | 0:137634ff4186 | 440 | size_t plen; |
ansond | 0:137634ff4186 | 441 | |
ansond | 0:137634ff4186 | 442 | if( format != POLARSSL_ECP_PF_UNCOMPRESSED && |
ansond | 0:137634ff4186 | 443 | format != POLARSSL_ECP_PF_COMPRESSED ) |
ansond | 0:137634ff4186 | 444 | return( POLARSSL_ERR_ECP_BAD_INPUT_DATA ); |
ansond | 0:137634ff4186 | 445 | |
ansond | 0:137634ff4186 | 446 | /* |
ansond | 0:137634ff4186 | 447 | * Common case: P == 0 |
ansond | 0:137634ff4186 | 448 | */ |
ansond | 0:137634ff4186 | 449 | if( mpi_cmp_int( &P->Z, 0 ) == 0 ) |
ansond | 0:137634ff4186 | 450 | { |
ansond | 0:137634ff4186 | 451 | if( buflen < 1 ) |
ansond | 0:137634ff4186 | 452 | return( POLARSSL_ERR_ECP_BUFFER_TOO_SMALL ); |
ansond | 0:137634ff4186 | 453 | |
ansond | 0:137634ff4186 | 454 | buf[0] = 0x00; |
ansond | 0:137634ff4186 | 455 | *olen = 1; |
ansond | 0:137634ff4186 | 456 | |
ansond | 0:137634ff4186 | 457 | return( 0 ); |
ansond | 0:137634ff4186 | 458 | } |
ansond | 0:137634ff4186 | 459 | |
ansond | 0:137634ff4186 | 460 | plen = mpi_size( &grp->P ); |
ansond | 0:137634ff4186 | 461 | |
ansond | 0:137634ff4186 | 462 | if( format == POLARSSL_ECP_PF_UNCOMPRESSED ) |
ansond | 0:137634ff4186 | 463 | { |
ansond | 0:137634ff4186 | 464 | *olen = 2 * plen + 1; |
ansond | 0:137634ff4186 | 465 | |
ansond | 0:137634ff4186 | 466 | if( buflen < *olen ) |
ansond | 0:137634ff4186 | 467 | return( POLARSSL_ERR_ECP_BUFFER_TOO_SMALL ); |
ansond | 0:137634ff4186 | 468 | |
ansond | 0:137634ff4186 | 469 | buf[0] = 0x04; |
ansond | 0:137634ff4186 | 470 | MPI_CHK( mpi_write_binary( &P->X, buf + 1, plen ) ); |
ansond | 0:137634ff4186 | 471 | MPI_CHK( mpi_write_binary( &P->Y, buf + 1 + plen, plen ) ); |
ansond | 0:137634ff4186 | 472 | } |
ansond | 0:137634ff4186 | 473 | else if( format == POLARSSL_ECP_PF_COMPRESSED ) |
ansond | 0:137634ff4186 | 474 | { |
ansond | 0:137634ff4186 | 475 | *olen = plen + 1; |
ansond | 0:137634ff4186 | 476 | |
ansond | 0:137634ff4186 | 477 | if( buflen < *olen ) |
ansond | 0:137634ff4186 | 478 | return( POLARSSL_ERR_ECP_BUFFER_TOO_SMALL ); |
ansond | 0:137634ff4186 | 479 | |
ansond | 0:137634ff4186 | 480 | buf[0] = 0x02 + mpi_get_bit( &P->Y, 0 ); |
ansond | 0:137634ff4186 | 481 | MPI_CHK( mpi_write_binary( &P->X, buf + 1, plen ) ); |
ansond | 0:137634ff4186 | 482 | } |
ansond | 0:137634ff4186 | 483 | |
ansond | 0:137634ff4186 | 484 | cleanup: |
ansond | 0:137634ff4186 | 485 | return( ret ); |
ansond | 0:137634ff4186 | 486 | } |
ansond | 0:137634ff4186 | 487 | |
ansond | 0:137634ff4186 | 488 | /* |
ansond | 0:137634ff4186 | 489 | * Import a point from unsigned binary data (SEC1 2.3.4) |
ansond | 0:137634ff4186 | 490 | */ |
ansond | 0:137634ff4186 | 491 | int ecp_point_read_binary( const ecp_group *grp, ecp_point *pt, |
ansond | 0:137634ff4186 | 492 | const unsigned char *buf, size_t ilen ) |
ansond | 0:137634ff4186 | 493 | { |
ansond | 0:137634ff4186 | 494 | int ret; |
ansond | 0:137634ff4186 | 495 | size_t plen; |
ansond | 0:137634ff4186 | 496 | |
ansond | 0:137634ff4186 | 497 | if( ilen < 1 ) |
ansond | 0:137634ff4186 | 498 | return( POLARSSL_ERR_ECP_BAD_INPUT_DATA ); |
ansond | 0:137634ff4186 | 499 | |
ansond | 0:137634ff4186 | 500 | if( buf[0] == 0x00 ) |
ansond | 0:137634ff4186 | 501 | { |
ansond | 0:137634ff4186 | 502 | if( ilen == 1 ) |
ansond | 0:137634ff4186 | 503 | return( ecp_set_zero( pt ) ); |
ansond | 0:137634ff4186 | 504 | else |
ansond | 0:137634ff4186 | 505 | return( POLARSSL_ERR_ECP_BAD_INPUT_DATA ); |
ansond | 0:137634ff4186 | 506 | } |
ansond | 0:137634ff4186 | 507 | |
ansond | 0:137634ff4186 | 508 | plen = mpi_size( &grp->P ); |
ansond | 0:137634ff4186 | 509 | |
ansond | 0:137634ff4186 | 510 | if( buf[0] != 0x04 ) |
ansond | 0:137634ff4186 | 511 | return( POLARSSL_ERR_ECP_FEATURE_UNAVAILABLE ); |
ansond | 0:137634ff4186 | 512 | |
ansond | 0:137634ff4186 | 513 | if( ilen != 2 * plen + 1 ) |
ansond | 0:137634ff4186 | 514 | return( POLARSSL_ERR_ECP_BAD_INPUT_DATA ); |
ansond | 0:137634ff4186 | 515 | |
ansond | 0:137634ff4186 | 516 | MPI_CHK( mpi_read_binary( &pt->X, buf + 1, plen ) ); |
ansond | 0:137634ff4186 | 517 | MPI_CHK( mpi_read_binary( &pt->Y, buf + 1 + plen, plen ) ); |
ansond | 0:137634ff4186 | 518 | MPI_CHK( mpi_lset( &pt->Z, 1 ) ); |
ansond | 0:137634ff4186 | 519 | |
ansond | 0:137634ff4186 | 520 | cleanup: |
ansond | 0:137634ff4186 | 521 | return( ret ); |
ansond | 0:137634ff4186 | 522 | } |
ansond | 0:137634ff4186 | 523 | |
ansond | 0:137634ff4186 | 524 | /* |
ansond | 0:137634ff4186 | 525 | * Import a point from a TLS ECPoint record (RFC 4492) |
ansond | 0:137634ff4186 | 526 | * struct { |
ansond | 0:137634ff4186 | 527 | * opaque point <1..2^8-1>; |
ansond | 0:137634ff4186 | 528 | * } ECPoint; |
ansond | 0:137634ff4186 | 529 | */ |
ansond | 0:137634ff4186 | 530 | int ecp_tls_read_point( const ecp_group *grp, ecp_point *pt, |
ansond | 0:137634ff4186 | 531 | const unsigned char **buf, size_t buf_len ) |
ansond | 0:137634ff4186 | 532 | { |
ansond | 0:137634ff4186 | 533 | unsigned char data_len; |
ansond | 0:137634ff4186 | 534 | const unsigned char *buf_start; |
ansond | 0:137634ff4186 | 535 | |
ansond | 0:137634ff4186 | 536 | /* |
ansond | 0:137634ff4186 | 537 | * We must have at least two bytes (1 for length, at least one for data) |
ansond | 0:137634ff4186 | 538 | */ |
ansond | 0:137634ff4186 | 539 | if( buf_len < 2 ) |
ansond | 0:137634ff4186 | 540 | return( POLARSSL_ERR_ECP_BAD_INPUT_DATA ); |
ansond | 0:137634ff4186 | 541 | |
ansond | 0:137634ff4186 | 542 | data_len = *(*buf)++; |
ansond | 0:137634ff4186 | 543 | if( data_len < 1 || data_len > buf_len - 1 ) |
ansond | 0:137634ff4186 | 544 | return( POLARSSL_ERR_ECP_BAD_INPUT_DATA ); |
ansond | 0:137634ff4186 | 545 | |
ansond | 0:137634ff4186 | 546 | /* |
ansond | 0:137634ff4186 | 547 | * Save buffer start for read_binary and update buf |
ansond | 0:137634ff4186 | 548 | */ |
ansond | 0:137634ff4186 | 549 | buf_start = *buf; |
ansond | 0:137634ff4186 | 550 | *buf += data_len; |
ansond | 0:137634ff4186 | 551 | |
ansond | 0:137634ff4186 | 552 | return ecp_point_read_binary( grp, pt, buf_start, data_len ); |
ansond | 0:137634ff4186 | 553 | } |
ansond | 0:137634ff4186 | 554 | |
ansond | 0:137634ff4186 | 555 | /* |
ansond | 0:137634ff4186 | 556 | * Export a point as a TLS ECPoint record (RFC 4492) |
ansond | 0:137634ff4186 | 557 | * struct { |
ansond | 0:137634ff4186 | 558 | * opaque point <1..2^8-1>; |
ansond | 0:137634ff4186 | 559 | * } ECPoint; |
ansond | 0:137634ff4186 | 560 | */ |
ansond | 0:137634ff4186 | 561 | int ecp_tls_write_point( const ecp_group *grp, const ecp_point *pt, |
ansond | 0:137634ff4186 | 562 | int format, size_t *olen, |
ansond | 0:137634ff4186 | 563 | unsigned char *buf, size_t blen ) |
ansond | 0:137634ff4186 | 564 | { |
ansond | 0:137634ff4186 | 565 | int ret; |
ansond | 0:137634ff4186 | 566 | |
ansond | 0:137634ff4186 | 567 | /* |
ansond | 0:137634ff4186 | 568 | * buffer length must be at least one, for our length byte |
ansond | 0:137634ff4186 | 569 | */ |
ansond | 0:137634ff4186 | 570 | if( blen < 1 ) |
ansond | 0:137634ff4186 | 571 | return( POLARSSL_ERR_ECP_BAD_INPUT_DATA ); |
ansond | 0:137634ff4186 | 572 | |
ansond | 0:137634ff4186 | 573 | if( ( ret = ecp_point_write_binary( grp, pt, format, |
ansond | 0:137634ff4186 | 574 | olen, buf + 1, blen - 1) ) != 0 ) |
ansond | 0:137634ff4186 | 575 | return( ret ); |
ansond | 0:137634ff4186 | 576 | |
ansond | 0:137634ff4186 | 577 | /* |
ansond | 0:137634ff4186 | 578 | * write length to the first byte and update total length |
ansond | 0:137634ff4186 | 579 | */ |
ansond | 0:137634ff4186 | 580 | buf[0] = (unsigned char) *olen; |
ansond | 0:137634ff4186 | 581 | ++*olen; |
ansond | 0:137634ff4186 | 582 | |
ansond | 0:137634ff4186 | 583 | return( 0 ); |
ansond | 0:137634ff4186 | 584 | } |
ansond | 0:137634ff4186 | 585 | |
ansond | 0:137634ff4186 | 586 | /* |
ansond | 0:137634ff4186 | 587 | * Import an ECP group from ASCII strings, case A == -3 |
ansond | 0:137634ff4186 | 588 | */ |
ansond | 0:137634ff4186 | 589 | int ecp_group_read_string( ecp_group *grp, int radix, |
ansond | 0:137634ff4186 | 590 | const char *p, const char *b, |
ansond | 0:137634ff4186 | 591 | const char *gx, const char *gy, const char *n) |
ansond | 0:137634ff4186 | 592 | { |
ansond | 0:137634ff4186 | 593 | int ret; |
ansond | 0:137634ff4186 | 594 | |
ansond | 0:137634ff4186 | 595 | MPI_CHK( mpi_read_string( &grp->P, radix, p ) ); |
ansond | 0:137634ff4186 | 596 | MPI_CHK( mpi_read_string( &grp->B, radix, b ) ); |
ansond | 0:137634ff4186 | 597 | MPI_CHK( ecp_point_read_string( &grp->G, radix, gx, gy ) ); |
ansond | 0:137634ff4186 | 598 | MPI_CHK( mpi_read_string( &grp->N, radix, n ) ); |
ansond | 0:137634ff4186 | 599 | |
ansond | 0:137634ff4186 | 600 | grp->pbits = mpi_msb( &grp->P ); |
ansond | 0:137634ff4186 | 601 | grp->nbits = mpi_msb( &grp->N ); |
ansond | 0:137634ff4186 | 602 | |
ansond | 0:137634ff4186 | 603 | cleanup: |
ansond | 0:137634ff4186 | 604 | if( ret != 0 ) |
ansond | 0:137634ff4186 | 605 | ecp_group_free( grp ); |
ansond | 0:137634ff4186 | 606 | |
ansond | 0:137634ff4186 | 607 | return( ret ); |
ansond | 0:137634ff4186 | 608 | } |
ansond | 0:137634ff4186 | 609 | |
ansond | 0:137634ff4186 | 610 | /* |
ansond | 0:137634ff4186 | 611 | * Set a group from an ECParameters record (RFC 4492) |
ansond | 0:137634ff4186 | 612 | */ |
ansond | 0:137634ff4186 | 613 | int ecp_tls_read_group( ecp_group *grp, const unsigned char **buf, size_t len ) |
ansond | 0:137634ff4186 | 614 | { |
ansond | 0:137634ff4186 | 615 | uint16_t tls_id; |
ansond | 0:137634ff4186 | 616 | const ecp_curve_info *curve_info; |
ansond | 0:137634ff4186 | 617 | |
ansond | 0:137634ff4186 | 618 | /* |
ansond | 0:137634ff4186 | 619 | * We expect at least three bytes (see below) |
ansond | 0:137634ff4186 | 620 | */ |
ansond | 0:137634ff4186 | 621 | if( len < 3 ) |
ansond | 0:137634ff4186 | 622 | return( POLARSSL_ERR_ECP_BAD_INPUT_DATA ); |
ansond | 0:137634ff4186 | 623 | |
ansond | 0:137634ff4186 | 624 | /* |
ansond | 0:137634ff4186 | 625 | * First byte is curve_type; only named_curve is handled |
ansond | 0:137634ff4186 | 626 | */ |
ansond | 0:137634ff4186 | 627 | if( *(*buf)++ != POLARSSL_ECP_TLS_NAMED_CURVE ) |
ansond | 0:137634ff4186 | 628 | return( POLARSSL_ERR_ECP_BAD_INPUT_DATA ); |
ansond | 0:137634ff4186 | 629 | |
ansond | 0:137634ff4186 | 630 | /* |
ansond | 0:137634ff4186 | 631 | * Next two bytes are the namedcurve value |
ansond | 0:137634ff4186 | 632 | */ |
ansond | 0:137634ff4186 | 633 | tls_id = *(*buf)++; |
ansond | 0:137634ff4186 | 634 | tls_id <<= 8; |
ansond | 0:137634ff4186 | 635 | tls_id |= *(*buf)++; |
ansond | 0:137634ff4186 | 636 | |
ansond | 0:137634ff4186 | 637 | if( ( curve_info = ecp_curve_info_from_tls_id( tls_id ) ) == NULL ) |
ansond | 0:137634ff4186 | 638 | return( POLARSSL_ERR_ECP_FEATURE_UNAVAILABLE ); |
ansond | 0:137634ff4186 | 639 | |
ansond | 0:137634ff4186 | 640 | return ecp_use_known_dp( grp, curve_info->grp_id ); |
ansond | 0:137634ff4186 | 641 | } |
ansond | 0:137634ff4186 | 642 | |
ansond | 0:137634ff4186 | 643 | /* |
ansond | 0:137634ff4186 | 644 | * Write the ECParameters record corresponding to a group (RFC 4492) |
ansond | 0:137634ff4186 | 645 | */ |
ansond | 0:137634ff4186 | 646 | int ecp_tls_write_group( const ecp_group *grp, size_t *olen, |
ansond | 0:137634ff4186 | 647 | unsigned char *buf, size_t blen ) |
ansond | 0:137634ff4186 | 648 | { |
ansond | 0:137634ff4186 | 649 | const ecp_curve_info *curve_info; |
ansond | 0:137634ff4186 | 650 | |
ansond | 0:137634ff4186 | 651 | if( ( curve_info = ecp_curve_info_from_grp_id( grp->id ) ) == NULL ) |
ansond | 0:137634ff4186 | 652 | return( POLARSSL_ERR_ECP_BAD_INPUT_DATA ); |
ansond | 0:137634ff4186 | 653 | |
ansond | 0:137634ff4186 | 654 | /* |
ansond | 0:137634ff4186 | 655 | * We are going to write 3 bytes (see below) |
ansond | 0:137634ff4186 | 656 | */ |
ansond | 0:137634ff4186 | 657 | *olen = 3; |
ansond | 0:137634ff4186 | 658 | if( blen < *olen ) |
ansond | 0:137634ff4186 | 659 | return( POLARSSL_ERR_ECP_BUFFER_TOO_SMALL ); |
ansond | 0:137634ff4186 | 660 | |
ansond | 0:137634ff4186 | 661 | /* |
ansond | 0:137634ff4186 | 662 | * First byte is curve_type, always named_curve |
ansond | 0:137634ff4186 | 663 | */ |
ansond | 0:137634ff4186 | 664 | *buf++ = POLARSSL_ECP_TLS_NAMED_CURVE; |
ansond | 0:137634ff4186 | 665 | |
ansond | 0:137634ff4186 | 666 | /* |
ansond | 0:137634ff4186 | 667 | * Next two bytes are the namedcurve value |
ansond | 0:137634ff4186 | 668 | */ |
ansond | 0:137634ff4186 | 669 | buf[0] = curve_info->tls_id >> 8; |
ansond | 0:137634ff4186 | 670 | buf[1] = curve_info->tls_id & 0xFF; |
ansond | 0:137634ff4186 | 671 | |
ansond | 0:137634ff4186 | 672 | return( 0 ); |
ansond | 0:137634ff4186 | 673 | } |
ansond | 0:137634ff4186 | 674 | |
ansond | 0:137634ff4186 | 675 | /* |
ansond | 0:137634ff4186 | 676 | * Wrapper around fast quasi-modp functions, with fall-back to mpi_mod_mpi. |
ansond | 0:137634ff4186 | 677 | * See the documentation of struct ecp_group. |
ansond | 0:137634ff4186 | 678 | * |
ansond | 0:137634ff4186 | 679 | * This function is in the critial loop for ecp_mul, so pay attention to perf. |
ansond | 0:137634ff4186 | 680 | */ |
ansond | 0:137634ff4186 | 681 | static int ecp_modp( mpi *N, const ecp_group *grp ) |
ansond | 0:137634ff4186 | 682 | { |
ansond | 0:137634ff4186 | 683 | int ret; |
ansond | 0:137634ff4186 | 684 | |
ansond | 0:137634ff4186 | 685 | if( grp->modp == NULL ) |
ansond | 0:137634ff4186 | 686 | return( mpi_mod_mpi( N, N, &grp->P ) ); |
ansond | 0:137634ff4186 | 687 | |
ansond | 0:137634ff4186 | 688 | /* N->s < 0 is a much faster test, which fails only if N is 0 */ |
ansond | 0:137634ff4186 | 689 | if( ( N->s < 0 && mpi_cmp_int( N, 0 ) != 0 ) || |
ansond | 0:137634ff4186 | 690 | mpi_msb( N ) > 2 * grp->pbits ) |
ansond | 0:137634ff4186 | 691 | { |
ansond | 0:137634ff4186 | 692 | return( POLARSSL_ERR_ECP_BAD_INPUT_DATA ); |
ansond | 0:137634ff4186 | 693 | } |
ansond | 0:137634ff4186 | 694 | |
ansond | 0:137634ff4186 | 695 | MPI_CHK( grp->modp( N ) ); |
ansond | 0:137634ff4186 | 696 | |
ansond | 0:137634ff4186 | 697 | /* N->s < 0 is a much faster test, which fails only if N is 0 */ |
ansond | 0:137634ff4186 | 698 | while( N->s < 0 && mpi_cmp_int( N, 0 ) != 0 ) |
ansond | 0:137634ff4186 | 699 | MPI_CHK( mpi_add_mpi( N, N, &grp->P ) ); |
ansond | 0:137634ff4186 | 700 | |
ansond | 0:137634ff4186 | 701 | while( mpi_cmp_mpi( N, &grp->P ) >= 0 ) |
ansond | 0:137634ff4186 | 702 | /* we known P, N and the result are positive */ |
ansond | 0:137634ff4186 | 703 | MPI_CHK( mpi_sub_abs( N, N, &grp->P ) ); |
ansond | 0:137634ff4186 | 704 | |
ansond | 0:137634ff4186 | 705 | cleanup: |
ansond | 0:137634ff4186 | 706 | return( ret ); |
ansond | 0:137634ff4186 | 707 | } |
ansond | 0:137634ff4186 | 708 | |
ansond | 0:137634ff4186 | 709 | /* |
ansond | 0:137634ff4186 | 710 | * Fast mod-p functions expect their argument to be in the 0..p^2 range. |
ansond | 0:137634ff4186 | 711 | * |
ansond | 0:137634ff4186 | 712 | * In order to guarantee that, we need to ensure that operands of |
ansond | 0:137634ff4186 | 713 | * mpi_mul_mpi are in the 0..p range. So, after each operation we will |
ansond | 0:137634ff4186 | 714 | * bring the result back to this range. |
ansond | 0:137634ff4186 | 715 | * |
ansond | 0:137634ff4186 | 716 | * The following macros are shortcuts for doing that. |
ansond | 0:137634ff4186 | 717 | */ |
ansond | 0:137634ff4186 | 718 | |
ansond | 0:137634ff4186 | 719 | /* |
ansond | 0:137634ff4186 | 720 | * Reduce a mpi mod p in-place, general case, to use after mpi_mul_mpi |
ansond | 0:137634ff4186 | 721 | */ |
ansond | 0:137634ff4186 | 722 | #if defined(POLARSSL_SELF_TEST) |
ansond | 0:137634ff4186 | 723 | #define INC_MUL_COUNT mul_count++; |
ansond | 0:137634ff4186 | 724 | #else |
ansond | 0:137634ff4186 | 725 | #define INC_MUL_COUNT |
ansond | 0:137634ff4186 | 726 | #endif |
ansond | 0:137634ff4186 | 727 | |
ansond | 0:137634ff4186 | 728 | #define MOD_MUL( N ) do { MPI_CHK( ecp_modp( &N, grp ) ); INC_MUL_COUNT } \ |
ansond | 0:137634ff4186 | 729 | while( 0 ) |
ansond | 0:137634ff4186 | 730 | |
ansond | 0:137634ff4186 | 731 | /* |
ansond | 0:137634ff4186 | 732 | * Reduce a mpi mod p in-place, to use after mpi_sub_mpi |
ansond | 0:137634ff4186 | 733 | * N->s < 0 is a very fast test, which fails only if N is 0 |
ansond | 0:137634ff4186 | 734 | */ |
ansond | 0:137634ff4186 | 735 | #define MOD_SUB( N ) \ |
ansond | 0:137634ff4186 | 736 | while( N.s < 0 && mpi_cmp_int( &N, 0 ) != 0 ) \ |
ansond | 0:137634ff4186 | 737 | MPI_CHK( mpi_add_mpi( &N, &N, &grp->P ) ) |
ansond | 0:137634ff4186 | 738 | |
ansond | 0:137634ff4186 | 739 | /* |
ansond | 0:137634ff4186 | 740 | * Reduce a mpi mod p in-place, to use after mpi_add_mpi and mpi_mul_int. |
ansond | 0:137634ff4186 | 741 | * We known P, N and the result are positive, so sub_abs is correct, and |
ansond | 0:137634ff4186 | 742 | * a bit faster. |
ansond | 0:137634ff4186 | 743 | */ |
ansond | 0:137634ff4186 | 744 | #define MOD_ADD( N ) \ |
ansond | 0:137634ff4186 | 745 | while( mpi_cmp_mpi( &N, &grp->P ) >= 0 ) \ |
ansond | 0:137634ff4186 | 746 | MPI_CHK( mpi_sub_abs( &N, &N, &grp->P ) ) |
ansond | 0:137634ff4186 | 747 | |
ansond | 0:137634ff4186 | 748 | #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS) |
ansond | 0:137634ff4186 | 749 | /* |
ansond | 0:137634ff4186 | 750 | * For curves in short Weierstrass form, we do all the internal operations in |
ansond | 0:137634ff4186 | 751 | * Jacobian coordinates. |
ansond | 0:137634ff4186 | 752 | * |
ansond | 0:137634ff4186 | 753 | * For multiplication, we'll use a comb method with coutermeasueres against |
ansond | 0:137634ff4186 | 754 | * SPA, hence timing attacks. |
ansond | 0:137634ff4186 | 755 | */ |
ansond | 0:137634ff4186 | 756 | |
ansond | 0:137634ff4186 | 757 | /* |
ansond | 0:137634ff4186 | 758 | * Normalize jacobian coordinates so that Z == 0 || Z == 1 (GECC 3.2.1) |
ansond | 0:137634ff4186 | 759 | * Cost: 1N := 1I + 3M + 1S |
ansond | 0:137634ff4186 | 760 | */ |
ansond | 0:137634ff4186 | 761 | static int ecp_normalize_jac( const ecp_group *grp, ecp_point *pt ) |
ansond | 0:137634ff4186 | 762 | { |
ansond | 0:137634ff4186 | 763 | int ret; |
ansond | 0:137634ff4186 | 764 | mpi Zi, ZZi; |
ansond | 0:137634ff4186 | 765 | |
ansond | 0:137634ff4186 | 766 | if( mpi_cmp_int( &pt->Z, 0 ) == 0 ) |
ansond | 0:137634ff4186 | 767 | return( 0 ); |
ansond | 0:137634ff4186 | 768 | |
ansond | 0:137634ff4186 | 769 | mpi_init( &Zi ); mpi_init( &ZZi ); |
ansond | 0:137634ff4186 | 770 | |
ansond | 0:137634ff4186 | 771 | /* |
ansond | 0:137634ff4186 | 772 | * X = X / Z^2 mod p |
ansond | 0:137634ff4186 | 773 | */ |
ansond | 0:137634ff4186 | 774 | MPI_CHK( mpi_inv_mod( &Zi, &pt->Z, &grp->P ) ); |
ansond | 0:137634ff4186 | 775 | MPI_CHK( mpi_mul_mpi( &ZZi, &Zi, &Zi ) ); MOD_MUL( ZZi ); |
ansond | 0:137634ff4186 | 776 | MPI_CHK( mpi_mul_mpi( &pt->X, &pt->X, &ZZi ) ); MOD_MUL( pt->X ); |
ansond | 0:137634ff4186 | 777 | |
ansond | 0:137634ff4186 | 778 | /* |
ansond | 0:137634ff4186 | 779 | * Y = Y / Z^3 mod p |
ansond | 0:137634ff4186 | 780 | */ |
ansond | 0:137634ff4186 | 781 | MPI_CHK( mpi_mul_mpi( &pt->Y, &pt->Y, &ZZi ) ); MOD_MUL( pt->Y ); |
ansond | 0:137634ff4186 | 782 | MPI_CHK( mpi_mul_mpi( &pt->Y, &pt->Y, &Zi ) ); MOD_MUL( pt->Y ); |
ansond | 0:137634ff4186 | 783 | |
ansond | 0:137634ff4186 | 784 | /* |
ansond | 0:137634ff4186 | 785 | * Z = 1 |
ansond | 0:137634ff4186 | 786 | */ |
ansond | 0:137634ff4186 | 787 | MPI_CHK( mpi_lset( &pt->Z, 1 ) ); |
ansond | 0:137634ff4186 | 788 | |
ansond | 0:137634ff4186 | 789 | cleanup: |
ansond | 0:137634ff4186 | 790 | |
ansond | 0:137634ff4186 | 791 | mpi_free( &Zi ); mpi_free( &ZZi ); |
ansond | 0:137634ff4186 | 792 | |
ansond | 0:137634ff4186 | 793 | return( ret ); |
ansond | 0:137634ff4186 | 794 | } |
ansond | 0:137634ff4186 | 795 | |
ansond | 0:137634ff4186 | 796 | /* |
ansond | 0:137634ff4186 | 797 | * Normalize jacobian coordinates of an array of (pointers to) points, |
ansond | 0:137634ff4186 | 798 | * using Montgomery's trick to perform only one inversion mod P. |
ansond | 0:137634ff4186 | 799 | * (See for example Cohen's "A Course in Computational Algebraic Number |
ansond | 0:137634ff4186 | 800 | * Theory", Algorithm 10.3.4.) |
ansond | 0:137634ff4186 | 801 | * |
ansond | 0:137634ff4186 | 802 | * Warning: fails (returning an error) if one of the points is zero! |
ansond | 0:137634ff4186 | 803 | * This should never happen, see choice of w in ecp_mul_comb(). |
ansond | 0:137634ff4186 | 804 | * |
ansond | 0:137634ff4186 | 805 | * Cost: 1N(t) := 1I + (6t - 3)M + 1S |
ansond | 0:137634ff4186 | 806 | */ |
ansond | 0:137634ff4186 | 807 | static int ecp_normalize_jac_many( const ecp_group *grp, |
ansond | 0:137634ff4186 | 808 | ecp_point *T[], size_t t_len ) |
ansond | 0:137634ff4186 | 809 | { |
ansond | 0:137634ff4186 | 810 | int ret; |
ansond | 0:137634ff4186 | 811 | size_t i; |
ansond | 0:137634ff4186 | 812 | mpi *c, u, Zi, ZZi; |
ansond | 0:137634ff4186 | 813 | |
ansond | 0:137634ff4186 | 814 | if( t_len < 2 ) |
ansond | 0:137634ff4186 | 815 | return( ecp_normalize_jac( grp, *T ) ); |
ansond | 0:137634ff4186 | 816 | |
ansond | 0:137634ff4186 | 817 | if( ( c = polarssl_malloc( t_len * sizeof( mpi ) ) ) == NULL ) |
ansond | 0:137634ff4186 | 818 | return( POLARSSL_ERR_ECP_MALLOC_FAILED ); |
ansond | 0:137634ff4186 | 819 | |
ansond | 0:137634ff4186 | 820 | mpi_init( &u ); mpi_init( &Zi ); mpi_init( &ZZi ); |
ansond | 0:137634ff4186 | 821 | for( i = 0; i < t_len; i++ ) |
ansond | 0:137634ff4186 | 822 | mpi_init( &c[i] ); |
ansond | 0:137634ff4186 | 823 | |
ansond | 0:137634ff4186 | 824 | /* |
ansond | 0:137634ff4186 | 825 | * c[i] = Z_0 * ... * Z_i |
ansond | 0:137634ff4186 | 826 | */ |
ansond | 0:137634ff4186 | 827 | MPI_CHK( mpi_copy( &c[0], &T[0]->Z ) ); |
ansond | 0:137634ff4186 | 828 | for( i = 1; i < t_len; i++ ) |
ansond | 0:137634ff4186 | 829 | { |
ansond | 0:137634ff4186 | 830 | MPI_CHK( mpi_mul_mpi( &c[i], &c[i-1], &T[i]->Z ) ); |
ansond | 0:137634ff4186 | 831 | MOD_MUL( c[i] ); |
ansond | 0:137634ff4186 | 832 | } |
ansond | 0:137634ff4186 | 833 | |
ansond | 0:137634ff4186 | 834 | /* |
ansond | 0:137634ff4186 | 835 | * u = 1 / (Z_0 * ... * Z_n) mod P |
ansond | 0:137634ff4186 | 836 | */ |
ansond | 0:137634ff4186 | 837 | MPI_CHK( mpi_inv_mod( &u, &c[t_len-1], &grp->P ) ); |
ansond | 0:137634ff4186 | 838 | |
ansond | 0:137634ff4186 | 839 | for( i = t_len - 1; ; i-- ) |
ansond | 0:137634ff4186 | 840 | { |
ansond | 0:137634ff4186 | 841 | /* |
ansond | 0:137634ff4186 | 842 | * Zi = 1 / Z_i mod p |
ansond | 0:137634ff4186 | 843 | * u = 1 / (Z_0 * ... * Z_i) mod P |
ansond | 0:137634ff4186 | 844 | */ |
ansond | 0:137634ff4186 | 845 | if( i == 0 ) { |
ansond | 0:137634ff4186 | 846 | MPI_CHK( mpi_copy( &Zi, &u ) ); |
ansond | 0:137634ff4186 | 847 | } |
ansond | 0:137634ff4186 | 848 | else |
ansond | 0:137634ff4186 | 849 | { |
ansond | 0:137634ff4186 | 850 | MPI_CHK( mpi_mul_mpi( &Zi, &u, &c[i-1] ) ); MOD_MUL( Zi ); |
ansond | 0:137634ff4186 | 851 | MPI_CHK( mpi_mul_mpi( &u, &u, &T[i]->Z ) ); MOD_MUL( u ); |
ansond | 0:137634ff4186 | 852 | } |
ansond | 0:137634ff4186 | 853 | |
ansond | 0:137634ff4186 | 854 | /* |
ansond | 0:137634ff4186 | 855 | * proceed as in normalize() |
ansond | 0:137634ff4186 | 856 | */ |
ansond | 0:137634ff4186 | 857 | MPI_CHK( mpi_mul_mpi( &ZZi, &Zi, &Zi ) ); MOD_MUL( ZZi ); |
ansond | 0:137634ff4186 | 858 | MPI_CHK( mpi_mul_mpi( &T[i]->X, &T[i]->X, &ZZi ) ); MOD_MUL( T[i]->X ); |
ansond | 0:137634ff4186 | 859 | MPI_CHK( mpi_mul_mpi( &T[i]->Y, &T[i]->Y, &ZZi ) ); MOD_MUL( T[i]->Y ); |
ansond | 0:137634ff4186 | 860 | MPI_CHK( mpi_mul_mpi( &T[i]->Y, &T[i]->Y, &Zi ) ); MOD_MUL( T[i]->Y ); |
ansond | 0:137634ff4186 | 861 | |
ansond | 0:137634ff4186 | 862 | /* |
ansond | 0:137634ff4186 | 863 | * Post-precessing: reclaim some memory by shrinking coordinates |
ansond | 0:137634ff4186 | 864 | * - not storing Z (always 1) |
ansond | 0:137634ff4186 | 865 | * - shrinking other coordinates, but still keeping the same number of |
ansond | 0:137634ff4186 | 866 | * limbs as P, as otherwise it will too likely be regrown too fast. |
ansond | 0:137634ff4186 | 867 | */ |
ansond | 0:137634ff4186 | 868 | MPI_CHK( mpi_shrink( &T[i]->X, grp->P.n ) ); |
ansond | 0:137634ff4186 | 869 | MPI_CHK( mpi_shrink( &T[i]->Y, grp->P.n ) ); |
ansond | 0:137634ff4186 | 870 | mpi_free( &T[i]->Z ); |
ansond | 0:137634ff4186 | 871 | |
ansond | 0:137634ff4186 | 872 | if( i == 0 ) |
ansond | 0:137634ff4186 | 873 | break; |
ansond | 0:137634ff4186 | 874 | } |
ansond | 0:137634ff4186 | 875 | |
ansond | 0:137634ff4186 | 876 | cleanup: |
ansond | 0:137634ff4186 | 877 | |
ansond | 0:137634ff4186 | 878 | mpi_free( &u ); mpi_free( &Zi ); mpi_free( &ZZi ); |
ansond | 0:137634ff4186 | 879 | for( i = 0; i < t_len; i++ ) |
ansond | 0:137634ff4186 | 880 | mpi_free( &c[i] ); |
ansond | 0:137634ff4186 | 881 | polarssl_free( c ); |
ansond | 0:137634ff4186 | 882 | |
ansond | 0:137634ff4186 | 883 | return( ret ); |
ansond | 0:137634ff4186 | 884 | } |
ansond | 0:137634ff4186 | 885 | |
ansond | 0:137634ff4186 | 886 | /* |
ansond | 0:137634ff4186 | 887 | * Conditional point inversion: Q -> -Q = (Q.X, -Q.Y, Q.Z) without leak. |
ansond | 0:137634ff4186 | 888 | * "inv" must be 0 (don't invert) or 1 (invert) or the result will be invalid |
ansond | 0:137634ff4186 | 889 | */ |
ansond | 0:137634ff4186 | 890 | static int ecp_safe_invert_jac( const ecp_group *grp, |
ansond | 0:137634ff4186 | 891 | ecp_point *Q, |
ansond | 0:137634ff4186 | 892 | unsigned char inv ) |
ansond | 0:137634ff4186 | 893 | { |
ansond | 0:137634ff4186 | 894 | int ret; |
ansond | 0:137634ff4186 | 895 | unsigned char nonzero; |
ansond | 0:137634ff4186 | 896 | mpi mQY; |
ansond | 0:137634ff4186 | 897 | |
ansond | 0:137634ff4186 | 898 | mpi_init( &mQY ); |
ansond | 0:137634ff4186 | 899 | |
ansond | 0:137634ff4186 | 900 | /* Use the fact that -Q.Y mod P = P - Q.Y unless Q.Y == 0 */ |
ansond | 0:137634ff4186 | 901 | MPI_CHK( mpi_sub_mpi( &mQY, &grp->P, &Q->Y ) ); |
ansond | 0:137634ff4186 | 902 | nonzero = mpi_cmp_int( &Q->Y, 0 ) != 0; |
ansond | 0:137634ff4186 | 903 | MPI_CHK( mpi_safe_cond_assign( &Q->Y, &mQY, inv & nonzero ) ); |
ansond | 0:137634ff4186 | 904 | |
ansond | 0:137634ff4186 | 905 | cleanup: |
ansond | 0:137634ff4186 | 906 | mpi_free( &mQY ); |
ansond | 0:137634ff4186 | 907 | |
ansond | 0:137634ff4186 | 908 | return( ret ); |
ansond | 0:137634ff4186 | 909 | } |
ansond | 0:137634ff4186 | 910 | |
ansond | 0:137634ff4186 | 911 | /* |
ansond | 0:137634ff4186 | 912 | * Point doubling R = 2 P, Jacobian coordinates |
ansond | 0:137634ff4186 | 913 | * |
ansond | 0:137634ff4186 | 914 | * Based on http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-1998-cmo-2 . |
ansond | 0:137634ff4186 | 915 | * |
ansond | 0:137634ff4186 | 916 | * We follow the variable naming fairly closely. The formula variations that trade a MUL for a SQR |
ansond | 0:137634ff4186 | 917 | * (plus a few ADDs) aren't useful as our bignum implementation doesn't distinguish squaring. |
ansond | 0:137634ff4186 | 918 | * |
ansond | 0:137634ff4186 | 919 | * Standard optimizations are applied when curve parameter A is one of { 0, -3 }. |
ansond | 0:137634ff4186 | 920 | * |
ansond | 0:137634ff4186 | 921 | * Cost: 1D := 3M + 4S (A == 0) |
ansond | 0:137634ff4186 | 922 | * 4M + 4S (A == -3) |
ansond | 0:137634ff4186 | 923 | * 3M + 6S + 1a otherwise |
ansond | 0:137634ff4186 | 924 | */ |
ansond | 0:137634ff4186 | 925 | static int ecp_double_jac( const ecp_group *grp, ecp_point *R, |
ansond | 0:137634ff4186 | 926 | const ecp_point *P ) |
ansond | 0:137634ff4186 | 927 | { |
ansond | 0:137634ff4186 | 928 | int ret; |
ansond | 0:137634ff4186 | 929 | mpi M, S, T, U; |
ansond | 0:137634ff4186 | 930 | |
ansond | 0:137634ff4186 | 931 | #if defined(POLARSSL_SELF_TEST) |
ansond | 0:137634ff4186 | 932 | dbl_count++; |
ansond | 0:137634ff4186 | 933 | #endif |
ansond | 0:137634ff4186 | 934 | |
ansond | 0:137634ff4186 | 935 | mpi_init( &M ); mpi_init( &S ); mpi_init( &T ); mpi_init( &U ); |
ansond | 0:137634ff4186 | 936 | |
ansond | 0:137634ff4186 | 937 | /* Special case for A = -3 */ |
ansond | 0:137634ff4186 | 938 | if( grp->A.p == NULL ) |
ansond | 0:137634ff4186 | 939 | { |
ansond | 0:137634ff4186 | 940 | /* M = 3(X + Z^2)(X - Z^2) */ |
ansond | 0:137634ff4186 | 941 | MPI_CHK( mpi_mul_mpi( &S, &P->Z, &P->Z ) ); MOD_MUL( S ); |
ansond | 0:137634ff4186 | 942 | MPI_CHK( mpi_add_mpi( &T, &P->X, &S ) ); MOD_ADD( T ); |
ansond | 0:137634ff4186 | 943 | MPI_CHK( mpi_sub_mpi( &U, &P->X, &S ) ); MOD_SUB( U ); |
ansond | 0:137634ff4186 | 944 | MPI_CHK( mpi_mul_mpi( &S, &T, &U ) ); MOD_MUL( S ); |
ansond | 0:137634ff4186 | 945 | MPI_CHK( mpi_mul_int( &M, &S, 3 ) ); MOD_ADD( M ); |
ansond | 0:137634ff4186 | 946 | } |
ansond | 0:137634ff4186 | 947 | else |
ansond | 0:137634ff4186 | 948 | { |
ansond | 0:137634ff4186 | 949 | /* M = 3.X^2 */ |
ansond | 0:137634ff4186 | 950 | MPI_CHK( mpi_mul_mpi( &S, &P->X, &P->X ) ); MOD_MUL( S ); |
ansond | 0:137634ff4186 | 951 | MPI_CHK( mpi_mul_int( &M, &S, 3 ) ); MOD_ADD( M ); |
ansond | 0:137634ff4186 | 952 | |
ansond | 0:137634ff4186 | 953 | /* Optimize away for "koblitz" curves with A = 0 */ |
ansond | 0:137634ff4186 | 954 | if( mpi_cmp_int( &grp->A, 0 ) != 0 ) |
ansond | 0:137634ff4186 | 955 | { |
ansond | 0:137634ff4186 | 956 | /* M += A.Z^4 */ |
ansond | 0:137634ff4186 | 957 | MPI_CHK( mpi_mul_mpi( &S, &P->Z, &P->Z ) ); MOD_MUL( S ); |
ansond | 0:137634ff4186 | 958 | MPI_CHK( mpi_mul_mpi( &T, &S, &S ) ); MOD_MUL( T ); |
ansond | 0:137634ff4186 | 959 | MPI_CHK( mpi_mul_mpi( &S, &T, &grp->A ) ); MOD_MUL( S ); |
ansond | 0:137634ff4186 | 960 | MPI_CHK( mpi_add_mpi( &M, &M, &S ) ); MOD_ADD( M ); |
ansond | 0:137634ff4186 | 961 | } |
ansond | 0:137634ff4186 | 962 | } |
ansond | 0:137634ff4186 | 963 | |
ansond | 0:137634ff4186 | 964 | /* S = 4.X.Y^2 */ |
ansond | 0:137634ff4186 | 965 | MPI_CHK( mpi_mul_mpi( &T, &P->Y, &P->Y ) ); MOD_MUL( T ); |
ansond | 0:137634ff4186 | 966 | MPI_CHK( mpi_shift_l( &T, 1 ) ); MOD_ADD( T ); |
ansond | 0:137634ff4186 | 967 | MPI_CHK( mpi_mul_mpi( &S, &P->X, &T ) ); MOD_MUL( S ); |
ansond | 0:137634ff4186 | 968 | MPI_CHK( mpi_shift_l( &S, 1 ) ); MOD_ADD( S ); |
ansond | 0:137634ff4186 | 969 | |
ansond | 0:137634ff4186 | 970 | /* U = 8.Y^4 */ |
ansond | 0:137634ff4186 | 971 | MPI_CHK( mpi_mul_mpi( &U, &T, &T ) ); MOD_MUL( U ); |
ansond | 0:137634ff4186 | 972 | MPI_CHK( mpi_shift_l( &U, 1 ) ); MOD_ADD( U ); |
ansond | 0:137634ff4186 | 973 | |
ansond | 0:137634ff4186 | 974 | /* T = M^2 - 2.S */ |
ansond | 0:137634ff4186 | 975 | MPI_CHK( mpi_mul_mpi( &T, &M, &M ) ); MOD_MUL( T ); |
ansond | 0:137634ff4186 | 976 | MPI_CHK( mpi_sub_mpi( &T, &T, &S ) ); MOD_SUB( T ); |
ansond | 0:137634ff4186 | 977 | MPI_CHK( mpi_sub_mpi( &T, &T, &S ) ); MOD_SUB( T ); |
ansond | 0:137634ff4186 | 978 | |
ansond | 0:137634ff4186 | 979 | /* S = M(S - T) - U */ |
ansond | 0:137634ff4186 | 980 | MPI_CHK( mpi_sub_mpi( &S, &S, &T ) ); MOD_SUB( S ); |
ansond | 0:137634ff4186 | 981 | MPI_CHK( mpi_mul_mpi( &S, &S, &M ) ); MOD_MUL( S ); |
ansond | 0:137634ff4186 | 982 | MPI_CHK( mpi_sub_mpi( &S, &S, &U ) ); MOD_SUB( S ); |
ansond | 0:137634ff4186 | 983 | |
ansond | 0:137634ff4186 | 984 | /* U = 2.Y.Z */ |
ansond | 0:137634ff4186 | 985 | MPI_CHK( mpi_mul_mpi( &U, &P->Y, &P->Z ) ); MOD_MUL( U ); |
ansond | 0:137634ff4186 | 986 | MPI_CHK( mpi_shift_l( &U, 1 ) ); MOD_ADD( U ); |
ansond | 0:137634ff4186 | 987 | |
ansond | 0:137634ff4186 | 988 | MPI_CHK( mpi_copy( &R->X, &T ) ); |
ansond | 0:137634ff4186 | 989 | MPI_CHK( mpi_copy( &R->Y, &S ) ); |
ansond | 0:137634ff4186 | 990 | MPI_CHK( mpi_copy( &R->Z, &U ) ); |
ansond | 0:137634ff4186 | 991 | |
ansond | 0:137634ff4186 | 992 | cleanup: |
ansond | 0:137634ff4186 | 993 | mpi_free( &M ); mpi_free( &S ); mpi_free( &T ); mpi_free( &U ); |
ansond | 0:137634ff4186 | 994 | |
ansond | 0:137634ff4186 | 995 | return( ret ); |
ansond | 0:137634ff4186 | 996 | } |
ansond | 0:137634ff4186 | 997 | |
ansond | 0:137634ff4186 | 998 | /* |
ansond | 0:137634ff4186 | 999 | * Addition: R = P + Q, mixed affine-Jacobian coordinates (GECC 3.22) |
ansond | 0:137634ff4186 | 1000 | * |
ansond | 0:137634ff4186 | 1001 | * The coordinates of Q must be normalized (= affine), |
ansond | 0:137634ff4186 | 1002 | * but those of P don't need to. R is not normalized. |
ansond | 0:137634ff4186 | 1003 | * |
ansond | 0:137634ff4186 | 1004 | * Special cases: (1) P or Q is zero, (2) R is zero, (3) P == Q. |
ansond | 0:137634ff4186 | 1005 | * None of these cases can happen as intermediate step in ecp_mul_comb(): |
ansond | 0:137634ff4186 | 1006 | * - at each step, P, Q and R are multiples of the base point, the factor |
ansond | 0:137634ff4186 | 1007 | * being less than its order, so none of them is zero; |
ansond | 0:137634ff4186 | 1008 | * - Q is an odd multiple of the base point, P an even multiple, |
ansond | 0:137634ff4186 | 1009 | * due to the choice of precomputed points in the modified comb method. |
ansond | 0:137634ff4186 | 1010 | * So branches for these cases do not leak secret information. |
ansond | 0:137634ff4186 | 1011 | * |
ansond | 0:137634ff4186 | 1012 | * We accept Q->Z being unset (saving memory in tables) as meaning 1. |
ansond | 0:137634ff4186 | 1013 | * |
ansond | 0:137634ff4186 | 1014 | * Cost: 1A := 8M + 3S |
ansond | 0:137634ff4186 | 1015 | */ |
ansond | 0:137634ff4186 | 1016 | static int ecp_add_mixed( const ecp_group *grp, ecp_point *R, |
ansond | 0:137634ff4186 | 1017 | const ecp_point *P, const ecp_point *Q ) |
ansond | 0:137634ff4186 | 1018 | { |
ansond | 0:137634ff4186 | 1019 | int ret; |
ansond | 0:137634ff4186 | 1020 | mpi T1, T2, T3, T4, X, Y, Z; |
ansond | 0:137634ff4186 | 1021 | |
ansond | 0:137634ff4186 | 1022 | #if defined(POLARSSL_SELF_TEST) |
ansond | 0:137634ff4186 | 1023 | add_count++; |
ansond | 0:137634ff4186 | 1024 | #endif |
ansond | 0:137634ff4186 | 1025 | |
ansond | 0:137634ff4186 | 1026 | /* |
ansond | 0:137634ff4186 | 1027 | * Trivial cases: P == 0 or Q == 0 (case 1) |
ansond | 0:137634ff4186 | 1028 | */ |
ansond | 0:137634ff4186 | 1029 | if( mpi_cmp_int( &P->Z, 0 ) == 0 ) |
ansond | 0:137634ff4186 | 1030 | return( ecp_copy( R, Q ) ); |
ansond | 0:137634ff4186 | 1031 | |
ansond | 0:137634ff4186 | 1032 | if( Q->Z.p != NULL && mpi_cmp_int( &Q->Z, 0 ) == 0 ) |
ansond | 0:137634ff4186 | 1033 | return( ecp_copy( R, P ) ); |
ansond | 0:137634ff4186 | 1034 | |
ansond | 0:137634ff4186 | 1035 | /* |
ansond | 0:137634ff4186 | 1036 | * Make sure Q coordinates are normalized |
ansond | 0:137634ff4186 | 1037 | */ |
ansond | 0:137634ff4186 | 1038 | if( Q->Z.p != NULL && mpi_cmp_int( &Q->Z, 1 ) != 0 ) |
ansond | 0:137634ff4186 | 1039 | return( POLARSSL_ERR_ECP_BAD_INPUT_DATA ); |
ansond | 0:137634ff4186 | 1040 | |
ansond | 0:137634ff4186 | 1041 | mpi_init( &T1 ); mpi_init( &T2 ); mpi_init( &T3 ); mpi_init( &T4 ); |
ansond | 0:137634ff4186 | 1042 | mpi_init( &X ); mpi_init( &Y ); mpi_init( &Z ); |
ansond | 0:137634ff4186 | 1043 | |
ansond | 0:137634ff4186 | 1044 | MPI_CHK( mpi_mul_mpi( &T1, &P->Z, &P->Z ) ); MOD_MUL( T1 ); |
ansond | 0:137634ff4186 | 1045 | MPI_CHK( mpi_mul_mpi( &T2, &T1, &P->Z ) ); MOD_MUL( T2 ); |
ansond | 0:137634ff4186 | 1046 | MPI_CHK( mpi_mul_mpi( &T1, &T1, &Q->X ) ); MOD_MUL( T1 ); |
ansond | 0:137634ff4186 | 1047 | MPI_CHK( mpi_mul_mpi( &T2, &T2, &Q->Y ) ); MOD_MUL( T2 ); |
ansond | 0:137634ff4186 | 1048 | MPI_CHK( mpi_sub_mpi( &T1, &T1, &P->X ) ); MOD_SUB( T1 ); |
ansond | 0:137634ff4186 | 1049 | MPI_CHK( mpi_sub_mpi( &T2, &T2, &P->Y ) ); MOD_SUB( T2 ); |
ansond | 0:137634ff4186 | 1050 | |
ansond | 0:137634ff4186 | 1051 | /* Special cases (2) and (3) */ |
ansond | 0:137634ff4186 | 1052 | if( mpi_cmp_int( &T1, 0 ) == 0 ) |
ansond | 0:137634ff4186 | 1053 | { |
ansond | 0:137634ff4186 | 1054 | if( mpi_cmp_int( &T2, 0 ) == 0 ) |
ansond | 0:137634ff4186 | 1055 | { |
ansond | 0:137634ff4186 | 1056 | ret = ecp_double_jac( grp, R, P ); |
ansond | 0:137634ff4186 | 1057 | goto cleanup; |
ansond | 0:137634ff4186 | 1058 | } |
ansond | 0:137634ff4186 | 1059 | else |
ansond | 0:137634ff4186 | 1060 | { |
ansond | 0:137634ff4186 | 1061 | ret = ecp_set_zero( R ); |
ansond | 0:137634ff4186 | 1062 | goto cleanup; |
ansond | 0:137634ff4186 | 1063 | } |
ansond | 0:137634ff4186 | 1064 | } |
ansond | 0:137634ff4186 | 1065 | |
ansond | 0:137634ff4186 | 1066 | MPI_CHK( mpi_mul_mpi( &Z, &P->Z, &T1 ) ); MOD_MUL( Z ); |
ansond | 0:137634ff4186 | 1067 | MPI_CHK( mpi_mul_mpi( &T3, &T1, &T1 ) ); MOD_MUL( T3 ); |
ansond | 0:137634ff4186 | 1068 | MPI_CHK( mpi_mul_mpi( &T4, &T3, &T1 ) ); MOD_MUL( T4 ); |
ansond | 0:137634ff4186 | 1069 | MPI_CHK( mpi_mul_mpi( &T3, &T3, &P->X ) ); MOD_MUL( T3 ); |
ansond | 0:137634ff4186 | 1070 | MPI_CHK( mpi_mul_int( &T1, &T3, 2 ) ); MOD_ADD( T1 ); |
ansond | 0:137634ff4186 | 1071 | MPI_CHK( mpi_mul_mpi( &X, &T2, &T2 ) ); MOD_MUL( X ); |
ansond | 0:137634ff4186 | 1072 | MPI_CHK( mpi_sub_mpi( &X, &X, &T1 ) ); MOD_SUB( X ); |
ansond | 0:137634ff4186 | 1073 | MPI_CHK( mpi_sub_mpi( &X, &X, &T4 ) ); MOD_SUB( X ); |
ansond | 0:137634ff4186 | 1074 | MPI_CHK( mpi_sub_mpi( &T3, &T3, &X ) ); MOD_SUB( T3 ); |
ansond | 0:137634ff4186 | 1075 | MPI_CHK( mpi_mul_mpi( &T3, &T3, &T2 ) ); MOD_MUL( T3 ); |
ansond | 0:137634ff4186 | 1076 | MPI_CHK( mpi_mul_mpi( &T4, &T4, &P->Y ) ); MOD_MUL( T4 ); |
ansond | 0:137634ff4186 | 1077 | MPI_CHK( mpi_sub_mpi( &Y, &T3, &T4 ) ); MOD_SUB( Y ); |
ansond | 0:137634ff4186 | 1078 | |
ansond | 0:137634ff4186 | 1079 | MPI_CHK( mpi_copy( &R->X, &X ) ); |
ansond | 0:137634ff4186 | 1080 | MPI_CHK( mpi_copy( &R->Y, &Y ) ); |
ansond | 0:137634ff4186 | 1081 | MPI_CHK( mpi_copy( &R->Z, &Z ) ); |
ansond | 0:137634ff4186 | 1082 | |
ansond | 0:137634ff4186 | 1083 | cleanup: |
ansond | 0:137634ff4186 | 1084 | |
ansond | 0:137634ff4186 | 1085 | mpi_free( &T1 ); mpi_free( &T2 ); mpi_free( &T3 ); mpi_free( &T4 ); |
ansond | 0:137634ff4186 | 1086 | mpi_free( &X ); mpi_free( &Y ); mpi_free( &Z ); |
ansond | 0:137634ff4186 | 1087 | |
ansond | 0:137634ff4186 | 1088 | return( ret ); |
ansond | 0:137634ff4186 | 1089 | } |
ansond | 0:137634ff4186 | 1090 | |
ansond | 0:137634ff4186 | 1091 | /* |
ansond | 0:137634ff4186 | 1092 | * Addition: R = P + Q, result's coordinates normalized |
ansond | 0:137634ff4186 | 1093 | */ |
ansond | 0:137634ff4186 | 1094 | int ecp_add( const ecp_group *grp, ecp_point *R, |
ansond | 0:137634ff4186 | 1095 | const ecp_point *P, const ecp_point *Q ) |
ansond | 0:137634ff4186 | 1096 | { |
ansond | 0:137634ff4186 | 1097 | int ret; |
ansond | 0:137634ff4186 | 1098 | |
ansond | 0:137634ff4186 | 1099 | if( ecp_get_type( grp ) != POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS ) |
ansond | 0:137634ff4186 | 1100 | return( POLARSSL_ERR_ECP_FEATURE_UNAVAILABLE ); |
ansond | 0:137634ff4186 | 1101 | |
ansond | 0:137634ff4186 | 1102 | MPI_CHK( ecp_add_mixed( grp, R, P, Q ) ); |
ansond | 0:137634ff4186 | 1103 | MPI_CHK( ecp_normalize_jac( grp, R ) ); |
ansond | 0:137634ff4186 | 1104 | |
ansond | 0:137634ff4186 | 1105 | cleanup: |
ansond | 0:137634ff4186 | 1106 | return( ret ); |
ansond | 0:137634ff4186 | 1107 | } |
ansond | 0:137634ff4186 | 1108 | |
ansond | 0:137634ff4186 | 1109 | /* |
ansond | 0:137634ff4186 | 1110 | * Subtraction: R = P - Q, result's coordinates normalized |
ansond | 0:137634ff4186 | 1111 | */ |
ansond | 0:137634ff4186 | 1112 | int ecp_sub( const ecp_group *grp, ecp_point *R, |
ansond | 0:137634ff4186 | 1113 | const ecp_point *P, const ecp_point *Q ) |
ansond | 0:137634ff4186 | 1114 | { |
ansond | 0:137634ff4186 | 1115 | int ret; |
ansond | 0:137634ff4186 | 1116 | ecp_point mQ; |
ansond | 0:137634ff4186 | 1117 | |
ansond | 0:137634ff4186 | 1118 | ecp_point_init( &mQ ); |
ansond | 0:137634ff4186 | 1119 | |
ansond | 0:137634ff4186 | 1120 | if( ecp_get_type( grp ) != POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS ) |
ansond | 0:137634ff4186 | 1121 | return( POLARSSL_ERR_ECP_FEATURE_UNAVAILABLE ); |
ansond | 0:137634ff4186 | 1122 | |
ansond | 0:137634ff4186 | 1123 | /* mQ = - Q */ |
ansond | 0:137634ff4186 | 1124 | MPI_CHK( ecp_copy( &mQ, Q ) ); |
ansond | 0:137634ff4186 | 1125 | if( mpi_cmp_int( &mQ.Y, 0 ) != 0 ) |
ansond | 0:137634ff4186 | 1126 | MPI_CHK( mpi_sub_mpi( &mQ.Y, &grp->P, &mQ.Y ) ); |
ansond | 0:137634ff4186 | 1127 | |
ansond | 0:137634ff4186 | 1128 | MPI_CHK( ecp_add_mixed( grp, R, P, &mQ ) ); |
ansond | 0:137634ff4186 | 1129 | MPI_CHK( ecp_normalize_jac( grp, R ) ); |
ansond | 0:137634ff4186 | 1130 | |
ansond | 0:137634ff4186 | 1131 | cleanup: |
ansond | 0:137634ff4186 | 1132 | ecp_point_free( &mQ ); |
ansond | 0:137634ff4186 | 1133 | |
ansond | 0:137634ff4186 | 1134 | return( ret ); |
ansond | 0:137634ff4186 | 1135 | } |
ansond | 0:137634ff4186 | 1136 | |
ansond | 0:137634ff4186 | 1137 | /* |
ansond | 0:137634ff4186 | 1138 | * Randomize jacobian coordinates: |
ansond | 0:137634ff4186 | 1139 | * (X, Y, Z) -> (l^2 X, l^3 Y, l Z) for random l |
ansond | 0:137634ff4186 | 1140 | * This is sort of the reverse operation of ecp_normalize_jac(). |
ansond | 0:137634ff4186 | 1141 | * |
ansond | 0:137634ff4186 | 1142 | * This countermeasure was first suggested in [2]. |
ansond | 0:137634ff4186 | 1143 | */ |
ansond | 0:137634ff4186 | 1144 | static int ecp_randomize_jac( const ecp_group *grp, ecp_point *pt, |
ansond | 0:137634ff4186 | 1145 | int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) |
ansond | 0:137634ff4186 | 1146 | { |
ansond | 0:137634ff4186 | 1147 | int ret; |
ansond | 0:137634ff4186 | 1148 | mpi l, ll; |
ansond | 0:137634ff4186 | 1149 | size_t p_size = ( grp->pbits + 7 ) / 8; |
ansond | 0:137634ff4186 | 1150 | int count = 0; |
ansond | 0:137634ff4186 | 1151 | |
ansond | 0:137634ff4186 | 1152 | mpi_init( &l ); mpi_init( &ll ); |
ansond | 0:137634ff4186 | 1153 | |
ansond | 0:137634ff4186 | 1154 | /* Generate l such that 1 < l < p */ |
ansond | 0:137634ff4186 | 1155 | do |
ansond | 0:137634ff4186 | 1156 | { |
ansond | 0:137634ff4186 | 1157 | mpi_fill_random( &l, p_size, f_rng, p_rng ); |
ansond | 0:137634ff4186 | 1158 | |
ansond | 0:137634ff4186 | 1159 | while( mpi_cmp_mpi( &l, &grp->P ) >= 0 ) |
ansond | 0:137634ff4186 | 1160 | MPI_CHK( mpi_shift_r( &l, 1 ) ); |
ansond | 0:137634ff4186 | 1161 | |
ansond | 0:137634ff4186 | 1162 | if( count++ > 10 ) |
ansond | 0:137634ff4186 | 1163 | return( POLARSSL_ERR_ECP_RANDOM_FAILED ); |
ansond | 0:137634ff4186 | 1164 | } |
ansond | 0:137634ff4186 | 1165 | while( mpi_cmp_int( &l, 1 ) <= 0 ); |
ansond | 0:137634ff4186 | 1166 | |
ansond | 0:137634ff4186 | 1167 | /* Z = l * Z */ |
ansond | 0:137634ff4186 | 1168 | MPI_CHK( mpi_mul_mpi( &pt->Z, &pt->Z, &l ) ); MOD_MUL( pt->Z ); |
ansond | 0:137634ff4186 | 1169 | |
ansond | 0:137634ff4186 | 1170 | /* X = l^2 * X */ |
ansond | 0:137634ff4186 | 1171 | MPI_CHK( mpi_mul_mpi( &ll, &l, &l ) ); MOD_MUL( ll ); |
ansond | 0:137634ff4186 | 1172 | MPI_CHK( mpi_mul_mpi( &pt->X, &pt->X, &ll ) ); MOD_MUL( pt->X ); |
ansond | 0:137634ff4186 | 1173 | |
ansond | 0:137634ff4186 | 1174 | /* Y = l^3 * Y */ |
ansond | 0:137634ff4186 | 1175 | MPI_CHK( mpi_mul_mpi( &ll, &ll, &l ) ); MOD_MUL( ll ); |
ansond | 0:137634ff4186 | 1176 | MPI_CHK( mpi_mul_mpi( &pt->Y, &pt->Y, &ll ) ); MOD_MUL( pt->Y ); |
ansond | 0:137634ff4186 | 1177 | |
ansond | 0:137634ff4186 | 1178 | cleanup: |
ansond | 0:137634ff4186 | 1179 | mpi_free( &l ); mpi_free( &ll ); |
ansond | 0:137634ff4186 | 1180 | |
ansond | 0:137634ff4186 | 1181 | return( ret ); |
ansond | 0:137634ff4186 | 1182 | } |
ansond | 0:137634ff4186 | 1183 | |
ansond | 0:137634ff4186 | 1184 | /* |
ansond | 0:137634ff4186 | 1185 | * Check and define parameters used by the comb method (see below for details) |
ansond | 0:137634ff4186 | 1186 | */ |
ansond | 0:137634ff4186 | 1187 | #if POLARSSL_ECP_WINDOW_SIZE < 2 || POLARSSL_ECP_WINDOW_SIZE > 7 |
ansond | 0:137634ff4186 | 1188 | #error "POLARSSL_ECP_WINDOW_SIZE out of bounds" |
ansond | 0:137634ff4186 | 1189 | #endif |
ansond | 0:137634ff4186 | 1190 | |
ansond | 0:137634ff4186 | 1191 | /* d = ceil( n / w ) */ |
ansond | 0:137634ff4186 | 1192 | #define COMB_MAX_D ( POLARSSL_ECP_MAX_BITS + 1 ) / 2 |
ansond | 0:137634ff4186 | 1193 | |
ansond | 0:137634ff4186 | 1194 | /* number of precomputed points */ |
ansond | 0:137634ff4186 | 1195 | #define COMB_MAX_PRE ( 1 << ( POLARSSL_ECP_WINDOW_SIZE - 1 ) ) |
ansond | 0:137634ff4186 | 1196 | |
ansond | 0:137634ff4186 | 1197 | /* |
ansond | 0:137634ff4186 | 1198 | * Compute the representation of m that will be used with our comb method. |
ansond | 0:137634ff4186 | 1199 | * |
ansond | 0:137634ff4186 | 1200 | * The basic comb method is described in GECC 3.44 for example. We use a |
ansond | 0:137634ff4186 | 1201 | * modified version that provides resistance to SPA by avoiding zero |
ansond | 0:137634ff4186 | 1202 | * digits in the representation as in [3]. We modify the method further by |
ansond | 0:137634ff4186 | 1203 | * requiring that all K_i be odd, which has the small cost that our |
ansond | 0:137634ff4186 | 1204 | * representation uses one more K_i, due to carries. |
ansond | 0:137634ff4186 | 1205 | * |
ansond | 0:137634ff4186 | 1206 | * Also, for the sake of compactness, only the seven low-order bits of x[i] |
ansond | 0:137634ff4186 | 1207 | * are used to represent K_i, and the msb of x[i] encodes the the sign (s_i in |
ansond | 0:137634ff4186 | 1208 | * the paper): it is set if and only if if s_i == -1; |
ansond | 0:137634ff4186 | 1209 | * |
ansond | 0:137634ff4186 | 1210 | * Calling conventions: |
ansond | 0:137634ff4186 | 1211 | * - x is an array of size d + 1 |
ansond | 0:137634ff4186 | 1212 | * - w is the size, ie number of teeth, of the comb, and must be between |
ansond | 0:137634ff4186 | 1213 | * 2 and 7 (in practice, between 2 and POLARSSL_ECP_WINDOW_SIZE) |
ansond | 0:137634ff4186 | 1214 | * - m is the MPI, expected to be odd and such that bitlength(m) <= w * d |
ansond | 0:137634ff4186 | 1215 | * (the result will be incorrect if these assumptions are not satisfied) |
ansond | 0:137634ff4186 | 1216 | */ |
ansond | 0:137634ff4186 | 1217 | static void ecp_comb_fixed( unsigned char x[], size_t d, |
ansond | 0:137634ff4186 | 1218 | unsigned char w, const mpi *m ) |
ansond | 0:137634ff4186 | 1219 | { |
ansond | 0:137634ff4186 | 1220 | size_t i, j; |
ansond | 0:137634ff4186 | 1221 | unsigned char c, cc, adjust; |
ansond | 0:137634ff4186 | 1222 | |
ansond | 0:137634ff4186 | 1223 | memset( x, 0, d+1 ); |
ansond | 0:137634ff4186 | 1224 | |
ansond | 0:137634ff4186 | 1225 | /* First get the classical comb values (except for x_d = 0) */ |
ansond | 0:137634ff4186 | 1226 | for( i = 0; i < d; i++ ) |
ansond | 0:137634ff4186 | 1227 | for( j = 0; j < w; j++ ) |
ansond | 0:137634ff4186 | 1228 | x[i] |= mpi_get_bit( m, i + d * j ) << j; |
ansond | 0:137634ff4186 | 1229 | |
ansond | 0:137634ff4186 | 1230 | /* Now make sure x_1 .. x_d are odd */ |
ansond | 0:137634ff4186 | 1231 | c = 0; |
ansond | 0:137634ff4186 | 1232 | for( i = 1; i <= d; i++ ) |
ansond | 0:137634ff4186 | 1233 | { |
ansond | 0:137634ff4186 | 1234 | /* Add carry and update it */ |
ansond | 0:137634ff4186 | 1235 | cc = x[i] & c; |
ansond | 0:137634ff4186 | 1236 | x[i] = x[i] ^ c; |
ansond | 0:137634ff4186 | 1237 | c = cc; |
ansond | 0:137634ff4186 | 1238 | |
ansond | 0:137634ff4186 | 1239 | /* Adjust if needed, avoiding branches */ |
ansond | 0:137634ff4186 | 1240 | adjust = 1 - ( x[i] & 0x01 ); |
ansond | 0:137634ff4186 | 1241 | c |= x[i] & ( x[i-1] * adjust ); |
ansond | 0:137634ff4186 | 1242 | x[i] = x[i] ^ ( x[i-1] * adjust ); |
ansond | 0:137634ff4186 | 1243 | x[i-1] |= adjust << 7; |
ansond | 0:137634ff4186 | 1244 | } |
ansond | 0:137634ff4186 | 1245 | } |
ansond | 0:137634ff4186 | 1246 | |
ansond | 0:137634ff4186 | 1247 | /* |
ansond | 0:137634ff4186 | 1248 | * Precompute points for the comb method |
ansond | 0:137634ff4186 | 1249 | * |
ansond | 0:137634ff4186 | 1250 | * If i = i_{w-1} ... i_1 is the binary representation of i, then |
ansond | 0:137634ff4186 | 1251 | * T[i] = i_{w-1} 2^{(w-1)d} P + ... + i_1 2^d P + P |
ansond | 0:137634ff4186 | 1252 | * |
ansond | 0:137634ff4186 | 1253 | * T must be able to hold 2^{w - 1} elements |
ansond | 0:137634ff4186 | 1254 | * |
ansond | 0:137634ff4186 | 1255 | * Cost: d(w-1) D + (2^{w-1} - 1) A + 1 N(w-1) + 1 N(2^{w-1} - 1) |
ansond | 0:137634ff4186 | 1256 | */ |
ansond | 0:137634ff4186 | 1257 | static int ecp_precompute_comb( const ecp_group *grp, |
ansond | 0:137634ff4186 | 1258 | ecp_point T[], const ecp_point *P, |
ansond | 0:137634ff4186 | 1259 | unsigned char w, size_t d ) |
ansond | 0:137634ff4186 | 1260 | { |
ansond | 0:137634ff4186 | 1261 | int ret; |
ansond | 0:137634ff4186 | 1262 | unsigned char i, k; |
ansond | 0:137634ff4186 | 1263 | size_t j; |
ansond | 0:137634ff4186 | 1264 | ecp_point *cur, *TT[COMB_MAX_PRE - 1]; |
ansond | 0:137634ff4186 | 1265 | |
ansond | 0:137634ff4186 | 1266 | /* |
ansond | 0:137634ff4186 | 1267 | * Set T[0] = P and |
ansond | 0:137634ff4186 | 1268 | * T[2^{l-1}] = 2^{dl} P for l = 1 .. w-1 (this is not the final value) |
ansond | 0:137634ff4186 | 1269 | */ |
ansond | 0:137634ff4186 | 1270 | MPI_CHK( ecp_copy( &T[0], P ) ); |
ansond | 0:137634ff4186 | 1271 | |
ansond | 0:137634ff4186 | 1272 | k = 0; |
ansond | 0:137634ff4186 | 1273 | for( i = 1; i < ( 1U << ( w - 1 ) ); i <<= 1 ) |
ansond | 0:137634ff4186 | 1274 | { |
ansond | 0:137634ff4186 | 1275 | cur = T + i; |
ansond | 0:137634ff4186 | 1276 | MPI_CHK( ecp_copy( cur, T + ( i >> 1 ) ) ); |
ansond | 0:137634ff4186 | 1277 | for( j = 0; j < d; j++ ) |
ansond | 0:137634ff4186 | 1278 | MPI_CHK( ecp_double_jac( grp, cur, cur ) ); |
ansond | 0:137634ff4186 | 1279 | |
ansond | 0:137634ff4186 | 1280 | TT[k++] = cur; |
ansond | 0:137634ff4186 | 1281 | } |
ansond | 0:137634ff4186 | 1282 | |
ansond | 0:137634ff4186 | 1283 | MPI_CHK( ecp_normalize_jac_many( grp, TT, k ) ); |
ansond | 0:137634ff4186 | 1284 | |
ansond | 0:137634ff4186 | 1285 | /* |
ansond | 0:137634ff4186 | 1286 | * Compute the remaining ones using the minimal number of additions |
ansond | 0:137634ff4186 | 1287 | * Be careful to update T[2^l] only after using it! |
ansond | 0:137634ff4186 | 1288 | */ |
ansond | 0:137634ff4186 | 1289 | k = 0; |
ansond | 0:137634ff4186 | 1290 | for( i = 1; i < ( 1U << ( w - 1 ) ); i <<= 1 ) |
ansond | 0:137634ff4186 | 1291 | { |
ansond | 0:137634ff4186 | 1292 | j = i; |
ansond | 0:137634ff4186 | 1293 | while( j-- ) |
ansond | 0:137634ff4186 | 1294 | { |
ansond | 0:137634ff4186 | 1295 | MPI_CHK( ecp_add_mixed( grp, &T[i + j], &T[j], &T[i] ) ); |
ansond | 0:137634ff4186 | 1296 | TT[k++] = &T[i + j]; |
ansond | 0:137634ff4186 | 1297 | } |
ansond | 0:137634ff4186 | 1298 | } |
ansond | 0:137634ff4186 | 1299 | |
ansond | 0:137634ff4186 | 1300 | MPI_CHK( ecp_normalize_jac_many( grp, TT, k ) ); |
ansond | 0:137634ff4186 | 1301 | |
ansond | 0:137634ff4186 | 1302 | cleanup: |
ansond | 0:137634ff4186 | 1303 | return( ret ); |
ansond | 0:137634ff4186 | 1304 | } |
ansond | 0:137634ff4186 | 1305 | |
ansond | 0:137634ff4186 | 1306 | /* |
ansond | 0:137634ff4186 | 1307 | * Select precomputed point: R = sign(i) * T[ abs(i) / 2 ] |
ansond | 0:137634ff4186 | 1308 | */ |
ansond | 0:137634ff4186 | 1309 | static int ecp_select_comb( const ecp_group *grp, ecp_point *R, |
ansond | 0:137634ff4186 | 1310 | const ecp_point T[], unsigned char t_len, |
ansond | 0:137634ff4186 | 1311 | unsigned char i ) |
ansond | 0:137634ff4186 | 1312 | { |
ansond | 0:137634ff4186 | 1313 | int ret; |
ansond | 0:137634ff4186 | 1314 | unsigned char ii, j; |
ansond | 0:137634ff4186 | 1315 | |
ansond | 0:137634ff4186 | 1316 | /* Ignore the "sign" bit and scale down */ |
ansond | 0:137634ff4186 | 1317 | ii = ( i & 0x7Fu ) >> 1; |
ansond | 0:137634ff4186 | 1318 | |
ansond | 0:137634ff4186 | 1319 | /* Read the whole table to thwart cache-based timing attacks */ |
ansond | 0:137634ff4186 | 1320 | for( j = 0; j < t_len; j++ ) |
ansond | 0:137634ff4186 | 1321 | { |
ansond | 0:137634ff4186 | 1322 | MPI_CHK( mpi_safe_cond_assign( &R->X, &T[j].X, j == ii ) ); |
ansond | 0:137634ff4186 | 1323 | MPI_CHK( mpi_safe_cond_assign( &R->Y, &T[j].Y, j == ii ) ); |
ansond | 0:137634ff4186 | 1324 | } |
ansond | 0:137634ff4186 | 1325 | |
ansond | 0:137634ff4186 | 1326 | /* Safely invert result if i is "negative" */ |
ansond | 0:137634ff4186 | 1327 | MPI_CHK( ecp_safe_invert_jac( grp, R, i >> 7 ) ); |
ansond | 0:137634ff4186 | 1328 | |
ansond | 0:137634ff4186 | 1329 | cleanup: |
ansond | 0:137634ff4186 | 1330 | return( ret ); |
ansond | 0:137634ff4186 | 1331 | } |
ansond | 0:137634ff4186 | 1332 | |
ansond | 0:137634ff4186 | 1333 | /* |
ansond | 0:137634ff4186 | 1334 | * Core multiplication algorithm for the (modified) comb method. |
ansond | 0:137634ff4186 | 1335 | * This part is actually common with the basic comb method (GECC 3.44) |
ansond | 0:137634ff4186 | 1336 | * |
ansond | 0:137634ff4186 | 1337 | * Cost: d A + d D + 1 R |
ansond | 0:137634ff4186 | 1338 | */ |
ansond | 0:137634ff4186 | 1339 | static int ecp_mul_comb_core( const ecp_group *grp, ecp_point *R, |
ansond | 0:137634ff4186 | 1340 | const ecp_point T[], unsigned char t_len, |
ansond | 0:137634ff4186 | 1341 | const unsigned char x[], size_t d, |
ansond | 0:137634ff4186 | 1342 | int (*f_rng)(void *, unsigned char *, size_t), |
ansond | 0:137634ff4186 | 1343 | void *p_rng ) |
ansond | 0:137634ff4186 | 1344 | { |
ansond | 0:137634ff4186 | 1345 | int ret; |
ansond | 0:137634ff4186 | 1346 | ecp_point Txi; |
ansond | 0:137634ff4186 | 1347 | size_t i; |
ansond | 0:137634ff4186 | 1348 | |
ansond | 0:137634ff4186 | 1349 | ecp_point_init( &Txi ); |
ansond | 0:137634ff4186 | 1350 | |
ansond | 0:137634ff4186 | 1351 | /* Start with a non-zero point and randomize its coordinates */ |
ansond | 0:137634ff4186 | 1352 | i = d; |
ansond | 0:137634ff4186 | 1353 | MPI_CHK( ecp_select_comb( grp, R, T, t_len, x[i] ) ); |
ansond | 0:137634ff4186 | 1354 | MPI_CHK( mpi_lset( &R->Z, 1 ) ); |
ansond | 0:137634ff4186 | 1355 | if( f_rng != 0 ) |
ansond | 0:137634ff4186 | 1356 | MPI_CHK( ecp_randomize_jac( grp, R, f_rng, p_rng ) ); |
ansond | 0:137634ff4186 | 1357 | |
ansond | 0:137634ff4186 | 1358 | while( i-- != 0 ) |
ansond | 0:137634ff4186 | 1359 | { |
ansond | 0:137634ff4186 | 1360 | MPI_CHK( ecp_double_jac( grp, R, R ) ); |
ansond | 0:137634ff4186 | 1361 | MPI_CHK( ecp_select_comb( grp, &Txi, T, t_len, x[i] ) ); |
ansond | 0:137634ff4186 | 1362 | MPI_CHK( ecp_add_mixed( grp, R, R, &Txi ) ); |
ansond | 0:137634ff4186 | 1363 | } |
ansond | 0:137634ff4186 | 1364 | |
ansond | 0:137634ff4186 | 1365 | cleanup: |
ansond | 0:137634ff4186 | 1366 | ecp_point_free( &Txi ); |
ansond | 0:137634ff4186 | 1367 | |
ansond | 0:137634ff4186 | 1368 | return( ret ); |
ansond | 0:137634ff4186 | 1369 | } |
ansond | 0:137634ff4186 | 1370 | |
ansond | 0:137634ff4186 | 1371 | /* |
ansond | 0:137634ff4186 | 1372 | * Multiplication using the comb method, |
ansond | 0:137634ff4186 | 1373 | * for curves in short Weierstrass form |
ansond | 0:137634ff4186 | 1374 | */ |
ansond | 0:137634ff4186 | 1375 | static int ecp_mul_comb( ecp_group *grp, ecp_point *R, |
ansond | 0:137634ff4186 | 1376 | const mpi *m, const ecp_point *P, |
ansond | 0:137634ff4186 | 1377 | int (*f_rng)(void *, unsigned char *, size_t), |
ansond | 0:137634ff4186 | 1378 | void *p_rng ) |
ansond | 0:137634ff4186 | 1379 | { |
ansond | 0:137634ff4186 | 1380 | int ret; |
ansond | 0:137634ff4186 | 1381 | unsigned char w, m_is_odd, p_eq_g, pre_len, i; |
ansond | 0:137634ff4186 | 1382 | size_t d; |
ansond | 0:137634ff4186 | 1383 | unsigned char k[COMB_MAX_D + 1]; |
ansond | 0:137634ff4186 | 1384 | ecp_point *T; |
ansond | 0:137634ff4186 | 1385 | mpi M, mm; |
ansond | 0:137634ff4186 | 1386 | |
ansond | 0:137634ff4186 | 1387 | mpi_init( &M ); |
ansond | 0:137634ff4186 | 1388 | mpi_init( &mm ); |
ansond | 0:137634ff4186 | 1389 | |
ansond | 0:137634ff4186 | 1390 | /* we need N to be odd to trnaform m in an odd number, check now */ |
ansond | 0:137634ff4186 | 1391 | if( mpi_get_bit( &grp->N, 0 ) != 1 ) |
ansond | 0:137634ff4186 | 1392 | return( POLARSSL_ERR_ECP_BAD_INPUT_DATA ); |
ansond | 0:137634ff4186 | 1393 | |
ansond | 0:137634ff4186 | 1394 | /* |
ansond | 0:137634ff4186 | 1395 | * Minimize the number of multiplications, that is minimize |
ansond | 0:137634ff4186 | 1396 | * 10 * d * w + 18 * 2^(w-1) + 11 * d + 7 * w, with d = ceil( nbits / w ) |
ansond | 0:137634ff4186 | 1397 | * (see costs of the various parts, with 1S = 1M) |
ansond | 0:137634ff4186 | 1398 | */ |
ansond | 0:137634ff4186 | 1399 | w = grp->nbits >= 384 ? 5 : 4; |
ansond | 0:137634ff4186 | 1400 | |
ansond | 0:137634ff4186 | 1401 | /* |
ansond | 0:137634ff4186 | 1402 | * If P == G, pre-compute a bit more, since this may be re-used later. |
ansond | 0:137634ff4186 | 1403 | * Just adding one avoids upping the cost of the first mul too much, |
ansond | 0:137634ff4186 | 1404 | * and the memory cost too. |
ansond | 0:137634ff4186 | 1405 | */ |
ansond | 0:137634ff4186 | 1406 | #if POLARSSL_ECP_FIXED_POINT_OPTIM == 1 |
ansond | 0:137634ff4186 | 1407 | p_eq_g = ( mpi_cmp_mpi( &P->Y, &grp->G.Y ) == 0 && |
ansond | 0:137634ff4186 | 1408 | mpi_cmp_mpi( &P->X, &grp->G.X ) == 0 ); |
ansond | 0:137634ff4186 | 1409 | if( p_eq_g ) |
ansond | 0:137634ff4186 | 1410 | w++; |
ansond | 0:137634ff4186 | 1411 | #else |
ansond | 0:137634ff4186 | 1412 | p_eq_g = 0; |
ansond | 0:137634ff4186 | 1413 | #endif |
ansond | 0:137634ff4186 | 1414 | |
ansond | 0:137634ff4186 | 1415 | /* |
ansond | 0:137634ff4186 | 1416 | * Make sure w is within bounds. |
ansond | 0:137634ff4186 | 1417 | * (The last test is useful only for very small curves in the test suite.) |
ansond | 0:137634ff4186 | 1418 | */ |
ansond | 0:137634ff4186 | 1419 | if( w > POLARSSL_ECP_WINDOW_SIZE ) |
ansond | 0:137634ff4186 | 1420 | w = POLARSSL_ECP_WINDOW_SIZE; |
ansond | 0:137634ff4186 | 1421 | if( w >= grp->nbits ) |
ansond | 0:137634ff4186 | 1422 | w = 2; |
ansond | 0:137634ff4186 | 1423 | |
ansond | 0:137634ff4186 | 1424 | /* Other sizes that depend on w */ |
ansond | 0:137634ff4186 | 1425 | pre_len = 1U << ( w - 1 ); |
ansond | 0:137634ff4186 | 1426 | d = ( grp->nbits + w - 1 ) / w; |
ansond | 0:137634ff4186 | 1427 | |
ansond | 0:137634ff4186 | 1428 | /* |
ansond | 0:137634ff4186 | 1429 | * Prepare precomputed points: if P == G we want to |
ansond | 0:137634ff4186 | 1430 | * use grp->T if already initialized, or initialize it. |
ansond | 0:137634ff4186 | 1431 | */ |
ansond | 0:137634ff4186 | 1432 | T = p_eq_g ? grp->T : NULL; |
ansond | 0:137634ff4186 | 1433 | |
ansond | 0:137634ff4186 | 1434 | if( T == NULL ) |
ansond | 0:137634ff4186 | 1435 | { |
ansond | 0:137634ff4186 | 1436 | T = polarssl_malloc( pre_len * sizeof( ecp_point ) ); |
ansond | 0:137634ff4186 | 1437 | if( T == NULL ) |
ansond | 0:137634ff4186 | 1438 | { |
ansond | 0:137634ff4186 | 1439 | ret = POLARSSL_ERR_ECP_MALLOC_FAILED; |
ansond | 0:137634ff4186 | 1440 | goto cleanup; |
ansond | 0:137634ff4186 | 1441 | } |
ansond | 0:137634ff4186 | 1442 | |
ansond | 0:137634ff4186 | 1443 | for( i = 0; i < pre_len; i++ ) |
ansond | 0:137634ff4186 | 1444 | ecp_point_init( &T[i] ); |
ansond | 0:137634ff4186 | 1445 | |
ansond | 0:137634ff4186 | 1446 | MPI_CHK( ecp_precompute_comb( grp, T, P, w, d ) ); |
ansond | 0:137634ff4186 | 1447 | |
ansond | 0:137634ff4186 | 1448 | if( p_eq_g ) |
ansond | 0:137634ff4186 | 1449 | { |
ansond | 0:137634ff4186 | 1450 | grp->T = T; |
ansond | 0:137634ff4186 | 1451 | grp->T_size = pre_len; |
ansond | 0:137634ff4186 | 1452 | } |
ansond | 0:137634ff4186 | 1453 | } |
ansond | 0:137634ff4186 | 1454 | |
ansond | 0:137634ff4186 | 1455 | /* |
ansond | 0:137634ff4186 | 1456 | * Make sure M is odd (M = m or M = N - m, since N is odd) |
ansond | 0:137634ff4186 | 1457 | * using the fact that m * P = - (N - m) * P |
ansond | 0:137634ff4186 | 1458 | */ |
ansond | 0:137634ff4186 | 1459 | m_is_odd = ( mpi_get_bit( m, 0 ) == 1 ); |
ansond | 0:137634ff4186 | 1460 | MPI_CHK( mpi_copy( &M, m ) ); |
ansond | 0:137634ff4186 | 1461 | MPI_CHK( mpi_sub_mpi( &mm, &grp->N, m ) ); |
ansond | 0:137634ff4186 | 1462 | MPI_CHK( mpi_safe_cond_assign( &M, &mm, ! m_is_odd ) ); |
ansond | 0:137634ff4186 | 1463 | |
ansond | 0:137634ff4186 | 1464 | /* |
ansond | 0:137634ff4186 | 1465 | * Go for comb multiplication, R = M * P |
ansond | 0:137634ff4186 | 1466 | */ |
ansond | 0:137634ff4186 | 1467 | ecp_comb_fixed( k, d, w, &M ); |
ansond | 0:137634ff4186 | 1468 | MPI_CHK( ecp_mul_comb_core( grp, R, T, pre_len, k, d, f_rng, p_rng ) ); |
ansond | 0:137634ff4186 | 1469 | |
ansond | 0:137634ff4186 | 1470 | /* |
ansond | 0:137634ff4186 | 1471 | * Now get m * P from M * P and normalize it |
ansond | 0:137634ff4186 | 1472 | */ |
ansond | 0:137634ff4186 | 1473 | MPI_CHK( ecp_safe_invert_jac( grp, R, ! m_is_odd ) ); |
ansond | 0:137634ff4186 | 1474 | MPI_CHK( ecp_normalize_jac( grp, R ) ); |
ansond | 0:137634ff4186 | 1475 | |
ansond | 0:137634ff4186 | 1476 | cleanup: |
ansond | 0:137634ff4186 | 1477 | |
ansond | 0:137634ff4186 | 1478 | if( T != NULL && ! p_eq_g ) |
ansond | 0:137634ff4186 | 1479 | { |
ansond | 0:137634ff4186 | 1480 | for( i = 0; i < pre_len; i++ ) |
ansond | 0:137634ff4186 | 1481 | ecp_point_free( &T[i] ); |
ansond | 0:137634ff4186 | 1482 | polarssl_free( T ); |
ansond | 0:137634ff4186 | 1483 | } |
ansond | 0:137634ff4186 | 1484 | |
ansond | 0:137634ff4186 | 1485 | mpi_free( &M ); |
ansond | 0:137634ff4186 | 1486 | mpi_free( &mm ); |
ansond | 0:137634ff4186 | 1487 | |
ansond | 0:137634ff4186 | 1488 | if( ret != 0 ) |
ansond | 0:137634ff4186 | 1489 | ecp_point_free( R ); |
ansond | 0:137634ff4186 | 1490 | |
ansond | 0:137634ff4186 | 1491 | return( ret ); |
ansond | 0:137634ff4186 | 1492 | } |
ansond | 0:137634ff4186 | 1493 | |
ansond | 0:137634ff4186 | 1494 | #endif /* POLARSSL_ECP_SHORT_WEIERSTRASS */ |
ansond | 0:137634ff4186 | 1495 | |
ansond | 0:137634ff4186 | 1496 | #if defined(POLARSSL_ECP_MONTGOMERY) |
ansond | 0:137634ff4186 | 1497 | /* |
ansond | 0:137634ff4186 | 1498 | * For Montgomery curves, we do all the internal arithmetic in projective |
ansond | 0:137634ff4186 | 1499 | * coordinates. Import/export of points uses only the x coordinates, which is |
ansond | 0:137634ff4186 | 1500 | * internaly represented as X / Z. |
ansond | 0:137634ff4186 | 1501 | * |
ansond | 0:137634ff4186 | 1502 | * For scalar multiplication, we'll use a Montgomery ladder. |
ansond | 0:137634ff4186 | 1503 | */ |
ansond | 0:137634ff4186 | 1504 | |
ansond | 0:137634ff4186 | 1505 | /* |
ansond | 0:137634ff4186 | 1506 | * Normalize Montgomery x/z coordinates: X = X/Z, Z = 1 |
ansond | 0:137634ff4186 | 1507 | * Cost: 1M + 1I |
ansond | 0:137634ff4186 | 1508 | */ |
ansond | 0:137634ff4186 | 1509 | static int ecp_normalize_mxz( const ecp_group *grp, ecp_point *P ) |
ansond | 0:137634ff4186 | 1510 | { |
ansond | 0:137634ff4186 | 1511 | int ret; |
ansond | 0:137634ff4186 | 1512 | |
ansond | 0:137634ff4186 | 1513 | MPI_CHK( mpi_inv_mod( &P->Z, &P->Z, &grp->P ) ); |
ansond | 0:137634ff4186 | 1514 | MPI_CHK( mpi_mul_mpi( &P->X, &P->X, &P->Z ) ); MOD_MUL( P->X ); |
ansond | 0:137634ff4186 | 1515 | MPI_CHK( mpi_lset( &P->Z, 1 ) ); |
ansond | 0:137634ff4186 | 1516 | |
ansond | 0:137634ff4186 | 1517 | cleanup: |
ansond | 0:137634ff4186 | 1518 | return( ret ); |
ansond | 0:137634ff4186 | 1519 | } |
ansond | 0:137634ff4186 | 1520 | |
ansond | 0:137634ff4186 | 1521 | /* |
ansond | 0:137634ff4186 | 1522 | * Randomize projective x/z coordinates: |
ansond | 0:137634ff4186 | 1523 | * (X, Z) -> (l X, l Z) for random l |
ansond | 0:137634ff4186 | 1524 | * This is sort of the reverse operation of ecp_normalize_mxz(). |
ansond | 0:137634ff4186 | 1525 | * |
ansond | 0:137634ff4186 | 1526 | * This countermeasure was first suggested in [2]. |
ansond | 0:137634ff4186 | 1527 | * Cost: 2M |
ansond | 0:137634ff4186 | 1528 | */ |
ansond | 0:137634ff4186 | 1529 | static int ecp_randomize_mxz( const ecp_group *grp, ecp_point *P, |
ansond | 0:137634ff4186 | 1530 | int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) |
ansond | 0:137634ff4186 | 1531 | { |
ansond | 0:137634ff4186 | 1532 | int ret; |
ansond | 0:137634ff4186 | 1533 | mpi l; |
ansond | 0:137634ff4186 | 1534 | size_t p_size = ( grp->pbits + 7 ) / 8; |
ansond | 0:137634ff4186 | 1535 | int count = 0; |
ansond | 0:137634ff4186 | 1536 | |
ansond | 0:137634ff4186 | 1537 | mpi_init( &l ); |
ansond | 0:137634ff4186 | 1538 | |
ansond | 0:137634ff4186 | 1539 | /* Generate l such that 1 < l < p */ |
ansond | 0:137634ff4186 | 1540 | do |
ansond | 0:137634ff4186 | 1541 | { |
ansond | 0:137634ff4186 | 1542 | mpi_fill_random( &l, p_size, f_rng, p_rng ); |
ansond | 0:137634ff4186 | 1543 | |
ansond | 0:137634ff4186 | 1544 | while( mpi_cmp_mpi( &l, &grp->P ) >= 0 ) |
ansond | 0:137634ff4186 | 1545 | MPI_CHK( mpi_shift_r( &l, 1 ) ); |
ansond | 0:137634ff4186 | 1546 | |
ansond | 0:137634ff4186 | 1547 | if( count++ > 10 ) |
ansond | 0:137634ff4186 | 1548 | return( POLARSSL_ERR_ECP_RANDOM_FAILED ); |
ansond | 0:137634ff4186 | 1549 | } |
ansond | 0:137634ff4186 | 1550 | while( mpi_cmp_int( &l, 1 ) <= 0 ); |
ansond | 0:137634ff4186 | 1551 | |
ansond | 0:137634ff4186 | 1552 | MPI_CHK( mpi_mul_mpi( &P->X, &P->X, &l ) ); MOD_MUL( P->X ); |
ansond | 0:137634ff4186 | 1553 | MPI_CHK( mpi_mul_mpi( &P->Z, &P->Z, &l ) ); MOD_MUL( P->Z ); |
ansond | 0:137634ff4186 | 1554 | |
ansond | 0:137634ff4186 | 1555 | cleanup: |
ansond | 0:137634ff4186 | 1556 | mpi_free( &l ); |
ansond | 0:137634ff4186 | 1557 | |
ansond | 0:137634ff4186 | 1558 | return( ret ); |
ansond | 0:137634ff4186 | 1559 | } |
ansond | 0:137634ff4186 | 1560 | |
ansond | 0:137634ff4186 | 1561 | /* |
ansond | 0:137634ff4186 | 1562 | * Double-and-add: R = 2P, S = P + Q, with d = X(P - Q), |
ansond | 0:137634ff4186 | 1563 | * for Montgomery curves in x/z coordinates. |
ansond | 0:137634ff4186 | 1564 | * |
ansond | 0:137634ff4186 | 1565 | * http://www.hyperelliptic.org/EFD/g1p/auto-code/montgom/xz/ladder/mladd-1987-m.op3 |
ansond | 0:137634ff4186 | 1566 | * with |
ansond | 0:137634ff4186 | 1567 | * d = X1 |
ansond | 0:137634ff4186 | 1568 | * P = (X2, Z2) |
ansond | 0:137634ff4186 | 1569 | * Q = (X3, Z3) |
ansond | 0:137634ff4186 | 1570 | * R = (X4, Z4) |
ansond | 0:137634ff4186 | 1571 | * S = (X5, Z5) |
ansond | 0:137634ff4186 | 1572 | * and eliminating temporary variables tO, ..., t4. |
ansond | 0:137634ff4186 | 1573 | * |
ansond | 0:137634ff4186 | 1574 | * Cost: 5M + 4S |
ansond | 0:137634ff4186 | 1575 | */ |
ansond | 0:137634ff4186 | 1576 | static int ecp_double_add_mxz( const ecp_group *grp, |
ansond | 0:137634ff4186 | 1577 | ecp_point *R, ecp_point *S, |
ansond | 0:137634ff4186 | 1578 | const ecp_point *P, const ecp_point *Q, |
ansond | 0:137634ff4186 | 1579 | const mpi *d ) |
ansond | 0:137634ff4186 | 1580 | { |
ansond | 0:137634ff4186 | 1581 | int ret; |
ansond | 0:137634ff4186 | 1582 | mpi A, AA, B, BB, E, C, D, DA, CB; |
ansond | 0:137634ff4186 | 1583 | |
ansond | 0:137634ff4186 | 1584 | mpi_init( &A ); mpi_init( &AA ); mpi_init( &B ); |
ansond | 0:137634ff4186 | 1585 | mpi_init( &BB ); mpi_init( &E ); mpi_init( &C ); |
ansond | 0:137634ff4186 | 1586 | mpi_init( &D ); mpi_init( &DA ); mpi_init( &CB ); |
ansond | 0:137634ff4186 | 1587 | |
ansond | 0:137634ff4186 | 1588 | MPI_CHK( mpi_add_mpi( &A, &P->X, &P->Z ) ); MOD_ADD( A ); |
ansond | 0:137634ff4186 | 1589 | MPI_CHK( mpi_mul_mpi( &AA, &A, &A ) ); MOD_MUL( AA ); |
ansond | 0:137634ff4186 | 1590 | MPI_CHK( mpi_sub_mpi( &B, &P->X, &P->Z ) ); MOD_SUB( B ); |
ansond | 0:137634ff4186 | 1591 | MPI_CHK( mpi_mul_mpi( &BB, &B, &B ) ); MOD_MUL( BB ); |
ansond | 0:137634ff4186 | 1592 | MPI_CHK( mpi_sub_mpi( &E, &AA, &BB ) ); MOD_SUB( E ); |
ansond | 0:137634ff4186 | 1593 | MPI_CHK( mpi_add_mpi( &C, &Q->X, &Q->Z ) ); MOD_ADD( C ); |
ansond | 0:137634ff4186 | 1594 | MPI_CHK( mpi_sub_mpi( &D, &Q->X, &Q->Z ) ); MOD_SUB( D ); |
ansond | 0:137634ff4186 | 1595 | MPI_CHK( mpi_mul_mpi( &DA, &D, &A ) ); MOD_MUL( DA ); |
ansond | 0:137634ff4186 | 1596 | MPI_CHK( mpi_mul_mpi( &CB, &C, &B ) ); MOD_MUL( CB ); |
ansond | 0:137634ff4186 | 1597 | MPI_CHK( mpi_add_mpi( &S->X, &DA, &CB ) ); MOD_MUL( S->X ); |
ansond | 0:137634ff4186 | 1598 | MPI_CHK( mpi_mul_mpi( &S->X, &S->X, &S->X ) ); MOD_MUL( S->X ); |
ansond | 0:137634ff4186 | 1599 | MPI_CHK( mpi_sub_mpi( &S->Z, &DA, &CB ) ); MOD_SUB( S->Z ); |
ansond | 0:137634ff4186 | 1600 | MPI_CHK( mpi_mul_mpi( &S->Z, &S->Z, &S->Z ) ); MOD_MUL( S->Z ); |
ansond | 0:137634ff4186 | 1601 | MPI_CHK( mpi_mul_mpi( &S->Z, d, &S->Z ) ); MOD_MUL( S->Z ); |
ansond | 0:137634ff4186 | 1602 | MPI_CHK( mpi_mul_mpi( &R->X, &AA, &BB ) ); MOD_MUL( R->X ); |
ansond | 0:137634ff4186 | 1603 | MPI_CHK( mpi_mul_mpi( &R->Z, &grp->A, &E ) ); MOD_MUL( R->Z ); |
ansond | 0:137634ff4186 | 1604 | MPI_CHK( mpi_add_mpi( &R->Z, &BB, &R->Z ) ); MOD_ADD( R->Z ); |
ansond | 0:137634ff4186 | 1605 | MPI_CHK( mpi_mul_mpi( &R->Z, &E, &R->Z ) ); MOD_MUL( R->Z ); |
ansond | 0:137634ff4186 | 1606 | |
ansond | 0:137634ff4186 | 1607 | cleanup: |
ansond | 0:137634ff4186 | 1608 | mpi_free( &A ); mpi_free( &AA ); mpi_free( &B ); |
ansond | 0:137634ff4186 | 1609 | mpi_free( &BB ); mpi_free( &E ); mpi_free( &C ); |
ansond | 0:137634ff4186 | 1610 | mpi_free( &D ); mpi_free( &DA ); mpi_free( &CB ); |
ansond | 0:137634ff4186 | 1611 | |
ansond | 0:137634ff4186 | 1612 | return( ret ); |
ansond | 0:137634ff4186 | 1613 | } |
ansond | 0:137634ff4186 | 1614 | |
ansond | 0:137634ff4186 | 1615 | /* |
ansond | 0:137634ff4186 | 1616 | * Multiplication with Montgomery ladder in x/z coordinates, |
ansond | 0:137634ff4186 | 1617 | * for curves in Montgomery form |
ansond | 0:137634ff4186 | 1618 | */ |
ansond | 0:137634ff4186 | 1619 | static int ecp_mul_mxz( ecp_group *grp, ecp_point *R, |
ansond | 0:137634ff4186 | 1620 | const mpi *m, const ecp_point *P, |
ansond | 0:137634ff4186 | 1621 | int (*f_rng)(void *, unsigned char *, size_t), |
ansond | 0:137634ff4186 | 1622 | void *p_rng ) |
ansond | 0:137634ff4186 | 1623 | { |
ansond | 0:137634ff4186 | 1624 | int ret; |
ansond | 0:137634ff4186 | 1625 | size_t i; |
ansond | 0:137634ff4186 | 1626 | unsigned char b; |
ansond | 0:137634ff4186 | 1627 | ecp_point RP; |
ansond | 0:137634ff4186 | 1628 | mpi PX; |
ansond | 0:137634ff4186 | 1629 | |
ansond | 0:137634ff4186 | 1630 | ecp_point_init( &RP ); mpi_init( &PX ); |
ansond | 0:137634ff4186 | 1631 | |
ansond | 0:137634ff4186 | 1632 | /* Save PX and read from P before writing to R, in case P == R */ |
ansond | 0:137634ff4186 | 1633 | MPI_CHK( mpi_copy( &PX, &P->X ) ); |
ansond | 0:137634ff4186 | 1634 | MPI_CHK( ecp_copy( &RP, P ) ); |
ansond | 0:137634ff4186 | 1635 | |
ansond | 0:137634ff4186 | 1636 | /* Set R to zero in modified x/z coordinates */ |
ansond | 0:137634ff4186 | 1637 | MPI_CHK( mpi_lset( &R->X, 1 ) ); |
ansond | 0:137634ff4186 | 1638 | MPI_CHK( mpi_lset( &R->Z, 0 ) ); |
ansond | 0:137634ff4186 | 1639 | mpi_free( &R->Y ); |
ansond | 0:137634ff4186 | 1640 | |
ansond | 0:137634ff4186 | 1641 | /* RP.X might be sligtly larger than P, so reduce it */ |
ansond | 0:137634ff4186 | 1642 | MOD_ADD( RP.X ); |
ansond | 0:137634ff4186 | 1643 | |
ansond | 0:137634ff4186 | 1644 | /* Randomize coordinates of the starting point */ |
ansond | 0:137634ff4186 | 1645 | if( f_rng != NULL ) |
ansond | 0:137634ff4186 | 1646 | MPI_CHK( ecp_randomize_mxz( grp, &RP, f_rng, p_rng ) ); |
ansond | 0:137634ff4186 | 1647 | |
ansond | 0:137634ff4186 | 1648 | /* Loop invariant: R = result so far, RP = R + P */ |
ansond | 0:137634ff4186 | 1649 | i = mpi_msb( m ); /* one past the (zero-based) most significant bit */ |
ansond | 0:137634ff4186 | 1650 | while( i-- > 0 ) |
ansond | 0:137634ff4186 | 1651 | { |
ansond | 0:137634ff4186 | 1652 | b = mpi_get_bit( m, i ); |
ansond | 0:137634ff4186 | 1653 | /* |
ansond | 0:137634ff4186 | 1654 | * if (b) R = 2R + P else R = 2R, |
ansond | 0:137634ff4186 | 1655 | * which is: |
ansond | 0:137634ff4186 | 1656 | * if (b) double_add( RP, R, RP, R ) |
ansond | 0:137634ff4186 | 1657 | * else double_add( R, RP, R, RP ) |
ansond | 0:137634ff4186 | 1658 | * but using safe conditional swaps to avoid leaks |
ansond | 0:137634ff4186 | 1659 | */ |
ansond | 0:137634ff4186 | 1660 | MPI_CHK( mpi_safe_cond_swap( &R->X, &RP.X, b ) ); |
ansond | 0:137634ff4186 | 1661 | MPI_CHK( mpi_safe_cond_swap( &R->Z, &RP.Z, b ) ); |
ansond | 0:137634ff4186 | 1662 | MPI_CHK( ecp_double_add_mxz( grp, R, &RP, R, &RP, &PX ) ); |
ansond | 0:137634ff4186 | 1663 | MPI_CHK( mpi_safe_cond_swap( &R->X, &RP.X, b ) ); |
ansond | 0:137634ff4186 | 1664 | MPI_CHK( mpi_safe_cond_swap( &R->Z, &RP.Z, b ) ); |
ansond | 0:137634ff4186 | 1665 | } |
ansond | 0:137634ff4186 | 1666 | |
ansond | 0:137634ff4186 | 1667 | MPI_CHK( ecp_normalize_mxz( grp, R ) ); |
ansond | 0:137634ff4186 | 1668 | |
ansond | 0:137634ff4186 | 1669 | cleanup: |
ansond | 0:137634ff4186 | 1670 | ecp_point_free( &RP ); mpi_free( &PX ); |
ansond | 0:137634ff4186 | 1671 | |
ansond | 0:137634ff4186 | 1672 | return( ret ); |
ansond | 0:137634ff4186 | 1673 | } |
ansond | 0:137634ff4186 | 1674 | |
ansond | 0:137634ff4186 | 1675 | #endif /* POLARSSL_ECP_MONTGOMERY */ |
ansond | 0:137634ff4186 | 1676 | |
ansond | 0:137634ff4186 | 1677 | /* |
ansond | 0:137634ff4186 | 1678 | * Multiplication R = m * P |
ansond | 0:137634ff4186 | 1679 | */ |
ansond | 0:137634ff4186 | 1680 | int ecp_mul( ecp_group *grp, ecp_point *R, |
ansond | 0:137634ff4186 | 1681 | const mpi *m, const ecp_point *P, |
ansond | 0:137634ff4186 | 1682 | int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) |
ansond | 0:137634ff4186 | 1683 | { |
ansond | 0:137634ff4186 | 1684 | int ret; |
ansond | 0:137634ff4186 | 1685 | |
ansond | 0:137634ff4186 | 1686 | /* Common sanity checks */ |
ansond | 0:137634ff4186 | 1687 | if( mpi_cmp_int( &P->Z, 1 ) != 0 ) |
ansond | 0:137634ff4186 | 1688 | return( POLARSSL_ERR_ECP_BAD_INPUT_DATA ); |
ansond | 0:137634ff4186 | 1689 | |
ansond | 0:137634ff4186 | 1690 | if( ( ret = ecp_check_privkey( grp, m ) ) != 0 || |
ansond | 0:137634ff4186 | 1691 | ( ret = ecp_check_pubkey( grp, P ) ) != 0 ) |
ansond | 0:137634ff4186 | 1692 | return( ret ); |
ansond | 0:137634ff4186 | 1693 | |
ansond | 0:137634ff4186 | 1694 | #if defined(POLARSSL_ECP_MONTGOMERY) |
ansond | 0:137634ff4186 | 1695 | if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_MONTGOMERY ) |
ansond | 0:137634ff4186 | 1696 | return( ecp_mul_mxz( grp, R, m, P, f_rng, p_rng ) ); |
ansond | 0:137634ff4186 | 1697 | #endif |
ansond | 0:137634ff4186 | 1698 | #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS) |
ansond | 0:137634ff4186 | 1699 | if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS ) |
ansond | 0:137634ff4186 | 1700 | return( ecp_mul_comb( grp, R, m, P, f_rng, p_rng ) ); |
ansond | 0:137634ff4186 | 1701 | #endif |
ansond | 0:137634ff4186 | 1702 | return( POLARSSL_ERR_ECP_BAD_INPUT_DATA ); |
ansond | 0:137634ff4186 | 1703 | } |
ansond | 0:137634ff4186 | 1704 | |
ansond | 0:137634ff4186 | 1705 | #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS) |
ansond | 0:137634ff4186 | 1706 | /* |
ansond | 0:137634ff4186 | 1707 | * Check that an affine point is valid as a public key, |
ansond | 0:137634ff4186 | 1708 | * short weierstrass curves (SEC1 3.2.3.1) |
ansond | 0:137634ff4186 | 1709 | */ |
ansond | 0:137634ff4186 | 1710 | static int ecp_check_pubkey_sw( const ecp_group *grp, const ecp_point *pt ) |
ansond | 0:137634ff4186 | 1711 | { |
ansond | 0:137634ff4186 | 1712 | int ret; |
ansond | 0:137634ff4186 | 1713 | mpi YY, RHS; |
ansond | 0:137634ff4186 | 1714 | |
ansond | 0:137634ff4186 | 1715 | /* pt coordinates must be normalized for our checks */ |
ansond | 0:137634ff4186 | 1716 | if( mpi_cmp_int( &pt->X, 0 ) < 0 || |
ansond | 0:137634ff4186 | 1717 | mpi_cmp_int( &pt->Y, 0 ) < 0 || |
ansond | 0:137634ff4186 | 1718 | mpi_cmp_mpi( &pt->X, &grp->P ) >= 0 || |
ansond | 0:137634ff4186 | 1719 | mpi_cmp_mpi( &pt->Y, &grp->P ) >= 0 ) |
ansond | 0:137634ff4186 | 1720 | return( POLARSSL_ERR_ECP_INVALID_KEY ); |
ansond | 0:137634ff4186 | 1721 | |
ansond | 0:137634ff4186 | 1722 | mpi_init( &YY ); mpi_init( &RHS ); |
ansond | 0:137634ff4186 | 1723 | |
ansond | 0:137634ff4186 | 1724 | /* |
ansond | 0:137634ff4186 | 1725 | * YY = Y^2 |
ansond | 0:137634ff4186 | 1726 | * RHS = X (X^2 + A) + B = X^3 + A X + B |
ansond | 0:137634ff4186 | 1727 | */ |
ansond | 0:137634ff4186 | 1728 | MPI_CHK( mpi_mul_mpi( &YY, &pt->Y, &pt->Y ) ); MOD_MUL( YY ); |
ansond | 0:137634ff4186 | 1729 | MPI_CHK( mpi_mul_mpi( &RHS, &pt->X, &pt->X ) ); MOD_MUL( RHS ); |
ansond | 0:137634ff4186 | 1730 | |
ansond | 0:137634ff4186 | 1731 | /* Special case for A = -3 */ |
ansond | 0:137634ff4186 | 1732 | if( grp->A.p == NULL ) |
ansond | 0:137634ff4186 | 1733 | { |
ansond | 0:137634ff4186 | 1734 | MPI_CHK( mpi_sub_int( &RHS, &RHS, 3 ) ); MOD_SUB( RHS ); |
ansond | 0:137634ff4186 | 1735 | } |
ansond | 0:137634ff4186 | 1736 | else |
ansond | 0:137634ff4186 | 1737 | { |
ansond | 0:137634ff4186 | 1738 | MPI_CHK( mpi_add_mpi( &RHS, &RHS, &grp->A ) ); MOD_ADD( RHS ); |
ansond | 0:137634ff4186 | 1739 | } |
ansond | 0:137634ff4186 | 1740 | |
ansond | 0:137634ff4186 | 1741 | MPI_CHK( mpi_mul_mpi( &RHS, &RHS, &pt->X ) ); MOD_MUL( RHS ); |
ansond | 0:137634ff4186 | 1742 | MPI_CHK( mpi_add_mpi( &RHS, &RHS, &grp->B ) ); MOD_ADD( RHS ); |
ansond | 0:137634ff4186 | 1743 | |
ansond | 0:137634ff4186 | 1744 | if( mpi_cmp_mpi( &YY, &RHS ) != 0 ) |
ansond | 0:137634ff4186 | 1745 | ret = POLARSSL_ERR_ECP_INVALID_KEY; |
ansond | 0:137634ff4186 | 1746 | |
ansond | 0:137634ff4186 | 1747 | cleanup: |
ansond | 0:137634ff4186 | 1748 | |
ansond | 0:137634ff4186 | 1749 | mpi_free( &YY ); mpi_free( &RHS ); |
ansond | 0:137634ff4186 | 1750 | |
ansond | 0:137634ff4186 | 1751 | return( ret ); |
ansond | 0:137634ff4186 | 1752 | } |
ansond | 0:137634ff4186 | 1753 | #endif /* POLARSSL_ECP_SHORT_WEIERSTRASS */ |
ansond | 0:137634ff4186 | 1754 | |
ansond | 0:137634ff4186 | 1755 | |
ansond | 0:137634ff4186 | 1756 | #if defined(POLARSSL_ECP_MONTGOMERY) |
ansond | 0:137634ff4186 | 1757 | /* |
ansond | 0:137634ff4186 | 1758 | * Check validity of a public key for Montgomery curves with x-only schemes |
ansond | 0:137634ff4186 | 1759 | */ |
ansond | 0:137634ff4186 | 1760 | static int ecp_check_pubkey_mx( const ecp_group *grp, const ecp_point *pt ) |
ansond | 0:137634ff4186 | 1761 | { |
ansond | 0:137634ff4186 | 1762 | /* [M255 p. 5] Just check X is the correct number of bytes */ |
ansond | 0:137634ff4186 | 1763 | if( mpi_size( &pt->X ) > ( grp->nbits + 7 ) / 8 ) |
ansond | 0:137634ff4186 | 1764 | return( POLARSSL_ERR_ECP_INVALID_KEY ); |
ansond | 0:137634ff4186 | 1765 | |
ansond | 0:137634ff4186 | 1766 | return( 0 ); |
ansond | 0:137634ff4186 | 1767 | } |
ansond | 0:137634ff4186 | 1768 | #endif /* POLARSSL_ECP_MONTGOMERY */ |
ansond | 0:137634ff4186 | 1769 | |
ansond | 0:137634ff4186 | 1770 | /* |
ansond | 0:137634ff4186 | 1771 | * Check that a point is valid as a public key |
ansond | 0:137634ff4186 | 1772 | */ |
ansond | 0:137634ff4186 | 1773 | int ecp_check_pubkey( const ecp_group *grp, const ecp_point *pt ) |
ansond | 0:137634ff4186 | 1774 | { |
ansond | 0:137634ff4186 | 1775 | /* Must use affine coordinates */ |
ansond | 0:137634ff4186 | 1776 | if( mpi_cmp_int( &pt->Z, 1 ) != 0 ) |
ansond | 0:137634ff4186 | 1777 | return( POLARSSL_ERR_ECP_INVALID_KEY ); |
ansond | 0:137634ff4186 | 1778 | |
ansond | 0:137634ff4186 | 1779 | #if defined(POLARSSL_ECP_MONTGOMERY) |
ansond | 0:137634ff4186 | 1780 | if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_MONTGOMERY ) |
ansond | 0:137634ff4186 | 1781 | return( ecp_check_pubkey_mx( grp, pt ) ); |
ansond | 0:137634ff4186 | 1782 | #endif |
ansond | 0:137634ff4186 | 1783 | #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS) |
ansond | 0:137634ff4186 | 1784 | if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS ) |
ansond | 0:137634ff4186 | 1785 | return( ecp_check_pubkey_sw( grp, pt ) ); |
ansond | 0:137634ff4186 | 1786 | #endif |
ansond | 0:137634ff4186 | 1787 | return( POLARSSL_ERR_ECP_BAD_INPUT_DATA ); |
ansond | 0:137634ff4186 | 1788 | } |
ansond | 0:137634ff4186 | 1789 | |
ansond | 0:137634ff4186 | 1790 | /* |
ansond | 0:137634ff4186 | 1791 | * Check that an mpi is valid as a private key |
ansond | 0:137634ff4186 | 1792 | */ |
ansond | 0:137634ff4186 | 1793 | int ecp_check_privkey( const ecp_group *grp, const mpi *d ) |
ansond | 0:137634ff4186 | 1794 | { |
ansond | 0:137634ff4186 | 1795 | #if defined(POLARSSL_ECP_MONTGOMERY) |
ansond | 0:137634ff4186 | 1796 | if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_MONTGOMERY ) |
ansond | 0:137634ff4186 | 1797 | { |
ansond | 0:137634ff4186 | 1798 | /* see [M255] page 5 */ |
ansond | 0:137634ff4186 | 1799 | if( mpi_get_bit( d, 0 ) != 0 || |
ansond | 0:137634ff4186 | 1800 | mpi_get_bit( d, 1 ) != 0 || |
ansond | 0:137634ff4186 | 1801 | mpi_get_bit( d, 2 ) != 0 || |
ansond | 0:137634ff4186 | 1802 | mpi_msb( d ) - 1 != grp->nbits ) /* mpi_msb is one-based! */ |
ansond | 0:137634ff4186 | 1803 | return( POLARSSL_ERR_ECP_INVALID_KEY ); |
ansond | 0:137634ff4186 | 1804 | else |
ansond | 0:137634ff4186 | 1805 | return( 0 ); |
ansond | 0:137634ff4186 | 1806 | } |
ansond | 0:137634ff4186 | 1807 | #endif /* POLARSSL_ECP_MONTGOMERY */ |
ansond | 0:137634ff4186 | 1808 | #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS) |
ansond | 0:137634ff4186 | 1809 | if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS ) |
ansond | 0:137634ff4186 | 1810 | { |
ansond | 0:137634ff4186 | 1811 | /* see SEC1 3.2 */ |
ansond | 0:137634ff4186 | 1812 | if( mpi_cmp_int( d, 1 ) < 0 || |
ansond | 0:137634ff4186 | 1813 | mpi_cmp_mpi( d, &grp->N ) >= 0 ) |
ansond | 0:137634ff4186 | 1814 | return( POLARSSL_ERR_ECP_INVALID_KEY ); |
ansond | 0:137634ff4186 | 1815 | else |
ansond | 0:137634ff4186 | 1816 | return( 0 ); |
ansond | 0:137634ff4186 | 1817 | } |
ansond | 0:137634ff4186 | 1818 | #endif /* POLARSSL_ECP_SHORT_WEIERSTRASS */ |
ansond | 0:137634ff4186 | 1819 | |
ansond | 0:137634ff4186 | 1820 | return( POLARSSL_ERR_ECP_BAD_INPUT_DATA ); |
ansond | 0:137634ff4186 | 1821 | } |
ansond | 0:137634ff4186 | 1822 | |
ansond | 0:137634ff4186 | 1823 | /* |
ansond | 0:137634ff4186 | 1824 | * Generate a keypair |
ansond | 0:137634ff4186 | 1825 | */ |
ansond | 0:137634ff4186 | 1826 | int ecp_gen_keypair( ecp_group *grp, mpi *d, ecp_point *Q, |
ansond | 0:137634ff4186 | 1827 | int (*f_rng)(void *, unsigned char *, size_t), |
ansond | 0:137634ff4186 | 1828 | void *p_rng ) |
ansond | 0:137634ff4186 | 1829 | { |
ansond | 0:137634ff4186 | 1830 | int ret; |
ansond | 0:137634ff4186 | 1831 | size_t n_size = ( grp->nbits + 7 ) / 8; |
ansond | 0:137634ff4186 | 1832 | |
ansond | 0:137634ff4186 | 1833 | #if defined(POLARSSL_ECP_MONTGOMERY) |
ansond | 0:137634ff4186 | 1834 | if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_MONTGOMERY ) |
ansond | 0:137634ff4186 | 1835 | { |
ansond | 0:137634ff4186 | 1836 | /* [M225] page 5 */ |
ansond | 0:137634ff4186 | 1837 | size_t b; |
ansond | 0:137634ff4186 | 1838 | |
ansond | 0:137634ff4186 | 1839 | MPI_CHK( mpi_fill_random( d, n_size, f_rng, p_rng ) ); |
ansond | 0:137634ff4186 | 1840 | |
ansond | 0:137634ff4186 | 1841 | /* Make sure the most significant bit is nbits */ |
ansond | 0:137634ff4186 | 1842 | b = mpi_msb( d ) - 1; /* mpi_msb is one-based */ |
ansond | 0:137634ff4186 | 1843 | if( b > grp->nbits ) |
ansond | 0:137634ff4186 | 1844 | MPI_CHK( mpi_shift_r( d, b - grp->nbits ) ); |
ansond | 0:137634ff4186 | 1845 | else |
ansond | 0:137634ff4186 | 1846 | MPI_CHK( mpi_set_bit( d, grp->nbits, 1 ) ); |
ansond | 0:137634ff4186 | 1847 | |
ansond | 0:137634ff4186 | 1848 | /* Make sure the last three bits are unset */ |
ansond | 0:137634ff4186 | 1849 | MPI_CHK( mpi_set_bit( d, 0, 0 ) ); |
ansond | 0:137634ff4186 | 1850 | MPI_CHK( mpi_set_bit( d, 1, 0 ) ); |
ansond | 0:137634ff4186 | 1851 | MPI_CHK( mpi_set_bit( d, 2, 0 ) ); |
ansond | 0:137634ff4186 | 1852 | } |
ansond | 0:137634ff4186 | 1853 | else |
ansond | 0:137634ff4186 | 1854 | #endif /* POLARSSL_ECP_MONTGOMERY */ |
ansond | 0:137634ff4186 | 1855 | #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS) |
ansond | 0:137634ff4186 | 1856 | if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS ) |
ansond | 0:137634ff4186 | 1857 | { |
ansond | 0:137634ff4186 | 1858 | /* SEC1 3.2.1: Generate d such that 1 <= n < N */ |
ansond | 0:137634ff4186 | 1859 | int count = 0; |
ansond | 0:137634ff4186 | 1860 | unsigned char rnd[POLARSSL_ECP_MAX_BYTES]; |
ansond | 0:137634ff4186 | 1861 | |
ansond | 0:137634ff4186 | 1862 | /* |
ansond | 0:137634ff4186 | 1863 | * Match the procedure given in RFC 6979 (deterministic ECDSA): |
ansond | 0:137634ff4186 | 1864 | * - use the same byte ordering; |
ansond | 0:137634ff4186 | 1865 | * - keep the leftmost nbits bits of the generated octet string; |
ansond | 0:137634ff4186 | 1866 | * - try until result is in the desired range. |
ansond | 0:137634ff4186 | 1867 | * This also avoids any biais, which is especially important for ECDSA. |
ansond | 0:137634ff4186 | 1868 | */ |
ansond | 0:137634ff4186 | 1869 | do |
ansond | 0:137634ff4186 | 1870 | { |
ansond | 0:137634ff4186 | 1871 | MPI_CHK( f_rng( p_rng, rnd, n_size ) ); |
ansond | 0:137634ff4186 | 1872 | MPI_CHK( mpi_read_binary( d, rnd, n_size ) ); |
ansond | 0:137634ff4186 | 1873 | MPI_CHK( mpi_shift_r( d, 8 * n_size - grp->nbits ) ); |
ansond | 0:137634ff4186 | 1874 | |
ansond | 0:137634ff4186 | 1875 | /* |
ansond | 0:137634ff4186 | 1876 | * Each try has at worst a probability 1/2 of failing (the msb has |
ansond | 0:137634ff4186 | 1877 | * a probability 1/2 of being 0, and then the result will be < N), |
ansond | 0:137634ff4186 | 1878 | * so after 30 tries failure probability is a most 2**(-30). |
ansond | 0:137634ff4186 | 1879 | * |
ansond | 0:137634ff4186 | 1880 | * For most curves, 1 try is enough with overwhelming probability, |
ansond | 0:137634ff4186 | 1881 | * since N starts with a lot of 1s in binary, but some curves |
ansond | 0:137634ff4186 | 1882 | * such as secp224k1 are actually very close to the worst case. |
ansond | 0:137634ff4186 | 1883 | */ |
ansond | 0:137634ff4186 | 1884 | if( ++count > 30 ) |
ansond | 0:137634ff4186 | 1885 | return( POLARSSL_ERR_ECP_RANDOM_FAILED ); |
ansond | 0:137634ff4186 | 1886 | } |
ansond | 0:137634ff4186 | 1887 | while( mpi_cmp_int( d, 1 ) < 0 || |
ansond | 0:137634ff4186 | 1888 | mpi_cmp_mpi( d, &grp->N ) >= 0 ); |
ansond | 0:137634ff4186 | 1889 | } |
ansond | 0:137634ff4186 | 1890 | else |
ansond | 0:137634ff4186 | 1891 | #endif /* POLARSSL_ECP_SHORT_WEIERSTRASS */ |
ansond | 0:137634ff4186 | 1892 | return( POLARSSL_ERR_ECP_BAD_INPUT_DATA ); |
ansond | 0:137634ff4186 | 1893 | |
ansond | 0:137634ff4186 | 1894 | cleanup: |
ansond | 0:137634ff4186 | 1895 | if( ret != 0 ) |
ansond | 0:137634ff4186 | 1896 | return( ret ); |
ansond | 0:137634ff4186 | 1897 | |
ansond | 0:137634ff4186 | 1898 | return( ecp_mul( grp, Q, d, &grp->G, f_rng, p_rng ) ); |
ansond | 0:137634ff4186 | 1899 | } |
ansond | 0:137634ff4186 | 1900 | |
ansond | 0:137634ff4186 | 1901 | /* |
ansond | 0:137634ff4186 | 1902 | * Generate a keypair, prettier wrapper |
ansond | 0:137634ff4186 | 1903 | */ |
ansond | 0:137634ff4186 | 1904 | int ecp_gen_key( ecp_group_id grp_id, ecp_keypair *key, |
ansond | 0:137634ff4186 | 1905 | int (*f_rng)(void *, unsigned char *, size_t), void *p_rng ) |
ansond | 0:137634ff4186 | 1906 | { |
ansond | 0:137634ff4186 | 1907 | int ret; |
ansond | 0:137634ff4186 | 1908 | |
ansond | 0:137634ff4186 | 1909 | if( ( ret = ecp_use_known_dp( &key->grp, grp_id ) ) != 0 ) |
ansond | 0:137634ff4186 | 1910 | return( ret ); |
ansond | 0:137634ff4186 | 1911 | |
ansond | 0:137634ff4186 | 1912 | return( ecp_gen_keypair( &key->grp, &key->d, &key->Q, f_rng, p_rng ) ); |
ansond | 0:137634ff4186 | 1913 | } |
ansond | 0:137634ff4186 | 1914 | |
ansond | 0:137634ff4186 | 1915 | /* |
ansond | 0:137634ff4186 | 1916 | * Check a public-private key pair |
ansond | 0:137634ff4186 | 1917 | */ |
ansond | 0:137634ff4186 | 1918 | int ecp_check_pub_priv( const ecp_keypair *pub, const ecp_keypair *prv ) |
ansond | 0:137634ff4186 | 1919 | { |
ansond | 0:137634ff4186 | 1920 | int ret; |
ansond | 0:137634ff4186 | 1921 | ecp_point Q; |
ansond | 0:137634ff4186 | 1922 | ecp_group grp; |
ansond | 0:137634ff4186 | 1923 | |
ansond | 0:137634ff4186 | 1924 | if( pub->grp.id == POLARSSL_ECP_DP_NONE || |
ansond | 0:137634ff4186 | 1925 | pub->grp.id != prv->grp.id || |
ansond | 0:137634ff4186 | 1926 | mpi_cmp_mpi( &pub->Q.X, &prv->Q.X ) || |
ansond | 0:137634ff4186 | 1927 | mpi_cmp_mpi( &pub->Q.Y, &prv->Q.Y ) || |
ansond | 0:137634ff4186 | 1928 | mpi_cmp_mpi( &pub->Q.Z, &prv->Q.Z ) ) |
ansond | 0:137634ff4186 | 1929 | { |
ansond | 0:137634ff4186 | 1930 | return( POLARSSL_ERR_ECP_BAD_INPUT_DATA ); |
ansond | 0:137634ff4186 | 1931 | } |
ansond | 0:137634ff4186 | 1932 | |
ansond | 0:137634ff4186 | 1933 | ecp_point_init( &Q ); |
ansond | 0:137634ff4186 | 1934 | ecp_group_init( &grp ); |
ansond | 0:137634ff4186 | 1935 | |
ansond | 0:137634ff4186 | 1936 | /* ecp_mul() needs a non-const group... */ |
ansond | 0:137634ff4186 | 1937 | ecp_group_copy( &grp, &prv->grp ); |
ansond | 0:137634ff4186 | 1938 | |
ansond | 0:137634ff4186 | 1939 | /* Also checks d is valid */ |
ansond | 0:137634ff4186 | 1940 | MPI_CHK( ecp_mul( &grp, &Q, &prv->d, &prv->grp.G, NULL, NULL ) ); |
ansond | 0:137634ff4186 | 1941 | |
ansond | 0:137634ff4186 | 1942 | if( mpi_cmp_mpi( &Q.X, &prv->Q.X ) || |
ansond | 0:137634ff4186 | 1943 | mpi_cmp_mpi( &Q.Y, &prv->Q.Y ) || |
ansond | 0:137634ff4186 | 1944 | mpi_cmp_mpi( &Q.Z, &prv->Q.Z ) ) |
ansond | 0:137634ff4186 | 1945 | { |
ansond | 0:137634ff4186 | 1946 | ret = POLARSSL_ERR_ECP_BAD_INPUT_DATA; |
ansond | 0:137634ff4186 | 1947 | goto cleanup; |
ansond | 0:137634ff4186 | 1948 | } |
ansond | 0:137634ff4186 | 1949 | |
ansond | 0:137634ff4186 | 1950 | cleanup: |
ansond | 0:137634ff4186 | 1951 | ecp_point_free( &Q ); |
ansond | 0:137634ff4186 | 1952 | ecp_group_free( &grp ); |
ansond | 0:137634ff4186 | 1953 | |
ansond | 0:137634ff4186 | 1954 | return( ret ); |
ansond | 0:137634ff4186 | 1955 | } |
ansond | 0:137634ff4186 | 1956 | |
ansond | 0:137634ff4186 | 1957 | #if defined(POLARSSL_SELF_TEST) |
ansond | 0:137634ff4186 | 1958 | |
ansond | 0:137634ff4186 | 1959 | /* |
ansond | 0:137634ff4186 | 1960 | * Checkup routine |
ansond | 0:137634ff4186 | 1961 | */ |
ansond | 0:137634ff4186 | 1962 | int ecp_self_test( int verbose ) |
ansond | 0:137634ff4186 | 1963 | { |
ansond | 0:137634ff4186 | 1964 | int ret; |
ansond | 0:137634ff4186 | 1965 | size_t i; |
ansond | 0:137634ff4186 | 1966 | ecp_group grp; |
ansond | 0:137634ff4186 | 1967 | ecp_point R, P; |
ansond | 0:137634ff4186 | 1968 | mpi m; |
ansond | 0:137634ff4186 | 1969 | unsigned long add_c_prev, dbl_c_prev, mul_c_prev; |
ansond | 0:137634ff4186 | 1970 | /* exponents especially adapted for secp192r1 */ |
ansond | 0:137634ff4186 | 1971 | const char *exponents[] = |
ansond | 0:137634ff4186 | 1972 | { |
ansond | 0:137634ff4186 | 1973 | "000000000000000000000000000000000000000000000001", /* one */ |
ansond | 0:137634ff4186 | 1974 | "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22830", /* N - 1 */ |
ansond | 0:137634ff4186 | 1975 | "5EA6F389A38B8BC81E767753B15AA5569E1782E30ABE7D25", /* random */ |
ansond | 0:137634ff4186 | 1976 | "400000000000000000000000000000000000000000000000", /* one and zeros */ |
ansond | 0:137634ff4186 | 1977 | "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", /* all ones */ |
ansond | 0:137634ff4186 | 1978 | "555555555555555555555555555555555555555555555555", /* 101010... */ |
ansond | 0:137634ff4186 | 1979 | }; |
ansond | 0:137634ff4186 | 1980 | |
ansond | 0:137634ff4186 | 1981 | ecp_group_init( &grp ); |
ansond | 0:137634ff4186 | 1982 | ecp_point_init( &R ); |
ansond | 0:137634ff4186 | 1983 | ecp_point_init( &P ); |
ansond | 0:137634ff4186 | 1984 | mpi_init( &m ); |
ansond | 0:137634ff4186 | 1985 | |
ansond | 0:137634ff4186 | 1986 | /* Use secp192r1 if available, or any available curve */ |
ansond | 0:137634ff4186 | 1987 | #if defined(POLARSSL_ECP_DP_SECP192R1_ENABLED) |
ansond | 0:137634ff4186 | 1988 | MPI_CHK( ecp_use_known_dp( &grp, POLARSSL_ECP_DP_SECP192R1 ) ); |
ansond | 0:137634ff4186 | 1989 | #else |
ansond | 0:137634ff4186 | 1990 | MPI_CHK( ecp_use_known_dp( &grp, ecp_curve_list()->grp_id ) ); |
ansond | 0:137634ff4186 | 1991 | #endif |
ansond | 0:137634ff4186 | 1992 | |
ansond | 0:137634ff4186 | 1993 | if( verbose != 0 ) |
ansond | 0:137634ff4186 | 1994 | polarssl_printf( " ECP test #1 (constant op_count, base point G): " ); |
ansond | 0:137634ff4186 | 1995 | |
ansond | 0:137634ff4186 | 1996 | /* Do a dummy multiplication first to trigger precomputation */ |
ansond | 0:137634ff4186 | 1997 | MPI_CHK( mpi_lset( &m, 2 ) ); |
ansond | 0:137634ff4186 | 1998 | MPI_CHK( ecp_mul( &grp, &P, &m, &grp.G, NULL, NULL ) ); |
ansond | 0:137634ff4186 | 1999 | |
ansond | 0:137634ff4186 | 2000 | add_count = 0; |
ansond | 0:137634ff4186 | 2001 | dbl_count = 0; |
ansond | 0:137634ff4186 | 2002 | mul_count = 0; |
ansond | 0:137634ff4186 | 2003 | MPI_CHK( mpi_read_string( &m, 16, exponents[0] ) ); |
ansond | 0:137634ff4186 | 2004 | MPI_CHK( ecp_mul( &grp, &R, &m, &grp.G, NULL, NULL ) ); |
ansond | 0:137634ff4186 | 2005 | |
ansond | 0:137634ff4186 | 2006 | for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ ) |
ansond | 0:137634ff4186 | 2007 | { |
ansond | 0:137634ff4186 | 2008 | add_c_prev = add_count; |
ansond | 0:137634ff4186 | 2009 | dbl_c_prev = dbl_count; |
ansond | 0:137634ff4186 | 2010 | mul_c_prev = mul_count; |
ansond | 0:137634ff4186 | 2011 | add_count = 0; |
ansond | 0:137634ff4186 | 2012 | dbl_count = 0; |
ansond | 0:137634ff4186 | 2013 | mul_count = 0; |
ansond | 0:137634ff4186 | 2014 | |
ansond | 0:137634ff4186 | 2015 | MPI_CHK( mpi_read_string( &m, 16, exponents[i] ) ); |
ansond | 0:137634ff4186 | 2016 | MPI_CHK( ecp_mul( &grp, &R, &m, &grp.G, NULL, NULL ) ); |
ansond | 0:137634ff4186 | 2017 | |
ansond | 0:137634ff4186 | 2018 | if( add_count != add_c_prev || |
ansond | 0:137634ff4186 | 2019 | dbl_count != dbl_c_prev || |
ansond | 0:137634ff4186 | 2020 | mul_count != mul_c_prev ) |
ansond | 0:137634ff4186 | 2021 | { |
ansond | 0:137634ff4186 | 2022 | if( verbose != 0 ) |
ansond | 0:137634ff4186 | 2023 | polarssl_printf( "failed (%u)\n", (unsigned int) i ); |
ansond | 0:137634ff4186 | 2024 | |
ansond | 0:137634ff4186 | 2025 | ret = 1; |
ansond | 0:137634ff4186 | 2026 | goto cleanup; |
ansond | 0:137634ff4186 | 2027 | } |
ansond | 0:137634ff4186 | 2028 | } |
ansond | 0:137634ff4186 | 2029 | |
ansond | 0:137634ff4186 | 2030 | if( verbose != 0 ) |
ansond | 0:137634ff4186 | 2031 | polarssl_printf( "passed\n" ); |
ansond | 0:137634ff4186 | 2032 | |
ansond | 0:137634ff4186 | 2033 | if( verbose != 0 ) |
ansond | 0:137634ff4186 | 2034 | polarssl_printf( " ECP test #2 (constant op_count, other point): " ); |
ansond | 0:137634ff4186 | 2035 | /* We computed P = 2G last time, use it */ |
ansond | 0:137634ff4186 | 2036 | |
ansond | 0:137634ff4186 | 2037 | add_count = 0; |
ansond | 0:137634ff4186 | 2038 | dbl_count = 0; |
ansond | 0:137634ff4186 | 2039 | mul_count = 0; |
ansond | 0:137634ff4186 | 2040 | MPI_CHK( mpi_read_string( &m, 16, exponents[0] ) ); |
ansond | 0:137634ff4186 | 2041 | MPI_CHK( ecp_mul( &grp, &R, &m, &P, NULL, NULL ) ); |
ansond | 0:137634ff4186 | 2042 | |
ansond | 0:137634ff4186 | 2043 | for( i = 1; i < sizeof( exponents ) / sizeof( exponents[0] ); i++ ) |
ansond | 0:137634ff4186 | 2044 | { |
ansond | 0:137634ff4186 | 2045 | add_c_prev = add_count; |
ansond | 0:137634ff4186 | 2046 | dbl_c_prev = dbl_count; |
ansond | 0:137634ff4186 | 2047 | mul_c_prev = mul_count; |
ansond | 0:137634ff4186 | 2048 | add_count = 0; |
ansond | 0:137634ff4186 | 2049 | dbl_count = 0; |
ansond | 0:137634ff4186 | 2050 | mul_count = 0; |
ansond | 0:137634ff4186 | 2051 | |
ansond | 0:137634ff4186 | 2052 | MPI_CHK( mpi_read_string( &m, 16, exponents[i] ) ); |
ansond | 0:137634ff4186 | 2053 | MPI_CHK( ecp_mul( &grp, &R, &m, &P, NULL, NULL ) ); |
ansond | 0:137634ff4186 | 2054 | |
ansond | 0:137634ff4186 | 2055 | if( add_count != add_c_prev || |
ansond | 0:137634ff4186 | 2056 | dbl_count != dbl_c_prev || |
ansond | 0:137634ff4186 | 2057 | mul_count != mul_c_prev ) |
ansond | 0:137634ff4186 | 2058 | { |
ansond | 0:137634ff4186 | 2059 | if( verbose != 0 ) |
ansond | 0:137634ff4186 | 2060 | polarssl_printf( "failed (%u)\n", (unsigned int) i ); |
ansond | 0:137634ff4186 | 2061 | |
ansond | 0:137634ff4186 | 2062 | ret = 1; |
ansond | 0:137634ff4186 | 2063 | goto cleanup; |
ansond | 0:137634ff4186 | 2064 | } |
ansond | 0:137634ff4186 | 2065 | } |
ansond | 0:137634ff4186 | 2066 | |
ansond | 0:137634ff4186 | 2067 | if( verbose != 0 ) |
ansond | 0:137634ff4186 | 2068 | polarssl_printf( "passed\n" ); |
ansond | 0:137634ff4186 | 2069 | |
ansond | 0:137634ff4186 | 2070 | cleanup: |
ansond | 0:137634ff4186 | 2071 | |
ansond | 0:137634ff4186 | 2072 | if( ret < 0 && verbose != 0 ) |
ansond | 0:137634ff4186 | 2073 | polarssl_printf( "Unexpected error, return code = %08X\n", ret ); |
ansond | 0:137634ff4186 | 2074 | |
ansond | 0:137634ff4186 | 2075 | ecp_group_free( &grp ); |
ansond | 0:137634ff4186 | 2076 | ecp_point_free( &R ); |
ansond | 0:137634ff4186 | 2077 | ecp_point_free( &P ); |
ansond | 0:137634ff4186 | 2078 | mpi_free( &m ); |
ansond | 0:137634ff4186 | 2079 | |
ansond | 0:137634ff4186 | 2080 | if( verbose != 0 ) |
ansond | 0:137634ff4186 | 2081 | polarssl_printf( "\n" ); |
ansond | 0:137634ff4186 | 2082 | |
ansond | 0:137634ff4186 | 2083 | return( ret ); |
ansond | 0:137634ff4186 | 2084 | } |
ansond | 0:137634ff4186 | 2085 | |
ansond | 0:137634ff4186 | 2086 | #endif /* POLARSSL_SELF_TEST */ |
ansond | 0:137634ff4186 | 2087 | |
ansond | 0:137634ff4186 | 2088 | #endif /* POLARSSL_ECP_C */ |
ansond | 0:137634ff4186 | 2089 |