rsa.cpp

RSA 高级实现

// RSA.cpp: implementation of the CRSA class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "RSAUtil.h"
#include "RSA.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

#define bndPut(a, b) (void)0
#define bndPrintf	 TRACE

#define RSA_PAD_ENCRYPTED	1
#define RSA_PAD_SIGNED		2

#define PKCS_COMPAT 1

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CRSA::CRSA()
{
	m_prand = NULL;
}

CRSA::~CRSA()
{
	m_prand = NULL;
}

#define GenRandomGetBytes(a, b) memset(a, 0, b)

/*
* Fill the given bignum, from bytes high-1 through low (where 0 is
* the least significant byte), with non-zero random data.
*/
static int _zeroPad(CBigNumber *bn, unsigned low, unsigned high)
{
	//return prand->GenRand(bn, high - low + 1, high, low, 0);
	unsigned i, l;
	BYTE padding[64];   /* This can be any size (>0) whatsoever */
	
	high -= low;
	while (high) 
	{
		l = high < sizeof(padding) ? high : sizeof(padding);
		GenRandomGetBytes(padding, l);
		for (i = 0; i < l; i++) 
		{       /* Replace all zero bytes */ 
			while(padding[i] == 0)
				GenRandomGetBytes(padding+i, 1);
		}
		high -= l;
		if (bnInsertBigBytes(bn, padding, high+low, l) < 0)
			return -1;
	}
	
	return 0;
}

/*
* Fill the given bignum, from bytes high-1 through low (where 0 is
* the least significant byte), with all ones (0xFF) data.
*/
static int _onesPad(CBigNumber *bn, unsigned low, unsigned high)
{
	unsigned l;
	static BYTE const padding[] = 
	{
		255,255,255,255,255,255,255,255,
		255,255,255,255,255,255,255,255
	};
	
	high -= low;
	while (high) 
	{
		l = high < sizeof(padding) ? high : sizeof(padding);
		high -= l;
		if (bnInsertBigBytes(bn, padding, high + low, l) < 0)
		{
			return -1;
		}
	}
	return 0;
}

static int _rsaPack(CBigNumber *bn, BYTE const *in, unsigned len, BYTE padtype, unsigned bytes)
{
	//len + zero(1byte) + len(2byte) + padtype(2byte)
	if (len + 5 > bytes)
	{
		return -2;	/* data won't fit in pubkey! */
	}

	/* Set the entire number to 0 to start */
	(void)bnSetQ(bn, 0);
	
	if (padtype == RSA_PAD_ENCRYPTED) 
	{
		if (bnInsertBigBytes(bn, &padtype, bytes - 2, 1) < 0 ||
			bnInsertBigBytes(bn, (unsigned char*)&len, bytes - 4, 2) < 0 ||
			_zeroPad(bn, len + 1, bytes - 4) < 0 ||
			bnInsertBigBytes(bn, in, 0, len) < 0)
		{
			return -1;
		}
	} 
	else 
	{
		ASSERT(padtype == RSA_PAD_SIGNED);
		/* Constant padding */
		if (bnInsertBigBytes(bn, &padtype, bytes - 2, 1) < 0 ||
			bnInsertBigBytes(bn, (unsigned char*)&len, bytes - 4, 2) < 0 ||
			_onesPad(bn, len + 1, bytes - 4) < 0 ||
			bnInsertBigBytes(bn, in, 0, len) < 0)
		{
			return -1;
		}
	}
	return 0;
}

static int _rsaUnpack(BYTE *buf, unsigned len, CBigNumber *bn, BYTE padtype, unsigned bytes)
{
	BYTE	 _type;
	unsigned _len = 0;

	bnExtractBigBytes(bn, &_type, bytes - 2, 1);
	if (padtype == RSA_PAD_ENCRYPTED)
	{
		if (_type != padtype)
		{
			return -3;
		}
		bnExtractBigBytes(bn, (unsigned char*)&_len, bytes - 4, 2);
	} 
	else 
	{
		ASSERT(padtype==RSA_PAD_SIGNED);
		/* Signature check, constant padding */
		if (_type != padtype) 
		{
			return -3;
		}
		bnExtractBigBytes(bn, (unsigned char*)&_len, bytes - 4, 2);
	}
	if (_len + 1 > len)
	{
		return -2;
	}
	bnExtractBigBytes(bn, buf, 0, _len);
	buf[_len] = 0;

	return _len;
}

