ellproj.c   [plain text]

/**************************************************************
 *
 * ellproj.c
 *
   Fast algorithms for fundamental elliptic curve arithmetic,
   projective format.  Such algorithms apply in domains such as:
    -- factoring
    -- primality studies (e.g. rigorous primality proofs)
    -- elliptic curve cryptography (ECC) 
  
   PROJECTIVE FORMAT

   Functions are supplied herein for projective format
   of points.  Alternative formats differ in their
   range of applicability, efficiency, and so on.
   Primary advantages of the projective format herein are:
    -- No explicit inversions (until perhaps one such at the end of
       an elliptic multiply operation)
    -- Fairly low operation count (~11 muls for point doubling,
       ~16 muls for point addition)  

   The elliptic curve is over F_p, with p > 3 prime, and Weierstrass
   parameterization:

      y^2 = x^3 + a x + b

   The projective-format coordinates are actually stored in
   the form {X, Y, Z}, with true x,y 
   coordinates on the curve given by {x,y} = {X/Z^2, Y/Z^3}.  
   The function normalize_proj() performs the
   transformation from projective->true.  
   (The other direction is trivial, i.e. {x,y} -> {x,y,1} will do.)
   The basic point multiplication function is

      ell_mul_proj()

   which obtains the result k * P for given point P and integer
   multiplier k.  If true {x,y} are required for a multiple, one 
   passes a point P = {X, Y, 1} to ell_mul_proj(), then afterwards 
   calls normalize_proj(), 

   Projective format is an answer to the typical sluggishness of
   standard elliptic arithmetic, whose explicit inversion in the
   field is, depending of course on the machinery and programmer,
   costly.  Projective format is thus especially interesting for
   cryptography.  
 
   REFERENCES

   Crandall R and Pomerance C 1998, "Prime numbers: a computational
		perspective," Springer-Verlag, manuscript

   Solinas J 1998, IEEE P1363 Annex A (draft standard)

   LEGAL AND PATENT NOTICE

   This and related PSI library source code is intended solely for 
   educational and research applications, and should not be used
   for commercial purposes without explicit permission from PSI
   (not to mention proper clearance of legal restrictions beyond
   the purview of PSI).  
   The code herein will not perform cryptography per se,
   although the number-theoretical algorithms herein -- all of which 
   are in the public domain -- can be used in principle to effect 
   what is known as elliptic curve cryptography (ECC).  Note that 
   there are strict constraints on how cryptography may be used, 
   especially in regard to exportability.
   Therefore one should avoid any casual distribution of actual 
   cryptographic software.  Along similar lines, because of various 
   patents, proprietary to Apple Computer, Inc., and perhaps to other 
   organizations, one should not tacitly assume that an ECC scheme is 
   unconstrained.  For example,the commercial use of certain fields 
   F_p^k (i.e., fixation of certain primes p) is covered in Apple 
   patents.

 *	Updates:
 *		3 Apr 98    REC  Creation
 *
 *	c. 1998 Perfectly Scientific, Inc.
 *	All Rights Reserved.
 *
 *
 *************************************************************/

/* include files */

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#ifdef _WIN32 

#include <process.h>

#endif

#include <string.h>
#include "giants.h"
#include "ellproj.h"
#include "tools.h"

/* global variables */

static giant t0 = NULL, t1 = NULL, t2 = NULL, t3 = NULL, t4 = NULL,
	         t5 = NULL, t6 = NULL, t7 = NULL;

/**************************************************************
 *
 *	Maintenance functions
 *
 **************************************************************/

point_proj
new_point_proj(int shorts)
{
	point_proj pt;

	if(t0 == NULL) init_ell_proj(shorts);
	pt = (point_proj) malloc(sizeof(point_struct_proj));
	pt->x = newgiant(shorts);
	pt->y = newgiant(shorts);
	pt->z = newgiant(shorts);
	return(pt);
}

void
free_point_proj(point_proj pt)
{
	free(pt->x); free(pt->y); free(pt->z);
	free(pt);
}

void
ptop_proj(point_proj pt1, point_proj pt2)
{
	gtog(pt1->x, pt2->x);
	gtog(pt1->y, pt2->y);
	gtog(pt1->z, pt2->z);
}

void
init_ell_proj(int shorts) 
/* Called by new_point_proj(), to set up giant registers. */
{	
	t0 = newgiant(shorts);
	t1 = newgiant(shorts);
	t2 = newgiant(shorts);
	t3 = newgiant(shorts);
	t4 = newgiant(shorts);
	t5 = newgiant(shorts);
	t6 = newgiant(shorts);
	t7 = newgiant(shorts);
}


/**************************************************************
 *
 *	Elliptic curve operations
 *
 **************************************************************/

/* Begin projective-format functions for 
 
   y^2 = x^3 + a x + b.

   These are useful in elliptic curve cryptography (ECC).
   A point is kept as a triple {X,Y,Z}, with the true (x,y)
   coordinates given by

	{x,y} = {X/Z^2, Y/Z^3}

   The function normalize_proj() performs the inverse conversion to get
   the true (x,y) pair.
 */

void
ell_double_proj(point_proj pt, giant a, giant p)
/* pt := 2 pt on the curve. */
{	
	giant x = pt->x, y = pt->y, z = pt->z;

	if(isZero(y) || isZero(z)) {
		itog(1,x); itog(1,y); itog(0,z);
		return;
	}	
	gtog(z,t1); squareg(t1); modg(p, t1);
	squareg(t1); modg(p, t1);
	mulg(a, t1); modg(p, t1); /* t1 := a z^4. */
	gtog(x, t2); squareg(t2); smulg(3, t2); modg(p, t2); /* t2 := 3x^2. */
	addg(t2, t1); modg(p, t1);  /* t1 := slope m. */
	mulg(y, z); addg(z,z); modg(p, z);  /* z := 2 y z. */
	gtog(y, t2); squareg(t2); modg(p, t2); /* t2 := y^2. */
	gtog(t2, t3); squareg(t3); modg(p, t3); /* t3 := y^4. */
	gshiftleft(3, t3);  /* t3 := 8 y^4. */
	mulg(x, t2); gshiftleft(2, t2); modg(p, t2); /* t2 := 4xy^2. */
	gtog(t1, x); squareg(x); modg(p, x);
	subg(t2, x); subg(t2, x); modg(p, x); /* x done. */
	gtog(t1, y); subg(x, t2); mulg(t2, y); subg(t3, y);
	modg(p, y);
} 
/*
elldouble[pt_] := Block[{x,y,z,m,y2,s},
	x = pt[[1]]; y = pt[[2]]; z = pt[[3]];
	If[(y==0) || (z==0), Return[{1,1,0}]];
	m = Mod[3 x^2 + a Mod[Mod[z^2,p]^2,p],p];
	z = Mod[2 y z, p];
	y2 = Mod[y^2,p];
	s = Mod[4 x y2,p]; 
	x = Mod[m^2 - 2s,p];
	y = Mod[m(s - x) - 8 y2^2,p];
	Return[{x,y,z}];
];
*/

void
ell_add_proj(point_proj pt0, point_proj pt1, giant a, giant p)
/* pt0 := pt0 + pt1 on the curve. */
{   
	giant x0 = pt0->x, y0 = pt0->y, z0 = pt0->z,
		  x1 = pt1->x, y1 = pt1->y, z1 = pt1->z;
 
	if(isZero(z0)) {
		gtog(x1,x0); gtog(y1,y0); gtog(z1,z0);
		return;
	}
	if(isZero(z1)) return;
	gtog(x0, t1); gtog(y0,t2); gtog(z0, t3);
	gtog(x1, t4); gtog(y1, t5);
	if(!isone(z1)) {
		gtog(z1, t6);
		gtog(t6, t7); squareg(t7); modg(p, t7);
		mulg(t7, t1); modg(p, t1);
		mulg(t6, t7); modg(p, t7);
		mulg(t7, t2); modg(p, t2);
	}
	gtog(t3, t7); squareg(t7); modg(p, t7);
	mulg(t7, t4); modg(p, t4);
	mulg(t3, t7); modg(p, t7);
	mulg(t7, t5); modg(p, t5);
	negg(t4); addg(t1, t4); modg(p, t4);
	negg(t5); addg(t2, t5); modg(p, t5);
	if(isZero(t4)) {
		if(isZero(t5)) {
			ell_double_proj(pt0, a, p);
	    } else {
			itog(1, x0); itog(1, y0); itog(0, z0);
		}
		return;
	}
	addg(t1, t1); subg(t4, t1); modg(p, t1);
	addg(t2, t2); subg(t5, t2); modg(p, t2);
	if(!isone(z1)) {
		mulg(t6, t3); modg(p, t3);
	}
	mulg(t4, t3); modg(p, t3);
	gtog(t4, t7); squareg(t7); modg(p, t7);
	mulg(t7, t4); modg(p, t4);
	mulg(t1, t7); modg(p, t7);
	gtog(t5, t1); squareg(t1); modg(p, t1);
	subg(t7, t1); modg(p, t1);
	subg(t1, t7); subg(t1, t7); modg(p, t7);
	mulg(t7, t5); modg(p, t5);
	mulg(t2, t4); modg(p, t4);
	gtog(t5, t2); subg(t4,t2); modg(p, t2);
	if(t2->n[0] & 1) { /* Test if t2 is odd. */
		addg(p, t2);
	}
	gshiftright(1, t2);
	gtog(t1, x0); gtog(t2, y0); gtog(t3, z0);
}

/*
elladd[pt0_, pt1_] := Block[
	{x0,y0,z0,x1,y1,z1,
	t1,t2,t3,t4,t5,t6,t7},
	x0 = pt0[[1]]; y0 = pt0[[2]]; z0 = pt0[[3]];
	x1 = pt1[[1]]; y1 = pt1[[2]]; z1 = pt1[[3]];
	If[z0 == 0, Return[pt1]];
	If[z1 == 0, Return[pt0]];

	t1 = x0;
	t2 = y0;
	t3 = z0;
	t4 = x1;
	t5 = y1;
	If[(z1 != 1),
		t6 = z1;
		t7 = Mod[t6^2, p];
		t1 = Mod[t1 t7, p];
		t7 = Mod[t6 t7, p];
		t2 = Mod[t2 t7, p];
	];
	t7 = Mod[t3^2, p];
	t4 = Mod[t4 t7, p];
	t7 = Mod[t3 t7, p];
	t5 = Mod[t5 t7, p];
	t4 = Mod[t1-t4, p];
	t5 = Mod[t2 - t5, p];
	If[t4 == 0, If[t5 == 0,
				    Return[elldouble[pt0]],
	   				Return[{1,1,0}]
	   			]
	];
	t1 = Mod[2t1 - t4,p];
	t2 = Mod[2t2 - t5, p];
	If[z1 != 1, t3 = Mod[t3 t6, p]];
	t3 = Mod[t3 t4, p];
	t7 = Mod[t4^2, p];
	t4 = Mod[t4 t7, p];
	t7 = Mod[t1 t7, p];
	t1 = Mod[t5^2, p];
	t1 = Mod[t1-t7, p];
	t7 = Mod[t7 - 2t1, p];
	t5 = Mod[t5 t7, p];
	t4 = Mod[t2 t4, p];
	t2 = Mod[t5-t4, p];
	If[EvenQ[t2], t2 = t2/2, t2 = (p+t2)/2];
	Return[{t1, t2, t3}];
];
*/

void
ell_neg_proj(point_proj pt, giant p)
/* pt := -pt on the curve. */
{
	negg(pt->y); modg(p, pt->y);
}

void
ell_sub_proj(point_proj pt0, point_proj pt1,	giant a, giant p)
/* pt0 := pt0 - pt1 on the curve. */
{
	ell_neg_proj(pt1, p);
	ell_add_proj(pt0, pt1,a,p);
	ell_neg_proj(pt1,p);
}

void
ell_mul_proj(point_proj pt0, point_proj pt1, giant k, giant a, giant p)
/* General elliptic multiplication;
   pt1 := k*pt0 on the curve, 
   with k an arbitrary integer. 
 */
{	
	giant x = pt0->x, y = pt0->y, z = pt0->z,
		  xx = pt1->x, yy = pt1->y, zz = pt1->z;
	int ksign, hlen, klen, b, hb, kb;
    
	if(isZero(k)) {
		itog(1, xx);
		itog(1, yy);
		itog(0, zz);
		return;
	}
    ksign = k->sign;
	if(ksign < 0) negg(k);
	gtog(x,xx); gtog(y,yy); gtog(z,zz);
	gtog(k, t0); addg(t0, t0); addg(k, t0); /* t0 := 3k. */
	hlen = bitlen(t0);
	klen = bitlen(k);
	for(b = hlen-2; b > 0; b--) {
		ell_double_proj(pt1,a,p);
		hb = bitval(t0, b);
		if(b < klen) kb = bitval(k, b); else kb = 0;
		if((hb != 0) && (kb == 0))
			ell_add_proj(pt1, pt0, a, p);
		else if((hb == 0) && (kb !=0))
			ell_sub_proj(pt1, pt0, a, p);
	}
	if(ksign < 0) {
		ell_neg_proj(pt1, p);
		k->sign = -k->sign;
	}
}

/*
elliptic[pt_, k_] := Block[{pt2, hh, kk, hb, kb, lenh, lenk},
	If[k==0, Return[{1,1,0}]];
	hh = Reverse[bitList[3k]];
	kk = Reverse[bitList[k]];
	pt2 = pt;
	lenh = Length[hh];
	lenk = Length[kk];
	Do[
		pt2 = elldouble[pt2];
		hb = hh[[b]];
		If[b <= lenk, kb = kk[[b]], kb = 0];
		If[{hb,kb} == {1,0},
			pt2 = elladd[pt2, pt],
			If[{hb, kb} == {0,1},
			pt2 = ellsub[pt2, pt]]
		]
	   ,{b, lenh-1, 2,-1}
	 ];
	Return[pt2];
];
*/

void
normalize_proj(point_proj pt, giant p)
/* Obtain actual x,y coords via normalization:
   {x,y,z} := {x/z^2, y/z^3, 1}.
 */

{	giant x = pt->x, y = pt->y, z = pt->z;

	if(isZero(z)) {
		itog(1,x); itog(1,y);
		return;
	}
	binvaux(p, z); gtog(z, t1);
	squareg(z); modg(p, z);
	mulg(z, x); modg(p, x);
	mulg(t1, z); mulg(z, y); modg(p, y);
	itog(1, z);
}

/*
normalize[pt_] := Block[{z,z2,z3},
		If[pt[[3]] == 0, Return[pt]];
		z = ellinv[pt[[3]]];
		z2 = Mod[z^2,p];
		z3 = Mod[z z2,p];
		Return[{Mod[pt[[1]] z2, p], Mod[pt[[2]] z3, p], 1}];
		];
*/
				

void
find_point_proj(point_proj pt, giant seed, giant a, giant b, giant p)
/* Starting with seed, finds a random (projective) point {x,y,1} on curve.
 */
{	giant x = pt->x, y = pt->y, z = pt->z;

    modg(p, seed);
    while(1) {
		gtog(seed, x);
		squareg(x); modg(p, x);
		addg(a, x);
		mulg(seed,x); addg(b, x);
		modg(p, x); /* x := seed^3 + a seed + b. */
		if(sqrtmod(p, x)) break;  /* Test if cubic form has root. */
		iaddg(1, seed);
	}
	gtog(x, y);
    gtog(seed,x);
	itog(1, z);
}