what-is-libzahl.tex - libzahl - big integer library | |
git clone git://git.suckless.org/libzahl | |
Log | |
Files | |
Refs | |
README | |
LICENSE | |
--- | |
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 sy… | |
19 double-stroked (blackboard bold) ($\mathbb{Z}$). This symbol % hand-writ… | |
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. |