1 %%% -*-latex-*-
3 \section{Modular arithmetic}
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.
11 \subsection{Barrett reduction}
12 \label{sec:mp-barrett}
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.
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.
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.
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.
38 \subsubsection{How it works}
40 For brevity, let $b = 2^{\code{MPW_BITS}}$ be the base we're working in. Let
41 $m$ be the modulus, and let $k$ be an integer such that $b^{k - 1} \le m < 42 b^k$.
44 The precomputation simply involves calculating $\mu = \lfloor b^{2k} / m 45 \rfloor$. Hence, we have the bound on~$\mu$
46 \begin{equation}
47 \frac{b^{2k}}{m} - 1 < \mu \le \frac{b^{2k}}{m}.
48 \label{eq:mpbarrett-mu-bound}
49 \end{equation}
51 Let $x$ be an integer such that $0 \le x < b^{2k}$. Firstly, let
52 $q_0 = \lfloor x / b^{k - 1} \rfloor$. Thus,
53 \begin{equation}
54 \frac{x}{b^{k - 1}} - 1 < q_0 \le \frac{x}{b^{k - 1}}.
55 \label{eq:mpbarrett-q0-bound}
56 \end{equation}
57 This division an be done simply by ignoring the least significant $k - 1$
58 words in the representation of~$x$, requiring no computation.
60 Next, calculate $q = \lfloor q_0 \mu / b^{k + 1} \rfloor$. The division can
61 again be performed simply by ignoring the least significant $k + 1$ words of
62 the result.
64 Determining the bounds on $q$ is fairly easy, given
65 equations \ref{eq:mpbarrett-mu-bound} and~\ref{eq:mpbarrett-q0-bound}.
66 $67 \biggl\lfloor 68 \frac{(x / b^{k - 1} - 1)(b^{2k} \!/ m - 1) }{b^{k + 1}} 69 \biggr\rfloor 70 \le q \le 71 \biggl\lfloor \frac{(x / b^{k - 1})(b^{2k} \!/ m)}{b^{k + 1}} \biggr\rfloor 72$
73 Thus,
74 $75 \biggl\lfloor 76 \frac{x}{m} - \frac{x}{b^{2k}} - \frac{b^{k - 1}}{m} + \frac{1}{b^{k + 1}} 77 \biggr\rfloor 78 \le q \le 79 \biggl\lfloor \frac{x}{m} \biggr\rfloor 80$
81 Since $b^{k - 1} \le m$ and $x < b^{2k}$, this can be reduced to simply
82 \begin{equation}
83 \biggl\lfloor \frac{x}{m} \biggr\rfloor - 2
84 \le q \le
85 \biggl\lfloor \frac{x}{m} \biggr\rfloor
86 \label{eq:mpbarrett-q-bound}
87 \end{equation}
89 Finally, let $r = x - qm$.
91 Firstly, because of the bounds on $q$ given in
92 equation~\ref{eq:mpbarrett-q-bound}, we have
93 \begin{equation}
94 x \bmod m \le r \le x \bmod m + 2m
95 \label{eq:mpbarrett-r-bound}
96 \end{equation}
97 Since $q$ is an integer, $r$ is equal to $x \bmod m + am$ where $a$ is $0$,
98 $1$ or~$2$.
100 Obviously, $r \le x \bmod m + 2m < 3m$. If $b > 3$, then
101 $3 m < 3 b^k < b^{k + 1}$, because $m < b^k$. Hence the computation of $r$
102 may be performed modulo $b^{k + 1}$, and in particular only the $k + 1$ least
103 significant words of the product~$qm$ need be computed.
105 The actual result $x \bmod m$ may be computed from $r$ by repeatedly
106 subtracting $m$ while the result is still greater than $m$. The bound in
107 equation~\ref{eq:mpbarrett-r-bound} shows that this need be done at most
108 twice.
110 \subsubsection{The \code{mpbarrett_create} function}
111 \label{fn:mpbarrett-create}
113 \fsec{Synopsis}
115 \begin{listinglist}
116 |#include <catacomb/mpbarrett.h>| \\
117 |void mpbarrett_create(mpbarrett *|$b$|, mp *|$m$|);|
118 \end{listinglist}
120 \fsec{Description}
122 Initializes a Barrett reduction context $b$ suitable for performing
123 reductions modulo~$m$. The memory used by the context block must be provided
124 by the caller, and must not be discarded until the context is destroyed.
126 The computation performed is as follows. Let $k = 2 \cdot |MP_LEN(|m|)|$.
127 Calculate $\mu = \lfloor 2^{\code{MPW_BITS} \cdot k} / m \rfloor$. The
128 values $k$, $\mu$ and $m$ are stored in the context block for later use.
130 \subsubsection{The \code{mpbarrett_destroy} function}
131 \label{fn:mpbarrett-destroy}
133 \fsec{Synopsis}
135 \begin{listinglist}
136 |#include <catacomb/mpbarrett.h>| \\
137 |void mpbarrett_destroy(mpbarrett *|$b$|);|
138 \end{listinglist}
140 \fsec{Description}
142 Disposes of a Barrett reduction context. Resources associated with the
143 context block are freed. The memory used to hold the context may safely be
146 \subsubsection{The \code{mpbarrett_reduce} function}
147 \label{fn:mpbarrett-reduce}
149 \fsec{Synopsis}
151 \begin{listinglist}
152 |#include <catacomb/mpbarrett.h>| \\
153 |mp *mpbarrett_reduce(mpbarrett *|$b$|, mp *|$d$|, mp *|$x$|);|
154 \end{listinglist}
156 \fsec{Description}
158 Calculates $x \bmod m$, where $m$ is the modulus configured into the Barrett
159 reduction context~$b$. The argument~$d$ is a suggested destination.
161 Note that not all values of $x$ are suitable for reduction: in particular,
162 negative values are improperly handled. Let $k = 2 \cdot |MP_LEN(|m|)|$;
163 then $x$ must be in the interval $[\,0, 2^{\code{MPW_BITS} \cdot k})$. It's
164 probably safer (and easier) to ensure that $x < m^2$.
166 \fsec{Returns}
168 A value $d$ such that $0 \le d < m$ and $d \equiv x \pmod m$.
170 \subsubsection{The \code{mpbarrett_exp} function}
171 \label{fn:mpbarrett-exp}
173 \fsec{Synopsis}
175 \begin{listinglist}
176 |#include <catacomb/mpbarrett.h>| \\
177 |mp *mpbarrett_exp(mpbarrett *|$b$|, mp *|$d$|, mp *|$x$|, mp *|$e$|);|
178 \end{listinglist}
180 \fsec{Description}
182 Computes $x^e \bmod m$, where $m$ is the modulus configured into the Barrett
183 reduction context~$b$. The argument~$d$ is a suggested destination.
185 \fsec{Returns}
187 A value $d$ such that $0 \le d < m$ and $d \equiv x^e \pmod m$.
190 \subsection{Montgomery reduction}
191 \label{sec:mp-mont}
193 Peter Montgomery has invented an ingenious method for computing modular
194 reductions. The method requires a number of values to be precomputed.
195 \begin{itemize}
196 \item Let $m$ be the modulus. Let $b$ be the radix used to represent
197 multiprecision integers. (In Catacomb, then, $b = 2^{\code{MPW_BITS}}$.)
198 For Montgomery reduction to work, $m$ and~$b$ must have no common factors.
199 \item Let $R = b^n > m$ be the smallest power of $b$ which exceeds~$m$.
200 \item Precompute $m'$ such that $m m' \equiv -1 \pmod b$.
201 \item Precompute $R \bmod m$ and $R^2 \bmod m$, since these are generally
202 useful when using Montgomery's method.
203 \end{itemize}
204 Given $x < R^2$ and the above values, Montgomery's algorithm computes $\mont 205 x = x R^{-1} \bmod m$ efficiently, using only multiplications, additions and
206 word-sized shifts. The quantity $\mont x$ is called the \emph{Montgomery
207 reduction of~$x$}.
209 At first sight, this isn't particularly useful. However, an interesting
210 thing happens if you run an extra factor of $R$ all the way through your
211 calculation. Note for example that the Montgomery reduction of $x R \cdot y 212 R$ is $xy R^2 R^{-1} \bmod m = x y R \bmod m$ -- there's still only a single
213 factor of $R$ in the result. This can be removed finally by an additional
214 reduction step.
216 Catacomb provides a function for performing a simple Montgomery reduction,
217 and for calculating Montgomery multiplication: the Montgomery reduction of
218 the product of two integers.
220 Multiplying in the extra factor of $R$ can be done efficiently by multiplying
221 by $R^2 \bmod m$ and reducing.\footnote{%
222 Some of the Catacomb comments refer to values with a factor of $R$ as
223 having been `Montgomerized'. While this is an ugly word, it does describe
224 a useful concept.} %
225 This is the reason that $R^2 \bmod m$ is precomputed. The value $R \bmod m$
226 is the Montgomery multiplicative identity and is often useful as an initial
227 value when forming products.
229 \subsubsection{Overview of functions provided}
231 All of the types and declarations needed for Montgomery reduction are in the
234 Catacomb maintains precomputed values in a \emph{Montgomery reduction
235 context}, which has type \code{mpmont}. A reduction context is initialized
236 by calling \code{mpmont_create} (page~\pageref{fn:mpmont-create}) and
237 disposed of by \code{mpmont_destroy} (page~\pageref{fn:mpmont-destroy}).
239 The Montgomery reduction context is a structure containing the following
240 members:
241 \begin{description}
242 \def\makelabel#1{\code{#1}\hfil}
243 \item[mp *m] The modulus $m$ with which the reduction context is working.
244 \item[mp *mi] The integer $m'$ where $m m' \equiv -1 \pmod{R}$.
245 \item[size_t n] The smallest integer $n$ such that $R = 2^{\code{MPW_BITS} 246 \cdot n} > m$.
247 \item[mp *r] The integer $R \bmod m$. The Montgomery multiplicative
248 identity.
249 \item[mp *r2] The integer $R^2 \bmod m$.
250 \end{description}
251 All of these are set up by \code{mpmont_create} and should not be changed.
253 Montgomery reduction can be performed by passing a Montgomery reduction
254 context and a number to be reduced to \code{mpmont_reduce}
255 (page~\pageref{fn:mpmont-reduce}). Simultaneous multiplication and reduction
256 are performed by \code{mpmont_mul} (page~\pageref{fn:mpmont-mul}).
258 Catacomb can perform modular exponentiation using Montgomery reduction. The
259 function \code{mpmont_exp} (page~\pageref{fn:mpmont-exp}) performs a standard
260 modular exponentiation; \code{mpmont_expr} (page~\pageref{fn:mpmont-expr})
261 does the same but doesn't remove the factor of $R$ from the result, which can
262 be useful if you want to perform further computations.
264 Catacomb can also perform multiple simultaneous modular exponentations,
265 multiplying the results together, without much of a performance penalty over
266 a single exponentation. The function \code{mpmont_mexp}
267 (page~\pageref{fn:mpmont-mexp}) calculates the product $x_0^{e_0} x_1^{e_1} 268 \ldots x_{k - 1}^{e_{k - 1}} \bmod m$ given an array of $x_i$ and $e_i$;
269 \code{mpmont_mexpr} (page~\pageref{fn:mpmont-mexpr}) does the same but leaves
270 a factor of $R$ in the result. These functions are particularly useful for
271 verifying discrete-logarith-based digital signatures.
273 \subsubsection{Calculation using Montgomery reduction}
275 Before any reduction work can be done, a Montgomery context must be
276 initialized. Suppose $m$ is the modulus we need to work with:
277 \begin{listing}
278 mpmont mm;
279 mpmont_create(&mm, m);
280 \end{listing}
281 The next step is usually to multiply all of the inputs to the calculation
282 by~$R$. This is usually best done like this:
283 \begin{listing}
284 xr = mpmont_mul(&mm, MP_NEW, x, mm.r2);
285 \end{listing}
287 subtraction work normally, although it can be worth doing a little repeated
288 subtraction in case the result ends up larger than the modulus.
289 \begin{listing}
290 a = mp_add(a, a, b);
291 a = mp_add(a, a, c);
292 a = mp_add(a, a, d);
293 while (MP_CMP(a, >=, mm.m))
294 a = mp_sub(a, a, mm.m);
295 \end{listing}
296 Multiplication of different numbers is best done with the supplied
297 multiply-and-reduce operation.
298 \begin{listing}
299 ab = mpmont_mul(&mm, MP_NEW, a, b);
300 \end{listing}
301 However, squaring is best done using separate square and reduce steps.
302 \begin{listing}
303 a2 = mp_sqr(MP_NEW, a);
304 a2 = mpmont_reduce(&mm, a2, a2);
305 \end{listing}
306 When the computation has finished, the results can be read out using
307 straightforward Montgomery reduction. Don't forget to dispose of the
308 reduction context.
309 \begin{listing}
310 x = mpmont_reduce(&mm, x, xr);
311 mpmont_destroy(&mm);
312 \end{listing}
314 For particularly simple calculations, it can save a multiplication if you
315 reduce first and correct afterwards.
316 \begin{listing}
317 ab = mpmont_mul(&mm, MP_NEW, a, b);
318 ab = mpmont_mul(&mm, ab, ab, mm.r2);
319 \end{listing}
320 The first stage computes $ab R^{-1} \bmod m$. The second computes $abR^{-1} 321 \cdot R^2 \cdot R^{-1} \bmod m = ab \bmod m$. Doing this the usual way is
322 nowhere near as efficient:
323 \begin{listing}
324 ar = mpmont_mul(&mm, MP_NEW, a, mm.r2);
325 br = mpmont_mul(&mm, MP_NEW, b, mm.r2);
326 ab = mpmont_mul(&mm, ar, ar, br);
327 ab = mpmont_reduce(&mm, ab, ab);
328 mp_drop(br);
329 \end{listing}
331 Remember that for all of this magic to work, $m$ and $b$ must have no common
332 factors. Since in Catacomb $b$ is a power of 2, this means simply that
333 \emph{$m$ must be odd}. If you want to work with an even modulus, you'll
334 have to use Barrett reduction instead (section~\ref{sec:mp-barrett},
335 page~\pageref{sec:mp-barrett}).
337 \begin{note}[Important]
338 Montgomery reduction only works when the modulus is an odd number.
339 \end{note}
341 \subsubsection{How it works}
343 Let $x$ be the integer we wish to reduce. Compute $u = x m' \bmod R$, and
344 $v = x + u m$.
346 Examining $v \bmod R$, we note that $v \equiv x + m m' x \equiv 0 \pmod R$,
347 since $m m' \equiv -1 \pmod R$. Thus, $v$ is a multiple of $R$. Let $x' = v 348 / R$.
350 Examining $x' \bmod m$ is slightly trickier. By definition, $u = x m' - k R$
351 for some integer $k$. Then $v = x + m(x m' - k R)$, and $x' \equiv v R^{-1} 352 \equiv x R^{-1} \pmod m$.
354 Finally, if $x < m R$ to start with, $u < R$ and so $v < 2 m R$. Hence,
355 $x' < 2 m$, so at most one subtraction of $m$ is enough to compute $x 356 R^{-1} \bmod m$ from $x'$.
359 \subsubsection{The \code{mpmont_create} function}
360 \label{fn:mpmont-create}
362 \fsec{Synopsis}
364 \begin{listinglist}
365 |#include <catacomb/mpmont.h>| \\
366 |void mpmont_create(mpmont *|$\mm$|, mp *|$m$|);|
367 \end{listinglist}
369 \fsec{Description}
371 Initializes a Montgomery reduction context $\mm$, using the given
372 modulus~$m$. The caller must provide memory for the context, and must ensure
373 that the memory remains available until the context is destroyed.
375 If Catacomb is compiled with debugging support enabled, it will abort if $m$
376 is negative or even.
378 \subsubsection{The \code{mpmont_destroy} function}
379 \label{fn:mpmont-destroy}
381 \fsec{Synopsis}
383 \begin{listinglist}
384 |#include <catacomb/mpmont.h>| \\
385 |void mpmont_destroy(mpmont *|$\mm$|);|
386 \end{listinglist}
388 \fsec{Description}
390 Destroys the Montgomery reduction context $\mm$, releasing any resources it
393 \subsubsection{The \code{mpmont_reduce} function}
394 \label{fn:mpmont-reduce}
396 \fsec{Synopsis}
398 \begin{listinglist}
399 |#include <catacomb/mpmont.h>| \\
400 |mp *mpmont_reduce(mpmont *|$\mm$|, mp *|$d$|, mp *|$x$|);|
401 \end{listinglist}
403 \fsec{Description}
405 Performs a Montgomery reduction operation on the integer~$x$, modulo~$m$.
406 The integer~$d$ is a suggested destination.
408 For Montgomery reduction to work, $x$ must be less than~$mR$. In practice,
409 it's probably safest to ensure that $x < m^2$.
411 This function can be particularly efficient if $d = x$, i.e., if you
412 overwrite $x$ with its Montgomery reduction.
414 \fsec{Returns}
416 An integer $d$ such that $0 \le d < m$ and $d R \equiv x \pmod m$.
418 \subsubsection{The \code{mpmont_mul} function}
419 \label{fn:mpmont-mul}
421 \fsec{Synopsis}
423 \begin{listinglist}
424 |#include <catacomb/mpmont.h>| \\
425 |mp *mpmont_mul(mpmont *|$\mm$|, mp *|$d$|, mp *|$x$|, mp *|$y$|);|
426 \end{listinglist}
428 \fsec{Description}
430 Multiplies $x$ and~$y$, and returns the Montgomery reduction of the product
431 modulo $m$. The integer $d$ is a suggested destination.
433 Both $x$ and~$y$ must be less than $R$, and it's probably safer in practice
434 if you ensure that $x, y < m$.
436 \fsec{Returns}
438 An integer $d$ such that $0 \le d < m$ and $d R \equiv x y \bmod m$.
440 %%% Local Variables:
441 %%% mode: latex
442 %%% TeX-master: "catacomb"
443 %%% End: