?? rsacrypt.h
字號:
///
/// \brief \b [Internal] SHA-1 computation class
///
/// Performant RSA en/decryption with 256-bit to 16384-bit modulus
///
/// catid(cat02e@fsu.edu)
///
/// 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 ;
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -