integer.cpp

各种加密算法的集合

#include "pch.h" 
#include "integer.h" 
#include "modarith.h" 
#include "nbtheory.h" 
#include "asn.h" 
#include "words.h" 
 
#include <iostream> 
 
#include "algebra.cpp" 
#include "eprecomp.cpp" 
 
NAMESPACE_BEGIN(CryptoPP) 
 
#define MAKE_DWORD(lowWord, highWord) ((dword(highWord)<<WORD_BITS) | (lowWord)) 
 
#if defined(_MSC_VER) && defined(_M_IX86) && (_M_IX86<=500) 
 
// Add() and Subtract() are coded in Pentium assembly for a speed increase 
// of about 10-20 percent for a RSA signature 
 
static __declspec(naked) word __fastcall Add(word *C, const word *A, const word *B, unsigned int N) 
{ 
	__asm 
	{ 
		push ebp 
		push ebx 
		push esi 
		push edi 
 
		mov esi, [esp+24] 
		mov ebx, [esp+20] 
 
		sub ecx, edx 
		xor eax, eax 
 
		sub eax, esi 
		lea ebx, [ebx+4*esi] 
 
		sar eax, 1		// clears the carry flag 
		jz  loopend 
 
loopstart: 
		mov    esi,[edx] 
		mov    ebp,[edx+4] 
 
		mov    edi,[ebx+8*eax] 
		lea    edx,[edx+8] 
 
		adc    esi,edi 
		mov    edi,[ebx+8*eax+4] 
 
		adc    ebp,edi 
		inc    eax 
 
		mov    [edx+ecx-8],esi 
		mov    [edx+ecx-4],ebp 
 
		jnz    loopstart 
 
loopend: 
		adc eax, 0 
		pop edi 
		pop esi 
		pop ebx 
		pop ebp 
		ret 8 
	} 
} 
 
static __declspec(naked) word __fastcall Subtract(word *C, const word *A, const word *B, unsigned int N) 
{ 
	__asm 
	{ 
		push ebp 
		push ebx 
		push esi 
		push edi 
 
		mov esi, [esp+24] 
		mov ebx, [esp+20] 
 
		sub ecx, edx 
		xor eax, eax 
 
		sub eax, esi 
		lea ebx, [ebx+4*esi] 
 
		sar eax, 1		// clears the carry flag 
		jz  loopend 
 
loopstart: 
		mov    esi,[edx] 
		mov    ebp,[edx+4] 
 
		mov    edi,[ebx+8*eax] 
		lea    edx,[edx+8] 
 
		sbb    esi,edi 
		mov    edi,[ebx+8*eax+4] 
 
		sbb    ebp,edi 
		inc    eax 
 
		mov    [edx+ecx-8],esi 
		mov    [edx+ecx-4],ebp 
 
		jnz    loopstart 
 
loopend: 
		adc eax, 0 
		pop edi 
		pop esi 
		pop ebx 
		pop ebp 
		ret 8 
	} 
} 
 
#else	// defined(_MSC_VER) && defined(_M_IX86) && (_M_IX86<=500) 
 
static word Add(word *C, const word *A, const word *B, unsigned int N) 
{ 
	assert (N%2 == 0); 
 
	word carry=0; 
	for (unsigned i = 0; i < N; i+=2) 
	{ 
		dword u = (dword) carry + A[i] + B[i]; 
		C[i] = LOW_WORD(u); 
		u = (dword) HIGH_WORD(u) + A[i+1] + B[i+1]; 
		C[i+1] = LOW_WORD(u); 
		carry = HIGH_WORD(u); 
	} 
	return carry; 
} 
 
static word Subtract(word *C, const word *A, const word *B, unsigned int N) 
{ 
	assert (N%2 == 0); 
 
	word borrow=0; 
	for (unsigned i = 0; i < N; i+=2) 
	{ 
		dword u = (dword) A[i] - B[i] - borrow; 
		C[i] = LOW_WORD(u); 
		u = (dword) A[i+1] - B[i+1] - (word)(0-HIGH_WORD(u)); 
		C[i+1] = LOW_WORD(u); 
		borrow = 0-HIGH_WORD(u); 
	} 
	return borrow; 
} 
 
#endif	// defined(_MSC_VER) && defined(_M_IX86) && (_M_IX86<=500) 
 
static int Compare(const word *A, const word *B, unsigned int N) 
{ 
	while (N--) 
		if (A[N] > B[N]) 
			return 1; 
		else if (A[N] < B[N]) 
			return -1; 
 
	return 0; 
} 
 
static word Increment(word *A, unsigned int N, word B=1) 
{ 
	assert(N); 
	word t = A[0]; 
	A[0] = t+B; 
	if (A[0] >= t) 
		return 0; 
	for (unsigned i=1; i<N; i++) 
		if (++A[i]) 
			return 0; 
	return 1; 
} 
 
static word Decrement(word *A, unsigned int N, word B=1) 
{ 
	assert(N); 
	word t = A[0]; 
	A[0] = t-B; 
	if (A[0] <= t) 
		return 0; 
	for (unsigned i=1; i<N; i++) 
		if (A[i]--) 
			return 0; 
	return 1; 
} 
 
static void TwosComplement(word *A, unsigned int N) 
{ 
	Decrement(A, N); 
	for (unsigned i=0; i<N; i++) 
		A[i] = ~A[i]; 
} 
 
static word LinearMultiply(word *C, const word *A, word B, unsigned int N) 
{ 
	word carry=0; 
	for(unsigned i=0; i<N; i++) 
	{ 
		dword p = (dword)A[i] * B + carry; 
		C[i] = LOW_WORD(p); 
		carry = HIGH_WORD(p); 
	} 
	return carry; 
} 
 
static void AtomicMultiply(word *C, word A0, word A1, word B0, word B1) 
{ 
	word s; 
	dword d; 
 
	if (A1 >= A0) 
		if (B0 >= B1) 
		{ 
			s = 0; 
			d = (dword)(A1-A0)*(B0-B1); 
		} 
		else 
		{ 
			s = (A1-A0); 
			d = (dword)s*(word)(B0-B1); 
		} 
	else 
		if (B0 > B1) 
		{ 
			s = (B0-B1); 
			d = (word)(A1-A0)*(dword)s; 
		} 
		else 
		{ 
			s = 0; 
			d = (dword)(A0-A1)*(B1-B0); 
		} 
 
	dword A0B0 = (dword)A0*B0; 
	C[0] = LOW_WORD(A0B0); 
 
	dword A1B1 = (dword)A1*B1; 
	dword t = (dword) HIGH_WORD(A0B0) + LOW_WORD(A0B0) + LOW_WORD(d) + LOW_WORD(A1B1); 
	C[1] = LOW_WORD(t); 
 
	t = A1B1 + HIGH_WORD(t) + HIGH_WORD(A0B0) + HIGH_WORD(d) + HIGH_WORD(A1B1) - s; 
	C[2] = LOW_WORD(t); 
	C[3] = HIGH_WORD(t); 
} 
 
static word AtomicMultiplyAdd(word *C, word A0, word A1, word B0, word B1) 
{ 
	word s; 
	dword d; 
 
	if (A1 >= A0) 
		if (B0 >= B1) 
		{ 
			s = 0; 
			d = (dword)(A1-A0)*(B0-B1); 
		} 
		else 
		{ 
			s = (A1-A0); 
			d = (dword)s*(word)(B0-B1); 
		} 
	else 
		if (B0 > B1) 
		{ 
			s = (B0-B1); 
			d = (word)(A1-A0)*(dword)s; 
		} 
		else 
		{ 
			s = 0; 
			d = (dword)(A0-A1)*(B1-B0); 
		} 
 
	dword A0B0 = (dword)A0*B0; 
	dword t = A0B0 + C[0]; 
	C[0] = LOW_WORD(t); 
 
	dword A1B1 = (dword)A1*B1; 
	t = (dword) HIGH_WORD(t) + LOW_WORD(A0B0) + LOW_WORD(d) + LOW_WORD(A1B1) + C[1]; 
	C[1] = LOW_WORD(t); 
 
	t = (dword) HIGH_WORD(t) + LOW_WORD(A1B1) + HIGH_WORD(A0B0) + HIGH_WORD(d) + HIGH_WORD(A1B1) - s + C[2]; 
	C[2] = LOW_WORD(t); 
 
	t = (dword) HIGH_WORD(t) + HIGH_WORD(A1B1) + C[3]; 
	C[3] = LOW_WORD(t); 
	return HIGH_WORD(t); 
} 
 
static inline void AtomicSquare(word *C, word A, word B) 
{ 
	dword t1 = (dword) A*A; 
	C[0] = LOW_WORD(t1); 
 
	dword t2 = (dword) A*B; 
	t1 = (dword) HIGH_WORD(t1) + LOW_WORD(t2) + LOW_WORD(t2); 
	C[1] = LOW_WORD(t1); 
 
	t1 = (dword) B*B + HIGH_WORD(t1) + HIGH_WORD(t2) + HIGH_WORD(t2); 
	C[2] = LOW_WORD(t1); 
	C[3] = HIGH_WORD(t1); 
} 
 
static inline void AtomicMultiplyBottom(word *C, word A0, word A1, word B0, word B1) 
{ 
	dword t = (dword)A0*B0; 
	C[0] = LOW_WORD(t); 
	C[1] = HIGH_WORD(t) + A0*B1 + A1*B0; 
} 
 
static inline void AtomicMultiplyBottomAdd(word *C, word A0, word A1, word B0, word B1) 
{ 
	dword t = (dword)A0*B0 + C[0]; 
	C[0] = LOW_WORD(t); 
	C[1] += HIGH_WORD(t) + A0*B1 + A1*B0; 
} 
 
static void CombaMultiply(word *R, const word *A, const word *B) 
{ 
	dword p; 
	word c=0, d=0, e=0; 
 
#define MulAcc(x, y)								\ 
	p = (dword)A[x] * B[y] + c;						\ 
	c = LOW_WORD(p);								\ 
	p = (dword)d + HIGH_WORD(p);					\ 
	d = LOW_WORD(p);								\ 
	e += HIGH_WORD(p); 
 
#define SaveMulAcc(s, x, y)							\ 
	R[s] = c;										\ 
	p = (dword)A[x] * B[y] + d;						\ 
	c = LOW_WORD(p);								\ 
	p = (dword)e + HIGH_WORD(p);					\ 
	d = LOW_WORD(p);								\ 
	e = HIGH_WORD(p); 
 
	p = (dword)A[0] * B[0]; 
	R[0] = LOW_WORD(p); 
	c = HIGH_WORD(p); 
	d = e = 0; 
 
	MulAcc(0, 1); 
	MulAcc(1, 0); 
 
	SaveMulAcc(1, 2, 0); 
	MulAcc(1, 1); 
	MulAcc(0, 2); 
 
	SaveMulAcc(2, 0, 3); 
	MulAcc(1, 2); 
	MulAcc(2, 1); 
	MulAcc(3, 0); 
 
	SaveMulAcc(3, 3, 1); 
	MulAcc(2, 2); 
	MulAcc(1, 3); 
 
	SaveMulAcc(4, 2, 3); 
	MulAcc(3, 2); 
 
	R[5] = c; 
	p = (dword)A[3] * B[3] + d; 
	R[6] = LOW_WORD(p); 
	R[7] = e + HIGH_WORD(p); 
 
#undef MulAcc 
#undef SaveMulAcc 
} 
 
static void AtomicInverseModPower2(word *C, word A0, word A1) 
{ 
	assert(A0%2==1); 
 
	dword A=MAKE_DWORD(A0, A1), R=A0%8; 
 
	for (unsigned i=3; i<2*WORD_BITS; i*=2) 
		R = R*(2-R*A); 
 
	assert(R*A==1); 
 
	C[0] = LOW_WORD(R); 
	C[1] = HIGH_WORD(R); 
} 
 
// ******************************************************** 
 
#define A0		A 
#define A1		(A+N2) 
#define B0		B 
#define B1		(B+N2) 
 
#define T0		T 
#define T1		(T+N2) 
#define T2		(T+N) 
#define T3		(T+N+N2) 
 
#define R0		R 
#define R1		(R+N2) 
#define R2		(R+N) 
#define R3		(R+N+N2) 
 
// R[2*N] - result = A*B 
// T[2*N] - temporary work space 
// A[N] --- multiplier 
// B[N] --- multiplicant 
 
void RecursiveMultiply(word *R, word *T, const word *A, const word *B, unsigned int N) 
{ 
	assert(N>=2 && N%2==0); 
 
	if (N==2) 
		AtomicMultiply(R, A[0], A[1], B[0], B[1]); 
	else if (N==4) 
		CombaMultiply(R, A, B); 
	else 
	{ 
		const unsigned int N2 = N/2; 
		int carry; 
 
		int aComp = Compare(A0, A1, N2); 
		int bComp = Compare(B0, B1, N2); 
 
		switch (2*aComp + aComp + bComp) 
		{ 
		case -4: 
			Subtract(R0, A1, A0, N2); 
			Subtract(R1, B0, B1, N2); 
			RecursiveMultiply(T0, T2, R0, R1, N2); 
			Subtract(T1, T1, R0, N2); 
			carry = -1; 
			break; 
		case -2: 
			Subtract(R0, A1, A0, N2); 
			Subtract(R1, B0, B1, N2); 
			RecursiveMultiply(T0, T2, R0, R1, N2); 
			carry = 0; 
			break; 
		case 2: 
			Subtract(R0, A0, A1, N2); 
			Subtract(R1, B1, B0, N2); 
			RecursiveMultiply(T0, T2, R0, R1, N2); 
			carry = 0; 
			break; 
		case 4: 
			Subtract(R0, A1, A0, N2); 
			Subtract(R1, B0, B1, N2); 
			RecursiveMultiply(T0, T2, R0, R1, N2); 
			Subtract(T1, T1, R1, N2); 
			carry = -1; 
			break; 
		default: 
			SetWords(T0, 0, N); 
			carry = 0; 
		} 
 
		RecursiveMultiply(R0, T2, A0, B0, N2); 
		RecursiveMultiply(R2, T2, A1, B1, N2); 
 
		// now T[01] holds (A1-A0)*(B0-B1), R[01] holds A0*B0, R[23] holds A1*B1 
 
		carry += Add(T0, T0, R0, N); 
		carry += Add(T0, T0, R2, N); 
		carry += Add(R1, R1, T0, N); 
 
		assert (carry >= 0 && carry <= 2); 
		Increment(R3, N2, carry); 
	} 
} 
 
// R[2*N] - result = A*A 
// T[2*N] - temporary work space 
// A[N] --- number to be squared 
 
void RecursiveSquare(word *R, word *T, const word *A, unsigned int N) 
{ 
	assert(N && N%2==0); 
 
	if (N==2) 
		AtomicSquare(R, A[0], A[1]); 
	else if (N==4) 
	{ 
		AtomicSquare(R, A[0], A[1]); 
		AtomicSquare(R+4, A[2], A[3]); 
		AtomicMultiply(T, A[0], A[1], A[2], A[3]); 
		word carry = Add(R+2, R+2, T, 4); 
		carry += Add(R+2, R+2, T, 4); 
		Increment(R+6, 2, carry); 
	} 
	else 
	{ 
		const unsigned int N2 = N/2; 
 
		RecursiveSquare(R0, T2, A0, N2); 
		RecursiveSquare(R2, T2, A1, N2); 
		RecursiveMultiply(T0, T2, A0, A1, N2); 
 
		word carry = Add(R1, R1, T0, N); 
		carry += Add(R1, R1, T0, N); 
		Increment(R3, N2, carry); 
	} 
} 
 
// R[N] - bottom half of A*B 
// T[N] - temporary work space 
// A[N] - multiplier 
// B[N] - multiplicant 
 
void RecursiveMultiplyBottom(word *R, word *T, const word *A, const word *B, unsigned int N) 
{ 
	assert(N>=2 && N%2==0); 
 
	if (N==2) 
		AtomicMultiplyBottom(R, A[0], A[1], B[0], B[1]); 
	else if (N==4) 
	{ 
		AtomicMultiply(R, A[0], A[1], B[0], B[1]); 
		AtomicMultiplyBottomAdd(R+2, A[0], A[1], B[2], B[3]); 
		AtomicMultiplyBottomAdd(R+2, A[2], A[3], B[0], B[1]); 
	} 
	else 
	{ 
		const unsigned int N2 = N/2; 
 
		RecursiveMultiply(R, T, A0, B0, N2); 
		RecursiveMultiplyBottom(T0, T1, A1, B0, N2); 
		Add(R1, R1, T0, N2); 
		RecursiveMultiplyBottom(T0, T1, A0, B1, N2); 
		Add(R1, R1, T0, N2); 
	} 
} 
 
// R[N] --- upper half of A*B 
// T[2*N] - temporary work space 
// L[N] --- lower half of A*B 
// A[N] --- multiplier 
// B[N] --- multiplicant 
 
void RecursiveMultiplyTop(word *R, word *T, const word *L, const word *A, const word *B, unsigned int N) 
{ 
	assert(N>=2 && N%2==0); 
 
	if (N==2) 
	{ 
		AtomicMultiply(T, A[0], A[1], B[0], B[1]); 
		R[0] = T[2]; 
		R[1] = T[3]; 
	} 
	else 
	{ 
		const unsigned int N2 = N/2; 
		int carry; 
 
		int aComp = Compare(A0, A1, N2); 
		int bComp = Compare(B0, B1, N2); 
 
		switch (2*aComp + aComp + bComp) 
		{ 
		case -4: 
			Subtract(R0, A1, A0, N2); 
			Subtract(R1, B0, B1, N2); 
			RecursiveMultiply(T0, T2, R0, R1, N2); 
			Subtract(T1, T1, R0, N2); 
			carry = -1; 
			break; 
		case -2: 
			Subtract(R0, A1, A0, N2); 
			Subtract(R1, B0, B1, N2); 
			RecursiveMultiply(T0, T2, R0, R1, N2); 
			carry = 0; 
			break; 
		case 2: 
			Subtract(R0, A0, A1, N2); 
			Subtract(R1, B1, B0, N2); 
			RecursiveMultiply(T0, T2, R0, R1, N2); 
			carry = 0; 
			break; 
		case 4: 
			Subtract(R0, A1, A0, N2); 
			Subtract(R1, B0, B1, N2); 
			RecursiveMultiply(T0, T2, R0, R1, N2); 
			Subtract(T1, T1, R1, N2); 
			carry = -1; 
			break; 
		default: