rsa.cpp

RSA 高级实现

 * that the padding differs.  The type is 1, and the padding is all 1's
 * (hex 0xFF).  In addition, if the data is a DER-padded MD5 hash, there's
 * an option for encoding it with the old PGP 2.2 format, in which case
 * that's all replaced by a 1 byte indicating MD5.
 *
 * When decrypting, distinguishing these is a bit trickier, since the
 * second most significant byte is 1 in both cases, but in general,
 * it could only cause confusion if the PGP hash were all 1's.
 *
 * To summarize, the formats are:
 *
 * Position     Value   Function
 * n-1           0      This is needed to ensure that the padded number
 *                      is less than the modulus.
 * n-2           1      The padding type (all ones).
 * n-3..len+1   255     All ones padding to ensure signatures are rare.
 * len           0      Zero byte to mark the end of the padding
 * len-1..x     ASN.1	The ASN.1 DER magic cookie (18 bytes)
 * x-1..0       data    The payload MD5 hash (16 bytes).
 *
 *
 * Position     Value
 * n-1           0
 * n-2           1	"This is MD5"
 * n-2..n-len-2 data    Supplied payload MD5 hash (len == 16).
 * n-len-2       0      Zero byte to mark the end of the padding
 * n-len-3..1   255     All ones padding.
 * 0             1      The padding type (all ones).
 *
 *
 * The reason for the all 1's padding is an extra consistency check.
 * A randomly invented signature will not decrypt to have the long
 * run of ones necessary for acceptance.
 *
 * Oh... the public key isn't needed to decrypt, but it's passed in
 * because a different glue library may need it for some reason.
 *
 * TODO: Have the caller put on the PKCS wrapper.  We can notice and
 * strip it off if we're trying to be compatible.
 */
static const BYTE signedType = 1;

int CRSA::rsaPrivateEncrypt(CBigNumber *bn, const PBYTE in, unsigned len)
{
	unsigned bytes = (bnBits(&n)+7)/8;

	_rsaPack(bn, in, len, RSA_PAD_SIGNED, bytes);

bndPrintf("\nRSA signing.");
bndPut("plaintext = ", bn);
#if defined(__TEST_CRAEX__)
	CBigNumber bnGood;
	bnGood = *bn;
	_bnExpModCRAEx(&bnGood, &d, &p, &q, &u);
	CBigNumber bnTemp1;
	bnTemp1 = *bn;
	_bnExpModCRA(&bnTemp1, &d, &p, &q, &u);
#endif
	int ret = bnExpMod(bn, bn, &d, &n);
#if defined(__TEST_CRAEX__)
	if (0 != bnCmp(&bnGood, &bnTemp1))
	{
		bndPrintf("\n *** bnExpModCRA error !");
	}
	if (0 != bnCmp(&bnGood, bn))
	{
		bndPrintf("\n *** bnExpModCRAEx error !");
	}
	if (0 != bnCmp(bn, &bnTemp1))
	{
		bndPrintf("\n *** bnExpModCRA != bnExpModCRAEx !");
	}
#endif
	return ret;
	//return _bnExpModCRA(bn, &d, &p, &q, &u);
	//return bnExpMod(bn, bn, &d, &n);
}

/*
 * Decrypt a message with a public key.
 * These destroy (actually, replace with a decrypted version) the
 * input bignum bn.
 *
 * It recongizes the PGP 2.2 format, but not in all its generality;
 * only the one case (framing byte = 1, length = 16) which was ever
 * generated.  It fakes the DER prefix in that case.
 *
 * Performs an RSA signature check.  Returns a prefix of the unwrapped
 * data in the given buf.  Returns the length of the untruncated
 * data, which may exceed "len". Returns <0 on error.
 */
int CRSA::rsaPublicDecrypt(PBYTE buf, unsigned len, const CBigNumber *bn)
{
	unsigned bytes;

	CBigNumber bnOutput;
	bnOutput = *bn;
	bndPrintf("RSA signature checking.\n");
	if (bnExpMod(&bnOutput, bn, &e, &n) < 0)
		return -1;
	bndPut("decrypted = ", &bnOutput);
	bytes = (bnBits(&n)+7)/8;
	return _rsaUnpack(buf, len, &bnOutput, RSA_PAD_SIGNED, bytes);
}


/*
 * Performs an RSA decryption.  Returns a prefix of the unwrapped
 * data in the given buf.  Returns the length of the untruncated
 * data, which may exceed "len". Returns <0 on error.
 */
int CRSA::rsaPrivateDecrypt(PBYTE buf, unsigned len, const CBigNumber *bn)
{
	unsigned bytes;

	CBigNumber bnOutput = *bn;
	bndPrintf("RSA decrypting\n");
	if (_bnExpModCRA(&bnOutput, &d, &p, &q, &u) < 0)
		return -1;
	bndPut("decrypted = ", &bnOutput);
	bytes = (bnBits(&n)+7)/8;
	return _rsaUnpack(buf, len, &bnOutput, RSA_PAD_ENCRYPTED, bytes);
}

/*
 * Generate an RSA secret key with modulus of the specified number of bits.
 * We choose public exponent from the #define value above.
 * The high two bits of each prime are always
 * set to make the number more difficult to factor by forcing the
 * number into the high end of the range.
 * Make callbacks to progress function periodically.
 * Secret key is returned in the unlocked form, with no passphrase set.
 * fastgen is an unused flag which is used by the discrete log keygens to
 * allow use of canned primes.
 */
#define RSA_DEFAULT_EXPONENT	0x10001

static BOOL _RsaPrimesGen(CRandomGenerator* prand, CBigNumber& pOut, CBigNumber& qOut, unsigned bits, unsigned pe, int (*progress)(void *arg, int c), void *arg, int *error)
{
	BOOL bResult = true;
	unsigned ent;	/* Entropy */
	int i;
	int exp = pe; //RSA_DEFAULT_EXPONENT;

	CBigNumber p;
	CBigNumber q;
	CBigNumber t;		/* temporary */
	
	*error = 0;

	/* Allocate data structures */
	
	/* n is not inherently sensitive, but holds sensitive intermediates */
	
	ASSERT(prand);
	prand->GenRand(&p, bits / 2, 0xc0, 1, bits / 2 - 3);

	/* And search for a prime */
	i = p.bnPrimeGen(NULL, progress, arg, exp, 0);
	if (i < 0)
		goto bnerror;
	ASSERT(bnModQ(&p, exp) != 1);

	pOut = p;
	
	/* Make sure p and q aren't too close together */

	/* Bits of entropy needed to generate q. */
	ent = (bits+1)/2 - 3;
	/* Pick random q until we get one not too close to p */
	do {
		/* Visual separator between the two progress indicators */
		//if (progress)
		//	progress(arg, ' ');
		if (prand->GenRand(&q, (bits+1)/2, 0xC0, 1, ent) < 0)
			goto bnerror;
		ent = 0;	/* No entropy charge next time around */
		if (bnCopy(&t, &q) < 0)
			goto bnerror;
		if (bnSub(&t, &p) < 0)
			goto bnerror;
		/* Note that bnSub(a,b) returns abs(a-b) */
	} while (bnBits(&t) < bits/2-5);

	i = q.bnPrimeGen(NULL, progress, arg, exp, 0);
	if (i < 0)
		goto bnerror;
	ASSERT(bnModQ(&p, exp) != 1);

	qOut = q;
	
	/* And that's it... success! */

	goto done;

bnerror:
	bResult = false;
	*error = -1;
	/* Fall through */
done:

	if (bResult)
	{
		//save all result
	}

	return bResult;
}

static BOOL _RsaKeyGen(CRandomGenerator* prand, const CBigNumber& pIn, const CBigNumber& qIn, CBigNumber& nOut, CBigNumber& dOut, CBigNumber& uOut, unsigned pe, int (*progress)(void *arg, int c), void *arg, int* error)
{
	BOOL bResult = true;
	int i;
	int exp = pe; //RSA_DEFAULT_EXPONENT;

	CBigNumber e;
	CBigNumber p;
	CBigNumber q;
	CBigNumber n;
	CBigNumber d;
	CBigNumber u;
	CBigNumber t;		/* temporary */
	
	*error = 0;

	/* Initialize local pointers (simplify cleanup below) */

	/* Allocate data structures */
	
	/* n is not inherently sensitive, but holds sensitive intermediates */
	if (bnCopy(&p, &pIn) < 0)
		goto bnerror;
	if (bnCopy(&q, &qIn) < 0)
		goto bnerror;
	if (bnSetQ(&e, exp))
		goto bnerror;
	
	ASSERT(prand);
	/* Wash the random number pool. */
	for (i = 0; i < 5; i++)
	{
		prand->Update((rand() << 16) | (rand() & 0xffff));
	}

	/* Ensure that q is larger */
	if (bnCmp(&p, &q) > 0)
	{
		//bnSwap(&p, &q);
		union
		{
			unsigned n;
			void*	 pv;
		};
#define SWAPDWORD(t, a, b) t = a; a = b; b = t
		SWAPDWORD(pv, p.ptr,		q.ptr);
		SWAPDWORD(n,  p.size,		q.size);
		SWAPDWORD(n,  p.allocated,	q.allocated);
#undef  SWAPDWORD
	}	

	/*
	m_d = EuclideanMultiplicativeInverse(m_e, LCM(m_p-1, m_q-1));
	inline Integer EuclideanMultiplicativeInverse(const Integer &a, const Integer &b)
	{return a.InverseMod(b);}
	inline Integer LCM(const Integer &a, const Integer &b)
	{return a/Integer::Gcd(a,b)*b;}

	==>
	m_d = m_e.InverseMode((m_p-1) / gcd(m_p - 1, m_q - 1) * (m_q - 1));
	
	下面的算法
	q = m_q - 1;
	u = m_p - 1;
	m_d = m_e.InverseMode(u / gcd(u, q) * q);
	t = gcd(q, u);
	m_d = m_e.InverseMode(u / t * q);
	d = u / t;
	m_d = m_e.InverseMode(d * q);
	n = q * d;
	m_d = m_e.InverseMode(n);
	d = e inv n;
	m_d = d;
	*/

	
	/*
	 * Now we compute d,
	 * the decryption exponent, from the encryption exponent.
	 */

	/* Decrement q temporarily */
	(void)bnSubQ(&q, 1);
	/* And u = p-1, to be divided by gcd(p-1,q-1) */
	if (bnCopy(&u, &p) < 0)
		goto bnerror;
	(void)bnSubQ(&u, 1);

	/* Use t to store gcd(p-1,q-1) */
	if (bnGcd(&t, &q, &u) < 0) {
		goto bnerror;
	}

	/* Let d = (p-1) / gcd(p-1,q-1) (n is scratch for the remainder) */
	i = bnDivMod(&d, &n, &u, &t);
	if (i < 0)
		goto bnerror;
	ASSERT(bnBits(&n) == 0);

	/* Now we have q-1 and d = (p-1) / gcd(p-1,q-1) */
	/* Find the product, n = lcm(p-1,q-1) = c * d */
	if (bnMul(&n, &q, &d) < 0)
		goto bnerror;

	/* Find the inverse of the exponent mod n */
	i = bnInv(&d, &e, &n);
	if (i < 0)
		goto bnerror;
	if (i)
		goto bnerror;

	ASSERT(!i);	/* We should NOT get an error here */

	dOut = d;
	
	/*
	 * Now we have the comparatively simple task of computing
	 * u = p^-1 mod q.
	 */

	/* But it *would* be nice to have q back first. */
	(void)bnAddQ(&q, 1);

	/* Now compute u = p^-1 mod q */
	i = bnInv(&u, &p, &q);
	if (i < 0)
		goto bnerror;
	ASSERT(!i);	/* p and q had better be relatively prime! */

	uOut = u;

	/* And finally,  n = p * q */
	if (bnMul(&n, &p, &q) < 0)
		goto bnerror;

	nOut = n;
	/* And that's it... success! */

	goto done;

bnerror:
	bResult = false;
	*error = -1;
	/* Fall through */
done:

	if (bResult)
	{
		//save all result
	}

	return bResult;
}
	
BOOL CRSA::RsaPrimesGen(unsigned bits, unsigned pe, int (*progress)(void *arg, int c), void *arg, int *error)
{
	ASSERT(m_prand);
	e = pe;
	return _RsaPrimesGen(m_prand, p, q, bits, pe, progress, arg, error);
}

BOOL CRSA::RsaKeyGen(unsigned pe, int (*progress)(void *arg, int c), void *arg, int *error)
{
	ASSERT(m_prand);
	e = pe;
	return _RsaKeyGen(m_prand, p, q, n, d, u, pe, progress, arg, error);
}

int CRSA::rsaTestPrivateE(CBigNumber* bn, const PBYTE in, unsigned len)
{
	CBigNumber t;
	
	t = n; //set size
	memset(t.ptr, 0, t.size);
	memcpy(t.ptr, in, min(t.size, len + 1));
	return bnExpMod(bn, &t, &d, &n);
}

int CRSA::rsaTestPublicD(const PBYTE in, unsigned len, const CBigNumber* bn)
{
	CBigNumber t;
	CBigNumber tn;
	
	tn = *bn;
	t = n; //set size
	int nret = bnExpMod(&tn, &tn, &e, &n);
	memcpy(in, tn.ptr, tn.size);

	return nret;
}