X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/3471ebd194145da52d419c6315459237b076e18d..3e248c3b5b309bc03eb5f70762d3f5671d51f996:/manual/mp-mp.tex diff --git a/manual/mp-mp.tex b/manual/mp-mp.tex index 4f3aa67..7c40cd7 100644 --- a/manual/mp-mp.tex +++ b/manual/mp-mp.tex @@ -64,8 +64,8 @@ more than once, which can otherwise lead to confusing bugs. \fsec{Returns} -The number of words used in the representation of the integer $m$. Note that -the argument $m$ may be evaluated multiple times by this macro. +The number of words used in the representation of the integer~$m$. Note that +the argument~$m$ may be evaluated multiple times by this macro. \subsubsection{The \code{mp_burn} function} @@ -80,8 +80,8 @@ the argument $m$ may be evaluated multiple times by this macro. \fsec{Description} -Sets the \code{MP_BURN} flag on the integer $m$. Whenever memory associated -with $m$, or results derived from it, is deallocated, it is overwritten with +Sets the \code{MP_BURN} flag on the integer~$m$. Whenever memory associated +with~$m$, or results derived from it, is deallocated, it is overwritten with zeros to prevent traces being found in swap files or core dumps. @@ -98,10 +98,10 @@ are declared in \hdr{}: \multicolumn{1}{c|}{\textbf{Value}} & \qquad & \multicolumn{1}{c|}{\textbf{Constant}} & \multicolumn{1}{c|}{\textbf{Value}} \\ \hlx{vc{1,2,4,5}v} - MP_ZERO & 0 && MP_FOUR & 4 \\ - MP_ONE & 1 && MP_FIVE & 5 \\ - MP_TWO & 2 && MP_TEN & 10 \\ - MP_THREE & 3 && MP_MONE & -1 \\ \hlx{vc{1,2,4,5}} + MP_ZERO & 0 && MP_FOUR & 4 \\ + MP_ONE & 1 && MP_FIVE & 5 \\ + MP_TWO & 2 && MP_TEN & 10 \\ + MP_THREE & 3 && MP_MONE & -1 \\ \hlx{vc{1,2,4,5}} \end{tabular} \goodbreak @@ -176,7 +176,7 @@ A pointer to a newly allocated multiprecision integer. \fsec{Description} -Destroys the multiprecision integer $m$. All resouces allocated to the +Destroys the multiprecision integer~$m$. All resouces allocated to the integer are freed. It's most unusual for this to be the function you want: most of the time \code{mp_drop} (page~\pageref{fn:mp-drop}) is much more useful. @@ -228,9 +228,9 @@ copying any data.\footnote{% \fsec{Description} -The function \code{mp_copy} adds a reference to the multiprecision integer -$m$. The integer will not be destroyed until all references to it have been -dropped. +The function \code{mp_copy} adds a reference to the multiprecision +integer~$m$. The integer will not be destroyed until all references to it +have been dropped. The macro \code{MP_COPY} performs exactly the same action as the \code{mp_copy} function, except that it uses inline code rather than a @@ -239,7 +239,7 @@ function call. It's probably smaller and faster than the function call too. \fsec{Returns} The address of the new reference. This will usually be the same as the -original argument $m$. +original argument~$m$. \subsubsection{The \code{mp_drop} function and \code{MP_DROP} macro} \label{fn:mp-drop} @@ -255,7 +255,7 @@ original argument $m$. \fsec{Description} The function \code{mp_drop} removes (`drops') a reference to the -multiprecision integer $m$. If there are no more references to the integer, +multiprecision integer~$m$. If there are no more references to the integer, it is destroyed, as if by \code{mp_destroy} (page~\pageref{fn:mp-destroy}). The macro \code{MP_DROP} performs exactly the same action as the @@ -275,7 +275,7 @@ function call, so it's slightly faster but uses a little more code. \fsec{Description} -If the integer $m$ has only one reference, the \code{mp_split} function +If the integer~$m$ has only one reference, the \code{mp_split} function returns $m$ unchanged; otherwise, a copy is made and returned, and the reference count of $m$ is decremented. Thus, either way, \code{mp_split} returns a pointer to an integer with the same value as $m$ and a single @@ -284,7 +284,7 @@ refernce. Thus, the result of \code{mp_split} is therefore safe to modify. The macro \code{MP_SPLIT} performs the same action as the \code{mp_split} function except that it uses inline code rather than a function call, and it modifies its argument in place rather than returning the new reference. The -macro \code{MP_SPLIT} may evaluate its argument $m$ multiple times. +macro \code{MP_SPLIT} may evaluate its argument~$m$ multiple times. \fsec{Returns} @@ -310,32 +310,32 @@ The actual behaviour is complicated: \begin{itemize} \item If $m$ is equal to \code{MP_NEW}, or the \code{MP_CONST} flag is set on - $m$, then allocate a new integer $d$ of size $\sz$ by calling + $m$, then allocate a new integer~$d$ of size $\sz$ by calling \code{mp_create} (page~\pageref{fn:mp-create}). \item Otherwise, if $m$ has more than one reference, a reference is removed asif by \code{mp_drop} (page~\pageref{fn:mp-drop}) and a new integer $d$ of size $\sz$ is allocated as if by \code{mp_create}. -\item Otherwise, the integer $m$ is extended to $\sz$ words, as if by calling - \code{mp_ensure} (page~\pageref{fn:mp-ensure}), and $d$ is set equal to - $m$. +\item Otherwise, the integer~$m$ is extended to $\sz$ words, as if by calling + \code{mp_ensure} (page~\pageref{fn:mp-ensure}), and $d$ is set equal + to~$m$. \end{itemize} The resulting integer $d$ is returned from the function. The upshot of all of this is that $d$ has exactly one reference, space for -$\sz$ words of data, and no particular value set. Any other references to -the original integer $m$ (whether counted or not) continue to refer to the -same value. The total number of references to $d$ and $m$ after +$\sz$~words of data, and no particular value set. Any other references to +the original integer~$m$ (whether counted or not) continue to refer to the +same value. The total number of references to $d$ and~$m$ after \code{mp_modify} returns is equal to the initial number of references to $m$ before the call. The macro \code{MP_MODIFY} does the same job using inline code; it sets $m$ -to the new integer $d$ when it's finished. The macro expands to a fairly +to the new integer~$d$ when it's finished. The macro expands to a fairly large chunk of code. \fsec{Returns} -The function \code{mp_modify} returns the destination integer $d$ as +The function \code{mp_modify} returns the destination integer~$d$ as described above. @@ -359,9 +359,9 @@ of a multiprecision integer. \fsec{Description} The function \code{mp_resize} resizes the array used to hold the value of the -integer $m$ such that it has space for $\sz$ words. No check is made to see +integer~$m$ such that it has space for $\sz$ words. No check is made to see whether $m$'s array is already the correct size. The integer's array limit -pointer \code{vl} is set to point $\sz$ words higher than the base pointer +pointer \code{vl} is set to point $\sz$~words higher than the base pointer \code{v}. The macro \code{MP_RESIZE} performs exactly the same action as the @@ -427,7 +427,7 @@ The macro \code{MP_SHRINK} performs exactly the same operation as \fsec{Description} -Minimizes the amount of memory used by the represenation of the integer $m$. +Minimizes the amount of memory used by the represenation of the integer~$m$. This isn't usually useful unless $m$ is going to remain constant for a long time, or has become extremely large for some reason. @@ -444,7 +444,103 @@ time, or has become extremely large for some reason. \subsection{More advanced algorithms} \label{sec:mp-adv} -%%% Local Variables: +\subsubsection{The \code{mp_gcd} function} +\label{fn:mp-gcd} + +\fsec{Synopsis} + +\begin{listinglist} +|#include | \\ +|void mp_gcd(mp **|$g$|, mp **|$a$|, mp **|$b$|, mp *|$x$|, mp *|$y$|);| +\end{listinglist} + +\fsec{Description} + +The function \code{mp_gcd} implements an `extended GCD' algorithm. Given +integers $x$ and~$y$, it computes integers $g$, $a$, and~$b$ such that $g = +\gcd(x, y)$ is the greatest common divisor of $x$ and $y$, and $ax + by = g$. + +If the arguments $g$, $a$ or~$b$ are null pointers, the appropriate result is +discarded; otherwise, the current value of $|*|g$, $|*|a$ or $|*|b$ is used +as a suggested destination for the result, and replaced by the actual result. + +If both $a$ and~$b$ are null, the results $a$ and $b$ are not computed. +Hence \code{mp_gcd} can efficiently perform a simple greatest-common-divisor +computation. + +A major use for \code{mp_gcd} is the calculation of modular inverses. If +$\gcd(x, n) = 1$ then \code{mp_gcd} computes integers $a$ and~$b$ such that +$ax + bn = 1$, i.e., $ax \equiv 1 \pmod n$, so $a$ is the inverse of $x$, +written $a \equiv x^{-1} \pmod n$. + +In order to better support this usage, \code{mp_gcd} implements a \emph{sign +preference} system. If only $a$ is requested, it will either be zero or +have the same sign as~$y$; otherwise, $b$ will be zero or have the same sign +as~$x$. Thus, $x^{-1} \bmod n$ may be conveniently computed using the code +\begin{listing} +mp *xinv = MP_NEW; +mp_gcd(0, 0, &xinv, n, x); +\end{listing} +(It's conventional to ensure that $x > y$, even though it doesn't actually +make any difference.) + +The function \code{mp_gcd} works correctly for all integers $x$ and $y$. The +following properties of the results are guaranteed: +\begin{itemize} + \unverb\| +\item $\gcd(x, y) = \gcd(y, x)$ for all integers $x$ and~$y$. +\item $\gcd(x, 0) = \gcd(0, x) = x$ for all integers~$x$. +\item $|a| < |y|$, unless $y = 0$; similarly, $|b| < |x|$ if $x \ne 0$. +\item If $x = y = 0$, then $a = b = 0$. Otherwise, if $x = 0$, then $a = 0$ + and $b = 1$; similarly, if $y = 0$, then $a = 1$ and $b = 0$. +\end{itemize} + +\subsubsection{The \code{mp_jacobi} function} +\label{fn:mp-jacobi} + +\fsec{Synopsis} + +\begin{listinglist} +|#include | \\ +|int mp_jacobi(mp *|$a$|, mp *|$n$|);| +\end{listinglist} + +\fsec{Returns} + +The value of the Jacobi symbol $\jacobi{a}{n}$.\footnote{% + Schneier writes the Jacobi symbol as $J(a, n)$. The notation + $(\!\frac{a}{n}\!)$ seems more usual.} % +The Jacobi symbol $\jacobi{a}{n}$ is defined for all integers~$a$ and odd +integers~$n$ in terms of the Legendre symbol $\jacobi{a}{p}$ for prime~$p$, +which is: +\[ + \jacobi{a}{p} = \begin{cases} + 0 & if $a$ is a multiple of $p$ \\ + -1 & if $a$ is a quadratic nonresidue mod $p$ \\ + 1 & if $a$ is a quadratic residue mod $p$ + \end{cases} +\] +(An integer $x$ is a quadratic residue mod $n$ if and only if there exists an +integer $y$ such that $y^2 \equiv x \pmod n$. Note that $\jacobi{a}{p} +\equiv a^{(p - 1)/2} \pmod p$.) + +The Jacobi symbol is defined as follows: let $p_0^{e_0} p_1^{e_1} \ldots +p_k^{e_k} = n$ be the prime factors of $n$. Then +\[ + \jacobi{a}{n} = \jacobi{a}{p_0}^{e_0} \jacobi{a}{p_1}^{e_1} \cdots + \jacobi{a}{p_k}^{e_k} +\] +Fortunately, the Jacobi symbol can be computed efficiently without factoring +$n$ or performing modular exponentiations. + +The Jacobi symbol is used in the Solovay-Strassen primality test (not +implemented in Catacomb -- the Rabin-Miller test is better), and in some +subliminal channels in digital signature algorithms. + +The RSA public-key encryption algorithm leaks the Jacobi symbol of its +plaintext. + +%%% Local Variables: %%% mode: latex %%% TeX-master: "catacomb" -%%% End: +%%% End: