poly_integer.c

来自「ECC的C++源码」· C语言 代码 · 共 575 行 · 第 1/2 页

/****************************************************************
*																*
*		Combine polynomial math package with integer math		*
*  routines to create advanced elliptic curve protocols based	*
*  on IEEE P1363 standard.										*
*																*
****************************************************************/

#include <stdio.h>
#include "bigint.h"
#include "poly.h"
#include "eliptic.h"
#include "protocols.h"

extern FIELD2N poly_prime;
extern void sha_memory();
extern unsigned long random_seed;

void print_int( string, number)
char	*string;
BIGINT	*number;
{
	char	teststring[MAXSTRING], outchar[2*MAXSTRING];
	

	bigint_to_ascii(number, teststring);
	sprintf(outchar, "%s\n%s\n", string, teststring);
	printf("%s\n", outchar);
}
	
/*  function to compare BIGINT value to 1.
	Returns 1 if it is, 0 otherwise.
*/

INDEX int_onecmp( number)
BIGINT *number;
{
	INDEX	i;
	
	if ( number->hw[INTMAX] > 1) return (0);
	for ( i=0; i<INTMAX; i++)
		if ( number->hw[i]) return (0);
	if (number->hw[INTMAX]) return (1);
	return (0);
}

/*  Generate a key pair, a random value plus a point.
	This was called ECKGP for Elliptic Curve Key Generation
	Primitive in an early draft of IEEE P1363.

	Input:  EC parameters including public curve, point,
			point order and cofactor
	
	Output: EC key pair including
			secret key k and random point R = k* base point
*/

void poly_ECKGP( Base, Key)
EC_PARAMETER	*Base;
EC_KEYPAIR		*Key;
{
	BIGINT		key_num, point_order, quotient, remainder;
	FIELD2N		rand_key;
	
/*  ensure random value is less than point order  */
	
	random_field( &rand_key);
	field_to_int( &rand_key, &key_num);
	field_to_int( &Base->pnt_order, &point_order);
	int_div( &key_num, &point_order, &quotient, &remainder);
	int_to_field( &remainder, &Key->prvt_key);

	poly_elptic_mul( &Key->prvt_key, &Base->pnt, &Key->pblc_key, &Base->crv);
}

/*  Subroutine to compute hash of a message and return the result 
	as an integer.  Used in all signature schemes.
	
	Enter with pointer to message, message length
*/

void hash_to_int( Message, length, hash_value)
char 			*Message;
unsigned long 	length;
BIGINT			*hash_value;		/*  then to an integer  */
{
	unsigned long	message_digest[5];	/*  from SHA-1 hash function  */
	FIELD2N		 	mdtemp;			/*  convert to NUMBITS size (if needed)  */
	INDEX			i, count;
	
/*  compute hash of input message  */

	sha_memory(	Message, length, message_digest);

/*  convert message digest into an integer */

	null ( &mdtemp);
	count = 0;
	SUMLOOP (i)
	{
		mdtemp.e[ NUMWORD - i] = message_digest[ 4 - i];
		count++;
		if (count > 4) break;
	}
	mdtemp.e[0] &= UPRMASK;
	field_to_int( &mdtemp, hash_value);
}
	
/*  Implement Nyberg-Rueppel signature scheme described in IEEE P1363 draft
	standard of August 1997.  This uses SHA-1 as the hash algorithm on the
	message.  Inputs are a pointer to Message, public elliptic curve parameters
	including the order of the curve, and the signers secret key for signing, 
	or public key for verification.
*/

/*  Nyberg-Rueppel elliptic curve signature scheme.

	Inputs: pointer to Message to be signed and its length,
			pointer to elliptic curve parameters,
			pointer to signer's secret key,
			pointer to signature storage area.
			
	Output: fills signature storage area with 2 numbers
			first number = SHA(Message) + random value
			second number = random value - signer's secret key times first number
					both are done modulo base point order
			
			The output is converted back to FIELD2N variables to save space
			and to make verification easier.
*/

