rsacrypt.h

RSA 1024位加密算法封装

///
/// \brief \b [Internal] SHA-1 computation class
///
/// Performant RSA en/decryption with 256-bit to 16384-bit modulus
///
/// catid([e-mail])
///
/// 7/30/2004 Fixed VS6 compat
/// 7/26/2004 Now internally generates private keys
/// simpleModExp() is faster for encryption than MontyModExp
/// CRT-MontyModExp is faster for decryption than CRT-SimpleModExp
/// 7/25/2004 Implemented Montgomery modular exponentation
/// Implemented CRT modular exponentation optimization
/// 7/21/2004 Did some pre-lim coding
///
/// Best performance on my 1.8 GHz P4 (mobile):
/// 1024-bit generate key : 30 seconds
/// 1024-bit set private key : 100 ms (pre-compute this step)
/// 1024-bit encryption : 200 usec
/// 1024-bit decryption : 400 ms
///
/// \todo There's a bug in MonModExp() that restricts us to k-1 bits
///
/// Tabs: 4 spaces
/// Dist: public

#ifndef RSACRYPT_H
#define RSACRYPT_H

#if !defined(_COMPATIBILITY_1)

#define RSASUPPORTGENPRIME
#include "Export.h"
/// Can't go under 256 or you'll need to disable the USEASSEMBLY macro in bigtypes.h
/// That's because the assembly assumes at least 128-bit data to work on
#define RSA_BIT_SIZE big::u512
///#define RSA_BIT_SIZE big::u256

#include "BigTypes.h"
#include "Rand.h" //Giblet - added missing include for randomMT()

#ifdef _MSC_VER
#pragma warning( push )
#endif

namespace big
{

	using namespace cat;

	// r = x^y Mod n (fast for small y)
	BIGONETYPE void simpleModExp( T &x0, T &y0, T &n0, T &r0 )
	{
		BIGDOUBLESIZE( T, x );
		BIGDOUBLESIZE( T, y );
		BIGDOUBLESIZE( T, n );
		BIGDOUBLESIZE( T, r );

		usetlow( x, x0 );
		usetlow( y, y0 );
		usetlow( n, n0 );
		usetw( r, 1 );

		umodulo( x, n, x );

		u32 squares = 0;

		for ( u32 ii = 0; ii < BIGWORDCOUNT( T ); ++ii )
		{
			word y_i = y[ ii ];

			u32 ctr = WORDBITS;

			while ( y_i )
			{
				if ( y_i & 1 )
				{
					if ( squares )
						do
						{
							usquare( x );
							umodulo( x, n, x );
						}

						while ( --squares );

						umultiply( r, x, r );

						umodulo( r, n, r );
				}

				y_i >>= 1;
				++squares;
				--ctr;
			}

			squares += ctr;
		}

		takelow( r0, r );
	}

	// computes Rn = 2^k (mod n), n < 2^k
	BIGONETYPE void rModn( T &n, T &Rn )
	{
		BIGDOUBLESIZE( T, dR );
		BIGDOUBLESIZE( T, dn );
		BIGDOUBLESIZE( T, dRn );
		T one;

		// dR = 2^k
		usetw( one, 1 );
		sethigh( dR, one );

		// Rn = 2^k (mod n)
		usetlow( dn, n );
		umodulo( dR, dn, dRn );
		takelow( Rn, dRn );
	}

	// computes c = GCD(a, b)
	BIGONETYPE void GCD( T &a0, T &b0, T &c )
	{
		T a;

		umodulo( a0, b0, c );

		if ( isZero( c ) )
		{
			set ( c, b0 )

				;
			return ;
		}

		umodulo( b0, c, a );

		if ( isZero( a ) )
			return ;

#ifdef _MSC_VER
#pragma warning( disable : 4127 ) // warning C4127: conditional expression is constant
#endif
		while ( true )
		{
			umodulo( c, a, c );

			if ( isZero( c ) )
			{
				set ( c, a )

					;
				return ;
			}

			umodulo( a, c, a );

			if ( isZero( a ) )
				return ;
		}
	}

	// directly computes x = c - a * b (mod n) > 0, c < n
	BIGONETYPE void SubMulMod( T &a, T &b, T &c, T &n, T &x )
	{
		BIGDOUBLESIZE( T, da );
		BIGDOUBLESIZE( T, dn );
		T y;

		// y = a b (mod n)
		usetlow( da, a );
		umultiply( da, b );
		usetlow( dn, n );
		umodulo( da, dn, da );
		takelow( y, da );

		// x = (c - y) (mod n) > 0

		set ( x, c )

			;
		if ( ugreater( c, y ) )
		{
			subtract( x, y );
		}

		else
		{
			subtract( x, y );

			add ( x, n )

				;
		}
	}

	/*
	directly compute a' s.t. a' a - b' b = 1

	b = b0 = n0
	rp = a'
	a = 2^k
	a > b > 0
	GCD(a, b) = 1 (b odd)

	Trying to keep everything positive
	*/
	BIGONETYPE void computeRinverse( T &n0, T &rp )
	{
		T x0, x1, x2, a, b, q;

		//x[0] = 1
		usetw( x0, 1 );

		// a = 2^k (mod b0)
		rModn( n0, a );

		// {q, b} = b0 / a
		udivide( n0, a, q, b );

		// if b = 0, return x[0]

		if ( isZero( b ) )
		{
			set ( rp, x0 )

				;
			return ;
		}

		// x[1] = -q (mod b0) = b0 - q, q <= b0
		set ( x1, n0 )

			;
		subtract( x1, q );

		// {q, a} = a / b
		udivide( a, b, q, a );

		// if a = 0, return x[1]
		if ( isZero( a ) )
		{
			set ( rp, x1 )

				;
			return ;
		}
#ifdef _MSC_VER
#pragma warning( disable : 4127 ) // warning C4127: conditional expression is constant
#endif
		while ( true )
		{
			// x[2] = x[0] - x[1] * q (mod b0)
			SubMulMod( q, x1, x0, n0, x2 );

			// {q, b} = b / a
			udivide( b, a, q, b );

			// if b = 0, return x[2]

			if ( isZero( b ) )
			{
				set ( rp, x2 )

					;
				return ;
			}

			// x[0] = x[1] - x[2] * q (mod b0)
			SubMulMod( q, x2, x1, n0, x0 );

			// {q, a} = a / b
			udivide( a, b, q, a );

			// if a = 0, return x[0]
			if ( isZero( a ) )
			{
				set ( rp, x0 )

					;
				return ;
			}

			// x[1] = x[2] - x[0] * q (mod b0)
			SubMulMod( q, x0, x2, n0, x1 );

			// {q, b} = b / a
			udivide( b, a, q, b );

			// if b = 0, return x[1]
			if ( isZero( b ) )
			{
				set ( rp, x1 )

					;
				return ;
			}

			// x[2] = x[0] - x[1] * q (mod b0)
			SubMulMod( q, x1, x0, n0, x2 );

			// {q, a} = a / b
			udivide( a, b, q, a );

			// if a = 0, return x[2]
			if ( isZero( a ) )
			{
				set ( rp, x2 )

					;
				return ;
			}

			// x[0] = x[1] - x[2] * q (mod b0)
			SubMulMod( q, x2, x1, n0, x0 );

			// {q, b} = b / a
			udivide( b, a, q, b );

			// if b = 0, return x[0]
			if ( isZero( b ) )
			{
				set ( rp, x0 )

					;
				return ;
			}

			// x[1] = x[2] - x[0] * q (mod b0)
			SubMulMod( q, x0, x2, n0, x1 );

			// {q, a} = a / b
			udivide( a, b, q, a );

			// if a = 0, return x[1]
			if ( isZero( a ) )
			{
				set ( rp, x1 )

					;
				return ;
			}
		}
	}

	/* BIGONETYPE void computeRinverse2(T &_n0, T &_rp)
	{
	//T x0, x1, x2, a, b, q;
	BIGDOUBLESIZE(T, x0);
	BIGDOUBLESIZE(T, x1);
	BIGDOUBLESIZE(T, x2);
	BIGDOUBLESIZE(T, a);
	BIGDOUBLESIZE(T, b);
	BIGDOUBLESIZE(T, q);
	BIGDOUBLESIZE(T, n0);
	BIGDOUBLESIZE(T, rp);

	usetlow(n0, _n0);
	usetlow(rp, _rp);

	std::string old;
	//x[0] = 1
	usetw(x0, 1);

	T _a;
	// a = 2^k (mod b0)
	rModn(_n0, _a);
	RECORD("TEST") << "a=" << toString(a, false) << " = 2^k (mod " << toString(n0, false) << ")";
	usetlow(a, _a);

	// {q, b} = b0 / a
	udivide(n0, a, q, b);
	RECORD("TEST") << "{q=" << toString(q, false) << ", b=" << toString(b, false) << "} = n0=" << toString(n0, false) << " / a=" << toString(a, false);

	// if b = 0, return x[0]
	if (isZero(b))
	{
	RECORD("TEST") << "b == 0, Returning x[0]";
	set(rp, x0);
	takelow(_rp, rp);
	return;
	}

	// x[1] = -q (mod b0)
	negate(q);
	smodulo(q, n0, x1);
	if (BIGHIGHBIT(x1))
	add(x1, n0); // q > 0
	RECORD("TEST") << "x1=" << toString(x1, false) << " = q=" << toString(q, false) << " (mod n0=" << toString(n0, false) << ")";

	// {q, a} = a / b
	old = toString(a, false);
	udivide(a, b, q, a);
	RECORD("TEST") << "{q=" << toString(q, false) << ", a=" << toString(a, false) << "} = a=" << old << " / b=" << toString(b);

	// if a = 0, return x[1]
	if (isZero(a))
	{
	RECORD("TEST") << "a == 0, Returning x[1]";
	set(rp, x1);
	takelow(_rp, rp);
	return;
	}

	RECORD("TEST") << "Entering loop...";
	while (true)
	{
	// x[2] = x[0] - x[1] * q (mod b0)
	SubMulMod(q, x1, x0, n0, x2);
	RECORD("TEST") << "x[0] = " << toString(x0, false);
	RECORD("TEST") << "x[1] = " << toString(x1, false);
	RECORD("TEST") << "x[2] = " << toString(x2, false);

	// {q, b} = b / a
	old = toString(b);
	udivide(b, a, q, b);
	RECORD("TEST") << "{q=" << toString(q, false) << ", b=" << toString(b) << "} = b=" << old << " / a=" << toString(a, false);

	// if b = 0, return x[2]
	if (isZero(b))
	{
	RECORD("TEST") << "b == 0, Returning x[2]";
	set(rp, x2);
	takelow(_rp, rp);
	return;
	}

	// x[0] = x[1] - x[2] * q (mod b0)
	SubMulMod(q, x2, x1, n0, x0);
	RECORD("TEST") << "x[0] = " << toString(x0, false);
	RECORD("TEST") << "x[1] = " << toString(x1, false);
	RECORD("TEST") << "x[2] = " << toString(x2, false);

	// {q, a} = a / b
	old = toString(a, false);
	udivide(a, b, q, a);
	RECORD("TEST") << "{q=" << toString(q, false) << ", a=" << toString(a, false) << "} = a=" << old << " / b=" << toString(b);

	// if a = 0, return x[0]
	if (isZero(a))
	{
	RECORD("TEST") << "a == 0, Returning x[0]";
	set(rp, x0);
	takelow(_rp, rp);
	return;
	}

	// x[1] = x[2] - x[0] * q (mod b0)
	SubMulMod(q, x0, x2, n0, x1);
	RECORD("TEST") << "x[0] = " << toString(x0, false);
	RECORD("TEST") << "x[1] = " << toString(x1, false);
	RECORD("TEST") << "x[2] = " << toString(x2, false);

	// {q, b} = b / a
	old = toString(b);
	udivide(b, a, q, b);
	RECORD("TEST") << "{q=" << toString(q, false) << ", b=" << toString(b) << "} = b=" << old << " / a=" << toString(a, false);

	// if b = 0, return x[1]
	if (isZero(b))
	{
	RECORD("TEST") << "b == 0, Returning x[1]";
	set(rp, x1);
	takelow(_rp, rp);
	return;
	}

	// x[2] = x[0] - x[1] * q (mod b0)
	SubMulMod(q, x1, x0, n0, x2);
	RECORD("TEST") << "x[0] = " << toString(x0, false);
	RECORD("TEST") << "x[1] = " << toString(x1, false);
	RECORD("TEST") << "x[2] = " << toString(x2, false);

	// {q, a} = a / b
	old = toString(a, false);
	udivide(a, b, q, a);
	RECORD("TEST") << "{q=" << toString(q, false) << ", a=" << toString(a, false) << "} = a=" << old << " / b=" << toString(b);

	// if a = 0, return x[2]
	if (isZero(a))
	{
	RECORD("TEST") << "a == 0, Returning x[2]";
	set(rp, x2);
	takelow(_rp, rp);
	return;
	}

	// x[0] = x[1] - x[2] * q (mod b0)
	SubMulMod(q, x2, x1, n0, x0);
	RECORD("TEST") << "x[0] = " << toString(x0, false);
	RECORD("TEST") << "x[1] = " << toString(x1, false);
	RECORD("TEST") << "x[2] = " << toString(x2, false);

	// {q, b} = b / a
	old = toString(b);
	udivide(b, a, q, b);
	RECORD("TEST") << "{q=" << toString(q, false) << ", b=" << toString(b) << "} = b=" << old << " / a=" << toString(a, false);

	// if b = 0, return x[0]
	if (isZero(b))
	{
	RECORD("TEST") << "b == 0, Returning x[0]";
	set(rp, x0);
	takelow(_rp, rp);
	return;
	}

	// x[1] = x[2] - x[0] * q (mod b0)
	SubMulMod(q, x0, x2, n0, x1);
	RECORD("TEST") << "x[0] = " << toString(x0, false);
	RECORD("TEST") << "x[1] = " << toString(x1, false);
	RECORD("TEST") << "x[2] = " << toString(x2, false);

	// {q, a} = a / b
	old = toString(a, false);
	udivide(a, b, q, a);
	RECORD("TEST") << "{q=" << toString(q, false) << ", a=" << toString(a, false) << "} = a=" << old << " / b=" << toString(b);

	// if a = 0, return x[1]
	if (isZero(a))
	{
	RECORD("TEST") << "a == 0, Returning x[1]";
	set(rp, x1);
	takelow(_rp, rp);
	return;
	}
	}
	}
	*/
	// directly compute a^-1 s.t. a^-1 a (mod b) = 1, a < b, GCD(a, b)
	BIGONETYPE void computeModularInverse( T &a0, T &b0, T &ap )
	{
		T x0, x1, x2;
		T a, b, q;

		// x[2] = 1
		usetw( x2, 1 );

		// {q, b} = b0 / a0
		udivide( b0, a0, q, b );

		// x[0] = -q (mod b0) = b0 - q, q <= b0

		set ( x0, b0 )

			;
		subtract( x0, q );

		set ( a, a0 )

			;

#ifdef _MSC_VER
#pragma warning( disable : 4127 ) // warning C4127: conditional expression is constant
#endif
		while ( true )
		{
			// {q, a} = a / b
			udivide( a, b, q, a );

			// if a = 0, return x[0]

			if ( isZero( a ) )
			{
				set ( ap, x0 )

					;
				return ;
			}

			// x[1] = x[2] - x[0] * q (mod b0)
			SubMulMod( x0, q, x2, b0, x1 );

			// {q, b} = b / a
			udivide( b, a, q, b );

			// if b = 0, return x[1]
			if ( isZero( b ) )
			{
				set ( ap, x1 )

					;
				return ;
			}

			// x[2] = x[0] - x[1] * q (mod b0)
			SubMulMod( x1, q, x0, b0, x2 );

			// {q, a} = a / b
			udivide( a, b, q, a );

			// if a = 0, return x[2]
			if ( isZero( a ) )
			{
				set ( ap, x2 )

					;
				return ;
			}

			// x[0] = x[1] - x[2] * q (mod b0)
			SubMulMod( x2, q, x1, b0, x0 );

			// {q, b} = b / a
			udivide( b, a, q, b );

			// if b = 0, return x[0]
			if ( isZero( b ) )
			{
				set ( ap, x0 )

					;
				return ;
			}

			// x[1] = x[2] - x[0] * q (mod b0)
			SubMulMod( x0, q, x2, b0, x1 );

			// {q, a} = a / b
			udivide( a, b, q, a );

			// if a = 0, return x[1]
			if ( isZero( a ) )
			{
				set ( ap, x1 )

					;
				return ;