/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 | 11.1M | { |
33 | 11.1M | word w2 = 0, w1 = 0, w0 = 0; |
34 | 11.1M | |
35 | 11.1M | w0 = z[0]; |
36 | 11.1M | |
37 | 11.1M | ws[0] = w0 * p_dash; |
38 | 11.1M | |
39 | 11.1M | word3_muladd(&w2, &w1, &w0, ws[0], p[0]); |
40 | 11.1M | |
41 | 11.1M | w0 = w1; |
42 | 11.1M | w1 = w2; |
43 | 11.1M | w2 = 0; |
44 | 11.1M | |
45 | 135M | for(size_t i = 1; i != p_size; ++i) |
46 | 124M | { |
47 | 2.89G | for(size_t j = 0; j < i; ++j) |
48 | 2.77G | { |
49 | 2.77G | word3_muladd(&w2, &w1, &w0, ws[j], p[i-j]); |
50 | 2.77G | } |
51 | 124M | |
52 | 124M | word3_add(&w2, &w1, &w0, z[i]); |
53 | 124M | |
54 | 124M | ws[i] = w0 * p_dash; |
55 | 124M | |
56 | 124M | word3_muladd(&w2, &w1, &w0, ws[i], p[0]); |
57 | 124M | |
58 | 124M | w0 = w1; |
59 | 124M | w1 = w2; |
60 | 124M | w2 = 0; |
61 | 124M | } |
62 | 11.1M | |
63 | 146M | for(size_t i = 0; i != p_size; ++i) |
64 | 135M | { |
65 | 2.91G | for(size_t j = i + 1; j != p_size; ++j) |
66 | 2.77G | { |
67 | 2.77G | word3_muladd(&w2, &w1, &w0, ws[j], p[p_size + i-j]); |
68 | 2.77G | } |
69 | 135M | |
70 | 135M | word3_add(&w2, &w1, &w0, z[p_size+i]); |
71 | 135M | |
72 | 135M | ws[i] = w0; |
73 | 135M | w0 = w1; |
74 | 135M | w1 = w2; |
75 | 135M | w2 = 0; |
76 | 135M | } |
77 | 11.1M | |
78 | 11.1M | word3_add(&w2, &w1, &w0, z[z_size-1]); |
79 | 11.1M | |
80 | 11.1M | ws[p_size] = w0; |
81 | 11.1M | ws[p_size+1] = w1; |
82 | 11.1M | |
83 | 11.1M | /* |
84 | 11.1M | * The result might need to be reduced mod p. To avoid a timing |
85 | 11.1M | * channel, always perform the subtraction. If in the compution |
86 | 11.1M | * of x - p a borrow is required then x was already < p. |
87 | 11.1M | * |
88 | 11.1M | * x starts at ws[0] and is p_size+1 bytes long. |
89 | 11.1M | * x - p starts at ws[p_size+1] and is also p_size+1 bytes log |
90 | 11.1M | * |
91 | 11.1M | * Select which address to copy from indexing off of the final |
92 | 11.1M | * borrow. |
93 | 11.1M | */ |
94 | 11.1M | |
95 | 11.1M | // word borrow = bigint_sub3(ws + p_size + 1, ws, p_size + 1, p, p_size); |
96 | 11.1M | word borrow = 0; |
97 | 146M | for(size_t i = 0; i != p_size; ++i) |
98 | 135M | ws[p_size + 1 + i] = word_sub(ws[i], p[i], &borrow); |
99 | 11.1M | ws[2*p_size+1] = word_sub(ws[p_size], 0, &borrow); |
100 | 11.1M | |
101 | 11.1M | BOTAN_DEBUG_ASSERT(borrow == 0 || borrow == 1); |
102 | 11.1M | |
103 | 11.1M | CT::conditional_copy_mem(borrow, z, ws, ws + (p_size + 1), (p_size + 1)); |
104 | 11.1M | clear_mem(z + p_size, z_size - p_size - 2); |
105 | 11.1M | } |
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 | 60.7M | { |
113 | 60.7M | const size_t z_size = 2*(p_size+1); |
114 | 60.7M | |
115 | 60.7M | BOTAN_ARG_CHECK(ws_size >= z_size, "workspace too small"); |
116 | 60.7M | |
117 | 60.7M | if(p_size == 4) |
118 | 24.7M | bigint_monty_redc_4(z, p, p_dash, ws); |
119 | 35.9M | else if(p_size == 6) |
120 | 7.93M | bigint_monty_redc_6(z, p, p_dash, ws); |
121 | 28.0M | else if(p_size == 8) |
122 | 12.9M | bigint_monty_redc_8(z, p, p_dash, ws); |
123 | 15.0M | else if(p_size == 16) |
124 | 212k | bigint_monty_redc_16(z, p, p_dash, ws); |
125 | 14.8M | else if(p_size == 24) |
126 | 113k | bigint_monty_redc_24(z, p, p_dash, ws); |
127 | 14.7M | else if(p_size == 32) |
128 | 3.52M | bigint_monty_redc_32(z, p, p_dash, ws); |
129 | 11.1M | else |
130 | 11.1M | bigint_monty_redc_generic(z, z_size, p, p_size, p_dash, ws); |
131 | 60.7M | } |
132 | | |
133 | | } |