Information
Authors
Contents
Preface
Sample Chapter
Cover
Slides
Errata
Publisher's Page
|
Theory and Practice First Edition |
| ISBN | : | 9788131708323 |
| Pages | : | 584 |
| Publisher | : | Pearson Education |
| Publication date | : | April 2009 |
Public-key Cryptography: Theory and Practice provides a comprehensive treatment of public-key cryptosystems and the associated cryptanalytic techniques. The books starts with a huge collection of mathematical tools necessary for understanding this area. Subsequently, the theory of cryptosystems based on the integer factoring problem and on various variants of the discrete logarithm problem is developed. The book then compiles IEEE and RSA-Lab standards on public-key cryptography. The book ends with a study of pactical cryptanalytic techniques like side-channel attacks and backdoor attacks, and of the implications of quantum computation on cryptography.
Symmetric cryptography (block ciphers, stream ciphers and hash functions) are handled in an appendix. Another appendix deals with key exchange in sensor networks.
The book contains a collection of over 300 exercises. Hints are provided for some difficult exercises.
The book is meant for graduate students and practitioners of cryptography. The book may be followed in undergraduate courses too. The topics of the book are graded according to their level of difficulty (unstarred, singly starred, doubly starred).
Authors
| Abhijit Das is Assistant Professor, Department of Computer Science and Engineering, Indian Institute of Technology Kharagpur. He has held academic positions at the Indian Institute of Technology Kanpur and Ruhr-Universität Bochum, Germany. His research interests include arithmetic and algebraic computations with specific applications to cryptology.
Author's Homepage |
| C. E. Veni Madhavan is Professor, Department of Computer Science and Automation, Indian Institute of Science, Bangalore. His research, teaching, and development interests include cryptography, steganography, and arithmetic, algebraic, and combinatorial algorithms.
Author's Homepage |
Contents
1. Overview
1.1 Introduction
1.2 Common Cryptographic Primitives
1.3 Public-key Cryptography
1.4 Some Cryptographic Terms
2. Mathematical Concepts
2.1 Introduction
2.2 Sets, Relations and Functions
2.3 Groups
2.4 Rings
2.5 Integers
2.6 Polynomials
2.7 Vector Spaces and Modules
2.8 Fields
2.9 Finite Fields
2.10 Affine and Projective Curves
2.11 Elliptic Curves
2.12 Hyperelliptic Curves
2.13 Number Fields
2.14 p-adic Numbers
2.15 Statistical Methods
3. Algebraic and Number-theoretic Computations
3.1 Introduction
3.2 Complexity Issues
3.3 Multiple-precision Integer Arithmetic
3.4 Elementary Number-theoretic Computations
3.5 Arithmetic in Finite Fields
3.6 Arithmetic on Elliptic Curves
3.7 Arithmetic on Hyperelliptic Curves
3.8 Random Numbers
4. The Intractable Mathematical Problems
4.1 Introduction
4.2 The Problems at a Glance
4.3 The Integer Factorization Problem
4.4 The Finite Field Discrete Logarithm Problem
4.5 The Elliptic Curve Discrete Logarithm Problem
4.6 The Hyperelliptic Curve Discrete Logarithm Problem
4.7 Solving Large Sparse Linear Systems over Finite Rings
4.8 The Subset Sum Problem
5. Cryptographic Algorithms
5.1 Introduction
5.2 Secure Transmission of Messages
5.3 Key Exchange
5.4 Digital Signatures
5.5 Entity Authentication
6. Standards
6.1 Introduction
6.2 IEEE Standards
6.3 RSA Standards
7. Cryptanalysis in Practice
7.1 Introduction
7.2 Side Channel Attacks
7.3 Backdoor Attacks
8. Quantum Computation and Cryptography
8.1 Introduction
8.2 Quantum Computation
8.3 Quantum Cryptography
8.4 Quantum Cryptanalysis
Appendices
A. Symmetric Techniques
A.1 Introduction
A.2 Block Ciphers
A.3 Stream Ciphers
A.4 Hash Functions
B. Key Exchange in Sensor Networks
B.1 Introduction
B.2 Security Issues in a Sensor Network
B.3 The Basic Bootstrapping Framework
B.4 The Basic Random Key Predistribution Scheme
B.5 Random Pairwise Scheme
B.6 Polynomial-pool-based Key Predistribution
B.7 Matrix-based Key Predistribution
B.8 Location-aware Key Predistribution
C. Complexity Theory and Cryptography
C.1 Introduction
C.2 Provably Difficult Computational Problems Are not Suitable
C.3 One-way Functions and the Complexity Class UP
D. Hints to Selected Exercises
References
Index
PDF of detailed Table of Contents (Copyright owned by the publisher)
Preface
The first moral question that we faced (like most authors) is: "Why another book?" Available textbooks on public-key cryptography (or cryptography in general) are many. In the presence of all these books, writing another may sound like a waste of energy and effort.
Fortunately, we have a big answer. Most cryptography textbooks today, even many of the celebrated ones, essentially take a narrative approach. While such an approach may be suitable for beginners at an undergraduate level, it misses the finer details in this rapidly growing area of applied mathematics. The fact that public-key cryptography is mathematical is hard to deny and a mathematical subject would be better treated in the mathematical way.
This is precisely the point that this book addresses, that is, it proceeds in a canonically mathematical way while revealing cryptographic concepts. This mathematics is often not so simple (and that is why other textbooks didn't bother to mention it), but we plan to stick to mathematical sophistication as far as possible. A typical feature of this book is that it does not rely on anything other than the readers' mathematical intuitions; it develops all the mathematical abstractions starting from scratch. Although computer science and mathematics students nowadays do undergo some courses on discrete structures somewhere in their curricula, we do not assume this; instead we develop the algebra starting at the level of set operations. Simpler structures like groups, rings and fields are followed by more complex concepts like finite fields, algebraic curves, number fields and p-adic numbers. The resulting (long) compilation of abstract mathematical tools tends to relieve cryptography students and researchers from consulting many mathematics books for understanding the background concepts. We are happy to offer this self-sufficient treatment complete with proofs and other details. The only place where we had to be somewhat sketchy is the discussion on elliptic and hyperelliptic curves. The mathematics here seems to be too vast to fit in a few pages and we opted for a deliberate simplification of these topics.
A big problem with discrete mathematics is that many of its proofs are existential. However, in order to make things work in a practical environment one must undergo algorithmic studies of algebra and number theory. This is what our book does next. While many algorithmic issues in this area are settled favourably, there remain some problems whose best known algorithmic complexities are still poor. Some of these so-called computationally difficult problems are used to build secure public-key cryptosystems. The security of these systems are assumed (rather than proven) and so we extensively deal with the algorithms known till date to solve these difficult problems. This is precisely the point that utilizes the mathematics developed in earlier chapters, to a great extent.
In Chapter 5, we eventually hit upon the culmination of all these mathematical and algorithmic studies in the design of public-key systems for achieving various cryptographic goals. Under the theoretical base developed in earlier chapters, Chapter 5 turns out to be an easy chapter. This is our way of looking into the problem, namely, a formal bottom-up approach. We claim to be different from most textbooks in this regard. Our discussion of mathematics is not for its own sake, but to develop the foundation of cryptographic primitives.
We then turn to some purely implementation and practical issues of public-key cryptography. Standards proposed by organizations such as IEEE and RSA Security Inc. promote interoperability of using crypto primitives in Internet applications. We then look at some small applications of the crypto basics. Some indirect ways of cryptanalysis are described next. These techniques (side-channel and backdoor attacks) give the book a strong practical flavour in tandem with its otherwise formal appearance.
As an eleventh-hour decision, we added a final chapter to our book, a chapter on quantum computation and its implications on public-key cryptography. Although somewhat theoretical at this point, quantum computation exhibits important ramifications in public-key cryptography. The mathematics behind quantum mechanics and computation are never discussed earlier just to highlight the distinctive nature of this chapter, which may perhaps be titled cryptography in future.
This schematic description of this book perhaps makes it clear that this book is better suited as a graduate-level textbook. A one- or two-semester graduate or advanced undergraduate course can run based on the contents of this book. Self-studying this book is also possible at an advanced graduate or research level, but is expected to be difficult at an undergraduate level. We highlight the importance of classroom teaching, if an undergraduate course is to be based on this textbook.
We rated different items in the book by their levels of difficulty and/or mathematical sophistication. Unstarred items can be covered even in undergraduate courses. Items marked by single stars can be taken seriously for a second course or a second reading. Doubly starred items, on the other hand, are research-level materials and can be pursued only in really advanced courses or for undergoing research. Inclusion of a good amount of these advanced topics marks another distinction of this book compared to other available textbooks.
The book comes with plenty of exercises. We have two-fold motivations behind these exercises. In the first place, they help the readers deepen their understanding of the matter discussed in the text. In the second place, some of these exercises build additional theory that we omit in the text proper. We occasionally make use of these additional topics in proving and/or explaining results in the text. We do not classify the exercises into easy and difficult ones, but specify hints, some of which are pretty explicit, for intellectually challenging parts. We separate out the hints in an appendix near the end of this book and leave the marker [H] in appropriate locations of the statements of the exercises. This practice prevents a reader from accidentally seeing a hint. Only when the reader gets stuck, (s)he can look at the hints at the end. We believe that the exercises, together with our discussion on algorithms and implementation issues, will offer serious students many ways to carry out substantial implementation work to further their research and development in cryptography.
Every chapter ends with annotated references for further studies. We do not claim to be encyclopaedic in this respect. Instead we mention only those references that, we feel, are directly related to the topics dealt with in the respective chapters.
As a trade-off between bulk and coverage, we had to leave many issues untouched. For example, we were limited by constraints of space to present symmetric-key cryptography in detail. However, in view of its importance today, we include brief discussions in an appendix on block ciphers, stream ciphers and hash functions. We also do not discuss anything about formal security of public-key protocols. The issues related to provable security are at the minimum theoretically important in the study of cryptography, but are entirely left out here. Only a brief discussion on the implication of complexity theory on the security of public-key protocols is included in another appendix. The Handbook of Applied Cryptography by Menezes et al. can supplement this book for learning symmetric techniques, whereas the book by Delfs and Knebl or those by Goldreich can be consulted for formal security issues.
We are indebted to everybody whose criticism, encouragement and support made this project materializable. Special thanks go to Bimal Roy, Chandan Mazumdar, C. Pandurangan, Debdeep Mukhopadhyay, Dipanwita Roychowdhury, Gagan Garg, Hartmut Wiebe, H. V. Kumar Swamy, Indranil Sengupta, Kapil Paranjape, Manindra Agarwal, Palash Sarkar, Rajesh Pillai, Rana Barua, R. Balasubramanian, Sanjay Barman, Shailesh, Satrajit Ghosh, Souvik Bhattacherjee, Srihari Vavilapalli, Subhamoy Maitra, Surjyakanta Mohapatro, and Uwe Storch. This book has been tested in postgraduate courses in the Indian Institute of Science, Bangalore, and in the Indian Institute of Technology Kharagpur. We sincerely thank all our students for pointing out many errors and suggesting several improvements. We express our deep gratitude to our family members for their constant understanding and moral support. We are also indebted to our institutes for providing the wonderful intellectual climate for completing this work.
PDF of Preface (Copyright owned by the publisher)
Sample Chapter
Pearson Education has given us permission to make the first chapter available online. However, please note that the copyright of this material vests with the publisher.
Slides
For two beginner's courses on cryptography, one of the authors prepared a set of slides [Download Link]. These slides are suitable for 10-20 hour crash courses on cryptography, and focus on both symmetric and asymmetric techniques.
Later, after the publication of the book, the slides have been reorganized and augmented so as to closely follow the structure of the book. In this present form, the slides can be used in 40-50 hour courses on cryptography at advanced undergraduate and beginning graduate levels. The slides do not provide an exhaustive coverage of the book, but are meant for students and teachers for a first course on cryptography, based on this book.
These slides are prepared by the Beamer package of LaTeX, and are to be viewed by a PDF viewer (like the Acrobat Reader). The animated slide files are of sizes 4-8 Mbytes each, whereas the non-animated ones are about 1 Mbyte each.
Errata
Readers are requested to report errors (if any is detected) to us along with their full names and affiliations. As errors are reported, we will post the list of suggested corrections at this page.