| 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{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 | |
| 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 |
| 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. |
| 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 |
| 159 | reduction context~$b$. The argument~$d$ is a suggested destination. |
| 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 |
| 164 | probably safer (and easier) to ensure that $x < m^2$. |
| 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 |
| 183 | reduction context~$b$. The argument~$d$ is a suggested destination. |
| 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}}$.) |
| 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$}. |
| 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. |
| 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. |
| 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} |
| 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} |
| 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 | |
| 343 | Let $x$ be the integer we wish to reduce. Compute $u = x m' \bmod R$, and |
| 344 | $v = x + u m$. |
| 345 | |
| 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$. |
| 349 | |
| 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$. |
| 353 | |
| 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'$. |
| 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 | |
| 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. |
| 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 | |
| 405 | Performs a Montgomery reduction operation on the integer~$x$, modulo~$m$. |
| 406 | The integer~$d$ is a suggested destination. |
| 407 | |
| 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$. |
| 410 | |
| 411 | This function can be particularly efficient if $d = x$, i.e., if you |
| 412 | overwrite $x$ with its Montgomery reduction. |
| 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 | |
| 430 | Multiplies $x$ and~$y$, and returns the Montgomery reduction of the product |
| 431 | modulo $m$. The integer $d$ is a suggested destination. |
| 432 | |
| 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$. |
| 435 | |
| 436 | \fsec{Returns} |
| 437 | |
| 438 | An 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: |