Coverage Report

Created: 2021-04-07 06:07

/src/botan/src/lib/math/mp/mp_monty.cpp
Line
Count
Source
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
7.33M
   {
33
7.33M
   word w2 = 0, w1 = 0, w0 = 0;
34
35
7.33M
   w0 = z[0];
36
37
7.33M
   ws[0] = w0 * p_dash;
38
39
7.33M
   word3_muladd(&w2, &w1, &w0, ws[0], p[0]);
40
41
7.33M
   w0 = w1;
42
7.33M
   w1 = w2;
43
7.33M
   w2 = 0;
44
45
40.2M
   for(size_t i = 1; i != p_size; ++i)
46
32.8M
      {
47
202M
      for(size_t j = 0; j < i; ++j)
48
169M
         {
49
169M
         word3_muladd(&w2, &w1, &w0, ws[j], p[i-j]);
50
169M
         }
51
52
32.8M
      word3_add(&w2, &w1, &w0, z[i]);
53
54
32.8M
      ws[i] = w0 * p_dash;
55
56
32.8M
      word3_muladd(&w2, &w1, &w0, ws[i], p[0]);
57
58
32.8M
      w0 = w1;
59
32.8M
      w1 = w2;
60
32.8M
      w2 = 0;
61
32.8M
      }
62
63
47.5M
   for(size_t i = 0; i != p_size; ++i)
64
40.2M
      {
65
209M
      for(size_t j = i + 1; j != p_size; ++j)
66
169M
         {
67
169M
         word3_muladd(&w2, &w1, &w0, ws[j], p[p_size + i-j]);
68
169M
         }
69
70
40.2M
      word3_add(&w2, &w1, &w0, z[p_size+i]);
71
72
40.2M
      ws[i] = w0;
73
40.2M
      w0 = w1;
74
40.2M
      w1 = w2;
75
40.2M
      w2 = 0;
76
40.2M
      }
77
78
7.33M
   word3_add(&w2, &w1, &w0, z[z_size-1]);
79
80
7.33M
   ws[p_size] = w0;
81
7.33M
   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
7.33M
   word borrow = 0;
97
47.5M
   for(size_t i = 0; i != p_size; ++i)
98
40.2M
      ws[p_size + 1 + i] = word_sub(ws[i], p[i], &borrow);
99
7.33M
   ws[2*p_size+1] = word_sub(ws[p_size], 0, &borrow);
100
101
7.33M
   BOTAN_DEBUG_ASSERT(borrow == 0 || borrow == 1);
102
103
7.33M
   CT::conditional_copy_mem(borrow, z, ws, ws + (p_size + 1), (p_size + 1));
104
7.33M
   clear_mem(z + p_size, z_size - p_size - 2);
105
7.33M
   }
106
107
}
108
109
void bigint_monty_redc(word z[],
110
                       const word p[], size_t p_size, word p_dash,
111
                       word ws[], size_t ws_size)
112
89.2M
   {
113
89.2M
   const size_t z_size = 2*(p_size+1);
114
115
89.2M
   BOTAN_ARG_CHECK(ws_size >= z_size, "workspace too small");
116
117
89.2M
   if(p_size == 4)
118
32.1M
      bigint_monty_redc_4(z, p, p_dash, ws);
119
57.0M
   else if(p_size == 6)
120
4.34M
      bigint_monty_redc_6(z, p, p_dash, ws);
121
52.7M
   else if(p_size == 8)
122
45.0M
      bigint_monty_redc_8(z, p, p_dash, ws);
123
7.62M
   else if(p_size == 16)
124
80.5k
      bigint_monty_redc_16(z, p, p_dash, ws);
125
7.54M
   else if(p_size == 24)
126
38.3k
      bigint_monty_redc_24(z, p, p_dash, ws);
127
7.50M
   else if(p_size == 32)
128
167k
      bigint_monty_redc_32(z, p, p_dash, ws);
129
7.33M
   else
130
7.33M
      bigint_monty_redc_generic(z, z_size, p, p_size, p_dash, ws);
131
89.2M
   }
132
133
}