Elliptic Curve Routines

In these routines a big parameter can also be used wherever a flash is specified, but not visa-versa. Further information may be gleaned from the (lightly) commented source code. An asterisk after the name indicates that the function does not take a mip parameter if MR_GENERIC_MT is defined in mirdef.h .

Function:

BOOL ebrick_init(binst,x,y,a,b,n,w,nb)

ebrick *binst;

big x,y;

big a,b,n;

int w,nb;
Module Description Parameters Return value Restrictions
mrebrick.c Initialises an instance of the Comb method for GF(p) elliptic curve multiplication with precomputation. Internally memory is allocated for 2w elliptic curve points which will be precomputed and stored. For bigger w more space is required, but the exponentiation is quicker. Try w=8. A pointer to the current instance binst, the fixed point G=(x,y) on the curve y2 =x3 + ax + b, the modulus n, and the maximum number of bits to be used in the exponent nb. TRUE if all went well, FALSE if there was a problem. Note: If MR_STATIC is defined in mirdef.h, then the x and y parameters in this function are replaced by a single mr_small * pointer to a precomputed table. In this case the function returns a void.

Function:

BOOL ebrick2_init(binst,x,y,A,B,m,a,b,c,nb)

ebrick2 *binst;

big x,y;

big A,B;

int m,a,b,c,nb;
Module Description Parameters Return value Restrictions
mrec2m.c Initialises an instance of the Comb method for GF(2m) elliptic curve multiplication with precomputation. The field is defined with respect to the trinomial basis tm+ta+1 or the pentanomial basis tm+ta+tb+tc+1. Internally memory is allocated for 2w elliptic curve points which will be precomputed and stored. For bigger w more space is required, but the exponentiation is quicker. Try w=8. A pointer to the current instance binst, the fixed point G=(x,y) on the curve y2 + xy = x3 + Ax2 + B, the field parameters m, a, b, c, and the maximum number of bits to be used in the exponent nb. Set b = 0 for a trinomial basis. TRUE if all went well, FALSE if there was a problem. Note: If MR_STATIC is defined in mirdef.h, then the x and y parameters in this function are replaced by a single mr_small * pointer to a precomputed table. In this case the function returns a void.

Function:

void ebrick_end(binst)

ebrick *binst
Module Description Parameters Return value Restrictions
mrebrick.c Cleans up after an application of the Comb for GF(p) elliptic curves A pointer to the current instance None None

Function:

void ebrick2_end(binst)

ebrick2 *binst
Module Description Parameters Return value Restrictions
mrec2m.c Cleans up after an application of the Comb method for GF(2m) elliptic curves. A pointer to the current instance None None

Function:

void ecurve_add(p,pa)

epoint *p,*pa;
Module Description Parameters Return value Restrictions
mrcurve.c Adds two points on a GF(p) elliptic curve using the special rule for addition. Note that if pa=p, then a different duplication rule is used. Addition is quicker if p is normalised. Two points on the current active curve, pa and p. On exit pa=pa+p. None The input points must actually be on the current active curve.

Function:

void ecurve2_add(p,pa)

epoint *p,*pa;
Module Description Parameters Return value Restrictions
mrec2m.c Adds two points on a GF(2m) elliptic curve using the special rule for addition. Note that if pa=p, then a different duplication rule is used. Addition is quicker if p is normalised. Two points on the current active curve, pa and p. On exit pa=pa+p. None The input points must actually be on the current active curve.

Function:

void ecurve_init(A,B,p,type)

big A,B,p;

int type;
Module Description Parameters Return value Restrictions
mrcurve.c Initialises the internal parameters of the current active GF(p) elliptic curve. The curve is assumed to be of the form y2 =x3 + Ax + B mod p, the so-called Weierstrass model. This routine can be called subsequently with the parameters of a different curve. Three big numbers A, B and p. The type parameter must be either MR_PROJECTIVE or MR_AFFINE, and specifies whether projective or affine co-ordinates should be used internally. Normally the former is faster. None Allocated memory will be freed when the current instance of MIRACL is terminated by a call to mirexit. However only one elliptic curve, GF(p) or GF(2m) may be active within a single MIRACL instance. In addition, a call to a function like powmod will overwrite the stored modulus. This can be restored by a repeat call to ecurve_init

Function:

BOOL ecurve2_init(m,a,b,c,A,B,check,type)

big A,B;

int m,a,b,c,type;

BOOL check;
Module Description Parameters Return value Restrictions
mrec2m.c Initialises the internal parameters of the current active elliptic curve. The curve is assumed to be of the form y2 + xy =x3 + Ax2 + B . The field is defined with respect to the trinomial basis tm+ta+1 or the pentanomial basis tm+ta+tb+tc+1. This routine can be called subsequently with the parameters of a different curve. The fixed point G=(x,y) on the curve y2 + xy = x3 + Ax2 + B, the field parameters m, a, b, c. Set b = 0 for a trinomial basis. The type parameter must be either MR_PROJECTIVE or MR_AFFINE, and specifies whether projective or affine co-ordinates should be used internally. Normally the former is faster. If check is TRUE a check is made that the specified basis is irreducible. If FALSE, this basis validity check, which is time-consuming, is suppressed. TRUE if parameters make sense, otherwise FALSE. Allocated memory will be freed when the current instance of MIRACL is terminated by a call to mirexit. However only one elliptic curve, GF(p) or GF(2m) may be active within a single MIRACL instance.

Function:

void ecurve_mult(k,p,pa)

big k;

epoint *p,*pa;
Module Description Parameters Return value Restrictions
mrcurve.c Multiplies a point on a GP(p) elliptic curve by an integer. Uses the addition/subtraction method. A big number k, and two points p and pa. On exit pa=k*p. None The point p must be on the active curve.

Function:

void ecurve2_mult(k,p,pa)

big k;

epoint *p,*pa;
Module Description Parameters Return value Restrictions
mrec2m.c Multiplies a point on a GF(2m) elliptic curve by an integer. Uses the addition/subtraction method. A big number k, and two points p and pa. On exit pa=k*p. None The point p must be on the active curve.

Function:

void ecurve_mult2(k1,p1,k2,p2,pa)

big k1,k2;

epoint *p1,*p2,*pa;
Module Description Parameters Return value Restrictions
mrcurve.c Calculates the point k1.p1+k2.p2 on a GF(p) elliptic curve. This is quicker than doing two separate multiplications and an addition. Useful for certain cryptosystems. (See ecsver.c for example) Two big integers k1 and k2, and three points p1, p2 and pa. On exit pa = k1.p1+k2.p2 None The points p1 and p2 must be on the active curve.

Function:

void ecurve2_mult2(k1,p1,k2,p2,pa)

big k1,k2;

epoint *p1,*p2,*pa;
Module Description Parameters Return value Restrictions
mrec2m.c Calculates the point k1.p1+k2.p2 on a GF(2m) elliptic curve. This is quicker than doing two separate multiplications and an addition. Useful for certain cryptosystems. (See ecsver2.c for example) Two big integers k1 and k2, and three points p1, p2 and pa. On exit pa = k1.p1+k2.p2 None The points p1 and p2 must be on the active curve.

Function:

void ecurve_multi_add(m,x,w)

int m;

epoint x,w;
Module Description Parameters Return value Restrictions
mrcurve.c Simultaneously adds pairs of points on the active GF(p) curve. This is much quicker than adding them individually, but only when using Affine co-ordinates. An integer m and two arrays of points w and x. On exit w[i]=w[i]+x[i] for i =0 to m-1 None Only useful when using Affine co-ordinates. See also: ecurve_init and nres_multi_inverse, which is used internally.

Function:

void ecurve2_multi_add(m,x,w)

int m;

epoint x,w;
Module Description Parameters Return value Restrictions See also
mrec2m.c Simultaneously adds pairs of points on the active GF(2m) curve. This is much quicker than adding them individually, but only when using Affine co-ordinates. An integer m and two arrays of points w and x. On exit w[i]=w[i]+x[i] for i =0 to m-1 None Only useful when using Affine co-ordinates. See also: ecurve2_init

Function:

void ecurve_multn(n,k,p,pa)

int n;

big *k;

epoint p;
Module Description Parameters Return value Restrictions
mrcurve.c Calculates the point k[0].p[0] + k[1].p[1] + … + k[n-1].p[n-1] on a GF(p) elliptic curve, for n>2. An integer n, an array of n big numbers k[], and an array of n points. The result is returned in pa. None The points must be on the active curve. The k[] values must all be positive. The underlying number base must be a power of 2.

Function:

void ecurve2_multn(n,k,p,pa)

int n;

big *k;

