Botan  1.11.15
src/lib/math/mp/mp_monty.cpp
Go to the documentation of this file.
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 }