49 #if defined(POLARSSL_ECP_C)
53 #if defined(POLARSSL_MEMORY_C)
56 #define polarssl_malloc malloc
57 #define polarssl_free free
62 #if defined(_MSC_VER) && !defined strcasecmp && !defined(EFIX64) && \
64 #define strcasecmp _stricmp
67 #if defined(_MSC_VER) && !defined(inline)
68 #define inline _inline
70 #if defined(__ARMCC_VERSION) && !defined(inline)
71 #define inline __inline
75 #if defined(POLARSSL_SELF_TEST)
80 static unsigned long add_count, dbl_count, mul_count;
83 #if defined(POLARSSL_ECP_DP_SECP192R1_ENABLED) || \
84 defined(POLARSSL_ECP_DP_SECP224R1_ENABLED) || \
85 defined(POLARSSL_ECP_DP_SECP256R1_ENABLED) || \
86 defined(POLARSSL_ECP_DP_SECP384R1_ENABLED) || \
87 defined(POLARSSL_ECP_DP_SECP521R1_ENABLED) || \
88 defined(POLARSSL_ECP_DP_BP256R1_ENABLED) || \
89 defined(POLARSSL_ECP_DP_BP384R1_ENABLED) || \
90 defined(POLARSSL_ECP_DP_BP512R1_ENABLED)
91 #define POLARSSL_ECP_SHORT_WEIERSTRASS
94 #if defined(POLARSSL_ECP_DP_M221_ENABLED) || \
95 defined(POLARSSL_ECP_DP_M255_ENABLED) || \
96 defined(POLARSSL_ECP_DP_M383_ENABLED) || \
97 defined(POLARSSL_ECP_DP_M511_ENABLED)
98 #define POLARSSL_ECP_MONTGOMERY
106 POLARSSL_ECP_TYPE_NONE = 0,
107 POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS,
108 POLARSSL_ECP_TYPE_MONTGOMERY,
120 #if defined(POLARSSL_ECP_DP_BP512R1_ENABLED)
123 #if defined(POLARSSL_ECP_DP_BP384R1_ENABLED)
126 #if defined(POLARSSL_ECP_DP_BP256R1_ENABLED)
129 #if defined(POLARSSL_ECP_DP_SECP521R1_ENABLED)
132 #if defined(POLARSSL_ECP_DP_SECP384R1_ENABLED)
135 #if defined(POLARSSL_ECP_DP_SECP256R1_ENABLED)
138 #if defined(POLARSSL_ECP_DP_SECP224R1_ENABLED)
141 #if defined(POLARSSL_ECP_DP_SECP192R1_ENABLED)
152 return ecp_supported_curves;
166 if( curve_info->
grp_id == grp_id )
167 return( curve_info );
184 if( curve_info->
tls_id == tls_id )
185 return( curve_info );
202 if( strcasecmp( curve_info->
name, name ) == 0 )
203 return( curve_info );
212 static inline ecp_curve_type ecp_get_type(
const ecp_group *grp )
214 if( grp->
G.
X.
p == NULL )
215 return( POLARSSL_ECP_TYPE_NONE );
217 if( grp->
G.
Y.
p == NULL )
218 return( POLARSSL_ECP_TYPE_MONTGOMERY );
220 return( POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS );
294 for( i = 0; i < grp->
T_size; i++ )
365 const char *x,
const char *y )
381 int format,
size_t *olen,
382 unsigned char *buf,
size_t buflen )
409 *olen = 2 * plen + 1;
437 const unsigned char *buf,
size_t ilen ) {
441 if( ilen == 1 && buf[0] == 0x00 )
446 if( ilen != 2 * plen + 1 || buf[0] != 0x04 )
464 const unsigned char **buf,
size_t buf_len )
466 unsigned char data_len;
467 const unsigned char *buf_start;
475 data_len = *(*buf)++;
476 if( data_len < 1 || data_len > buf_len - 1 )
495 int format,
size_t *olen,
496 unsigned char *buf,
size_t blen )
507 olen, buf + 1, blen - 1) ) != 0 )
513 buf[0] = (
unsigned char) *olen;
523 const char *p,
const char *b,
524 const char *gx,
const char *gy,
const char *n)
580 unsigned char *buf,
size_t blen )
602 buf[0] = curve_info->
tls_id >> 8;
603 buf[1] = curve_info->
tls_id & 0xFF;
618 if( grp->
modp == NULL )
655 #if defined(POLARSSL_SELF_TEST)
656 #define INC_MUL_COUNT mul_count++;
658 #define INC_MUL_COUNT
661 #define MOD_MUL( N ) do { MPI_CHK( ecp_modp( &N, grp ) ); INC_MUL_COUNT } \
668 #define MOD_SUB( N ) \
669 while( N.s < 0 && mpi_cmp_int( &N, 0 ) != 0 ) \
670 MPI_CHK( mpi_add_mpi( &N, &N, &grp->P ) )
677 #define MOD_ADD( N ) \
678 while( mpi_cmp_mpi( &N, &grp->P ) >= 0 ) \
679 MPI_CHK( mpi_sub_abs( &N, &N, &grp->P ) )
681 #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
740 static int ecp_normalize_jac_many(
const ecp_group *grp,
748 return( ecp_normalize_jac( grp, *T ) );
754 for( i = 0; i < t_len; i++ )
761 for( i = 1; i < t_len; i++ )
772 for( i = t_len - 1; ; i-- )
812 for( i = 0; i < t_len; i++ )
823 static int ecp_safe_invert_jac(
const ecp_group *grp,
828 unsigned char nonzero;
858 mpi T1, T2, T3, X3, Y3, Z3;
860 #if defined(POLARSSL_SELF_TEST)
880 if( grp->
A.
p == NULL )
935 mpi T1, T2, T3, T4, X, Y, Z;
937 #if defined(POLARSSL_SELF_TEST)
971 ret = ecp_double_jac( grp, R, P );
1014 if( ecp_get_type( grp ) != POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
1017 MPI_CHK( ecp_add_mixed( grp, R, P, Q ) );
1018 MPI_CHK( ecp_normalize_jac( grp, R ) );
1035 if( ecp_get_type( grp ) != POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
1043 MPI_CHK( ecp_add_mixed( grp, R, P, &mQ ) );
1044 MPI_CHK( ecp_normalize_jac( grp, R ) );
1060 int (*f_rng)(
void *,
unsigned char *,
size_t),
void *p_rng )
1064 size_t p_size = (grp->
pbits + 7) / 8;
1102 #if POLARSSL_ECP_WINDOW_SIZE < 2 || POLARSSL_ECP_WINDOW_SIZE > 7
1103 #error "POLARSSL_ECP_WINDOW_SIZE out of bounds"
1107 #define COMB_MAX_D ( POLARSSL_ECP_MAX_BITS + 1 ) / 2
1110 #define COMB_MAX_PRE ( 1 << ( POLARSSL_ECP_WINDOW_SIZE - 1 ) )
1132 static void ecp_comb_fixed(
unsigned char x[],
size_t d,
1133 unsigned char w,
const mpi *m )
1136 unsigned char c, cc, adjust;
1138 memset( x, 0, d+1 );
1141 for( i = 0; i < d; i++ )
1142 for( j = 0; j < w; j++ )
1147 for( i = 1; i <= d; i++ )
1155 adjust = 1 - ( x[i] & 0x01 );
1156 c |= x[i] & ( x[i-1] * adjust );
1157 x[i] = x[i] ^ ( x[i-1] * adjust );
1158 x[i-1] |= adjust << 7;
1172 static int ecp_precompute_comb(
const ecp_group *grp,
1174 unsigned char w,
size_t d )
1188 for( i = 1; i < ( 1U << (w-1) ); i <<= 1 )
1192 for( j = 0; j < d; j++ )
1193 MPI_CHK( ecp_double_jac( grp, cur, cur ) );
1198 MPI_CHK( ecp_normalize_jac_many( grp, TT, k ) );
1205 for( i = 1; i < ( 1U << (w-1) ); i <<= 1 )
1210 MPI_CHK( ecp_add_mixed( grp, &T[i + j], &T[j], &T[i] ) );
1211 TT[k++] = &T[i + j];
1215 MPI_CHK( ecp_normalize_jac_many( grp, TT, k ) );
1225 const ecp_point T[],
unsigned char t_len,
1229 unsigned char ii, j;
1232 ii = ( i & 0x7Fu ) >> 1;
1235 for( j = 0; j < t_len; j++ )
1242 MPI_CHK( ecp_safe_invert_jac( grp, R, i >> 7 ) );
1255 const ecp_point T[],
unsigned char t_len,
1256 const unsigned char x[],
size_t d,
1257 int (*f_rng)(
void *,
unsigned char *,
size_t),
1268 MPI_CHK( ecp_select_comb( grp, R, T, t_len, x[i] ) );
1271 MPI_CHK( ecp_randomize_jac( grp, R, f_rng, p_rng ) );
1275 MPI_CHK( ecp_double_jac( grp, R, R ) );
1276 MPI_CHK( ecp_select_comb( grp, &Txi, T, t_len, x[i] ) );
1277 MPI_CHK( ecp_add_mixed( grp, R, R, &Txi ) );
1292 int (*f_rng)(
void *,
unsigned char *,
size_t),
1296 unsigned char w, m_is_odd, p_eq_g, pre_len, i;
1298 unsigned char k[COMB_MAX_D + 1];
1314 w = grp->
nbits >= 384 ? 5 : 4;
1321 #if POLARSSL_ECP_FIXED_POINT_OPTIM == 1
1336 if( w >= grp->
nbits )
1340 pre_len = 1U << ( w - 1 );
1341 d = ( grp->
nbits + w - 1 ) / w;
1347 T = p_eq_g ? grp->
T : NULL;
1358 for( i = 0; i < pre_len; i++ )
1361 MPI_CHK( ecp_precompute_comb( grp, T, P, w, d ) );
1382 ecp_comb_fixed( k, d, w, &M );
1383 MPI_CHK( ecp_mul_comb_core( grp, R, T, pre_len, k, d, f_rng, p_rng ) );
1388 MPI_CHK( ecp_safe_invert_jac( grp, R, ! m_is_odd ) );
1389 MPI_CHK( ecp_normalize_jac( grp, R ) );
1393 if( T != NULL && ! p_eq_g )
1395 for( i = 0; i < pre_len; i++ )
1411 #if defined(POLARSSL_ECP_MONTGOMERY)
1445 int (*f_rng)(
void *,
unsigned char *,
size_t),
void *p_rng )
1449 size_t p_size = (grp->
pbits + 7) / 8;
1491 static int ecp_double_add_mxz(
const ecp_group *grp,
1497 mpi A, AA, B, BB, E, C, D, DA, CB;
1536 int (*f_rng)(
void *,
unsigned char *,
size_t),
1561 MPI_CHK( ecp_randomize_mxz( grp, &RP, f_rng, p_rng ) );
1577 MPI_CHK( ecp_double_add_mxz( grp, R, &RP, R, &RP, &PX ) );
1582 MPI_CHK( ecp_normalize_mxz( grp, R ) );
1597 int (*f_rng)(
void *,
unsigned char *,
size_t),
void *p_rng )
1609 #if defined(POLARSSL_ECP_MONTGOMERY)
1610 if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_MONTGOMERY )
1611 return( ecp_mul_mxz( grp, R, m, P, f_rng, p_rng ) );
1613 #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
1614 if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
1615 return( ecp_mul_comb( grp, R, m, P, f_rng, p_rng ) );
1620 #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
1647 if( grp->
A.
p == NULL )
1671 #if defined(POLARSSL_ECP_MONTGOMERY)
1694 #if defined(POLARSSL_ECP_MONTGOMERY)
1695 if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_MONTGOMERY )
1696 return( ecp_check_pubkey_mx( grp, pt ) );
1698 #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
1699 if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
1700 return( ecp_check_pubkey_sw( grp, pt ) );
1710 #if defined(POLARSSL_ECP_MONTGOMERY)
1711 if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_MONTGOMERY )
1723 #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
1724 if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
1742 int (*f_rng)(
void *,
unsigned char *,
size_t),
1745 size_t n_size = (grp->
nbits + 7) / 8;
1747 #if defined(POLARSSL_ECP_MONTGOMERY)
1748 if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_MONTGOMERY )
1757 if( b > grp->
nbits )
1769 #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
1770 if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
1790 return(
ecp_mul( grp, Q, d, &grp->
G, f_rng, p_rng ) );
1797 int (*f_rng)(
void *,
unsigned char *,
size_t),
void *p_rng )
1807 #if defined(POLARSSL_SELF_TEST)
1819 unsigned long add_c_prev, dbl_c_prev, mul_c_prev;
1821 const char *exponents[] =
1823 "000000000000000000000000000000000000000000000001",
1824 "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22830",
1825 "5EA6F389A38B8BC81E767753B15AA5569E1782E30ABE7D25",
1826 "400000000000000000000000000000000000000000000000",
1827 "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
1828 "555555555555555555555555555555555555555555555555",
1837 #if defined(POLARSSL_ECP_DP_SECP192R1_ENABLED)
1844 printf(
" ECP test #1 (constant op_count, base point G): " );
1856 for( i = 1; i <
sizeof( exponents ) /
sizeof( exponents[0] ); i++ )
1858 add_c_prev = add_count;
1859 dbl_c_prev = dbl_count;
1860 mul_c_prev = mul_count;
1868 if( add_count != add_c_prev ||
1869 dbl_count != dbl_c_prev ||
1870 mul_count != mul_c_prev )
1873 printf(
"failed (%u)\n", (
unsigned int) i );
1881 printf(
"passed\n" );
1884 printf(
" ECP test #2 (constant op_count, other point): " );
1893 for( i = 1; i <
sizeof( exponents ) /
sizeof( exponents[0] ); i++ )
1895 add_c_prev = add_count;
1896 dbl_c_prev = dbl_count;
1897 mul_c_prev = mul_count;
1905 if( add_count != add_c_prev ||
1906 dbl_count != dbl_c_prev ||
1907 mul_count != mul_c_prev )
1910 printf(
"failed (%u)\n", (
unsigned int) i );
1918 printf(
"passed\n" );
1922 if( ret < 0 && verbose != 0 )
1923 printf(
"Unexpected error, return code = %08X\n", ret );
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.
void *(* polarssl_malloc)(size_t len)
#define POLARSSL_ECP_PF_COMPRESSED
Compressed point format.
const ecp_curve_info * ecp_curve_list(void)
Return the list of supported curves with associated info.
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.
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)
void(* polarssl_free)(void *ptr)
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.
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.
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.