6c04ec3664d324486d5cbbc87e0aca5bce3d4d50
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{The \code{mpbarrett_create} function}
39 \label{fn:mpbarrett-create}
41 \fsec{Synopsis}
43 \begin{listinglist}
44 |#include <catacomb/mpbarrett.h>| \\
45 |void mpbarrett_create(mpbarrett *|$b$|, mp *|$m$|);|
46 \end{listinglist}
48 \fsec{Description}
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.
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.
58 \subsubsection{The \code{mpbarrett_destroy} function}
59 \label{fn:mpbarrett-destroy}
61 \fsec{Synopsis}
63 \begin{listinglist}
64 |#include <catacomb/mpbarrett.h>| \\
65 |void mpbarrett_destroy(mpbarrett *|$b$|);|
66 \end{listinglist}
68 \fsec{Description}
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
74 \subsubsection{The \code{mpbarrett_reduce} function}
75 \label{fn:mpbarrett-reduce}
77 \fsec{Synopsis}
79 \begin{listinglist}
80 |#include <catacomb/mpbarrett.h>| \\
81 |mp *mpbarrett_reduce(mpbarrett *|$b$|, mp *|$d$|, mp *|$x$|);|
82 \end{listinglist}
84 \fsec{Description}
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.
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$.
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}
104 \fsec{Returns}
106 A value $d$ such that $0 \le d < m$ and $d \equiv x \pmod m$.
108 \subsubsection{The \code{mpbarrett_exp} function}
109 \label{fn:mpbarrett-exp}
111 \fsec{Synopsis}
113 \begin{listinglist}
114 |#include <catacomb/mpbarrett.h>| \\
115 |mp *mpbarrett_exp(mpbarrett *|$b$|, mp *|$d$|, mp *|$x$|, mp *|$e$|);|
116 \end{listinglist}
118 \fsec{Description}
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.
123 \fsec{Returns}
125 A value $d$ such that $0 \le d < m$ and $d \equiv x^e \pmod m$.
128 \subsection{Montgomery reduction}
129 \label{sec:mp-mont}
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$}.
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.
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.
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.
167 \subsubsection{Overview of functions provided}
169 All of the types and declarations needed for Montgomery reduction are in the
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}).
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.
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}).
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.
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.
212 \subsubsection{Calculation using Montgomery reduction}
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}
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}
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}
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}).
276 \begin{note}[Important]
277 Montgomery reduction only works when the modulus is an odd number.
278 \end{note}
280 \subsubsection{How it works}
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$.
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$.
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$.
295 \subsubsection{The \code{mpmont_create} function}
296 \label{fn:mpmont-create}
298 \fsec{Synopsis}
300 \begin{listinglist}
301 |#include <catacomb/mpmont.h>| \\
302 |void mpmont_create(mpmont *|$\mm$|, mp *|$m$|);|
303 \end{listinglist}
305 \fsec{Description}
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.
311 If Catacomb is compiled with debugging support enabled, it will abort if $m$
312 is negative or even.
314 \subsubsection{The \code{mpmont_destroy} function}
315 \label{fn:mpmont-destroy}
317 \fsec{Synopsis}
319 \begin{listinglist}
320 |#include <catacomb/mpmont.h>| \\
321 |void mpmont_destroy(mpmont *|$\mm$|);|
322 \end{listinglist}
324 \fsec{Description}
326 Destroys the Montgomery reduction context $\mm$, releasing any resources it
329 \subsubsection{The \code{mpmont_reduce} function}
330 \label{fn:mpmont-reduce}
332 \fsec{Synopsis}
334 \begin{listinglist}
335 |#include <catacomb/mpmont.h>| \\
336 |mp *mpmont_reduce(mpmont *|$\mm$|, mp *|$d$|, mp *|$x$|);|
337 \end{listinglist}
339 \fsec{Description}
341 Performs a Montgomery reduction operation on the integer $x$, modulo $m$.
342 The integer $d$ is a suggested destination.
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$.
347 This function is particularly efficient if $d = x$, i.e., if you overwrite
348 $x$ with its Montgomery reduction.
350 \fsec{Returns}
352 An integer $d$ such that $0 \le d < m$ and $d R \equiv x \pmod m$.
354 \subsubsection{The \code{mpmont_mul} function}
355 \label{fn:mpmont-mul}
357 \fsec{Synopsis}
359 \begin{listinglist}
360 |#include <catacomb/mpmont.h>| \\
361 |mp *mpmont_mul(mpmont *|$\mm$|, mp *|$d$|, mp *|$x$|, mp *|$y$|);|
362 \end{listinglist}
364 \fsec{Description}
366 Multiplies $x$ and $y$, and returns the Montgomery reduction of the product
367 modulo $m$. The integer $d$ is a suggested destination.
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$.
372 \fsec{Returns}
374 An integer $d$ such that $0 \le d < m$ and $d R \equiv x y \bmod m$.
376 %%% Local Variables:
377 %%% mode: latex
378 %%% TeX-master: "catacomb"
379 %%% End: