/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 | 13.6M | { |
28 | 13.6M | word w2 = 0, w1 = 0, w0 = 0; |
29 | | |
30 | 13.6M | w0 = z[0]; |
31 | | |
32 | 13.6M | ws[0] = w0 * p_dash; |
33 | | |
34 | 13.6M | word3_muladd(&w2, &w1, &w0, ws[0], p[0]); |
35 | | |
36 | 13.6M | w0 = w1; |
37 | 13.6M | w1 = w2; |
38 | 13.6M | w2 = 0; |
39 | | |
40 | 69.9M | for(size_t i = 1; i != p_size; ++i) |
41 | 56.3M | { |
42 | 325M | for(size_t j = 0; j < i; ++j) |
43 | 269M | { |
44 | 269M | word3_muladd(&w2, &w1, &w0, ws[j], p[i-j]); |
45 | 269M | } |
46 | | |
47 | 56.3M | word3_add(&w2, &w1, &w0, z[i]); |
48 | | |
49 | 56.3M | ws[i] = w0 * p_dash; |
50 | | |
51 | 56.3M | word3_muladd(&w2, &w1, &w0, ws[i], p[0]); |
52 | | |
53 | 56.3M | w0 = w1; |
54 | 56.3M | w1 = w2; |
55 | 56.3M | w2 = 0; |
56 | 56.3M | } |
57 | | |
58 | 83.6M | for(size_t i = 0; i != p_size; ++i) |
59 | 69.9M | { |
60 | 339M | for(size_t j = i + 1; j != p_size; ++j) |
61 | 269M | { |
62 | 269M | word3_muladd(&w2, &w1, &w0, ws[j], p[p_size + i-j]); |
63 | 269M | } |
64 | | |
65 | 69.9M | word3_add(&w2, &w1, &w0, z[p_size+i]); |
66 | | |
67 | 69.9M | ws[i] = w0; |
68 | 69.9M | w0 = w1; |
69 | 69.9M | w1 = w2; |
70 | 69.9M | w2 = 0; |
71 | 69.9M | } |
72 | | |
73 | 13.6M | word3_add(&w2, &w1, &w0, z[z_size-1]); |
74 | | |
75 | 13.6M | ws[p_size] = w0; |
76 | 13.6M | 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 | 13.6M | word borrow = bigint_sub3(ws + p_size + 1, ws, p_size + 1, p, p_size); |
91 | | |
92 | 13.6M | BOTAN_DEBUG_ASSERT(borrow == 0 || borrow == 1); |
93 | | |
94 | 13.6M | CT::conditional_copy_mem(borrow, z, ws, ws + (p_size + 1), (p_size + 1)); |
95 | 13.6M | clear_mem(z + p_size, z_size - p_size - 2); |
96 | 13.6M | } |
97 | | |
98 | | } |