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 |
674cd11e |
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 |
3471ebd1 |
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 |
674cd11e |
29 | less 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 |
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 | |
674cd11e |
38 | \subsubsection{How it works} |
39 | |
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$. |
43 | |
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} |
50 | |
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. |
59 | |
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. |
63 | |
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} |
88 | |
89 | Finally, let $r = x - qm$. |
90 | |
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$. |
99 | |
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. |
104 | |
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. |
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 | |
122 | Initializes a Barrett reduction context $b$ suitable for performing |
674cd11e |
123 | reductions modulo~$m$. The memory used by the context block must be provided |
3471ebd1 |
124 | by the caller, and must not be discarded until the context is destroyed. |
125 | |
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. |
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 | |
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 |
144 | discarded. |
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 | |
158 | Calculates $x \bmod m$, where $m$ is the modulus configured into the Barrett |
674cd11e |
159 | reduction context~$b$. The argument~$d$ is a suggested destination. |
3471ebd1 |
160 | |
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 |
674cd11e |
164 | probably safer (and easier) to ensure that $x < m^2$. |
3471ebd1 |
165 | |
166 | \fsec{Returns} |
167 | |
168 | A 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 | |
182 | Computes $x^e \bmod m$, where $m$ is the modulus configured into the Barrett |
674cd11e |
183 | reduction context~$b$. The argument~$d$ is a suggested destination. |
3471ebd1 |
184 | |
185 | \fsec{Returns} |
186 | |
187 | A 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 | |
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}}$.) |
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} |
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 |
674cd11e |
207 | reduction of~$x$}. |
3471ebd1 |
208 | |
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. |
215 | |
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. |
219 | |
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. |
228 | |
229 | \subsubsection{Overview of functions provided} |
230 | |
231 | All of the types and declarations needed for Montgomery reduction are in the |
232 | header file \hdr{<catacomb/mpmont.h>}. |
233 | |
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}). |
238 | |
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. |
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} |
251 | All of these are set up by \code{mpmont_create} and should not be changed. |
252 | |
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}). |
257 | |
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. |
263 | |
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. |
272 | |
273 | \subsubsection{Calculation using Montgomery reduction} |
274 | |
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} |
674cd11e |
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: |
3471ebd1 |
283 | \begin{listing} |
284 | xr = mpmont_mul(&mm, MP_NEW, x, mm.r2); |
285 | \end{listing} |
286 | Because multiplication is distributive over addition, addition and |
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} |
313 | |
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} |
330 | |
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}). |
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 |
343 | Let $x$ be the integer we wish to reduce. Compute $u = x m' \bmod R$, and |
344 | $v = x + u m$. |
3471ebd1 |
345 | |
674cd11e |
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$. |
3471ebd1 |
349 | |
674cd11e |
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$. |
3471ebd1 |
353 | |
674cd11e |
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'$. |
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 |
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. |
3471ebd1 |
374 | |
375 | If Catacomb is compiled with debugging support enabled, it will abort if $m$ |
376 | is 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 | |
390 | Destroys the Montgomery reduction context $\mm$, releasing any resources it |
391 | had acquired. |
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 |
405 | Performs a Montgomery reduction operation on the integer~$x$, modulo~$m$. |
406 | The integer~$d$ is a suggested destination. |
3471ebd1 |
407 | |
674cd11e |
408 | For Montgomery reduction to work, $x$ must be less than~$mR$. In practice, |
3471ebd1 |
409 | it's probably safest to ensure that $x < m^2$. |
410 | |
674cd11e |
411 | This function can be particularly efficient if $d = x$, i.e., if you |
412 | overwrite $x$ with its Montgomery reduction. |
3471ebd1 |
413 | |
414 | \fsec{Returns} |
415 | |
416 | An 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 |
430 | Multiplies $x$ and~$y$, and returns the Montgomery reduction of the product |
3471ebd1 |
431 | modulo $m$. The integer $d$ is a suggested destination. |
432 | |
674cd11e |
433 | Both $x$ and~$y$ must be less than $R$, and it's probably safer in practice |
3471ebd1 |
434 | if you ensure that $x, y < m$. |
435 | |
436 | \fsec{Returns} |
437 | |
438 | An integer $d$ such that $0 \le d < m$ and $d R \equiv x y \bmod m$. |
439 | |
45c0fd36 |
440 | %%% Local Variables: |
3471ebd1 |
441 | %%% mode: latex |
442 | %%% TeX-master: "catacomb" |
45c0fd36 |
443 | %%% End: |