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
80 #if defined(POLARSSL_SELF_TEST)
85 static unsigned long add_count, dbl_count, mul_count;
88 #if defined(POLARSSL_ECP_DP_SECP192R1_ENABLED) || \
89 defined(POLARSSL_ECP_DP_SECP224R1_ENABLED) || \
90 defined(POLARSSL_ECP_DP_SECP256R1_ENABLED) || \
91 defined(POLARSSL_ECP_DP_SECP384R1_ENABLED) || \
92 defined(POLARSSL_ECP_DP_SECP521R1_ENABLED) || \
93 defined(POLARSSL_ECP_DP_BP256R1_ENABLED) || \
94 defined(POLARSSL_ECP_DP_BP384R1_ENABLED) || \
95 defined(POLARSSL_ECP_DP_BP512R1_ENABLED) || \
96 defined(POLARSSL_ECP_DP_SECP192K1_ENABLED) || \
97 defined(POLARSSL_ECP_DP_SECP224K1_ENABLED) || \
98 defined(POLARSSL_ECP_DP_SECP256K1_ENABLED)
99 #define POLARSSL_ECP_SHORT_WEIERSTRASS
102 #if defined(POLARSSL_ECP_DP_M221_ENABLED) || \
103 defined(POLARSSL_ECP_DP_M255_ENABLED) || \
104 defined(POLARSSL_ECP_DP_M383_ENABLED) || \
105 defined(POLARSSL_ECP_DP_M511_ENABLED)
106 #define POLARSSL_ECP_MONTGOMERY
114 POLARSSL_ECP_TYPE_NONE = 0,
115 POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS,
116 POLARSSL_ECP_TYPE_MONTGOMERY,
131 #if defined(POLARSSL_ECP_DP_SECP521R1_ENABLED)
134 #if defined(POLARSSL_ECP_DP_BP512R1_ENABLED)
137 #if defined(POLARSSL_ECP_DP_SECP384R1_ENABLED)
140 #if defined(POLARSSL_ECP_DP_BP384R1_ENABLED)
143 #if defined(POLARSSL_ECP_DP_SECP256R1_ENABLED)
146 #if defined(POLARSSL_ECP_DP_SECP256K1_ENABLED)
149 #if defined(POLARSSL_ECP_DP_BP256R1_ENABLED)
152 #if defined(POLARSSL_ECP_DP_SECP224R1_ENABLED)
155 #if defined(POLARSSL_ECP_DP_SECP224K1_ENABLED)
158 #if defined(POLARSSL_ECP_DP_SECP192R1_ENABLED)
161 #if defined(POLARSSL_ECP_DP_SECP192K1_ENABLED)
174 return ecp_supported_curves;
182 static int init_done = 0;
193 ecp_supported_grp_id[i++] = curve_info->
grp_id;
200 return ecp_supported_grp_id;
214 if( curve_info->
grp_id == grp_id )
215 return( curve_info );
232 if( curve_info->
tls_id == tls_id )
233 return( curve_info );
250 if( strcasecmp( curve_info->
name, name ) == 0 )
251 return( curve_info );
260 static inline ecp_curve_type ecp_get_type(
const ecp_group *grp )
262 if( grp->
G.
X.
p == NULL )
263 return( POLARSSL_ECP_TYPE_NONE );
265 if( grp->
G.
Y.
p == NULL )
266 return( POLARSSL_ECP_TYPE_MONTGOMERY );
268 return( POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS );
342 for( i = 0; i < grp->
T_size; i++ )
413 const char *x,
const char *y )
429 int format,
size_t *olen,
430 unsigned char *buf,
size_t buflen )
457 *olen = 2 * plen + 1;
485 const unsigned char *buf,
size_t ilen )
503 if( ilen != 2 * plen + 1 )
521 const unsigned char **buf,
size_t buf_len )
523 unsigned char data_len;
524 const unsigned char *buf_start;
532 data_len = *(*buf)++;
533 if( data_len < 1 || data_len > buf_len - 1 )
552 int format,
size_t *olen,
553 unsigned char *buf,
size_t blen )
564 olen, buf + 1, blen - 1) ) != 0 )
570 buf[0] = (
unsigned char) *olen;
580 const char *p,
const char *b,
581 const char *gx,
const char *gy,
const char *n)
637 unsigned char *buf,
size_t blen )
659 buf[0] = curve_info->
tls_id >> 8;
660 buf[1] = curve_info->
tls_id & 0xFF;
675 if( grp->
modp == NULL )
712 #if defined(POLARSSL_SELF_TEST)
713 #define INC_MUL_COUNT mul_count++;
715 #define INC_MUL_COUNT
718 #define MOD_MUL( N ) do { MPI_CHK( ecp_modp( &N, grp ) ); INC_MUL_COUNT } \
725 #define MOD_SUB( N ) \
726 while( N.s < 0 && mpi_cmp_int( &N, 0 ) != 0 ) \
727 MPI_CHK( mpi_add_mpi( &N, &N, &grp->P ) )
734 #define MOD_ADD( N ) \
735 while( mpi_cmp_mpi( &N, &grp->P ) >= 0 ) \
736 MPI_CHK( mpi_sub_abs( &N, &N, &grp->P ) )
738 #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
797 static int ecp_normalize_jac_many(
const ecp_group *grp,
805 return( ecp_normalize_jac( grp, *T ) );
811 for( i = 0; i < t_len; i++ )
818 for( i = 1; i < t_len; i++ )
829 for( i = t_len - 1; ; i-- )
869 for( i = 0; i < t_len; i++ )
880 static int ecp_safe_invert_jac(
const ecp_group *grp,
885 unsigned char nonzero;
915 mpi T1, T2, T3, X3, Y3, Z3;
917 #if defined(POLARSSL_SELF_TEST)
937 if( grp->
A.
p == NULL )
992 mpi T1, T2, T3, T4, X, Y, Z;
994 #if defined(POLARSSL_SELF_TEST)
1028 ret = ecp_double_jac( grp, R, P );
1071 if( ecp_get_type( grp ) != POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
1074 MPI_CHK( ecp_add_mixed( grp, R, P, Q ) );
1075 MPI_CHK( ecp_normalize_jac( grp, R ) );
1092 if( ecp_get_type( grp ) != POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
1100 MPI_CHK( ecp_add_mixed( grp, R, P, &mQ ) );
1101 MPI_CHK( ecp_normalize_jac( grp, R ) );
1117 int (*f_rng)(
void *,
unsigned char *,
size_t),
void *p_rng )
1121 size_t p_size = (grp->
pbits + 7) / 8;
1159 #if POLARSSL_ECP_WINDOW_SIZE < 2 || POLARSSL_ECP_WINDOW_SIZE > 7
1160 #error "POLARSSL_ECP_WINDOW_SIZE out of bounds"
1164 #define COMB_MAX_D ( POLARSSL_ECP_MAX_BITS + 1 ) / 2
1167 #define COMB_MAX_PRE ( 1 << ( POLARSSL_ECP_WINDOW_SIZE - 1 ) )
1189 static void ecp_comb_fixed(
unsigned char x[],
size_t d,
1190 unsigned char w,
const mpi *m )
1193 unsigned char c, cc, adjust;
1195 memset( x, 0, d+1 );
1198 for( i = 0; i < d; i++ )
1199 for( j = 0; j < w; j++ )
1204 for( i = 1; i <= d; i++ )
1212 adjust = 1 - ( x[i] & 0x01 );
1213 c |= x[i] & ( x[i-1] * adjust );
1214 x[i] = x[i] ^ ( x[i-1] * adjust );
1215 x[i-1] |= adjust << 7;
1229 static int ecp_precompute_comb(
const ecp_group *grp,
1231 unsigned char w,
size_t d )
1245 for( i = 1; i < ( 1U << (w-1) ); i <<= 1 )
1249 for( j = 0; j < d; j++ )
1250 MPI_CHK( ecp_double_jac( grp, cur, cur ) );
1255 MPI_CHK( ecp_normalize_jac_many( grp, TT, k ) );
1262 for( i = 1; i < ( 1U << (w-1) ); i <<= 1 )
1267 MPI_CHK( ecp_add_mixed( grp, &T[i + j], &T[j], &T[i] ) );
1268 TT[k++] = &T[i + j];
1272 MPI_CHK( ecp_normalize_jac_many( grp, TT, k ) );
1282 const ecp_point T[],
unsigned char t_len,
1286 unsigned char ii, j;
1289 ii = ( i & 0x7Fu ) >> 1;
1292 for( j = 0; j < t_len; j++ )
1299 MPI_CHK( ecp_safe_invert_jac( grp, R, i >> 7 ) );
1312 const ecp_point T[],
unsigned char t_len,
1313 const unsigned char x[],
size_t d,
1314 int (*f_rng)(
void *,
unsigned char *,
size_t),
1325 MPI_CHK( ecp_select_comb( grp, R, T, t_len, x[i] ) );
1328 MPI_CHK( ecp_randomize_jac( grp, R, f_rng, p_rng ) );
1332 MPI_CHK( ecp_double_jac( grp, R, R ) );
1333 MPI_CHK( ecp_select_comb( grp, &Txi, T, t_len, x[i] ) );
1334 MPI_CHK( ecp_add_mixed( grp, R, R, &Txi ) );
1349 int (*f_rng)(
void *,
unsigned char *,
size_t),
1353 unsigned char w, m_is_odd, p_eq_g, pre_len, i;
1355 unsigned char k[COMB_MAX_D + 1];
1371 w = grp->
nbits >= 384 ? 5 : 4;
1378 #if POLARSSL_ECP_FIXED_POINT_OPTIM == 1
1393 if( w >= grp->
nbits )
1397 pre_len = 1U << ( w - 1 );
1398 d = ( grp->
nbits + w - 1 ) / w;
1404 T = p_eq_g ? grp->
T : NULL;
1415 for( i = 0; i < pre_len; i++ )
1418 MPI_CHK( ecp_precompute_comb( grp, T, P, w, d ) );
1439 ecp_comb_fixed( k, d, w, &M );
1440 MPI_CHK( ecp_mul_comb_core( grp, R, T, pre_len, k, d, f_rng, p_rng ) );
1445 MPI_CHK( ecp_safe_invert_jac( grp, R, ! m_is_odd ) );
1446 MPI_CHK( ecp_normalize_jac( grp, R ) );
1450 if( T != NULL && ! p_eq_g )
1452 for( i = 0; i < pre_len; i++ )
1468 #if defined(POLARSSL_ECP_MONTGOMERY)
1502 int (*f_rng)(
void *,
unsigned char *,
size_t),
void *p_rng )
1506 size_t p_size = (grp->
pbits + 7) / 8;
1548 static int ecp_double_add_mxz(
const ecp_group *grp,
1554 mpi A, AA, B, BB, E, C, D, DA, CB;
1593 int (*f_rng)(
void *,
unsigned char *,
size_t),
1618 MPI_CHK( ecp_randomize_mxz( grp, &RP, f_rng, p_rng ) );
1634 MPI_CHK( ecp_double_add_mxz( grp, R, &RP, R, &RP, &PX ) );
1639 MPI_CHK( ecp_normalize_mxz( grp, R ) );
1654 int (*f_rng)(
void *,
unsigned char *,
size_t),
void *p_rng )
1666 #if defined(POLARSSL_ECP_MONTGOMERY)
1667 if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_MONTGOMERY )
1668 return( ecp_mul_mxz( grp, R, m, P, f_rng, p_rng ) );
1670 #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
1671 if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
1672 return( ecp_mul_comb( grp, R, m, P, f_rng, p_rng ) );
1677 #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
1704 if( grp->
A.
p == NULL )
1728 #if defined(POLARSSL_ECP_MONTGOMERY)
1751 #if defined(POLARSSL_ECP_MONTGOMERY)
1752 if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_MONTGOMERY )
1753 return( ecp_check_pubkey_mx( grp, pt ) );
1755 #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
1756 if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
1757 return( ecp_check_pubkey_sw( grp, pt ) );
1767 #if defined(POLARSSL_ECP_MONTGOMERY)
1768 if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_MONTGOMERY )
1780 #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
1781 if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
1799 int (*f_rng)(
void *,
unsigned char *,
size_t),
1803 size_t n_size = (grp->
nbits + 7) / 8;
1805 #if defined(POLARSSL_ECP_MONTGOMERY)
1806 if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_MONTGOMERY )
1815 if( b > grp->
nbits )
1827 #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
1828 if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
1843 MPI_CHK( f_rng( p_rng, rnd, n_size ) );
1870 return(
ecp_mul( grp, Q, d, &grp->
G, f_rng, p_rng ) );
1877 int (*f_rng)(
void *,
unsigned char *,
size_t),
void *p_rng )
1887 #if defined(POLARSSL_SELF_TEST)
1899 unsigned long add_c_prev, dbl_c_prev, mul_c_prev;
1901 const char *exponents[] =
1903 "000000000000000000000000000000000000000000000001",
1904 "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22830",
1905 "5EA6F389A38B8BC81E767753B15AA5569E1782E30ABE7D25",
1906 "400000000000000000000000000000000000000000000000",
1907 "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
1908 "555555555555555555555555555555555555555555555555",
1917 #if defined(POLARSSL_ECP_DP_SECP192R1_ENABLED)
1924 polarssl_printf(
" ECP test #1 (constant op_count, base point G): " );
1936 for( i = 1; i <
sizeof( exponents ) /
sizeof( exponents[0] ); i++ )
1938 add_c_prev = add_count;
1939 dbl_c_prev = dbl_count;
1940 mul_c_prev = mul_count;
1948 if( add_count != add_c_prev ||
1949 dbl_count != dbl_c_prev ||
1950 mul_count != mul_c_prev )
1973 for( i = 1; i <
sizeof( exponents ) /
sizeof( exponents[0] ); i++ )
1975 add_c_prev = add_count;
1976 dbl_c_prev = dbl_count;
1977 mul_c_prev = mul_count;
1985 if( add_count != add_c_prev ||
1986 dbl_count != dbl_c_prev ||
1987 mul_count != mul_c_prev )
2002 if( ret < 0 && verbose != 0 )
int mpi_cmp_int(const mpi *X, t_sint z)
Compare signed values.
#define POLARSSL_ECP_TLS_NAMED_CURVE
ECCurveType's named_curve.
int mpi_shrink(mpi *X, size_t nblimbs)
Resize down, keeping at least the specified number of limbs.
int ecp_sub(const ecp_group *grp, ecp_point *R, const ecp_point *P, const ecp_point *Q)
Subtraction: R = P - Q.
int ecp_check_privkey(const ecp_group *grp, const mpi *d)
Check that an mpi is a valid private key for this curve.
int mpi_safe_cond_assign(mpi *X, const mpi *Y, unsigned char assign)
Safe conditional assignement X = Y if assign is 1.
#define POLARSSL_ERR_ECP_BAD_INPUT_DATA
Bad input parameters to function.
void ecp_keypair_init(ecp_keypair *key)
Initialize a key pair (as an invalid one)
int ecp_group_copy(ecp_group *dst, const ecp_group *src)
Copy the contents of a group object.
#define POLARSSL_ECP_PF_COMPRESSED
Compressed point format.
const ecp_curve_info * ecp_curve_list(void)
Get the list of supported curves in order of preferrence (full information)
int ecp_self_test(int verbose)
Checkup routine.
Elliptic curves over GF(p)
int mpi_fill_random(mpi *X, size_t size, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
Fill an MPI X with size bytes of random.
int mpi_sub_abs(mpi *X, const mpi *A, const mpi *B)
Unsigned subtraction: X = |A| - |B|.
#define POLARSSL_ERR_ECP_MALLOC_FAILED
Memory allocation failed.
#define POLARSSL_ECP_PF_UNCOMPRESSED
Uncompressed point format.
Configuration options (set of defines)
int mpi_lset(mpi *X, t_sint z)
Set value from integer.
int ecp_mul(ecp_group *grp, ecp_point *R, const mpi *m, const ecp_point *P, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
Multiplication by an integer: R = m * P (Not thread-safe to use same group in multiple threads) ...
int ecp_point_read_binary(const ecp_group *grp, ecp_point *P, const unsigned char *buf, size_t ilen)
Import a point from unsigned binary data.
#define POLARSSL_ERR_ECP_FEATURE_UNAVAILABLE
Requested curve not available.
void mpi_init(mpi *X)
Initialize one MPI.
int mpi_cmp_mpi(const mpi *X, const mpi *Y)
Compare signed values.
#define POLARSSL_ECP_WINDOW_SIZE
Maximum window size used.
int mpi_shift_r(mpi *X, size_t count)
Right-shift: X >>= count.
#define POLARSSL_ERR_ECP_BUFFER_TOO_SMALL
The buffer is too small to write to.
#define POLARSSL_ECP_DP_MAX
Number of supported curves (plus one for NONE).
int mpi_add_mpi(mpi *X, const mpi *A, const mpi *B)
Signed addition: X = A + B.
int ecp_gen_key(ecp_group_id grp_id, ecp_keypair *key, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
Generate a keypair.
ECP point structure (jacobian coordinates)
int ecp_is_zero(ecp_point *pt)
Tell if a point is zero.
void ecp_point_init(ecp_point *pt)
Initialize a point (as zero)
const ecp_curve_info * ecp_curve_info_from_grp_id(ecp_group_id grp_id)
Get curve information from an internal group identifier.
int mpi_inv_mod(mpi *X, const mpi *A, const mpi *N)
Modular inverse: X = A^-1 mod N.
int ecp_point_read_string(ecp_point *P, int radix, const char *x, const char *y)
Import a non-zero point from two ASCII strings.
void mpi_free(mpi *X)
Unallocate one MPI.
int mpi_mul_int(mpi *X, const mpi *A, t_sint b)
Baseline multiplication: X = A * b Note: despite the functon signature, b is treated as a t_uint...
void ecp_group_free(ecp_group *grp)
Free the components of an ECP group.
Curve information for use by other modules.
int ecp_tls_write_point(const ecp_group *grp, const ecp_point *pt, int format, size_t *olen, unsigned char *buf, size_t blen)
Export a point as a TLS ECPoint record.
int ecp_gen_keypair(ecp_group *grp, mpi *d, ecp_point *Q, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
Generate a keypair.
#define POLARSSL_ECP_MAX_BYTES
size_t mpi_msb(const mpi *X)
Return the number of bits up to and including the most significant '1' bit'.
int ecp_use_known_dp(ecp_group *grp, ecp_group_id index)
Set a group using well-known domain parameters.
int mpi_read_string(mpi *X, int radix, const char *s)
Import from an ASCII string.
int ecp_copy(ecp_point *P, const ecp_point *Q)
Copy the contents of point Q into P.
int mpi_read_binary(mpi *X, const unsigned char *buf, size_t buflen)
Import X from unsigned binary data, big endian.
int ecp_tls_write_group(const ecp_group *grp, size_t *olen, unsigned char *buf, size_t blen)
Write the TLS ECParameters record for a group.
ecp_group_id
Domain parameters (curve, subgroup and generator) identifiers.
int ecp_point_write_binary(const ecp_group *grp, const ecp_point *P, int format, size_t *olen, unsigned char *buf, size_t buflen)
Export a point into unsigned binary data.
void ecp_group_init(ecp_group *grp)
Initialize a group (to something meaningless)
#define POLARSSL_ERR_ECP_RANDOM_FAILED
Generation of random value, such as (ephemeral) key, failed.
size_t mpi_size(const mpi *X)
Return the total size in bytes.
int mpi_copy(mpi *X, const mpi *Y)
Copy the contents of Y into X.
int mpi_mod_mpi(mpi *R, const mpi *A, const mpi *B)
Modulo: R = A mod B.
int mpi_get_bit(const mpi *X, size_t pos)
Get a specific bit from X.
int mpi_write_binary(const mpi *X, unsigned char *buf, size_t buflen)
Export X into unsigned binary data, big endian.
int ecp_tls_read_group(ecp_group *grp, const unsigned char **buf, size_t len)
Set a group from a TLS ECParameters record.
int mpi_safe_cond_swap(mpi *X, mpi *Y, unsigned char assign)
Safe conditional swap X <-> Y if swap is 1.
int ecp_check_pubkey(const ecp_group *grp, const ecp_point *pt)
Check that a point is a valid public key on this curve.
const ecp_curve_info * ecp_curve_info_from_tls_id(uint16_t tls_id)
Get curve information from a TLS NamedCurve value.
const ecp_curve_info * ecp_curve_info_from_name(const char *name)
Get curve information from a human-readable name.
int ecp_add(const ecp_group *grp, ecp_point *R, const ecp_point *P, const ecp_point *Q)
Addition: R = P + Q.
int mpi_mul_mpi(mpi *X, const mpi *A, const mpi *B)
Baseline multiplication: X = A * B.
int ecp_set_zero(ecp_point *pt)
Set a point to zero.
int mpi_sub_mpi(mpi *X, const mpi *A, const mpi *B)
Signed subtraction: X = A - B.
int mpi_set_bit(mpi *X, size_t pos, unsigned char val)
Set a bit of X to a specific value of 0 or 1.
int mpi_sub_int(mpi *X, const mpi *A, t_sint b)
Signed subtraction: X = A - b.
#define POLARSSL_ERR_ECP_INVALID_KEY
Invalid private or public key.
void ecp_keypair_free(ecp_keypair *key)
Free the components of a key pair.
int ecp_tls_read_point(const ecp_group *grp, ecp_point *pt, const unsigned char **buf, size_t len)
Import a point from a TLS ECPoint record.
const ecp_group_id * ecp_grp_id_list(void)
Get the list of supported curves in order of preferrence (grp_id only)
int ecp_group_read_string(ecp_group *grp, int radix, const char *p, const char *b, const char *gx, const char *gy, const char *n)
Import an ECP group from null-terminated ASCII strings.
void ecp_point_free(ecp_point *pt)
Free the components of a point.