1 /*
2 * Montgomery Reduction
3 * (C) 1999-2011 Jack Lloyd
4 * 2006 Luca Piccarreta
5 *
6 * Distributed under the terms of the Botan license
7 */
8
9 #include <botan/internal/mp_core.h>
10 #include <botan/internal/mp_asm.h>
11 #include <botan/internal/mp_asmi.h>
12 #include <botan/mem_ops.h>
13
14 namespace Botan {
15
16 extern "C" {
17
18 /*
19 * Montgomery Reduction Algorithm
20 */
bigint_monty_redc(word z[],size_t z_size,const word p[],size_t p_size,word p_dash,word ws[])21 void bigint_monty_redc(word z[], size_t z_size,
22 const word p[], size_t p_size,
23 word p_dash, word ws[])
24 {
25 const size_t blocks_of_8 = p_size - (p_size % 8);
26
27 for(size_t i = 0; i != p_size; ++i)
28 {
29 word* z_i = z + i;
30
31 const word y = z_i[0] * p_dash;
32
33 /*
34 bigint_linmul3(ws, p, p_size, y);
35 bigint_add2(z_i, z_size - i, ws, p_size+1);
36 */
37
38 word carry = 0;
39
40 for(size_t j = 0; j != blocks_of_8; j += 8)
41 carry = word8_madd3(z_i + j, p + j, y, carry);
42
43 for(size_t j = blocks_of_8; j != p_size; ++j)
44 z_i[j] = word_madd3(p[j], y, z_i[j], &carry);
45
46 word z_sum = z_i[p_size] + carry;
47 carry = (z_sum < z_i[p_size]);
48 z_i[p_size] = z_sum;
49
50 for(size_t j = p_size + 1; carry && j != z_size - i; ++j)
51 {
52 ++z_i[j];
53 carry = !z_i[j];
54 }
55 }
56
57 word borrow = 0;
58 for(size_t i = 0; i != p_size; ++i)
59 ws[i] = word_sub(z[p_size + i], p[i], &borrow);
60
61 ws[p_size] = word_sub(z[p_size+p_size], 0, &borrow);
62
63 copy_mem(ws + p_size + 1, z + p_size, p_size + 1);
64
65 copy_mem(z, ws + borrow*(p_size+1), p_size + 1);
66 clear_mem(z + p_size + 1, z_size - p_size - 1);
67 }
68
bigint_monty_mul(word z[],size_t z_size,const word x[],size_t x_size,size_t x_sw,const word y[],size_t y_size,size_t y_sw,const word p[],size_t p_size,word p_dash,word ws[])69 void bigint_monty_mul(word z[], size_t z_size,
70 const word x[], size_t x_size, size_t x_sw,
71 const word y[], size_t y_size, size_t y_sw,
72 const word p[], size_t p_size, word p_dash,
73 word ws[])
74 {
75 bigint_mul(&z[0], z_size, &ws[0],
76 &x[0], x_size, x_sw,
77 &y[0], y_size, y_sw);
78
79 bigint_monty_redc(&z[0], z_size,
80 &p[0], p_size, p_dash,
81 &ws[0]);
82 }
83
bigint_monty_sqr(word z[],size_t z_size,const word x[],size_t x_size,size_t x_sw,const word p[],size_t p_size,word p_dash,word ws[])84 void bigint_monty_sqr(word z[], size_t z_size,
85 const word x[], size_t x_size, size_t x_sw,
86 const word p[], size_t p_size, word p_dash,
87 word ws[])
88 {
89 bigint_sqr(&z[0], z_size, &ws[0],
90 &x[0], x_size, x_sw);
91
92 bigint_monty_redc(&z[0], z_size,
93 &p[0], p_size, p_dash,
94 &ws[0]);
95 }
96
97 }
98
99 }
100