Botan  2.7.0
Crypto and TLS for C++11
mp_monty.cpp
Go to the documentation of this file.
1 /*
2 * Montgomery Reduction
3 * (C) 1999-2011 Jack Lloyd
4 * 2006 Luca Piccarreta
5 * 2016 Matthias Gierlings
6 *
7 * Botan is released under the Simplified BSD License (see license.txt)
8 */
9 
10 #include <botan/internal/mp_core.h>
11 #include <botan/internal/mp_monty.h>
12 #include <botan/internal/mp_madd.h>
13 #include <botan/internal/mp_asmi.h>
14 #include <botan/internal/ct_utils.h>
15 #include <botan/mem_ops.h>
16 #include <botan/exceptn.h>
17 
18 namespace Botan {
19 
20 namespace {
21 
22 /*
23 * Montgomery reduction - product scanning form
24 *
25 * https://www.iacr.org/archive/ches2005/006.pdf
26 * https://eprint.iacr.org/2013/882.pdf
27 * https://www.microsoft.com/en-us/research/wp-content/uploads/1996/01/j37acmon.pdf
28 */
29 void bigint_monty_redc_generic(word z[], size_t z_size,
30  const word p[], size_t p_size, word p_dash,
31  word ws[])
32  {
33  word w2 = 0, w1 = 0, w0 = 0;
34 
35  w0 = z[0];
36 
37  ws[0] = w0 * p_dash;
38 
39  word3_muladd(&w2, &w1, &w0, ws[0], p[0]);
40 
41  w0 = w1;
42  w1 = w2;
43  w2 = 0;
44 
45  for(size_t i = 1; i != p_size; ++i)
46  {
47  for(size_t j = 0; j < i; ++j)
48  {
49  word3_muladd(&w2, &w1, &w0, ws[j], p[i-j]);
50  }
51 
52  word3_add(&w2, &w1, &w0, z[i]);
53 
54  ws[i] = w0 * p_dash;
55 
56  word3_muladd(&w2, &w1, &w0, ws[i], p[0]);
57 
58  w0 = w1;
59  w1 = w2;
60  w2 = 0;
61  }
62 
63  for(size_t i = 0; i != p_size; ++i)
64  {
65  for(size_t j = i + 1; j != p_size; ++j)
66  {
67  word3_muladd(&w2, &w1, &w0, ws[j], p[p_size + i-j]);
68  }
69 
70  word3_add(&w2, &w1, &w0, z[p_size+i]);
71 
72  ws[i] = w0;
73  w0 = w1;
74  w1 = w2;
75  w2 = 0;
76  }
77 
78  word3_add(&w2, &w1, &w0, z[z_size-1]);
79 
80  ws[p_size] = w0;
81  ws[p_size+1] = w1;
82 
83  /*
84  * The result might need to be reduced mod p. To avoid a timing
85  * channel, always perform the subtraction. If in the compution
86  * of x - p a borrow is required then x was already < p.
87  *
88  * x starts at ws[0] and is p_size+1 bytes long.
89  * x - p starts at ws[p_size+1] and is also p_size+1 bytes log
90  *
91  * Select which address to copy from indexing off of the final
92  * borrow.
93  */
94 
95  // word borrow = bigint_sub3(ws + p_size + 1, ws, p_size + 1, p, p_size);
96  word borrow = 0;
97  for(size_t i = 0; i != p_size; ++i)
98  ws[p_size + 1 + i] = word_sub(ws[i], p[i], &borrow);
99  ws[2*p_size+1] = word_sub(ws[p_size], 0, &borrow);
100 
101  CT::conditional_copy_mem(borrow, z, ws, ws + (p_size + 1), (p_size + 1));
102  clear_mem(z + p_size, z_size - p_size - 2);
103 
104  // This check comes after we've used it but that's ok here
105  CT::unpoison(&borrow, 1);
106  BOTAN_ASSERT(borrow == 0 || borrow == 1, "Expected borrow");
107  }
108 
109 }
110 
111 void bigint_monty_redc(word z[],
112  const word p[], size_t p_size, word p_dash,
113  word ws[], size_t ws_size)
114  {
115  const size_t z_size = 2*(p_size+1);
116 
117  BOTAN_ARG_CHECK(ws_size >= z_size, "workspace too small");
118 
119  if(p_size == 4)
120  bigint_monty_redc_4(z, p, p_dash, ws);
121  else if(p_size == 6)
122  bigint_monty_redc_6(z, p, p_dash, ws);
123  else if(p_size == 8)
124  bigint_monty_redc_8(z, p, p_dash, ws);
125  else if(p_size == 16)
126  bigint_monty_redc_16(z, p, p_dash, ws);
127  else if(p_size == 24)
128  bigint_monty_redc_24(z, p, p_dash, ws);
129  else if(p_size == 32)
130  bigint_monty_redc_32(z, p, p_dash, ws);
131  else
132  bigint_monty_redc_generic(z, z_size, p, p_size, p_dash, ws);
133  }
134 
135 }
void word3_muladd(word *w2, word *w1, word *w0, word x, word y)
Definition: mp_asmi.h:717
void bigint_monty_redc_32(word z[], const word p[], word p_dash, word ws[])
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:97
void bigint_monty_redc_8(word z[], const word p[], word p_dash, word ws[])
void bigint_monty_redc_6(word z[], const word p[], word p_dash, word ws[])
T conditional_copy_mem(T value, T *to, const T *from0, const T *from1, size_t elems)
Definition: ct_utils.h:154
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:43
void bigint_monty_redc_24(word z[], const word p[], word p_dash, word ws[])
void bigint_monty_redc_16(word z[], const word p[], word p_dash, word ws[])
void bigint_monty_redc_4(word z[], const word p[], word p_dash, word ws[])
void word3_add(word *w2, word *w1, word *w0, word x)
Definition: mp_asmi.h:764
Definition: alg_id.cpp:13
#define BOTAN_ARG_CHECK(expr, msg)
Definition: assert.h:37
void bigint_monty_redc(word z[], const word p[], size_t p_size, word p_dash, word workspace[], size_t ws_size)
Definition: mp_monty.cpp:111
word word_sub(word x, word y, word *carry)
Definition: mp_asmi.h:280
void unpoison(const T *p, size_t n)
Definition: ct_utils.h:57