rsa.c

linux下从网卡远程启动

        for (j = 0; j < ciBits; j += 2, ci <<= 2) {
        /* Compute t = t^4 * b^s mod d, where s = two MSB's of ci. */
            NN_ModMult (t, t, t, d, dDigits);
            NN_ModMult (t, t, t, d, dDigits);
            if ((s = DIGIT_2MSB (ci)) != 0)
            NN_ModMult (t, t, bPower[s-1], d, dDigits);
        }
    }
	NN_Assign (a, t, dDigits);
}

/* Compute a = 1/b mod c, assuming inverse exists.
   Lengths: a[digits], b[digits], c[digits].
	 Assumes gcd (b, c) = 1, digits < MAX_NN_DIGITS.
 */
void NN_ModInv (a, b, c, digits)
NN_DIGIT *a, *b, *c;
unsigned int digits;
{
    NN_DIGIT q[MAX_NN_DIGITS], t1[MAX_NN_DIGITS], t3[MAX_NN_DIGITS],
		u1[MAX_NN_DIGITS], u3[MAX_NN_DIGITS], v1[MAX_NN_DIGITS],
		v3[MAX_NN_DIGITS], w[2*MAX_NN_DIGITS];
    int u1Sign;
    /* Apply extended Euclidean algorithm, modified to avoid negative
       numbers.
    */
    NN_ASSIGN_DIGIT (u1, 1, digits);
	NN_AssignZero (v1, digits);
    NN_Assign (u3, b, digits);
	NN_Assign (v3, c, digits);
    u1Sign = 1;
	while (! NN_Zero (v3, digits)) {
        NN_Div (q, t3, u3, digits, v3, digits);
        NN_Mult (w, q, v1, digits);
		NN_Add (t1, u1, w, digits);
        NN_Assign (u1, v1, digits);
		NN_Assign (v1, t1, digits);
		NN_Assign (u3, v3, digits);
		NN_Assign (v3, t3, digits);
		u1Sign = -u1Sign;
	}
    /* Negate result if sign is negative. */
	if (u1Sign < 0)	NN_Sub (a, c, u1, digits); else	NN_Assign (a, u1, digits);
}
/* Computes a = gcd(b, c).
	 Assumes b > c, digits < MAX_NN_DIGITS.
*/
#define iplus1  ( i==2 ? 0 : i+1 )      /* used by Euclid algorithms */
#define iminus1 ( i==0 ? 2 : i-1 )      /* used by Euclid algorithms */
#define g(i) (  &(t[i][0])  )
void NN_Gcd(a ,b ,c, digits) NN_DIGIT *a, *b, *c; unsigned int digits;
{
	short i; NN_DIGIT t[3][MAX_NN_DIGITS];
	NN_Assign(g(0), c, digits);
	NN_Assign(g(1), b, digits);
	i=1;
	while(!NN_Zero(g(i),digits)) {
		NN_Mod(g(iplus1), g(iminus1), digits, g(i), digits);
		i = iplus1;
	}
	NN_Assign(a , g(iminus1), digits);
}
/* Returns the significant length of a in bits.
	 Lengths: a[digits]. */
unsigned int NN_Bits (a, digits) NN_DIGIT *a;
unsigned int digits;
{
	if ((digits = NN_Digits (a, digits)) == 0)
		return (0);
	return ((digits - 1) * NN_DIGIT_BITS + NN_DigitBits (a[digits-1]));
}
#ifndef USEASM
/* Returns sign of a - b. */
int NN_Cmp (a, b, digits)
NN_DIGIT *a, *b;
unsigned int digits;
{
	if(digits) {
		do {
			digits--;
			if(*(a+digits) > *(b+digits))
				return(1);
			if(*(a+digits) < *(b+digits))
				return(-1);
		}while(digits);
	}
	return (0);
}
/* Returns nonzero iff a is zero. */
int NN_Zero (a, digits)
NN_DIGIT *a;
unsigned int digits;
{
	if(digits) {
		do {
			if(*a++)
				return(0);
		}while(--digits);
	}
	return (1);
}
/* Assigns a = b. */
void NN_Assign (a, b, digits)
NN_DIGIT *a, *b;
unsigned int digits;
{
	if(digits) {
		do {
			*a++ = *b++;
		}while(--digits);
	}
}
/* Returns the significant length of a in digits. */
unsigned int NN_Digits (a, digits) NN_DIGIT *a; unsigned int digits;
{
	if(digits) {
		digits--;
		do { if(*(a+digits)) break; }while(digits--);
		return(digits + 1);
	}
	return(digits);
}
/* Computes a = b + c. Returns carry.
	 Lengths: a[digits], b[digits], c[digits].
 */
NN_DIGIT NN_Add (a, b, c, digits) NN_DIGIT *a, *b, *c; unsigned int digits;
{
	NN_DIGIT temp, carry = 0;
	if(digits)
		do {
			if((temp = (*b++) + carry) < carry)
				temp = *c++;
            		else {      /* Patch to prevent bug for Sun CC */
               		 if((temp += *c) < *c) carry = 1; else carry = 0;
			 c++;
            		}
			*a++ = temp;
		}while(--digits);
	return (carry);
}
#endif
static NN_DIGIT subdigitmult(a, b, c, d, digits) NN_DIGIT *a, *b, c, *d; unsigned int digits;
{
	NN_DIGIT borrow, thigh, tlow;
	unsigned int i;
	borrow = 0;
	if(c != 0) {
		for(i = 0; i < digits; i++) {
			dmult(c, d[i], &thigh, &tlow);
			if((a[i] = b[i] - borrow) > (MAX_NN_DIGIT - borrow))
				borrow = 1;
			else
				borrow = 0;
			if((a[i] -= tlow) > (MAX_NN_DIGIT - tlow))
				borrow++;
			borrow += thigh;
		}
	}
	return (borrow);
}
/* Returns the significant length of a in bits, where a is a digit. */
static unsigned int NN_DigitBits (a) NN_DIGIT a;
{
	unsigned int i;
	for (i = 0; i < NN_DIGIT_BITS; i++, a >>= 1) if (a == 0) break;
	return (i);
}
/* Computes a * b, result stored in high and low. */
static void dmult( a, b, high, low) NN_DIGIT a, b; NN_DIGIT *high; NN_DIGIT *low;
{
	NN_HALF_DIGIT al, ah, bl, bh;
	NN_DIGIT m1, m2, m, ml, mh, carry = 0;
	al = (NN_HALF_DIGIT)LOW_HALF(a);
	ah = (NN_HALF_DIGIT)HIGH_HALF(a);
	bl = (NN_HALF_DIGIT)LOW_HALF(b);
	bh = (NN_HALF_DIGIT)HIGH_HALF(b);
	*low = (NN_DIGIT) al*bl;
	*high = (NN_DIGIT) ah*bh;
	m1 = (NN_DIGIT) al*bh;
	m2 = (NN_DIGIT) ah*bl;
	m = m1 + m2;
	if(m < m1)
        carry = 1L << (NN_DIGIT_BITS / 2);
	ml = (m & MAX_NN_HALF_DIGIT) << (NN_DIGIT_BITS / 2);
	mh = m >> (NN_DIGIT_BITS / 2);
	*low += ml;
	if(*low < ml) carry++;
	*high += carry + mh;
}
/*****************************************************************************
 *************************************************************** r_stdlib.c */
//BYTE *Copyright[] = { "Copyright (c) J.S.A.Kapp 94-96." };
#ifndef USE_ANSI
/* Secure memset routine */
#ifndef USEASM
void R_memset(output, value, len)
POINTER output;                 /* output block */
int value;                      /* value */
unsigned int len;               /* length of block */
{ if(len != 0) { do { *output++ = (unsigned char)value;	}while(--len != 0); }}
/* Secure memcpy routine */
void R_memcpy(output, input, len)
POINTER output;                 /* output block */
POINTER input;                  /* input block */
unsigned int len;               /* length of blocks */
{ if (len != 0) { do {	*output++ = *input++;	}while (--len != 0); } }
/* Secure memcmp routine */
int R_memcmp(Block1, Block2, len)
POINTER Block1;                 /* first block */
POINTER Block2;                 /* second block */
unsigned int len;               /* length of blocks */
{
	if(len != 0) {
		/* little trick in declaring vars */
		register const unsigned char *p1 = Block1, *p2 = Block2;
		do { if(*p1++ != *p2++)	return(*--p1 - *--p2);	}while(--len != 0);
	}
	return(0);
}
#endif /* USEASM */
#endif /* USE_ANSI */
/*****************************************************************************
 *****************************************************************************
 *****************************************************************************
 *****************************************************************************
 *****************************************************************************
 *****************************************************************************
 *****************************************************************************
 *****************************************************************************
 *****************************************************************************
 *****************************************************************************
 *****************************************************************************
 *****************************************************************************
 *****************************************************************************
 *****************************************************************************
 *****************************************************************************
 *****************************************************************************
 *****************************************************************************
 *****************************************************************************
 *****************************************************************************
 *****************************************************************************
 *****************************************************************************
 *****************************************************************************
 ********************************************************** finish includes */
