Secure Key Exchange over an Insecure Medium with Public Key Cryptography - Implementing SSL/TLS Using Cryptography and PKI - page 152

NOTE If you look at other texts on elliptic curves, notice that they also
defi ne n the order of the curve and h the cofactor of the curve. h is used to
speed things up in advanced ECC implementations and isn't discussed here.
n is discussed in Chapter 4.
2. You also need a modular inversion routine. You examined one for the huge
implementation earlier, but because you're just doing integer arithmetic
here, you can use the simple ext_euclid routine from Listing 3-25. This
is wrapped up in Listing 3-38.
Listing 3-38: “ecc_int.c” invert routine
/**
* Extended Euclidean algorithm to perform a modular inversion
* of x by y (e.g. (x/y) % p).
*/
static int invert( int x, int y, int p )
{
int inverse = ext_euclid( y, p );
return x * inverse;
}
3. Now, defi ne an add_points operation (modulo a prime p), shown in
Listing 3-39.
Listing 3-39: “ecc_int.c” add_points routine
static void add_points( point *p1, point *p2, int p )
{
point p3;
int lambda = invert( p2->y - p1->y, p2->x - p1->x, p );
p3.x = ( ( lambda * lambda ) - p1->x - p2->x ) % p;
p3.y = ( ( lambda * ( p1->x - p3.x ) ) - p1->y ) % p;
p1->x = p3.x;
p1->y = p3.y;
}
Compare this to the equations defi ning point addition, in the previous sec-
tion. Notice that the result is returned in p1 , just as with the huge routines.
4. You also need a double_point routine, shown in Listing 3-40.
Listing 3-40: “ecc_int.c” double_point routine
static void double_point( point *p1, int p, int a )
{
point p3;
int lambda = invert( 3 * ( p1->x * p1->x ) + a, 2 * p1->y, p );