2021 | Book

# Fundamentals of Cryptography

## Introducing Mathematical and Algorithmic Foundations

Author: Dr. Duncan Buell

Publisher:

Book Series : Undergraduate Topics in Computer Science

Part of:

insite
SEARCH

Cryptography, as done in this century, is heavily mathematical. But it also has roots in what is computationally feasible.
This unique textbook text balances the theorems of mathematics against the feasibility of computation. Cryptography is something one actually “does”, not a mathematical game one proves theorems about. There is deep math; there are some theorems that must be proved; and there is a need to recognize the brilliant work done by those who focus on theory. But at the level of an undergraduate course, the emphasis should be first on knowing and understanding the algorithms and how to implement them, and also to be aware that the algorithms must be implemented carefully to avoid the “easy” ways to break the cryptography. This text covers the algorithmic foundations and is complemented by core mathematics and arithmetic.

##### 1. Introduction
Abstract
The desire of governments, generals, and even private individuals to communicate in a fashion that prevents private communications from being read by others goes back millennia. The ability of third parties to read messages not intended for them, or for messages to be unreadable by third parties, has frequently changed the path of history. The use of technology in the last 200 years has changed the process of communicating messages, first with the telegraph, then with wireless, and now with the internet. With telegraph systems based on wires, a third party needed physical access to the communication medium. With wireless radio, the transmission became public, and the need for secure communications increased. With messages sent in packets over the internet, literally anyone can be eavesdropping from anywhere in the world. In this chapter we will briefly cover some of the history, and we will define basic terms and uses that will continue through the book.
Duncan Buell
Abstract
Duncan Buell
##### 3. Divisibility, Congruences, and Modular Arithmetic
Abstract
Modern cryptography is largely based on the mathematicals of modular arithmetic, congruences, and the arithmetic in the integers modulo prime numbers or products of (usually) two large prime numbers. In this chapter we cover the basic number theory that appears in both symmetric and asymmetric cryptographic systems: divisibility and congruences, greatest common divisor, exponentiation, and the Euler totient. Our emphasis is on mathematical theorems that must be understood and used, rather than on their proofs, unless the method or constructions in the proofs are relevant to cryptography itself. Although we treat this as background mathematics, we point out that the reader can readily generate examples for all the principles that are covered as well as find examples that demonstrate why the assumptions made are necessary and the conclusions tightly drawn.
Duncan Buell
##### 4. Groups, Rings, Fields
Abstract
Modern cryptography relies, for its ability to convert plaintext into ciphertext that appears to be random sequences of symbols, on the basic notions of abstract algebra. We introduce in this chapter the basics of groups, rings, and fields, including subgroups, cyclic groups, the order of elements, and Lagrange’s Theorem. A group is a set that is closed under an operation that is usually referred to (and often is) either as addition or as multiplication, with additional properties. A ring has both an addition and a multiplication, but which may not have an operation that resembles division. A field has all the characteristics we normally associate with doing arithmetic. All three are in some sense merely descriptions in the abstract of ordinary arithmetic. Proofs will to a large extent be left to later, or not done at all. And since we are interested more in using groups, rings, and fields than in proving theorems about them as algebraic objects, this chapter can be viewed largely as simply providing definitions for and formal statements of the truth of what we observe when doing the operations for encrypting and decrypting.
Duncan Buell
##### 5. Square Roots and Quadratic Symbols
Abstract
We will do square roots modulo primes using primitive roots and exponents. This is a little different from the way that is done in many references, but we want to emphasize that it is the world of additive exponent arithmetic that is important. Modulo a prime p, the exponents work additively modulo $$p-1$$. When we get to RSA encryption, in which we have a modulus $$N = pq$$ for two large and unknown primes p and q, we cannot play the same exponent games as with primes because $$\phi (N) = (p-1)(q-1)$$ is not $$N-1$$, and it is the $$\phi (N)$$ that determines the arithmetic on the exponents. In the later chapters on factoring and elliptic curves, it will be computationally beneficial to be able to determine whether an integer is or is not congruent to a square modulo a modulus N. Fortunately, determining whether an integer is a square modulo a prime, or determining that an integer is not a square modulo a composite number, can be done by a process that resembles the gcd and has the same logarithmic complexity.
Duncan Buell
##### 6. Finite Fields of Characteristic 2
Abstract
In this chapter we extend beyond integers modulo primes to consider finite fields of characteristic 2. For a more extensive presentation of finite fields, the reader should consult Lidl and Niederreiter [1]. For a different presentation of finite fields of characteristic 2, the reader could consult Golomb [2]. Finite field arithmetic in characteristic 2 is used in the Advanced Encryption Standard (AES). It can be preferable in other cryptosystems, because computer hardware works in binary, and thus the underlying arithmetic operations needed to encrypt and decrypt can be very fast.
Duncan Buell
##### 7. Elliptic Curves
Abstract
Elliptic curves are one of the more elegant objects in algebra. A background of the underlying arithmetic of curves is necessary for cryptography, because they are used for (at least) three purposes: for factoring integers, for cryptography itself, and for key exchange. The arithmetic of elliptic curves parallels in many ways the arithmetic of integers modulo primes or composites, at least. In this chapter we present an introduction to elliptic curves as background for later chapters that use them for cryptographic purposes.
Duncan Buell
##### 8. Mathematics, Computing, and Arithmetic
Abstract
We have remarked earlier that actually doing cryptography requires combining mathematics and computing. In this chapter we describe several algorithms and computational tricks that make it possible to do the discrete mathematics that is cryptography on computers that have not necessarily been designed to provide robust support for discrete mathematics. This chapter covers a few of these tricks and algorithms necessary for understanding how one might actually do cryptography in the real world. The first set of tricks has been used extensively in testing integers for primality, using the bit patterns of the integers to eliminate the need for modular reduction. Multiprecise arithmetic is needed for much of modern cryptography, with modular reduction and multiplication dominating the cost of arithmetic. Multiplication itself is done with fast methods like the FFT, which we cover here, and reduction can be dealt with by Montgomery multiplication, which essentially extends the Mersenne prime trick to all integer moduli.
Duncan Buell
##### 9. Modern Symmetric Ciphers—DES and AES
Abstract
In a symmetric cryptosystem, the key used for encrypting a message is the same as the key used for decrypting a message. Although this does place a burden of proper key management and security on the users of such a cryptosystem, there have been two major cryptosystems, the Digital Encryption Standard (DES) and the Advanced Encryption Standard (AES), promulgated by the National Institute of Standards and Technology. DES was controversial due to the manner in which it was promulgated, and it has largely been superseded by the AES, about which almost no controversy exists. AES is currently in wide use in part because it is the NIST standard and in part because its design makes it fast and usable on a variety of platforms with different computational capabilities. This chapter covers the technical aspects of AES. Code for AES and test results appear in Appendix B so that code testing can be done and the encryption process observed.
Duncan Buell
##### 10. Asymmetric Ciphers—RSA and Others
Abstract
The notion of an asymmetric encryption system dates to the 1970s, with the first and still primary version of asymmetric encryption being the RSA algorithm of Rivest, Shamir, and Adleman. In asymmetric encryption, an encryption key that is made public is used to encrypt a message that is sent to the owner of the public key. That owner then uses a privately held key to decrypt. The RSA algorithm relies on a choice of two large primes p and q, multiplied together to produce a modulus $$N = pq$$. The public encryption key e and private decryption key d are chosen so that $$e d \equiv 1 \pmod {\phi (N)}$$. Current knowledge of the mathematics is that if N and e are public, but p, q, and d are kept private, then decrypting a message requires factoring N into p times q, and that is computationally hard. In this chapter we lay out the foundation of the RSA process, with an example, and we comment on the current records in factoring as a estimate of the security of RSA.
Duncan Buell
##### 11. How to Factor a Number
Abstract
The security of the RSA cryptosystem is based on the difficulty of factoring integers N that are the products of two large primes p and q. If p and q are chosen well, then factoring N is indeed hard, but there are also factoring methods that work very quickly on certain kinds of integers. In order to ensure security of an RSA system, one must be careful to choose an N that does not succumb to one of the faster methods. We will discuss the Pollard rho and Pollard $$p-1$$ methods first. These are not only used in general for factoring, but have been generalized to be applicable in other attacks against cryptographic systems. We then move on to CFRAC, a precursor to the state-of-the-art factoring method that is the primary topic of Chap. 12.
Duncan Buell
##### 12. How to Factor More Effectively
Abstract
In Chap. 11 we described several factoring methods. Each will succeed in factoring some integers, but none of these is a state-of-the-art method that we would expect to succeed on a well-chosen RSA $$N = pq$$. Even the best of these, CFRAC, suffers from the need to do trial division that will fail most of the time to provide any forward motion toward factoring N. In this chapter we discuss sieve methods for factoring. The primary computational benefit of a sieve method is that all the computational steps taken actually work toward finding factors, and that a sieve, stepping at constant stride through an array in memory, is highly efficient at the very lowest levels of a computing process. We discuss the Quadratic Sieve and the Multiple Polynomial Quadratic Sieve, and then finish with a nod to the current best method for factoring large “hard” integers, the Number Field Sieve.
Duncan Buell
##### 13. Cycles, Randomness, Discrete Logarithms, and Key Exchange
Abstract
With symmetric cryptography, it is necessary for the two parties who wish to communicate to have access to a common key so that one party can encrypt a message and the other party can decrypt the message. This would limit the ability of two parties who have not communicated in the past to engage in the kind of secure communication necessary for electronic commerce, for example. In this chapter we describe how number-theoretic constructs that create seemingly-random sequences of integers can be used to allow two parties to exchange information that would allow them to agree upon a common cryptographic key, even if no other communication has taken place between them. This exchange of key information can be done by exponentiation modulo a large prime number, in a manner similar to that of RSA encryption, or using elliptic curve groups in the same fashion. We will also cover the basics of the index calculus method that can be used, although with difficulty, to attack this kind of key exchange.
Duncan Buell
##### 14. Elliptic Curve Cryptography
Abstract
The first proposed asymmetric encryption scheme was that of Rivest, Shamir, and Adleman, using exponentiation in the group of integers modulo the product of two large primes. Koblitz and Miller independently proposed the use of the groups of points on elliptic curves. In this chapter we cover the algorithm for using curves for cryptography both for encryption and for key exchange. Since the arithmetic to do point addition is expensive, we include the formulas for adding points efficiently. Finally, we include the Pohlig-Hellman attack, which should not be successful if the curves are chosen properly, and the Pollard rho attack, which is the current best attack on the elliptic curve discrete log problem.
Duncan Buell
##### 15. Lattice-Based Cryptography and NTRU
Abstract
With the publication of Peter Shor’s seminal paper that factoring and discrete log computations would be entirely feasible on a quantum computer, and with advances in the building of quantum computers, there has been a focus on what is referred to as “post-quantum cryptography”. Among the most viable candidates for post-quantum cryptography are cryptosystems based on the problem of finding short vectors in lattices. In this chapter we outline briefly why quantum computers can make RSA-type cryptosystems obsolete and how lattices can be used in cryptography. We concentrate on perhaps the best-known lattice system, NTRU, and explain how it is used and why attacks on it still seem computationally infeasible.
Duncan Buell
##### 16. Homomorphic Encryption
Abstract
Shortly after the original RSA paper [1], a question was posed by Rivest, Adleman, and Dertouzos [2]: would it be possible to have a database of encrypted information (such as financial or health data), stored in an external location, that would nonetheless allow computations on the encrypted data without decrypting it? This would permit, for example, external storage, and computation on the encrypted data stored at the external site, without having to trust the owner or operator of the external site.$$\mathbb {R}^{3}$$
Duncan Buell
##### Backmatter
Title
Fundamentals of Cryptography
Author
Dr. Duncan Buell