47 #if !defined(POLARSSL_CONFIG_FILE)
50 #include POLARSSL_CONFIG_FILE
53 #if defined(POLARSSL_ECP_C)
57 #if defined(POLARSSL_PLATFORM_C)
60 #define polarssl_printf printf
61 #define polarssl_malloc malloc
62 #define polarssl_free free
67 #if defined(_MSC_VER) && !defined strcasecmp && !defined(EFIX64) && \
69 #define strcasecmp _stricmp
72 #if defined(_MSC_VER) && !defined(inline)
73 #define inline _inline
75 #if defined(__ARMCC_VERSION) && !defined(inline)
76 #define inline __inline
81 static void polarssl_zeroize(
void *v,
size_t n ) {
82 volatile unsigned char *p = v;
while( n-- ) *p++ = 0;
85 #if defined(POLARSSL_SELF_TEST)
90 static unsigned long add_count, dbl_count, mul_count;
93 #if defined(POLARSSL_ECP_DP_SECP192R1_ENABLED) || \
94 defined(POLARSSL_ECP_DP_SECP224R1_ENABLED) || \
95 defined(POLARSSL_ECP_DP_SECP256R1_ENABLED) || \
96 defined(POLARSSL_ECP_DP_SECP384R1_ENABLED) || \
97 defined(POLARSSL_ECP_DP_SECP521R1_ENABLED) || \
98 defined(POLARSSL_ECP_DP_BP256R1_ENABLED) || \
99 defined(POLARSSL_ECP_DP_BP384R1_ENABLED) || \
100 defined(POLARSSL_ECP_DP_BP512R1_ENABLED) || \
101 defined(POLARSSL_ECP_DP_SECP192K1_ENABLED) || \
102 defined(POLARSSL_ECP_DP_SECP224K1_ENABLED) || \
103 defined(POLARSSL_ECP_DP_SECP256K1_ENABLED)
104 #define POLARSSL_ECP_SHORT_WEIERSTRASS
107 #if defined(POLARSSL_ECP_DP_M221_ENABLED) || \
108 defined(POLARSSL_ECP_DP_M255_ENABLED) || \
109 defined(POLARSSL_ECP_DP_M383_ENABLED) || \
110 defined(POLARSSL_ECP_DP_M511_ENABLED)
111 #define POLARSSL_ECP_MONTGOMERY
119 POLARSSL_ECP_TYPE_NONE = 0,
120 POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS,
121 POLARSSL_ECP_TYPE_MONTGOMERY,
136 #if defined(POLARSSL_ECP_DP_SECP521R1_ENABLED)
139 #if defined(POLARSSL_ECP_DP_BP512R1_ENABLED)
142 #if defined(POLARSSL_ECP_DP_SECP384R1_ENABLED)
145 #if defined(POLARSSL_ECP_DP_BP384R1_ENABLED)
148 #if defined(POLARSSL_ECP_DP_SECP256R1_ENABLED)
151 #if defined(POLARSSL_ECP_DP_SECP256K1_ENABLED)
154 #if defined(POLARSSL_ECP_DP_BP256R1_ENABLED)
157 #if defined(POLARSSL_ECP_DP_SECP224R1_ENABLED)
160 #if defined(POLARSSL_ECP_DP_SECP224K1_ENABLED)
163 #if defined(POLARSSL_ECP_DP_SECP192R1_ENABLED)
166 #if defined(POLARSSL_ECP_DP_SECP192K1_ENABLED)
172 #define ECP_NB_CURVES sizeof( ecp_supported_curves ) / \
173 sizeof( ecp_supported_curves[0] )
175 static ecp_group_id ecp_supported_grp_id[ECP_NB_CURVES];
182 return( ecp_supported_curves );
190 static int init_done = 0;
201 ecp_supported_grp_id[i++] = curve_info->
grp_id;
208 return( ecp_supported_grp_id );
222 if( curve_info->
grp_id == grp_id )
223 return( curve_info );
240 if( curve_info->
tls_id == tls_id )
241 return( curve_info );
258 if( strcasecmp( curve_info->
name, name ) == 0 )
259 return( curve_info );
268 static inline ecp_curve_type ecp_get_type(
const ecp_group *grp )
270 if( grp->
G.
X.
p == NULL )
271 return( POLARSSL_ECP_TYPE_NONE );
273 if( grp->
G.
Y.
p == NULL )
274 return( POLARSSL_ECP_TYPE_MONTGOMERY );
276 return( POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS );
350 for( i = 0; i < grp->
T_size; i++ )
355 polarssl_zeroize( grp,
sizeof(
ecp_group ) );
421 const char *x,
const char *y )
437 int format,
size_t *olen,
438 unsigned char *buf,
size_t buflen )
465 *olen = 2 * plen + 1;
493 const unsigned char *buf,
size_t ilen )
514 if( ilen != 2 * plen + 1 )
532 const unsigned char **buf,
size_t buf_len )
534 unsigned char data_len;
535 const unsigned char *buf_start;
543 data_len = *(*buf)++;
544 if( data_len < 1 || data_len > buf_len - 1 )
563 int format,
size_t *olen,
564 unsigned char *buf,
size_t blen )
575 olen, buf + 1, blen - 1) ) != 0 )
581 buf[0] = (
unsigned char) *olen;
591 const char *p,
const char *b,
592 const char *gx,
const char *gy,
const char *n)
648 unsigned char *buf,
size_t blen )
670 buf[0] = curve_info->
tls_id >> 8;
671 buf[1] = curve_info->
tls_id & 0xFF;
686 if( grp->
modp == NULL )
723 #if defined(POLARSSL_SELF_TEST)
724 #define INC_MUL_COUNT mul_count++;
726 #define INC_MUL_COUNT
729 #define MOD_MUL( N ) do { MPI_CHK( ecp_modp( &N, grp ) ); INC_MUL_COUNT } \
736 #define MOD_SUB( N ) \
737 while( N.s < 0 && mpi_cmp_int( &N, 0 ) != 0 ) \
738 MPI_CHK( mpi_add_mpi( &N, &N, &grp->P ) )
745 #define MOD_ADD( N ) \
746 while( mpi_cmp_mpi( &N, &grp->P ) >= 0 ) \
747 MPI_CHK( mpi_sub_abs( &N, &N, &grp->P ) )
749 #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
808 static int ecp_normalize_jac_many(
const ecp_group *grp,
816 return( ecp_normalize_jac( grp, *T ) );
822 for( i = 0; i < t_len; i++ )
829 for( i = 1; i < t_len; i++ )
840 for( i = t_len - 1; ; i-- )
880 for( i = 0; i < t_len; i++ )
891 static int ecp_safe_invert_jac(
const ecp_group *grp,
896 unsigned char nonzero;
926 mpi T1, T2, T3, X3, Y3, Z3;
928 #if defined(POLARSSL_SELF_TEST)
948 if( grp->
A.
p == NULL )
1003 mpi T1, T2, T3, T4, X, Y, Z;
1005 #if defined(POLARSSL_SELF_TEST)
1039 ret = ecp_double_jac( grp, R, P );
1082 if( ecp_get_type( grp ) != POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
1085 MPI_CHK( ecp_add_mixed( grp, R, P, Q ) );
1086 MPI_CHK( ecp_normalize_jac( grp, R ) );
1103 if( ecp_get_type( grp ) != POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
1111 MPI_CHK( ecp_add_mixed( grp, R, P, &mQ ) );
1112 MPI_CHK( ecp_normalize_jac( grp, R ) );
1128 int (*f_rng)(
void *,
unsigned char *,
size_t),
void *p_rng )
1132 size_t p_size = ( grp->
pbits + 7 ) / 8;
1170 #if POLARSSL_ECP_WINDOW_SIZE < 2 || POLARSSL_ECP_WINDOW_SIZE > 7
1171 #error "POLARSSL_ECP_WINDOW_SIZE out of bounds"
1175 #define COMB_MAX_D ( POLARSSL_ECP_MAX_BITS + 1 ) / 2
1178 #define COMB_MAX_PRE ( 1 << ( POLARSSL_ECP_WINDOW_SIZE - 1 ) )
1200 static void ecp_comb_fixed(
unsigned char x[],
size_t d,
1201 unsigned char w,
const mpi *m )
1204 unsigned char c, cc, adjust;
1206 memset( x, 0, d+1 );
1209 for( i = 0; i < d; i++ )
1210 for( j = 0; j < w; j++ )
1215 for( i = 1; i <= d; i++ )
1223 adjust = 1 - ( x[i] & 0x01 );
1224 c |= x[i] & ( x[i-1] * adjust );
1225 x[i] = x[i] ^ ( x[i-1] * adjust );
1226 x[i-1] |= adjust << 7;
1240 static int ecp_precompute_comb(
const ecp_group *grp,
1242 unsigned char w,
size_t d )
1256 for( i = 1; i < ( 1U << ( w - 1 ) ); i <<= 1 )
1260 for( j = 0; j < d; j++ )
1261 MPI_CHK( ecp_double_jac( grp, cur, cur ) );
1266 MPI_CHK( ecp_normalize_jac_many( grp, TT, k ) );
1273 for( i = 1; i < ( 1U << ( w - 1 ) ); i <<= 1 )
1278 MPI_CHK( ecp_add_mixed( grp, &T[i + j], &T[j], &T[i] ) );
1279 TT[k++] = &T[i + j];
1283 MPI_CHK( ecp_normalize_jac_many( grp, TT, k ) );
1293 const ecp_point T[],
unsigned char t_len,
1297 unsigned char ii, j;
1300 ii = ( i & 0x7Fu ) >> 1;
1303 for( j = 0; j < t_len; j++ )
1310 MPI_CHK( ecp_safe_invert_jac( grp, R, i >> 7 ) );
1323 const ecp_point T[],
unsigned char t_len,
1324 const unsigned char x[],
size_t d,
1325 int (*f_rng)(
void *,
unsigned char *,
size_t),
1336 MPI_CHK( ecp_select_comb( grp, R, T, t_len, x[i] ) );
1339 MPI_CHK( ecp_randomize_jac( grp, R, f_rng, p_rng ) );
1343 MPI_CHK( ecp_double_jac( grp, R, R ) );
1344 MPI_CHK( ecp_select_comb( grp, &Txi, T, t_len, x[i] ) );
1345 MPI_CHK( ecp_add_mixed( grp, R, R, &Txi ) );
1360 int (*f_rng)(
void *,
unsigned char *,
size_t),
1364 unsigned char w, m_is_odd, p_eq_g, pre_len, i;
1366 unsigned char k[COMB_MAX_D + 1];
1382 w = grp->
nbits >= 384 ? 5 : 4;
1389 #if POLARSSL_ECP_FIXED_POINT_OPTIM == 1
1404 if( w >= grp->
nbits )
1408 pre_len = 1U << ( w - 1 );
1409 d = ( grp->
nbits + w - 1 ) / w;
1415 T = p_eq_g ? grp->
T : NULL;
1426 for( i = 0; i < pre_len; i++ )
1429 MPI_CHK( ecp_precompute_comb( grp, T, P, w, d ) );
1450 ecp_comb_fixed( k, d, w, &M );
1451 MPI_CHK( ecp_mul_comb_core( grp, R, T, pre_len, k, d, f_rng, p_rng ) );
1456 MPI_CHK( ecp_safe_invert_jac( grp, R, ! m_is_odd ) );
1457 MPI_CHK( ecp_normalize_jac( grp, R ) );
1461 if( T != NULL && ! p_eq_g )
1463 for( i = 0; i < pre_len; i++ )
1479 #if defined(POLARSSL_ECP_MONTGOMERY)
1513 int (*f_rng)(
void *,
unsigned char *,
size_t),
void *p_rng )
1517 size_t p_size = ( grp->
pbits + 7 ) / 8;
1559 static int ecp_double_add_mxz(
const ecp_group *grp,
1565 mpi A, AA, B, BB, E, C, D, DA, CB;
1604 int (*f_rng)(
void *,
unsigned char *,
size_t),
1629 MPI_CHK( ecp_randomize_mxz( grp, &RP, f_rng, p_rng ) );
1645 MPI_CHK( ecp_double_add_mxz( grp, R, &RP, R, &RP, &PX ) );
1650 MPI_CHK( ecp_normalize_mxz( grp, R ) );
1665 int (*f_rng)(
void *,
unsigned char *,
size_t),
void *p_rng )
1677 #if defined(POLARSSL_ECP_MONTGOMERY)
1678 if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_MONTGOMERY )
1679 return( ecp_mul_mxz( grp, R, m, P, f_rng, p_rng ) );
1681 #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
1682 if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
1683 return( ecp_mul_comb( grp, R, m, P, f_rng, p_rng ) );
1688 #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
1715 if( grp->
A.
p == NULL )
1739 #if defined(POLARSSL_ECP_MONTGOMERY)
1762 #if defined(POLARSSL_ECP_MONTGOMERY)
1763 if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_MONTGOMERY )
1764 return( ecp_check_pubkey_mx( grp, pt ) );
1766 #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
1767 if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
1768 return( ecp_check_pubkey_sw( grp, pt ) );
1778 #if defined(POLARSSL_ECP_MONTGOMERY)
1779 if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_MONTGOMERY )
1791 #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
1792 if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
1810 int (*f_rng)(
void *,
unsigned char *,
size_t),
1814 size_t n_size = ( grp->
nbits + 7 ) / 8;
1816 #if defined(POLARSSL_ECP_MONTGOMERY)
1817 if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_MONTGOMERY )
1826 if( b > grp->
nbits )
1838 #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
1839 if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
1854 MPI_CHK( f_rng( p_rng, rnd, n_size ) );
1881 return(
ecp_mul( grp, Q, d, &grp->
G, f_rng, p_rng ) );
1888 int (*f_rng)(
void *,
unsigned char *,
size_t),
void *p_rng )
1898 #if defined(POLARSSL_SELF_TEST)
1910 unsigned long add_c_prev, dbl_c_prev, mul_c_prev;
1912 const char *exponents[] =
1914 "000000000000000000000000000000000000000000000001",
1915 "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22830",
1916 "5EA6F389A38B8BC81E767753B15AA5569E1782E30ABE7D25",
1917 "400000000000000000000000000000000000000000000000",
1918 "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
1919 "555555555555555555555555555555555555555555555555",
1928 #if defined(POLARSSL_ECP_DP_SECP192R1_ENABLED)
1935 polarssl_printf(
" ECP test #1 (constant op_count, base point G): " );
1947 for( i = 1; i <
sizeof( exponents ) /
sizeof( exponents[0] ); i++ )
1949 add_c_prev = add_count;
1950 dbl_c_prev = dbl_count;
1951 mul_c_prev = mul_count;
1959 if( add_count != add_c_prev ||
1960 dbl_count != dbl_c_prev ||
1961 mul_count != mul_c_prev )
1984 for( i = 1; i <
sizeof( exponents ) /
sizeof( exponents[0] ); i++ )
1986 add_c_prev = add_count;
1987 dbl_c_prev = dbl_count;
1988 mul_c_prev = mul_count;
1996 if( add_count != add_c_prev ||
1997 dbl_count != dbl_c_prev ||
1998 mul_count != mul_c_prev )
2013 if( ret < 0 && verbose != 0 )