Mercurial > dropbear
comparison libtommath/bn.tex @ 284:eed26cff980b
propagate from branch 'au.asn.ucc.matt.ltm.dropbear' (head 6c790cad5a7fa866ad062cb3a0c279f7ba788583)
to branch 'au.asn.ucc.matt.dropbear' (head fff0894a0399405a9410ea1c6d118f342cf2aa64)
| author | Matt Johnston <matt@ucc.asn.au> |
|---|---|
| date | Wed, 08 Mar 2006 13:23:49 +0000 |
| parents | |
| children | 5ff8218bcee9 |
comparison
equal
deleted
inserted
replaced
| 283:bd240aa12ba7 | 284:eed26cff980b |
|---|---|
| 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} |