Chapter 13: Let C Simplify Your Life | Cryptography in C and C++

Team-Fly

Overview

Our life is frittered away by detail.... Simplify, simplify.

—H. D. Thoreau, Walden

THE PROGRAMMING LANGUAGE C++, UNDER development since 1979 by Bjarne Stroustrup^[1] 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.")

The structural designs for what goes on in the "internal affairs" of objects, containing complete information on the organization of data structures and functions, are the classes. With these the external interface of an object is established, and this is decisive for the suite of behaviors that an object can perform. Since all objects of a class reflect the same structural design, they also possess the same interface. But once they have been created (computer scientists say that classes are instantiated by objects), they lead independent lives. Their internal states are changed independently of one another and they execute different tasks corresponding to their respective roles in the program.

Object-oriented programming propagates the use of classes as the building blocks of larger structures, which can again be classes or groups of classes, into complete programs, just as houses or automobiles are constructed of prefabricated modules. In the ideal case programs can be cobbled together from libraries of preexisting classes without the necessity for the creation of a significant amount of new code, at least not on the order of magnitude as is typical in conventional program development. As a result it is easier to orient program development to reflect the actual situation, to model directly the actual processes, and thereby to achieve successive refinement until the result is a collection of objects of particular classes and their interrelations, in which the underlying real-world model can still be recognized.

Such a way of proceeding is well known to us from many aspects of our lives, for we do not generally operate directly with raw materials if we wish to build something, but we use, rather, completed modules about whose construction or inner workings we have no detailed knowledge, nor the necessity of such knowledge. By standing on the shoulders of those who built before us, it becomes possible for us to create more and more complex structures with a manageable amount of effort. In the creation of software this natural state of affairs has not previously found its true expression, as software developers turn again and again to the raw materials themselves: Programs are constructed out of atomic elements of a programming language (this constructive process is commonly called coding). The use of run-time libraries such as the C standard library does not improve this situation to any great degree, since the functions contained in such libraries are too primitive to permit a direct connection to a more complex application.

Every programmer knows that data structures and functions that provide acceptable solutions for particular problems only seldom can be used for similar but different tasks without modification. The result is a reduction in the advantage of being able to rely on fully tested and trusted components, since any alteration contains the risk of new errors—as much in the design as in programming. (One is reminded of the notification in manuals that accompany various consumer products: "Any alteration by other than an authorized service provider voids the warranty.")

In order that the goal of reusability of software in the form of prefabricated building blocks not founder on the rocks of insufficient flexibility, the concept of inheritance, among a number of other concepts, has been developed. This makes it possible to modify classes to meet new requirements without actually altering them. Instead, the necessary changes are packaged in an extension layer. The objects that thus arise take on, in addition to their new properties, all the properties of the old objects. One might say that they inherit these properties. The principle of information hiding remains intact. The chances of error are greatly reduced, and productivity is increased. It is like a dream come true.

As an object-oriented programming language C++ possesses the requisite mechanisms for the support of these principles of abstraction.^[2] These, however, represent only a potential, but not a guarantee, of being used in the sense of object-oriented programming. To the contrary, the switch from conventional to object-oriented software development requires a considerable intellectual retooling. This is particularly apparent in two respects: On the one hand, the developer who has hitherto achieved good results is forced to devote considerably more attention to the modeling and design phases than what was usually required in traditional methods of software development. On the other hand, in the development and testing of new classes the greatest care is required to obtain error-free building blocks, since they will go on to be used in a great variety of future applications. Information hiding can also mean bug hiding, since it defeats the purpose of the idea of object-oriented programming if the user of a class must become familiar with its inner workings in order to find a bug. The result is that errors contained in a class implementation are inherited together with the class, so that all subclasses will be infected with the same "hereditary disease." On the other hand, the analysis of errors that occur with the objects of a class can be restricted to the implementation of the class, which can greatly reduce the scope of the search for the error.

All in all, we must say that while there is a strong trend in the direction of using C++ as a programming language, nonetheless, the principles of object-oriented programming beyond an understanding of the essentially complex language elements of C++ are multifaceted, and it will be a long time before it is used as a standard method of software development.

Thus the title of this chapter refers not to object-oriented programming and the use of C++ in general, but to the mechanisms offered therein and their significance for our project. These enable the formulation of arithmetic operations with large numbers in a way that is so natural that it is as if they belonged to the standard operations of the programming language. In the following sections, therefore, we will not be presenting an introduction to C++, but a discussion of the development of classes that represent large natural numbers and that export functions to work with these numbers as abstract methods.^[3] The (few) details of the data structures will be hidden both from the user and the client of the class, as will the implementation of the numerous arithmetic and number-theoretic functions. However, before we can use the classes they must be developed, and in this regard we shall have to get our hands dirty with the internal details. Nonetheless, it will surprise no one that we are not going to begin from scratch, but rather make use of the implementation work that we accomplished in the first part of the book and formulate the arithmetic class as an abstract layer, or shell, around our C library.

We shall give the name LINT (Large INTegers) to our class. It will contain data structures and functions as components with the attribute public, which determine the possibilities for external access. Access to the structures of the class declared as private, on the other hand, can be accomplished only with functions that have been declared either a member or friend of the class. Member functions of the class LINT can access the functions and data elements of LINT objects by name and are required for servicing the external interface, for processing instructions to the class, and serving as fundamental routines and auxiliary functions for managing and processing internal data structures. Member functions of the class LINT always possess a LINT object as implied left argument, which does not appear in its parameter list. Friend functions of the class do not belong to the class, but they can nonetheless access the internal structure of the class. Unlike the member functions, the friend functions do not possess an implicit argument.

