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