botan.math.numbertheory.def

1 /**
2 * Modular Exponentiation
3 * 
4 * Copyright:
5 * (C) 1999-2007 Jack Lloyd
6 * (C) 2014-2015 Etienne Cimon
7 *
8 * License:
9 * Botan is released under the Simplified BSD License (see LICENSE.md)
10 */
11 module botan.math.numbertheory.def_powm;
12 
13 import botan.constants;
14 static if (BOTAN_HAS_PUBLIC_KEY_CRYPTO):
15 
16 import botan.math.mp.mp_core;
17 import botan.math.numbertheory.pow_mod;
18 import botan.math.numbertheory.reducer;
19 import botan.math.numbertheory.numthry;
20 import botan.math.bigint.bigint;
21 import botan.utils.types;
22 import botan.constants;
23 
24 /**
25 * Fixed Window Exponentiator
26 */
27 final class FixedWindowExponentiator : ModularExponentiator
28 {
29 public:
30     /*
31     * Set the exponent
32     */
33     override void setExponent(const ref BigInt e)
34     {
35         m_exp = e.dup;
36     }
37 
38     /*
39     * Set the base
40     */
41     override void setBase(const ref BigInt base)
42     {
43         m_window_bits = PowerMod.windowBits(m_exp.bits(), base.bits(), m_hints);
44         auto base_2 = base.dup;
45         m_g.resize(1 << m_window_bits);
46         m_g[0] = RefCounted!BigInt(1);
47         m_g[1] = RefCounted!BigInt(base_2);
48         
49         for (size_t i = 2; i != m_g.length; ++i)
50             m_g[i] = RefCounted!BigInt(m_reducer.multiply(*(m_g[i-1]), *(m_g[0])));
51     }
52 
53     /*
54     * Compute the result
55     */
56     override BigInt execute() const
57     {
58         const size_t exp_nibbles = (m_exp.bits() + m_window_bits - 1) / m_window_bits;
59         
60         BigInt x = BigInt(1);
61         
62         for (size_t i = exp_nibbles; i > 0; --i)
63         {
64             foreach (size_t j; 0 .. m_window_bits)
65                 x = m_reducer.square(x);
66             
67             const uint nibble = m_exp.getSubstring(m_window_bits*(i-1), m_window_bits);
68             
69             x = m_reducer.multiply(x, *(m_g[nibble]));
70         }
71         return x.move();
72     }
73 
74     override ModularExponentiator copy() const
75     { 
76         FixedWindowExponentiator ret = new FixedWindowExponentiator;
77         ret.m_reducer = m_reducer.dup;
78         ret.m_exp = m_exp.dup;
79         ret.m_window_bits = m_window_bits;
80         ret.m_g = m_g.dup;
81         ret.m_hints = m_hints;
82         return ret;
83     }
84 
85     this()(auto const ref BigInt n, PowerMod.UsageHints _hints)
86     {
87         m_reducer = ModularReducer(n);
88         m_hints = _hints;
89         m_window_bits = 0;
90     }
91 
92 	~this() {
93 		foreach (ref RefCounted!BigInt bi; m_g[]) {
94 			(*bi).destroy();
95 		}
96 	}
97 
98 private:
99     this() { }
100     ModularReducer m_reducer;
101     BigInt m_exp;
102     size_t m_window_bits;
103     Vector!(RefCounted!BigInt) m_g;
104     PowerMod.UsageHints m_hints;
105 }
106 
107 /**
108 * Montgomery Exponentiator
109 */
110 class MontgomeryExponentiator : ModularExponentiator
111 {
112 public:
113     /*
114     * Set the exponent
115     */
116     override void setExponent(const ref BigInt exp)
117     {
118         m_exp = exp.dup;
119         m_exp_bits = exp.bits();
120     }
121 
122     /*
123     * Set the base
124     */
125     override void setBase(const ref BigInt base)
126     {
127         m_window_bits = PowerMod.windowBits(m_exp.bits(), base.bits(), m_hints);
128         m_g.resize((1 << m_window_bits));
129         
130         BigInt z = BigInt(BigInt.Positive, 2 * (m_mod_words + 1));
131         SecureVector!word workspace = SecureVector!word(z.length);
132         
133         m_g[0] = RefCounted!BigInt(1);
134         
135         bigint_monty_mul(z.mutablePtr(), z.length, m_g[0].ptr, m_g[0].length, m_g[0].sigWords(), m_R2_mod.ptr, 
136                          m_R2_mod.length, m_R2_mod.sigWords(), m_modulus.ptr, m_mod_words, m_mod_prime, workspace.ptr);
137         
138         m_g[0] = RefCounted!BigInt(z.dup);
139         
140         m_g[1] = (base >= m_modulus) ? RefCounted!BigInt(base % m_modulus) : RefCounted!BigInt(base.dup);
141         
142         bigint_monty_mul(z.mutablePtr(), z.length, m_g[1].ptr, m_g[1].length, m_g[1].sigWords(), m_R2_mod.ptr, 
143                          m_R2_mod.length, m_R2_mod.sigWords(), m_modulus.ptr, m_mod_words, m_mod_prime, workspace.ptr);
144         
145         m_g[1] = RefCounted!BigInt(z.dup);
146         
147         const BigInt* x = &*(m_g[1]);
148         const size_t x_sig = x.sigWords();
149         
150         for (size_t i = 2; i != m_g.length; ++i)
151         {
152             const BigInt* y = &*(m_g[i-1]);
153             const size_t y_sig = y.sigWords();
154             
155             bigint_monty_mul(z.mutablePtr(), z.length,
156                              x.ptr, x.length, x_sig,
157                              y.ptr, y.length, y_sig,
158                              m_modulus.ptr, m_mod_words, m_mod_prime,
159                              workspace.ptr);
160             
161             m_g[i] = RefCounted!BigInt(z.dup);
162         }
163     }
164 
165     /*
166     * Compute the result
167     */
168     override BigInt execute() const
169     {
170         const size_t exp_nibbles = (m_exp_bits + m_window_bits - 1) / m_window_bits;
171         
172         BigInt x = m_R_mod.dup;
173         
174         const size_t z_size = 2*(m_mod_words + 1);
175         
176         BigInt z = BigInt(BigInt.Positive, z_size);
177         SecureVector!word workspace = SecureVector!word(z_size);
178         
179         for (size_t i = exp_nibbles; i > 0; --i)
180         {
181             for (size_t k = 0; k != m_window_bits; ++k)
182             {
183                 bigint_monty_sqr(z.mutablePtr(), z_size, x.ptr, x.length, x.sigWords(),
184                                  m_modulus.ptr, m_mod_words, m_mod_prime, workspace.ptr);
185                 
186                 x.growTo(z.length);
187                 x.mutablePtr[0..x.length] = z.mutablePtr[0..z.length];
188             }
189             
190             const uint nibble = m_exp.getSubstring(m_window_bits*(i-1), m_window_bits);
191             
192             const BigInt* y = &*m_g[nibble];
193 
194 
195             bigint_monty_mul(z.mutablePtr(), z_size, x.ptr, x.length, x.sigWords(), y.ptr, y.length, y.sigWords(),
196                              m_modulus.ptr, m_mod_words, m_mod_prime, workspace.ptr);
197             x.growTo(z.length);
198             x.mutablePtr[0..x.length] = z.mutablePtr[0..z.length];
199         }
200         
201         x.growTo(2*m_mod_words + 1);
202         
203         bigint_monty_redc(x.mutablePtr(), m_modulus.ptr, m_mod_words, m_mod_prime, workspace.ptr);
204         return x.move();
205     }
206 
207     override ModularExponentiator copy() const
208     { 
209         MontgomeryExponentiator ret = new MontgomeryExponentiator;
210         ret.m_exp = m_exp.dup;
211         ret.m_modulus = m_modulus.dup;
212         ret.m_R_mod = m_R_mod.dup;
213         ret.m_R2_mod = m_R2_mod.dup;
214         ret.m_mod_prime = m_mod_prime;
215         ret.m_mod_words = m_mod_words;
216         ret.m_exp_bits = m_exp_bits;
217         ret.m_window_bits = m_window_bits;
218         ret.m_hints = m_hints;
219         ret.m_g = m_g.dup;
220         return ret;
221     }
222 
223     /*
224     * Montgomery_Exponentiator Constructor
225     */
226     this()(auto const ref BigInt mod, PowerMod.UsageHints hints)
227     {
228         m_modulus = mod.dup;
229         m_mod_words = m_modulus.sigWords();
230         m_window_bits = 1;
231         m_hints = hints;
232         // Montgomery reduction only works for positive odd moduli
233         if (!m_modulus.isPositive() || m_modulus.isEven())
234             throw new InvalidArgument("Montgomery_Exponentiator: invalid modulus");
235         
236         m_mod_prime = montyInverse(mod.wordAt(0));
237         
238         BigInt r = BigInt.powerOf2(m_mod_words * BOTAN_MP_WORD_BITS);
239         m_R_mod = r % m_modulus;
240 		auto r_mod_temp = (m_R_mod * m_R_mod);
241         m_R2_mod = r_mod_temp % m_modulus;
242     }
243 
244 	~this() {
245 		foreach (ref RefCounted!BigInt bi; m_g[]) {
246 			(*bi).destroy();
247 		}
248 	}
249 
250 private:
251     this() { }
252     BigInt m_exp, m_modulus, m_R_mod, m_R2_mod;
253     word m_mod_prime;
254     size_t m_mod_words, m_exp_bits, m_window_bits;
255     PowerMod.UsageHints m_hints;
256     Vector!(RefCounted!BigInt) m_g;
257 }
258