nach oben

2013 | Buch

Introduction to Cryptography with Maple

verfasst von: José Luis Gómez Pardo

Verlag: Springer Berlin Heidelberg

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

Einloggen, um Zugang zu erhalten

Über dieses Buch

This introduction to cryptography employs a programming-oriented approach to study the most important cryptographic schemes in current use and the main cryptanalytic attacks against them. Discussion of the theoretical aspects, emphasizing precise security definitions based on methodological tools such as complexity and randomness, and of the mathematical aspects, with emphasis on number-theoretic algorithms and their applications to cryptography and cryptanalysis, is integrated with the programming approach, thus providing implementations of the algorithms and schemes as well as examples of realistic size.

A distinctive feature of the author's approach is the use of Maple as a programming environment in which not just the cryptographic primitives but also the most important cryptographic schemes are implemented following the recommendations of standards bodies such as NIST, with many of the known cryptanalytic attacks implemented as well. The purpose of the Maple implementations is to let the reader experiment and learn, and for this reason the author includes numerous examples. The book discusses important recent subjects such as homomorphic encryption, identity-based cryptography and elliptic curve cryptography. The algorithms and schemes which are treated in detail and implemented in Maple include AES and modes of operation, CMAC, GCM/GMAC, SHA-256, HMAC, RSA, Rabin, Elgamal, Paillier, Cocks IBE, DSA and ECDSA. In addition, some recently introduced schemes enjoying strong security properties, such as RSA-OAEP, Rabin-SAEP, Cramer--Shoup, and PSS, are also discussed and implemented. On the cryptanalysis side, Maple implementations and examples are used to discuss many important algorithms, including birthday and man-in-the-middle attacks, integer factorization algorithms such as Pollard's rho and the quadratic sieve, and discrete log algorithms such as baby-step giant-step, Pollard's rho, Pohlig--Hellman and the index calculus method.

This textbook is suitable for advanced undergraduate and graduate students of computer science, engineering and mathematics, satisfying the requirements of various types of courses: a basic introductory course; a theoretically oriented course whose focus is on the precise definition of security concepts and on cryptographic schemes with reductionist security proofs; a practice-oriented course requiring little mathematical background and with an emphasis on applications; or a mathematically advanced course addressed to students with a stronger mathematical background. The main prerequisite is a basic knowledge of linear algebra and elementary calculus, and while some knowledge of probability and abstract algebra would be helpful, it is not essential because the book includes the necessary background from these subjects and, furthermore, explores the number-theoretic material in detail. The book is also a comprehensive reference and is suitable for self-study by practitioners and programmers.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Classical Ciphers and Their Cryptanalysis

Abstract

The object of this chapter is to examine some symmetric encryption schemes that are of historical interest. From this analysis it will turn out that all of them are easy to cryptanalyze. Thus their interest is not because they can be used in practice but, rather, because their cryptanalysis gives us valuable information about some kinds of attacks that have been tried and that should be prevented when designing an encryption scheme. This chapter has an introductory nature and in it we use only very basic mathematical notions, mainly from modular arithmetic, elementary probability and statistics, and linear algebra. Modular arithmetic and probability are reviewed in the next chapter in more detail than is required to understand the ciphers presented here, and we refer to that chapter for further background. At the same time, we use Maple to implement and to cryptanalyze these schemes and this also serves as an introduction to the Maple programming environment that we will be using throughout.

José Luis Gómez Pardo

Chapter 2. Basic Concepts from Probability, Complexity, Algebra and Number Theory

Abstract

In this chapter we study the basic notions from mathematics and computer science that we will be using throughout the book. Its purpose is not to give a comprehensive account of these concepts but, rather, to study them from the point of view of their applications to cryptography, emphasizing the algorithmic aspects. For this task we will be using Maple as a tool to implement the relevant algorithms and to experiment with them. Bearing in mind these premises, we include here the required concepts and results from probability, complexity theory and modular arithmetic, including quadratic residues and modular square roots, and we also give a brief introduction to the relevant aspects of group theory and finite fields. Thus, for readers already familiar with these subjects, this chapter will hopefully serve as a refresher of the topics mentioned in the Preface (with the exception of linear algebra which is not included here) and, at the same time, as an introduction to the use of Maple to explore the algorithms discussed. Even for readers not familiar with these subjects we hope that sufficient information is included here to allow them to profitably read the rest of the book. We include proofs of most of the algorithmic and mathematical results mentioned, with pointers to the literature for the reader who wishes to go deeper on these topics and, at the same time, we will be introducing here a great deal of the notation used throughout the book.

José Luis Gómez Pardo

Chapter 3. Private-Key Encryption

Abstract

In this chapter we introduce the basic ideas and concepts underlying private-key encryption (also called symmetric encryption). Particularly important is the concept of security, which for the classical ciphers studied in the first chapter was not precisely defined. Thus we shall start by looking at the first rigorous definition for this concept, namely perfect secrecy which, while providing the strongest security assurance, has important practical disadvantages that motivate the introduction of computational security concepts that are more suited for practical use. These notions are defined with the help of complexity theory and the concept of pseudorandomness, a weakening of randomness that takes into account the fact that computational resources are limited. The security notions also make use of the concepts of one-way function and pseudo-random generator, which are of crucial importance for cryptography and are also introduced here.

José Luis Gómez Pardo

Chapter 4. Block Ciphers and Modes of Operation

Abstract

