|
19
|
1 \documentclass[b5paper]{book} |
|
|
2 \usepackage{hyperref} |
|
|
3 \usepackage{makeidx} |
|
|
4 \usepackage{amssymb} |
|
|
5 \usepackage{color} |
|
|
6 \usepackage{alltt} |
|
|
7 \usepackage{graphicx} |
|
|
8 \usepackage{layout} |
|
|
9 \def\union{\cup} |
|
|
10 \def\intersect{\cap} |
|
|
11 \def\getsrandom{\stackrel{\rm R}{\gets}} |
|
|
12 \def\cross{\times} |
|
|
13 \def\cat{\hspace{0.5em} \| \hspace{0.5em}} |
|
|
14 \def\catn{$\|$} |
|
|
15 \def\divides{\hspace{0.3em} | \hspace{0.3em}} |
|
|
16 \def\nequiv{\not\equiv} |
|
|
17 \def\approx{\raisebox{0.2ex}{\mbox{\small $\sim$}}} |
|
|
18 \def\lcm{{\rm lcm}} |
|
|
19 \def\gcd{{\rm gcd}} |
|
|
20 \def\log{{\rm log}} |
|
|
21 \def\ord{{\rm ord}} |
|
|
22 \def\abs{{\mathit abs}} |
|
|
23 \def\rep{{\mathit rep}} |
|
|
24 \def\mod{{\mathit\ mod\ }} |
|
|
25 \renewcommand{\pmod}[1]{\ ({\rm mod\ }{#1})} |
|
|
26 \newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor} |
|
|
27 \newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil} |
|
|
28 \def\Or{{\rm\ or\ }} |
|
|
29 \def\And{{\rm\ and\ }} |
|
|
30 \def\iff{\hspace{1em}\Longleftrightarrow\hspace{1em}} |
|
|
31 \def\implies{\Rightarrow} |
|
|
32 \def\undefined{{\rm ``undefined"}} |
|
|
33 \def\Proof{\vspace{1ex}\noindent {\bf Proof:}\hspace{1em}} |
|
|
34 \let\oldphi\phi |
|
|
35 \def\phi{\varphi} |
|
|
36 \def\Pr{{\rm Pr}} |
|
|
37 \newcommand{\str}[1]{{\mathbf{#1}}} |
|
|
38 \def\F{{\mathbb F}} |
|
|
39 \def\N{{\mathbb N}} |
|
|
40 \def\Z{{\mathbb Z}} |
|
|
41 \def\R{{\mathbb R}} |
|
|
42 \def\C{{\mathbb C}} |
|
|
43 \def\Q{{\mathbb Q}} |
|
|
44 \definecolor{DGray}{gray}{0.5} |
|
|
45 \newcommand{\emailaddr}[1]{\mbox{$<${#1}$>$}} |
|
|
46 \def\twiddle{\raisebox{0.3ex}{\mbox{\tiny $\sim$}}} |
|
|
47 \def\gap{\vspace{0.5ex}} |
|
|
48 \makeindex |
|
|
49 \begin{document} |
|
|
50 \frontmatter |
|
|
51 \pagestyle{empty} |
|
142
|
52 \title{LibTomMath User Manual \\ v0.32} |
|
19
|
53 \author{Tom St Denis \\ [email protected]} |
|
|
54 \maketitle |
|
|
55 This text, the library and the accompanying textbook are all hereby placed in the public domain. This book has been |
|
|
56 formatted for B5 [176x250] paper using the \LaTeX{} {\em book} macro package. |
|
|
57 |
|
|
58 \vspace{10cm} |
|
|
59 |
|
|
60 \begin{flushright}Open Source. Open Academia. Open Minds. |
|
|
61 |
|
|
62 \mbox{ } |
|
|
63 |
|
|
64 Tom St Denis, |
|
|
65 |
|
|
66 Ontario, Canada |
|
|
67 \end{flushright} |
|
|
68 |
|
|
69 \tableofcontents |
|
|
70 \listoffigures |
|
|
71 \mainmatter |
|
|
72 \pagestyle{headings} |
|
|
73 \chapter{Introduction} |
|
|
74 \section{What is LibTomMath?} |
|
|
75 LibTomMath is a library of source code which provides a series of efficient and carefully written functions for manipulating |
|
|
76 large integer numbers. It was written in portable ISO C source code so that it will build on any platform with a conforming |
|
|
77 C compiler. |
|
|
78 |
|
|
79 In a nutshell the library was written from scratch with verbose comments to help instruct computer science students how |
|
|
80 to implement ``bignum'' math. However, the resulting code has proven to be very useful. It has been used by numerous |
|
|
81 universities, commercial and open source software developers. It has been used on a variety of platforms ranging from |
|
|
82 Linux and Windows based x86 to ARM based Gameboys and PPC based MacOS machines. |
|
|
83 |
|
|
84 \section{License} |
|
|
85 As of the v0.25 the library source code has been placed in the public domain with every new release. As of the v0.28 |
|
|
86 release the textbook ``Implementing Multiple Precision Arithmetic'' has been placed in the public domain with every new |
|
|
87 release as well. This textbook is meant to compliment the project by providing a more solid walkthrough of the development |
|
|
88 algorithms used in the library. |
|
|
89 |
|
|
90 Since both\footnote{Note that the MPI files under mtest/ are copyrighted by Michael Fromberger. They are not required to use LibTomMath.} are in the |
|
|
91 public domain everyone is entitled to do with them as they see fit. |
|
|
92 |
|
|
93 \section{Building LibTomMath} |
|
|
94 |
|
|
95 LibTomMath is meant to be very ``GCC friendly'' as it comes with a makefile well suited for GCC. However, the library will |
|
|
96 also build in MSVC, Borland C out of the box. For any other ISO C compiler a makefile will have to be made by the end |
|
|
97 developer. |
|
|
98 |
|
142
|
99 \subsection{Static Libraries} |
|
|
100 To build as a static library for GCC issue the following |
|
19
|
101 \begin{alltt} |
|
|
102 make |
|
|
103 \end{alltt} |
|
|
104 |
|
142
|
105 command. This will build the library and archive the object files in ``libtommath.a''. Now you link against |
|
|
106 that and include ``tommath.h'' within your programs. Alternatively to build with MSVC issue the following |
|
19
|
107 \begin{alltt} |
|
|
108 nmake -f makefile.msvc |
|
|
109 \end{alltt} |
|
|
110 |
|
142
|
111 This will build the library and archive the object files in ``tommath.lib''. This has been tested with MSVC |
|
|
112 version 6.00 with service pack 5. |
|
19
|
113 |
|
142
|
114 \subsection{Shared Libraries} |
|
|
115 To build as a shared library for GCC issue the following |
|
|
116 \begin{alltt} |
|
|
117 make -f makefile.shared |
|
|
118 \end{alltt} |
|
|
119 This requires the ``libtool'' package (common on most Linux/BSD systems). It will build LibTomMath as both shared |
|
|
120 and static then install (by default) into /usr/lib as well as install the header files in /usr/include. The shared |
|
|
121 library (resource) will be called ``libtommath.la'' while the static library called ``libtommath.a''. Generally |
|
|
122 you use libtool to link your application against the shared object. |
|
|
123 |
|
|
124 There is limited support for making a ``DLL'' in windows via the ``makefile.cygwin\_dll'' makefile. It requires |
|
|
125 Cygwin to work with since it requires the auto-export/import functionality. The resulting DLL and import library |
|
|
126 ``libtommath.dll.a'' can be used to link LibTomMath dynamically to any Windows program using Cygwin. |
|
19
|
127 |
|
|
128 \subsection{Testing} |
|
|
129 To build the library and the test harness type |
|
|
130 |
|
|
131 \begin{alltt} |
|
|
132 make test |
|
|
133 \end{alltt} |
|
|
134 |
|
|
135 This will build the library, ``test'' and ``mtest/mtest''. The ``test'' program will accept test vectors and verify the |
|
|
136 results. ``mtest/mtest'' will generate test vectors using the MPI library by Michael Fromberger\footnote{A copy of MPI |
|
|
137 is included in the package}. Simply pipe mtest into test using |
|
|
138 |
|
|
139 \begin{alltt} |
|
|
140 mtest/mtest | test |
|
|
141 \end{alltt} |
|
|
142 |
|
|
143 If you do not have a ``/dev/urandom'' style RNG source you will have to write your own PRNG and simply pipe that into |
|
|
144 mtest. For example, if your PRNG program is called ``myprng'' simply invoke |
|
|
145 |
|
|
146 \begin{alltt} |
|
|
147 myprng | mtest/mtest | test |
|
|
148 \end{alltt} |
|
|
149 |
|
|
150 This will output a row of numbers that are increasing. Each column is a different test (such as addition, multiplication, etc) |
|
|
151 that is being performed. The numbers represent how many times the test was invoked. If an error is detected the program |
|
|
152 will exit with a dump of the relevent numbers it was working with. |
|
|
153 |
|
142
|
154 \section{Build Configuration} |
|
|
155 LibTomMath can configured at build time in three phases we shall call ``depends'', ``tweaks'' and ``trims''. |
|
|
156 Each phase changes how the library is built and they are applied one after another respectively. |
|
|
157 |
|
|
158 To make the system more powerful you can tweak the build process. Classes are defined in the file |
|
|
159 ``tommath\_superclass.h''. By default, the symbol ``LTM\_ALL'' shall be defined which simply |
|
|
160 instructs the system to build all of the functions. This is how LibTomMath used to be packaged. This will give you |
|
|
161 access to every function LibTomMath offers. |
|
|
162 |
|
|
163 However, there are cases where such a build is not optional. For instance, you want to perform RSA operations. You |
|
|
164 don't need the vast majority of the library to perform these operations. Aside from LTM\_ALL there is |
|
|
165 another pre--defined class ``SC\_RSA\_1'' which works in conjunction with the RSA from LibTomCrypt. Additional |
|
|
166 classes can be defined base on the need of the user. |
|
|
167 |
|
|
168 \subsection{Build Depends} |
|
|
169 In the file tommath\_class.h you will see a large list of C ``defines'' followed by a series of ``ifdefs'' |
|
|
170 which further define symbols. All of the symbols (technically they're macros $\ldots$) represent a given C source |
|
|
171 file. For instance, BN\_MP\_ADD\_C represents the file ``bn\_mp\_add.c''. When a define has been enabled the |
|
|
172 function in the respective file will be compiled and linked into the library. Accordingly when the define |
|
|
173 is absent the file will not be compiled and not contribute any size to the library. |
|
|
174 |
|
|
175 You will also note that the header tommath\_class.h is actually recursively included (it includes itself twice). |
|
|
176 This is to help resolve as many dependencies as possible. In the last pass the symbol LTM\_LAST will be defined. |
|
|
177 This is useful for ``trims''. |
|
|
178 |
|
|
179 \subsection{Build Tweaks} |
|
|
180 A tweak is an algorithm ``alternative''. For example, to provide tradeoffs (usually between size and space). |
|
|
181 They can be enabled at any pass of the configuration phase. |
|
|
182 |
|
|
183 \begin{small} |
|
|
184 \begin{center} |
|
|
185 \begin{tabular}{|l|l|} |
|
|
186 \hline \textbf{Define} & \textbf{Purpose} \\ |
|
|
187 \hline BN\_MP\_DIV\_SMALL & Enables a slower, smaller and equally \\ |
|
|
188 & functional mp\_div() function \\ |
|
|
189 \hline |
|
|
190 \end{tabular} |
|
|
191 \end{center} |
|
|
192 \end{small} |
|
|
193 |
|
|
194 \subsection{Build Trims} |
|
|
195 A trim is a manner of removing functionality from a function that is not required. For instance, to perform |
|
|
196 RSA cryptography you only require exponentiation with odd moduli so even moduli support can be safely removed. |
|
|
197 Build trims are meant to be defined on the last pass of the configuration which means they are to be defined |
|
|
198 only if LTM\_LAST has been defined. |
|
|
199 |
|
|
200 \subsubsection{Moduli Related} |
|
|
201 \begin{small} |
|
|
202 \begin{center} |
|
|
203 \begin{tabular}{|l|l|} |
|
|
204 \hline \textbf{Restriction} & \textbf{Undefine} \\ |
|
|
205 \hline Exponentiation with odd moduli only & BN\_S\_MP\_EXPTMOD\_C \\ |
|
|
206 & BN\_MP\_REDUCE\_C \\ |
|
|
207 & BN\_MP\_REDUCE\_SETUP\_C \\ |
|
|
208 & BN\_S\_MP\_MUL\_HIGH\_DIGS\_C \\ |
|
|
209 & BN\_FAST\_S\_MP\_MUL\_HIGH\_DIGS\_C \\ |
|
|
210 \hline Exponentiation with random odd moduli & (The above plus the following) \\ |
|
|
211 & BN\_MP\_REDUCE\_2K\_C \\ |
|
|
212 & BN\_MP\_REDUCE\_2K\_SETUP\_C \\ |
|
|
213 & BN\_MP\_REDUCE\_IS\_2K\_C \\ |
|
|
214 & BN\_MP\_DR\_IS\_MODULUS\_C \\ |
|
|
215 & BN\_MP\_DR\_REDUCE\_C \\ |
|
|
216 & BN\_MP\_DR\_SETUP\_C \\ |
|
|
217 \hline Modular inverse odd moduli only & BN\_MP\_INVMOD\_SLOW\_C \\ |
|
|
218 \hline Modular inverse (both, smaller/slower) & BN\_FAST\_MP\_INVMOD\_C \\ |
|
|
219 \hline |
|
|
220 \end{tabular} |
|
|
221 \end{center} |
|
|
222 \end{small} |
|
|
223 |
|
|
224 \subsubsection{Operand Size Related} |
|
|
225 \begin{small} |
|
|
226 \begin{center} |
|
|
227 \begin{tabular}{|l|l|} |
|
|
228 \hline \textbf{Restriction} & \textbf{Undefine} \\ |
|
|
229 \hline Moduli $\le 2560$ bits & BN\_MP\_MONTGOMERY\_REDUCE\_C \\ |
|
|
230 & BN\_S\_MP\_MUL\_DIGS\_C \\ |
|
|
231 & BN\_S\_MP\_MUL\_HIGH\_DIGS\_C \\ |
|
|
232 & BN\_S\_MP\_SQR\_C \\ |
|
|
233 \hline Polynomial Schmolynomial & BN\_MP\_KARATSUBA\_MUL\_C \\ |
|
|
234 & BN\_MP\_KARATSUBA\_SQR\_C \\ |
|
|
235 & BN\_MP\_TOOM\_MUL\_C \\ |
|
|
236 & BN\_MP\_TOOM\_SQR\_C \\ |
|
|
237 |
|
|
238 \hline |
|
|
239 \end{tabular} |
|
|
240 \end{center} |
|
|
241 \end{small} |
|
|
242 |
|
|
243 |
|
19
|
244 \section{Purpose of LibTomMath} |
|
|
245 Unlike GNU MP (GMP) Library, LIP, OpenSSL or various other commercial kits (Miracl), LibTomMath was not written with |
|
|
246 bleeding edge performance in mind. First and foremost LibTomMath was written to be entirely open. Not only is the |
|
|
247 source code public domain (unlike various other GPL/etc licensed code), not only is the code freely downloadable but the |
|
|
248 source code is also accessible for computer science students attempting to learn ``BigNum'' or multiple precision |
|
|
249 arithmetic techniques. |
|
|
250 |
|
|
251 LibTomMath was written to be an instructive collection of source code. This is why there are many comments, only one |
|
|
252 function per source file and often I use a ``middle-road'' approach where I don't cut corners for an extra 2\% speed |
|
|
253 increase. |
|
|
254 |
|
|
255 Source code alone cannot really teach how the algorithms work which is why I also wrote a textbook that accompanies |
|
|
256 the library (beat that!). |
|
|
257 |
|
|
258 So you may be thinking ``should I use LibTomMath?'' and the answer is a definite maybe. Let me tabulate what I think |
|
|
259 are the pros and cons of LibTomMath by comparing it to the math routines from GnuPG\footnote{GnuPG v1.2.3 versus LibTomMath v0.28}. |
|
|
260 |
|
|
261 \newpage\begin{figure}[here] |
|
|
262 \begin{small} |
|
|
263 \begin{center} |
|
|
264 \begin{tabular}{|l|c|c|l|} |
|
|
265 \hline \textbf{Criteria} & \textbf{Pro} & \textbf{Con} & \textbf{Notes} \\ |
|
|
266 \hline Few lines of code per file & X & & GnuPG $ = 300.9$, LibTomMath $ = 76.04$ \\ |
|
|
267 \hline Commented function prototypes & X && GnuPG function names are cryptic. \\ |
|
|
268 \hline Speed && X & LibTomMath is slower. \\ |
|
|
269 \hline Totally free & X & & GPL has unfavourable restrictions.\\ |
|
|
270 \hline Large function base & X & & GnuPG is barebones. \\ |
|
|
271 \hline Four modular reduction algorithms & X & & Faster modular exponentiation. \\ |
|
|
272 \hline Portable & X & & GnuPG requires configuration to build. \\ |
|
|
273 \hline |
|
|
274 \end{tabular} |
|
|
275 \end{center} |
|
|
276 \end{small} |
|
|
277 \caption{LibTomMath Valuation} |
|
|
278 \end{figure} |
|
|
279 |
|
|
280 It may seem odd to compare LibTomMath to GnuPG since the math in GnuPG is only a small portion of the entire application. |
|
|
281 However, LibTomMath was written with cryptography in mind. It provides essentially all of the functions a cryptosystem |
|
|
282 would require when working with large integers. |
|
|
283 |
|
|
284 So it may feel tempting to just rip the math code out of GnuPG (or GnuMP where it was taken from originally) in your |
|
|
285 own application but I think there are reasons not to. While LibTomMath is slower than libraries such as GnuMP it is |
|
|
286 not normally significantly slower. On x86 machines the difference is normally a factor of two when performing modular |
|
|
287 exponentiations. |
|
|
288 |
|
|
289 Essentially the only time you wouldn't use LibTomMath is when blazing speed is the primary concern. |
|
|
290 |
|
|
291 \chapter{Getting Started with LibTomMath} |
|
|
292 \section{Building Programs} |
|
|
293 In order to use LibTomMath you must include ``tommath.h'' and link against the appropriate library file (typically |
|
|
294 libtommath.a). There is no library initialization required and the entire library is thread safe. |
|
|
295 |
|
|
296 \section{Return Codes} |
|
|
297 There are three possible return codes a function may return. |
|
|
298 |
|
|
299 \index{MP\_OKAY}\index{MP\_YES}\index{MP\_NO}\index{MP\_VAL}\index{MP\_MEM} |
|
|
300 \begin{figure}[here!] |
|
|
301 \begin{center} |
|
|
302 \begin{small} |
|
|
303 \begin{tabular}{|l|l|} |
|
|
304 \hline \textbf{Code} & \textbf{Meaning} \\ |
|
|
305 \hline MP\_OKAY & The function succeeded. \\ |
|
|
306 \hline MP\_VAL & The function input was invalid. \\ |
|
|
307 \hline MP\_MEM & Heap memory exhausted. \\ |
|
|
308 \hline &\\ |
|
|
309 \hline MP\_YES & Response is yes. \\ |
|
|
310 \hline MP\_NO & Response is no. \\ |
|
|
311 \hline |
|
|
312 \end{tabular} |
|
|
313 \end{small} |
|
|
314 \end{center} |
|
|
315 \caption{Return Codes} |
|
|
316 \end{figure} |
|
|
317 |
|
|
318 The last two codes listed are not actually ``return'ed'' by a function. They are placed in an integer (the caller must |
|
|
319 provide the address of an integer it can store to) which the caller can access. To convert one of the three return codes |
|
|
320 to a string use the following function. |
|
|
321 |
|
|
322 \index{mp\_error\_to\_string} |
|
|
323 \begin{alltt} |
|
|
324 char *mp_error_to_string(int code); |
|
|
325 \end{alltt} |
|
|
326 |
|
|
327 This will return a pointer to a string which describes the given error code. It will not work for the return codes |
|
|
328 MP\_YES and MP\_NO. |
|
|
329 |
|
|
330 \section{Data Types} |
|
|
331 The basic ``multiple precision integer'' type is known as the ``mp\_int'' within LibTomMath. This data type is used to |
|
|
332 organize all of the data required to manipulate the integer it represents. Within LibTomMath it has been prototyped |
|
|
333 as the following. |
|
|
334 |
|
|
335 \index{mp\_int} |
|
|
336 \begin{alltt} |
|
|
337 typedef struct \{ |
|
|
338 int used, alloc, sign; |
|
|
339 mp_digit *dp; |
|
|
340 \} mp_int; |
|
|
341 \end{alltt} |
|
|
342 |
|
|
343 Where ``mp\_digit'' is a data type that represents individual digits of the integer. By default, an mp\_digit is the |
|
|
344 ISO C ``unsigned long'' data type and each digit is $28-$bits long. The mp\_digit type can be configured to suit other |
|
|
345 platforms by defining the appropriate macros. |
|
|
346 |
|
|
347 All LTM functions that use the mp\_int type will expect a pointer to mp\_int structure. You must allocate memory to |
|
|
348 hold the structure itself by yourself (whether off stack or heap it doesn't matter). The very first thing that must be |
|
|
349 done to use an mp\_int is that it must be initialized. |
|
|
350 |
|
|
351 \section{Function Organization} |
|
|
352 |
|
|
353 The arithmetic functions of the library are all organized to have the same style prototype. That is source operands |
|
|
354 are passed on the left and the destination is on the right. For instance, |
|
|
355 |
|
|
356 \begin{alltt} |
|
|
357 mp_add(&a, &b, &c); /* c = a + b */ |
|
|
358 mp_mul(&a, &a, &c); /* c = a * a */ |
|
|
359 mp_div(&a, &b, &c, &d); /* c = [a/b], d = a mod b */ |
|
|
360 \end{alltt} |
|
|
361 |
|
|
362 Another feature of the way the functions have been implemented is that source operands can be destination operands as well. |
|
|
363 For instance, |
|
|
364 |
|
|
365 \begin{alltt} |
|
|
366 mp_add(&a, &b, &b); /* b = a + b */ |
|
|
367 mp_div(&a, &b, &a, &c); /* a = [a/b], c = a mod b */ |
|
|
368 \end{alltt} |
|
|
369 |
|
|
370 This allows operands to be re-used which can make programming simpler. |
|
|
371 |
|
|
372 \section{Initialization} |
|
|
373 \subsection{Single Initialization} |
|
|
374 A single mp\_int can be initialized with the ``mp\_init'' function. |
|
|
375 |
|
|
376 \index{mp\_init} |
|
|
377 \begin{alltt} |
|
|
378 int mp_init (mp_int * a); |
|
|
379 \end{alltt} |
|
|
380 |
|
|
381 This function expects a pointer to an mp\_int structure and will initialize the members of the structure so the mp\_int |
|
|
382 represents the default integer which is zero. If the functions returns MP\_OKAY then the mp\_int is ready to be used |
|
|
383 by the other LibTomMath functions. |
|
|
384 |
|
|
385 \begin{small} \begin{alltt} |
|
|
386 int main(void) |
|
|
387 \{ |
|
|
388 mp_int number; |
|
|
389 int result; |
|
|
390 |
|
|
391 if ((result = mp_init(&number)) != MP_OKAY) \{ |
|
|
392 printf("Error initializing the number. \%s", |
|
|
393 mp_error_to_string(result)); |
|
|
394 return EXIT_FAILURE; |
|
|
395 \} |
|
|
396 |
|
|
397 /* use the number */ |
|
|
398 |
|
|
399 return EXIT_SUCCESS; |
|
|
400 \} |
|
|
401 \end{alltt} \end{small} |
|
|
402 |
|
|
403 \subsection{Single Free} |
|
|
404 When you are finished with an mp\_int it is ideal to return the heap it used back to the system. The following function |
|
|
405 provides this functionality. |
|
|
406 |
|
|
407 \index{mp\_clear} |
|
|
408 \begin{alltt} |
|
|
409 void mp_clear (mp_int * a); |
|
|
410 \end{alltt} |
|
|
411 |
|
|
412 The function expects a pointer to a previously initialized mp\_int structure and frees the heap it uses. It sets the |
|
|
413 pointer\footnote{The ``dp'' member.} within the mp\_int to \textbf{NULL} which is used to prevent double free situations. |
|
|
414 Is is legal to call mp\_clear() twice on the same mp\_int in a row. |
|
|
415 |
|
|
416 \begin{small} \begin{alltt} |
|
|
417 int main(void) |
|
|
418 \{ |
|
|
419 mp_int number; |
|
|
420 int result; |
|
|
421 |
|
|
422 if ((result = mp_init(&number)) != MP_OKAY) \{ |
|
|
423 printf("Error initializing the number. \%s", |
|
|
424 mp_error_to_string(result)); |
|
|
425 return EXIT_FAILURE; |
|
|
426 \} |
|
|
427 |
|
|
428 /* use the number */ |
|
|
429 |
|
|
430 /* We're done with it. */ |
|
|
431 mp_clear(&number); |
|
|
432 |
|
|
433 return EXIT_SUCCESS; |
|
|
434 \} |
|
|
435 \end{alltt} \end{small} |
|
|
436 |
|
|
437 \subsection{Multiple Initializations} |
|
|
438 Certain algorithms require more than one large integer. In these instances it is ideal to initialize all of the mp\_int |
|
|
439 variables in an ``all or nothing'' fashion. That is, they are either all initialized successfully or they are all |
|
|
440 not initialized. |
|
|
441 |
|
|
442 The mp\_init\_multi() function provides this functionality. |
|
|
443 |
|
|
444 \index{mp\_init\_multi} \index{mp\_clear\_multi} |
|
|
445 \begin{alltt} |
|
|
446 int mp_init_multi(mp_int *mp, ...); |
|
|
447 \end{alltt} |
|
|
448 |
|
|
449 It accepts a \textbf{NULL} terminated list of pointers to mp\_int structures. It will attempt to initialize them all |
|
|
450 at once. If the function returns MP\_OKAY then all of the mp\_int variables are ready to use, otherwise none of them |
|
|
451 are available for use. A complementary mp\_clear\_multi() function allows multiple mp\_int variables to be free'd |
|
|
452 from the heap at the same time. |
|
|
453 |
|
|
454 \begin{small} \begin{alltt} |
|
|
455 int main(void) |
|
|
456 \{ |
|
|
457 mp_int num1, num2, num3; |
|
|
458 int result; |
|
|
459 |
|
|
460 if ((result = mp_init_multi(&num1, |
|
|
461 &num2, |
|
|
462 &num3, NULL)) != MP\_OKAY) \{ |
|
|
463 printf("Error initializing the numbers. \%s", |
|
|
464 mp_error_to_string(result)); |
|
|
465 return EXIT_FAILURE; |
|
|
466 \} |
|
|
467 |
|
|
468 /* use the numbers */ |
|
|
469 |
|
|
470 /* We're done with them. */ |
|
|
471 mp_clear_multi(&num1, &num2, &num3, NULL); |
|
|
472 |
|
|
473 return EXIT_SUCCESS; |
|
|
474 \} |
|
|
475 \end{alltt} \end{small} |
|
|
476 |
|
|
477 \subsection{Other Initializers} |
|
|
478 To initialized and make a copy of an mp\_int the mp\_init\_copy() function has been provided. |
|
|
479 |
|
|
480 \index{mp\_init\_copy} |
|
|
481 \begin{alltt} |
|
|
482 int mp_init_copy (mp_int * a, mp_int * b); |
|
|
483 \end{alltt} |
|
|
484 |
|
|
485 This function will initialize $a$ and make it a copy of $b$ if all goes well. |
|
|
486 |
|
|
487 \begin{small} \begin{alltt} |
|
|
488 int main(void) |
|
|
489 \{ |
|
|
490 mp_int num1, num2; |
|
|
491 int result; |
|
|
492 |
|
|
493 /* initialize and do work on num1 ... */ |
|
|
494 |
|
|
495 /* We want a copy of num1 in num2 now */ |
|
|
496 if ((result = mp_init_copy(&num2, &num1)) != MP_OKAY) \{ |
|
|
497 printf("Error initializing the copy. \%s", |
|
|
498 mp_error_to_string(result)); |
|
|
499 return EXIT_FAILURE; |
|
|
500 \} |
|
|
501 |
|
|
502 /* now num2 is ready and contains a copy of num1 */ |
|
|
503 |
|
|
504 /* We're done with them. */ |
|
|
505 mp_clear_multi(&num1, &num2, NULL); |
|
|
506 |
|
|
507 return EXIT_SUCCESS; |
|
|
508 \} |
|
|
509 \end{alltt} \end{small} |
|
|
510 |
|
|
511 Another less common initializer is mp\_init\_size() which allows the user to initialize an mp\_int with a given |
|
|
512 default number of digits. By default, all initializers allocate \textbf{MP\_PREC} digits. This function lets |
|
|
513 you override this behaviour. |
|
|
514 |
|
|
515 \index{mp\_init\_size} |
|
|
516 \begin{alltt} |
|
|
517 int mp_init_size (mp_int * a, int size); |
|
|
518 \end{alltt} |
|
|
519 |
|
|
520 The $size$ parameter must be greater than zero. If the function succeeds the mp\_int $a$ will be initialized |
|
|
521 to have $size$ digits (which are all initially zero). |
|
|
522 |
|
|
523 \begin{small} \begin{alltt} |
|
|
524 int main(void) |
|
|
525 \{ |
|
|
526 mp_int number; |
|
|
527 int result; |
|
|
528 |
|
|
529 /* we need a 60-digit number */ |
|
|
530 if ((result = mp_init_size(&number, 60)) != MP_OKAY) \{ |
|
|
531 printf("Error initializing the number. \%s", |
|
|
532 mp_error_to_string(result)); |
|
|
533 return EXIT_FAILURE; |
|
|
534 \} |
|
|
535 |
|
|
536 /* use the number */ |
|
|
537 |
|
|
538 return EXIT_SUCCESS; |
|
|
539 \} |
|
|
540 \end{alltt} \end{small} |
|
|
541 |
|
|
542 \section{Maintenance Functions} |
|
|
543 |
|
|
544 \subsection{Reducing Memory Usage} |
|
|
545 When an mp\_int is in a state where it won't be changed again\footnote{A Diffie-Hellman modulus for instance.} excess |
|
|
546 digits can be removed to return memory to the heap with the mp\_shrink() function. |
|
|
547 |
|
|
548 \index{mp\_shrink} |
|
|
549 \begin{alltt} |
|
|
550 int mp_shrink (mp_int * a); |
|
|
551 \end{alltt} |
|
|
552 |
|
|
553 This will remove excess digits of the mp\_int $a$. If the operation fails the mp\_int should be intact without the |
|
|
554 excess digits being removed. Note that you can use a shrunk mp\_int in further computations, however, such operations |
|
|
555 will require heap operations which can be slow. It is not ideal to shrink mp\_int variables that you will further |
|
|
556 modify in the system (unless you are seriously low on memory). |
|
|
557 |
|
|
558 \begin{small} \begin{alltt} |
|
|
559 int main(void) |
|
|
560 \{ |
|
|
561 mp_int number; |
|
|
562 int result; |
|
|
563 |
|
|
564 if ((result = mp_init(&number)) != MP_OKAY) \{ |
|
|
565 printf("Error initializing the number. \%s", |
|
|
566 mp_error_to_string(result)); |
|
|
567 return EXIT_FAILURE; |
|
|
568 \} |
|
|
569 |
|
|
570 /* use the number [e.g. pre-computation] */ |
|
|
571 |
|
|
572 /* We're done with it for now. */ |
|
|
573 if ((result = mp_shrink(&number)) != MP_OKAY) \{ |
|
|
574 printf("Error shrinking the number. \%s", |
|
|
575 mp_error_to_string(result)); |
|
|
576 return EXIT_FAILURE; |
|
|
577 \} |
|
|
578 |
|
|
579 /* use it .... */ |
|
|
580 |
|
|
581 |
|
|
582 /* we're done with it. */ |
|
|
583 mp_clear(&number); |
|
|
584 |
|
|
585 return EXIT_SUCCESS; |
|
|
586 \} |
|
|
587 \end{alltt} \end{small} |
|
|
588 |
|
|
589 \subsection{Adding additional digits} |
|
|
590 |
|
|
591 Within the mp\_int structure are two parameters which control the limitations of the array of digits that represent |
|
|
592 the integer the mp\_int is meant to equal. The \textit{used} parameter dictates how many digits are significant, that is, |
|
|
593 contribute to the value of the mp\_int. The \textit{alloc} parameter dictates how many digits are currently available in |
|
|
594 the array. If you need to perform an operation that requires more digits you will have to mp\_grow() the mp\_int to |
|
|
595 your desired size. |
|
|
596 |
|
|
597 \index{mp\_grow} |
|
|
598 \begin{alltt} |
|
|
599 int mp_grow (mp_int * a, int size); |
|
|
600 \end{alltt} |
|
|
601 |
|
|
602 This will grow the array of digits of $a$ to $size$. If the \textit{alloc} parameter is already bigger than |
|
|
603 $size$ the function will not do anything. |
|
|
604 |
|
|
605 \begin{small} \begin{alltt} |
|
|
606 int main(void) |
|
|
607 \{ |
|
|
608 mp_int number; |
|
|
609 int result; |
|
|
610 |
|
|
611 if ((result = mp_init(&number)) != MP_OKAY) \{ |
|
|
612 printf("Error initializing the number. \%s", |
|
|
613 mp_error_to_string(result)); |
|
|
614 return EXIT_FAILURE; |
|
|
615 \} |
|
|
616 |
|
|
617 /* use the number */ |
|
|
618 |
|
|
619 /* We need to add 20 digits to the number */ |
|
|
620 if ((result = mp_grow(&number, number.alloc + 20)) != MP_OKAY) \{ |
|
|
621 printf("Error growing the number. \%s", |
|
|
622 mp_error_to_string(result)); |
|
|
623 return EXIT_FAILURE; |
|
|
624 \} |
|
|
625 |
|
|
626 |
|
|
627 /* use the number */ |
|
|
628 |
|
|
629 /* we're done with it. */ |
|
|
630 mp_clear(&number); |
|
|
631 |
|
|
632 return EXIT_SUCCESS; |
|
|
633 \} |
|
|
634 \end{alltt} \end{small} |
|
|
635 |
|
|
636 \chapter{Basic Operations} |
|
|
637 \section{Small Constants} |
|
|
638 Setting mp\_ints to small constants is a relatively common operation. To accomodate these instances there are two |
|
|
639 small constant assignment functions. The first function is used to set a single digit constant while the second sets |
|
|
640 an ISO C style ``unsigned long'' constant. The reason for both functions is efficiency. Setting a single digit is quick but the |
|
|
641 domain of a digit can change (it's always at least $0 \ldots 127$). |
|
|
642 |
|
|
643 \subsection{Single Digit} |
|
|
644 |
|
|
645 Setting a single digit can be accomplished with the following function. |
|
|
646 |
|
|
647 \index{mp\_set} |
|
|
648 \begin{alltt} |
|
|
649 void mp_set (mp_int * a, mp_digit b); |
|
|
650 \end{alltt} |
|
|
651 |
|
|
652 This will zero the contents of $a$ and make it represent an integer equal to the value of $b$. Note that this |
|
|
653 function has a return type of \textbf{void}. It cannot cause an error so it is safe to assume the function |
|
|
654 succeeded. |
|
|
655 |
|
|
656 \begin{small} \begin{alltt} |
|
|
657 int main(void) |
|
|
658 \{ |
|
|
659 mp_int number; |
|
|
660 int result; |
|
|
661 |
|
|
662 if ((result = mp_init(&number)) != MP_OKAY) \{ |
|
|
663 printf("Error initializing the number. \%s", |
|
|
664 mp_error_to_string(result)); |
|
|
665 return EXIT_FAILURE; |
|
|
666 \} |
|
|
667 |
|
|
668 /* set the number to 5 */ |
|
|
669 mp_set(&number, 5); |
|
|
670 |
|
|
671 /* we're done with it. */ |
|
|
672 mp_clear(&number); |
|
|
673 |
|
|
674 return EXIT_SUCCESS; |
|
|
675 \} |
|
|
676 \end{alltt} \end{small} |
|
|
677 |
|
|
678 \subsection{Long Constants} |
|
|
679 |
|
|
680 To set a constant that is the size of an ISO C ``unsigned long'' and larger than a single digit the following function |
|
|
681 can be used. |
|
|
682 |
|
|
683 \index{mp\_set\_int} |
|
|
684 \begin{alltt} |
|
|
685 int mp_set_int (mp_int * a, unsigned long b); |
|
|
686 \end{alltt} |
|
|
687 |
|
|
688 This will assign the value of the 32-bit variable $b$ to the mp\_int $a$. Unlike mp\_set() this function will always |
|
|
689 accept a 32-bit input regardless of the size of a single digit. However, since the value may span several digits |
|
|
690 this function can fail if it runs out of heap memory. |
|
|
691 |
|
|
692 To get the ``unsigned long'' copy of an mp\_int the following function can be used. |
|
|
693 |
|
|
694 \index{mp\_get\_int} |
|
|
695 \begin{alltt} |
|
|
696 unsigned long mp_get_int (mp_int * a); |
|
|
697 \end{alltt} |
|
|
698 |
|
|
699 This will return the 32 least significant bits of the mp\_int $a$. |
|
|
700 |
|
|
701 \begin{small} \begin{alltt} |
|
|
702 int main(void) |
|
|
703 \{ |
|
|
704 mp_int number; |
|
|
705 int result; |
|
|
706 |
|
|
707 if ((result = mp_init(&number)) != MP_OKAY) \{ |
|
|
708 printf("Error initializing the number. \%s", |
|
|
709 mp_error_to_string(result)); |
|
|
710 return EXIT_FAILURE; |
|
|
711 \} |
|
|
712 |
|
|
713 /* set the number to 654321 (note this is bigger than 127) */ |
|
|
714 if ((result = mp_set_int(&number, 654321)) != MP_OKAY) \{ |
|
|
715 printf("Error setting the value of the number. \%s", |
|
|
716 mp_error_to_string(result)); |
|
|
717 return EXIT_FAILURE; |
|
|
718 \} |
|
|
719 |
|
|
720 printf("number == \%lu", mp_get_int(&number)); |
|
|
721 |
|
|
722 /* we're done with it. */ |
|
|
723 mp_clear(&number); |
|
|
724 |
|
|
725 return EXIT_SUCCESS; |
|
|
726 \} |
|
|
727 \end{alltt} \end{small} |
|
|
728 |
|
|
729 This should output the following if the program succeeds. |
|
|
730 |
|
|
731 \begin{alltt} |
|
|
732 number == 654321 |
|
|
733 \end{alltt} |
|
|
734 |
|
|
735 \subsection{Initialize and Setting Constants} |
|
|
736 To both initialize and set small constants the following two functions are available. |
|
|
737 \index{mp\_init\_set} \index{mp\_init\_set\_int} |
|
|
738 \begin{alltt} |
|
|
739 int mp_init_set (mp_int * a, mp_digit b); |
|
|
740 int mp_init_set_int (mp_int * a, unsigned long b); |
|
|
741 \end{alltt} |
|
|
742 |
|
|
743 Both functions work like the previous counterparts except they first mp\_init $a$ before setting the values. |
|
|
744 |
|
|
745 \begin{alltt} |
|
|
746 int main(void) |
|
|
747 \{ |
|
|
748 mp_int number1, number2; |
|
|
749 int result; |
|
|
750 |
|
|
751 /* initialize and set a single digit */ |
|
|
752 if ((result = mp_init_set(&number1, 100)) != MP_OKAY) \{ |
|
|
753 printf("Error setting number1: \%s", |
|
|
754 mp_error_to_string(result)); |
|
|
755 return EXIT_FAILURE; |
|
|
756 \} |
|
|
757 |
|
|
758 /* initialize and set a long */ |
|
|
759 if ((result = mp_init_set_int(&number2, 1023)) != MP_OKAY) \{ |
|
|
760 printf("Error setting number2: \%s", |
|
|
761 mp_error_to_string(result)); |
|
|
762 return EXIT_FAILURE; |
|
|
763 \} |
|
|
764 |
|
|
765 /* display */ |
|
|
766 printf("Number1, Number2 == \%lu, \%lu", |
|
|
767 mp_get_int(&number1), mp_get_int(&number2)); |
|
|
768 |
|
|
769 /* clear */ |
|
|
770 mp_clear_multi(&number1, &number2, NULL); |
|
|
771 |
|
|
772 return EXIT_SUCCESS; |
|
|
773 \} |
|
|
774 \end{alltt} |
|
|
775 |
|
|
776 If this program succeeds it shall output. |
|
|
777 \begin{alltt} |
|
|
778 Number1, Number2 == 100, 1023 |
|
|
779 \end{alltt} |
|
|
780 |
|
|
781 \section{Comparisons} |
|
|
782 |
|
|
783 Comparisons in LibTomMath are always performed in a ``left to right'' fashion. There are three possible return codes |
|
|
784 for any comparison. |
|
|
785 |
|
|
786 \index{MP\_GT} \index{MP\_EQ} \index{MP\_LT} |
|
|
787 \begin{figure}[here] |
|
|
788 \begin{center} |
|
|
789 \begin{tabular}{|c|c|} |
|
|
790 \hline \textbf{Result Code} & \textbf{Meaning} \\ |
|
|
791 \hline MP\_GT & $a > b$ \\ |
|
|
792 \hline MP\_EQ & $a = b$ \\ |
|
|
793 \hline MP\_LT & $a < b$ \\ |
|
|
794 \hline |
|
|
795 \end{tabular} |
|
|
796 \end{center} |
|
|
797 \caption{Comparison Codes for $a, b$} |
|
|
798 \label{fig:CMP} |
|
|
799 \end{figure} |
|
|
800 |
|
|
801 In figure \ref{fig:CMP} two integers $a$ and $b$ are being compared. In this case $a$ is said to be ``to the left'' of |
|
|
802 $b$. |
|
|
803 |
|
|
804 \subsection{Unsigned comparison} |
|
|
805 |
|
|
806 An unsigned comparison considers only the digits themselves and not the associated \textit{sign} flag of the |
|
|
807 mp\_int structures. This is analogous to an absolute comparison. The function mp\_cmp\_mag() will compare two |
|
|
808 mp\_int variables based on their digits only. |
|
|
809 |
|
|
810 \index{mp\_cmp\_mag} |
|
|
811 \begin{alltt} |
|
|
812 int mp_cmp(mp_int * a, mp_int * b); |
|
|
813 \end{alltt} |
|
|
814 This will compare $a$ to $b$ placing $a$ to the left of $b$. This function cannot fail and will return one of the |
|
|
815 three compare codes listed in figure \ref{fig:CMP}. |
|
|
816 |
|
|
817 \begin{small} \begin{alltt} |
|
|
818 int main(void) |
|
|
819 \{ |
|
|
820 mp_int number1, number2; |
|
|
821 int result; |
|
|
822 |
|
|
823 if ((result = mp_init_multi(&number1, &number2, NULL)) != MP_OKAY) \{ |
|
|
824 printf("Error initializing the numbers. \%s", |
|
|
825 mp_error_to_string(result)); |
|
|
826 return EXIT_FAILURE; |
|
|
827 \} |
|
|
828 |
|
|
829 /* set the number1 to 5 */ |
|
|
830 mp_set(&number1, 5); |
|
|
831 |
|
|
832 /* set the number2 to -6 */ |
|
|
833 mp_set(&number2, 6); |
|
|
834 if ((result = mp_neg(&number2, &number2)) != MP_OKAY) \{ |
|
|
835 printf("Error negating number2. \%s", |
|
|
836 mp_error_to_string(result)); |
|
|
837 return EXIT_FAILURE; |
|
|
838 \} |
|
|
839 |
|
|
840 switch(mp_cmp_mag(&number1, &number2)) \{ |
|
|
841 case MP_GT: printf("|number1| > |number2|"); break; |
|
|
842 case MP_EQ: printf("|number1| = |number2|"); break; |
|
|
843 case MP_LT: printf("|number1| < |number2|"); break; |
|
|
844 \} |
|
|
845 |
|
|
846 /* we're done with it. */ |
|
|
847 mp_clear_multi(&number1, &number2, NULL); |
|
|
848 |
|
|
849 return EXIT_SUCCESS; |
|
|
850 \} |
|
|
851 \end{alltt} \end{small} |
|
|
852 |
|
|
853 If this program\footnote{This function uses the mp\_neg() function which is discussed in section \ref{sec:NEG}.} completes |
|
|
854 successfully it should print the following. |
|
|
855 |
|
|
856 \begin{alltt} |
|
|
857 |number1| < |number2| |
|
|
858 \end{alltt} |
|
|
859 |
|
|
860 This is because $\vert -6 \vert = 6$ and obviously $5 < 6$. |
|
|
861 |
|
|
862 \subsection{Signed comparison} |
|
|
863 |
|
|
864 To compare two mp\_int variables based on their signed value the mp\_cmp() function is provided. |
|
|
865 |
|
|
866 \index{mp\_cmp} |
|
|
867 \begin{alltt} |
|
|
868 int mp_cmp(mp_int * a, mp_int * b); |
|
|
869 \end{alltt} |
|
|
870 |
|
|
871 This will compare $a$ to the left of $b$. It will first compare the signs of the two mp\_int variables. If they |
|
|
872 differ it will return immediately based on their signs. If the signs are equal then it will compare the digits |
|
|
873 individually. This function will return one of the compare conditions codes listed in figure \ref{fig:CMP}. |
|
|
874 |
|
|
875 \begin{small} \begin{alltt} |
|
|
876 int main(void) |
|
|
877 \{ |
|
|
878 mp_int number1, number2; |
|
|
879 int result; |
|
|
880 |
|
|
881 if ((result = mp_init_multi(&number1, &number2, NULL)) != MP_OKAY) \{ |
|
|
882 printf("Error initializing the numbers. \%s", |
|
|
883 mp_error_to_string(result)); |
|
|
884 return EXIT_FAILURE; |
|
|
885 \} |
|
|
886 |
|
|
887 /* set the number1 to 5 */ |
|
|
888 mp_set(&number1, 5); |
|
|
889 |
|
|
890 /* set the number2 to -6 */ |
|
|
891 mp_set(&number2, 6); |
|
|
892 if ((result = mp_neg(&number2, &number2)) != MP_OKAY) \{ |
|
|
893 printf("Error negating number2. \%s", |
|
|
894 mp_error_to_string(result)); |
|
|
895 return EXIT_FAILURE; |
|
|
896 \} |
|
|
897 |
|
|
898 switch(mp_cmp(&number1, &number2)) \{ |
|
|
899 case MP_GT: printf("number1 > number2"); break; |
|
|
900 case MP_EQ: printf("number1 = number2"); break; |
|
|
901 case MP_LT: printf("number1 < number2"); break; |
|
|
902 \} |
|
|
903 |
|
|
904 /* we're done with it. */ |
|
|
905 mp_clear_multi(&number1, &number2, NULL); |
|
|
906 |
|
|
907 return EXIT_SUCCESS; |
|
|
908 \} |
|
|
909 \end{alltt} \end{small} |
|
|
910 |
|
|
911 If this program\footnote{This function uses the mp\_neg() function which is discussed in section \ref{sec:NEG}.} completes |
|
|
912 successfully it should print the following. |
|
|
913 |
|
|
914 \begin{alltt} |
|
|
915 number1 > number2 |
|
|
916 \end{alltt} |
|
|
917 |
|
|
918 \subsection{Single Digit} |
|
|
919 |
|
|
920 To compare a single digit against an mp\_int the following function has been provided. |
|
|
921 |
|
|
922 \index{mp\_cmp\_d} |
|
|
923 \begin{alltt} |
|
|
924 int mp_cmp_d(mp_int * a, mp_digit b); |
|
|
925 \end{alltt} |
|
|
926 |
|
|
927 This will compare $a$ to the left of $b$ using a signed comparison. Note that it will always treat $b$ as |
|
|
928 positive. This function is rather handy when you have to compare against small values such as $1$ (which often |
|
|
929 comes up in cryptography). The function cannot fail and will return one of the tree compare condition codes |
|
|
930 listed in figure \ref{fig:CMP}. |
|
|
931 |
|
|
932 |
|
|
933 \begin{small} \begin{alltt} |
|
|
934 int main(void) |
|
|
935 \{ |
|
|
936 mp_int number; |
|
|
937 int result; |
|
|
938 |
|
|
939 if ((result = mp_init(&number)) != MP_OKAY) \{ |
|
|
940 printf("Error initializing the number. \%s", |
|
|
941 mp_error_to_string(result)); |
|
|
942 return EXIT_FAILURE; |
|
|
943 \} |
|
|
944 |
|
|
945 /* set the number to 5 */ |
|
|
946 mp_set(&number, 5); |
|
|
947 |
|
|
948 switch(mp_cmp_d(&number, 7)) \{ |
|
|
949 case MP_GT: printf("number > 7"); break; |
|
|
950 case MP_EQ: printf("number = 7"); break; |
|
|
951 case MP_LT: printf("number < 7"); break; |
|
|
952 \} |
|
|
953 |
|
|
954 /* we're done with it. */ |
|
|
955 mp_clear(&number); |
|
|
956 |
|
|
957 return EXIT_SUCCESS; |
|
|
958 \} |
|
|
959 \end{alltt} \end{small} |
|
|
960 |
|
|
961 If this program functions properly it will print out the following. |
|
|
962 |
|
|
963 \begin{alltt} |
|
|
964 number < 7 |
|
|
965 \end{alltt} |
|
|
966 |
|
|
967 \section{Logical Operations} |
|
|
968 |
|
|
969 Logical operations are operations that can be performed either with simple shifts or boolean operators such as |
|
|
970 AND, XOR and OR directly. These operations are very quick. |
|
|
971 |
|
|
972 \subsection{Multiplication by two} |
|
|
973 |
|
|
974 Multiplications and divisions by any power of two can be performed with quick logical shifts either left or |
|
|
975 right depending on the operation. |
|
|
976 |
|
|
977 When multiplying or dividing by two a special case routine can be used which are as follows. |
|
|
978 \index{mp\_mul\_2} \index{mp\_div\_2} |
|
|
979 \begin{alltt} |
|
|
980 int mp_mul_2(mp_int * a, mp_int * b); |
|
|
981 int mp_div_2(mp_int * a, mp_int * b); |
|
|
982 \end{alltt} |
|
|
983 |
|
|
984 The former will assign twice $a$ to $b$ while the latter will assign half $a$ to $b$. These functions are fast |
|
|
985 since the shift counts and maskes are hardcoded into the routines. |
|
|
986 |
|
|
987 \begin{small} \begin{alltt} |
|
|
988 int main(void) |
|
|
989 \{ |
|
|
990 mp_int number; |
|
|
991 int result; |
|
|
992 |
|
|
993 if ((result = mp_init(&number)) != MP_OKAY) \{ |
|
|
994 printf("Error initializing the number. \%s", |
|
|
995 mp_error_to_string(result)); |
|
|
996 return EXIT_FAILURE; |
|
|
997 \} |
|
|
998 |
|
|
999 /* set the number to 5 */ |
|
|
1000 mp_set(&number, 5); |
|
|
1001 |
|
|
1002 /* multiply by two */ |
|
|
1003 if ((result = mp\_mul\_2(&number, &number)) != MP_OKAY) \{ |
|
|
1004 printf("Error multiplying the number. \%s", |
|
|
1005 mp_error_to_string(result)); |
|
|
1006 return EXIT_FAILURE; |
|
|
1007 \} |
|
|
1008 switch(mp_cmp_d(&number, 7)) \{ |
|
|
1009 case MP_GT: printf("2*number > 7"); break; |
|
|
1010 case MP_EQ: printf("2*number = 7"); break; |
|
|
1011 case MP_LT: printf("2*number < 7"); break; |
|
|
1012 \} |
|
|
1013 |
|
|
1014 /* now divide by two */ |
|
|
1015 if ((result = mp\_div\_2(&number, &number)) != MP_OKAY) \{ |
|
|
1016 printf("Error dividing the number. \%s", |
|
|
1017 mp_error_to_string(result)); |
|
|
1018 return EXIT_FAILURE; |
|
|
1019 \} |
|
|
1020 switch(mp_cmp_d(&number, 7)) \{ |
|
|
1021 case MP_GT: printf("2*number/2 > 7"); break; |
|
|
1022 case MP_EQ: printf("2*number/2 = 7"); break; |
|
|
1023 case MP_LT: printf("2*number/2 < 7"); break; |
|
|
1024 \} |
|
|
1025 |
|
|
1026 /* we're done with it. */ |
|
|
1027 mp_clear(&number); |
|
|
1028 |
|
|
1029 return EXIT_SUCCESS; |
|
|
1030 \} |
|
|
1031 \end{alltt} \end{small} |
|
|
1032 |
|
|
1033 If this program is successful it will print out the following text. |
|
|
1034 |
|
|
1035 \begin{alltt} |
|
|
1036 2*number > 7 |
|
|
1037 2*number/2 < 7 |
|
|
1038 \end{alltt} |
|
|
1039 |
|
|
1040 Since $10 > 7$ and $5 < 7$. To multiply by a power of two the following function can be used. |
|
|
1041 |
|
|
1042 \index{mp\_mul\_2d} |
|
|
1043 \begin{alltt} |
|
|
1044 int mp_mul_2d(mp_int * a, int b, mp_int * c); |
|
|
1045 \end{alltt} |
|
|
1046 |
|
|
1047 This will multiply $a$ by $2^b$ and store the result in ``c''. If the value of $b$ is less than or equal to |
|
|
1048 zero the function will copy $a$ to ``c'' without performing any further actions. |
|
|
1049 |
|
|
1050 To divide by a power of two use the following. |
|
|
1051 |
|
|
1052 \index{mp\_div\_2d} |
|
|
1053 \begin{alltt} |
|
|
1054 int mp_div_2d (mp_int * a, int b, mp_int * c, mp_int * d); |
|
|
1055 \end{alltt} |
|
|
1056 Which will divide $a$ by $2^b$, store the quotient in ``c'' and the remainder in ``d'. If $b \le 0$ then the |
|
|
1057 function simply copies $a$ over to ``c'' and zeroes $d$. The variable $d$ may be passed as a \textbf{NULL} |
|
|
1058 value to signal that the remainder is not desired. |
|
|
1059 |
|
|
1060 \subsection{Polynomial Basis Operations} |
|
|
1061 |
|
|
1062 Strictly speaking the organization of the integers within the mp\_int structures is what is known as a |
|
|
1063 ``polynomial basis''. This simply means a field element is stored by divisions of a radix. For example, if |
|
|
1064 $f(x) = \sum_{i=0}^{k} y_ix^k$ for any vector $\vec y$ then the array of digits in $\vec y$ are said to be |
|
|
1065 the polynomial basis representation of $z$ if $f(\beta) = z$ for a given radix $\beta$. |
|
|
1066 |
|
|
1067 To multiply by the polynomial $g(x) = x$ all you have todo is shift the digits of the basis left one place. The |
|
|
1068 following function provides this operation. |
|
|
1069 |
|
|
1070 \index{mp\_lshd} |
|
|
1071 \begin{alltt} |
|
|
1072 int mp_lshd (mp_int * a, int b); |
|
|
1073 \end{alltt} |
|
|
1074 |
|
|
1075 This will multiply $a$ in place by $x^b$ which is equivalent to shifting the digits left $b$ places and inserting zeroes |
|
|
1076 in the least significant digits. Similarly to divide by a power of $x$ the following function is provided. |
|
|
1077 |
|
|
1078 \index{mp\_rshd} |
|
|
1079 \begin{alltt} |
|
|
1080 void mp_rshd (mp_int * a, int b) |
|
|
1081 \end{alltt} |
|
|
1082 This will divide $a$ in place by $x^b$ and discard the remainder. This function cannot fail as it performs the operations |
|
|
1083 in place and no new digits are required to complete it. |
|
|
1084 |
|
|
1085 \subsection{AND, OR and XOR Operations} |
|
|
1086 |
|
|
1087 While AND, OR and XOR operations are not typical ``bignum functions'' they can be useful in several instances. The |
|
|
1088 three functions are prototyped as follows. |
|
|
1089 |
|
|
1090 \index{mp\_or} \index{mp\_and} \index{mp\_xor} |
|
|
1091 \begin{alltt} |
|
|
1092 int mp_or (mp_int * a, mp_int * b, mp_int * c); |
|
|
1093 int mp_and (mp_int * a, mp_int * b, mp_int * c); |
|
|
1094 int mp_xor (mp_int * a, mp_int * b, mp_int * c); |
|
|
1095 \end{alltt} |
|
|
1096 |
|
|
1097 Which compute $c = a \odot b$ where $\odot$ is one of OR, AND or XOR. |
|
|
1098 |
|
|
1099 \section{Addition and Subtraction} |
|
|
1100 |
|
|
1101 To compute an addition or subtraction the following two functions can be used. |
|
|
1102 |
|
|
1103 \index{mp\_add} \index{mp\_sub} |
|
|
1104 \begin{alltt} |
|
|
1105 int mp_add (mp_int * a, mp_int * b, mp_int * c); |
|
|
1106 int mp_sub (mp_int * a, mp_int * b, mp_int * c) |
|
|
1107 \end{alltt} |
|
|
1108 |
|
|
1109 Which perform $c = a \odot b$ where $\odot$ is one of signed addition or subtraction. The operations are fully sign |
|
|
1110 aware. |
|
|
1111 |
|
|
1112 \section{Sign Manipulation} |
|
|
1113 \subsection{Negation} |
|
|
1114 \label{sec:NEG} |
|
|
1115 Simple integer negation can be performed with the following. |
|
|
1116 |
|
|
1117 \index{mp\_neg} |
|
|
1118 \begin{alltt} |
|
|
1119 int mp_neg (mp_int * a, mp_int * b); |
|
|
1120 \end{alltt} |
|
|
1121 |
|
|
1122 Which assigns $-a$ to $b$. |
|
|
1123 |
|
|
1124 \subsection{Absolute} |
|
|
1125 Simple integer absolutes can be performed with the following. |
|
|
1126 |
|
|
1127 \index{mp\_neg} |
|
|
1128 \begin{alltt} |
|
|
1129 int mp_abs (mp_int * a, mp_int * b); |
|
|
1130 \end{alltt} |
|
|
1131 |
|
|
1132 Which assigns $\vert a \vert$ to $b$. |
|
|
1133 |
|
|
1134 \section{Integer Division and Remainder} |
|
|
1135 To perform a complete and general integer division with remainder use the following function. |
|
|
1136 |
|
|
1137 \index{mp\_div} |
|
|
1138 \begin{alltt} |
|
|
1139 int mp_div (mp_int * a, mp_int * b, mp_int * c, mp_int * d); |
|
|
1140 \end{alltt} |
|
|
1141 |
|
|
1142 This divides $a$ by $b$ and stores the quotient in $c$ and $d$. The signed quotient is computed such that |
|
|
1143 $bc + d = a$. Note that either of $c$ or $d$ can be set to \textbf{NULL} if their value is not required. If |
|
|
1144 $b$ is zero the function returns \textbf{MP\_VAL}. |
|
|
1145 |
|
|
1146 |
|
|
1147 \chapter{Multiplication and Squaring} |
|
|
1148 \section{Multiplication} |
|
|
1149 A full signed integer multiplication can be performed with the following. |
|
|
1150 \index{mp\_mul} |
|
|
1151 \begin{alltt} |
|
|
1152 int mp_mul (mp_int * a, mp_int * b, mp_int * c); |
|
|
1153 \end{alltt} |
|
|
1154 Which assigns the full signed product $ab$ to $c$. This function actually breaks into one of four cases which are |
|
|
1155 specific multiplication routines optimized for given parameters. First there are the Toom-Cook multiplications which |
|
|
1156 should only be used with very large inputs. This is followed by the Karatsuba multiplications which are for moderate |
|
|
1157 sized inputs. Then followed by the Comba and baseline multipliers. |
|
|
1158 |
|
|
1159 Fortunately for the developer you don't really need to know this unless you really want to fine tune the system. mp\_mul() |
|
|
1160 will determine on its own\footnote{Some tweaking may be required.} what routine to use automatically when it is called. |
|
|
1161 |
|
|
1162 \begin{alltt} |
|
|
1163 int main(void) |
|
|
1164 \{ |
|
|
1165 mp_int number1, number2; |
|
|
1166 int result; |
|
|
1167 |
|
|
1168 /* Initialize the numbers */ |
|
|
1169 if ((result = mp_init_multi(&number1, |
|
|
1170 &number2, NULL)) != MP_OKAY) \{ |
|
|
1171 printf("Error initializing the numbers. \%s", |
|
|
1172 mp_error_to_string(result)); |
|
|
1173 return EXIT_FAILURE; |
|
|
1174 \} |
|
|
1175 |
|
|
1176 /* set the terms */ |
|
|
1177 if ((result = mp_set_int(&number, 257)) != MP_OKAY) \{ |
|
|
1178 printf("Error setting number1. \%s", |
|
|
1179 mp_error_to_string(result)); |
|
|
1180 return EXIT_FAILURE; |
|
|
1181 \} |
|
|
1182 |
|
|
1183 if ((result = mp_set_int(&number2, 1023)) != MP_OKAY) \{ |
|
|
1184 printf("Error setting number2. \%s", |
|
|
1185 mp_error_to_string(result)); |
|
|
1186 return EXIT_FAILURE; |
|
|
1187 \} |
|
|
1188 |
|
|
1189 /* multiply them */ |
|
|
1190 if ((result = mp_mul(&number1, &number2, |
|
|
1191 &number1)) != MP_OKAY) \{ |
|
|
1192 printf("Error multiplying terms. \%s", |
|
|
1193 mp_error_to_string(result)); |
|
|
1194 return EXIT_FAILURE; |
|
|
1195 \} |
|
|
1196 |
|
|
1197 /* display */ |
|
|
1198 printf("number1 * number2 == \%lu", mp_get_int(&number1)); |
|
|
1199 |
|
|
1200 /* free terms and return */ |
|
|
1201 mp_clear_multi(&number1, &number2, NULL); |
|
|
1202 |
|
|
1203 return EXIT_SUCCESS; |
|
|
1204 \} |
|
|
1205 \end{alltt} |
|
|
1206 |
|
|
1207 If this program succeeds it shall output the following. |
|
|
1208 |
|
|
1209 \begin{alltt} |
|
|
1210 number1 * number2 == 262911 |
|
|
1211 \end{alltt} |
|
|
1212 |
|
|
1213 \section{Squaring} |
|
|
1214 Since squaring can be performed faster than multiplication it is performed it's own function instead of just using |
|
|
1215 mp\_mul(). |
|
|
1216 |
|
|
1217 \index{mp\_sqr} |
|
|
1218 \begin{alltt} |
|
|
1219 int mp_sqr (mp_int * a, mp_int * b); |
|
|
1220 \end{alltt} |
|
|
1221 |
|
|
1222 Will square $a$ and store it in $b$. Like the case of multiplication there are four different squaring |
|
|
1223 algorithms all which can be called from mp\_sqr(). It is ideal to use mp\_sqr over mp\_mul when squaring terms. |
|
|
1224 |
|
|
1225 \section{Tuning Polynomial Basis Routines} |
|
|
1226 |
|
|
1227 Both of the Toom-Cook and Karatsuba multiplication algorithms are faster than the traditional $O(n^2)$ approach that |
|
|
1228 the Comba and baseline algorithms use. At $O(n^{1.464973})$ and $O(n^{1.584962})$ running times respectfully they require |
|
|
1229 considerably less work. For example, a 10000-digit multiplication would take roughly 724,000 single precision |
|
|
1230 multiplications with Toom-Cook or 100,000,000 single precision multiplications with the standard Comba (a factor |
|
|
1231 of 138). |
|
|
1232 |
|
|
1233 So why not always use Karatsuba or Toom-Cook? The simple answer is that they have so much overhead that they're not |
|
|
1234 actually faster than Comba until you hit distinct ``cutoff'' points. For Karatsuba with the default configuration, |
|
|
1235 GCC 3.3.1 and an Athlon XP processor the cutoff point is roughly 110 digits (about 70 for the Intel P4). That is, at |
|
|
1236 110 digits Karatsuba and Comba multiplications just about break even and for 110+ digits Karatsuba is faster. |
|
|
1237 |
|
|
1238 Toom-Cook has incredible overhead and is probably only useful for very large inputs. So far no known cutoff points |
|
|
1239 exist and for the most part I just set the cutoff points very high to make sure they're not called. |
|
|
1240 |
|
|
1241 A demo program in the ``etc/'' directory of the project called ``tune.c'' can be used to find the cutoff points. This |
|
|
1242 can be built with GCC as follows |
|
|
1243 |
|
|
1244 \begin{alltt} |
|
|
1245 make XXX |
|
|
1246 \end{alltt} |
|
|
1247 Where ``XXX'' is one of the following entries from the table \ref{fig:tuning}. |
|
|
1248 |
|
|
1249 \begin{figure}[here] |
|
|
1250 \begin{center} |
|
|
1251 \begin{small} |
|
|
1252 \begin{tabular}{|l|l|} |
|
|
1253 \hline \textbf{Value of XXX} & \textbf{Meaning} \\ |
|
|
1254 \hline tune & Builds portable tuning application \\ |
|
|
1255 \hline tune86 & Builds x86 (pentium and up) program for COFF \\ |
|
|
1256 \hline tune86c & Builds x86 program for Cygwin \\ |
|
|
1257 \hline tune86l & Builds x86 program for Linux (ELF format) \\ |
|
|
1258 \hline |
|
|
1259 \end{tabular} |
|
|
1260 \end{small} |
|
|
1261 \end{center} |
|
|
1262 \caption{Build Names for Tuning Programs} |
|
|
1263 \label{fig:tuning} |
|
|
1264 \end{figure} |
|
|
1265 |
|
|
1266 When the program is running it will output a series of measurements for different cutoff points. It will first find |
|
|
1267 good Karatsuba squaring and multiplication points. Then it proceeds to find Toom-Cook points. Note that the Toom-Cook |
|
|
1268 tuning takes a very long time as the cutoff points are likely to be very high. |
|
|
1269 |
|
|
1270 \chapter{Modular Reduction} |
|
|
1271 |
|
|
1272 Modular reduction is process of taking the remainder of one quantity divided by another. Expressed |
|
|
1273 as (\ref{eqn:mod}) the modular reduction is equivalent to the remainder of $b$ divided by $c$. |
|
|
1274 |
|
|
1275 \begin{equation} |
|
|
1276 a \equiv b \mbox{ (mod }c\mbox{)} |
|
|
1277 \label{eqn:mod} |
|
|
1278 \end{equation} |
|
|
1279 |
|
|
1280 Of particular interest to cryptography are reductions where $b$ is limited to the range $0 \le b < c^2$ since particularly |
|
|
1281 fast reduction algorithms can be written for the limited range. |
|
|
1282 |
|
|
1283 Note that one of the four optimized reduction algorithms are automatically chosen in the modular exponentiation |
|
|
1284 algorithm mp\_exptmod when an appropriate modulus is detected. |
|
|
1285 |
|
|
1286 \section{Straight Division} |
|
|
1287 In order to effect an arbitrary modular reduction the following algorithm is provided. |
|
|
1288 |
|
|
1289 \index{mp\_mod} |
|
|
1290 \begin{alltt} |
|
|
1291 int mp_mod(mp_int *a, mp_int *b, mp_int *c); |
|
|
1292 \end{alltt} |
|
|
1293 |
|
|
1294 This reduces $a$ modulo $b$ and stores the result in $c$. The sign of $c$ shall agree with the sign |
|
|
1295 of $b$. This algorithm accepts an input $a$ of any range and is not limited by $0 \le a < b^2$. |
|
|
1296 |
|
|
1297 \section{Barrett Reduction} |
|
|
1298 |
|
|
1299 Barrett reduction is a generic optimized reduction algorithm that requires pre--computation to achieve |
|
|
1300 a decent speedup over straight division. First a $mu$ value must be precomputed with the following function. |
|
|
1301 |
|
|
1302 \index{mp\_reduce\_setup} |
|
|
1303 \begin{alltt} |
|
|
1304 int mp_reduce_setup(mp_int *a, mp_int *b); |
|
|
1305 \end{alltt} |
|
|
1306 |
|
|
1307 Given a modulus in $b$ this produces the required $mu$ value in $a$. For any given modulus this only has to |
|
|
1308 be computed once. Modular reduction can now be performed with the following. |
|
|
1309 |
|
|
1310 \index{mp\_reduce} |
|
|
1311 \begin{alltt} |
|
|
1312 int mp_reduce(mp_int *a, mp_int *b, mp_int *c); |
|
|
1313 \end{alltt} |
|
|
1314 |
|
|
1315 This will reduce $a$ in place modulo $b$ with the precomputed $mu$ value in $c$. $a$ must be in the range |
|
|
1316 $0 \le a < b^2$. |
|
|
1317 |
|
|
1318 \begin{alltt} |
|
|
1319 int main(void) |
|
|
1320 \{ |
|
|
1321 mp_int a, b, c, mu; |
|
|
1322 int result; |
|
|
1323 |
|
|
1324 /* initialize a,b to desired values, mp_init mu, |
|
|
1325 * c and set c to 1...we want to compute a^3 mod b |
|
|
1326 */ |
|
|
1327 |
|
|
1328 /* get mu value */ |
|
|
1329 if ((result = mp_reduce_setup(&mu, b)) != MP_OKAY) \{ |
|
|
1330 printf("Error getting mu. \%s", |
|
|
1331 mp_error_to_string(result)); |
|
|
1332 return EXIT_FAILURE; |
|
|
1333 \} |
|
|
1334 |
|
|
1335 /* square a to get c = a^2 */ |
|
|
1336 if ((result = mp_sqr(&a, &c)) != MP_OKAY) \{ |
|
|
1337 printf("Error squaring. \%s", |
|
|
1338 mp_error_to_string(result)); |
|
|
1339 return EXIT_FAILURE; |
|
|
1340 \} |
|
|
1341 |
|
|
1342 /* now reduce `c' modulo b */ |
|
|
1343 if ((result = mp_reduce(&c, &b, &mu)) != MP_OKAY) \{ |
|
|
1344 printf("Error reducing. \%s", |
|
|
1345 mp_error_to_string(result)); |
|
|
1346 return EXIT_FAILURE; |
|
|
1347 \} |
|
|
1348 |
|
|
1349 /* multiply a to get c = a^3 */ |
|
|
1350 if ((result = mp_mul(&a, &c, &c)) != MP_OKAY) \{ |
|
|
1351 printf("Error reducing. \%s", |
|
|
1352 mp_error_to_string(result)); |
|
|
1353 return EXIT_FAILURE; |
|
|
1354 \} |
|
|
1355 |
|
|
1356 /* now reduce `c' modulo b */ |
|
|
1357 if ((result = mp_reduce(&c, &b, &mu)) != MP_OKAY) \{ |
|
|
1358 printf("Error reducing. \%s", |
|
|
1359 mp_error_to_string(result)); |
|
|
1360 return EXIT_FAILURE; |
|
|
1361 \} |
|
|
1362 |
|
|
1363 /* c now equals a^3 mod b */ |
|
|
1364 |
|
|
1365 return EXIT_SUCCESS; |
|
|
1366 \} |
|
|
1367 \end{alltt} |
|
|
1368 |
|
|
1369 This program will calculate $a^3 \mbox{ mod }b$ if all the functions succeed. |
|
|
1370 |
|
|
1371 \section{Montgomery Reduction} |
|
|
1372 |
|
|
1373 Montgomery is a specialized reduction algorithm for any odd moduli. Like Barrett reduction a pre--computation |
|
|
1374 step is required. This is accomplished with the following. |
|
|
1375 |
|
|
1376 \index{mp\_montgomery\_setup} |
|
|
1377 \begin{alltt} |
|
|
1378 int mp_montgomery_setup(mp_int *a, mp_digit *mp); |
|
|
1379 \end{alltt} |
|
|
1380 |
|
|
1381 For the given odd moduli $a$ the precomputation value is placed in $mp$. The reduction is computed with the |
|
|
1382 following. |
|
|
1383 |
|
|
1384 \index{mp\_montgomery\_reduce} |
|
|
1385 \begin{alltt} |
|
|
1386 int mp_montgomery_reduce(mp_int *a, mp_int *m, mp_digit mp); |
|
|
1387 \end{alltt} |
|
|
1388 This reduces $a$ in place modulo $m$ with the pre--computed value $mp$. $a$ must be in the range |
|
|
1389 $0 \le a < b^2$. |
|
|
1390 |
|
|
1391 Montgomery reduction is faster than Barrett reduction for moduli smaller than the ``comba'' limit. With the default |
|
|
1392 setup for instance, the limit is $127$ digits ($3556$--bits). Note that this function is not limited to |
|
|
1393 $127$ digits just that it falls back to a baseline algorithm after that point. |
|
|
1394 |
|
|
1395 An important observation is that this reduction does not return $a \mbox{ mod }m$ but $aR^{-1} \mbox{ mod }m$ |
|
|
1396 where $R = \beta^n$, $n$ is the n number of digits in $m$ and $\beta$ is radix used (default is $2^{28}$). |
|
|
1397 |
|
|
1398 To quickly calculate $R$ the following function was provided. |
|
|
1399 |
|
|
1400 \index{mp\_montgomery\_calc\_normalization} |
|
|
1401 \begin{alltt} |
|
|
1402 int mp_montgomery_calc_normalization(mp_int *a, mp_int *b); |
|
|
1403 \end{alltt} |
|
|
1404 Which calculates $a = R$ for the odd moduli $b$ without using multiplication or division. |
|
|
1405 |
|
|
1406 The normal modus operandi for Montgomery reductions is to normalize the integers before entering the system. For |
|
|
1407 example, to calculate $a^3 \mbox { mod }b$ using Montgomery reduction the value of $a$ can be normalized by |
|
|
1408 multiplying it by $R$. Consider the following code snippet. |
|
|
1409 |
|
|
1410 \begin{alltt} |
|
|
1411 int main(void) |
|
|
1412 \{ |
|
|
1413 mp_int a, b, c, R; |
|
|
1414 mp_digit mp; |
|
|
1415 int result; |
|
|
1416 |
|
|
1417 /* initialize a,b to desired values, |
|
|
1418 * mp_init R, c and set c to 1.... |
|
|
1419 */ |
|
|
1420 |
|
|
1421 /* get normalization */ |
|
|
1422 if ((result = mp_montgomery_calc_normalization(&R, b)) != MP_OKAY) \{ |
|
|
1423 printf("Error getting norm. \%s", |
|
|
1424 mp_error_to_string(result)); |
|
|
1425 return EXIT_FAILURE; |
|
|
1426 \} |
|
|
1427 |
|
|
1428 /* get mp value */ |
|
|
1429 if ((result = mp_montgomery_setup(&c, &mp)) != MP_OKAY) \{ |
|
|
1430 printf("Error setting up montgomery. \%s", |
|
|
1431 mp_error_to_string(result)); |
|
|
1432 return EXIT_FAILURE; |
|
|
1433 \} |
|
|
1434 |
|
|
1435 /* normalize `a' so now a is equal to aR */ |
|
|
1436 if ((result = mp_mulmod(&a, &R, &b, &a)) != MP_OKAY) \{ |
|
|
1437 printf("Error computing aR. \%s", |
|
|
1438 mp_error_to_string(result)); |
|
|
1439 return EXIT_FAILURE; |
|
|
1440 \} |
|
|
1441 |
|
|
1442 /* square a to get c = a^2R^2 */ |
|
|
1443 if ((result = mp_sqr(&a, &c)) != MP_OKAY) \{ |
|
|
1444 printf("Error squaring. \%s", |
|
|
1445 mp_error_to_string(result)); |
|
|
1446 return EXIT_FAILURE; |
|
|
1447 \} |
|
|
1448 |
|
|
1449 /* now reduce `c' back down to c = a^2R^2 * R^-1 == a^2R */ |
|
|
1450 if ((result = mp_montgomery_reduce(&c, &b, mp)) != MP_OKAY) \{ |
|
|
1451 printf("Error reducing. \%s", |
|
|
1452 mp_error_to_string(result)); |
|
|
1453 return EXIT_FAILURE; |
|
|
1454 \} |
|
|
1455 |
|
|
1456 /* multiply a to get c = a^3R^2 */ |
|
|
1457 if ((result = mp_mul(&a, &c, &c)) != MP_OKAY) \{ |
|
|
1458 printf("Error reducing. \%s", |
|
|
1459 mp_error_to_string(result)); |
|
|
1460 return EXIT_FAILURE; |
|
|
1461 \} |
|
|
1462 |
|
|
1463 /* now reduce `c' back down to c = a^3R^2 * R^-1 == a^3R */ |
|
|
1464 if ((result = mp_montgomery_reduce(&c, &b, mp)) != MP_OKAY) \{ |
|
|
1465 printf("Error reducing. \%s", |
|
|
1466 mp_error_to_string(result)); |
|
|
1467 return EXIT_FAILURE; |
|
|
1468 \} |
|
|
1469 |
|
|
1470 /* now reduce (again) `c' back down to c = a^3R * R^-1 == a^3 */ |
|
|
1471 if ((result = mp_montgomery_reduce(&c, &b, mp)) != MP_OKAY) \{ |
|
|
1472 printf("Error reducing. \%s", |
|
|
1473 mp_error_to_string(result)); |
|
|
1474 return EXIT_FAILURE; |
|
|
1475 \} |
|
|
1476 |
|
|
1477 /* c now equals a^3 mod b */ |
|
|
1478 |
|
|
1479 return EXIT_SUCCESS; |
|
|
1480 \} |
|
|
1481 \end{alltt} |
|
|
1482 |
|
|
1483 This particular example does not look too efficient but it demonstrates the point of the algorithm. By |
|
|
1484 normalizing the inputs the reduced results are always of the form $aR$ for some variable $a$. This allows |
|
|
1485 a single final reduction to correct for the normalization and the fast reduction used within the algorithm. |
|
|
1486 |
|
|
1487 For more details consider examining the file \textit{bn\_mp\_exptmod\_fast.c}. |
|
|
1488 |
|
|
1489 \section{Restricted Dimminished Radix} |
|
|
1490 |
|
|
1491 ``Dimminished Radix'' reduction refers to reduction with respect to moduli that are ameniable to simple |
|
|
1492 digit shifting and small multiplications. In this case the ``restricted'' variant refers to moduli of the |
|
|
1493 form $\beta^k - p$ for some $k \ge 0$ and $0 < p < \beta$ where $\beta$ is the radix (default to $2^{28}$). |
|
|
1494 |
|
|
1495 As in the case of Montgomery reduction there is a pre--computation phase required for a given modulus. |
|
|
1496 |
|
|
1497 \index{mp\_dr\_setup} |
|
|
1498 \begin{alltt} |
|
|
1499 void mp_dr_setup(mp_int *a, mp_digit *d); |
|
|
1500 \end{alltt} |
|
|
1501 |
|
|
1502 This computes the value required for the modulus $a$ and stores it in $d$. This function cannot fail |
|
|
1503 and does not return any error codes. After the pre--computation a reduction can be performed with the |
|
|
1504 following. |
|
|
1505 |
|
|
1506 \index{mp\_dr\_reduce} |
|
|
1507 \begin{alltt} |
|
|
1508 int mp_dr_reduce(mp_int *a, mp_int *b, mp_digit mp); |
|
|
1509 \end{alltt} |
|
|
1510 |
|
|
1511 This reduces $a$ in place modulo $b$ with the pre--computed value $mp$. $b$ must be of a restricted |
|
|
1512 dimminished radix form and $a$ must be in the range $0 \le a < b^2$. Dimminished radix reductions are |
|
|
1513 much faster than both Barrett and Montgomery reductions as they have a much lower asymtotic running time. |
|
|
1514 |
|
|
1515 Since the moduli are restricted this algorithm is not particularly useful for something like Rabin, RSA or |
|
|
1516 BBS cryptographic purposes. This reduction algorithm is useful for Diffie-Hellman and ECC where fixed |
|
|
1517 primes are acceptable. |
|
|
1518 |
|
|
1519 Note that unlike Montgomery reduction there is no normalization process. The result of this function is |
|
|
1520 equal to the correct residue. |
|
|
1521 |
|
|
1522 \section{Unrestricted Dimminshed Radix} |
|
|
1523 |
|
|
1524 Unrestricted reductions work much like the restricted counterparts except in this case the moduli is of the |
|
|
1525 form $2^k - p$ for $0 < p < \beta$. In this sense the unrestricted reductions are more flexible as they |
|
|
1526 can be applied to a wider range of numbers. |
|
|
1527 |
|
|
1528 \index{mp\_reduce\_2k\_setup} |
|
|
1529 \begin{alltt} |
|
|
1530 int mp_reduce_2k_setup(mp_int *a, mp_digit *d); |
|
|
1531 \end{alltt} |
|
|
1532 |
|
|
1533 This will compute the required $d$ value for the given moduli $a$. |
|
|
1534 |
|
|
1535 \index{mp\_reduce\_2k} |
|
|
1536 \begin{alltt} |
|
|
1537 int mp_reduce_2k(mp_int *a, mp_int *n, mp_digit d); |
|
|
1538 \end{alltt} |
|
|
1539 |
|
|
1540 This will reduce $a$ in place modulo $n$ with the pre--computed value $d$. From my experience this routine is |
|
|
1541 slower than mp\_dr\_reduce but faster for most moduli sizes than the Montgomery reduction. |
|
|
1542 |
|
|
1543 \chapter{Exponentiation} |
|
|
1544 \section{Single Digit Exponentiation} |
|
|
1545 \index{mp\_expt\_d} |
|
|
1546 \begin{alltt} |
|
|
1547 int mp_expt_d (mp_int * a, mp_digit b, mp_int * c) |
|
|
1548 \end{alltt} |
|
|
1549 This computes $c = a^b$ using a simple binary left-to-right algorithm. It is faster than repeated multiplications by |
|
|
1550 $a$ for all values of $b$ greater than three. |
|
|
1551 |
|
|
1552 \section{Modular Exponentiation} |
|
|
1553 \index{mp\_exptmod} |
|
|
1554 \begin{alltt} |
|
|
1555 int mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y) |
|
|
1556 \end{alltt} |
|
|
1557 This computes $Y \equiv G^X \mbox{ (mod }P\mbox{)}$ using a variable width sliding window algorithm. This function |
|
|
1558 will automatically detect the fastest modular reduction technique to use during the operation. For negative values of |
|
|
1559 $X$ the operation is performed as $Y \equiv (G^{-1} \mbox{ mod }P)^{\vert X \vert} \mbox{ (mod }P\mbox{)}$ provided that |
|
|
1560 $gcd(G, P) = 1$. |
|
|
1561 |
|
|
1562 This function is actually a shell around the two internal exponentiation functions. This routine will automatically |
|
|
1563 detect when Barrett, Montgomery, Restricted and Unrestricted Dimminished Radix based exponentiation can be used. Generally |
|
|
1564 moduli of the a ``restricted dimminished radix'' form lead to the fastest modular exponentiations. Followed by Montgomery |
|
|
1565 and the other two algorithms. |
|
|
1566 |
|
|
1567 \section{Root Finding} |
|
|
1568 \index{mp\_n\_root} |
|
|
1569 \begin{alltt} |
|
|
1570 int mp_n_root (mp_int * a, mp_digit b, mp_int * c) |
|
|
1571 \end{alltt} |
|
|
1572 This computes $c = a^{1/b}$ such that $c^b \le a$ and $(c+1)^b > a$. The implementation of this function is not |
|
|
1573 ideal for values of $b$ greater than three. It will work but become very slow. So unless you are working with very small |
|
|
1574 numbers (less than 1000 bits) I'd avoid $b > 3$ situations. Will return a positive root only for even roots and return |
|
|
1575 a root with the sign of the input for odd roots. For example, performing $4^{1/2}$ will return $2$ whereas $(-8)^{1/3}$ |
|
|
1576 will return $-2$. |
|
|
1577 |
|
|
1578 This algorithm uses the ``Newton Approximation'' method and will converge on the correct root fairly quickly. Since |
|
|
1579 the algorithm requires raising $a$ to the power of $b$ it is not ideal to attempt to find roots for large |
|
|
1580 values of $b$. If particularly large roots are required then a factor method could be used instead. For example, |
|
|
1581 $a^{1/16}$ is equivalent to $\left (a^{1/4} \right)^{1/4}$. |
|
|
1582 |
|
|
1583 \chapter{Prime Numbers} |
|
|
1584 \section{Trial Division} |
|
|
1585 \index{mp\_prime\_is\_divisible} |
|
|
1586 \begin{alltt} |
|
|
1587 int mp_prime_is_divisible (mp_int * a, int *result) |
|
|
1588 \end{alltt} |
|
|
1589 This will attempt to evenly divide $a$ by a list of primes\footnote{Default is the first 256 primes.} and store the |
|
|
1590 outcome in ``result''. That is if $result = 0$ then $a$ is not divisible by the primes, otherwise it is. Note that |
|
|
1591 if the function does not return \textbf{MP\_OKAY} the value in ``result'' should be considered undefined\footnote{Currently |
|
|
1592 the default is to set it to zero first.}. |
|
|
1593 |
|
|
1594 \section{Fermat Test} |
|
|
1595 \index{mp\_prime\_fermat} |
|
|
1596 \begin{alltt} |
|
|
1597 int mp_prime_fermat (mp_int * a, mp_int * b, int *result) |
|
|
1598 \end{alltt} |
|
|
1599 Performs a Fermat primality test to the base $b$. That is it computes $b^a \mbox{ mod }a$ and tests whether the value is |
|
|
1600 equal to $b$ or not. If the values are equal then $a$ is probably prime and $result$ is set to one. Otherwise $result$ |
|
|
1601 is set to zero. |
|
|
1602 |
|
|
1603 \section{Miller-Rabin Test} |
|
|
1604 \index{mp\_prime\_miller\_rabin} |
|
|
1605 \begin{alltt} |
|
|
1606 int mp_prime_miller_rabin (mp_int * a, mp_int * b, int *result) |
|
|
1607 \end{alltt} |
|
|
1608 Performs a Miller-Rabin test to the base $b$ of $a$. This test is much stronger than the Fermat test and is very hard to |
|
|
1609 fool (besides with Carmichael numbers). If $a$ passes the test (therefore is probably prime) $result$ is set to one. |
|
|
1610 Otherwise $result$ is set to zero. |
|
|
1611 |
|
|
1612 Note that is suggested that you use the Miller-Rabin test instead of the Fermat test since all of the failures of |
|
|
1613 Miller-Rabin are a subset of the failures of the Fermat test. |
|
|
1614 |
|
|
1615 \subsection{Required Number of Tests} |
|
|
1616 Generally to ensure a number is very likely to be prime you have to perform the Miller-Rabin with at least a half-dozen |
|
|
1617 or so unique bases. However, it has been proven that the probability of failure goes down as the size of the input goes up. |
|
|
1618 This is why a simple function has been provided to help out. |
|
|
1619 |
|
|
1620 \index{mp\_prime\_rabin\_miller\_trials} |
|
|
1621 \begin{alltt} |
|
|
1622 int mp_prime_rabin_miller_trials(int size) |
|
|
1623 \end{alltt} |
|
|
1624 This returns the number of trials required for a $2^{-96}$ (or lower) probability of failure for a given ``size'' expressed |
|
|
1625 in bits. This comes in handy specially since larger numbers are slower to test. For example, a 512-bit number would |
|
|
1626 require ten tests whereas a 1024-bit number would only require four tests. |
|
|
1627 |
|
|
1628 You should always still perform a trial division before a Miller-Rabin test though. |
|
|
1629 |
|
|
1630 \section{Primality Testing} |
|
|
1631 \index{mp\_prime\_is\_prime} |
|
|
1632 \begin{alltt} |
|
|
1633 int mp_prime_is_prime (mp_int * a, int t, int *result) |
|
|
1634 \end{alltt} |
|
|
1635 This will perform a trial division followed by $t$ rounds of Miller-Rabin tests on $a$ and store the result in $result$. |
|
|
1636 If $a$ passes all of the tests $result$ is set to one, otherwise it is set to zero. Note that $t$ is bounded by |
|
|
1637 $1 \le t < PRIME\_SIZE$ where $PRIME\_SIZE$ is the number of primes in the prime number table (by default this is $256$). |
|
|
1638 |
|
|
1639 \section{Next Prime} |
|
|
1640 \index{mp\_prime\_next\_prime} |
|
|
1641 \begin{alltt} |
|
|
1642 int mp_prime_next_prime(mp_int *a, int t, int bbs_style) |
|
|
1643 \end{alltt} |
|
|
1644 This finds the next prime after $a$ that passes mp\_prime\_is\_prime() with $t$ tests. Set $bbs\_style$ to one if you |
|
|
1645 want only the next prime congruent to $3 \mbox{ mod } 4$, otherwise set it to zero to find any next prime. |
|
|
1646 |
|
|
1647 \section{Random Primes} |
|
|
1648 \index{mp\_prime\_random} |
|
|
1649 \begin{alltt} |
|
|
1650 int mp_prime_random(mp_int *a, int t, int size, int bbs, |
|
|
1651 ltm_prime_callback cb, void *dat) |
|
|
1652 \end{alltt} |
|
|
1653 This will find a prime greater than $256^{size}$ which can be ``bbs\_style'' or not depending on $bbs$ and must pass |
|
|
1654 $t$ rounds of tests. The ``ltm\_prime\_callback'' is a typedef for |
|
|
1655 |
|
|
1656 \begin{alltt} |
|
|
1657 typedef int ltm_prime_callback(unsigned char *dst, int len, void *dat); |
|
|
1658 \end{alltt} |
|
|
1659 |
|
|
1660 Which is a function that must read $len$ bytes (and return the amount stored) into $dst$. The $dat$ variable is simply |
|
|
1661 copied from the original input. It can be used to pass RNG context data to the callback. The function |
|
|
1662 mp\_prime\_random() is more suitable for generating primes which must be secret (as in the case of RSA) since there |
|
|
1663 is no skew on the least significant bits. |
|
|
1664 |
|
|
1665 \textit{Note:} As of v0.30 of the LibTomMath library this function has been deprecated. It is still available |
|
|
1666 but users are encouraged to use the new mp\_prime\_random\_ex() function instead. |
|
|
1667 |
|
|
1668 \subsection{Extended Generation} |
|
|
1669 \index{mp\_prime\_random\_ex} |
|
|
1670 \begin{alltt} |
|
|
1671 int mp_prime_random_ex(mp_int *a, int t, |
|
|
1672 int size, int flags, |
|
|
1673 ltm_prime_callback cb, void *dat); |
|
|
1674 \end{alltt} |
|
|
1675 This will generate a prime in $a$ using $t$ tests of the primality testing algorithms. The variable $size$ |
|
|
1676 specifies the bit length of the prime desired. The variable $flags$ specifies one of several options available |
|
|
1677 (see fig. \ref{fig:primeopts}) which can be OR'ed together. The callback parameters are used as in |
|
|
1678 mp\_prime\_random(). |
|
|
1679 |
|
|
1680 \begin{figure}[here] |
|
|
1681 \begin{center} |
|
|
1682 \begin{small} |
|
|
1683 \begin{tabular}{|r|l|} |
|
|
1684 \hline \textbf{Flag} & \textbf{Meaning} \\ |
|
|
1685 \hline LTM\_PRIME\_BBS & Make the prime congruent to $3$ modulo $4$ \\ |
|
|
1686 \hline LTM\_PRIME\_SAFE & Make a prime $p$ such that $(p - 1)/2$ is also prime. \\ |
|
|
1687 & This option implies LTM\_PRIME\_BBS as well. \\ |
|
|
1688 \hline LTM\_PRIME\_2MSB\_OFF & Makes sure that the bit adjacent to the most significant bit \\ |
|
|
1689 & Is forced to zero. \\ |
|
|
1690 \hline LTM\_PRIME\_2MSB\_ON & Makes sure that the bit adjacent to the most significant bit \\ |
|
|
1691 & Is forced to one. \\ |
|
|
1692 \hline |
|
|
1693 \end{tabular} |
|
|
1694 \end{small} |
|
|
1695 \end{center} |
|
|
1696 \caption{Primality Generation Options} |
|
|
1697 \label{fig:primeopts} |
|
|
1698 \end{figure} |
|
|
1699 |
|
|
1700 \chapter{Input and Output} |
|
|
1701 \section{ASCII Conversions} |
|
|
1702 \subsection{To ASCII} |
|
|
1703 \index{mp\_toradix} |
|
|
1704 \begin{alltt} |
|
|
1705 int mp_toradix (mp_int * a, char *str, int radix); |
|
|
1706 \end{alltt} |
|
|
1707 This still store $a$ in ``str'' as a base-``radix'' string of ASCII chars. This function appends a NUL character |
|
|
1708 to terminate the string. Valid values of ``radix'' line in the range $[2, 64]$. To determine the size (exact) required |
|
|
1709 by the conversion before storing any data use the following function. |
|
|
1710 |
|
|
1711 \index{mp\_radix\_size} |
|
|
1712 \begin{alltt} |
|
|
1713 int mp_radix_size (mp_int * a, int radix, int *size) |
|
|
1714 \end{alltt} |
|
|
1715 This stores in ``size'' the number of characters (including space for the NUL terminator) required. Upon error this |
|
|
1716 function returns an error code and ``size'' will be zero. |
|
|
1717 |
|
|
1718 \subsection{From ASCII} |
|
|
1719 \index{mp\_read\_radix} |
|
|
1720 \begin{alltt} |
|
|
1721 int mp_read_radix (mp_int * a, char *str, int radix); |
|
|
1722 \end{alltt} |
|
|
1723 This will read the base-``radix'' NUL terminated string from ``str'' into $a$. It will stop reading when it reads a |
|
|
1724 character it does not recognize (which happens to include th NUL char... imagine that...). A single leading $-$ sign |
|
|
1725 can be used to denote a negative number. |
|
|
1726 |
|
|
1727 \section{Binary Conversions} |
|
|
1728 |
|
|
1729 Converting an mp\_int to and from binary is another keen idea. |
|
|
1730 |
|
|
1731 \index{mp\_unsigned\_bin\_size} |
|
|
1732 \begin{alltt} |
|
|
1733 int mp_unsigned_bin_size(mp_int *a); |
|
|
1734 \end{alltt} |
|
|
1735 |
|
|
1736 This will return the number of bytes (octets) required to store the unsigned copy of the integer $a$. |
|
|
1737 |
|
|
1738 \index{mp\_to\_unsigned\_bin} |
|
|
1739 \begin{alltt} |
|
|
1740 int mp_to_unsigned_bin(mp_int *a, unsigned char *b); |
|
|
1741 \end{alltt} |
|
|
1742 This will store $a$ into the buffer $b$ in big--endian format. Fortunately this is exactly what DER (or is it ASN?) |
|
|
1743 requires. It does not store the sign of the integer. |
|
|
1744 |
|
|
1745 \index{mp\_read\_unsigned\_bin} |
|
|
1746 \begin{alltt} |
|
|
1747 int mp_read_unsigned_bin(mp_int *a, unsigned char *b, int c); |
|
|
1748 \end{alltt} |
|
|
1749 This will read in an unsigned big--endian array of bytes (octets) from $b$ of length $c$ into $a$. The resulting |
|
|
1750 integer $a$ will always be positive. |
|
|
1751 |
|
|
1752 For those who acknowledge the existence of negative numbers (heretic!) there are ``signed'' versions of the |
|
|
1753 previous functions. |
|
|
1754 |
|
|
1755 \begin{alltt} |
|
|
1756 int mp_signed_bin_size(mp_int *a); |
|
|
1757 int mp_read_signed_bin(mp_int *a, unsigned char *b, int c); |
|
|
1758 int mp_to_signed_bin(mp_int *a, unsigned char *b); |
|
|
1759 \end{alltt} |
|
|
1760 They operate essentially the same as the unsigned copies except they prefix the data with zero or non--zero |
|
|
1761 byte depending on the sign. If the sign is zpos (e.g. not negative) the prefix is zero, otherwise the prefix |
|
|
1762 is non--zero. |
|
|
1763 |
|
|
1764 \chapter{Algebraic Functions} |
|
|
1765 \section{Extended Euclidean Algorithm} |
|
|
1766 \index{mp\_exteuclid} |
|
|
1767 \begin{alltt} |
|
|
1768 int mp_exteuclid(mp_int *a, mp_int *b, |
|
|
1769 mp_int *U1, mp_int *U2, mp_int *U3); |
|
|
1770 \end{alltt} |
|
|
1771 |
|
|
1772 This finds the triple U1/U2/U3 using the Extended Euclidean algorithm such that the following equation holds. |
|
|
1773 |
|
|
1774 \begin{equation} |
|
|
1775 a \cdot U1 + b \cdot U2 = U3 |
|
|
1776 \end{equation} |
|
|
1777 |
|
|
1778 Any of the U1/U2/U3 paramters can be set to \textbf{NULL} if they are not desired. |
|
|
1779 |
|
|
1780 \section{Greatest Common Divisor} |
|
|
1781 \index{mp\_gcd} |
|
|
1782 \begin{alltt} |
|
|
1783 int mp_gcd (mp_int * a, mp_int * b, mp_int * c) |
|
|
1784 \end{alltt} |
|
|
1785 This will compute the greatest common divisor of $a$ and $b$ and store it in $c$. |
|
|
1786 |
|
|
1787 \section{Least Common Multiple} |
|
|
1788 \index{mp\_lcm} |
|
|
1789 \begin{alltt} |
|
|
1790 int mp_lcm (mp_int * a, mp_int * b, mp_int * c) |
|
|
1791 \end{alltt} |
|
|
1792 This will compute the least common multiple of $a$ and $b$ and store it in $c$. |
|
|
1793 |
|
|
1794 \section{Jacobi Symbol} |
|
|
1795 \index{mp\_jacobi} |
|
|
1796 \begin{alltt} |
|
|
1797 int mp_jacobi (mp_int * a, mp_int * p, int *c) |
|
|
1798 \end{alltt} |
|
|
1799 This will compute the Jacobi symbol for $a$ with respect to $p$. If $p$ is prime this essentially computes the Legendre |
|
|
1800 symbol. The result is stored in $c$ and can take on one of three values $\lbrace -1, 0, 1 \rbrace$. If $p$ is prime |
|
|
1801 then the result will be $-1$ when $a$ is not a quadratic residue modulo $p$. The result will be $0$ if $a$ divides $p$ |
|
|
1802 and the result will be $1$ if $a$ is a quadratic residue modulo $p$. |
|
|
1803 |
|
|
1804 \section{Modular Inverse} |
|
|
1805 \index{mp\_invmod} |
|
|
1806 \begin{alltt} |
|
|
1807 int mp_invmod (mp_int * a, mp_int * b, mp_int * c) |
|
|
1808 \end{alltt} |
|
|
1809 Computes the multiplicative inverse of $a$ modulo $b$ and stores the result in $c$ such that $ac \equiv 1 \mbox{ (mod }b\mbox{)}$. |
|
|
1810 |
|
|
1811 \section{Single Digit Functions} |
|
|
1812 |
|
|
1813 For those using small numbers (\textit{snicker snicker}) there are several ``helper'' functions |
|
|
1814 |
|
|
1815 \index{mp\_add\_d} \index{mp\_sub\_d} \index{mp\_mul\_d} \index{mp\_div\_d} \index{mp\_mod\_d} |
|
|
1816 \begin{alltt} |
|
|
1817 int mp_add_d(mp_int *a, mp_digit b, mp_int *c); |
|
|
1818 int mp_sub_d(mp_int *a, mp_digit b, mp_int *c); |
|
|
1819 int mp_mul_d(mp_int *a, mp_digit b, mp_int *c); |
|
|
1820 int mp_div_d(mp_int *a, mp_digit b, mp_int *c, mp_digit *d); |
|
|
1821 int mp_mod_d(mp_int *a, mp_digit b, mp_digit *c); |
|
|
1822 \end{alltt} |
|
|
1823 |
|
|
1824 These work like the full mp\_int capable variants except the second parameter $b$ is a mp\_digit. These |
|
|
1825 functions fairly handy if you have to work with relatively small numbers since you will not have to allocate |
|
|
1826 an entire mp\_int to store a number like $1$ or $2$. |
|
|
1827 |
|
|
1828 \input{bn.ind} |
|
|
1829 |
|
|
1830 \end{document} |
