pgpshamir.c

pgp soucecode pgp soucecode

		f_log[0] = i;	/* Bogus value, FIELD_SIZE-1 */
	}
}

#endif	/* PGP_STATIC_SHAMIR_ARRAYS */

/*
 * This is the core of secret sharing.  This computes the coefficients
 * used in Lagrange polynomial interpolation, returning the
 * vector of logarithms of b1(xtarget), b2(xtarget), ..., bn(xtarget).
 * Takes values from the "xCoordinate" header element, inserts the
 * results in the "lagrange" header element.
 * The interpolation values come from the headers of the "shares" array,
 * plus one additional value, xInput, which is the value we are going
 * to interpolate to.
 * 
 * Returns kPGPError_OK on success, error if not all x[i] are unique.
 */
	static PGPError
sInterp(PGPByte *shares, PGPSize bodySize, PGPByte xInput, PGPUInt32 nShares)
{
	PGPUInt32		i, j;
	PGPByte			xi, xj;
	PGPUInt32		numer, denom;

#if !PGP_STATIC_SHAMIR_ARRAYS
	s_FSetup();
#endif /* !PGP_STATIC_SHAMIR_ARRAYS */

	/* First, accumulate the numerator, Prod(xInput-x[i],i=0..n) */
	numer = 0;
	for (i = 0; i < nShares; i++)
	{
		xi = HEADER(shares,bodySize,i)->xCoordinate;
		numer += f_log[ f_sub(xi, xInput) ];
	}
	/* Preliminary partial reduction */
	numer = (numer%FIELD_SIZE) + (numer/FIELD_SIZE);

	/* Then, for each coefficient, compute the corresponding denominator */
	for (i = 0; i < nShares; i++) {
		xi = HEADER(shares,bodySize,i)->xCoordinate;
		denom = 0;
		for (j = 0; j < nShares; j++) {
			xj = (i == j) ? xInput : HEADER(shares,bodySize,j)->xCoordinate;
			if (xi == xj)
				return -1;
			denom += f_log[f_sub(xi,xj)];
		}
		denom = (denom%FIELD_SIZE)+(denom/FIELD_SIZE);
		/* 0 <= denom < 2*FIELD_SIZE-1. */

		/* Now find numer/denom.  In log form, that's a subtract. */
		denom = numer + 2*FIELD_SIZE-2 - denom;
		denom = (denom%FIELD_SIZE)+(denom/FIELD_SIZE);
		denom = (denom%FIELD_SIZE)+(denom/FIELD_SIZE);

		HEADER(shares,bodySize,i)->lagrange = (PGPByte)denom;
	}
	return kPGPError_NoErr;	/* Success */
}



/*
 * This actually does the interpolation, using the coefficients
 * computed by sInterp().  Uses shares at offset byteNumber within the
 * bodies.
 * The Lagrange values come from the headers of the "shares" array.
 */
	static PGPByte
sDoInterp(PGPByte *shares, PGPSize bodySize, PGPUInt32 nShares,
	PGPUInt32 byteNumber)
{
	PGPByte x, y;
	PGPByte lagrange;
	PGPUInt32 i;

	x = 0;
	for( i=0; i < nShares; ++i )
	{
		y = BODY(shares, bodySize, i)[byteNumber];
		if (y != 0)
		{
			lagrange = HEADER(shares, bodySize, i)->lagrange;
			y = f_exp[lagrange + f_log[y]];
		}
		x = f_add(x,y);
	}

	return x;
}



	PGPError
PGPSecretShareData(
	PGPContextRef		context,
	void const *		input,
	PGPSize				inputBytes,
	PGPUInt32			threshold,
	PGPUInt32			nShares,
	void *				output
	)
{
	PGPUInt32			i, j;
	PGPByte				xupdate;
	PGPRandomContext	*rng;			/* Random state */

	rng = pgpContextGetX9_17RandomContext( context );

	/* Set X coordinate randomly for each share */
	for( i=0; i<nShares; ++i )
	{
		PGPBoolean xok = FALSE;
		/* Pick a unique, random x coordinate != X0 */
		while( !xok )
		{
			pgpRandomGetBytes( rng,
						   &(HEADER(output,inputBytes,i)->xCoordinate), 1 );
			if( HEADER(output,inputBytes,i)->xCoordinate != X0 )
			{
				for( j=0; j<i; ++j )
				{
					if( HEADER(output,inputBytes,i)->xCoordinate ==
						HEADER(output,inputBytes,j)->xCoordinate )
						break;
				}
				if( j == i )
				{
					xok = TRUE;
				}
			}
		}
		/* Set other header values as well */
		HEADER(output,inputBytes,i)->version = kPGPShare_Version1;
		HEADER(output,inputBytes,i)->threshold = threshold;
		HEADER(output,inputBytes,i)->lagrange = 0;
	}

	/* Initialize thresh-1 bodies to random numbers */
	for( i=0; i<threshold-1; ++i )
	{
		pgpRandomGetBytes( rng, BODY(output,inputBytes,i), inputBytes );
	}

	/* Copy input to the first share body past the random ones */
	pgpCopyMemory( input, BODY(output,inputBytes,threshold-1), inputBytes );
		
	/* Put X0 into xCoordinate for that header */
	/* xupdate holds the X value for the share we will be updating */
	xupdate = HEADER(output,inputBytes,threshold-1)->xCoordinate;
	HEADER(output,inputBytes,threshold-1)->xCoordinate = X0;

	/*
	 * Now set each of the remaining bodies via interpolation.
	 * Work from last to threshold-1 so we can leave our input copy in
	 * the threshold slot.
	 */
	for( i=nShares-1; i!=threshold-2; --i )
	{
		PGPByte tmp;

		/* Interpolate to that value */
		sInterp( (unsigned char *) output, inputBytes, xupdate, threshold );
		for( j=0; j<inputBytes; ++j )
		{
			BODY(output, inputBytes, i)[j] =
				sDoInterp( (unsigned char *) output, inputBytes, threshold, j );
		}
		/* Swap in xupdate value for share we just calculated */
		tmp = HEADER(output,inputBytes,i)->xCoordinate;
		HEADER(output,inputBytes,i)->xCoordinate = xupdate;
		xupdate = tmp;
	}

	/* Zero lagrange values, were just temporary */
	for( i=0; i<nShares; ++i )
	{
		HEADER(output,inputBytes,i)->lagrange = 0;
	}
	return kPGPError_NoErr;
}


	PGPError
PGPSecretReconstructData(
	PGPContextRef		context,
	void *				input,
	PGPSize				outputBytes,
	PGPUInt32			nShares,
	void *				output
	)
{
	PGPUInt32			i, j;
	PGPByte				threshold;
	PGPError			err = kPGPError_NoErr;

	(void) context;

	/* Verify version and threshold consistency */
	threshold = HEADER(input,outputBytes,0)->threshold;

	for( i=0; i<nShares; ++i )
	{
		if( HEADER(input,outputBytes,i)->version != kPGPShare_Version1 )
		{
			pgpDebugMsg( "Error: invalid Reconstruction version" );
			err = kPGPError_BadParams;
			goto error;
		}
		if( HEADER(input,outputBytes,i)->threshold != threshold )
		{
			pgpDebugMsg( "Error: inconsistent threshold in reconstruction" );
			err = kPGPError_BadParams;
			goto error;
		}
	}

	/* Make sure we have enough shares */
	if (nShares < threshold)
	{
		pgpDebugMsg( "Error: insufficient shares in reconstruction" );
		err = kPGPError_BadParams;
		goto error;
	}

	/* Set up Lagrange coefficients to interpolate to x=X0 */
	sInterp( (unsigned char *) input, outputBytes, X0, threshold );

	/* For each byte j, interpolate to output[j] using coordinates */
	for( j=0; j<outputBytes; ++j )
	{
		((PGPByte *)output)[j] =
				sDoInterp( (PGPByte *)input, outputBytes, threshold, j );
	}
	
	/* Zero lagrange values, were just temporary */
	for( i=0; i<nShares; ++i )
	{
		HEADER(input,outputBytes,i)->lagrange = 0;
	}

error:

	return err;
}




/*__Editor_settings____

	Local Variables:
	tab-width: 4
	End:
	vi: ts=4 sw=4
	vim: si
_____________________*/