Coverage Report

Created: 2021-05-04 09:02

/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/ct_utils.h>
12
#include <botan/mem_ops.h>
13
#include <botan/exceptn.h>
14
15
namespace Botan {
16
17
/*
18
* Montgomery reduction - product scanning form
19
*
20
* https://www.iacr.org/archive/ches2005/006.pdf
21
* https://eprint.iacr.org/2013/882.pdf
22
* https://www.microsoft.com/en-us/research/wp-content/uploads/1996/01/j37acmon.pdf
23
*/
24
void bigint_monty_redc_generic(word z[], size_t z_size,
25
                               const word p[], size_t p_size, word p_dash,
26
                               word ws[])
27
7.54M
   {
28
7.54M
   word w2 = 0, w1 = 0, w0 = 0;
29
30
7.54M
   w0 = z[0];
31
32
7.54M
   ws[0] = w0 * p_dash;
33
34
7.54M
   word3_muladd(&w2, &w1, &w0, ws[0], p[0]);
35
36
7.54M
   w0 = w1;
37
7.54M
   w1 = w2;
38
7.54M
   w2 = 0;
39
40
42.2M
   for(size_t i = 1; i != p_size; ++i)
41
34.7M
      {
42
216M
      for(size_t j = 0; j < i; ++j)
43
181M
         {
44
181M
         word3_muladd(&w2, &w1, &w0, ws[j], p[i-j]);
45
181M
         }
46
47
34.7M
      word3_add(&w2, &w1, &w0, z[i]);
48
49
34.7M
      ws[i] = w0 * p_dash;
50
51
34.7M
      word3_muladd(&w2, &w1, &w0, ws[i], p[0]);
52
53
34.7M
      w0 = w1;
54
34.7M
      w1 = w2;
55
34.7M
      w2 = 0;
56
34.7M
      }
57
58
49.8M
   for(size_t i = 0; i != p_size; ++i)
59
42.2M
      {
60
223M
      for(size_t j = i + 1; j != p_size; ++j)
61
181M
         {
62
181M
         word3_muladd(&w2, &w1, &w0, ws[j], p[p_size + i-j]);
63
181M
         }
64
65
42.2M
      word3_add(&w2, &w1, &w0, z[p_size+i]);
66
67
42.2M
      ws[i] = w0;
68
42.2M
      w0 = w1;
69
42.2M
      w1 = w2;
70
42.2M
      w2 = 0;
71
42.2M
      }
72
73
7.54M
   word3_add(&w2, &w1, &w0, z[z_size-1]);
74
75
7.54M
   ws[p_size] = w0;
76
7.54M
   ws[p_size+1] = w1;
77
78
   /*
79
   * The result might need to be reduced mod p. To avoid a timing
80
   * channel, always perform the subtraction. If in the compution
81
   * of x - p a borrow is required then x was already < p.
82
   *
83
   * x starts at ws[0] and is p_size+1 bytes long.
84
   * x - p starts at ws[p_size+1] and is also p_size+1 bytes log
85
   *
86
   * Select which address to copy from indexing off of the final
87
   * borrow.
88
   */
89
90
7.54M
   word borrow = bigint_sub3(ws + p_size + 1, ws, p_size + 1, p, p_size);
91
92
7.54M
   BOTAN_DEBUG_ASSERT(borrow == 0 || borrow == 1);
93
94
7.54M
   CT::conditional_copy_mem(borrow, z, ws, ws + (p_size + 1), (p_size + 1));
95
7.54M
   clear_mem(z + p_size, z_size - p_size - 2);
96
7.54M
   }
97
98
}