mpilib.cpp

各种加密算法的集合

*post_lowerunit(r1) = *pre_lowerunit(r2); 
*r1 = 0; 
} /* mp_lshift_unit */ 

/* moduli_buf contains shifted images of the modulus, set by stage_modulus */ 
static unit moduli_buf[UNITSIZE - 1][MAX_UNIT_PRECISION] = 
{0}; 
static unitptr moduli[UNITSIZE] = /* contains pointers into moduli_buf */ 
{0, moduli_buf[0], moduli_buf[1], moduli_buf[2], 
moduli_buf[3], moduli_buf[4], moduli_buf[5], moduli_buf[6] 
#ifndef UNIT8 
,moduli_buf[7], moduli_buf[8], moduli_buf[9], moduli_buf[10], 
moduli_buf[11], moduli_buf[12], moduli_buf[13], moduli_buf[14] 
#ifndef UNIT16 /* and not UNIT8 */ 
,moduli_buf[15], moduli_buf[16], moduli_buf[17], moduli_buf[18], 
moduli_buf[19], moduli_buf[20], moduli_buf[21], moduli_buf[22], 
moduli_buf[23], moduli_buf[24], moduli_buf[25], moduli_buf[26], 
moduli_buf[27], moduli_buf[28], moduli_buf[29], moduli_buf[30] 
#endif /* UNIT16 and UNIT8 not defined */ 
#endif /* UNIT8 not defined */ 
}; 

/* 
* To optimize msubs, need following 2 unit arrays, each filled 
* with the most significant unit and next-to-most significant unit 
* of the preshifted images of the modulus. 
*/ 
static unit msu_moduli[UNITSIZE] = 
{0}; /* most signif. unit */ 
static unit nmsu_moduli[UNITSIZE] = 
{0}; /* next-most signif. unit */ 

/* 
* mpdbuf contains preshifted images of the multiplicand, mod n. 
* It is used only by mp_modmult. It could be staticly declared 
* inside of mp_modmult, but we put it outside mp_modmult so that 
* it can be wiped clean by modmult_burn(), which is called at the 
* end of mp_modexp. This is so that no sensitive data is left in 
* memory after the program exits. 
*/ 
static unit mpdbuf[UNITSIZE - 1][MAX_UNIT_PRECISION] = 
{0}; 

/* 
* Computes UNITSIZE images of r, each shifted left 1 more bit. 
* Used only by modmult function. 
*/ 
static void stage_mp_images(unitptr images[UNITSIZE], unitptr r) 
{ 
short int i; 

images[0] = r; /* no need to move the first image, just copy ptr */ 
for (i = 1; i < UNITSIZE; i++) { 
mp_move(images[i], images[i - 1]); 
mp_shift_left(images[i]); 
msub(images[i], moduli[0]); 
} 
} /* stage_mp_images */ 

/* 
* Computes UNITSIZE images of modulus, each shifted left 1 more bit. 
* Before calling mp_modmult, you must first stage the moduli images by 
* calling stage_modulus. n is the pointer to the modulus. 
* Assumes that global_precision has already been adjusted to the 
* size of the modulus, plus SLOP_BITS. 
*/ 
int stage_merritt_modulus(const unit * n) 
{ 
short int i; 
unitptr msu; /* ptr to most significant unit, for faster msubs */ 

moduli[0] = n; /* no need to move the first image, just copy ptr */ 

/* used by optimized msubs macro... */ 
msu = msbptr(n, global_precision); /* needed by msubs */ 
msu_moduli[0] = *post_lowerunit(msu); 
nmsu_moduli[0] = *msu; 

for (i = 1; i < UNITSIZE; i++) { 
mp_move(moduli[i], moduli[i - 1]); 
mp_shift_left(moduli[i]); 

/* used by optimized msubs macro... */ 
msu = msbptr(moduli[i], global_precision); /* needed by msubs */ 
msu_moduli[i] = *post_lowerunit(msu); /* for faster msubs */ 
nmsu_moduli[i] = *msu; 
} 
return 0; /* normal return */ 
} /* stage_merritt_modulus */ 

/* The following macros, sniffadd and msubs, are used by modmult... */ 
#define sniffadd(i) if (*multiplier &amt; power_of_2(i)) mp_add(prod,mpd[i]) 

/* Unoptimized msubs macro (msubs0) follows... */ 
/* #define msubs0(i) msub(prod,moduli[i]) 
*/ 

/* 
* To optimize msubs, compare the most significant units of the 
* product and the shifted modulus before deciding to call the full 
* mp_compare routine. Better still, compare the upper two units 
* before deciding to call mp_compare. 
* Optimization of msubs relies heavily on standard C left-to-right 
* parsimonious evaluation of logical expressions. 
*/ 

/* Partially-optimized msubs macro (msubs1) follows... */ 
/* #define msubs1(i) if ( \ 
((p_m = (*msu_prod-msu_moduli[i])) >= 0) &amt;&amt; \ 
(p_m || (mp_compare(prod,moduli[i]) >= 0) ) \ 
) mp_sub(prod,moduli[i]) 
*/ 

/* Fully-optimized msubs macro (msubs2) follows... */ 
#define msubs(i) if (((p_m = *msu_prod-msu_moduli[i])>0) || ( \ 
(p_m==0) &amt;&amt; ( (*nmsu_prod>nmsu_moduli[i]) || ( \ 
(*nmsu_prod==nmsu_moduli[i]) &amt;&amt; ((mp_compare(prod,moduli[i]) >= 0)) ))) ) \ 
mp_sub(prod,moduli[i]) 

/* 
* Performs combined multiply/modulo operation. 
* Computes: prod = (multiplicand*multiplier) mod modulus 
* WARNING: All the arguments must be less than the modulus! 
* Assumes the modulus has been predefined by first calling 
* stage_modulus. 
*/ 
int merritt_modmult(register unitptr prod, 
unitptr multiplicand, register unitptr multiplier) 
{ 
/* p_m, msu_prod, and nmsu_prod are used by the optimized msubs macro... */ 
register signedunit p_m; 
register unitptr msu_prod; /* ptr to most significant unit of product */ 
register unitptr nmsu_prod; /* next-most signif. unit of product */ 
short mprec; /* precision of multiplier, in units */ 
/* Array mpd contains a list of pointers to preshifted images of 
the multiplicand: */ 
static unitptr mpd[UNITSIZE] = 
{ 
0, mpdbuf[0], mpdbuf[1], mpdbuf[2], 
mpdbuf[3], mpdbuf[4], mpdbuf[5], mpdbuf[6] 
#ifndef UNIT8 
,mpdbuf[7], mpdbuf[8], mpdbuf[9], mpdbuf[10], 
mpdbuf[11], mpdbuf[12], mpdbuf[13], mpdbuf[14] 
#ifndef UNIT16 /* and not UNIT8 */ 
,mpdbuf[15], mpdbuf[16], mpdbuf[17], mpdbuf[18], 
mpdbuf[19], mpdbuf[20], mpdbuf[21], mpdbuf[22], 
mpdbuf[23], mpdbuf[24], mpdbuf[25], mpdbuf[26], 
mpdbuf[27], mpdbuf[28], mpdbuf[29], mpdbuf[30] 
#endif /* UNIT16 and UNIT8 not defined */ 
#endif /* UNIT8 not defined */ 
}; 

/* Compute preshifted images of multiplicand, mod n: */ 
stage_mp_images(mpd, multiplicand); 

/* To optimize msubs, set up msu_prod and nmsu_prod: */ 
msu_prod = msbptr(prod, global_precision); /* Get ptr to MSU of prod */ 
nmsu_prod = msu_prod; 
post_lowerunit(nmsu_prod); /* Get next-MSU of prod */ 

/* 
* To understand this algorithm, it would be helpful to first 
* study the conventional Russian peasant modmult algorithm. 
* This one does about the same thing as Russian peasant, but 
* is organized differently to save some steps. It loops 
* through the multiplier a word (unit) at a time, instead of 
* a bit at a time. It word-shifts the product instead of 
* bit-shifting it, so it should be faster. It also does about 
* half as many subtracts as Russian peasant. 
*/ 

mp_init(prod, 0); /* Initialize product to 0. */ 

/* 
* The way mp_modmult is actually used in cryptographic 
* applications, there will NEVER be a zero multiplier or 
* multiplicand. So there is no need to optimize for that 
* condition. 
*/ 
/* if (testeq(multiplicand,0)) 
return 0; *//* zero multiplicand means zero product */ 
/* Normalize and compute number of units in multiplier first: */ 
normalize(multiplier, mprec); 
if (mprec == 0) /* if precision of multiplier is 0 */ 
return 0; /* zero multiplier means zero product */ 
make_msbptr(multiplier, mprec); /* start at MSU of multiplier */ 

while (mprec--) { /* Loop for the number of units in the multiplier */ 
/* 
* Shift the product one whole unit to the left. 
* This is part of the multiply phase of modmult. 
*/ 

mp_lshift_unit(prod); 

/* 
* The product may have grown by as many as UNITSIZE 
* bits. That's why we have global_precision set to the 
* size of the modulus plus UNITSIZE slop bits. 
* Now reduce the product back down by conditionally 
* subtracting the preshifted images of the modulus. 
* This is part of the modulo reduction phase of modmult. 
* The following loop is unrolled for speed, using macros... 

for (i=UNITSIZE-1; i>=LOG_UNITSIZE; i--) 
if (mp_compare(prod,moduli[i]) >= 0) 
mp_sub(prod,moduli[i]); 
*/ 

#ifndef UNIT8 
#ifndef UNIT16 /* and not UNIT8 */ 
msubs(31); 
msubs(30); 
msubs(29); 
msubs(28); 
msubs(27); 
msubs(26); 
msubs(25); 
msubs(24); 
msubs(23); 
msubs(22); 
msubs(21); 
msubs(20); 
msubs(19); 
msubs(18); 
msubs(17); 
msubs(16); 
#endif /* not UNIT16 and not UNIT8 */ 
msubs(15); 
msubs(14); 
msubs(13); 
msubs(12); 
msubs(11); 
msubs(10); 
msubs(9); 
msubs(8); 
#endif /* not UNIT8 */ 
msubs(7); 
msubs(6); 
msubs(5); 
#ifndef UNIT32 
msubs(4); 
#ifndef UNIT16 
msubs(3); 
#endif 
#endif 

/* 
* Sniff each bit in the current unit of the multiplier, 
* and conditionally add the corresponding preshifted 
* image of the multiplicand to the product. 
* This is also part of the multiply phase of modmult. 
* 
* The following loop is unrolled for speed, using macros... 

for (i=UNITSIZE-1; i>=0; i--) 
if (*multiplier &amt; power_of_2(i)) 
mp_add(prod,mpd[i]); 
*/ 
#ifndef UNIT8 
#ifndef UNIT16 /* and not UNIT8 */ 
sniffadd(31); 
sniffadd(30); 
sniffadd(29); 
sniffadd(28); 
sniffadd(27); 
sniffadd(26); 
sniffadd(25); 
sniffadd(24); 
sniffadd(23); 
sniffadd(22); 
sniffadd(21); 
sniffadd(20); 
sniffadd(19); 
sniffadd(18); 
sniffadd(17); 
sniffadd(16); 
#endif /* not UNIT16 and not UNIT8 */ 
sniffadd(15); 
sniffadd(14); 
sniffadd(13); 
sniffadd(12); 
sniffadd(11); 
sniffadd(10); 
sniffadd(9); 
sniffadd(8); 
#endif /* not UNIT8 */ 
sniffadd(7); 
sniffadd(6); 
sniffadd(5); 
sniffadd(4); 
sniffadd(3); 
sniffadd(2); 
sniffadd(1); 
sniffadd(0); 

/* 
* The product may have grown by as many as LOG_UNITSIZE+1 
* bits. 
* Now reduce the product back down by conditionally 
* subtracting LOG_UNITSIZE+1 preshifted images of the 
* modulus. This is the modulo reduction phase of modmult. 
* 
* The following loop is unrolled for speed, using macros... 

for (i=LOG_UNITSIZE; i>=0; i--) 
if (mp_compare(prod,moduli[i]) >= 0) 
mp_sub(prod,moduli[i]); 
*/ 

#ifndef UNIT8 
#ifndef UNIT16 
msubs(5); 
#endif 
msubs(4); 
#endif 
msubs(3); 
msubs(2); 
msubs(1); 
msubs(0); 

/* Bump pointer to next lower unit of multiplier: */ 
post_lowerunit(multiplier); 

} /* Loop for the number of units in the 
multiplier */ 

return 0; /* normal return */ 

} /* merritt_modmult */ 

#undef msubs 
#undef sniffadd 

/* 
* Merritt's mp_modmult function leaves some internal tables in memory, 
* so we have to call modmult_burn() at the end of mp_modexp. 
* This is so that no cryptographically sensitive data is left in memory 
* after the program exits. 
*/ 

/* Alias for modmult_burn, merritt_burn() is called only by mp_modexp. */ 
void merritt_burn(void) 
{ 
unitfill0(&amt;(mpdbuf[0][0]), (UNITSIZE - 1) * MAX_UNIT_PRECISION); 
unitfill0(&amt;(moduli_buf[0][0]), (UNITSIZE - 1) * MAX_UNIT_PRECISION); 
unitfill0(msu_moduli, UNITSIZE); 
unitfill0(nmsu_moduli, UNITSIZE); 
} /* merritt_burn() */ 

/******* end of Merritt's MODMULT stuff. *******/ 
/*=========================================================================*/ 
#endif /* MERRITT */ 


#ifdef UPTON_OR_SMITH /* Used by Upton's and Smith's 
modmult algorithms */ 

/* 
* Jimmy Upton's multiprecision modmult algorithm in C. 
* Performs a multiply combined with a modulo operation. 
* 
* The following support functions and data structures 
* are used only by Upton's modmult algorithm... 
*/ 

short munit_prec; /* global_precision expressed in MULTUNITs */ 

/* 
* Note that since the SPARC CPU has no hardware integer multiply 
* instruction, there is not that much advantage in having an 
* assembly version of mp_smul on that machine. It might be faster 
* to use Merritt's modmult instead of Upton's modmult on the SPARC. 
*/ 

/* 
* Multiply the single-word multiplier times the multiprecision integer 
* in multiplicand, accumulating result in prod. The resulting 
* multiprecision prod will be 1 word longer than the multiplicand. 
* multiplicand is munit_prec words long. We add into prod, so caller 
* should zero it out first. For best results, this time-critical 
* function should be implemented in assembly. 
* NOTE: Unlike other functions in the multiprecision arithmetic 
* library, both multiplicand and prod are pointing at the LSB, 
* regardless of byte order of the machine. On an 80x86, this makes 
* no difference. But if this assembly function is implemented 
* on a 680x0, it becomes important. 
*/ 

/* 
* Note that this has been modified from the previous version to allow 
* better support for Smith's modmult: 
* The final carry bit is added to the existing product 
* array, rather than simply stored. 
*/