God created the integers. All the rest is the work of man.
If you look at zero you see nothing; but look through it and you will see the world.
TO Be Involved With Modern cryptography is to dive willy-nilly into number theory, that is, the study of the natural numbers, one of the most beautiful areas of mathematics. However, we have no intention of becoming deep-sea divers who raise sunken treasure from the mathematical ocean floor, which in any case is unnecessary for cryptographic applications. Our goals are much more modest. On the other hand, there is no limit to the depth of involvement of number theory with cryptography, and many significant mathematicians have made important contributions to this area.
The roots of number theory reach back to antiquity. The Pythagoreans—the Greek mathematician and philosopher Pythagoras and his school—were already deeply involved in the sixth century B.C.E. with relations among the integers, and they achieved significant mathematical results, for example the famed Pythagorean theorem, which is a part of every school child's education. With religious zeal they took the position that all numbers should be commensurate with the natural numbers, and they found themselves on the horns of a serious dilemma when they discovered the existence of "irrational" numbers such as
Two of the oldest number-theoretic algorithms, which have been passed down to us from the Greek mathematicians Euclid (third century B.C.E.) and Eratosthenes (276-195 B.C.E.), are closely related to the most contemporary encryption algorithms that we use every day to secure communication across the Internet. The "Euclidean algorithm" and the "sieve of Eratosthenes" are both quite up-to-date for our work, and we shall discuss their theory and application in Sections 10.1 and 10.5 of this book.
Among the most important founders of modern number theory are to be counted Pierre de Fermat (1601-1665), Leonhard Euler (1707-1783), Adrien Marie Legendre (1752-1833), Carl Friedrich Gauss (1777-1855), and Ernst Eduard Kummer (1810-1893). Their work forms the basis for the modern development of this area of mathematics and in particular the interesting application areas such as cryptography, with its asymmetric procedures for encryption and the generation of digital signatures (cf. Chapter 17). We could mention many more names of important contributors to this field, who continue to this day to be involved in often dramatic developments in number theory, and to those interested in a thrilling account of the history of number theory and its protagonists, I heartily recommend the book Fermat's Last Theorem, by Simon Singh.
Considering that already as children we learned counting as something to be taken for granted and that we were readily convinced of such facts as that two plus two equals four, we must turn to surprisingly abstract thought constructs to derive the theoretical justification for such assertions. For example, set theory allows us to derive the existence and arithmetic of the natural numbers from (almost) nothing. This "almost nothing" is the empty (or null) set • := { }, that is, the set that has no elements. If we consider the empty set to correspond to the number 0, then we are able to construct additional sets as follows. The successor 0+ of 0 is associated with the set 0+ := { 0 } = { • }, which contains a single element, namely the null set. We give the successor of 0 the name 1, and for this set as well we can determine a successor, namely 1+ := {•, {•}}. The successor of 1, which contains 0 and 1 as its elements, is given the name 2. The sets thus constructed, which we have rashly given the names 0, 1, and 2, we identify—not surprisingly—with the well-known natural numbers 0,1, and 2.
This principle of construction, which to every number x associates a successor x+ := x
From this postulated existence of (at least) one so-called successor set, which, beginning with 0, contains all successors, set theory derives the existence of a minimal successor set •, which is itself a subset of every successor set. This minimal and thus uniquely determined successor set • is called the set of natural numbers, in which we expressly include zero as an element.[1]
The natural numbers can be characterized by means of the axioms of Giuseppe Peano (1858-1932), which coincide with our intuitive understanding of the natural numbers:
(I) The successors of two unequal natural numbers are unequal: From n
(II) Every natural number, with the exception of 0, has a predecessor: •+ = • { 0 }.
(III) The principle of complete induction: If S
The principle of complete induction makes it possible to derive the arithmetic operations with natural numbers in which we are interested. The fundamental operations of addition and multiplication can be defined recursively as follows. We begin with addition:
| For every natural number n € • there exists a function sn from • to • such that |
(i) sn (0) = n,
(ii) sn (x+) =(sn(x))+ for all natural numbers x € •.
The value of the function sn(x) is called the sum n + x of n and x.
The existence of such functions sn for all natural numbers n € • must, however, bse proved, since the infinitude of natural numbers does not a priori justify such an assumption. The existence proof goes back to the principle of complete induction, corresponding to Peano's third axiom above (see [Halm], Chapters 11–13). For multiplication one proceeds analogously:
| For every natural number n € • there exists a function pn from • to • such that |
(i) pn (0) = 0,
(ii) pn (x+) = pn(x) + n for all natural numbers x € •.
The value of the function pn(x) is called the product n • x of n and x.
As expected, multiplication is defined in terms of addition. For the arithmetic operations thus defined one can prove, through repeated application of complete induction on x in accordance with Axiom III, such well-known arithmetic laws as associativity, commutativity, and distributivity (cf. [Halm], Chapter 13). Although we usually use these laws without further ado, we shall help ourselves to them as much as we please in testing our FLINT functions (see Chapters 13 and 18).
In a similar way we obtain a definition of exponentiation, which we give here in view of the importance of this operation in what follows.
For every natural number n € • there exists a function en from • to • such that
(i) en(0) = 1,
(ii) en (x+) = en(x) • n for every natural number x € •.
The value of the function en (x) is called the xth power nx of n. With complete induction we can prove the power law
to which we shall return in Chapter 6.
In addition to the calculational operations, the set • of natural numbers has defined on it an order relation "<" that makes it possible to compare two elements n, m € •. Although this fact is worthy of our great attention from a set-theoretic point of view, here we shall content ourselves with noting that the order relation has precisely those properties that we know about and use in our everyday lives.
Now that we have begun with establishing the empty set as the sole fundamental building block of the natural numbers, we now proceed to consider the materials with which we shall be concerned in what follows. Although number theory generally considers the natural numbers and the integers as given and goes on to consider their properties without excessive beating about the bush, it is nonetheless of interest to us to have at least once taken a glance at a process of "mathematical cell division," a process that produces not only the natural numbers, but also the arithmetic operations and rules with which we shall be deeply involved from here on.
The software described in this book constitutes in its entirety a package, a so-called function library, to which frequent reference will be made. This library has been given the name FLINT/C, which is an acronym for "functions for large integers in number theory and cryptography."
The FLINT/C library contains, among other items, the modules shown in Tables 1-1 through 1-5, which can be found as source code at www.apress.com.
Table 1-1. Arithmetic and number theory in C in directory flint/src
| header file for using functions from |
| arithmetic and number-theoretic functions in C |
| functions for Karatsuba multiplication and squaring |
| implementation of the hash function RIPEMD-160 |
| implementations of the hash functions SHA-1, SHA-256 |
| generation of entropy as start value for pseudorandom sequences |
| generation of pseudorandom numbers |
| implementation of the Advanced Encryption Standard |
Table 1-2. Arithmetic modules in 80x86 assembler (see Chapter 19) in directory flint/src/asm
| multiplication, replaces the C function |
| multiplication, replaces the C function |
| squaring, replaces the C function |
| division, replaces the C function |
Table 1-3. Tests (see Sections 13.2 and 18) in directories flint/test and flint/test/testvals
| test programs in C and C++ |
| test vectors for AES |
Table 1-4. Libraries in 80x86 assembler (see Chapter 19) in directories flint/lib and flint/lib/dll
| library with assembler functions in OMF (object module format) |
| library with assembler functions in COFF (common object file format) |
| archive with assembler functions for emx/gcc under OS/2 |
| archive with assembler functions for use under LINUX |
| DLL with the FLINT/C functions for use with MS VC/C++ |
| link library for |
Table 1-5. RSA implementation (see Chapter 17) in directory flint/rsa
| header file for the RSA classes |
| implementation of the RSA classes |
| example application of the RSA classes and their functions |
A list of the individual components of the FLINT/C software can be found in the file readme.doc is the source code. The software has been tested with the indicated development tools on the following platforms:
GNU gcc under Linux, SunOS 4.1, and Sun Solaris
GNU/EMX gcc under OS/2 Warp, DOS, and Windows (9x, NT)
Borland BCC32 under Windows (9x, NT, 2000, XP)
lcc-win32 under Windows (9x, NT, 2000, XP)
Cygnus cygwin B20 under Windows (9x, NT, 2000, XP)
IBM VisualAge under OS/2 Warp and Windows (9x, NT, 2000, XP)
Microsoft C under DOS, OS/2 Warp, and Windows (9x, NT)
Microsoft Visual C/C++ under Windows (9x, NT, 2000, XP)
Watcom C/C++ under DOS, OS/2 Warp, and Windows (3.1, 9x, NT, XP)
OpenWatcom C/C++ under Windows (2000, XP)
The assembler programs can be translated with Microsoft MASM,[2] with Watcom WASM, or with the GNU assembler GAS. They are contained in the downloadable source code in translated form as libraries in OMF (object module format) and COFF (common object file format), respectively, as well as in the form of a LINUX archive, and are used instead of the corresponding C functions when in translating C programs the macro FLINT_ASM is defined and the assembler object modules from the libraries, respectively archives, are linked.
A typical compiler call, here for the GNU compiler gcc, looks something like the following (with the paths to the source directories suppressed):
gcc -O2 -o rsademo rsademo.cpp rsakey.cpp flintpp.cpp randompp.cpp flint.c aes.c ripemd.c sha256.c entropy.c random.c -lstdc++
The C++ header files following the ANSI standard are used when in compilation the macro FLINTPP_ANSI is defined; otherwise, the traditional header files xxxxx.h are used.
Depending on the computer platform, there may be deviations with regard to the compiler switches; but to achieve maximum performance the options for speed optimization should always be turned on. Because of the demands on the stack, in many environments and applications it will have to be adjusted.[3] Regarding the necessary stack size for particular applications, one should note the suggestion about the exponentiation functions in Chapter 6 and in the overview on page 117. The stack requirements can be lessened by using the exponentiation function with dynamic stack allocation as well as by the implementation of dynamic registers (see Chapter 9).
The C functions and constants have been provided with the macros
_FLINT_API | Qualifier for C functions |
_FLINT_API_A | Qualifier for assembler functions |
_FLINT_API_DATA | Qualifier for constants |
as in
extern int __FLINT_API add_l(CLINT, CLINT, CLINT); extern USHORT __FLINT_API_DATA smallprimes[];
or, respectively, in the use of the assembler functions
extern int __FLINT_API_A div_l (CLINT, CLINT, CLINT, CLINT);
These macros are generally defined as empty comments /**/. With their aid, using the appropriate definitions, compiler- and linker-specific instructions to functions and data can be made. If the assembler modules are used and not the GNU compiler gcc, the macro __FLINT_API_A is defined by __cdecl, and some compilers understand this as an instruction that the assembler functions corresponding to the C name and calling conventions are to be called.
For modules that import FLINT/C functions and constants from a dynamic link library (DLL) under Microsoft Visual C/C++, in translation the macros -D__FLINT_API=__cdecl and -D__FLINT_API_DATA= __declspec (dllimport) must be defined. This has already been taken into account in flint.h, and it suffices in this case to define the macro FLINT_USEDLL for compilation. For other development environments analogous definitions should be employed.
The small amount of work involved in initializing a FLINT/C DLL is taken care of by the function FLINTInit_l(), which provides initial values for the random number generator[4] and generates a set of dynamic registers (see Chapter 9). The complementary function FLINTExit_l() deallocates the dynamic registers. Sensibly enough, the initialization is not handed over to every individual process that uses the DLL, but is executed once at the start of the DLL. As a rule, a function with creator-specific signature and calling convention should be used, which is executed automatically when the DLL is loaded by the run-time system. This function can take over the FLINT/C initialization and use the two functions mentioned above. All of this should be considered when a DLL is created.
Some effort was made to make the software usable in security-critical applications. To this end, in security mode local variables in functions, in particular CLINT and LINT objects, are deleted after use by being overwritten with zeros. For the C functions this is accomplished with the help of the macro PURGEVARS_L() and the associated function purgevars_l(). For the C++ functions the destructor ~LINT() is similarly equipped. The assembler functions overwrite their working memory. The deletion of variables that are passed as arguments to functions is the responsibility of the calling functions.
If the deletion of variables, which requires a certain additional expenditure of time, is to be omitted, then in compilation the macro FLINT_UNSECURE must be defined. At run time the function char* verstr_l() gives information about the modes set at compile time, in which additionally to the version label X.x, the letters "a" for assembler support and "s" for security mode are output in a character string if these modes have been turned on.
The software is exclusively for private use. For such purposes the software may be used, altered, and distributed under the following conditions:
The copyright notice may not be altered or deleted.
All changes must be annotated by means of comment lines. Any other use, in particular the use of the software for commercial purposes, requires written permission from the publisher or the author.
The software has been created and tested with the greatest possible care. Since errors can never be completely eliminated, neither the author nor the publisher can take responsibility for direct or indirect damages that may arise from the use or unusability of the software, regardless of the purpose to which it has been put.
The author would be glad to receive information about errors or any other helpful criticism or comment. Please write to him at [email protected].
[1] It was not decisive for this choice that according to standard DIN 5473 zero belongs to the natural numbers. From the point of view of computer science, however, it is practical to begin counting at zero instead of 1, which is indicative of the important role played by zero as the neutral element for addition (additive identity).
[2] Call: ml /Cx /c /Gd (filename).
[3] With modern computers with virtual memory, except in the case of DOS, one usually does not have to worry about this point, in particular with Unix or Linux systems.
[4] The initial values are made up of 32-bit numbers taken from the system clock. For applications in which security is critical it is advisable touse suitable random values from a sufficiently large interval as initial values.