Objects are generated as instances of a class by means of constructors, which complete the allocation of memory, the initialization of data, and other management tasks before an object is ready for action. We shall require several such constructors in order to generate our LINT objects from various contexts. Complementary to the constructors we have destructors, which serve the purpose of removing objects that are no longer needed and releasing the resources that have been bound to them.

The elements of C++ that we shall particularly use for our class development are the following:

the overloading of operators and functions;
the improved possibilities, vis à vis C, for input and output.

The following sections are devoted to the application of these two principles in the framework of our LINT class. To give the reader an idea of the form that the LINT class will assume, we show a small segment of its declaration:

 class LINT {   public:     LINT (void); // constructor     ~LINT (); // destructor     const LINT& operator= (const LINT&);     const LINT& operator+= (const LINT&);     const LINT& operator-= (const LINT&);     const LINT& operator*= (const LINT&);     const LINT& operator/= (const LINT&);     const LINT& operator     const LINT gcd (const LINT&);     const LINT lcm (const LINT&);     const int jacobi (const LINT&);     friend const LINT operator + (const LINT&, const LINT&);     friend const LINT operator - (const LINT&, const LINT&);     friend const LINT operator * (const LINT&, const LINT&);     friend const LINT operator / (const LINT&, const LINT&);     friend const LINT operator     friend const LINT mexp (const LINT&, const LINT&, const LINT&);     friend const LINT mexp (const USHORT, const LINT&, const LINT&);     friend const LINT mexp (const LINT&, const USHORT, const LINT&);     friend const LINT gcd (const LINT&, const LINT&);     friend const LINT lcm (const LINT&, const LINT&);     friend const int jacobi (const LINT&, const LINT&);   private:     clint *n_l;     int maxlen;     int init;     int status; };

One may recognize the typical subdivision into two blocks: First the public block is declared with a constructor, a destructor, arithmetic operators, and member functions as well as the friend functions of the class. A short block of private data elements is joined to the public interface, identified by the label private. It is an aid to clarity and is considered good style to place the public interface before the private block and to use the labels "public" and "private" only once each within a class declaration.

The list of operators appearing in the section of the class declaration shown here is by no means complete. It is missing some arithmetic functions that cannot be represented as operators as well as most of the number-theoretic functions, which we know already as C functions. Furthermore, the announced constructors are as little represented as the functions for input and output of LINT objects.

In the following parameter lists of the operators and functions the address operator & appears, which has the effect that objects of the class LINT are passed not by value, but by reference, that is, as pointers to the object. The same holds for the return value of LINT objects. This use of & is unknown in C. On close inspection, however, one recognizes that only certain of the member functions return a pointer to a LINT object, while most of the others return their results by value. The basic rule that determines which of these two methods is followed is this: Functions that alter one or more of the arguments passed to them can return this result as a reference, while other functions, those that do not alter their arguments, return their results by value. As we proceed we shall see which method goes with which of the LINT functions.

Classes in C++ are an extension of the complex data type struct in C, and access to an element x of a class is accomplished syntactically in the same way as access to an element of a structure, that is, by A.x, where A denotes an object and x an element of the class.

One should note that in the parameter list of a member function an argument is less completely named than in a like-named friend function, as the following example illustrates:

   friend LINT gcd (const LINT&, const LINT&);

versus

   LINT LINT::gcd (const LINT&);

Since the function gcd() as a member function of the class LINT belongs to an object A of type LINT, a call to gcd() must be in the form A.gcd(b) without A appearing in the parameter list of gcd(). In contrast, the friend function gcd() belongs to no object and thus possesses no implicit argument.

We shall fill in the above sketch of our LINT class in the following chapters and work out many of the details, so that eventually we shall have a complete implementation of the LINT class. The reader who is also interested in a general discussion of C++ is referred to the standard references [Deit], [ElSt], [Lipp], and especially [Mey1] and [Mey2].

^[1]The following, from Bjarne Stroustrup's Internet home page (http://www.research.att.com/~bs/), may help to answer the question, How do you pronounce "Bjarne Stroustrup"?: "It can be difficult for non-Scandinavians. The best suggestion I have heard yet was 'start by saying it a few times in Norwegian, then stuff a potato down your throat and do it again' :-). Both of my names are pronounced with two syllables: Bjar-ne Strou-strup. Neither the B nor the J in my first name are stressed and the NE is rather weak so maybe Be-ar-neh or By-ar-ne would give an idea. The first U in my second name really should have been a V making the first syllable end far down the throat: Strov-strup. The second U is a bit like the OO in OOP, but still short; maybe Strov-stroop will give an idea."

^[2]C++ is not the only object-oriented language. Others are Simula (the precursor of all object-oriented languages), Smalltalk, Eiffel, Oberon, and Java.

^[3]The reader is referred to several works in the standard literature for an introduction to C++ and discussions about it, namely [ElSt], [Str1], [Str2], [Deit], [Lipp], just to name a few of the more important titles. In particular, [ElSt] was taken as the basis for the standardization efforts of the ISO, which meanwhile has become standard.

Team-Fly