onb_integer.c

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

/************************************************************
*															*
*  Implement combinations of math packages to create 		*
*  advanced protocols.  Massy-Omura is first example.		*
*  Nyberg_Rueppel second.									*
*															*
*				Author = Mike Rosing						*
*				 Date  = Jan 4, 1998						*
*															*
*		NR Jan. 9, 1998										*
*															*
************************************************************/

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

extern unsigned long random_seed;
extern void sha_memory();

/*  print out an integer.  input is label string and pointer
	to integer, sends to terminal.
*/

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 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);

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

/*  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);

/*  find random value prime to curve order.  EC curves over
	GF(2^n) are always even  */
	
	random_field( &garbage);
	garbage.e[NUMWORD] |= 1L;
	field_to_int( &garbage, &en);
	int_gcd( &en, &crv_order, &gcd_check);

/*  hunt for value that is relatively prime to curve order  */

	while ( !int_onecmp( &gcd_check))
	{
		int_add( &search, &en, &en);
		int_gcd( &en, &crv_order, &gcd_check);
	}

/*  compute an inverse to complete the pair  */

	mod_inv( &en, &crv_order, &de);
	int_to_field( &en, e);
	int_to_field( &de, d);
}

/*  Massey-Omura secret sharing protocol, sender side.
	Computes an encryption, decryption pair (e, d) and
	embeds data on public curve (Pub_crv).  
	Output is e*Pm and d.
*/

void onb_Massey_Omura_send( Pub_crv, message, send_point, decrypt)
EC_PARAMETER	*Pub_crv;
FIELD2N			*message, *decrypt;
POINT			*send_point;
{
	POINT	msg;
	FIELD2N	e;
	
/*  embed data on given curve.  Change increment or field size to
	ensure trouble free operations.
*/
	opt_embed( message, &Pub_crv->crv, 0, 0, &msg);

/*  create random encryption and decryption pair  */

	gen_MO_pair( Pub_crv, &e, decrypt);

/*  compute point to transmit  */

	elptic_mul( &e, &msg, send_point, &Pub_crv->crv);
}

/*  Massey-Omura secret sharing protocol, receiver side.
	input: senders point (rcv_point), public curve (Pub_crv).
	generates encrypt, decrypt pair,
	output: e*rcv_point (step2), decrypt
*/

void onb_Massey_Omura_rcv( Pub_crv, rcv_point, step2, decrypt)
EC_PARAMETER	*Pub_crv;
POINT			*rcv_point, *step2;
FIELD2N			*decrypt;
{
	FIELD2N	e;
	
/* create encrypt, decrypt pair  */

	gen_MO_pair (Pub_crv, &e, decrypt);

/*  compute point to transmit back  */

	elptic_mul ( &e, rcv_point, step2, &Pub_crv->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 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);
	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( &sig_value, &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 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  */