epoint p;
Module Description Parameters Return value Restrictions
mrec2m.c Calculates the point k[0].p[0] + k[1].p[1] + … + k[n-1].p[n-1] on a GF(2m) elliptic curve, for n>2. An integer n, an array of n big numbers k[], and an array of n points. The result is returned in pa. None The points must be on the active curve. The k[] values must all be positive. The underlying number base must be a power of 2.

Function:

void ecurve_sub(p,pa)

epoint *p,*pa;
Module Description Parameters Return value Restrictions
mrcurve.c Subtracts two points on a GF(p) elliptic curve. Actually negates p and adds it to pa. Subtraction is quicker if p is normalised. Two points on the current active curve, pa and p. On exit pa = pa-p. None The input points must actually be on the current active curve.

Function:

void ecurve2_sub(p,pa)

epoint *p,*pa;
Module Description Parameters Return value Restrictions
mrec2m.c Subtracts two points on a GF(2m) elliptic curve. Actually negates p and adds it to pa. Subtraction is quicker if p is normalised. Two points on the current active curve, pa and p. On exit pa = pa-p. None The input points must actually be on the current active curve.

Function:

BOOL epoint_comp(p1,p2) epoint *p1,*p2;
Module Description Parameters Return value Restrictions
mrcurve.c Compares two points on the current active GF(p) elliptic curve. Two points p1 and p2. TRUE if the points are the same, otherwise FALSE. None

Function: BOOL epoint2_comp(p1,p2)

epoint *p1,*p2;
Module Description Parameters Return value Restrictions
mrec2m.c Compares two points on the current active GF(2m) elliptic curve. Two points p1 and p2. TRUE if the points are the same, otherwise FALSE. None

Function: void epoint_copy(p1,p2)

epoint *p1,*p2;
Module Description Parameters Return value Restrictions
mrcurve.c Copies one point to another on a GF(p) elliptic curve. Two points p1 and p2. On exit p2=p1. None None

Function:

void epoint2_copy(p1,p2)

epoint *p1,*p2;
Module Description Parameters Return value Restrictions
mrec2m.c Copies one point to another on a GF(2m) elliptic curve. Two points p1 and p2. On exit p2=p1. None None

Function:

void epoint_free(p) epoint *p;
Module Description Parameters Return value Restrictions
mrcore.c Frees memory associated with a point on a GF(p) elliptic curve. A point p. None None

Function:

int epoint_get(p,x,y)

epoint *p;

big x,y;
Module Description Parameters Return value Restrictions
mrcurve.c Normalises a point and extracts its (x,y) co-ordinates on the active GF(p) elliptic curve. A point p, and two big integers x and y. If x and y are not distinct variables on entry then only the value of x is returned. The least significant bit of y. Note that it is possible to reconstruct a point from its x co-ordinate and just the least significant bit of y. Often such a "compressed" description of a point is useful. The point p must be on the active curve.

Example:

i=epoint_get(p,x,x);|  /* extract x co-ordinate and lsb of y */

Function:

void epoint_getxyz(p,x,y,z)

epoint *p;

big x,y,z;
Module Description Parameters Return value Restrictions
mrcurve.c Extracts the raw (x,y,z) co-ordinates of a point on the active GF(p) elliptic curve. A point p, and three big integers x, y and z. If any of these is NULL that coordinate is not returned. None The point p must be on the active curve.

Function: int epoint2_get(p,x,y)

epoint *p;

big x,y;
Module Description Parameters Return value Restrictions
mrec2m.c Normalises a point and extracts its (x,y) co-ordinates on the active GF(2m) elliptic curve. A point p, and two big integers x and y. If x and y are not distinct variables on entry then only the value of x is returned. The least significant bit of y/x. Note that it is possible to reconstruct a point from its x co-ordinate and just the least significant bit of y/x. Often such a "compressed" description of a point is useful. The point p must be on the active curve.

Example:

i=epoint_get(p,x,x);|   /* extract x co-ordinate and lsb of y/x */

Function:

void epoint2_getxyz(p,x,y,z)

epoint *p;

big x,y,z;
Module Description Parameters Return value Restrictions
mrcurve.c Extracts the raw (x,y,z) co-ordinates of a point on the active GF(2m) elliptic curve. A point p, and three big integers x, y and z. If any of these is NULL that coordinate is not returned. None The point p must be on the active curve.

Function: epoint* epoint_init()

Module Description Parameters Return value Restrictions
mrcore.c Assigns memory to a point on a GF(p) elliptic curve, and initialises it to the "point at infinity". None A point p (in fact a pointer to a structure allocated from the heap). It is the C programmers responsibility to ensure that all elliptic curve points initialised by a call to this function, are ultimately freed by a call to epoint_free. If not a memory leak will result.

Function:

epoint* epoint_init_mem(mem,index)

char *mem;

int index;
Module Description Parameters Return value Restrictions
mrcore.c Initialises memory for an elliptic curve point from a pre-allocated byte array mem. This array may be created from the heap by a call to ecp_memalloc, or in some other way. This is quicker than multiple calls to epoint_init A pointer to the pre-allocated array mem, and an index into that array. Each index should be unique. An initialised elliptic curve point. Sufficient memory must have been allocated and pointed to by mem.

Function:

BOOL epoint_norm(p)

epoint *p;
Module Description Parameters Return value
mrcurve.c Normalises a point on the current active GF(p) elliptic curve. This sets the z coordinate to 1. Point addition is quicker when adding a normalised point. This function does nothing if affine coordinates are being used (in which case there is no z co-ordinate) A point on the current active elliptic curve. TRUE if successful.

Function:

BOOL epoint2_norm(p)

epoint *p;
Module Description Parameters Return value
mrec2m.c Normalises a point on the current active GF(2m) elliptic curve. This sets the z coordinate to 1. Point addition is quicker when adding a normalised point. This function does nothing if affine coordinates are being used (in which case there is no z co-ordinate) A point on the current active elliptic curve. TRUE if successful.

Function:

BOOL epoint_set(x,y,lsb,p)

big x,y;

int lsb;

epoint *p;
Module Description Parameters Return value Restrictions
mrcurve.c Sets a point on the current active GF(p) elliptic curve (if possible). The integer co-ordinates x and y of the point p. If x and y are not distinct variables then x only is passed to the function, and lsb is taken as the least significant bit of y. In this case the full value of y is reconstructed internally. This is known as "point decompression" (and is a bit time-consuming, requiring the extraction of a modular square root). On exit p=(x,y). TRUE if the point exists on the current active point, otherwise FALSE. None

Example:

p=epoint_init();

epoint_set(x,x,1,p); /* decompress p */

Function:

BOOL epoint2_set(x,y,lsb,p)

big x,y;

int lsb;

epoint *p;
Module Description Parameters Return value Restrictions
mrec2m.c Sets a point on the current active GF(2m) elliptic curve (if possible). The integer co-ordinates x and y of the point p. If x and y are not distinct variables then x only is passed to the function, and lsb is taken as the least significant bit of y/x. In this case the full value of y is reconstructed internally. This is known as "point decompression" (and is a bit time-consuming, requiring the extraction of a field square root). On exit p=(x,y). TRUE if the point exists on the current active point, otherwise FALSE. None

Example:

p=epoint_init();

epoint2_set(x,x,1,p); /* decompress p */

Function:

BOOL epoint_x(x)

big x;
Module Description Parameters Return value Restrictions
mrcurve.c Tests to see if the parameter x is a valid co-ordinate of a point on the curve. It is faster to test an x co-ordinate first in this way, rather than trying to directly set it on the curve by calling epoint_set, as it avoids an expensive modular square root. The integer coordinate x. TRUE if x is the coordinate of a curve point, otherwise FALSE None

Function:

int mul_brick(binst,e,x,y)

ebrick *binst;

big e,x,y;
Module Description Parameters Return value Restrictions
mrebrick.c Carries out a GF(p) elliptic curve multiplication using the precomputed values stored in the ebrick structure. A pointer to the current instance, a big exponent e and a big number w. On exit (x,y) = e.G mod n, where G and n are specified in the initial call to ebrick_init. If x and y are not distinct variables, only x is returned. The least significant bit of y. Must be preceded by a call to ebrick_init.

Function:

int mul2_brick(binst,e,x,y)

ebrick2 *binst;

big e,x,y;
Module Description Parameters Return value Restrictions
mrec2m.c Carries out a GF(2m) elliptic curve multiplication using the precomputed values stored in the ebrick2 structure. A pointer to the current instance, a big exponent e and a big number w. On exit (x,y) = e.G, where G is specified in the initial call to ebrick2_init. If x and y are not distinct variables, only x is returned. The least significant bit of y/x. Must be preceded by a call to ebrick2_init.

Function:

BOOL point_at_infinity(p)

epoint *p;
Module Description Parameters Return value Restrictions
mrcore.c Tests if an elliptic curve point is the "point at infinity". An elliptic curve point p. TRUE if p is the point-at-infinity, otherwise FALSE. The point must be initialised.