/*
Chinese remainder theorem
中国剩余定理

中国有一本数学古书《孙子算经》有这样的记载：

「今有物，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二，问物几何？」 

答曰：「二十三」 

术曰：「三三数之剩二，置一百四十，五五数之剩三，置六十三，七七数之剩二，置三十，
并之，得二百三十三，以二百一十减之，即得。凡三三数之剩一，则置七十，五五数之剩一，
则置二十一，七七数之剩一，则置十五，即得。」


孙子算经的作者及确实着作年代均不可考，不过根据考证，着作年代不会在晋朝之后，
以这个考证来说上面这种问题的解法，中国人发现得比西方早，所以这个问题的推广及其解法，
被称为中国剩余定理。中国剩余定理（Chinese Remainder Theorem）
在近代抽象代数学中占有一席非常重要的地位。
它揭示了这样两个系统的一致性：一是模两两互质的一组数的同余方程组，二是模它们的乘积的方程。

中国剩余定理的内容如下：

令n=n1n2...nk，其中ni是两两互质的数，
则对0<=a<n与0<=ai<ni且ai=a mod ni，a与(a1,a2...,ak)之间有一种一一对应的关系，
一切对a的操作均可被等价的转换为对对应k元组中的每一元进行同样的操作。
因此我们可以将一种表达经过简单的转换后得出另一种表达，其中从a到(a1,a2...,ak)的转换十分容易，
而从(a1,a2...,ak)推得对应的a则要稍微复杂一些。 

首先定义mi=n/ni(i=1,2...k)，则mi是除了ni以外的所有nj的乘积，接下来令ci=mi与模n意义下mi的逆元的积，
则a为(a1c1+a2c2+...+akck) (mod n)。 

例如我们已知a模5余2且模13余3，那么a1=2,n1=m2=5,a2=3,n2=m1=13，
则有c1=13*(2 mod 5)=26，c2=5*(8 mod 13)=40，所以a=(2*26+3*40)（mod 65)=42。 
*/

/*
vlong  public_key::encrypt(  const  vlong&  plain  )  
{  
	return  modexp(  plain,  e,  m  );  
}  

  vlong  private_key::decrypt(  const  vlong&  cipher  )  
  {  
  //  Calculate  values  for  performing  decryption  
  //  These  could  be  cached,  but  the  calculation  is  quite  fast  
  vlong  d  =  modinv(  e,  (p-1)*(q-1)  );  
  vlong  u  =  modinv(  p,  q  );  
  vlong  dp  =  d  %  (p-1);  
  vlong  dq  =  d  %  (q-1);  
  
	//  Apply  chinese  remainder  theorem  
	vlong  a  =  modexp(  cipher  %  p,  dp,  p  );  
	vlong  b  =  modexp(  cipher  %  q,  dq,  q  );  
	if  (  b  <  a  )  b  +=  q;  
	return  a  +  p  *  (  ((b-a)*u)  %  q  );  
	}  
*/
static int _bnExpModCRAEx(CBigNumber *x, CBigNumber const *d,	CBigNumber const *p, CBigNumber const *q, CBigNumber const *u)
{
	//xp = (x % p) ^ (d % (p-1)) % p;
	//xq = (x % q) ^ (d % (q-1)) % q;
	//if (xq < xp) xq += q;
	//return xp + p * (((xq - xp) * u) % q);
	
	CBigNumber xp, xq, k;
	int i;

	/* Compute xp = (x mod p) ^ (d mod p-1) mod p */
	if (bnCopy(&xp, p) < 0)		/* First, use xp to hold p-1 */
		goto fail;
	(void)bnSubQ(&xp, 1);		/* p > 1, so subtracting is safe. */
	if (bnMod(&k, d, &xp) < 0)	/* k = d mod (p-1) */
		goto fail;
	if (bnMod(&xp, x, p) < 0)	/* Now xp = (x mod p) */
		goto fail;
	if (bnExpMod(&xp, &xp, &k, p) < 0)	/* xp = (x mod p)^k mod p */
		goto fail;

	/* Compute xq = (x mod q) ^ (d mod q-1) mod q */
	if (bnCopy(&xq, q) < 0)		/* First, use xq to hold q-1 */
		goto fail;
	(void)bnSubQ(&xq, 1);		/* q > 1, so subtracting is safe. */
	if (bnMod(&k, d, &xq) < 0)	/* k = d mod (q-1) */
		goto fail;
	if (bnMod(&xq, x, q) < 0)	/* Now xq = (x mod q) */
		goto fail;
	if (bnExpMod(&xq, &xq, &k, q) < 0)	/* xq = (x mod q)^k mod q */
		goto fail;

	//if (xq < xp) xq += q;
	i = bnCmp(&xq, &xp);
	if (i < 0)
	{
		if (bnAdd(&xq, q) < 0)
			goto fail;
	}

	//return xp + p * (((xq - xp) * u) % q);
	if (bnSub(&xq, &xp) < 0)
		goto fail;
	if (bnMul(&k, u, &xq) < 0)
		goto fail;
	if (bnMod(&k, &k, q) < 0)
		goto fail;

	/* Now x = k * p + xp is the final answer */
	if (bnMul(x, &k, p) < 0)
		goto fail;
	if (bnAdd(x, &xp) < 0)
		goto fail;
	//ok x is the answer

	return 0;

fail:
	return -1;
}

/*
 * This performs a modular exponentiation using the Chinese Remainder
 * Algorithm when the modulus is known to have two relatively prime
 * factors n = p * q, and u = p^-1 (mod q) has been precomputed.
 *
 * The chinese remainder algorithm lets a computation mod n be performed
 * mod p and mod q, and the results combined.  Since it takes
 * (considerably) more than twice as long to perform modular exponentiation
 * mod n as it does to perform it mod p and mod q, time is saved.
 *
 * If x is the desired result, let xp and xq be the values of x mod p
 * and mod q, respectively.  Obviously, x = xp + p * k for some k.
 * Taking this mod q, xq == xp + p*k (mod q), so p*k == xq-xp (mod q)
 * and k == p^-1 * (xq-xp) (mod q), so k = u * (xq-xp mod q) mod q.
 * After that, x = xp + p * k.
 *
 * by aSprite
 * x = xp + u * (xq - xp) % q * p;
 *
 * Another savings comes from reducing the exponent d modulo phi(p)
 * and phi(q).  Here, we assume that p and q are prime, so phi(p) = p-1
 * and phi(q) = q-1.
 */
static int _bnExpModCRA(CBigNumber *x, CBigNumber const *d,	CBigNumber const *p, CBigNumber const *q, CBigNumber const *u)
{
	CBigNumber xp, xq, k;
	int i;

bndPrintf("Performing Chinese Remainder Algorithm\n");
bndPut("x = ", x);
bndPut("p = ", p);
bndPut("q = ", q);
bndPut("d = ", d);
bndPut("u = ", u);

	/* Compute xp = (x mod p) ^ (d mod p-1) mod p */
	if (bnCopy(&xp, p) < 0)		/* First, use xp to hold p-1 */
		goto fail;
	(void)bnSubQ(&xp, 1);		/* p > 1, so subtracting is safe. */
	if (bnMod(&k, d, &xp) < 0)	/* k = d mod (p-1) */
		goto fail;
bndPut("d mod p-1 = ", &k);
	if (bnMod(&xp, x, p) < 0)	/* Now xp = (x mod p) */
		goto fail;
bndPut("x mod p = ", &xp);
	if (bnExpMod(&xp, &xp, &k, p) < 0)	/* xp = (x mod p)^k mod p */
		goto fail;
bndPut("xp = x^d mod p = ", &xp);

	/* Compute xq = (x mod q) ^ (d mod q-1) mod q */
	if (bnCopy(&xq, q) < 0)		/* First, use xq to hold q-1 */
		goto fail;
	(void)bnSubQ(&xq, 1);		/* q > 1, so subtracting is safe. */
	if (bnMod(&k, d, &xq) < 0)	/* k = d mod (q-1) */
		goto fail;
bndPut("d mod q-1 = ", &k);
	if (bnMod(&xq, x, q) < 0)	/* Now xq = (x mod q) */
		goto fail;
bndPut("x mod q = ", &xq);
	if (bnExpMod(&xq, &xq, &k, q) < 0)	/* xq = (x mod q)^k mod q */
		goto fail;
bndPut("xq = x^d mod q = ", &xq);

	/* xp < p and PGP has p < q, so this is a no-op, but just in case */
	if (bnMod(&k, &xp, q) < 0)
		goto fail;	
bndPut("xp mod q = ", &k);
	
	i = bnSub(&xq, &k);
bndPut("xq - xp = ", &xq);
bndPrintf("With sign %d\n", i);
	if (i < 0)
		goto fail;
	if (i) 
	{
		/*
		 * Borrow out - xq-xp is negative, so bnSub returned
		 * xp-xq instead, the negative of the true answer.
		 * Add q back (which is subtracting from the negative)
		 * so the sign flips again.
		 */
		i = bnSub(&xq, q);
		if (i < 0)
			goto fail;
bndPut("xq - xp mod q = ", &xq);
bndPrintf("With sign %d\n", i);		/* Must be 1 */
	}

	/* Compute k = xq * u mod q */
	if (bnMul(&k, u, &xq) < 0)
		goto fail;
bndPut("(xq-xp) * u = ", &k);
	if (bnMod(&k, &k, q) < 0)
		goto fail;
bndPut("k = (xq-xp)*u % q = ", &k);

	/* Now x = k * p + xp is the final answer */
	if (bnMul(x, &k, p) < 0)
		goto fail;
bndPut("k * p = ", x);
	if (bnAdd(x, &xp) < 0)
		goto fail;
bndPut("k*p + xp = ", x);

	return 0;

fail:
	return -1;
}

int CRSA::rsaPublicEncrypt(CBigNumber *bn, const PBYTE in, unsigned len)
{
	unsigned bytes = (bnBits(&n)+7)/8;
	_rsaPack(bn, in, len, RSA_PAD_ENCRYPTED, bytes);
	return bnExpMod(bn, bn, &e, &n);
}


/*
 * This does an RSA signing operation, which is very similar, except