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