randomly + static.c

Elliptic Curve Cryptography full working C code for encryption and decryprion.

#include <stdio.h>


#define WORDSIZE	(sizeof(int)*8)
#define NUMBITS		162
#define TYPE2

#ifdef TYPE2
#define field_prime	((NUMBITS<<1)+1)
#else
#define field_prime (NUMBITS+1)
#endif

#define	NUMWORD		(NUMBITS/WORDSIZE)
#define UPRSHIFT	(NUMBITS%WORDSIZE)
#define MAXLONG		(NUMWORD+1)

#define MAXBITS		(MAXLONG*WORDSIZE)
#define MAXSHIFT	(WORDSIZE-1)
#define MSB			(1L<<MAXSHIFT)

#define UPRBIT		(1L<<(UPRSHIFT-1))
#define UPRMASK		(~(-1L<<UPRSHIFT))
#define SUMLOOP(i)	for(i=0; i<MAXLONG; i++)

typedef	short int INDEX;

typedef unsigned long ELEMENT;

typedef struct {
	ELEMENT 	e[MAXLONG];
}  FIELD2N;


#define DBLBITS		2*NUMBITS
#define DBLWORD		(DBLBITS/WORDSIZE)
#define	DBLSHIFT	(DBLBITS%WORDSIZE)
#define	MAXDBL		(DBLWORD+1)

#define	DERIVMASK	0x55555555

#define DBLLOOP(i)	for(i=0; i<MAXDBL; i++)

typedef struct {
	ELEMENT		e[MAXDBL];
} DBLFIELD;


#define	HALFSIZE	(WORDSIZE/2)
#define	HIMASK		(-1L<<HALFSIZE)
#define LOMASK		(~HIMASK)
#define CARRY		(1L<<HALFSIZE)
#define MSB_HW		(CARRY>>1)
#define	INTMAX		(4*MAXLONG-1)
#define MAXSTRING	(MAXLONG*WORDSIZE/3)

#define	INTLOOP(i)	for(i=INTMAX;i>=0;i--)

typedef struct {
	ELEMENT		hw[4*MAXLONG];
}  BIGINT;


//*                                                               *
//*       These are structures used to create elliptic curve      *
//*  points and parameters.  "form" is a just a fast way to check *
//*  if a2 == 0.                                                  *
//*               form            equation                        *
//*                                                               *
//*                0              y^2 + xy = x^3 + a_6            *
//*                1              y^2 + xy = x^3 + a_2*x^2 + a_6  *  


typedef struct 
{
        INDEX   form;
        FIELD2N  a2;
        FIELD2N  a6;
} CURVE;


typedef struct 
{
        FIELD2N  x;
        FIELD2N  y;
} POINT;


void int_null( a)
BIGINT *a;
{
	INDEX i;
	
	INTLOOP (i) a->hw[i] = 0;
}

/*  copy one BIGINT block to another  */

void int_copy( a, b)
BIGINT *a, *b;
{
	INDEX i;
	
	INTLOOP (i) b->hw[i] = a->hw[i];
}

void field_to_int( a, b)
FIELD2N *a;
BIGINT *b;
{
	INDEX	i, j;
	
	int_null( b);
	for (i=NUMWORD; i>=0; i--)
	{
		j = INTMAX - ((NUMWORD - i)<<1);
		b->hw[j] = a->e[i] & LOMASK;
		j--;
		b->hw[j] = (a->e[i] & HIMASK) >> HALFSIZE;
	}
}

/*  Pack a BIGINT variable back into a FIELD2N size one.  */

void int_to_field( a, b)
BIGINT *a;
FIELD2N *b;
{
	INDEX i, j;
	
	SUMLOOP(i)
	{
		j = (i + MAXLONG) << 1;
		b->e[i] = a->hw[j+1] | (a->hw[j] << HALFSIZE);
	}
}

/*  Negate a BIGINT in place.  Each half word is complemented, then we add 1  */

void int_neg( a)
BIGINT *a;
{
	INDEX i;
	
	INTLOOP(i) a->hw[i] = ~a->hw[i] & LOMASK;
	INTLOOP(i)
	{
		a->hw[i]++;
		if (a->hw[i] & LOMASK) break;
		a->hw[i] &= LOMASK;
	}
}

void int_add( a, b, c)
BIGINT *a, *b, *c;
{
	INDEX i;
	ELEMENT ec;
	
	ec = 0;
	INTLOOP (i)
	{
	/* add previous carry bit to each term  */
		ec = a->hw[i] + b->hw[i] + (ec >> HALFSIZE);	
		c->hw[i] = ec & LOMASK;
	}
}


void int_sub( a, b, c)
BIGINT *a, *b, *c;
{
	BIGINT negb;
	
	int_copy( b, &negb);
	int_neg( &negb);
	int_add( a, &negb, c);
}


void int_mul( a, b, c)
BIGINT *a, *b, *c;
{
	ELEMENT		ea, eb, mul;
	INDEX		i, j, k;
	BIGINT		sum;
	
	int_null(c);
	
	for ( i = INTMAX; i > INTMAX/2; i--)
	{
		ea = a->hw[i];
		int_null( &sum);
		for ( j = INTMAX; j > INTMAX/2; j--)
		{
			eb = b->hw[j];
			k = i + j - INTMAX;
			mul = ea * eb + sum.hw[k];
			sum.hw[k] = mul & LOMASK;
			sum.hw[k-1] = mul >> HALFSIZE;
		}
		int_add( &sum, c, c);
	}
}


void int_div( top, bottom, quotient, remainder)
BIGINT *top, *bottom, *quotient, *remainder;
{
	BIGINT d, e;
	ELEMENT mask;
	INDEX	l, m, n, i, j;
	
/*  first step, initialize counters to most significant
	bit position in top and bottom.
*/
	int_copy( top, &d);
	int_copy( bottom, &e);
	l = (INTMAX + 1) * HALFSIZE;
	for( i=0; i<=INTMAX; i++)
	{
		if (!d.hw[i]) l -= HALFSIZE;
		else break;
	}
	mask = MSB_HW;
	for ( j=0; j<HALFSIZE; j++)
	{
		if ( !(d.hw[i] & mask))
		{
			l--;
			mask >>= 1;
		}
		else break;
	}

/*  same thing for bottom, compute msb position  */

	m = (INTMAX + 1) * HALFSIZE;
	for( i=0; i<=INTMAX; i++)
	{
		if (!e.hw[i]) m -= HALFSIZE;
		else break;
	}
	mask = MSB_HW;
	for ( j=0; j<HALFSIZE; j++)
	{
		if ( !(e.hw[i] & mask))
		{
			m--;
			mask >>= 1;
		}
		else break;
	}
	
/*  check for error inputs, does not check for zero, so is 
	actually incorrect.
*/
	if (!m)			/*  x/1 = x */
	{
		int_copy( top, quotient);
		int_null( remainder);
		return;
	}
	if (!l | (l<m))			/*  1/x = 0 */
	{
		int_null( quotient);
		int_copy( top, remainder);
		return;
	}

/*  next step, shift bottom over to align msb with top msb  */

	n = l - m;
	i = n;
	while ( i > HALFSIZE )
	{
		for (j=0; j<INTMAX; j++) e.hw[j] = e.hw[j+1];
		i -= HALFSIZE;
		e.hw[INTMAX] = 0;
	}
	mask = 0;
	while ( i > 0 )
	{
		INTLOOP (j)
		{
			e.hw[j] = (e.hw[j] << 1) | mask;
			mask = e.hw[j] & CARRY ? 1 : 0;
			e.hw[j] &= LOMASK;
		}
		i--;
	}


	int_null( quotient);
	while ( n>=0)
	{
		i = INTMAX - l/HALFSIZE;
		j = INTMAX - n/HALFSIZE;
		while ( (d.hw[i] == e.hw[i]) && ( i<INTMAX) ) i++;
		if ( d.hw[i] >= e.hw[i] )
		{
			int_sub( &d, &e, &d);
			mask = 1L << ( n%HALFSIZE );
			quotient->hw[j] |= mask;
		}
		INTLOOP(j)
		{
			if (j) mask = ( e.hw[j-1] & 1) ? CARRY : 0;
			else mask = 0;
			e.hw[j] = (e.hw[j] | mask) >> 1;
		}
		n--;
		l--;
	}
	int_copy ( &d, remainder);
}


void ascii_to_bigint( instring, outhex)
char *instring;
BIGINT *outhex;
{
	ELEMENT	ch;
	BIGINT	ten, digit, temp;
	INDEX	i=0;
	
	int_null( &ten);		/* create decimal multiplier */
	ten.hw[INTMAX] = 0xA;
	int_null( &digit);
	int_null( outhex);
	
	while (ch = *instring++)
	{
		digit.hw[INTMAX] = ch & 0xF;
		int_mul( outhex, &ten, &temp);
		if (digit.hw[INTMAX] > 9) continue;
		int_add( &temp, &digit, outhex);
	}
}

void bigint_to_ascii( inhex, outstring)
BIGINT *inhex;
char *outstring;
{
	BIGINT	top, ten, quotient, remainder;
	ELEMENT	check;
	INDEX	i;

	int_copy( inhex, &top);
	int_null( &ten);		/*  create constant 10 */
	ten.hw[INTMAX] = 0xA;
	for (i=0; i<MAXSTRING; i++) *outstring++ = ' ';  /*  blank fill and null string */
	outstring--;
	*outstring-- = 0;
	
	check = 1;
	while (check)
	{
		int_div( &top, &ten, &quotient, &remainder);
		*outstring-- = remainder.hw[INTMAX] | '0';
		check = 0;
		INTLOOP(i) check |= quotient.hw[i];
		int_copy( &quotient, &top);
	}
}

/////////////////////////////////////////////////////////////////////////////////
/*  divide a large integer by 2.  A simple shift right operation.  */

void int_div2( x)
BIGINT *x;
{
	INDEX j;
	ELEMENT mask;
	
	INTLOOP(j)
	{
		if (j) mask = ( x->hw[j-1] & 1) ? CARRY : 0;
		else mask = 0;
		x->hw[j] = (x->hw[j] | mask) >> 1;
	}
}


void int_gcd(u, v, w)
BIGINT *u, *v, *w;
{
	INDEX  k, i, flag;
	ELEMENT check, carry_bit;
	BIGINT t, U, V;
	
	int_copy( u, &U);
	int_copy( v, &V);
	
/*  find common powers of 2 and eliminate them */

	k = 0;
	
/*  check that both u and v are even */

	while ( !(U.hw[INTMAX] & 1 || V.hw[INTMAX] & 1))   
	{
	/*  increment power of 2 and divide both u and v by 2 */
		k++;					
		int_div2( &U);
		int_div2( &V);
	}
	


	if (U.hw[INTMAX] & 1)
	{
		int_copy( &V, &t);
		flag = -1;
	}
	else 
	{
		int_copy( &U, &t);
		flag = 1;
	}
	
	check = 0;
	INTLOOP (i) check |= t.hw[i];
	while (check)
	{
	/* while t is even, divide by 2  */
	
		while ( !(t.hw[INTMAX] & 1)) int_div2( &t);  

/* reset u or v to t depending on sign of flag  */

		if (flag > 0) int_copy( &t, &U);
		else int_copy( &t, &V);
/*		t = u - v;			  core reduction step, gcd remains unchanged  */
		int_sub( &U, &V, &t);
		if (t.hw[0] & MSB_HW)
		{
			flag = -1;
			int_neg( &t);
		}
		else flag = 1;
		check = 0;
		INTLOOP (i) check |= t.hw[i];
	}

	/*  reapply common powers of 2. First do words, then do bits.*/
	
	int_copy( &U, w);
	while ( k > HALFSIZE )
	{
		for (i=0; i<INTMAX; i++) w->hw[i] = w->hw[i+1];
		k -= HALFSIZE;
		w->hw[INTMAX] = 0;
	}
	carry_bit = 0;
	while ( k > 0 )
	{
		INTLOOP (i)
		{
			w->hw[i] = (w->hw[i] << 1) | carry_bit;
			carry_bit = w->hw[i] & CARRY ? 1 : 0;
			w->hw[i] &= LOMASK;
		}
		k--;
	}
}


void mod_exp(x, n, q, z)
BIGINT *x, *n, *q, *z;
{
	BIGINT  N, Y, Z, temp, dummy;
	ELEMENT check;
	INDEX   i;
	
/*  initialize variables  */

	int_copy (n, &N);
	int_null( &Y);
	Y.hw[INTMAX] = 1;
	int_copy (x, &Z);

/*  Main loop divides N by 2 each step.  Repeat until N = 0, and return Y as result.  */

	check = 0;
	INTLOOP (i) check |= N.hw[i];
	while (check)
	{

/*  if N is odd, multiply by extra factor of Y */

		if (N.hw[INTMAX] & 1) 
		{
			/*  Y = (Y * Z) % q;  */
			int_mul (&Y, &Z, &temp);
			int_div (&temp, q, &dummy, &Y);
		}
		int_div2( &N);					/* divide N by 2 */
	/*		Z = (Z * Z) % q;		  square Z  */
		int_mul (&Z, &Z, &temp);
		int_div( &temp, q, &dummy, &Z);
		check = 0;
		INTLOOP (i) check |= N.hw[i];
	}
	int_copy (&Y, z);
}

void mod_inv(a, b, x)
BIGINT *a, *b, *x;
{
	BIGINT  m, n, p0, p1, p2, q, r, temp, dummy;
	ELEMENT check;
	INDEX   sw, i;
	

	sw = 1;
	int_copy( b, &m);
	int_copy( a, &n);
	int_null ( &p0);
	p0.hw[INTMAX] = 1;
	int_div ( &m, &n, &p1, &r);
	int_copy ( &p1, &q);
	
/*  main loop, compute continued fraction  intermediates  */

	check = 0;
	INTLOOP (i) check |= r.hw[i];
	while (check)
	{
		sw = -sw;
		int_copy( &n, &m);
		int_copy( &r, &n);
		int_div( &m, &n, &q, &r);
 /*		p2 = (q * p1 + p0) % b;   core operation of routine  */
 		int_mul( &q, &p1, &temp);
 		int_add( &temp, &p0, &temp);
 		int_div( &temp, b, &dummy, &p2);
 		int_copy( &p1, &p0);
 		int_copy( &p2, &p1);
		check = 0;
		INTLOOP (i) check |= r.hw[i];
	}
	
/*  sw keeps track of sign.  If sw < 0, add modulus to result */

	if (sw < 0) int_sub( b, &p0, x);
	else int_copy( &p0, x);
}

/////////////////////////////////////////////////////////////////////////////////


//162 bit
FIELD2N  poly_prime = {0x00000004,0x00000000,0x00000000,0x00000000,0x00000000,0x08000001};  
/*FIELD2N  poly_prime = {0x20000000,0x00000000,0x00000005};	/*93*/


void rot_left(a)
FIELD2N *a;
{
        INDEX i;
        ELEMENT bit,temp;

        bit = (a->e[0] & UPRBIT) ? 1L : 0L;
        for (i=NUMWORD; i>=0; i--) {
           temp = (a->e[i] & MSB) ? 1L : 0L;
           a->e[i] = ( a->e[i] << 1) | bit;
           bit = temp;
        }
        a->e[0] &= UPRMASK;
}

void rot_right(a)
FIELD2N *a;
{
        INDEX i;
        ELEMENT bit,temp;

        bit = (a->e[NUMWORD] & 1) ? UPRBIT : 0L;
        SUMLOOP(i) {
           temp = ( a->e[i] >> 1)  | bit;
           bit = (a->e[i] & 1) ? MSB : 0L;
           a->e[i] = temp;
        }
        a->e[0] &= UPRMASK;
}

/*  Shift left one bit used by multiply routine.  Make inline for speed.  */

void mul_shift(a)
DBLFIELD *a;
{
	ELEMENT	*eptr, temp, bit;	/* eptr points to one ELEMENT at a time  */
	INDEX	i;
	
	eptr = &a->e[DBLWORD];		/* point to end, note: bigendian processing  */
	bit = 0;					/*  initial carry bit is clear */
	DBLLOOP (i)
	{
		temp = (*eptr << 1) | bit;		/* compute result as temporary  */
		bit = (*eptr & MSB) ? 1L : 0L;	/* get carry bit from shift  */
		*eptr-- = temp;					/* save new result  */
	}
}

/*  null out a FIELD2N variable.  Make inline for speed.  */

void null(a)
FIELD2N *a;
{
	INDEX i;
	
	SUMLOOP(i) a->e[i] = 0L;
}

void dblnull(a)
DBLFIELD *a;
{
	INDEX i;
	
	DBLLOOP(i) a->e[i] = 0L;
}

/*  copy one FIELD2N variable to another.  Make inline for speed.  */

void copy(from, to)
FIELD2N *from, *to;
{
	INDEX	i;
	
	SUMLOOP(i) to->e[i] = from->e[i];
}

/*  copy a FIELD2N variable into a DBLFIELD variable */

void sngltodbl(from, to)
FIELD2N *from;
DBLFIELD *to;
{
	INDEX i;
	
	dblnull (to);
	SUMLOOP(i) to->e[DBLWORD - NUMWORD + i] = from->e[i];
}


void dbltosngl(from, to)
FIELD2N *to;
DBLFIELD *from;
{
	INDEX i;
	
	SUMLOOP(i) to->e[i] = from->e[DBLWORD - NUMWORD + i];
}


void poly_mul_partial(a, b, c)
FIELD2N *a, *b;
DBLFIELD *c;
{
	INDEX i, bit_count, word;
	ELEMENT mask;
	DBLFIELD B;
	
/*  clear all bits in result  */

	dblnull(c);
	
/*  initialize local copy of b so we can shift it  */

	sngltodbl(b, &B);
	
/*  for every bit in 'a' that is set, add present B to result  */

	mask = 1;
	for (bit_count=0; bit_count<NUMBITS; bit_count++)
	{
		word = NUMWORD - bit_count/WORDSIZE;
		if (mask & a->e[word])
		{
			DBLLOOP(i) c->e[i] ^= B.e[i];
		}
		mul_shift( &B);			/* multiply copy of b by x  */
		mask <<= 1;				/* shift mask bit up  */
		if (!mask) mask = 1;	/* when it goes to zero, reset to 1  */
	}
}

void div_shift(a)
DBLFIELD *a;
{
	ELEMENT	*eptr, temp, bit;
	INDEX	i;
	
	eptr = (ELEMENT*) &a->e[0];
	bit = 0;
	DBLLOOP (i)
	{
		temp = (*eptr>>1) | bit;		/*  same as shift left but  */
		bit = (*eptr & 1) ? MSB : 0L;	/*  carry bit goes off other end  */
		*eptr++ = temp;
	}
}

/*  binary search for most significant bit within word */

INDEX log_2 (x)
ELEMENT x;
{
	ELEMENT ebit, bitsave, bitmask;