dss_sha.c

1. 8623L平台

	/* Fixup result in case the modulus was shifted */
	if (mshift) {
		for (i = 2 * pqlen - mlen - 1; i < 2 * pqlen - 1; i++)
			a[i] = (a[i] << mshift) | (a[i + 1] >> (16 - mshift));
		a[2 * pqlen - 1] = a[2 * pqlen - 1] << mshift;
		internal_mod(a, pqlen * 2, m, mlen, NULL, 0);
		for (i = 2 * pqlen - 1; i >= 2 * pqlen - mlen; i--)
			a[i] = (a[i] >> mshift) | (a[i - 1] << (16 - mshift));
	}
	
	/* Copy result to buffer */
	rlen = (mlen < pqlen * 2 ? mlen : pqlen * 2);
	result = newbn(rlen);
	for (i = 0; i < rlen; i++)
		result[result[0] - i] = a[i + 2 * pqlen - rlen];
	while (result[0] > 1 && result[result[0]] == 0)
		result[0]--;
	
	/* Free temporary arrays */
	for (i = 0; i < 2 * pqlen; i++)
		a[i] = 0;
	free(a);
	for (i = 0; i < mlen; i++)
		m[i] = 0;
	free(m);
	for (i = 0; i < pqlen; i++)
		n[i] = 0;
	free(n);
	for (i = 0; i < pqlen; i++)
		o[i] = 0;
	free(o);
	
	return result;
}

/*
 * Non-modular multiplication and addition.
 */
Bignum bigmuladd(Bignum a, Bignum b, Bignum addend)
{
	RMint32 alen = a[0], blen = b[0];
	RMint32 mlen = (alen > blen ? alen : blen);
	RMint32 rlen, i, maxspot;
	RMuint16 *workspace;
	Bignum ret;
	
	/* mlen space for a, mlen space for b, 2*mlen for result */
	workspace = malloc(mlen * 4 * sizeof(RMuint16));
	for (i = 0; i < mlen; i++) {
//		workspace[0 * mlen + i] = (mlen - i <= a[0] ? a[mlen - i] : 0);
		workspace[i] = (mlen - i <= a[0] ? a[mlen - i] : 0);
		workspace[1 * mlen + i] = (mlen - i <= b[0] ? b[mlen - i] : 0);
	}
	
	internal_mul(workspace + 0 * mlen, workspace + 1 * mlen,
	             workspace + 2 * mlen, mlen);
	
	/* now just copy the result back */
	rlen = alen + blen + 1;
	if (addend && rlen <= addend[0])
		rlen = addend[0] + 1;
	ret = newbn(rlen);
	maxspot = 0;
	for (i = 1; i <= ret[0]; i++) {
		ret[i] = (i <= 2 * mlen ? workspace[4 * mlen - i] : 0);
		if (ret[i] != 0)
			maxspot = i;
	}
	ret[0] = maxspot;
	
	/* now add in the addend, if any */
	if (addend) {
		RMuint32 carry = 0;
		for (i = 1; i <= rlen; i++) {
			carry += (i <= ret[0] ? ret[i] : 0);
			carry += (i <= addend[0] ? addend[i] : 0);
			ret[i] = (RMuint16) carry & 0xFFFF;
			carry >>= 16;
			if (ret[i] != 0 && i > maxspot)
				maxspot = i;
		}
	}
	ret[0] = maxspot;
	
	free(workspace);
	
	return ret;
}


/*
 * Compute p % 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.
 * We optionally write out a quotient if 'quotient' is non-NULL.
 * We can avoid writing out the result if 'result' is NULL.
 */
static void bigdivmod(Bignum p, Bignum mod, Bignum result, Bignum quotient)
{
	RMuint16 *n, *m;
	RMint32 mshift;
	RMint32 plen, mlen, i, j;
	
	/* 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;
	}
	
	plen = p[0];
	/* Ensure plen > mlen */
	if (plen <= mlen)
		plen = mlen + 1;
	
	/* Allocate n of size plen, copy p to n */
	n = malloc(plen * sizeof(RMuint16));
	for (j = 0; j < plen; j++)
		n[j] = 0;
	for (j = 1; j <= p[0]; j++)
		n[plen - j] = p[j];
	
	/* Main computation */
	internal_mod(n, plen, m, mlen, quotient, mshift);
	
	/* Fixup result in case the modulus was shifted */
	if (mshift) {
		for (i = plen - mlen - 1; i < plen - 1; i++)
			n[i] = (n[i] << mshift) | (n[i + 1] >> (16 - mshift));
		n[plen - 1] = n[plen - 1] << mshift;
		internal_mod(n, plen, m, mlen, quotient, 0);
		for (i = plen - 1; i >= plen - mlen; i--)
			n[i] = (n[i] >> mshift) | (n[i - 1] << (16 - mshift));
	}
	
	/* Copy result to buffer */
	if (result) {
		for (i = 1; i <= result[0]; i++) {
			RMint32 j = plen - i;
			result[i] = j >= 0 ? n[j] : 0;
		}
	}
	
	/* Free temporary arrays */
	for (i = 0; i < mlen; i++)
		m[i] = 0;
	free(m);
	for (i = 0; i < plen; i++)
		n[i] = 0;
	free(n);
}

/*
 * Modular inverse, using Euclid's extended algorithm.
 */
Bignum modinv(Bignum number, Bignum modulus)
{
	Bignum a = copybn(modulus);
	Bignum b = copybn(number);
	Bignum xp = copybn(Zero);
	Bignum x = copybn(One);
	RMint32 sign = +1;
	
	while (bignum_cmp(b, One) != 0) {
		Bignum t = newbn(b[0]);
		Bignum q = newbn(a[0]);
		bigdivmod(a, b, t, q);
		while (t[0] > 1 && t[t[0]] == 0)
			t[0]--;
		freebn(a);
		a = b;
		b = t;
		t = xp;
		xp = x;
		x = bigmuladd(q, xp, t);
		sign = -sign;
		freebn(t);
		freebn(q);
	}
	
	freebn(b);
	freebn(a);
	freebn(xp);
	
	/* now we know that sign * x == 1, and that x < modulus */
	if (sign < 0) {
		/* set a new x to be modulus - x */
		Bignum newx = newbn(modulus[0]);
		RMuint16 carry = 0;
		RMint32 maxspot = 1;
		RMint32 i;
		
		for (i = 1; i <= newx[0]; i++) {
			RMuint16 aword = (i <= modulus[0] ? modulus[i] : 0);
			RMuint16 bword = (i <= x[0] ? x[i] : 0);
			newx[i] = aword - bword - carry;
			bword = ~bword;
			carry = carry ? (newx[i] >= bword) : (newx[i] > bword);
			if (newx[i] != 0)
				maxspot = i;
		}
		newx[0] = maxspot;
		freebn(x);
		x = newx;
	}
	
	/* and return. */
	return x;
}


Bignum bignum_from_bytes(RMuint8 *data, RMint32 nbytes)
{
	Bignum result;
	RMint32 w, i;
	
	w = (nbytes + 1) / 2;			   /* bytes -> words */
	
	result = newbn(w);
	for (i = 1; i <= w; i++)
		result[i] = 0;
	for (i = nbytes; i--;) {
		RMuint8 byte = *data++;
		if (i & 1)
			result[1 + i / 2] |= byte << 8;
		else
			result[1 + i / 2] |= byte;
	}
	
	while (result[0] > 1 && result[result[0]] == 0)
		result[0]--;
	return result;
}



/*
 * SHA1 hash algorithm. Used in SSH2 as a MAC, and the transform is
 * also used as a 'stirring' function for the PuTTY random number
 * pool. Implemented directly from the specification by Simon
 * Tatham.
 */

/* ----------------------------------------------------------------------
 * Core SHA algorithm: processes 16-word blocks into a message digest.
 */

#define rol(x,y) ( ((x) << (y)) | (((RMuint32)x) >> (32-y)) )

static void RMSHA_Core_Init(RMuint32 h[5])
{
	h[0] = 0x67452301;
	h[1] = 0xefcdab89;
	h[2] = 0x98badcfe;
	h[3] = 0x10325476;
	h[4] = 0xc3d2e1f0;
}

void RMSHATransform(RMuint32 * digest, RMuint32 * block)
{
	RMuint32 w[80];
	RMuint32 a, b, c, d, e;
	RMint32 t;
	
	for (t = 0; t < 16; t++)
		w[t] = block[t];
	
	for (t = 16; t < 80; t++) {
		RMuint32 tmp = w[t - 3] ^ w[t - 8] ^ w[t - 14] ^ w[t - 16];
		w[t] = rol(tmp, 1);
	}
	
	a = digest[0];
	b = digest[1];
	c = digest[2];
	d = digest[3];
	e = digest[4];
	
	for (t = 0; t < 20; t++) {
		RMuint32 tmp =
			rol(a, 5) + ((b & c) | (d & ~b)) + e + w[t] + 0x5a827999;
		e = d;
		d = c;
		c = rol(b, 30);
		b = a;
		a = tmp;
	}
	for (t = 20; t < 40; t++) {
		RMuint32 tmp = rol(a, 5) + (b ^ c ^ d) + e + w[t] + 0x6ed9eba1;
		e = d;
		d = c;
		c = rol(b, 30);
		b = a;
		a = tmp;
	}
	for (t = 40; t < 60; t++) {
		RMuint32 tmp = rol(a,
						 5) + ((b & c) | (b & d) | (c & d)) + e + w[t] +
			0x8f1bbcdc;
		e = d;
		d = c;
		c = rol(b, 30);
		b = a;
		a = tmp;
	}
	for (t = 60; t < 80; t++) {
		RMuint32 tmp = rol(a, 5) + (b ^ c ^ d) + e + w[t] + 0xca62c1d6;
		e = d;
		d = c;
		c = rol(b, 30);
		b = a;
		a = tmp;
	}
	
	digest[0] += a;
	digest[1] += b;
	digest[2] += c;
	digest[3] += d;
	digest[4] += e;
}

/* ----------------------------------------------------------------------
 * Outer SHA algorithm: take an arbitrary length byte string,
 * convert it into 16-word blocks with the prescribed padding at
 * the end, and pass those blocks to the core SHA algorithm.
 */

void RMSHA_Init(RMSHA_State * s)
{
	RMSHA_Core_Init(s->h);
	s->blkused = 0;
	s->lenhi = s->lenlo = 0;
}

void RMSHA_Bytes(RMSHA_State * s, void *p, RMint32 len)
{
	RMuint8 *q = (RMuint8 *) p;
	RMuint32 wordblock[16];
	RMuint32 lenw = len;
	RMint32 i;
	
	/*
	 * Update the length field.
	 */
	s->lenlo += lenw;
	s->lenhi += (s->lenlo < lenw);
	
	if (s->blkused && s->blkused + len < 64) {
		/*
		 * Trivial case: just add to the block.
		 */
		memcpy(s->block + s->blkused, q, len);
		s->blkused += len;
	} else {
		/*
		 * We must complete and process at least one block.
		 */
		while (s->blkused + len >= 64) {
			memcpy(s->block + s->blkused, q, 64 - s->blkused);
			q += 64 - s->blkused;
			len -= 64 - s->blkused;
			/* Now process the block. Gather bytes big-endian into words */
			for (i = 0; i < 16; i++) {
				wordblock[i] =
					(((RMuint32) s->block[i * 4 + 0]) << 24) |
					(((RMuint32) s->block[i * 4 + 1]) << 16) |
					(((RMuint32) s->block[i * 4 + 2]) << 8) |
					(((RMuint32) s->block[i * 4 + 3]) << 0);
			}
			RMSHATransform(s->h, wordblock);
			s->blkused = 0;
		}
		memcpy(s->block, q, len);
		s->blkused = len;
	}
}

void RMSHA_Final(RMSHA_State * s, RMuint8 *output)
{
	RMint32 i;
	RMint32 pad;
	RMuint8 c[64];
	RMuint32 lenhi, lenlo;
	
	if (s->blkused >= 56)
		pad = 56 + 64 - s->blkused;
	else
		pad = 56 - s->blkused;
	
	lenhi = (s->lenhi << 3) | (s->lenlo >> (32 - 3));
	lenlo = (s->lenlo << 3);
	
	memset(c, 0, pad);
	c[0] = 0x80;
	RMSHA_Bytes(s, &c, pad);
	
	c[0] = (lenhi >> 24) & 0xFF;
	c[1] = (lenhi >> 16) & 0xFF;
	c[2] = (lenhi >> 8) & 0xFF;
	c[3] = (lenhi >> 0) & 0xFF;
	c[4] = (lenlo >> 24) & 0xFF;
	c[5] = (lenlo >> 16) & 0xFF;
	c[6] = (lenlo >> 8) & 0xFF;
	c[7] = (lenlo >> 0) & 0xFF;
	
	RMSHA_Bytes(s, &c, 8);
	
	for (i = 0; i < 5; i++) {
		output[i * 4] = (s->h[i] >> 24) & 0xFF;
		output[i * 4 + 1] = (s->h[i] >> 16) & 0xFF;
		output[i * 4 + 2] = (s->h[i] >> 8) & 0xFF;
		output[i * 4 + 3] = (s->h[i]) & 0xFF;
	}
}

void RMSHA_Simple(void *p, RMint32 len, RMuint8 *output)
{
	RMSHA_State s;
	
	RMSHA_Init(&s);
	RMSHA_Bytes(&s, p, len);
	RMSHA_Final(&s, output);
}