| 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{The \code{mpbarrett_create} function} |
| 39 | \label{fn:mpbarrett-create} |
| 40 | |
| 41 | \fsec{Synopsis} |
| 42 | |
| 43 | \begin{listinglist} |
| 44 | |#include <catacomb/mpbarrett.h>| \\ |
| 45 | |void mpbarrett_create(mpbarrett *|$b$|, mp *|$m$|);| |
| 46 | \end{listinglist} |
| 47 | |
| 48 | \fsec{Description} |
| 49 | |
| 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. |
| 53 | |
| 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. |
| 57 | |
| 58 | \subsubsection{The \code{mpbarrett_destroy} function} |
| 59 | \label{fn:mpbarrett-destroy} |
| 60 | |
| 61 | \fsec{Synopsis} |
| 62 | |
| 63 | \begin{listinglist} |
| 64 | |#include <catacomb/mpbarrett.h>| \\ |
| 65 | |void mpbarrett_destroy(mpbarrett *|$b$|);| |
| 66 | \end{listinglist} |
| 67 | |
| 68 | \fsec{Description} |
| 69 | |
| 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 |
| 72 | discarded. |
| 73 | |
| 74 | \subsubsection{The \code{mpbarrett_reduce} function} |
| 75 | \label{fn:mpbarrett-reduce} |
| 76 | |
| 77 | \fsec{Synopsis} |
| 78 | |
| 79 | \begin{listinglist} |
| 80 | |#include <catacomb/mpbarrett.h>| \\ |
| 81 | |mp *mpbarrett_reduce(mpbarrett *|$b$|, mp *|$d$|, mp *|$x$|);| |
| 82 | \end{listinglist} |
| 83 | |
| 84 | \fsec{Description} |
| 85 | |
| 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. |
| 88 | |
| 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$. |
| 93 | |
| 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} |
| 103 | |
| 104 | \fsec{Returns} |
| 105 | |
| 106 | A value $d$ such that $0 \le d < m$ and $d \equiv x \pmod m$. |
| 107 | |
| 108 | \subsubsection{The \code{mpbarrett_exp} function} |
| 109 | \label{fn:mpbarrett-exp} |
| 110 | |
| 111 | \fsec{Synopsis} |
| 112 | |
| 113 | \begin{listinglist} |
| 114 | |#include <catacomb/mpbarrett.h>| \\ |
| 115 | |mp *mpbarrett_exp(mpbarrett *|$b$|, mp *|$d$|, mp *|$x$|, mp *|$e$|);| |
| 116 | \end{listinglist} |
| 117 | |
| 118 | \fsec{Description} |
| 119 | |
| 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. |
| 122 | |
| 123 | \fsec{Returns} |
| 124 | |
| 125 | A value $d$ such that $0 \le d < m$ and $d \equiv x^e \pmod m$. |
| 126 | |
| 127 | |
| 128 | \subsection{Montgomery reduction} |
| 129 | \label{sec:mp-mont} |
| 130 | |
| 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$}. |
| 146 | |
| 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. |
| 153 | |
| 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. |
| 157 | |
| 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. |
| 166 | |
| 167 | \subsubsection{Overview of functions provided} |
| 168 | |
| 169 | All of the types and declarations needed for Montgomery reduction are in the |
| 170 | header file \hdr{<catacomb/mpmont.h>}. |
| 171 | |
| 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}). |
| 176 | |
| 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. |
| 191 | |
| 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}). |
| 196 | |
| 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. |
| 202 | |
| 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. |
| 211 | |
| 212 | \subsubsection{Calculation using Montgomery reduction} |
| 213 | |
| 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} |
| 225 | Because multiplication is distributive over addition, addition and |
| 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} |
| 252 | |
| 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} |
| 269 | |
| 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}). |
| 275 | |
| 276 | \begin{note}[Important] |
| 277 | Montgomery reduction only works when the modulus is an odd number. |
| 278 | \end{note} |
| 279 | |
| 280 | \subsubsection{How it works} |
| 281 | |
| 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$. |
| 284 | |
| 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$. |
| 289 | |
| 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$. |
| 292 | |
| 293 | |
| 294 | |
| 295 | \subsubsection{The \code{mpmont_create} function} |
| 296 | \label{fn:mpmont-create} |
| 297 | |
| 298 | \fsec{Synopsis} |
| 299 | |
| 300 | \begin{listinglist} |
| 301 | |#include <catacomb/mpmont.h>| \\ |
| 302 | |void mpmont_create(mpmont *|$\mm$|, mp *|$m$|);| |
| 303 | \end{listinglist} |
| 304 | |
| 305 | \fsec{Description} |
| 306 | |
| 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. |
| 310 | |
| 311 | If Catacomb is compiled with debugging support enabled, it will abort if $m$ |
| 312 | is negative or even. |
| 313 | |
| 314 | \subsubsection{The \code{mpmont_destroy} function} |
| 315 | \label{fn:mpmont-destroy} |
| 316 | |
| 317 | \fsec{Synopsis} |
| 318 | |
| 319 | \begin{listinglist} |
| 320 | |#include <catacomb/mpmont.h>| \\ |
| 321 | |void mpmont_destroy(mpmont *|$\mm$|);| |
| 322 | \end{listinglist} |
| 323 | |
| 324 | \fsec{Description} |
| 325 | |
| 326 | Destroys the Montgomery reduction context $\mm$, releasing any resources it |
| 327 | had acquired. |
| 328 | |
| 329 | \subsubsection{The \code{mpmont_reduce} function} |
| 330 | \label{fn:mpmont-reduce} |
| 331 | |
| 332 | \fsec{Synopsis} |
| 333 | |
| 334 | \begin{listinglist} |
| 335 | |#include <catacomb/mpmont.h>| \\ |
| 336 | |mp *mpmont_reduce(mpmont *|$\mm$|, mp *|$d$|, mp *|$x$|);| |
| 337 | \end{listinglist} |
| 338 | |
| 339 | \fsec{Description} |
| 340 | |
| 341 | Performs a Montgomery reduction operation on the integer $x$, modulo $m$. |
| 342 | The integer $d$ is a suggested destination. |
| 343 | |
| 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$. |
| 346 | |
| 347 | This function is particularly efficient if $d = x$, i.e., if you overwrite |
| 348 | $x$ with its Montgomery reduction. |
| 349 | |
| 350 | \fsec{Returns} |
| 351 | |
| 352 | An integer $d$ such that $0 \le d < m$ and $d R \equiv x \pmod m$. |
| 353 | |
| 354 | \subsubsection{The \code{mpmont_mul} function} |
| 355 | \label{fn:mpmont-mul} |
| 356 | |
| 357 | \fsec{Synopsis} |
| 358 | |
| 359 | \begin{listinglist} |
| 360 | |#include <catacomb/mpmont.h>| \\ |
| 361 | |mp *mpmont_mul(mpmont *|$\mm$|, mp *|$d$|, mp *|$x$|, mp *|$y$|);| |
| 362 | \end{listinglist} |
| 363 | |
| 364 | \fsec{Description} |
| 365 | |
| 366 | Multiplies $x$ and $y$, and returns the Montgomery reduction of the product |
| 367 | modulo $m$. The integer $d$ is a suggested destination. |
| 368 | |
| 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$. |
| 371 | |
| 372 | \fsec{Returns} |
| 373 | |
| 374 | An integer $d$ such that $0 \le d < m$ and $d R \equiv x y \bmod m$. |
| 375 | |
| 376 | %%% Local Variables: |
| 377 | %%% mode: latex |
| 378 | %%% TeX-master: "catacomb" |
| 379 | %%% End: |