monotone

monotone Mtn Source Tree

Root/botan/powm_mnt.cpp

1/*************************************************
2* Montgomery Exponentiation Source File *
3* (C) 1999-2007 The Botan Project *
4*************************************************/
5
6#include <botan/def_powm.h>
7#include <botan/numthry.h>
8#include <botan/mp_core.h>
9
10namespace Botan {
11
12namespace {
13
14/*************************************************
15* Try to choose a good window size *
16*************************************************/
17u32bit choose_window_bits(u32bit exp_bits, u32bit,
18 Power_Mod::Usage_Hints hints)
19 {
20 static const u32bit wsize[][2] = {
21 { 2048, 4 }, { 1024, 3 }, { 256, 2 }, { 128, 1 }, { 0, 0 }
22 };
23
24 u32bit window_bits = 1;
25
26 if(exp_bits)
27 {
28 for(u32bit j = 0; wsize[j][0]; ++j)
29 {
30 if(exp_bits >= wsize[j][0])
31 {
32 window_bits += wsize[j][1];
33 break;
34 }
35 }
36 }
37
38 if(hints & Power_Mod::BASE_IS_FIXED)
39 window_bits += 2;
40 if(hints & Power_Mod::EXP_IS_LARGE)
41 ++window_bits;
42
43 return window_bits;
44 }
45
46/*************************************************
47* Montgomery Reduction *
48*************************************************/
49inline void montgomery_reduce(BigInt& out, MemoryRegion<word>& z_buf,
50 const BigInt& x_bn, u32bit x_size, word u)
51 {
52 const word* x = x_bn.data();
53 word* z = z_buf.begin();
54 u32bit z_size = z_buf.size();
55
56 bigint_monty_redc(z, z_size, x, x_size, u);
57
58 out.get_reg().set(z + x_size, x_size + 1);
59 }
60
61}
62
63/*************************************************
64* Set the exponent *
65*************************************************/
66void Montgomery_Exponentiator::set_exponent(const BigInt& exp)
67 {
68 this->exp = exp;
69 exp_bits = exp.bits();
70 }
71
72/*************************************************
73* Set the base *
74*************************************************/
75void Montgomery_Exponentiator::set_base(const BigInt& base)
76 {
77 window_bits = choose_window_bits(exp.bits(), base.bits(), hints);
78
79 g.resize((1 << window_bits) - 1);
80
81 SecureVector<word> z(2 * (mod_words + 1));
82 SecureVector<word> workspace(z.size());
83
84 g[0] = (base >= modulus) ? (base % modulus) : base;
85 bigint_mul(z.begin(), z.size(), workspace,
86 g[0].data(), g[0].size(), g[0].sig_words(),
87 R2.data(), R2.size(), R2.sig_words());
88
89 montgomery_reduce(g[0], z, modulus, mod_words, mod_prime);
90
91 const BigInt& x = g[0];
92 const u32bit x_sig = x.sig_words();
93
94 for(u32bit j = 1; j != g.size(); ++j)
95 {
96 const BigInt& y = g[j-1];
97 const u32bit y_sig = y.sig_words();
98
99 z.clear();
100 bigint_mul(z.begin(), z.size(), workspace,
101 x.data(), x.size(), x_sig,
102 y.data(), y.size(), y_sig);
103
104 montgomery_reduce(g[j], z, modulus, mod_words, mod_prime);
105 }
106 }
107
108/*************************************************
109* Compute the result *
110*************************************************/
111BigInt Montgomery_Exponentiator::execute() const
112 {
113 const u32bit exp_nibbles = (exp_bits + window_bits - 1) / window_bits;
114
115 BigInt x = R_mod;
116 SecureVector<word> z(2 * (mod_words + 1));
117 SecureVector<word> workspace(2 * (mod_words + 1));
118
119 for(u32bit j = exp_nibbles; j > 0; --j)
120 {
121 for(u32bit k = 0; k != window_bits; ++k)
122 {
123 z.clear();
124 bigint_sqr(z.begin(), z.size(), workspace,
125 x.data(), x.size(), x.sig_words());
126
127 montgomery_reduce(x, z, modulus, mod_words, mod_prime);
128 }
129
130 u32bit nibble = exp.get_substring(window_bits*(j-1), window_bits);
131 if(nibble)
132 {
133 const BigInt& y = g[nibble-1];
134
135 z.clear();
136 bigint_mul(z.begin(), z.size(), workspace,
137 x.data(), x.size(), x.sig_words(),
138 y.data(), y.size(), y.sig_words());
139
140 montgomery_reduce(x, z, modulus, mod_words, mod_prime);
141 }
142 }
143
144 z.clear();
145 z.copy(x.data(), x.size());
146
147 montgomery_reduce(x, z, modulus, mod_words, mod_prime);
148 return x;
149 }
150
151/*************************************************
152* Montgomery_Exponentiator Constructor *
153*************************************************/
154Montgomery_Exponentiator::Montgomery_Exponentiator(const BigInt& mod,
155 Power_Mod::Usage_Hints hints)
156 {
157 if(!mod.is_positive())
158 throw Exception("Montgomery_Exponentiator: modulus must be positive");
159 if(mod.is_even())
160 throw Exception("Montgomery_Exponentiator: modulus must be odd");
161
162 window_bits = 0;
163 this->hints = hints;
164 modulus = mod;
165
166 mod_words = modulus.sig_words();
167
168 BigInt mod_prime_bn(BigInt::Power2, MP_WORD_BITS);
169 mod_prime = (mod_prime_bn - inverse_mod(modulus, mod_prime_bn)).word_at(0);
170
171 R_mod = BigInt(BigInt::Power2, MP_WORD_BITS * mod_words);
172 R_mod %= modulus;
173
174 R2 = BigInt(BigInt::Power2, 2 * MP_WORD_BITS * mod_words);
175 R2 %= modulus;
176 }
177
178}

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status