Skip to main content

About this book

This book covers everything you need to know to write professional-level cryptographic code. This expanded, improved second edition includes about 100 pages of additional material as well as numerous improvements to the original text. The chapter about random number generation has been completely rewritten, and the latest cryptographic techniques are covered in detail. Furthermore, this book covers the recent improvements in primality testing.

Table of Contents

Arithmetic and Number Theory in C


Chapter 1. Introduction

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.
Michael Welschenbach

Chapter 2. Number Formats: The Representation of Large Numbers in C

One of the first steps in creating a function library for calculating with large numbers is to determine how large numbers are to represented in the computer’s main memory. It is necessary to plan carefully, since decisions made at this point will be difficult to revise at a later time. Changes to the internal structure of a software library are always possible, but the user interface should be kept as stable as possible in the sense of “upward compatibility.”
Michael Welschenbach

Chapter 3. Interface Semantics

In the following we shall set some fundamental properties that relate to the behavior of the interface and the use of FLINT/C functions. First we shall consider the textual representation of CLINT objects and FLINT/C functions, but primarily we wish to clarify some fundamentals of the implementation that are important to the use of the functions.
Michael Welschenbach

Chapter 4. The Fundamental Operations

The fundamental building blocks of any software package for computer arithmetic are the functions that carry out the basic operations of addition, subtraction, multiplication, and division. The efficiency of the entire package hangs on the last two of these, and for that reason great care must be taken in the selection and implementation of the associated algorithms. Fortunately, volume 2 of Donald Knuth’s classic The Art of Computer Programming contains most of what we need for this portion of the FLINT/C functions.
Michael Welschenbach

Chapter 5. Modular Arithmetic: Calculating with Residue Classes

We begin this chapter with a discussion of the principle of division with remainder. In relation to this we shall explain the significance of these remainders, their possible applications, and how one calculates with them. In order for the functions to be introduced later to be understandable, we begin with a bit of algebra.
Michael Welschenbach

Chapter 6. Where All Roads Meet: Modular Exponentiation

In addition to the calculational rules for addition, subtraction, and multiplication in residue classes we can also define an operation of exponentiation, where the exponent specifies how many times the base is to be multiplied by itself. Exponentiation is carried out, as usual, by means of recursive calls to multiplication: For a in ℤ m we have a0:= ī and a e+1 := a · a e .
Michael Welschenbach

Chapter 7. Bitwise and Logical Functions

In this chapter we shall present functions that carry out bitwise operations on CLINT objects, and we shall also introduce functions for determining the equality and size of CLINT objects, which we have already used quite a bit.
Michael Welschenbach

Chapter 8. Input, Output, Assignment, Conversion

We begin this chapter with assignment, the simplest and also the most important function. To be able to assign to a CLINT object a_l the value of another CLINT object b_l, we require a function that copies the digits of b_l to the reserved storage space for a_l, an event that we shall call elementwise assignment. It will not suffice merely to copy the address of the object b_l into the variable a_l, since then both objects would refer to the same location in memory, namely that of b_l, and any change in a_l would be reflected in a change in the object b_l, and conversely. Furthermore, access to the area of memory addressed by a_l could become lost.
Michael Welschenbach

Chapter 9. Dynamic Registers

In addition to the automatic, or in exceptional cases global, CLINT objects used up to now, it is sometimes practical to be able to create and purge CLINT variables automatically. To this end we shall create several functions that will enable us to generate, use, clear, and remove a set of CLINT objects, the so-called register bank, as a dynamically allocated data structure, where we take up the sketch presented in [Skal] and work out the details for its use with CLINT objects.
Michael Welschenbach

Chapter 10. Basic Number-Theoretic Functions

Now that we are fitted out with a sturdy tool box of arithmetic functions that we developed in the previous chapters, we turn our attention to the implementation of several fundamental algorithms from the realm of number theory. The number-theoretic functions discussed in the following chapters form a collection that on the one hand exemplifies the application of the arithmetic of large numbers and on the other forms a useful foundation for more complex number-theoretic calculations and cryptographic applications. The resources provided here can be extended in a number of directions, so that for almost every type of application the necessary tools can be assembled with the demonstrated methods.
Michael Welschenbach