Most modern private-key encryption schemes are built from two ingredients: a block cipher and a mode of operation. Block ciphers are cryptographic primitives that provide encryption and decryption functions which operate on strings of a fixed size (blocks). The modes of operation act on top of block ciphers and allow the encryption of arbitrary length messages and also provide the probabilistic encryption necessary for the system to be secure. In this chapter we are going to look at these constructions and, in particular, at the most used block cipher today: the Advanced Encryption Standard.

José Luis Gómez Pardo

Chapter 5. Message Authentication

Abstract

Since ancient times, cryptography has been closely associated with providing confidentiality and so it is often implicitly or explicitly identified with the use of encryption and decryption. But, important as confidentiality is, modern cryptography goes far beyond this objective and message authentication and message integrity are perhaps even more important goals. In this chapter we will look at techniques that provide message integrity in the private-key setting, in which the honest parties share some secret key. These techniques will try to guarantee that any modification of the message will be detected by the honest parties.

José Luis Gómez Pardo

Chapter 6. Algorithmic Number Theory for Cryptography and Cryptanalysis: Primality, Factoring and Discrete Logarithms

Abstract

In the previous chapters we have introduced the most important aspects of private-key cryptography and we have noticed that prime numbers underlie many of the constructions and algorithms discussed. Also, computational number-theoretic problems which are presumed to be hard made their appearance and we mentioned, in particular, the integer factorization problem and the discrete logarithm problem. In the coming chapters we will study publickey cryptography and we will see that all these aspects play a relevant role in this setting. In fact, number theory and, in particular, presumedly hard number-theoretic problems such as the ones just mentioned, are of central importance for public-key cryptography because the security of most public-key schemes relies on the hardness of some of these problems. The study of the known algorithms to solve these hard problems can thus be seen as a form of cryptanalysis and, as such, is an indispensable complement to cryptography and a prerequisite for the practical evaluation of the security of public-key schemes in order to establish, for example, the key sizes that should be used. Thus we devote this chapter to the aspects of algorithmic number theory which are most relevant to public-key cryptographic schemes.

José Luis Gómez Pardo

Chapter 7. Introduction to Public-Key Cryptography: The Diffie–Hellman Protocol

Abstract

The private-key encryption schemes studied in the preceding chapters have some drawbacks when used in the context of modern communication networks. The main inconvenience is that, when using such a scheme, the communicating parties need a secure channel to exchange the secret key. In this chapter we present an introduction to the ideas underlying public-key cryptography, which removes this inconvenience. We illustrate some of these ideas with the very first public-key protocol, namely, the Diffie-Hellman key agreement.

José Luis Gómez Pardo

Chapter 8. Public-Key Encryption

Abstract

The preceding chapter offered a brief glimpse at the origins of public-key cryptography, which was born with the purpose of enabling secure communication between two parties that do not have to share a common secret key. Public-key cryptography started with the realization that it should be possible to design encryption schemes in which it is computationally infeasible to find the decryption algorithm from the encryption one. This, in turn, entails that the same key cannot be used for both encryption and decryption as happens in private-key cryptography, and leads to each user having two keys: a public key which is used for encryption and a private key which is used for decryption. This chapter is devoted to the study of these public-key encryption schemes.

José Luis Gómez Pardo

Chapter 9. Digital Signatures

Abstract

One of the main goals of modern cryptography is to guarantee the authenticity and the integrity of the messages received, which is of the utmost importance in fields like ecomerce and e-banking, where physical protection of exchanged data is impossible. A reasonable guarantee of data authenticity in the private-key setting can be obtained by using a MAC. However, the requirement that the parties share a secret key severely limits the applicability of these schemes and, moreover, MACs do not provide non-repudiation and allow the possibility that the sender of an authenticated message might later repudiate it. These problems are solved with the use of digital signatures, that serve to guarantee authenticity in the public-key setting, and are studied in this chapter.

José Luis Gómez Pardo

Chapter 10. Identity-Based Cryptography

Abstract

This chapter is devoted to giving a brief introduction to identity-based cryptography (IBC), which presents a nice solution for some problems that limit the wide deployment of public-key cryptography, in particular, the problem of binding public keys with user identities. The basic idea of IBC starts from the realization that there is some minimal information that a user has to learn before communicating with another party, even in unencrypted form, namely, some identity information such as, for example, an email address. In IBC, this basic informacion replaces the need for a public key or, in slightly different terms, the public key of a user is her identity string or some string easily derivable from this identity by a specified method.

José Luis Gómez Pardo

Chapter 11. An Introduction to Elliptic Curve Cryptography

Abstract

This chapter presents an introduction to elliptic curve cryptography. Elliptic curves provide an important source of finite abelian groups in which cryptographic schemes relying on the hardness of the discrete logarithm problem (DLP) can be implemented. One important advantage of elliptic curve groups over other finite abelian groups such as the subgroups of the multiplicative groups of finite fields is the fact that in the elliptic case only generic algorithms—which have exponential complexity—are known for the DLP and this allows the use of smaller parameters, which is advantageous in restricted computing environments such as, for example, smart cards. Another advantage is that they provide an appropriate context for the development of identity-based cryptography.

José Luis Gómez Pardo

Backmatter

Titel: Introduction to Cryptography with Maple
verfasst von: José Luis Gómez Pardo
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-642-32166-5
Print ISBN: 978-3-642-32165-8
DOI: https://doi.org/10.1007/978-3-642-32166-5