static int rsapublicfunc PROTO_LIST((unsigned char *, unsigned int *, unsigned char *, unsigned int, R_RSA_PUBLIC_KEY *));
static int rsaprivatefunc PROTO_LIST((unsigned char *, unsigned int *, unsigned char *, unsigned int, R_RSA_PRIVATE_KEY *));

// RSA decryption, according to RSADSI's PKCS #1.
int RSAPublicDecrypt(output, outputLen, input, inputLen, publicKey)
unsigned char *output;          // output block 
unsigned int *outputLen;        // length of output block
unsigned char *input;           // input block
unsigned int inputLen;          // length of input block
R_RSA_PUBLIC_KEY *publicKey;    // RSA public key
{
	int status;
	unsigned char pkcsBlock[MAX_RSA_MODULUS_LEN];
	unsigned int i, modulusLen, pkcsBlockLen;
	// Generate publicKey->bits ourselves
#define pk(x) ((unsigned char)(publicKey->modulus[(x)]))
	status = 0;
	for ( i = 0; i < MAX_RSA_MODULUS_LEN; ++i ) {
		if      ( pk(i) >= 0x80 ) status = 8;
		else if ( pk(i) >= 0x40 ) status = 7;
		else if ( pk(i) >= 0x20 ) status = 6;
		else if ( pk(i) >= 0x10 ) status = 5;
		else if ( pk(i) >= 0x08 ) status = 4;
		else if ( pk(i) >= 0x04 ) status = 3;
		else if ( pk(i) >= 0x02 ) status = 2;
		else if ( pk(i) >= 0x01 ) status = 1;
		if ( status > 0 ) {
			status += ( 8 * ( MAX_RSA_MODULUS_LEN - i ) ) - 8;
			i = MAX_RSA_MODULUS_LEN;
		}
	}
	publicKey->bits = status;
	status = 0;
	modulusLen = (publicKey->bits + 7) / 8;
	if(inputLen > modulusLen)
		return(RE_LEN);
	status = rsapublicfunc(pkcsBlock, &pkcsBlockLen, input, inputLen, publicKey);
	if(status)
		return(status);
	if(pkcsBlockLen != modulusLen)
		return(RE_LEN);
	/* Require block type 1. */
	if((pkcsBlock[0] != 0) || (pkcsBlock[1] != 1))
	 return(RE_DATA);

	for(i = 2; i < modulusLen-1; i++)
		if(*(pkcsBlock+i) != 0xff)
			break;
	/* separator check */
	if(pkcsBlock[i++] != 0)
		return(RE_DATA);
	*outputLen = modulusLen - i;
	if(*outputLen + 11 > modulusLen)
		return(RE_DATA);
	R_memcpy((POINTER)output, (POINTER)&pkcsBlock[i], *outputLen);
	/* Clear sensitive information. */
	R_memset((POINTER)pkcsBlock, 0, sizeof(pkcsBlock));
	return(ID_OK);
}
// Raw RSA public-key operation. Output has same length as modulus.
//	 Requires input < modulus.
static int rsapublicfunc(output, outputLen, input, inputLen, publicKey)
unsigned char *output;          // output block
unsigned int *outputLen;        // length of output block
unsigned char *input;           // input block
unsigned int inputLen;          // length of input block
R_RSA_PUBLIC_KEY *publicKey;    // RSA public key
{
	NN_DIGIT c[MAX_NN_DIGITS], e[MAX_NN_DIGITS], m[MAX_NN_DIGITS],
		n[MAX_NN_DIGITS];
	unsigned int eDigits, nDigits;
		/* decode the required RSA function input data */
	NN_Decode(m, MAX_NN_DIGITS, input, inputLen);
	NN_Decode(n, MAX_NN_DIGITS, publicKey->modulus, MAX_RSA_MODULUS_LEN);
	NN_Decode(e, MAX_NN_DIGITS, publicKey->exponent, MAX_RSA_MODULUS_LEN);
	nDigits = NN_Digits(n, MAX_NN_DIGITS);
	eDigits = NN_Digits(e, MAX_NN_DIGITS);
	if(NN_Cmp(m, n, nDigits) >= 0)
		return(RE_DATA);
	*outputLen = (publicKey->bits + 7) / 8;
	/* Compute c = m^e mod n.  To perform actual RSA calc.*/
	NN_ModExp (c, m, e, eDigits, n, nDigits);
	/* encode output to standard form */
	NN_Encode (output, *outputLen, c, nDigits);
	/* Clear sensitive information. */
	R_memset((POINTER)c, 0, sizeof(c));
	R_memset((POINTER)m, 0, sizeof(m));
	return(ID_OK);
}
#endif