CommitLineData
3471ebd1 1%%% -*-latex-*-
2
3\section{Modular arithmetic}
4
5Many public key cryptographic algorithms require modular arithmetic of
6various kinds. Modular exponentiation (calculation of $g^x \bmod n$) is
7particularly important. Catacomb provides two efficient methods for
8performing modular arithmetic.
9
10
11\subsection{Barrett reduction}
12\label{sec:mp-barrett}
13
14P.~Barrett invented an elegant method for computing modular reductions. It
674cd11e 15requires a small amount of precomputation, depending only on the modulus~$m$.
16Thereafter, it can compute residues mod~$m$ using only multiplication and
3471ebd1 17arithmetic shifts.
18
19Montgomery's method (section~\ref{sec:mp-mont}, page~\pageref{sec:mp-mont})
20is similar, and more efficient for heavy use, but only works with odd moduli.
21Barrett reduction works with an arbitrary modulus.
22
23The 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
26initialized 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
674cd11e 29less then~$m^2$ may then be reduced modulo~$m$ by passing it to
3471ebd1 30\code{mpbarrett_reduce} (page~\pageref{fn:mpbarrett-reduce}) along with the
31appropriate reduction context.
32
33Since modular exponentiation is such a common operation in cryptography, a
34function \code{mpbarrett_exp} (page~\pageref{fn:mpbarrett-exp}) is provided
35which uses a simple square-and-multiply method combined with Barrett
36reduction.
37
674cd11e 38\subsubsection{How it works}
39
40For 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 < 42b^k$.
43
44The precomputation simply involves calculating $\mu = \lfloor b^{2k} / m 45\rfloor$. Hence, we have the bound on~$\mu$
46
47 \frac{b^{2k}}{m} - 1 < \mu \le \frac{b^{2k}}{m}.
48 \label{eq:mpbarrett-mu-bound}
49
50
51Let $x$ be an integer such that $0 \le x < b^{2k}$. Firstly, let
52$q_0 = \lfloor x / b^{k - 1} \rfloor$. Thus,
53
54 \frac{x}{b^{k - 1}} - 1 < q_0 \le \frac{x}{b^{k - 1}}.
55 \label{eq:mpbarrett-q0-bound}
56
57This division an be done simply by ignoring the least significant $k - 1$
58words in the representation of~$x$, requiring no computation.
59
60Next, calculate $q = \lfloor q_0 \mu / b^{k + 1} \rfloor$. The division can
61again be performed simply by ignoring the least significant $k + 1$ words of
62the result.
63
64Determining the bounds on $q$ is fairly easy, given
65equations \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$
73Thus,
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$
81Since $b^{k - 1} \le m$ and $x < b^{2k}$, this can be reduced to simply
82
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
88
89Finally, let $r = x - qm$.
90
91Firstly, because of the bounds on $q$ given in
92equation~\ref{eq:mpbarrett-q-bound}, we have
93
94 x \bmod m \le r \le x \bmod m + 2m
95 \label{eq:mpbarrett-r-bound}
96
97Since $q$ is an integer, $r$ is equal to $x \bmod m + am$ where $a$ is $0$,
98$1$ or~$2$.
99
100Obviously, $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$
102may be performed modulo $b^{k + 1}$, and in particular only the $k + 1$ least
103significant words of the product~$qm$ need be computed.
104
105The actual result $x \bmod m$ may be computed from $r$ by repeatedly
106subtracting $m$ while the result is still greater than $m$. The bound in
107equation~\ref{eq:mpbarrett-r-bound} shows that this need be done at most
108twice.
109
3471ebd1 110\subsubsection{The \code{mpbarrett_create} function}
111\label{fn:mpbarrett-create}
112
113\fsec{Synopsis}
114
115\begin{listinglist}
116|#include <catacomb/mpbarrett.h>| \\
117|void mpbarrett_create(mpbarrett *|$b$|, mp *|$m$|);|
118\end{listinglist}
119
120\fsec{Description}
121
122Initializes a Barrett reduction context $b$ suitable for performing
674cd11e 123reductions modulo~$m$. The memory used by the context block must be provided
3471ebd1 124by the caller, and must not be discarded until the context is destroyed.
125
126The computation performed is as follows. Let $k = 2 \cdot |MP_LEN(|m|)|$.
127Calculate $\mu = \lfloor 2^{\code{MPW_BITS} \cdot k} / m \rfloor$. The
128values $k$, $\mu$ and $m$ are stored in the context block for later use.
129
130\subsubsection{The \code{mpbarrett_destroy} function}
131\label{fn:mpbarrett-destroy}
132
133\fsec{Synopsis}
134
135\begin{listinglist}
136|#include <catacomb/mpbarrett.h>| \\
137|void mpbarrett_destroy(mpbarrett *|$b$|);|
138\end{listinglist}
139
140\fsec{Description}
141
142Disposes of a Barrett reduction context. Resources associated with the
143context block are freed. The memory used to hold the context may safely be
145
146\subsubsection{The \code{mpbarrett_reduce} function}
147\label{fn:mpbarrett-reduce}
148
149\fsec{Synopsis}
150
151\begin{listinglist}
152|#include <catacomb/mpbarrett.h>| \\
153|mp *mpbarrett_reduce(mpbarrett *|$b$|, mp *|$d$|, mp *|$x$|);|
154\end{listinglist}
155
156\fsec{Description}
157
158Calculates $x \bmod m$, where $m$ is the modulus configured into the Barrett
674cd11e 159reduction context~$b$. The argument~$d$ is a suggested destination.
3471ebd1 160
161Note that not all values of $x$ are suitable for reduction: in particular,
162negative values are improperly handled. Let $k = 2 \cdot |MP_LEN(|m|)|$;
163then $x$ must be in the interval $[\,0, 2^{\code{MPW_BITS} \cdot k})$. It's
674cd11e 164probably safer (and easier) to ensure that $x < m^2$.
3471ebd1 165
166\fsec{Returns}
167
168A value $d$ such that $0 \le d < m$ and $d \equiv x \pmod m$.
169
170\subsubsection{The \code{mpbarrett_exp} function}
171\label{fn:mpbarrett-exp}
172
173\fsec{Synopsis}
174
175\begin{listinglist}
176|#include <catacomb/mpbarrett.h>| \\
177|mp *mpbarrett_exp(mpbarrett *|$b$|, mp *|$d$|, mp *|$x$|, mp *|$e$|);|
178\end{listinglist}
179
180\fsec{Description}
181
182Computes $x^e \bmod m$, where $m$ is the modulus configured into the Barrett
674cd11e 183reduction context~$b$. The argument~$d$ is a suggested destination.
3471ebd1 184
185\fsec{Returns}
186
187A value $d$ such that $0 \le d < m$ and $d \equiv x^e \pmod m$.
188
189
190\subsection{Montgomery reduction}
191\label{sec:mp-mont}
192
193Peter Montgomery has invented an ingenious method for computing modular
194reductions. 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}}$.)
674cd11e 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$.
3471ebd1 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}
204Given $x < R^2$ and the above values, Montgomery's algorithm computes $\mont 205x = x R^{-1} \bmod m$ efficiently, using only multiplications, additions and
206word-sized shifts. The quantity $\mont x$ is called the \emph{Montgomery
674cd11e 207reduction of~$x$}.
3471ebd1 208
209At first sight, this isn't particularly useful. However, an interesting
210thing happens if you run an extra factor of $R$ all the way through your
211calculation. Note for example that the Montgomery reduction of $x R \cdot y 212R$ is $xy R^2 R^{-1} \bmod m = x y R \bmod m$ -- there's still only a single
213factor of $R$ in the result. This can be removed finally by an additional
214reduction step.
215
216Catacomb provides a function for performing a simple Montgomery reduction,
217and for calculating Montgomery multiplication: the Montgomery reduction of
218the product of two integers.
219
220Multiplying in the extra factor of $R$ can be done efficiently by multiplying
221by $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.} %
225This is the reason that $R^2 \bmod m$ is precomputed. The value $R \bmod m$
226is the Montgomery multiplicative identity and is often useful as an initial
227value when forming products.
228
229\subsubsection{Overview of functions provided}
230
231All of the types and declarations needed for Montgomery reduction are in the
233
234Catacomb maintains precomputed values in a \emph{Montgomery reduction
235context}, which has type \code{mpmont}. A reduction context is initialized
236by calling \code{mpmont_create} (page~\pageref{fn:mpmont-create}) and
237disposed of by \code{mpmont_destroy} (page~\pageref{fn:mpmont-destroy}).
238
239The Montgomery reduction context is a structure containing the following
240members:
241\begin{description}
242 \def\makelabel#1{\code{#1}\hfil}
243\item[mp *m] The modulus $m$ with which the reduction context is working.
674cd11e 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
3471ebd1 248 identity.
674cd11e 249\item[mp *r2] The integer $R^2 \bmod m$.
3471ebd1 250\end{description}
251All of these are set up by \code{mpmont_create} and should not be changed.
252
253Montgomery reduction can be performed by passing a Montgomery reduction
254context and a number to be reduced to \code{mpmont_reduce}
255(page~\pageref{fn:mpmont-reduce}). Simultaneous multiplication and reduction
256are performed by \code{mpmont_mul} (page~\pageref{fn:mpmont-mul}).
257
258Catacomb can perform modular exponentiation using Montgomery reduction. The
259function \code{mpmont_exp} (page~\pageref{fn:mpmont-exp}) performs a standard
260modular exponentiation; \code{mpmont_expr} (page~\pageref{fn:mpmont-expr})
261does the same but doesn't remove the factor of $R$ from the result, which can
262be useful if you want to perform further computations.
263
264Catacomb can also perform multiple simultaneous modular exponentations,
265multiplying the results together, without much of a performance penalty over
266a 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
270a factor of $R$ in the result. These functions are particularly useful for
271verifying discrete-logarith-based digital signatures.
272
273\subsubsection{Calculation using Montgomery reduction}
274
275Before any reduction work can be done, a Montgomery context must be
276initialized. Suppose $m$ is the modulus we need to work with:
277\begin{listing}
278mpmont mm;
279mpmont_create(&mm, m);
280\end{listing}
674cd11e 281The next step is usually to multiply all of the inputs to the calculation
282by~$R$. This is usually best done like this:
3471ebd1 283\begin{listing}
284xr = mpmont_mul(&mm, MP_NEW, x, mm.r2);
285\end{listing}
286Because multiplication is distributive over addition, addition and
287subtraction work normally, although it can be worth doing a little repeated
288subtraction in case the result ends up larger than the modulus.
289\begin{listing}
290a = mp_add(a, a, b);
291a = mp_add(a, a, c);
292a = mp_add(a, a, d);
293while (MP_CMP(a, >=, mm.m))
294 a = mp_sub(a, a, mm.m);
295\end{listing}
296Multiplication of different numbers is best done with the supplied
297multiply-and-reduce operation.
298\begin{listing}
299ab = mpmont_mul(&mm, MP_NEW, a, b);
300\end{listing}
301However, squaring is best done using separate square and reduce steps.
302\begin{listing}
303a2 = mp_sqr(MP_NEW, a);
304a2 = mpmont_reduce(&mm, a2, a2);
305\end{listing}
306When the computation has finished, the results can be read out using
307straightforward Montgomery reduction. Don't forget to dispose of the
308reduction context.
309\begin{listing}
310x = mpmont_reduce(&mm, x, xr);
311mpmont_destroy(&mm);
312\end{listing}
313
314For particularly simple calculations, it can save a multiplication if you
315reduce first and correct afterwards.
316\begin{listing}
317ab = mpmont_mul(&mm, MP_NEW, a, b);
318ab = mpmont_mul(&mm, ab, ab, mm.r2);
319\end{listing}
320The 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
322nowhere near as efficient:
323\begin{listing}
324ar = mpmont_mul(&mm, MP_NEW, a, mm.r2);
325br = mpmont_mul(&mm, MP_NEW, b, mm.r2);
326ab = mpmont_mul(&mm, ar, ar, br);
327ab = mpmont_reduce(&mm, ab, ab);
328mp_drop(br);
329\end{listing}
330
331Remember that for all of this magic to work, $m$ and $b$ must have no common
332factors. 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
334have to use Barrett reduction instead (section~\ref{sec:mp-barrett},
335page~\pageref{sec:mp-barrett}).
336
337\begin{note}[Important]
338 Montgomery reduction only works when the modulus is an odd number.
339\end{note}
340
341\subsubsection{How it works}
342
674cd11e 343Let $x$ be the integer we wish to reduce. Compute $u = x m' \bmod R$, and
344$v = x + u m$.
3471ebd1 345
674cd11e 346Examining $v \bmod R$, we note that $v \equiv x + m m' x \equiv 0 \pmod R$,
347since $m m' \equiv -1 \pmod R$. Thus, $v$ is a multiple of $R$. Let $x' = v 348/ R$.
3471ebd1 349
674cd11e 350Examining $x' \bmod m$ is slightly trickier. By definition, $u = x m' - k R$
351for some integer $k$. Then $v = x + m(x m' - k R)$, and $x' \equiv v R^{-1} 352\equiv x R^{-1} \pmod m$.
3471ebd1 353
674cd11e 354Finally, 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 356R^{-1} \bmod m$ from $x'$.
3471ebd1 357
358
359\subsubsection{The \code{mpmont_create} function}
360\label{fn:mpmont-create}
361
362\fsec{Synopsis}
363
364\begin{listinglist}
365|#include <catacomb/mpmont.h>| \\
366|void mpmont_create(mpmont *|$\mm$|, mp *|$m$|);|
367\end{listinglist}
368
369\fsec{Description}
370
674cd11e 371Initializes a Montgomery reduction context $\mm$, using the given
372modulus~$m$. The caller must provide memory for the context, and must ensure
373that the memory remains available until the context is destroyed.
3471ebd1 374
375If Catacomb is compiled with debugging support enabled, it will abort if $m$
376is negative or even.
377
378\subsubsection{The \code{mpmont_destroy} function}
379\label{fn:mpmont-destroy}
380
381\fsec{Synopsis}
382
383\begin{listinglist}
384|#include <catacomb/mpmont.h>| \\
385|void mpmont_destroy(mpmont *|$\mm$|);|
386\end{listinglist}
387
388\fsec{Description}
389
390Destroys the Montgomery reduction context $\mm$, releasing any resources it
392
393\subsubsection{The \code{mpmont_reduce} function}
394\label{fn:mpmont-reduce}
395
396\fsec{Synopsis}
397
398\begin{listinglist}
399|#include <catacomb/mpmont.h>| \\
400|mp *mpmont_reduce(mpmont *|$\mm$|, mp *|$d$|, mp *|$x$|);|
401\end{listinglist}
402
403\fsec{Description}
404
674cd11e 405Performs a Montgomery reduction operation on the integer~$x$, modulo~$m$.
406The integer~$d$ is a suggested destination.
3471ebd1 407
674cd11e 408For Montgomery reduction to work, $x$ must be less than~$mR$. In practice,
3471ebd1 409it's probably safest to ensure that $x < m^2$.
410
674cd11e 411This function can be particularly efficient if $d = x$, i.e., if you
412overwrite $x$ with its Montgomery reduction.
3471ebd1 413
414\fsec{Returns}
415
416An integer $d$ such that $0 \le d < m$ and $d R \equiv x \pmod m$.
417
418\subsubsection{The \code{mpmont_mul} function}
419\label{fn:mpmont-mul}
420
421\fsec{Synopsis}
422
423\begin{listinglist}
424|#include <catacomb/mpmont.h>| \\
425|mp *mpmont_mul(mpmont *|$\mm$|, mp *|$d$|, mp *|$x$|, mp *|$y$|);|
426\end{listinglist}
427
428\fsec{Description}
429
674cd11e 430Multiplies $x$ and~$y$, and returns the Montgomery reduction of the product
3471ebd1 431modulo $m$. The integer $d$ is a suggested destination.
432
674cd11e 433Both $x$ and~$y$ must be less than $R$, and it's probably safer in practice
3471ebd1 434if you ensure that $x, y < m$.
435
436\fsec{Returns}
437
438An integer $d$ such that $0 \le d < m$ and $d R \equiv x y \bmod m$.
439
440%%% Local Variables:
441%%% mode: latex
442%%% TeX-master: "catacomb"
443%%% End: