Curve22519 is a Montgomery elliptic-curve. Such as Apple HomeKit, most of network and IoT software use it in Diffie-Hellman algorithm for key exchanging. On the Security Kinets MCU chip,if we use just the software algorithm (base on mbedTLS), Curve25519 will spend 180ms for calculation of the shared security. It is faster than other 256bit elliptic-curve with software algorithm, Because of the shared security calculation will take more than 1200ms with a Weierstrass’s BP256R1curve when use software algorithm. With LTC ECC HW acceleration, it take only 16ms to calculate the shared security on 256bit elliptic-curve. Whatever you do, the speed of hardware acceleration always faster than the software algorithm. Now that we should also want to use the LTC to accelerate the Curve22519. The LTC, however, only supported Weierstrass form curve, but Curve22519 is a Montgomery curve… Although, we can't use LTC in Curve22519 directly, we can use it by mapping it to a Weierstrass form to use it. As below, we gave parameters of these curves, transform formulas, example code and test result to show how and why to do it. 1. Curve parameter: Cuvre22519 in Montgomery form: Y^2 = X^3 + A*X^2 + X Fp = 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed A= 486662 Gx = 9 Gy = 0x20ae19a1b8a086b4e01edd2c7748d14c923d4d7e6d7c61b229e9c5a27eced3d9 Order of G point = 0x1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed Cuvre22519 in Weierstrass form : Y^2 = X^3 + a*X + b Fp = 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed a = 0x2aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa984914a144L b = 0x7b425ed097b425ed097b425ed097b425ed097b425ed097b4260b5e9c7710c864L Gx = 0x2aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaad245a Gy = 0x20ae19a1b8a086b4e01edd2c7748d14c923d4d7e6d7c61b229e9c5a27eced3d9 Order of G point = 0x1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed 2. Calculation formula: x_w – x-coordinate value in Weierstrass form y_w – y-coordinate value in Weierstrass form x_m - x-coordinate value in Montgomory form y_m - we don’t care y-coordinate value in Weierstrass mode a_m – a coefficient of Montgomery equation ( Y^2 = X^3 + a_m * X^2 + X) a_w – a coefficient of Weierstrass equation ( Y^2 = X^3 + a*X + b ) b_w – a coefficient of Weierstrass equation ( Y^2 = X^3 + a*X + b ) a) x_w = (x_m + a_m/3) % p b) y_w ^2 = x_w ^ 3 + a_w*x_w + b_w c) x_m = (x_w - a_m/3) % p You could reference these document as below: https://en.wikipedia.org/wiki/Curve25519 https://en.wikipedia.org/wiki/Montgomery_curve 3. example code: // public and private at Montgomery end
#define M255_d "0x7178DAC11D42AA5F39B10A62A8584DB0C8864564ADC9DF84EC0B13D9AEC220F8"
#define M255_Qx "0x3BA5048381744348D84E754B9944ABE080B37F7D4158DCE60CD79F66B98AB89E"
// public and private at Weierstrass end
#define WTS255_d "0x09CC5CCF43C656C1309EE5A3491D5A8361607CEEB0C9B2B31A575E0FEF2B8835"
#define WTS255_Qx "0x3F4BDE110EE7AF71EF428D1018D188E35BAFB019F34F84E6465C5194B363DC2D"
#define WTS255_Qy "0x7540577CE6F920354E2A9D38CE88847D7447E66FA4D188AC75CB63C17210B718"
#define WTS255_Qx_TO_M255_Qx "0x14A13366643D04C74497E2656E26DE38B105056F48A4DA3B9BB1A6EA08B6B7DC"
#define AM_INV3 "0x2aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaad2451"
int ecdh_wts_curve_end( )
{
unsigned int ticks;
int ret = 0;
size_t blen = 0, blen_peer = 0;
ecdh_context ecdh;
ecdh_context ecdh_peer; // to_wts255
ecdh_context ecdh_peer_m255;
mpi R;
mpi_init(&R);
ecdh_init( &ecdh);
ecdh_init( &ecdh_peer);
ecdh_init( &ecdh_peer_m255);
MPI_CHK(ecp_use_known_dp( &ecdh.grp, ECP_DP_WTS25519 ));
MPI_CHK(ecp_use_known_dp( &ecdh_peer.grp, ECP_DP_WTS25519 ));
MPI_CHK(ecp_use_known_dp( &ecdh_peer_m255.grp, ECP_DP_M255 ));
blen = set_hash_buff(/*TEST_ECP_GRP_ID*/ECP_DP_WTS25519, &secret_buf, ecp_name);
if(blen == 0) {
ret = -1;
goto cleanup;
}
mpi_read_string(&ecdh.d, 16, WTS255_d);
mpi_read_string(&ecdh.Q.X, 16, WTS255_Qx);
mpi_read_string(&ecdh.Q.Y, 16, WTS255_Qy);
mpi_lset(&ecdh.Q.Z, 1);
mpi_read_string(&ecdh_peer_m255.d, 16, M255_d);
mpi_read_string(&ecdh_peer_m255.Q.X, 16, M255_Qx);
mpi_init(&ecdh_peer_m255.Q.Y);
mpi_lset(&ecdh_peer_m255.Q.Z, 1);
// map M255 point to WTS255 point
my_timer_start();
mpi_read_string(&R, 16, AM_INV3);
mpi_add_mpi(&ecdh_peer.Q.X, &ecdh_peer_m255.Q.X, &R);
mpi_mod_mpi(&ecdh_peer.Q.X, &ecdh_peer.Q.X, &ecdh_peer_m255.grp.P);
mpi_lset(&R, 3);
mpi_exp_mod (&ecdh_peer_m255.Q.Y , &ecdh_peer.Q.X, &R, &ecdh_peer_m255.grp.P, NULL);
mpi_mul_mpi(&R, &ecdh_peer.grp.A, &ecdh_peer.Q.X);
mpi_mod_mpi(&R, &R, &ecdh_peer.grp.P);
mpi_add_mpi(&ecdh_peer_m255.Q.Y, &ecdh_peer_m255.Q.Y, &R);
mpi_add_mpi(&ecdh_peer_m255.Q.Y, &ecdh_peer_m255.Q.Y, &ecdh_peer.grp.B);
mpi_mod_mpi(&ecdh_peer_m255.Q.Y, &ecdh_peer_m255.Q.Y, &ecdh_peer.grp.P);
mpi_mod_sqrt(&ecdh_peer.Q.Y, &ecdh_peer_m255.Q.Y, &ecdh_peer_m255.grp.P);
// z = 1
mpi_lset(&ecdh_peer.Q.Z, 1);
MPI_CHK(ecp_copy(&ecdh.Qp, &ecdh_peer.Q));
MPI_CHK(ecdh_calc_secret_wts2mont( &ecdh, &blen, secret_buf, blen, myrand, NULL));
mpi_read_string(&R, 16, AM_INV3);
mpi_sub_mpi(&ecdh_peer_m255.Q.X, &ecdh.Q.X, &R);
mpi_mod_mpi(&ecdh_peer_m255.Q.X, &ecdh_peer_m255.Q.X, &ecdh_peer_m255.grp.P);
ticks = my_timer_stop();
// print out message
polarssl_printf("Weierstrass curve shared secutiy:\n");
mpi_printf_string( &ecdh.z, 16);
polarssl_printf("%s ecdh peer to peer: %lu ticks, %d ms (%d) \n", ecp_name , ticks, ticks / (CLOCK_SYS_GetPitFreq(0) / 1000),CLOCK_SYS_GetPitFreq(0) );
cleanup:
if( ret !=0 )
polarssl_printf( "%s test Unexpected error, return code = %08X\n", ecp_name, ret );
mpi_free(&R);
ecdh_free( &ecdh);
ecdh_free( &ecdh_peer);
ecdh_free( &ecdh_peer_m255);
return( 0 );
}
int ecdh_mont_curve_end( )
{
int verbose = 1;
unsigned int ticks;
int ret = 0;
size_t blen = 0, blen_peer = 0;
ecdh_context ecdh;
ecp_point Q_peer; // peer public point
ecdh_init( &ecdh);
ecp_point_init( &Q_peer);
MPI_CHK(ecp_use_known_dp( &ecdh.grp, ECP_DP_M255 ));
blen_peer = set_hash_buff(ECP_DP_M255, &secret_buf_peer, ecp_name);
if(blen_peer == 0) {
ret = -1;
goto cleanup;
}
mpi_read_string(&ecdh.d, 16, M255_d);
mpi_read_string(&ecdh.Q.X, 16, M255_Qx);
mpi_init(&ecdh.Q.Y); // don't care Y, only init it
mpi_lset(&ecdh.Q.Z, 1);
mpi_read_string(&Q_peer.X, 16, WTS255_Qx_TO_M255_Qx);
mpi_init(&Q_peer.Y);
mpi_lset(&Q_peer.Z, 1);
MPI_CHK(ecp_copy(&ecdh.Qp, &Q_peer));
my_timer_start();
MPI_CHK(ecdh_calc_secret( &ecdh, &blen_peer, secret_buf_peer, blen_peer, myrand, NULL));
ticks = my_timer_stop();
polarssl_printf("%s ecdh peer to peer: %lu ticks, %d ms (%d) \n", ecp_name , ticks, ticks / (CLOCK_SYS_GetPitFreq(0) / 1000),CLOCK_SYS_GetPitFreq(0) );
polarssl_printf("Montogemory curve shared secutiy:\n");
mpi_printf_string( &ecdh.z, 16);
polarssl_printf( "passed\n" );
cleanup:
if( ret !=0 && verbose != 0 )
polarssl_printf( "%s test Unexpected error, return code = %08X\n", ecp_name, ret );
ecdh_free( &ecdh);
ecp_point_free( &Q_peer);
if( verbose != 0 )
polarssl_printf( "\n" );
return( 0 );
}
4. Test result: Test result of curv25519 in Weierstrass form with LTC: 2. Test result of curve25519 in Montgomery form with software algorithm: We could see that the shared security both in Weierstrass form with LTC and Montgomery form are “0x1454BDCD6A94D6336AA5A76F3CB40BBE12B65A2CDC9DA6B478948906638896D1”. But the calculation speed with LTC was ten times faster than other one.
View full article
