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)
144 #if defined(POLARSSL_ECP_DP_SECP256K1_ENABLED)
147 #if defined(POLARSSL_ECP_DP_SECP224K1_ENABLED)
150 #if defined(POLARSSL_ECP_DP_SECP192K1_ENABLED)
161 return ecp_supported_curves;
175 if( curve_info->
grp_id == grp_id )
176 return( curve_info );
193 if( curve_info->
tls_id == tls_id )
194 return( curve_info );
211 if( strcasecmp( curve_info->
name, name ) == 0 )
212 return( curve_info );
221 static inline ecp_curve_type ecp_get_type(
const ecp_group *grp )
223 if( grp->
G.
X.
p == NULL )
224 return( POLARSSL_ECP_TYPE_NONE );
226 if( grp->
G.
Y.
p == NULL )
227 return( POLARSSL_ECP_TYPE_MONTGOMERY );
229 return( POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS );
303 for( i = 0; i < grp->
T_size; i++ )
374 const char *x,
const char *y )
390 int format,
size_t *olen,
391 unsigned char *buf,
size_t buflen )
418 *olen = 2 * plen + 1;
446 const unsigned char *buf,
size_t ilen ) {
450 if( ilen == 1 && buf[0] == 0x00 )
455 if( ilen != 2 * plen + 1 || buf[0] != 0x04 )
473 const unsigned char **buf,
size_t buf_len )
475 unsigned char data_len;
476 const unsigned char *buf_start;
484 data_len = *(*buf)++;
485 if( data_len < 1 || data_len > buf_len - 1 )
504 int format,
size_t *olen,
505 unsigned char *buf,
size_t blen )
516 olen, buf + 1, blen - 1) ) != 0 )
522 buf[0] = (
unsigned char) *olen;
532 const char *p,
const char *b,
533 const char *gx,
const char *gy,
const char *n)
589 unsigned char *buf,
size_t blen )
611 buf[0] = curve_info->
tls_id >> 8;
612 buf[1] = curve_info->
tls_id & 0xFF;
627 if( grp->
modp == NULL )
664 #if defined(POLARSSL_SELF_TEST)
665 #define INC_MUL_COUNT mul_count++;
667 #define INC_MUL_COUNT
670 #define MOD_MUL( N ) do { MPI_CHK( ecp_modp( &N, grp ) ); INC_MUL_COUNT } \
677 #define MOD_SUB( N ) \
678 while( N.s < 0 && mpi_cmp_int( &N, 0 ) != 0 ) \
679 MPI_CHK( mpi_add_mpi( &N, &N, &grp->P ) )
686 #define MOD_ADD( N ) \
687 while( mpi_cmp_mpi( &N, &grp->P ) >= 0 ) \
688 MPI_CHK( mpi_sub_abs( &N, &N, &grp->P ) )
690 #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
749 static int ecp_normalize_jac_many(
const ecp_group *grp,
757 return( ecp_normalize_jac( grp, *T ) );
763 for( i = 0; i < t_len; i++ )
770 for( i = 1; i < t_len; i++ )
781 for( i = t_len - 1; ; i-- )
821 for( i = 0; i < t_len; i++ )
832 static int ecp_safe_invert_jac(
const ecp_group *grp,
837 unsigned char nonzero;
867 mpi T1, T2, T3, X3, Y3, Z3;
869 #if defined(POLARSSL_SELF_TEST)
889 if( grp->
A.
p == NULL )
944 mpi T1, T2, T3, T4, X, Y, Z;
946 #if defined(POLARSSL_SELF_TEST)
980 ret = ecp_double_jac( grp, R, P );
1023 if( ecp_get_type( grp ) != POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
1026 MPI_CHK( ecp_add_mixed( grp, R, P, Q ) );
1027 MPI_CHK( ecp_normalize_jac( grp, R ) );
1044 if( ecp_get_type( grp ) != POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
1052 MPI_CHK( ecp_add_mixed( grp, R, P, &mQ ) );
1053 MPI_CHK( ecp_normalize_jac( grp, R ) );
1069 int (*f_rng)(
void *,
unsigned char *,
size_t),
void *p_rng )
1073 size_t p_size = (grp->
pbits + 7) / 8;
1111 #if POLARSSL_ECP_WINDOW_SIZE < 2 || POLARSSL_ECP_WINDOW_SIZE > 7
1112 #error "POLARSSL_ECP_WINDOW_SIZE out of bounds"
1116 #define COMB_MAX_D ( POLARSSL_ECP_MAX_BITS + 1 ) / 2
1119 #define COMB_MAX_PRE ( 1 << ( POLARSSL_ECP_WINDOW_SIZE - 1 ) )
1141 static void ecp_comb_fixed(
unsigned char x[],
size_t d,
1142 unsigned char w,
const mpi *m )
1145 unsigned char c, cc, adjust;
1147 memset( x, 0, d+1 );
1150 for( i = 0; i < d; i++ )
1151 for( j = 0; j < w; j++ )
1156 for( i = 1; i <= d; i++ )
1164 adjust = 1 - ( x[i] & 0x01 );
1165 c |= x[i] & ( x[i-1] * adjust );
1166 x[i] = x[i] ^ ( x[i-1] * adjust );
1167 x[i-1] |= adjust << 7;
1181 static int ecp_precompute_comb(
const ecp_group *grp,
1183 unsigned char w,
size_t d )
1197 for( i = 1; i < ( 1U << (w-1) ); i <<= 1 )
1201 for( j = 0; j < d; j++ )
1202 MPI_CHK( ecp_double_jac( grp, cur, cur ) );
1207 MPI_CHK( ecp_normalize_jac_many( grp, TT, k ) );
1214 for( i = 1; i < ( 1U << (w-1) ); i <<= 1 )
1219 MPI_CHK( ecp_add_mixed( grp, &T[i + j], &T[j], &T[i] ) );
1220 TT[k++] = &T[i + j];
1224 MPI_CHK( ecp_normalize_jac_many( grp, TT, k ) );
1234 const ecp_point T[],
unsigned char t_len,
1238 unsigned char ii, j;
1241 ii = ( i & 0x7Fu ) >> 1;
1244 for( j = 0; j < t_len; j++ )
1251 MPI_CHK( ecp_safe_invert_jac( grp, R, i >> 7 ) );
1264 const ecp_point T[],
unsigned char t_len,
1265 const unsigned char x[],
size_t d,
1266 int (*f_rng)(
void *,
unsigned char *,
size_t),
1277 MPI_CHK( ecp_select_comb( grp, R, T, t_len, x[i] ) );
1280 MPI_CHK( ecp_randomize_jac( grp, R, f_rng, p_rng ) );
1284 MPI_CHK( ecp_double_jac( grp, R, R ) );
1285 MPI_CHK( ecp_select_comb( grp, &Txi, T, t_len, x[i] ) );
1286 MPI_CHK( ecp_add_mixed( grp, R, R, &Txi ) );
1301 int (*f_rng)(
void *,
unsigned char *,
size_t),
1305 unsigned char w, m_is_odd, p_eq_g, pre_len, i;
1307 unsigned char k[COMB_MAX_D + 1];
1323 w = grp->
nbits >= 384 ? 5 : 4;
1330 #if POLARSSL_ECP_FIXED_POINT_OPTIM == 1
1345 if( w >= grp->
nbits )
1349 pre_len = 1U << ( w - 1 );
1350 d = ( grp->
nbits + w - 1 ) / w;
1356 T = p_eq_g ? grp->
T : NULL;
1367 for( i = 0; i < pre_len; i++ )
1370 MPI_CHK( ecp_precompute_comb( grp, T, P, w, d ) );
1391 ecp_comb_fixed( k, d, w, &M );
1392 MPI_CHK( ecp_mul_comb_core( grp, R, T, pre_len, k, d, f_rng, p_rng ) );
1397 MPI_CHK( ecp_safe_invert_jac( grp, R, ! m_is_odd ) );
1398 MPI_CHK( ecp_normalize_jac( grp, R ) );
1402 if( T != NULL && ! p_eq_g )
1404 for( i = 0; i < pre_len; i++ )
1420 #if defined(POLARSSL_ECP_MONTGOMERY)
1454 int (*f_rng)(
void *,
unsigned char *,
size_t),
void *p_rng )
1458 size_t p_size = (grp->
pbits + 7) / 8;
1500 static int ecp_double_add_mxz(
const ecp_group *grp,
1506 mpi A, AA, B, BB, E, C, D, DA, CB;
1545 int (*f_rng)(
void *,
unsigned char *,
size_t),
1570 MPI_CHK( ecp_randomize_mxz( grp, &RP, f_rng, p_rng ) );
1586 MPI_CHK( ecp_double_add_mxz( grp, R, &RP, R, &RP, &PX ) );
1591 MPI_CHK( ecp_normalize_mxz( grp, R ) );
1606 int (*f_rng)(
void *,
unsigned char *,
size_t),
void *p_rng )
1618 #if defined(POLARSSL_ECP_MONTGOMERY)
1619 if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_MONTGOMERY )
1620 return( ecp_mul_mxz( grp, R, m, P, f_rng, p_rng ) );
1622 #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
1623 if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
1624 return( ecp_mul_comb( grp, R, m, P, f_rng, p_rng ) );
1629 #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
1656 if( grp->
A.
p == NULL )
1680 #if defined(POLARSSL_ECP_MONTGOMERY)
1703 #if defined(POLARSSL_ECP_MONTGOMERY)
1704 if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_MONTGOMERY )
1705 return( ecp_check_pubkey_mx( grp, pt ) );
1707 #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
1708 if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
1709 return( ecp_check_pubkey_sw( grp, pt ) );
1719 #if defined(POLARSSL_ECP_MONTGOMERY)
1720 if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_MONTGOMERY )
1732 #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
1733 if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
1751 int (*f_rng)(
void *,
unsigned char *,
size_t),
1755 size_t n_size = (grp->
nbits + 7) / 8;
1757 #if defined(POLARSSL_ECP_MONTGOMERY)
1758 if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_MONTGOMERY )
1767 if( b > grp->
nbits )
1779 #if defined(POLARSSL_ECP_SHORT_WEIERSTRASS)
1780 if( ecp_get_type( grp ) == POLARSSL_ECP_TYPE_SHORT_WEIERSTRASS )
1795 MPI_CHK( f_rng( p_rng, rnd, n_size ) );
1813 return(
ecp_mul( grp, Q, d, &grp->
G, f_rng, p_rng ) );
1820 int (*f_rng)(
void *,
unsigned char *,
size_t),
void *p_rng )
1830 #if defined(POLARSSL_SELF_TEST)
1842 unsigned long add_c_prev, dbl_c_prev, mul_c_prev;
1844 const char *exponents[] =
1846 "000000000000000000000000000000000000000000000001",
1847 "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22830",
1848 "5EA6F389A38B8BC81E767753B15AA5569E1782E30ABE7D25",
1849 "400000000000000000000000000000000000000000000000",
1850 "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
1851 "555555555555555555555555555555555555555555555555",
1860 #if defined(POLARSSL_ECP_DP_SECP192R1_ENABLED)
1867 printf(
" ECP test #1 (constant op_count, base point G): " );
1879 for( i = 1; i <
sizeof( exponents ) /
sizeof( exponents[0] ); i++ )
1881 add_c_prev = add_count;
1882 dbl_c_prev = dbl_count;
1883 mul_c_prev = mul_count;
1891 if( add_count != add_c_prev ||
1892 dbl_count != dbl_c_prev ||
1893 mul_count != mul_c_prev )
1896 printf(
"failed (%u)\n", (
unsigned int) i );
1904 printf(
"passed\n" );
1907 printf(
" ECP test #2 (constant op_count, other point): " );
1916 for( i = 1; i <
sizeof( exponents ) /
sizeof( exponents[0] ); i++ )
1918 add_c_prev = add_count;
1919 dbl_c_prev = dbl_count;
1920 mul_c_prev = mul_count;
1928 if( add_count != add_c_prev ||
1929 dbl_count != dbl_c_prev ||
1930 mul_count != mul_c_prev )
1933 printf(
"failed (%u)\n", (
unsigned int) i );
1941 printf(
"passed\n" );
1945 if( ret < 0 && verbose != 0 )
1946 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.
#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.
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.