📄 mycryptlib.cpp
字号:
return FALSE;
}
// Rabin-Miller from FIPS-186-2 Appendix 2.
// Step 1. Set i = 1 [but do # tests requested by user].
// Step 2. Find a and m where w = 1 + (2^a)m
// m is odd and 2^a is largest power of 2 dividing w - 1
BNSubtractdw(w1, w, 1, nSize);
BNSetEqual(m, w1, nSize);
for (BNSetZero(a, nSize); (!(m[0]&0x1)); BNAdddw(a, a, 1, nSize))
{
BNShiftRight(m, m, 1, nSize);
}
if ( BNSizeof(w, nSize) == 1 )
maxrand = w[0] - 1;
else
maxrand = _MAXIMUMNR_;
bisprime = TRUE;
for (i = 0; i < t; i++)
{
failed = 1;
// Step 3. Generate random integer b, 1 < b < w
BNSetZero(b, nSize);
do
{
b[0] = RandBetween(2, maxrand);
} while (BNCompare(b, w, nSize) >= 0);
// Step 4. Set j = 0 and z = b^m mod w
BNSetZero(j, nSize);
BNModExp(z, b, m, w, nSize);
do
{
// Step 5. If j = 0 and z = 1, or if z = w - 1 */
if ((BNIsZero(j, nSize) && BNComparedw(z, 1, nSize) == 0) || (BNCompare(z, w1, nSize) == 0))
{ // Passes on this loop - go to Step 9
failed = 0;
break;
}
// Step 6. If j > 0 and z = 1 */
if ( !BNIsZero(j, nSize) && (BNComparedw(z, 1, nSize) == 0) )
{ // Fails - go to Step 8
failed = 1;
break;
}
// Step 7. j = j + 1. If j < a set z = z^2 mod w
BNAdddw(j, j, 1, nSize);
if ( BNCompare(j, a, nSize) < 0 )
BNModMult(z, z, z, w, nSize);
// if j < a go to Step 5
} while (BNCompare(j, a, nSize) < 0);
if ( failed )
{ // Step 8. Not a prime.
bisprime = FALSE;
break;
}
}
BNSetZero(m, nSize);
BNSetZero(a, nSize);
BNSetZero(b, nSize);
BNSetZero(z, nSize);
BNSetZero(w1, nSize);
BNSetZero(j, nSize);
BNFree(&m);
BNFree(&a);
BNFree(&b);
BNFree(&z);
BNFree(&w1);
BNFree(&j);
return bisprime;
}
/* The Mersenne Twister Random generator init
* The function inits the Random generator with pRandomPool and nSize
* If the pRandomPool is not provided it uses the old dangerus srand() and rand() to
* init.
*/
inline BOOL MyCryptLib::MTInit(BYTE *pRandomPool, UINT nSize)
{
// If no Random pool is given use the Function MTCollectEntropy to
// get entopry from the HW (see the MTCollectEntropy) function. The acctual
// entropy we get is less than ~128 bits. It's a good idea to have a tenth
// to a fifth as much entropy as the length of the key othervise it
// is very dangerous. But hey FBI & CIA is no after oss right ? :=)
if ( pRandomPool==NULL || nSize<624*4 )
{
if ( nSize>0&&pRandomPool )
{
memcpy(&m_mtbuffer,pRandomPool,nSize);
}
// If entropy is not given collect from HW.
if ( nSize<624*4 )
{
BYTE *pmtbuffer=(BYTE*)&m_mtbuffer;
MTCollectEntropy(pmtbuffer+nSize,624*4-nSize);
}
m_bSeeded=TRUE;
}
m_mtIndex=624; // Start with performin the shuffel so the randomness is spread around.
return m_bSeeded;
}
/*
* MTCollectEntropy(BYTE *pRandomPool, UINT nSize)
*
* This function collects entropy (true randomness) from the Hardware
* Using different source namely:
*
* - System time
* - Current process ID
* - Current thread ID
* - Get clock ticks since system booted
* - The nr pages and memory allockated.
*
* The entropies above are destilled to with SHA1 hash function to fill the
* pRadomPool of size nSize.
*
* Observe! Warning!
* - This function gives approximatly ~128 bit entropy destilled into
* pRandomPool with nSize.
* - The last 20 bytes may hold more entropie than the other in pRandomPool, Additional
* destilling is needed.
*/
BOOL MyCryptLib::MTCollectEntropy(BYTE *pRandomPool, UINT nSize)
{
SYSTEMTIME st;
FILETIME ft;
MEMORYSTATUS ms;
SHA1_STATETYPE csha1;
UINT nCollected = 0;
BYTE EntropyBucket[SHA1_DIGEST_SIZE];
BYTE *pEntropyBucket=(BYTE*)EntropyBucket;
DWORD dwRes=0;
DWORD dwTick=0;
ms.dwLength = sizeof(MEMORYSTATUS);
memset(&csha1,0,sizeof(csha1));
SHA1_Start(&csha1);
while ( nSize-nCollected>0 )
{
// Hash the previus entropy Bucket..
SHA1_Hash(pEntropyBucket,SHA1_DIGEST_SIZE,&csha1);
// Destill The process ID
dwRes=GetCurrentProcessId();
SHA1_Hash((BYTE*)&dwRes,sizeof(DWORD),&csha1);
// Destill The thread ID
dwRes=GetCurrentThreadId();
SHA1_Hash((BYTE*)&dwRes,sizeof(DWORD),&csha1);
// Destill The system time.
GetSystemTime(&st);
SystemTimeToFileTime(&st, &ft);
SHA1_Hash((BYTE*)&ft,sizeof(FILETIME),&csha1);
// Destill The processors tickcount.
dwTick = GetTickCount();
SHA1_Hash((BYTE*)&dwTick,sizeof(DWORD),&csha1);
// Destill The memory allocated
GlobalMemoryStatus(&ms);
SHA1_Hash((BYTE*)&ms, sizeof(MEMORYSTATUS),&csha1);
// Put it inside the Bucket.
SHA1_Finish(EntropyBucket,&csha1);
// Copy the Entropy to the pool
if ( nSize-nCollected<SHA1_DIGEST_SIZE )
{
memcpy(pRandomPool+nCollected,pEntropyBucket,nSize-nCollected);
nCollected+=nSize-nCollected;
}
else
{
memcpy(pRandomPool+nCollected,pEntropyBucket,SHA1_DIGEST_SIZE);
nCollected+=SHA1_DIGEST_SIZE;
}
}
return TRUE;
}
/*
* The Mersenne Twister is a new random number generator,
* discovered in 1996 by Matsumora and Nishimura.
* MT is a twisted GFSR(624,397), similar in spirit to R250 and R521 but faster.
* It takes up more space than R250 or R521, but less than the two combined.
* MT has an amazing period of 2^19937-1. Overall, and passes all the statistical tests.
* Assumes it is already initciaded.
*
* More info () ----------------------------------------
* The Mersenne Twister, a new variant of the twisted GFSR ("TGFSR") by Matsumoto and Nishimura,
* sets new standards for the period, quality and speed of random number generators. The incredible
* period is 219937 - 1, a number with about 6000 decimal digits; the 32-bit random numbers exhibit
* best possible equidistribution properties in dimensions up to 623; and it's fast, very fast.
* A paper on the Mersenne Twister has been submitted to ACM TOMACS.
*
* The Mersenne Twister generator passes all current statistical tests.
*/
inline DWORD MyCryptLib::MTRandom()
{
if( !m_bSeeded )
MTInit();
if ( m_mtIndex >= 624 )
{
m_mtIndex = 0;
int i = 0;
int s;
for (; i < 624 - 397; i++) {
s = (m_mtbuffer[i] & 0x80000000) | (m_mtbuffer[i+1] & 0x7FFFFFFF);
m_mtbuffer[i] = m_mtbuffer[i + 397] ^ (s >> 1) ^ ((s & 1) * 0x9908B0DF);
}
for (; i < 623; i++) {
s = (m_mtbuffer[i] & 0x80000000) | (m_mtbuffer[i+1] & 0x7FFFFFFF);
m_mtbuffer[i] = m_mtbuffer[i - (624 - 397)] ^ (s >> 1) ^ ((s & 1) * 0x9908B0DF);
}
s = (m_mtbuffer[623] & 0x80000000) | (m_mtbuffer[0] & 0x7FFFFFFF);
m_mtbuffer[623] = m_mtbuffer[396] ^ (s >> 1) ^ ((s & 1) * 0x9908B0DF);
}
DWORD tmp=m_mtbuffer[m_mtIndex++];
tmp ^= (tmp >> 11);
tmp ^= (tmp << 7) & 0x9D2C5680UL;
tmp ^= (tmp << 15) & 0xEFC60000UL;
return tmp ^ (tmp >> 18);
}
/*
* Generates an Random nr between dwLower and dwUpper.
*/
inline DWORD MyCryptLib::RandBetween(DWORD dwLower, DWORD dwUpper)
{
DWORD d, range;
unsigned char *bp;
int i, nbits;
DWORD mask;
if ( dwUpper <= dwLower )
{
return dwLower;
}
range = dwUpper - dwLower;
do
{
bp = (unsigned char *)&d;
for (i = 0; i < sizeof(DWORD); i++)
{
bp[i] = BYTE(MTRandom() & 0xFF);
}
mask = _HIBITMASK_;
for (nbits = sizeof(DWORD)*8; nbits > 0; nbits--, mask >>= 1)
{
if (range & mask)
break;
}
if (nbits < sizeof(DWORD)*8)
{
mask <<= 1;
mask--;
}
else
mask = _MAXIMUMNR_;
d &= mask;
} while (d > range);
return (dwLower + d);
}
/*
* Returns true if w > 2 is a probable prime
* tryes some small nr primes and then uses
* the rabin Miller alghorim to detect the prime nr
*
* nrRounds denotes the number of rounds to use when determine that
* the number is an primenumber or not.
*/
int MyCryptLib::BNIsPrime(DWORD W[], UINT nSize, UINT nrRounds)
{
// if the number is even then return FALSE;
if ((!(W[0] & 0x1)))
return 0;
// if the number is bigger than the biggest prime nr..
if (BNComparedw(W, SMALL_PRIMES[_NUMBEROFPRIMES_-1], nSize) > 0)
{
for (UINT i = 0; i < _NUMBEROFPRIMES_; i++)
{
if (BNModdw(W, SMALL_PRIMES[i], nSize) == 0) // if the number contain one of the small primes.
return FALSE;
}
}
else //W < Biggest prime in the list so we are going to check it our self.
{
for (UINT i = 0; i < _NUMBEROFPRIMES_; i++)
{
if (BNComparedw(W, SMALL_PRIMES[i], nSize) == 0)
return TRUE; // Is an small prime
}
return FALSE; // Not an prime.
}
// Use Rabin Miller now.
return BNRabinMiller(W, nSize, nrRounds);
}
/*
* Creates an prime nr.
* Return number of signifikant bits if success, -1 if the functions did not sucess.
* -------------------------------------------------------------------------------------------
* The prime nr is not completly cryptographically secure because it relies on the
* Mersenne Twister random generator, and Rabin Miller prime detection algorithm.
* But if it is propetly seeded it is quite safe (se below).
* ------------------------
* The Mersenne Twister, a new variant of the twisted GFSR ("TGFSR") by Matsumoto and Nishimura,
* sets new standards for the period, quality and speed of random number generators. The incredible
* period is 2^(219937 - 1), a number with about 6000 decimal digits; the 32-bit random numbers exhibit
* best possible equidistribution properties in dimensions up to 623; and it's fast, very fast.
* A paper on the Mersenne Twister has been submitted to ACM TOMACS.
*
* The Mersenne Twister generator passes all current statistical tests.
*/
int MyCryptLib::BNMakePrime(DWORD p[], UINT nSize, PBYTE pEntropyPool, UINT nSizeEntropyPool)
{
// if entropy is provided use it!
if ( pEntropyPool )
{
MTInit(pEntropyPool,nSizeEntropyPool);
}
for ( UINT i = 0; i < nSize; i++ )
p[i] = MTRandom();
// Make sure the highest and low bits are set, so we have an nice big odd nr.
p[nSize - 1] |= _HIBITMASK_;
p[0] |= 0x1;
// Check if prime
// Why 10 rounds ? well
// DSS Standard recommends using t >= 50
// Ferguson & Schneier recommend t = 64 for prob error < 2^-128
// But in practice the moste primes is found in round one or two so 10 is an nice
// home made nr of rounds.
while (!BNIsPrime(p, nSize, 10) )
{
// Keep adding 2 until we find a prime
BNAdddw(p, p, 2, nSize);
// Check for overflow
if (!(p[nSize - 1] & _HIBITMASK_))
return -1; // Failed to find a prime
}
// return nr of significant bits.
return BNBitLength(p,nSize);
}
/*
* BNMakeRSAPrime(DWORD p[], DWORD ee[], UINT nSize)
*
* Return number of signifikant bits if success, -1 if the functions did not sucess.
* -------------------------------------------------------------------------------------------
* The prime nr is not completly cryptographically secure because it relies on the
* Mersenne Twister random generator, and Rabin Miller prime detection algorithm.
* But if it is propetly seeded it is quite safe (se below).
* ------------------------
* The Mersenne Twister, a new variant of the twisted GFSR ("TGFSR") by Matsumoto and Nishimura,
* sets new standards for the period, quality and speed of random number generators. The incredible
* period is 219937 - 1, a number with about 6000 decimal digits; the 32-bit random numbers exhibit
* best possible equidistribution properties in dimensions up to 623; and it's fast, very fast.
* A paper on the Mersenne Twister has been submitted to ACM TOMACS.
*
* The Mersenne Twister generator passes all current statistical tests.
*
* Important assumptions!:
* - ee is an Fermat prime nr greater than 2.
*
*/
int MyCryptLib::BNMakeRSAPrime(DWORD p[], DWORD ee, UINT nSize,UINT nMaximumRetry)
{
UINT nRet=-1;
for ( UINT i=0; i<nMaximumRetry; i++ )
{
nRet=BNMakePrime(p,nSize);
if(nRet>0&&BNModdw(p, ee,nSize)!=1)
break;
}
return nRet;
}
/*
* Creates an random nr.
*
* OBS!! not cryptographically secure!! why?
* Well we do some homemade modification to the number.
* 1) We fill it up to n (n also random) with random numbers
* 2) We fill the rest with zeros.
* 3) We mask the number n with an mask.
*
* why? Because of practical resons, we do not whant numbers near owerflow and underflow.!
*/
UINT MyCryptLib::BNMakeRandomNr(DWORD a[], UINT nSize)
{
UINT i, n, bits;
DWORD mask;
n = (UINT)RandBetween(1, nSize);
for ( i = 0; i < n; i++)
a[i] = MTRandom();
for ( i = n; i < nSize; i++)
a[i] = 0;
// Mask it 50% chance
bits = (UINT)RandBetween(0, 16*sizeof(DWORD));
if ( bits != 0 && bits < 8*sizeof(DWORD) )
{
mask = _HIBITMASK_;
for (i = 1; i < bits; i++)
{
mask |= (mask >> 1);
}
mask = ~mask;
a[n-1] &= mask;
}
return n;
}
/*
* Generates keys used for RSA Encryption/Decryption Algorithm
*
* n is the public key modulus..
* e is the public exponent encryption exponent.
* d is the secret exponent or decryption exponent.
* The private key as a quintuple (p, q, dP, dQ, and qInv), is used
* for the Chinese Remainder Theorem (CRT) decryption.
* The CRT method of decryption is four times faster overall
* than calculating m = c^d mod n.
* p and q are prime factors of n.
* dP and dQ are known as the CRT exponents.
* qInv is the CRT coefficient.
*
* nPSize is the size of the prime nr P
* nQSize is the size of the prime nr Q
*
* The key length is nPSize+nQSize
*
* nSize is the size of the input variables.
*
* Observe! nSize must be big enough (eg nSize>=max(nPSize,nQSize)*2)
*
* In practice, common choices for e are 3, 17 and 65537 (2^16+1). These are Fermat primes and are chosen
* because they make the modular exponentiation operation faster.
*
* Assumed that e is an primenumber greater than 2.
*
* pSeedData is an pointer to an Random number pool of size nSeedData.
* This pool is used with the Mersenne Twister random nr generator to
* if pSeedData is NULL then the Random number pool is seeded with
* current time since 1981 and time in ms since the computer started and the
* old srand() rand function.
* if e is NULL then the the default nr 65537.
*/
int MyCryptLib::RSAGenerateKey(DWORD n[], DWORD d[], DWORD p[], DWORD q[], DWORD dP[], DWORD dQ[], DWORD qInv[], UINT nSize, UINT nPSize,UINT nQSize,DWORD e, BYTE* pSeedData,UINT nSeedData)
{
// Make sure that nSize is big enough
if( nSize<max(nPSize,nQSize)*2 )
return -30;
// The operation size of primes. (they are bigger than this nr)
UINT nPrimeSize=max(nPSize,nQSize);
// The operation size of public key N.
UINT nNSize=0;
// The operation size of private key D.
UINT nDSize=0;
// Create some temporary data.
DWORD *pG=BNAlloc(nSize);
if ( pG==NULL )
{
return -1;
}
DWORD *pP1=BNAlloc(nSize);
if ( pP1==NULL )
{
BNFree(&pG);
return -2;
}
DWORD *pQ1=BNAlloc(nSize);
if ( pQ1==NULL )
{
BNFree(&pG);
BNFree(&pP1);
return -3;
}
DWORD *pPhi=BNAlloc(nSize);
if ( pPhi==NULL )
{
BNFree(&pG);
BNFree(&pP1);
BNFree(&pQ1);
return -4;
}
DWORD *pE=BNAlloc(nSize);
if ( pE==NULL )
{
BNFree(&pG);
BNFree(&pP1);
BNFree(&pQ1);
BNFree(&pPhi);
return -5;
}
if ( pSeedData!=NULL && nSeedData>=0 )
MTInit(pSeedData,nSeedData/2);
else
MTInit();
int nRet=BNMakeRSAPrime(p,e,nPSize);
if ( nRet<=0 )
{
BNFree(&pG);
BNFree(&pP1);
BNFree(&pQ1);
BNFree(&pPhi);
BNFree(&pE);
return -6;
}
if ( pSeedData!=NULL && nSeedData>=0)
MTInit(pSeedData+nSeedData/2,nSeedData/2);
else
MTInit();
nRet=BNMakeRSAPrime(q,e,nQSize);
if ( nRet<=0 )
{
BNFree(&pG);
BNFree(&pP1);
BNFree(&pQ1);
BNFree(&pPhi);
BNFree(&pE);
return -7;
}
// Check if the prime nr is ok
if ( BNIsEqual(p,q,nPrimeSize) )
{
BNFree(&pG);
BNFree(&pP1);
BNFree(&pQ1);
BNFree(&pPhi);
BNFree(&pE);
return -8;
}
BNSetEqualdw(pE,e,nSize);
// If q > p swap p and q so p > q
if ( BNCompare(p, q,nPrimeSize) < 1 )
{
BNSetEqual(pG, p,nPrimeSize);
BNSetEqual(p, q,nPrimeSize);
BNSetEqual(q, pG,nPrimeSize);
}
if ( BNSubtractdw(pP1,p,1,nPrimeSize)!=0 )
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -