Botan
1.11.15
|
00001 /* 00002 * MPI Algorithms 00003 * (C) 1999-2010 Jack Lloyd 00004 * 2006 Luca Piccarreta 00005 * 00006 * Botan is released under the Simplified BSD License (see license.txt) 00007 */ 00008 00009 #ifndef BOTAN_MP_CORE_OPS_H__ 00010 #define BOTAN_MP_CORE_OPS_H__ 00011 00012 #include <botan/mp_types.h> 00013 00014 namespace Botan { 00015 00016 /* 00017 * The size of the word type, in bits 00018 */ 00019 const size_t MP_WORD_BITS = BOTAN_MP_WORD_BITS; 00020 00021 extern "C" { 00022 00023 /** 00024 * Two operand addition 00025 * @param x the first operand (and output) 00026 * @param x_size size of x 00027 * @param y the second operand 00028 * @param y_size size of y (must be >= x_size) 00029 */ 00030 void bigint_add2(word x[], size_t x_size, 00031 const word y[], size_t y_size); 00032 00033 /** 00034 * Three operand addition 00035 */ 00036 void bigint_add3(word z[], 00037 const word x[], size_t x_size, 00038 const word y[], size_t y_size); 00039 00040 /** 00041 * Two operand addition with carry out 00042 */ 00043 word bigint_add2_nc(word x[], size_t x_size, const word y[], size_t y_size); 00044 00045 /** 00046 * Three operand addition with carry out 00047 */ 00048 word bigint_add3_nc(word z[], 00049 const word x[], size_t x_size, 00050 const word y[], size_t y_size); 00051 00052 /** 00053 * Two operand subtraction 00054 */ 00055 word bigint_sub2(word x[], size_t x_size, 00056 const word y[], size_t y_size); 00057 00058 /** 00059 * Two operand subtraction, x = y - x; assumes y >= x 00060 */ 00061 void bigint_sub2_rev(word x[], const word y[], size_t y_size); 00062 00063 /** 00064 * Three operand subtraction 00065 */ 00066 word bigint_sub3(word z[], 00067 const word x[], size_t x_size, 00068 const word y[], size_t y_size); 00069 00070 /* 00071 * Shift Operations 00072 */ 00073 void bigint_shl1(word x[], size_t x_size, 00074 size_t word_shift, size_t bit_shift); 00075 00076 void bigint_shr1(word x[], size_t x_size, 00077 size_t word_shift, size_t bit_shift); 00078 00079 void bigint_shl2(word y[], const word x[], size_t x_size, 00080 size_t word_shift, size_t bit_shift); 00081 00082 void bigint_shr2(word y[], const word x[], size_t x_size, 00083 size_t word_shift, size_t bit_shift); 00084 00085 /* 00086 * Simple O(N^2) Multiplication and Squaring 00087 */ 00088 void bigint_simple_mul(word z[], 00089 const word x[], size_t x_size, 00090 const word y[], size_t y_size); 00091 00092 void bigint_simple_sqr(word z[], const word x[], size_t x_size); 00093 00094 /* 00095 * Linear Multiply 00096 */ 00097 void bigint_linmul2(word x[], size_t x_size, word y); 00098 void bigint_linmul3(word z[], const word x[], size_t x_size, word y); 00099 00100 /** 00101 * Montgomery Reduction 00102 * @param z integer to reduce, of size exactly 2*(p_size+1). 00103 Output is in the first p_size+1 words, higher 00104 words are set to zero. 00105 * @param p modulus 00106 * @param p_size size of p 00107 * @param p_dash Montgomery value 00108 * @param workspace array of at least 2*(p_size+1) words 00109 */ 00110 void bigint_monty_redc(word z[], 00111 const word p[], size_t p_size, 00112 word p_dash, 00113 word workspace[]); 00114 00115 /* 00116 * Montgomery Multiplication 00117 */ 00118 void bigint_monty_mul(word z[], size_t z_size, 00119 const word x[], size_t x_size, size_t x_sw, 00120 const word y[], size_t y_size, size_t y_sw, 00121 const word p[], size_t p_size, word p_dash, 00122 word workspace[]); 00123 00124 /* 00125 * Montgomery Squaring 00126 */ 00127 void bigint_monty_sqr(word z[], size_t z_size, 00128 const word x[], size_t x_size, size_t x_sw, 00129 const word p[], size_t p_size, word p_dash, 00130 word workspace[]); 00131 00132 /** 00133 * Compare x and y 00134 */ 00135 s32bit bigint_cmp(const word x[], size_t x_size, 00136 const word y[], size_t y_size); 00137 00138 /** 00139 * Compute ((n1<<bits) + n0) / d 00140 */ 00141 word bigint_divop(word n1, word n0, word d); 00142 00143 /** 00144 * Compute ((n1<<bits) + n0) % d 00145 */ 00146 word bigint_modop(word n1, word n0, word d); 00147 00148 /* 00149 * Comba Multiplication / Squaring 00150 */ 00151 void bigint_comba_mul4(word z[8], const word x[4], const word y[4]); 00152 void bigint_comba_mul6(word z[12], const word x[6], const word y[6]); 00153 void bigint_comba_mul8(word z[16], const word x[8], const word y[8]); 00154 void bigint_comba_mul9(word z[18], const word x[9], const word y[9]); 00155 void bigint_comba_mul16(word z[32], const word x[16], const word y[16]); 00156 00157 void bigint_comba_sqr4(word out[8], const word in[4]); 00158 void bigint_comba_sqr6(word out[12], const word in[6]); 00159 void bigint_comba_sqr8(word out[16], const word in[8]); 00160 void bigint_comba_sqr9(word out[18], const word in[9]); 00161 void bigint_comba_sqr16(word out[32], const word in[16]); 00162 00163 } 00164 00165 /* 00166 * High Level Multiplication/Squaring Interfaces 00167 */ 00168 void bigint_mul(word z[], size_t z_size, word workspace[], 00169 const word x[], size_t x_size, size_t x_sw, 00170 const word y[], size_t y_size, size_t y_sw); 00171 00172 void bigint_sqr(word z[], size_t z_size, word workspace[], 00173 const word x[], size_t x_size, size_t x_sw); 00174 00175 } 00176 00177 #endif