Chapter 11. Rijndael: A Successor to the Data Encryption Standard

The american national institute of Standards and Technology (NIST) launched a competition in 1997 under the aegis of an Advanced Encryption Standard (AES) with the goal of creating a new national standard (federal information processing standard, or FIPS) for encryption with a symmetric algorithm. Although we have concentrated our attention in this book on asymmetric cryptography, this development is important enough that we should give it some attention, if only cursorily. Through the new standard FIPS 197 [F197], an encryption algorithm will be established that satisfies all of today’s security requirements and that in all of its design and implementation aspects will be freely available without cost throughout the world. Finally, it replaces the dated data encryption standard (DES), which, however, as triple DES remains available for use in government agencies. However, the AES represents the cryptographic basis of the American administration for the protection of sensitive data.
Michael Welschenbach

Chapter 12. Large Random Numbers

Sequences of “random” numerical values are used in many statistical procedures, in numerical mathematics, in physics, and also in number-theoretic applications to replace statistical observations or to automate the input of variable quantities. Random numbers are used:
  • to select random samples from a larger set,
  • in cryptography to generate keys and in running security protocols,
  • as initial values in procedures to generate prime numbers,
  • to test computer programs (a topic to which we shall return),
  • for fun,
as well as in many additional applications. In computer simulations of natural phenomena random numbers can be used to represent measured values, thereby representing a natural process (Monte Carlo methods). Random numbers are useful even when numbers are required that can be selected arbitrarily. Before we set out in this chapter to produce some functions for the generation of large random numbers, which will be required, in particular, for cryptographic applications, we should take care of some methodological preparations.
Michael Welschenbach

Chapter 13. Strategies for Testing LINT

In the previous chapters we have encountered here and there hints for testing individual functions. Without meaningful tests to ensure the quality of our package, all of our work would be for naught, for on what else are we to base our confidence in the reliability of our functions? Therefore, we are now going to give our full attention to this important topic, and to this end we ask two questions that every software developer should ask:
How can we be certain that our software functions behave according to their specifications, which in our case means first of all that they are mathematically correct?
How can we achieve stability and reliability in the functioning of our software?
Michael Welschenbach

Arithmetic in C++ with the Class LINT


Chapter 14. Let C++ Simplify Your Life

The programming language c++, under development since 1979 by Bjarne Stroustrup1 at Bell Laboratories, is an extension of C that promises to dominate the field of software development. C++ supports the principles of object-oriented programming, which is based on the tenet that programs, or, better, processes, comprise a set of objects that interact exclusively through their interfaces. That is, they exchange information or accept certain external commands and process them as a task. In this the methods by which an object carries out a task are an internal affair “decided upon” autonomously by the object alone. The data structures and functions that represent the internal state of an object and effect transitions between states are the private affair of the object and should not be detectable from the outside. This principle, known as information hiding, assists software developers in concentrating on the tasks that an object has to fulfill within the framework of a program without having to worry about implementation details. (Another way of saying this is that the focus is on “what,” not on “how.”)
Michael Welschenbach

Chapter 15. The LINT Public Interface: Members and Friends

In addition to the constructor functions and operators already discussed, there exist further LINT functions that make the C functions developed in Part I available to LINT objects. In the following discussion we make a rough separation of the functions into the categories “arithmetic” and “number-theoretic.” The implementation of the functions will be discussed together with examples; otherwise, we shall restrict ourselves to a table of information needed for their proper use. We shall give more extensive treatment in the following sections to the functions for the formatted output of LINT objects, for which we shall make use of the properties of the stream classes contained in the C++ standard library. Possible applications, in particular for formatted output of objects of user-defined classes, are given rather short shrift in many C++ textbooks, and we are going to take the opportunity to explicate the construction of the functions needed to output our LINT objects.
Michael Welschenbach

Chapter 16. Error Handling

The C++ functions presented in the foregoing chapters embody mechanisms for analyzing whether during the execution of a called C function an error or other situation has occurred that requires a particular response or at least a warning. The functions test whether the passed variables have been initialized and evaluate the return value of the called C functions:
Michael Welschenbach

Chapter 17. An Application Example: The RSA Cryptosystem

As we approach the end of our story we would like to investigate the possibility of testing what we have labored over chapter by chapter against a realistic and current example, one that clearly demonstrates the connection between the theme of cryptographic application and the deployment of our programmed functions. We shall make a brief excursion into the principle of asymmetric cryptosystems and then turn our attention to the RSA algorithm as the classic example of such a system, which was published in 1978 by its inventors/discoverers, Ronald Rivest, Adi Shamir, and Leonard Adleman (see [Rive], [Elli]), and which by now has been implemented worldwide.1 The RSA algorithm is patented in the United States of America, but the patent expired on 20 September 2000. Against the free use of the RSA algorithm stood the claims of RSA Security, who possessed rights to the trade name “RSA,” which triggered vehement discussion in connection with work on the standard P1363 [IEEE], with in some cases rather grotesque results, for example, the suggestion of rechristening the RSA procedure “biprime cryptography.” There have also appeared less serious suggestions, such as FRA (former RSA algorithm), RAL (Ron, Adi, Leonard), and QRZ (RSA — 1). Upon expiry of their patent RSA Security weighed in with its opinion:
Clearly, the terms “RSA algorithm,” “RSA public-key algorithm,” “RSA cryptosystem,” and “RSA public-key cryptosystem” are well established in standards and open academic literature. RSA Security does not intend to prohibit the use of these terms by individuals or organizations that are implementing the RSA algorithm (“RSA-Security—Behind the Patent,” September 2000).2
Michael Welschenbach

Chapter 18. Do It Yourself: Test LINT

We have already discussed the topic of testing in Chapter 13, where we subjected the basic arithmetic functions of the first part of the book to extensive static and dynamic tests. We now require a similar treatment for the validation of the C++ class LINT, and furthermore, we still must provide tests of the number-theoretic C functions.
Michael Welschenbach

Chapter 19. Approaches for Further Extensions

Although we now have at our disposal a software package with a well-founded and well-rounded suite of functions, we confront now the question of in what directions our work might be continued. There are possibilities for work in the areas of functionality and performance.
Michael Welschenbach



Appendix A. Directory of C Functions

Michael Welschenbach

Appendix B. Directory of C++ Functions

Michael Welschenbach

Appendix C. Macros

Michael Welschenbach

Appendix D. Calculation Times

Calculation times for several flint/c functions, calculated with a Pentium 3 processor running at 2.4 GHz and 1 Gbyte main memory under Linux with gcc 3.2.2, are given in Tables D-1 and D-2. The times for n operations were measured and then divided by n. Depending on the functions, n ranged between 100 and 5 million. An additional table (Table D-3) shows, for comparison, calculation times that were measured for several functions in the GNU Multi Precision Arithmetic library (GMP, version 4.1.2); cf. page 464.
Michael Welschenbach

Appendix E. Notation

Michael Welschenbach

Appendix F. Arithmetic and Number-Theoretic Packages

If there be any lingering doubt in the mind of the reader as to the attractiveness and utility of algorithmic number theory, a glance at the large number of web sites that treat this topic should bring doubt to any such doubt at once, perhaps even by overwriting the reader’s cerebral registers. Just punch the search string “number theory” into your favorite Internet search engine, and up pop thousands of entries, a few of which have already been cited in this book. Many of these web sites contain links to available software packages or enable such packages to be downloaded. Such offers encapsulate a large bandwidth of functions for large-integer arithmetic, algebra, group theory, and number theory, demonstrating the efforts of many able and enthusiastic developers.
Michael Welschenbach
Additional information