dss_sha.c

1. 8623L平台

/*
 * samples/dss_sha.c
 *
 * Copyright (c) 2001-2004 Sigma Designs, Inc. 
 * All Rights Reserved. Proprietary and Confidential.
 *
 */
 
/**
  @file samples/dss_sha.c
  @brief DSS/SHA1 signature check
   
  @author Christian Wolff (based on code from SiliconImage, based on code from PuTTY SSH client)
*/

/*

PuTTY is copyright 1997-2001 Simon Tatham.

Portions copyright Robert de Bath, Joris van Rantwijk, Delian Delchev,
Andreas Schultz, Jeroen Massar, Wez Furlong, Nicolas Barry, and CORE SDI S.A.
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"),
to deal in the Software without restriction, including without limitation
he rights to use, copy, modify, merge, publish, distribute, sublicense,
and/or sell copies of the Software, and to permit persons to whom the Software
is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included
in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL SIMON TATHAM BE LIABLE FOR ANY CLAIM, DAMAGES
OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN THE SOFTWARE.

*/
/*
   Adoptation sowtware for demostration of verification DSS ( FIPS PUB 186-2 )
   used test values APPENDIX 5. EXAMPLE OF THE DSA
   pages 21-23
*/



/*
 * Bignum routines for RSA and DH and stuff.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ALLOW_OS_CODE 1
#include "../rua/include/rua.h"

#include "dss_sha.h"

/*
 * Useful thing.
 */
#ifndef lenof
#define lenof(x) ( (sizeof((x))) / (sizeof(*(x))))
#endif


/*
 * Bignum routines for RSA and DH and stuff.
 */

RMuint16 bnZero[1] = { 0 };
RMuint16 bnOne[2] = { 1, 1 };

/*
 * The Bignum format is an array of 'unsigned short'. The first
 * element of the array counts the remaining elements. The
 * remaining elements express the actual number, base 2^16, _least_
 * significant digit first. (So it's trivial to extract the bit
 * with value 2^n for any n.)
 *													  fopen
 * All Bignums in this module are positive. Negative numbers must
 * be dealt with outside it.
 *
 * INVARIANT: the most significant word of any Bignum must be
 * nonzero.
 */

Bignum Zero = bnZero, One = bnOne;

/*************************************************************************/
static Bignum newbn(RMint32 length)
{
	Bignum b = malloc((length + 1) * sizeof(RMuint16));
	if (!b)
		abort();					   /* FIXME */
	memset(b, 0, (length + 1) * sizeof(*b));
	b[0] = length;
	return b;
}

/*************************************************************************/
Bignum copybn(Bignum orig)
{
	Bignum b = malloc((orig[0] + 1) * sizeof(RMuint16));
	if (!b)
		abort();					   /* FIXME */
	memcpy(b, orig, (orig[0] + 1) * sizeof(*b));
	return b;
}

/************************************************************************/
void freebn(Bignum b)
{
	/*
	 * Burn the evidence, just in case.
	 */
	memset(b, 0, sizeof(b[0]) * (b[0] + 1));
	free(b);
}

/*
 * Compare two bignums. Returns like strcmp.
 */
RMint32 bignum_cmp(Bignum a, Bignum b)
{
	RMint32 amax = a[0], bmax = b[0];
	RMint32 i = (amax > bmax ? amax : bmax);
	while (i) {
		RMuint16 aval = (i > amax ? 0 : a[i]);
		RMuint16 bval = (i > bmax ? 0 : b[i]);
		if (aval < bval)
			return -1;
		if (aval > bval)
			return +1;
		i--;
	}
	return 0;
}
/******************************************************************************/
static void internal_add_shifted(
	RMuint16 *number,
	unsigned n, RMint32 shift)
{
	RMint32 word = 1 + (shift / 16);
	RMint32 bshift = shift % 16;
	RMuint32 addend;
	
	addend = n << bshift;
	
	while (addend) {
		addend += number[word];
		number[word] = (RMuint16) addend & 0xFFFF;
		addend >>= 16;
		word++;
	}
}
/*
 * Compute c = a * b.
 * Input is in the first len words of a and b.
 * Result is returned in the first 2*len words of c.
 */
static void internal_mul(
	RMuint16 *a, RMuint16 *b,
	RMuint16 *c, RMint32 len)
{
	RMint32 i, j;
	RMuint32 ai, t;
	
	for (j = 0; j < 2 * len; j++)
		c[j] = 0;
	
	for (i = len - 1; i >= 0; i--) {
		ai = a[i];
		t = 0;
		for (j = len - 1; j >= 0; j--) {
			t += ai * (RMuint32) b[j];
			t += (RMuint32) c[i + j + 1];
			c[i + j + 1] = (RMuint16) t;
			t = t >> 16;
		}
		c[i] = (RMuint16) t;
	}
}
/******************************************************************************/
/*
 * Compute a = a % m.
 * Input in first alen words of a and first mlen words of m.
 * Output in first alen words of a
 * (of which first alen-mlen words will be zero).
 * The MSW of m MUST have its high bit set.
 * Quotient is accumulated in the 'quotient' array, which is a Bignum
 * rather than the internal bigendian format. Quotient parts are shifted
 * left by 'qshift' before adding into quot.
 */
static void internal_mod(
	RMuint16 *a, RMint32 alen,
	RMuint16 *m, RMint32 mlen,
	RMuint16 *quot, RMint32 qshift)
{
	RMuint16 m0, m1;
	RMuint32 h;
	RMint32 i, k;
	
	m0 = m[0];
	if (mlen > 1)
		m1 = m[1];
	else
		m1 = 0;
	
	for (i = 0; i <= alen - mlen; i++) {
		RMuint32 t;
		RMuint32 q, r, c, ai1;
		
		if (i == 0) {
			h = 0;
		} else {
			h = a[i - 1];
			a[i - 1] = 0;
		}
		
		if (i == alen - 1)
			ai1 = 0;
		else
			ai1 = a[i + 1];
		
		/* Find q = h:a[i] / m0 */
		t = ((RMuint32) h << 16) + a[i];
		q = t / m0;
		r = t % m0;
		
		/* Refine our estimate of q by looking at
		   h:a[i]:a[i+1] / m0:m1 */
		t = (RMint32) m1 *(RMint32) q;
		if (t > ((RMuint32) r << 16) + ai1) {
			q--;
			t -= m1;
			r = (r + m0) & 0xffff;	 /* overflow? */
			if (r >= (RMuint32) m0 &&
				t > ((RMuint32) r << 16) + ai1) q--;
		}
		
		/* Subtract q * m from a[i...] */
		c = 0;
		for (k = mlen - 1; k >= 0; k--) {
			t = (RMint32) q *(RMint32) m[k];
			t += c;
			c = t >> 16;
			if ((RMuint16) t > a[i + k])
				c++;
			a[i + k] -= (RMuint16) t;
		}
		
		/* Add back m in case of borrow */
		if (c != h) {
			t = 0;
			for (k = mlen - 1; k >= 0; k--) {
				t += m[k];
				t += a[i + k];
				a[i + k] = (RMuint16) t;
				t = t >> 16;
			}
			q--;
		}
		if (quot)
			internal_add_shifted(quot, q, qshift + 16 * (alen - mlen - i));
	}
}
/******************************************************************************/
/*
 * Compute (base ^ exp) % mod.
 * The base MUST be smaller than the modulus.
 * The most significant word of mod MUST be non-zero.
 * We assume that the result array is the same size as the mod array.
 */
Bignum modpow(Bignum base, Bignum exp, Bignum mod)
{
	RMuint16 *a, *b, *n, *m;
	RMint32 mshift;
	RMint32 mlen, i, j;
	Bignum result;
	
	/* Allocate m of size mlen, copy mod to m */
	/* We use big endian internally */
	mlen = mod[0];
	m = malloc(mlen * sizeof(RMuint16));
	for (j = 0; j < mlen; j++)
		m[j] = mod[mod[0] - j];
	
	/* Shift m left to make msb bit set */
	for (mshift = 0; mshift < 15; mshift++)
		if ((m[0] << mshift) & 0x8000)
			break;
	if (mshift) {
		for (i = 0; i < mlen - 1; i++)
			m[i] = (m[i] << mshift) | (m[i + 1] >> (16 - mshift));
		m[mlen - 1] = m[mlen - 1] << mshift;
	}
	
	/* Allocate n of size mlen, copy base to n */
	n = malloc(mlen * sizeof(RMuint16));
	i = mlen - base[0];
	for (j = 0; j < i; j++)
		n[j] = 0;
	for (j = 0; j < base[0]; j++)
		n[i + j] = base[base[0] - j];
	
	/* Allocate a and b of size 2*mlen. Set a = 1 */
	a = malloc(2 * mlen * sizeof(RMuint16));
	b = malloc(2 * mlen * sizeof(RMuint16));
	for (i = 0; i < 2 * mlen; i++)
		a[i] = 0;
	a[2 * mlen - 1] = 1;
	
	/* Skip leading zero bits of exp. */
	i = 0;
	j = 15;
	while (i < exp[0] && (exp[exp[0] - i] & (1 << j)) == 0) {
		j--;
		if (j < 0) {
			i++;
			j = 15;
		}
	}
	
	/* Main computation */
	while (i < exp[0]) {
		while (j >= 0) {
			internal_mul(a + mlen, a + mlen, b, mlen);
			internal_mod(b, mlen * 2, m, mlen, NULL, 0);
			if ((exp[exp[0] - i] & (1 << j)) != 0) {
				internal_mul(b + mlen, n, a, mlen);
				internal_mod(a, mlen * 2, m, mlen, NULL, 0);
			} else {
				RMuint16 *t;
				t = a;
				a = b;
				b = t;
			}
			j--;
		}
		i++;
		j = 15;
	}
	
	/* Fixup result in case the modulus was shifted */
	if (mshift) {
		for (i = mlen - 1; i < 2 * mlen - 1; i++)
			a[i] = (a[i] << mshift) | (a[i + 1] >> (16 - mshift));
		a[2 * mlen - 1] = a[2 * mlen - 1] << mshift;
		internal_mod(a, mlen * 2, m, mlen, NULL, 0);
		for (i = 2 * mlen - 1; i >= mlen; i--)
			a[i] = (a[i] >> mshift) | (a[i - 1] << (16 - mshift));
	}
	
	/* Copy result to buffer */
	result = newbn(mod[0]);
	for (i = 0; i < mlen; i++)
		result[result[0] - i] = a[i + mlen];
	while (result[0] > 1 && result[result[0]] == 0)
		result[0]--;
	
	/* Free temporary arrays */
	for (i = 0; i < 2 * mlen; i++)
		a[i] = 0;
	free(a);
	for (i = 0; i < 2 * mlen; i++)
		b[i] = 0;
	free(b);
	for (i = 0; i < mlen; i++)
		m[i] = 0;
	free(m);
	for (i = 0; i < mlen; i++)
		n[i] = 0;
	free(n);
	
	return result;
}

/******************************************************************************/
/*
 * Compute (p * q) % mod.
 * The most significant word of mod MUST be non-zero.
 * We assume that the result array is the same size as the mod array.
 */
Bignum modmul(Bignum p, Bignum q, Bignum mod)
{
	RMuint16 *a, *n, *m, *o;
	RMint32 mshift;
	RMint32 pqlen, mlen, rlen, i, j;
	Bignum result;
	
	/* Allocate m of size mlen, copy mod to m */
	/* We use big endian internally */
	mlen = mod[0];
	m = malloc(mlen * sizeof(RMuint16));
	for (j = 0; j < mlen; j++)
		m[j] = mod[mod[0] - j];
	
	/* Shift m left to make msb bit set */
	for (mshift = 0; mshift < 15; mshift++)
		if ((m[0] << mshift) & 0x8000)
			break;
	if (mshift) {
		for (i = 0; i < mlen - 1; i++)
			m[i] = (m[i] << mshift) | (m[i + 1] >> (16 - mshift));
		m[mlen - 1] = m[mlen - 1] << mshift;
	}
	
	pqlen = (p[0] > q[0] ? p[0] : q[0]);
	
	/* Allocate n of size pqlen, copy p to n */
	n = malloc(pqlen * sizeof(RMuint16));
	i = pqlen - p[0];
	for (j = 0; j < i; j++)
		n[j] = 0;
	for (j = 0; j < p[0]; j++)
		n[i + j] = p[p[0] - j];
	
	/* Allocate o of size pqlen, copy q to o */
	o = malloc(pqlen * sizeof(RMuint16));
	i = pqlen - q[0];
	for (j = 0; j < i; j++)
		o[j] = 0;
	for (j = 0; j < q[0]; j++)
		o[i + j] = q[q[0] - j];
	
	/* Allocate a of size 2*pqlen for result */
	a = malloc(2 * pqlen * sizeof(RMuint16));
	
	/* Main computation */
	internal_mul(n, o, a, pqlen);
	internal_mod(a, pqlen * 2, m, mlen, NULL, 0);