what-is-libzahl.tex (8419B)
1 \chapter{What is libzahl?} 2 \label{chap:What is libzahl?} 3 4 In this chapter, it is discussed what libzahl is, 5 why it is called libzahl, why it exists, why 6 you should use it, what makes it different, and 7 what is its limitations. 8 9 \vspace{1cm} 10 \minitoc 11 12 13 \newpage 14 \section{The name and the what} 15 \label{sec:The name and the what} 16 17 In mathematics, the set of all integers is represented 18 by a bold uppercase `Z' ({\bf Z}), or sometimes % proper symbol 19 double-stroked (blackboard bold) ($\mathbb{Z}$). This symbol % hand-written style, specially on whiteboards and blackboards 20 is derived from the german word for integers: `Zahlen' 21 [\textprimstress{}tsa\textlengthmark{}l\textschwa{}n], 22 whose singular is `Zahl' [tsa\textlengthmark{}l]. libzahl 23 [l\textsecstress{}\textsci{}b\textprimstress{}tsa\textlengthmark{}l] 24 is a C library capable of representing very large integers, 25 limited by the memory address space and available memory. 26 Whilst this is almost none of the elements in {\bf Z}, 27 it is substantially more than available using the intrinsic 28 integer types in C. libzahl of course also implements 29 functions for performing arithmetic operations over 30 integers represented using libzahl. Libraries such as 31 libzahl are called bigint libraries, big integer libraries, 32 multiple precision integer libraries, arbitrary precision 33 integer libraries,\footnote{`Multiple precision integer' 34 and `arbitrary precision integer' are misnomers, precision 35 is only relevant for floating-point numbers.} or bignum 36 libraries, or any of the previous with `number' substituted 37 for `integer'. Some libraries that refer to themselves as bignum 38 libraries or any of using the word `number' support other 39 number types than integers. libzahl only supports integers. 40 41 42 \newpage 43 \section{Why does it exist?} 44 \label{sec:Why does it exist?} 45 46 libzahl's main competitors are GNU MP (gmp),\footnote{GNU 47 Multiple Precision Arithmetic Library} LibTomMath (ltm), 48 TomsFastMath (tfm) and Hebimath. All of these have problems: 49 50 \begin{itemize} 51 \item 52 GNU MP is extremely bloated, can only be complied with 53 GCC, and requires that you use glibc unless another C 54 standard library was used when GNU MP was compiled. 55 Additionally, whilst its performance is generally good, 56 it can still be improved. Furthermore, GNU MP cannot be 57 used for robust applications. 58 59 \item 60 LibTomMath is very slow, in fact performance is not its 61 priority, rather its simplicity is the priority. Despite 62 this, it is not really that simple. 63 64 \item 65 TomsFastMath is slow, complicated, and is not a true 66 big integer library and is specifically targeted at 67 cryptography. 68 \end{itemize} 69 70 libzahl is developed under the suckless.org umbrella. 71 As such, it attempts to follow the suckless 72 philosophy.\footnote{\href{http://suckless.org/philosophy} 73 {http://suckless.org/philosophy}} libzahl is simple, 74 very fast, simple to use, and can be used in robust 75 applications. Currently however, it does not support 76 multithreading, but it has better support for multiprocessing 77 and distributed computing than its competitors. 78 79 Lesser ``competitors'' (less known) to libzahl include 80 Hebimath and bsdnt. 81 82 \begin{itemize} 83 \item 84 Hebimath is far from stable, some fundamental functions 85 are not implemented and some functions are broken. The 86 author of libzahl thinks Hebimath is promising, but that 87 it could be better designed. Like libzahl, Hebimath aims 88 to follow the suckless philosophy. 89 90 \item 91 bsdnt has not been thoroughly investigated, but it 92 does not look promising. 93 \end{itemize} 94 95 96 \newpage 97 \section{How is it different?} 98 \label{sec:How is it different?} 99 100 All big number libraries have in common that both input 101 and output integers are parameters for the functions. 102 There are however two variants of this: input parameters 103 followed by output parameters, and output parameters 104 followed by input parameters. The former variant is the 105 conventional for C functions. The latter is more in style 106 with primitive operations, pseudo-code, mathematics, and 107 how it would look if the output was return. In libzahl, the 108 latter convention is used. That is, we write 109 110 \begin{alltt} 111 zadd(sum, augend, addend); 112 \end{alltt} 113 114 \noindent 115 rather than 116 117 \begin{alltt} 118 zadd(augend, addend, sum); 119 \end{alltt} 120 121 \noindent 122 This can be compared to 123 124 \vspace{1em} 125 $sum \gets augend + addend$ 126 \vspace{1em} 127 128 \noindent 129 versus 130 131 \vspace{1em} 132 $augend + addend \rightarrow sum$. 133 \vspace{1em} 134 135 libzahl, GNU MP, and Hebimath use the output-first 136 convention.\footnote{GNU MP-style.} LibTomMath and 137 TomsFastMath use the input-first convention.\footnote{BSD 138 MP-style.} 139 140 Unlike other bignum libraries, errors in libzahl are 141 caught using {\tt setjmp}. This ensure that it can be 142 used in robust applications, catching errors does not 143 become a mess, and it minimises the overhead of 144 catching errors. Typically, errors can be checked when 145 they can occur and after each function return; however, 146 here they can be checked only when they can occur. 147 148 Additionally, libzahl tries to keep the functions' 149 names simple and natural rather than technical or 150 mathematical. The names resemble those of the standard 151 integer operators. For example, the left-shift, right-shift 152 and truncation bit-operations in libzahl are called 153 {\tt zlsh}, {\tt zrsh} and {\tt ztrunc}, respectively. 154 In GNU MP, they are called {\tt mpz\_mul\_2exp}, 155 {\tt mpz\_tdiv\_q\_2exp} and {\tt mpz\_tdiv\_r\_2exp}. 156 The need of complicated names are diminished by resisting 157 to implement all possible variants of each operations. 158 Variants of a function simply append a short description 159 of the difference in plain text. For example, a variant of 160 {\tt zadd} that makes the assumption that both operands 161 are non-negative (or if not so, calculates the sum of 162 their absolute values) is called {\tt zadd\_unsigned}. 163 If libzahl would have had floored and ceiled variants of 164 {\tt zdiv} (truncated division), they would have been 165 called {\tt zdiv\_floor} and {\tt zdiv\_ceiling}. 166 {\tt zdiv} and {\tt zmod} (modulus) are variants of 167 {\tt zdivmod} that throw away one of the outputs. These 168 names can be compared to GNU MP's variants of truncated 169 division: {\tt mpz\_tdiv\_q}, {\tt mpz\_tdiv\_r} and 170 {\tt mpz\_tdiv\_qr}. 171 172 173 \newpage 174 \section{Limitations} 175 \label{sec:Limitations} 176 177 libzahl is not recommended for cryptographic 178 applications, it is not mature enough, and its 179 author does not have the necessary expertise. 180 And in particular, it does not implement constant 181 time operations, and it does not clear pooled 182 memory. Using libzahl in cryptographic application 183 is insecure; your application may become susceptible 184 attacks such as timing attacks, power-monitoring 185 attacks, electromagnetic attacks, acoustic 186 cryptanalysis, and data remanence attacks. libzahl 187 is known to be susceptible to timing attacks 188 (due to lack of constant time operations) and 189 data remanence attacks (due to pooling memory 190 for reuse without clearing the content of the 191 memory allocations.) Additionally, libzahl is not 192 thread-safe. 193 194 libzahl is also only designed for POSIX systems. 195 It will probably run just fine on any modern 196 system. But it makes some assumption that POSIX 197 stipulates or are unpractical to leave out from 198 machines that should support POSIX (or even 199 support modern software): 200 201 \begin{itemize} 202 \item 203 Bytes are octets. 204 205 \item 206 There is an integer type that is 64-bits wide. 207 (The compiler needs to support it, but it is not 208 strictly necessary for it to be an CPU-intrinsic, 209 but that would be favourable for performance.) 210 211 \item 212 Two's complement is used. 213 (The compiler needs to support it, but it is not 214 strictly necessary for it to be an CPU-intrinsic, 215 but that would be favourable for performance.) 216 \end{itemize} 217 218 Because of the prevalence of these properties 219 in contemporary machines, and the utilisation of 220 these properties in software, especially software 221 for POSIX and popular platforms with similar 222 properties, any new general-purpose machine must 223 have these properties, lest it be useless with 224 today's software. Therefore, libzahl can make 225 the assumption that the machine has these 226 properties. If the machine does not have these 227 properties, the compiler must compensate for 228 these machines deficiencies, making it generally 229 slower. 230 231 These limitations may be removed later. And there 232 is some code that does not make these assumptions 233 but acknowledge that it may be a case. On the other 234 hand, these limitations could be fixed, and agnostic 235 code could be rewritten to assume that these 236 restrictions are met.