3471ebd1 |
1 | %%% -*-latex-*- |
2 | |
3 | \section{Modular arithmetic} |
4 | |
5 | Many public key cryptographic algorithms require modular arithmetic of |
6 | various kinds. Modular exponentiation (calculation of $g^x \bmod n$) is |
7 | particularly important. Catacomb provides two efficient methods for |
8 | performing modular arithmetic. |
9 | |
10 | |
11 | \subsection{Barrett reduction} |
12 | \label{sec:mp-barrett} |
13 | |
14 | P.~Barrett invented an elegant method for computing modular reductions. It |
15 | requires a small amount of precomputation, depending only on the modulus $m$. |
16 | Thereafter, it can compute residues mod $m$ using only multiplication and |
17 | arithmetic shifts. |
18 | |
19 | Montgomery's method (section~\ref{sec:mp-mont}, page~\pageref{sec:mp-mont}) |
20 | is similar, and more efficient for heavy use, but only works with odd moduli. |
21 | Barrett reduction works with an arbitrary modulus. |
22 | |
23 | The declarations required to use Barrett reduction are in |
24 | \hdr{<catacomb/mpbarrett.h>}. The precomuted values required are stored in a |
25 | \emph{Barrett reduction context} of type \code{mpbarrett}. A context can be |
26 | initialized by calling \code{mpbarrett_create} |
27 | (page~\pageref{fn:mpbarrett-create}) and disposed of by |
28 | \code{mpbarrett_destroy} (page~\pageref{fn:mpbarrett-destroy}). A number |
29 | less then $m^2$ may then be reduced modulo $m$ by passing it to |
30 | \code{mpbarrett_reduce} (page~\pageref{fn:mpbarrett-reduce}) along with the |
31 | appropriate reduction context. |
32 | |
33 | Since modular exponentiation is such a common operation in cryptography, a |
34 | function \code{mpbarrett_exp} (page~\pageref{fn:mpbarrett-exp}) is provided |
35 | which uses a simple square-and-multiply method combined with Barrett |
36 | reduction. |
37 | |
38 | \subsubsection{The \code{mpbarrett_create} function} |
39 | \label{fn:mpbarrett-create} |
40 | |
41 | \fsec{Synopsis} |
42 | |
43 | \begin{listinglist} |
44 | |#include <catacomb/mpbarrett.h>| \\ |
45 | |void mpbarrett_create(mpbarrett *|$b$|, mp *|$m$|);| |
46 | \end{listinglist} |
47 | |
48 | \fsec{Description} |
49 | |
50 | Initializes a Barrett reduction context $b$ suitable for performing |
51 | reductions modulo $m$. The memory used by the context block must be provided |
52 | by the caller, and must not be discarded until the context is destroyed. |
53 | |
54 | The computation performed is as follows. Let $k = 2 \cdot |MP_LEN(|m|)|$. |
55 | Calculate $\mu = \lfloor 2^{\code{MPW_BITS} \cdot k} / m \rfloor$. The |
56 | values $k$, $\mu$ and $m$ are stored in the context block for later use. |
57 | |
58 | \subsubsection{The \code{mpbarrett_destroy} function} |
59 | \label{fn:mpbarrett-destroy} |
60 | |
61 | \fsec{Synopsis} |
62 | |
63 | \begin{listinglist} |
64 | |#include <catacomb/mpbarrett.h>| \\ |
65 | |void mpbarrett_destroy(mpbarrett *|$b$|);| |
66 | \end{listinglist} |
67 | |
68 | \fsec{Description} |
69 | |
70 | Disposes of a Barrett reduction context. Resources associated with the |
71 | context block are freed. The memory used to hold the context may safely be |
72 | discarded. |
73 | |
74 | \subsubsection{The \code{mpbarrett_reduce} function} |
75 | \label{fn:mpbarrett-reduce} |
76 | |
77 | \fsec{Synopsis} |
78 | |
79 | \begin{listinglist} |
80 | |#include <catacomb/mpbarrett.h>| \\ |
81 | |mp *mpbarrett_reduce(mpbarrett *|$b$|, mp *|$d$|, mp *|$x$|);| |
82 | \end{listinglist} |
83 | |
84 | \fsec{Description} |
85 | |
86 | Calculates $x \bmod m$, where $m$ is the modulus configured into the Barrett |
87 | reduction context $b$. The argument $d$ is a suggested destination. |
88 | |
89 | Note that not all values of $x$ are suitable for reduction: in particular, |
90 | negative values are improperly handled. Let $k = 2 \cdot |MP_LEN(|m|)|$; |
91 | then $x$ must be in the interval $[\,0, 2^{\code{MPW_BITS} \cdot k})$. It's |
92 | probably safer (and eqsier) to ensure that $x < m^2$. |
93 | |
94 | For reference, the calculation works as follows: |
95 | \begin{itemize} |
96 | \item To simplify the notation, let $b = 2^{\code{MPW_BITS}}$. |
97 | \item Let $q_0 = \lfloor x / b^{k - 1} \rfloor$. Let |
98 | $q = \lfloor q_0 \mu / b^{k + 1} \rfloor$. |
99 | \item Let $r = (x - q m) \bmod b^{k + 1}$. |
100 | \item At this point, $r \equiv x \pmod m$, but $r$ may be too large. It can |
101 | be reduced by repeated subtraction until it's in range. |
102 | \end{itemize} |
103 | |
104 | \fsec{Returns} |
105 | |
106 | A value $d$ such that $0 \le d < m$ and $d \equiv x \pmod m$. |
107 | |
108 | \subsubsection{The \code{mpbarrett_exp} function} |
109 | \label{fn:mpbarrett-exp} |
110 | |
111 | \fsec{Synopsis} |
112 | |
113 | \begin{listinglist} |
114 | |#include <catacomb/mpbarrett.h>| \\ |
115 | |mp *mpbarrett_exp(mpbarrett *|$b$|, mp *|$d$|, mp *|$x$|, mp *|$e$|);| |
116 | \end{listinglist} |
117 | |
118 | \fsec{Description} |
119 | |
120 | Computes $x^e \bmod m$, where $m$ is the modulus configured into the Barrett |
121 | reduction context $b$. The argument $d$ is a suggested destination. |
122 | |
123 | \fsec{Returns} |
124 | |
125 | A value $d$ such that $0 \le d < m$ and $d \equiv x^e \pmod m$. |
126 | |
127 | |
128 | \subsection{Montgomery reduction} |
129 | \label{sec:mp-mont} |
130 | |
131 | Peter Montgomery has invented an ingenious method for computing modular |
132 | reductions. The method requires a number of values to be precomputed. |
133 | \begin{itemize} |
134 | \item Let $m$ be the modulus. Let $b$ be the radix used to represent |
135 | multiprecision integers. (In Catacomb, then, $b = 2^{\code{MPW_BITS}}$.) |
136 | For Montgomery reduction to work, $m$ and $b$ must have no common factors. |
137 | \item Let $R = b^n > m$ be the smallest power of $b$ which exceeds $m$. |
138 | \item Precompute $m'$ such that $m m' \equiv -1 \pmod b$. |
139 | \item Precompute $R \bmod m$ and $R^2 \bmod m$, since these are generally |
140 | useful when using Montgomery's method. |
141 | \end{itemize} |
142 | Given $x < R^2$ and the above values, Montgomery's algorithm computes $\mont |
143 | x = x R^{-1} \bmod m$ efficiently, using only multiplications, additions and |
144 | word-sized shifts. The quantity $\mont x$ is called the \emph{Montgomery |
145 | reduction of $x$}. |
146 | |
147 | At first sight, this isn't particularly useful. However, an interesting |
148 | thing happens if you run an extra factor of $R$ all the way through your |
149 | calculation. Note for example that the Montgomery reduction of $x R \cdot y |
150 | R$ is $xy R^2 R^{-1} \bmod m = x y R \bmod m$ -- there's still only a single |
151 | factor of $R$ in the result. This can be removed finally by an additional |
152 | reduction step. |
153 | |
154 | Catacomb provides a function for performing a simple Montgomery reduction, |
155 | and for calculating Montgomery multiplication: the Montgomery reduction of |
156 | the product of two integers. |
157 | |
158 | Multiplying in the extra factor of $R$ can be done efficiently by multiplying |
159 | by $R^2 \bmod m$ and reducing.\footnote{% |
160 | Some of the Catacomb comments refer to values with a factor of $R$ as |
161 | having been `Montgomerized'. While this is an ugly word, it does describe |
162 | a useful concept.} % |
163 | This is the reason that $R^2 \bmod m$ is precomputed. The value $R \bmod m$ |
164 | is the Montgomery multiplicative identity and is often useful as an initial |
165 | value when forming products. |
166 | |
167 | \subsubsection{Overview of functions provided} |
168 | |
169 | All of the types and declarations needed for Montgomery reduction are in the |
170 | header file \hdr{<catacomb/mpmont.h>}. |
171 | |
172 | Catacomb maintains precomputed values in a \emph{Montgomery reduction |
173 | context}, which has type \code{mpmont}. A reduction context is initialized |
174 | by calling \code{mpmont_create} (page~\pageref{fn:mpmont-create}) and |
175 | disposed of by \code{mpmont_destroy} (page~\pageref{fn:mpmont-destroy}). |
176 | |
177 | The Montgomery reduction context is a structure containing the following |
178 | members: |
179 | \begin{description} |
180 | \def\makelabel#1{\code{#1}\hfil} |
181 | \item[mp *m] The modulus $m$ with which the reduction context is working. |
182 | \item[mp *mi] The quantity $m'$ where $m m' \equiv -1 |
183 | \pmod{ 2^{\code{MPW_BITS}}}$. |
184 | \item[size_t shift] The smallest integer $n$ such that |
185 | $R = 2^{\code{MPW_BITS} \cdot n} > m$. |
186 | \item[mp *r] The quantity $R \bmod m$. The Montgomery multiplicative |
187 | identity. |
188 | \item[mp *r2] The quantity $R^2 \bmod m$. |
189 | \end{description} |
190 | All of these are set up by \code{mpmont_create} and should not be changed. |
191 | |
192 | Montgomery reduction can be performed by passing a Montgomery reduction |
193 | context and a number to be reduced to \code{mpmont_reduce} |
194 | (page~\pageref{fn:mpmont-reduce}). Simultaneous multiplication and reduction |
195 | are performed by \code{mpmont_mul} (page~\pageref{fn:mpmont-mul}). |
196 | |
197 | Catacomb can perform modular exponentiation using Montgomery reduction. The |
198 | function \code{mpmont_exp} (page~\pageref{fn:mpmont-exp}) performs a standard |
199 | modular exponentiation; \code{mpmont_expr} (page~\pageref{fn:mpmont-expr}) |
200 | does the same but doesn't remove the factor of $R$ from the result, which can |
201 | be useful if you want to perform further computations. |
202 | |
203 | Catacomb can also perform multiple simultaneous modular exponentations, |
204 | multiplying the results together, without much of a performance penalty over |
205 | a single exponentation. The function \code{mpmont_mexp} |
206 | (page~\pageref{fn:mpmont-mexp}) calculates the product $x_0^{e_0} x_1^{e_1} |
207 | \ldots x_{k - 1}^{e_{k - 1}} \bmod m$ given an array of $x_i$ and $e_i$; |
208 | \code{mpmont_mexpr} (page~\pageref{fn:mpmont-mexpr}) does the same but leaves |
209 | a factor of $R$ in the result. These functions are particularly useful for |
210 | verifying discrete-logarith-based digital signatures. |
211 | |
212 | \subsubsection{Calculation using Montgomery reduction} |
213 | |
214 | Before any reduction work can be done, a Montgomery context must be |
215 | initialized. Suppose $m$ is the modulus we need to work with: |
216 | \begin{listing} |
217 | mpmont mm; |
218 | mpmont_create(&mm, m); |
219 | \end{listing} |
220 | The next step is usually to multiply all of the inputs to the calculation by |
221 | $R$. This is usually best done like this: |
222 | \begin{listing} |
223 | xr = mpmont_mul(&mm, MP_NEW, x, mm.r2); |
224 | \end{listing} |
225 | Because multiplication is distributive over addition, addition and |
226 | subtraction work normally, although it can be worth doing a little repeated |
227 | subtraction in case the result ends up larger than the modulus. |
228 | \begin{listing} |
229 | a = mp_add(a, a, b); |
230 | a = mp_add(a, a, c); |
231 | a = mp_add(a, a, d); |
232 | while (MP_CMP(a, >=, mm.m)) |
233 | a = mp_sub(a, a, mm.m); |
234 | \end{listing} |
235 | Multiplication of different numbers is best done with the supplied |
236 | multiply-and-reduce operation. |
237 | \begin{listing} |
238 | ab = mpmont_mul(&mm, MP_NEW, a, b); |
239 | \end{listing} |
240 | However, squaring is best done using separate square and reduce steps. |
241 | \begin{listing} |
242 | a2 = mp_sqr(MP_NEW, a); |
243 | a2 = mpmont_reduce(&mm, a2, a2); |
244 | \end{listing} |
245 | When the computation has finished, the results can be read out using |
246 | straightforward Montgomery reduction. Don't forget to dispose of the |
247 | reduction context. |
248 | \begin{listing} |
249 | x = mpmont_reduce(&mm, x, xr); |
250 | mpmont_destroy(&mm); |
251 | \end{listing} |
252 | |
253 | For particularly simple calculations, it can save a multiplication if you |
254 | reduce first and correct afterwards. |
255 | \begin{listing} |
256 | ab = mpmont_mul(&mm, MP_NEW, a, b); |
257 | ab = mpmont_mul(&mm, ab, ab, mm.r2); |
258 | \end{listing} |
259 | The first stage computes $ab R^{-1} \bmod m$. The second computes $abR^{-1} |
260 | \cdot R^2 \cdot R^{-1} \bmod m = ab \bmod m$. Doing this the usual way is |
261 | nowhere near as efficient: |
262 | \begin{listing} |
263 | ar = mpmont_mul(&mm, MP_NEW, a, mm.r2); |
264 | br = mpmont_mul(&mm, MP_NEW, b, mm.r2); |
265 | ab = mpmont_mul(&mm, ar, ar, br); |
266 | ab = mpmont_reduce(&mm, ab, ab); |
267 | mp_drop(br); |
268 | \end{listing} |
269 | |
270 | Remember that for all of this magic to work, $m$ and $b$ must have no common |
271 | factors. Since in Catacomb $b$ is a power of 2, this means simply that |
272 | \emph{$m$ must be odd}. If you want to work with an even modulus, you'll |
273 | have to use Barrett reduction instead (section~\ref{sec:mp-barrett}, |
274 | page~\pageref{sec:mp-barrett}). |
275 | |
276 | \begin{note}[Important] |
277 | Montgomery reduction only works when the modulus is an odd number. |
278 | \end{note} |
279 | |
280 | \subsubsection{How it works} |
281 | |
282 | Let $x_0$ be the integer we wish to reduce. Compute $u_1 = x_0 m' \bmod b$, |
283 | and $v_1 = x_0 + u_1 m$. |
284 | |
285 | Obviously $u_1 = x_0 m' + bk$ for some integer $k$. So $v_1 = x_0 + u_1 m = |
286 | x_0 + x_0 m m' + b k m$. Note that $m m' \equiv -1 \pmod b$; thus $m m' = |
287 | b k' - 1$ for some $k'$, so $v_1$ then becomes $x_0(1 + bk' - 1) + b k m = |
288 | b (k' x_0 + k m)$. Let $x_1 = v_1 / b = k' x_0 + k m$. |
289 | |
290 | Now note that $b k' = m m' + 1$, so $b k' \equiv 1 \pmod m$; hence, $k' |
291 | \equiv b^{-1} \pmod m$. Thus $x_1 \equiv x_0 b^{-1} \pmod m$. |
292 | |
293 | |
294 | |
295 | \subsubsection{The \code{mpmont_create} function} |
296 | \label{fn:mpmont-create} |
297 | |
298 | \fsec{Synopsis} |
299 | |
300 | \begin{listinglist} |
301 | |#include <catacomb/mpmont.h>| \\ |
302 | |void mpmont_create(mpmont *|$\mm$|, mp *|$m$|);| |
303 | \end{listinglist} |
304 | |
305 | \fsec{Description} |
306 | |
307 | Initializes a Montgomery reduction context $\mm$, using the given modulus |
308 | $m$. The caller must provide memory for the context, and must ensure that |
309 | the memory remains available until the context is destroyed. |
310 | |
311 | If Catacomb is compiled with debugging support enabled, it will abort if $m$ |
312 | is negative or even. |
313 | |
314 | \subsubsection{The \code{mpmont_destroy} function} |
315 | \label{fn:mpmont-destroy} |
316 | |
317 | \fsec{Synopsis} |
318 | |
319 | \begin{listinglist} |
320 | |#include <catacomb/mpmont.h>| \\ |
321 | |void mpmont_destroy(mpmont *|$\mm$|);| |
322 | \end{listinglist} |
323 | |
324 | \fsec{Description} |
325 | |
326 | Destroys the Montgomery reduction context $\mm$, releasing any resources it |
327 | had acquired. |
328 | |
329 | \subsubsection{The \code{mpmont_reduce} function} |
330 | \label{fn:mpmont-reduce} |
331 | |
332 | \fsec{Synopsis} |
333 | |
334 | \begin{listinglist} |
335 | |#include <catacomb/mpmont.h>| \\ |
336 | |mp *mpmont_reduce(mpmont *|$\mm$|, mp *|$d$|, mp *|$x$|);| |
337 | \end{listinglist} |
338 | |
339 | \fsec{Description} |
340 | |
341 | Performs a Montgomery reduction operation on the integer $x$, modulo $m$. |
342 | The integer $d$ is a suggested destination. |
343 | |
344 | For Montgomery reduction to work, $x$ must be less than $R^2$. In practice, |
345 | it's probably safest to ensure that $x < m^2$. |
346 | |
347 | This function is particularly efficient if $d = x$, i.e., if you overwrite |
348 | $x$ with its Montgomery reduction. |
349 | |
350 | \fsec{Returns} |
351 | |
352 | An integer $d$ such that $0 \le d < m$ and $d R \equiv x \pmod m$. |
353 | |
354 | \subsubsection{The \code{mpmont_mul} function} |
355 | \label{fn:mpmont-mul} |
356 | |
357 | \fsec{Synopsis} |
358 | |
359 | \begin{listinglist} |
360 | |#include <catacomb/mpmont.h>| \\ |
361 | |mp *mpmont_mul(mpmont *|$\mm$|, mp *|$d$|, mp *|$x$|, mp *|$y$|);| |
362 | \end{listinglist} |
363 | |
364 | \fsec{Description} |
365 | |
366 | Multiplies $x$ and $y$, and returns the Montgomery reduction of the product |
367 | modulo $m$. The integer $d$ is a suggested destination. |
368 | |
369 | Both $x$ and $y$ must be less than $R$, and it's probably safer in practice |
370 | if you ensure that $x, y < m$. |
371 | |
372 | \fsec{Returns} |
373 | |
374 | An integer $d$ such that $0 \le d < m$ and $d R \equiv x y \bmod m$. |
375 | |
376 | %%% Local Variables: |
377 | %%% mode: latex |
378 | %%% TeX-master: "catacomb" |
379 | %%% End: |