/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 | | } |