nach oben

2016 | Buch

Kapitel lesen Erstes Kapitel lesen

Algebra for Cryptologists

verfasst von: Alko R. Meijer

Verlag: Springer International Publishing

Buchreihe : Springer Undergraduate Texts in Mathematics and Technology

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This textbook provides an introduction to the mathematics on which modern cryptology is based. It covers not only public key cryptography, the glamorous component of modern cryptology, but also pays considerable attention to secret key cryptography, its workhorse in practice.

Modern cryptology has been described as the science of the integrity of information, covering all aspects like confidentiality, authenticity and non-repudiation and also including the protocols required for achieving these aims. In both theory and practice it requires notions and constructions from three major disciplines: computer science, electronic engineering and mathematics. Within mathematics, group theory, the theory of finite fields, and elementary number theory as well as some topics not normally covered in courses in algebra, such as the theory of Boolean functions and Shannon theory, are involved.

Although essentially self-contained, a degree of mathematical maturity on the part of the reader is assumed, corresponding to his or her background in computer science or engineering. Algebra for Cryptologists is a textbook for an introductory course in cryptography or an upper undergraduate course in algebra, or for self-study in preparation for postgraduate study in cryptology.

Inhaltsverzeichnis

Frontmatter

1. Prerequisites and Notation

Abstract

In this introductory chapter we shall quickly review some mathematical concepts and in the process establish some notational conventions which we shall follow, or at least attempt to follow, in the coming chapters.

Alko R. Meijer

2. Basic Properties of the Integers

Abstract

In this chapter we consider some of the elementary properties of the integers. Many of them are really elementary and known to every school child. The algebraist’s approach to such things as greatest common divisors (alias “highest common factors”) and similar things may, however, be experienced as refreshingly different. We shall use, as before, the notation \(\mathbb{Z}\) for the set of all integers, i.e. \(\mathbb{Z} =\{\ldots,-2,-1,0,1,2,3,\ldots \}\).

Alko R. Meijer

3. Groups, Rings and Ideals

Abstract

An algebraic structure generally consists of a set, and one or more binary operations on that set, as well as a number of properties that the binary operation(s) has (have) to satisfy.

Alko R. Meijer

4. Applications to Public Key Cryptography

Abstract

In this chapter we describe, at an elementary level, some of the applications of the Group Theory and Number Theory we have developed so far to Cryptology. We emphasise that these “textbook versions” of the applications do not do justice to the complexities that arise in practice, and warn the reader that implementing the mechanisms that we discuss in the form given here would lead to severe vulnerabilities of the schemes. The reader is encouraged to start by reading the paper on Why textbook ElGamal and RSA encryption are insecure.

Alko R. Meijer

5. Fields

Abstract

In this chapter and the next we consider fields, which are rings in which the nonzero elements also form a group, under multiplication. All the classical fields, such as \(\mathbb{R}\) and \(\mathbb{C}\), are infinite. We shall instead concentrate on the finite ones and in this chapter show how one may construct them.

Alko R. Meijer

6. Properties of Finite Fields

Abstract

In this chapter we shall use the construction of the previous chapter, and discuss some of the most important properties of finite fields. While we shall generally discuss our results in terms of fields of characteristic p, in our examples we shall concentrate on the case p = 2, which is, for many applications, and especially those in secret key cryptography, the most important case. For example, in the case of Rijndael, the Advanced Encryption Standard, most of the computations take place in the field GF(2⁸).

Alko R. Meijer

7. Applications to Stream Ciphers

Abstract

In this chapter, after some general observations on stream ciphers and block ciphers and on the fundamental concept of entropy as defined in Information Theory, we apply our ideas of finite fields to linear feedback shift registers (LFSRs), a frequent component of stream cipher designs. We also discuss methods in which LFSRs are used, which brings us to the problems involved in stream cipher design, and then provide a survey of such design methods.

Alko R. Meijer

8. Boolean Functions

Abstract

Following from our previous chapter in which we noted some properties that we require in Boolean functions which are to be used as combining functions and filter functions, we now look at Boolean functions more closely. We start with an efficient way of determining the Algebraic Normal Form of a Boolean function, given its outputs for all possible inputs (and conversely) and then proceed with the Walsh–Hadamard transform and its applications to the kind of problems that we have identified. We end the chapter with a brief introduction to the Discrete Fourier Transform, where our knowledge of finite fields is required once again.

Alko R. Meijer

9. Applications to Block Ciphers

Abstract

Finite fields have for a long time been important in Applied Algebra, in particular in the theory of error correcting codes. In more recent times, they have assumed an equally important role in Cryptography, initially mainly in the generation of pseudorandom sequences and the design of stream ciphers, as we have seen. But more recently, especially since the selection of Rijndael in 2000/2001 as the Advanced Encryption Standard (AES), they have assumed a vitally important role in the design of block ciphers as well. In this chapter we discuss some aspects of these further applications.

Alko R. Meijer

10. Number Theory in Public Key Cryptography

Abstract

We have already dealt with two of the most important applications of number theory, namely the difficulty of factoring as used in the RSA public key system, and the difficulty of the discrete logarithm problem in Diffie–Hellman key establishment and ElGamal encryption. It is worthwhile recalling that until as recently as 1976, when Diffie and Hellman’s famous paper appeared, it was generally thought to be impossible to encrypt a message from Alice to Bob, if Alice and Bob had not previously obtained a secret key. Until then number theory was seen as the “Queen of Mathematics”, which is how Gauss described it, and as one would like a queen to be, this could (somewhat rudely) be construed as meaning “beautiful, but of no practical value”.

Alko R. Meijer

11. Where Do We Go from Here?

Abstract

The purpose of the book which you have just completed was to highlight the most basic of the mathematical, and in particular the algebraic, aspects of modern cryptography. In the process we have covered quite a lot of ground, but even so we have barely scratched its surface. So in these concluding remarks, we shall indicate where you may dig deeper and also refer you to matters which have been left out of discussion altogether, some because the algebraic content is negligible or uninteresting, others simply because we wanted to keep the size of the book within reasonable bounds.

Alko R. Meijer

Backmatter

Titel: Algebra for Cryptologists
verfasst von: Alko R. Meijer
Verlag: Springer International Publishing
Electronic ISBN: 978-3-319-30396-3
Print ISBN: 978-3-319-30395-6
DOI: https://doi.org/10.1007/978-3-319-30396-3

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

1. Prerequisites and Notation

2. Basic Properties of the Integers

3. Groups, Rings and Ideals

4. Applications to Public Key Cryptography

5. Fields

6. Properties of Finite Fields

7. Applications to Stream Ciphers

8. Boolean Functions

9. Applications to Block Ciphers

10. Number Theory in Public Key Cryptography

11. Where Do We Go from Here?

Backmatter

Premium Partner