Added ecp_sub() as a variant of ecp_add()
diff --git a/include/polarssl/ecp.h b/include/polarssl/ecp.h
index cea403a..f3e636e 100644
--- a/include/polarssl/ecp.h
+++ b/include/polarssl/ecp.h
@@ -201,6 +201,20 @@
const ecp_point *P, const ecp_point *Q );
/**
+ * \brief Subtraction: R = P - Q
+ *
+ * \param grp ECP group
+ * \param R Destination point
+ * \param P Left-hand point
+ * \param Q Right-hand point
+ *
+ * \return 0 if successful,
+ * POLARSSL_ERR_MPI_MALLOC_FAILED if memory allocation failed
+ */
+int ecp_sub( const ecp_group *grp, ecp_point *R,
+ const ecp_point *P, const ecp_point *Q );
+
+/**
* \brief Multiplication by an integer: R = m * P
*
* \param grp ECP group
diff --git a/library/ecp.c b/library/ecp.c
index 1c614b5..748cccb 100644
--- a/library/ecp.c
+++ b/library/ecp.c
@@ -550,24 +550,44 @@
}
/*
- * Addition: R = P + Q, mixed affine-Jacobian coordinates (GECC 3.22)
- * The coordinates of Q must be normalized (= affine).
+ * Addition or subtraction: R = P + Q or R = P + Q,
+ * mixed affine-Jacobian coordinates (GECC 3.22)
+ *
+ * The coordinates of Q must be normalized (= affine),
+ * but those of P don't need to. R is not normalized.
+ *
+ * If sign >= 0, perform addition, otherwise perform subtraction,
+ * taking advantage of the fact that, for Q != 0, we have
+ * -Q = (Q.X, -Q.Y, Q.Z)
*/
static int ecp_add_mixed( const ecp_group *grp, ecp_point *R,
- const ecp_point *P, const ecp_point *Q )
+ const ecp_point *P, const ecp_point *Q,
+ signed char sign )
{
int ret;
mpi T1, T2, T3, T4, X, Y, Z;
/*
* Trivial cases: P == 0 or Q == 0
+ * (Check Q first, so that we know Q != 0 when we compute -Q.)
*/
- if( mpi_cmp_int( &P->Z, 0 ) == 0 )
- return( ecp_copy( R, Q ) );
-
if( mpi_cmp_int( &Q->Z, 0 ) == 0 )
return( ecp_copy( R, P ) );
+ if( mpi_cmp_int( &P->Z, 0 ) == 0 )
+ {
+ ret = ecp_copy( R, Q );
+
+ /*
+ * -R.Y mod P = P - R.Y unless R.Y == 0
+ */
+ if( ret == 0 && sign < 0)
+ if( mpi_cmp_int( &R->Y, 0 ) != 0 )
+ ret = mpi_sub_mpi( &R->Y, &grp->P, &R->Y );
+
+ return( ret );
+ }
+
/*
* Make sure Q coordinates are normalized
*/
@@ -581,6 +601,17 @@
MPI_CHK( mpi_mul_mpi( &T2, &T1, &P->Z ) ); MOD_MUL( T2 );
MPI_CHK( mpi_mul_mpi( &T1, &T1, &Q->X ) ); MOD_MUL( T1 );
MPI_CHK( mpi_mul_mpi( &T2, &T2, &Q->Y ) ); MOD_MUL( T2 );
+
+ /*
+ * For subtraction, -Q.Y should have been used instead of Q.Y,
+ * so we replace T2 by -T2, which is P - T2 mod P
+ */
+ if( sign < 0 )
+ {
+ MPI_CHK( mpi_sub_mpi( &T2, &grp->P, &T2 ) );
+ MOD_SUB( T2 );
+ }
+
MPI_CHK( mpi_sub_mpi( &T1, &T1, &P->X ) ); MOD_SUB( T1 );
MPI_CHK( mpi_sub_mpi( &T2, &T2, &P->Y ) ); MOD_SUB( T2 );
@@ -631,7 +662,22 @@
{
int ret;
- MPI_CHK( ecp_add_mixed( grp, R, P, Q ) );
+ MPI_CHK( ecp_add_mixed( grp, R, P, Q , 1 ) );
+ MPI_CHK( ecp_normalize( grp, R ) );
+
+cleanup:
+ return( ret );
+}
+
+/*
+ * Subtraction: R = P - Q, result's coordinates normalized
+ */
+int ecp_sub( const ecp_group *grp, ecp_point *R,
+ const ecp_point *P, const ecp_point *Q )
+{
+ int ret;
+
+ MPI_CHK( ecp_add_mixed( grp, R, P, Q, -1 ) );
MPI_CHK( ecp_normalize( grp, R ) );
cleanup:
@@ -667,7 +713,7 @@
for( pos = mpi_msb( m ) - 1 ; ; pos-- )
{
MPI_CHK( ecp_double_jac( grp, &Q[0], &Q[0] ) );
- MPI_CHK( ecp_add_mixed( grp, &Q[1], &Q[0], P ) );
+ MPI_CHK( ecp_add_mixed( grp, &Q[1], &Q[0], P, 1 ) );
MPI_CHK( ecp_copy( &Q[0], &Q[ mpi_get_bit( m, pos ) ] ) );
if( pos == 0 )
diff --git a/tests/suites/test_suite_ecp.data b/tests/suites/test_suite_ecp.data
index 816df77..c0dd018 100644
--- a/tests/suites/test_suite_ecp.data
+++ b/tests/suites/test_suite_ecp.data
@@ -22,6 +22,33 @@
ECP small addition #8
ecp_small_add:0:"14":"11":0:"14":"11":0:27:30
+ECP small subtraction #1
+ecp_small_sub:1:"":"":1:"":"":1:0:0
+
+ECP small subtraction #2
+ecp_small_sub:1:"":"":0:"14":"11":0:14:36
+
+ECP small subtraction #3
+ecp_small_sub:1:"":"":0:"13":"00":0:13:00
+
+ECP small subtraction #4
+ecp_small_sub:0:"13":"00":0:"13":"00":1:0:0
+
+ECP small subtraction #5
+ecp_small_sub:0:"14":"11":0:"14":"11":1:0:0
+
+ECP small subtraction #6
+ecp_small_sub:0:"13":"00":0:"37":"16":0:34:14
+
+ECP small subtraction #7
+ecp_small_sub:0:"14":"11":0:"37":"16":0:45:07
+
+ECP small subtraction #8
+ecp_small_sub:0:"37":"31":0:"37":"16":0:21:32
+
+ECP small subtraction #9
+ecp_small_sub:0:"14":"11":0:"14":"36":0:27:30
+
ECP small multiplication negative
ecp_small_mul:-1:0:0:0:POLARSSL_ERR_ECP_GENERIC
diff --git a/tests/suites/test_suite_ecp.function b/tests/suites/test_suite_ecp.function
index c82d6e5..f494f4e 100644
--- a/tests/suites/test_suite_ecp.function
+++ b/tests/suites/test_suite_ecp.function
@@ -54,6 +54,43 @@
END_CASE
BEGIN_CASE
+ecp_small_sub:a_zero:x_a:y_a:b_zero:x_b:y_b:c_zero:x_c:y_c
+{
+ ecp_group grp;
+ ecp_point A, B, C;
+
+ ecp_group_init( &grp );
+ ecp_point_init( &A ); ecp_point_init( &B ); ecp_point_init( &C );
+
+ TEST_ASSERT( ecp_group_read_string( &grp, 10,
+ "47", "4", "17", "42", "13" ) == 0 );
+
+ if( {a_zero} )
+ ecp_set_zero( &A );
+ else
+ TEST_ASSERT( ecp_point_read_string( &A, 10, {x_a}, {y_a} ) == 0 );
+
+ if( {b_zero} )
+ ecp_set_zero( &B );
+ else
+ TEST_ASSERT( ecp_point_read_string( &B, 10, {x_b}, {y_b} ) == 0 );
+
+ TEST_ASSERT( ecp_sub( &grp, &C, &A, &B ) == 0 );
+
+ if( {c_zero} )
+ TEST_ASSERT( mpi_cmp_int( &C.Z, 0 ) == 0 );
+ else
+ {
+ TEST_ASSERT( mpi_cmp_int( &C.X, {x_c} ) == 0 );
+ TEST_ASSERT( mpi_cmp_int( &C.Y, {y_c} ) == 0 );
+ }
+
+ ecp_group_free( &grp );
+ ecp_point_free( &A ); ecp_point_free( &B ); ecp_point_free( &C );
+}
+END_CASE
+
+BEGIN_CASE
ecp_small_mul:m:r_zero:x_r:y_r:ret
{
ecp_group grp;