Botan
1.11.15
|
00001 /* 00002 * Montgomery Reduction 00003 * (C) 1999-2011 Jack Lloyd 00004 * 2006 Luca Piccarreta 00005 * 00006 * Botan is released under the Simplified BSD License (see license.txt) 00007 */ 00008 00009 #include <botan/internal/mp_core.h> 00010 #include <botan/internal/mp_madd.h> 00011 #include <botan/internal/mp_asmi.h> 00012 #include <botan/mem_ops.h> 00013 00014 namespace Botan { 00015 00016 extern "C" { 00017 00018 /* 00019 * Montgomery Reduction Algorithm 00020 */ 00021 void bigint_monty_redc(word z[], 00022 const word p[], size_t p_size, 00023 word p_dash, word ws[]) 00024 { 00025 const size_t z_size = 2*(p_size+1); 00026 00027 const size_t blocks_of_8 = p_size - (p_size % 8); 00028 00029 for(size_t i = 0; i != p_size; ++i) 00030 { 00031 word* z_i = z + i; 00032 00033 const word y = z_i[0] * p_dash; 00034 00035 /* 00036 bigint_linmul3(ws, p, p_size, y); 00037 bigint_add2(z_i, z_size - i, ws, p_size+1); 00038 */ 00039 00040 word carry = 0; 00041 00042 for(size_t j = 0; j != blocks_of_8; j += 8) 00043 carry = word8_madd3(z_i + j, p + j, y, carry); 00044 00045 for(size_t j = blocks_of_8; j != p_size; ++j) 00046 z_i[j] = word_madd3(p[j], y, z_i[j], &carry); 00047 00048 word z_sum = z_i[p_size] + carry; 00049 carry = (z_sum < z_i[p_size]); 00050 z_i[p_size] = z_sum; 00051 00052 for(size_t j = p_size + 1; carry && j != z_size - i; ++j) 00053 { 00054 ++z_i[j]; 00055 carry = !z_i[j]; 00056 } 00057 } 00058 00059 /* 00060 * The result might need to be reduced mod p. To avoid a timing 00061 * channel, always perform the subtraction. If in the compution 00062 * of x - p a borrow is required then x was already < p. 00063 * 00064 * x - p starts at ws[0] and is p_size+1 bytes long 00065 * x starts at ws[p_size+1] and is also p_size+1 bytes log 00066 * (that's the copy_mem) 00067 * 00068 * Select which address to copy from indexing off of the final 00069 * borrow. 00070 */ 00071 00072 word borrow = 0; 00073 for(size_t i = 0; i != p_size; ++i) 00074 ws[i] = word_sub(z[p_size + i], p[i], &borrow); 00075 00076 ws[p_size] = word_sub(z[p_size+p_size], 0, &borrow); 00077 00078 BOTAN_ASSERT(borrow == 0 || borrow == 1, "Expected borrow"); 00079 00080 copy_mem(ws + p_size + 1, z + p_size, p_size + 1); 00081 00082 copy_mem(z, ws + borrow*(p_size+1), p_size + 1); 00083 clear_mem(z + p_size + 1, z_size - p_size - 1); 00084 } 00085 00086 void bigint_monty_mul(word z[], size_t z_size, 00087 const word x[], size_t x_size, size_t x_sw, 00088 const word y[], size_t y_size, size_t y_sw, 00089 const word p[], size_t p_size, word p_dash, 00090 word ws[]) 00091 { 00092 bigint_mul(&z[0], z_size, &ws[0], 00093 &x[0], x_size, x_sw, 00094 &y[0], y_size, y_sw); 00095 00096 bigint_monty_redc(&z[0], 00097 &p[0], p_size, p_dash, 00098 &ws[0]); 00099 } 00100 00101 void bigint_monty_sqr(word z[], size_t z_size, 00102 const word x[], size_t x_size, size_t x_sw, 00103 const word p[], size_t p_size, word p_dash, 00104 word ws[]) 00105 { 00106 bigint_sqr(&z[0], z_size, &ws[0], 00107 &x[0], x_size, x_sw); 00108 00109 bigint_monty_redc(&z[0], 00110 &p[0], p_size, p_dash, 00111 &ws[0]); 00112 } 00113 00114 } 00115 00116 }