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(BigInt)* e)
34     {
35         m_exp = e.dup;
36     }
37 
38     /*
39     * Set the base
40     */
41     override void setBase(const(BigInt)* base)
42     {
43         m_window_bits = PowerMod.windowBits(m_exp.bits(), base.bits(), m_hints);
44         m_g.resize(1 << m_window_bits);
45         auto base_2 = base.dup;
46         m_g[0] = RefCounted!BigInt(1);
47         m_g[1] = RefCounted!BigInt(&base_2);
48         for (size_t i = 2; i != m_g.length; ++i) {
49             auto mg_0 = m_reducer.multiply(&*m_g[i-1], &*m_g[1]);
50             m_g[i] = RefCounted!BigInt(&mg_0);
51         }
52     }
53 
54     /*
55     * Compute the result
56     */
57     override BigInt execute() const
58     {
59         const size_t exp_nibbles = (m_exp.bits() + m_window_bits - 1) / m_window_bits;
60         
61         BigInt x = BigInt(1);
62         
63         for (size_t i = exp_nibbles; i > 0; --i)
64         {
65             foreach (size_t j; 0 .. m_window_bits)
66                 x = m_reducer.square(&x);
67             
68             const uint nibble = m_exp.getSubstring(m_window_bits*(i-1), m_window_bits);
69           
70             x = m_reducer.multiply(&x, &* m_g[nibble]);
71         }
72         return x.move();
73     }
74 
75     override ModularExponentiator copy() const
76     { 
77         FixedWindowExponentiator ret = new FixedWindowExponentiator;
78         ret.m_reducer = m_reducer.dup;
79         ret.m_exp = m_exp.dup;
80         ret.m_window_bits = m_window_bits;
81         ret.m_g = m_g.dup;
82         ret.m_hints = m_hints;
83         return ret;
84     }
85 
86     this(const(BigInt)* n, PowerMod.UsageHints _hints)
87     {
88         m_reducer = ModularReducer(*n);
89         m_hints = _hints;
90         m_window_bits = 0;
91     }
92 private:
93     this() { }
94     ModularReducer m_reducer;
95     BigInt m_exp;
96     size_t m_window_bits;
97     Vector!(RefCounted!BigInt) m_g;
98     PowerMod.UsageHints m_hints;
99 }
100 
101 /**
102 * Montgomery Exponentiator
103 */
104 class MontgomeryExponentiator : ModularExponentiator
105 {
106 public:
107     /*
108     * Set the exponent
109     */
110     override void setExponent(const(BigInt)* exp)
111     {
112         m_exp = exp.dup;
113         m_exp_bits = exp.bits();
114     }
115 
116     /*
117     * Set the base
118     */
119     override void setBase(const(BigInt)* base)
120     {
121         m_window_bits = PowerMod.windowBits(m_exp.bits(), base.bits(), m_hints);
122         m_g.resize((1 << m_window_bits));
123         
124         BigInt z = BigInt(BigInt.Positive, 2 * (m_mod_words + 1));
125         SecureVector!word workspace = SecureVector!word(z.length);
126         
127         m_g[0] = RefCounted!BigInt(1);
128         
129         bigint_monty_mul(z.mutablePtr(), z.length, m_g[0].ptr, m_g[0].length, m_g[0].sigWords(), m_R2_mod.ptr, 
130                          m_R2_mod.length, m_R2_mod.sigWords(), m_modulus.ptr, m_mod_words, m_mod_prime, workspace.ptr);
131         
132         auto z_0 = z.dup;
133         m_g[0] = RefCounted!BigInt(&z_0);
134         
135         auto base_0 = (*base).dup;
136         if (base_0 >= &m_modulus) {
137             auto base_modulo = base_0 % &m_modulus;
138             m_g[1] = RefCounted!BigInt(&base_modulo);
139         }
140         else m_g[1] = RefCounted!BigInt(&base_0);
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         auto z_1 = z.dup;
146         m_g[1] = RefCounted!BigInt(&z_1);
147         
148         const BigInt* x = &*(m_g[1]);
149         const size_t x_sig = x.sigWords();
150         
151         for (size_t i = 2; i != m_g.length; ++i)
152         {
153             const BigInt* y = &*(m_g[i-1]);
154             const size_t y_sig = y.sigWords();
155             
156             bigint_monty_mul(z.mutablePtr(), z.length,
157                              x.ptr, x.length, x_sig,
158                              y.ptr, y.length, y_sig,
159                              m_modulus.ptr, m_mod_words, m_mod_prime,
160                              workspace.ptr);
161             auto z_dup = z.dup;
162             m_g[i] = RefCounted!BigInt(&z_dup);
163         }
164     }
165 
166     /*
167     * Compute the result
168     */
169     override BigInt execute() const
170     {
171         const size_t exp_nibbles = (m_exp_bits + m_window_bits - 1) / m_window_bits;
172         
173         BigInt x = m_R_mod.dup;
174         
175         const size_t z_size = 2*(m_mod_words + 1);
176         
177         BigInt z = BigInt(BigInt.Positive, z_size);
178         SecureVector!word workspace = SecureVector!word(z_size);
179         
180         for (size_t i = exp_nibbles; i > 0; --i)
181         {
182             for (size_t k = 0; k != m_window_bits; ++k)
183             {
184                 bigint_monty_sqr(z.mutablePtr(), z_size, x.ptr, x.length, x.sigWords(),
185                                  m_modulus.ptr, m_mod_words, m_mod_prime, workspace.ptr);
186                 
187                 x.growTo(z.length);
188                 x.mutablePtr[0..x.length] = z.mutablePtr[0..z.length];
189             }
190             
191             const uint nibble = m_exp.getSubstring(m_window_bits*(i-1), m_window_bits);
192             
193             const BigInt* y = &*m_g[nibble];
194 
195 
196             bigint_monty_mul(z.mutablePtr(), z_size, x.ptr, x.length, x.sigWords(), y.ptr, y.length, y.sigWords(),
197                              m_modulus.ptr, m_mod_words, m_mod_prime, workspace.ptr);
198             x.growTo(z.length);
199             x.mutablePtr[0..x.length] = z.mutablePtr[0..z.length];
200         }
201         
202         x.growTo(2*m_mod_words + 1);
203         
204         bigint_monty_redc(x.mutablePtr(), m_modulus.ptr, m_mod_words, m_mod_prime, workspace.ptr);
205         return x.move();
206     }
207 
208     override ModularExponentiator copy() const
209     { 
210         MontgomeryExponentiator ret = new MontgomeryExponentiator;
211         ret.m_exp = m_exp.dup;
212         ret.m_modulus = m_modulus.dup;
213         ret.m_R_mod = m_R_mod.dup;
214         ret.m_R2_mod = m_R2_mod.dup;
215         ret.m_mod_prime = m_mod_prime;
216         ret.m_mod_words = m_mod_words;
217         ret.m_exp_bits = m_exp_bits;
218         ret.m_window_bits = m_window_bits;
219         ret.m_hints = m_hints;
220         ret.m_g = m_g.dup;
221         return ret;
222     }
223 
224     /*
225     * Montgomery_Exponentiator Constructor
226     */
227     this(const(BigInt)* mod, PowerMod.UsageHints hints)
228     {
229         m_modulus = mod.dup;
230         m_mod_words = m_modulus.sigWords();
231         m_window_bits = 1;
232         m_hints = hints;
233         // Montgomery reduction only works for positive odd moduli
234         if (!m_modulus.isPositive() || m_modulus.isEven())
235             throw new InvalidArgument("Montgomery_Exponentiator: invalid modulus");
236         
237         m_mod_prime = montyInverse(mod.wordAt(0));
238         
239         BigInt r = BigInt.powerOf2(m_mod_words * BOTAN_MP_WORD_BITS);
240         m_R_mod = r % m_modulus;
241 		auto r_mod_temp = (m_R_mod * m_R_mod);
242         m_R2_mod = r_mod_temp % m_modulus;
243     }
244 
245 private:
246     this() { }
247     BigInt m_exp, m_modulus, m_R_mod, m_R2_mod;
248     word m_mod_prime;
249     size_t m_mod_words, m_exp_bits, m_window_bits;
250     PowerMod.UsageHints m_hints;
251     Vector!(RefCounted!BigInt) m_g;
252 }
253