Chapter Summary

This chapter provides the foundations of public-key cryptology. The long compilation of mathematical concepts presented in the chapter would be indispensable for understanding the topics that follow in the next chapters.

This chapter begins with the basic concepts of sets, functions and relations. We also present the fundamental axioms of mathematics. Although the curricula of plus-two courses of many examination boards do include these topics, we planned to have a discussion on them in order to make our treatment self-sufficient.

Next comes a study of groups which are sets with binary operations satisfying some nice properties (associativity, identity, inverse and optionally commutativity). Groups are extremely important for cryptology. In particular, all discrete-log-based cryptosystems use suitable groups. Subgroups, cosets and formation of quotient groups constitute a prototypical feature that illustrates the basic paradigm of modern algebra. Secure cryptographic algorithms on groups rely on the availability of elements of large orders: for example, generators of big cyclic groups. We study these topics at length. Finally, we present Sylow’s theorem. For us, this theorem has only theoretical significance; it is used for proving some other theorems.

A set with a single operation (like a group) is often too restrictive. Many mathematical structures we are familiar with (like integers, polynomials) are endowed with two basic operations addition and multiplication. A set with two such (compatible) operations is called a ring. A study of rings, fields, ideals and quotient rings is essential in algebra (and so in cryptography too). Three important types of rings, namely unique factorization domains, principal ideal domains and Euclidean domains, are also discussed. Euclidean division is an important property of integers and polynomials, and is useful from a computational perspective.

Then, as a specific example, we study the properties of , the ring of integers. We concentrate mostly on elementary properties of integers like divisibility, congruence, Chinese remainder theorem, Fermat’s and Euler’s theorems, quadratic residues and the law of quadratic reciprocity. We finally discuss some assorted topics from analytic number theory. In cryptography, we require many big randomly generated primes. The prime number theorem guarantees that there is essentially an abundant source of primes. Smooth integers (that is, integers having only small prime divisors) are useful for modern algorithms that compute factorization and discrete logarithms. We present an estimate on the density of smooth integers. The last topic we study is the Riemann hypothesis and its generalizations. This yet unproven hypothesis has a bearing on the running times of many number-theoretic algorithms relevant to cryptology.

The next example is the ring of polynomials over a ring. Polynomials over a field admit Euclidean division and consequently unique factorization. Irreducible polynomials are useful for constructing field extensions. Extension fields of characteristic 2 are quite frequently used in cryptographic systems.

We subsequently study the theory of vector spaces. Linear transformations are appropriate maps between vector spaces and necessitate the theory of matrices. Matrix algebra is widely useful in cryptology as it is in any other branch of algorithmic computer science. Algorithms to solve linear systems over rings and fields constitute a basic computational tool. A study of modules and algebras at the end of this section is mostly theoretical and can be avoided if the reader is willing to accept some theorems without proofs.

In the next section, we discuss the theory of field extensions. As mentioned earlier, cryptography relies heavily on extension fields of characteristic 2. Some related topics include splitting fields and algebraic closure of fields. At the end of this section, we have a short theoretical treatment of Galois theory.

Many popular cryptosystems are based on the multiplicative groups of finite fields. We study these fields as the next topic. Polynomials over finite fields are extremely useful for the construction and representation of finite fields. At the end of this section, we discuss several ways in which (elements of) finite fields can be represented in a computer’s memory. This study expedites the design, analysis and efficient implementation of finite-field arithmetic.

Elliptic- and hyperelliptic-curve cryptography having gained popularity in recent years, one needs to study the theory of plane algebraic curves. This is what we do in the next three sections. To start with, we define affine and projective spaces and curves. Going from the affine space to the projective space is necessitated by a systematic (algebraic) inclusion of points at infinity on a plane curve. We also discuss the theory of divisors and the Jacobian on plane curves. For elliptic curves, the Jacobian can be replaced by the equivalent group described in terms of the chord and tangent rule. For hyperelliptic curves, on the other hand, we have little option other than understanding the Jacobian itself.

Two kinds of elliptic curves that must be avoided in cryptography are supersingular curves and anomalous curves. The elliptic curve group (over a finite field) is the basic set used in elliptic curve cryptosystems. The orders (cardinality) of these groups are given by Hasse’s theorem. The structure theorem establishes that an elliptic curve group (over a finite field) is not necessarily cyclic, but has a rank of at most two.

We then study Jacobians of hyperelliptic curves over finite fields. This study supplements the theory of divisors on general curves. Reduced and semi-reduced divisors are expedient for the representation of the elements in the Jacobian of a hyperelliptic curve.

Many popular cryptosystems (including RSA) derive their security (presumably) from the intractability of the integer factorization problem. The best algorithm known till date for factoring integers is the number-field sieve method. An understanding of this algorithm requires the knowledge of number fields and number rings. We devote a section to the study of these mathematical objects. We start with some necessary commutative algebra including localization, integral dependence and Noetherian rings. Next, we deal with Dedekind domains. All number rings are Dedekind domains in which ideals admit unique factorization. We also discuss the factorization of ideals in number rings generated by rational primes and the structure of units in number rings (Dirichlet’s unit theorem).

The next section is a gentle introduction to the theory of p-adic numbers. These numbers are useful, for example, for designing attacks against elliptic curve cryptosystems.

In the last section, we summarize some statistical tools. Under the assumption that the reader is already familiar with the elementary notion of probability, we discuss properties of random variables and of some common probability distributions (including uniform and normal distributions). The birthday paradox described in an exercise is often useful in cryptographic context (for example, for collision attacks on hash functions).

That is the end of this chapter. The compilation may initially look long and boring, perhaps intimidating too. The unfortunate reality is that public-key cryptology is mathematical, and it is arguably better to treat it in the formal way. If the reader is not comfortable with mathematics (in general), cryptology is perhaps not her cup of tea. An elementary approach to cryptology is what many other books have adopted. This book aims at being different in that respect. It is up to the reader to decide to what level of details she is willing to study cryptography.