void poly_NR_Signature( Message, length, public_curve, secret_key, signature)
char *Message;
unsigned long length;
EC_PARAMETER *public_curve;
FIELD2N *secret_key;
SIGNATURE *signature;
{
	BIGINT			hash_value;
	FIELD2N			random_value;
	POINT			random_point;
	BIGINT			x_value, k_value, sig_value;
	BIGINT			temp, quotient;
	BIGINT			key_value, point_order;
	INDEX			i, count;

/*  compute hash of input message  */

	hash_to_int( Message, length, &temp);
	field_to_int( &public_curve->pnt_order, &point_order);
	int_div( &temp, &point_order, &quotient, &hash_value);
	
/*  create random value and generate random point on public curve  */

	random_field( &random_value);
	poly_elptic_mul( &random_value, &public_curve->pnt, 
					&random_point, &public_curve->crv);
		
/*  convert x component of random point to an integer and add to message
	digest modulo the order of the base point.
*/

	field_to_int( &random_point.x, &x_value);
	int_add( &x_value, &hash_value, &temp);

	int_div( &temp, &point_order, &quotient, &sig_value);
	int_to_field( &sig_value, &signature->c);

/*  final step is to combine signer's secret key with random value  
		second number = random value - secret key * first number
		modulo order of base point
*/

	field_to_int( &random_value, &k_value);
	field_to_int( secret_key, &key_value);
	int_mul( &key_value, &sig_value, &temp);
	int_div( &temp, &point_order, &quotient, &sig_value);
	
	int_sub( &k_value, &sig_value, &sig_value);
	while( sig_value.hw[0] & 0x8000) 
		int_add( &point_order, &sig_value, &sig_value);
	int_div( &sig_value, &point_order, &quotient, &temp);
	int_to_field( &temp, &signature->d);
}

/*  verify a signature of a message using Nyberg-Rueppel scheme.

	Inputs:	Message to be verified of given length,
			elliptic curve parameters public_curve 
			signer's public key (as a point),
			signature block.
	
	Output: value 1 if signature verifies,
			value 0 if failure to verify.
*/

int poly_NR_Verify( Message, length, public_curve, signer_point, signature)
char			*Message;
unsigned long 	length;
EC_PARAMETER	*public_curve;
POINT			*signer_point;
SIGNATURE		*signature;
{
	BIGINT			hash_value;
	POINT			Temp1, Temp2, Verify;
	BIGINT			x_value, c_value;
	BIGINT			temp, quotient;
	BIGINT			check_value, point_order;
	INDEX			i, count;
	
/*  find hidden point from public data  */

	poly_elptic_mul( &signature->d, &public_curve->pnt, 
						&Temp1, &public_curve->crv);
	poly_elptic_mul( &signature->c, signer_point, 
						&Temp2, &public_curve->crv);
	poly_esum( &Temp1, &Temp2, &Verify, &public_curve->crv);
	
/*  convert x value of verify point to an integer 
	and first signature value too  */

	field_to_int( &Verify.x, &x_value);
	field_to_int( &signature->c, &c_value);

/*  compute resultant message digest from original signature  */

	field_to_int( &public_curve->pnt_order, &point_order);
	int_sub( &c_value, &x_value, &temp);
	while( temp.hw[0] & 0x8000) 			/* ensure positive result */
		int_add( &point_order, &temp, &temp);
	int_div( &temp, &point_order, &quotient, &check_value);

/*  generate hash of message and compare to original signature  */

	hash_to_int( Message, length, &temp);
	int_div( &temp, &point_order, &quotient, &hash_value);
	
	int_null(&temp);
	int_sub( &hash_value, &check_value, &temp);
	while( temp.hw[0] & 0x8000) 		/*  ensure positive zero */
		int_add( &point_order, &temp, &temp);

/*  return error if result of subtraction is not zero  */

	INTLOOP(i) if (temp.hw[i]) return(0);  
	return(1);
}

/*  Massey-Omura protocol subroutines include gen_MO_pair,
	poly_Massey_Omura_send and poly_Massey_Omura_rcv.
	Protocol requires each side to perform several elliptic
	curve multiplies.  These multiplies must eliminate each
	other modulo the order of the base point.  The first
	call to the send routine creates a pair and returns the
	point to transmit as well as the decrypt key.  The receiver
	then calls the rcv routine which generates a pair of
	numbers and returns the point to send back to the sender
	and a decrypt key.  The sender multiplies that point by
	their decrypt key and returns the resultant point.  The
	receiver multiplies by their decrypt key and recovers
	the original message (plus some garbage needed to embed
	the message on the curve).
*/
/*  As required in Massey-Omura protocol, create a number
	and its inverse over known curve order.  Input is
	public EC parameters, output is random e and d
	modulo curve order where ed = 1 mod N
*/

void gen_MO_pair ( Public, e, d)
EC_PARAMETER	*Public;
FIELD2N			*e, *d;
{
	FIELD2N	garbage;
	BIGINT	gcd_check, crv_order, pnt_order, cfactor;
	BIGINT	search, en, de;

/*  since 2 is always a factor, stay odd while hunting  */

	int_null( &search);
	search.hw[INTMAX] = 2;

/*  compute curve order  */

	field_to_int( &Public->pnt_order, &pnt_order);
	field_to_int( &Public->cofactor, &cfactor);
	int_mul( &cfactor, &pnt_order, &crv_order);