1 /* 2 * MPI Algorithms 3 * (C) 1999-2010 Jack Lloyd 4 * 5 * Distributed under the terms of the Botan license 6 */ 7 8 #ifndef BOTAN_MP_CORE_H__ 9 #define BOTAN_MP_CORE_H__ 10 11 #include <botan/mp_types.h> 12 13 namespace Botan { 14 15 /* 16 * The size of the word type, in bits 17 */ 18 const size_t MP_WORD_BITS = BOTAN_MP_WORD_BITS; 19 20 extern "C" { 21 22 /* 23 * If cond == 0, does nothing. 24 * If cond > 0, swaps x[0:size] with y[0:size] 25 * Runs in constant time 26 */ 27 void bigint_cnd_swap(word cnd, word x[], word y[], size_t size); 28 29 /* 30 * If cond > 0 adds x[0:size] to y[0:size] and returns carry 31 * Runs in constant time 32 */ 33 word bigint_cnd_add(word cnd, word x[], const word y[], size_t size); 34 35 /* 36 * If cond > 0 subs x[0:size] to y[0:size] and returns borrow 37 * Runs in constant time 38 */ 39 word bigint_cnd_sub(word cnd, word x[], const word y[], size_t size); 40 41 /* 42 * 2s complement absolute value 43 * If cond > 0 sets x to ~x + 1 44 * Runs in constant time 45 */ 46 void bigint_cnd_abs(word cnd, word x[], size_t size); 47 48 /* 49 * Addition/Subtraction Operations 50 */ 51 void bigint_add2(word x[], size_t x_size, 52 const word y[], size_t y_size); 53 54 void bigint_add3(word z[], 55 const word x[], size_t x_size, 56 const word y[], size_t y_size); 57 58 word bigint_add2_nc(word x[], size_t x_size, const word y[], size_t y_size); 59 60 word bigint_add3_nc(word z[], 61 const word x[], size_t x_size, 62 const word y[], size_t y_size); 63 64 word bigint_sub2(word x[], size_t x_size, 65 const word y[], size_t y_size); 66 67 /** 68 * x = y - x; assumes y >= x 69 */ 70 void bigint_sub2_rev(word x[], const word y[], size_t y_size); 71 72 word bigint_sub3(word z[], 73 const word x[], size_t x_size, 74 const word y[], size_t y_size); 75 76 /* 77 * Shift Operations 78 */ 79 void bigint_shl1(word x[], size_t x_size, 80 size_t word_shift, size_t bit_shift); 81 82 void bigint_shr1(word x[], size_t x_size, 83 size_t word_shift, size_t bit_shift); 84 85 void bigint_shl2(word y[], const word x[], size_t x_size, 86 size_t word_shift, size_t bit_shift); 87 88 void bigint_shr2(word y[], const word x[], size_t x_size, 89 size_t word_shift, size_t bit_shift); 90 91 /* 92 * Simple O(N^2) Multiplication and Squaring 93 */ 94 void bigint_simple_mul(word z[], 95 const word x[], size_t x_size, 96 const word y[], size_t y_size); 97 98 void bigint_simple_sqr(word z[], const word x[], size_t x_size); 99 100 /* 101 * Linear Multiply 102 */ 103 void bigint_linmul2(word x[], size_t x_size, word y); 104 void bigint_linmul3(word z[], const word x[], size_t x_size, word y); 105 106 /** 107 * Montgomery Reduction 108 * @param z integer to reduce (also output in first p_size+1 words) 109 * @param z_size size of z (should be >= 2*p_size+1) 110 * @param p modulus 111 * @param p_size size of p 112 * @param p_dash Montgomery value 113 * @param workspace array of at least 2*(p_size+1) words 114 */ 115 void bigint_monty_redc(word z[], size_t z_size, 116 const word p[], size_t p_size, word p_dash, 117 word workspace[]); 118 119 /* 120 * Montgomery Multiplication 121 */ 122 void bigint_monty_mul(word z[], size_t z_size, 123 const word x[], size_t x_size, size_t x_sw, 124 const word y[], size_t y_size, size_t y_sw, 125 const word p[], size_t p_size, word p_dash, 126 word workspace[]); 127 128 /* 129 * Montgomery Squaring 130 */ 131 void bigint_monty_sqr(word z[], size_t z_size, 132 const word x[], size_t x_size, size_t x_sw, 133 const word p[], size_t p_size, word p_dash, 134 word workspace[]); 135 136 /* 137 * Division operation 138 */ 139 size_t bigint_divcore(word q, word y2, word y1, 140 word x3, word x2, word x1); 141 142 /** 143 * Compare x and y 144 */ 145 s32bit bigint_cmp(const word x[], size_t x_size, 146 const word y[], size_t y_size); 147 148 /** 149 * Compute ((n1<<bits) + n0) / d 150 */ 151 word bigint_divop(word n1, word n0, word d); 152 153 /** 154 * Compute ((n1<<bits) + n0) % d 155 */ 156 word bigint_modop(word n1, word n0, word d); 157 158 /* 159 * Comba Multiplication / Squaring 160 */ 161 void bigint_comba_mul4(word z[8], const word x[4], const word y[4]); 162 void bigint_comba_mul6(word z[12], const word x[6], const word y[6]); 163 void bigint_comba_mul8(word z[16], const word x[8], const word y[8]); 164 void bigint_comba_mul16(word z[32], const word x[16], const word y[16]); 165 166 void bigint_comba_sqr4(word out[8], const word in[4]); 167 void bigint_comba_sqr6(word out[12], const word in[6]); 168 void bigint_comba_sqr8(word out[16], const word in[8]); 169 void bigint_comba_sqr16(word out[32], const word in[16]); 170 171 } 172 173 /* 174 * High Level Multiplication/Squaring Interfaces 175 */ 176 void bigint_mul(word z[], size_t z_size, word workspace[], 177 const word x[], size_t x_size, size_t x_sw, 178 const word y[], size_t y_size, size_t y_sw); 179 180 void bigint_sqr(word z[], size_t z_size, word workspace[], 181 const word x[], size_t x_size, size_t x_sw); 182 183 } 184 185 #endif 186