密码学英文教材An Introduction to Mathematical Cryptography.pdf

发布时间：2022-06-06 发布人：admin 分类：说明书资料大小：5.68M 资料格式：pdf 举报版权申诉

qq_41824755-10894316-4744302542915959282.pdf-第1页.png

第1页 / 共549页

qq_41824755-10894316-4744302542915959282.pdf-第2页.png

第2页 / 共549页

qq_41824755-10894316-4744302542915959282.pdf-第3页.png

第3页 / 共549页

qq_41824755-10894316-4744302542915959282.pdf-第4页.png

第4页 / 共549页

qq_41824755-10894316-4744302542915959282.pdf-第5页.png

第5页 / 共549页

qq_41824755-10894316-4744302542915959282.pdf-第6页.png

第6页 / 共549页

qq_41824755-10894316-4744302542915959282.pdf-第7页.png

第7页 / 共549页

qq_41824755-10894316-4744302542915959282.pdf-第8页.png

第8页 / 共549页

Preface

Contents

Introduction

1 An Introduction to Cryptography

1.1 Simple Substitution Ciphers

1.1.1 Cryptanalysis of Simple Substitution Ciphers

1.2 Divisibility and Greatest Common Divisors

1.3 Modular Arithmetic

1.3.1 Modular Arithmetic and Shift Ciphers

1.3.2 The Fast Powering Algorithm

1.4 Prime Numbers, Unique Factorization, and Finite Fields

1.5 Powers and Primitive Roots in Finite Fields

1.6 Cryptography Before the Computer Age

1.7 Symmetric and Asymmetric Ciphers

1.7.1 Symmetric Ciphers

1.7.2 Encoding Schemes

1.7.3 Symmetric Encryption of Encoded Blocks

1.7.4 Examples of Symmetric Ciphers

1.7.5 Random Bit Sequences and Symmetric Ciphers

1.7.6 Asymmetric Ciphers Make a First Appearance

Exercises

2 Discrete Logarithms and Diffie–Hellman

2.1 The Birth of Public Key Cryptography

2.2 The Discrete Logarithm Problem

2.3 Diffie–Hellman Key Exchange

2.4 The Elgamal Public Key Cryptosystem

2.5 An Overview of the Theory of Groups

2.6 How Hard Is the Discrete Logarithm Problem?

2.7 A Collision Algorithm for the DLP

2.8 The Chinese Remainder Theorem

2.8.1 Solving Congruences with Composite Moduli

2.9 The Pohlig–Hellman Algorithm

2.10 Rings, Quotients, Polynomials, and Finite Fields

2.10.1 An Overview of the Theory of Rings

2.10.2 Divisibility and Quotient Rings

2.10.3 Polynomial Rings and the Euclidean Algorithm

2.10.4 Polynomial Ring Quotients and Finite Fields

Exercises

3 Integer Factorization and RSA

3.1 Euler's Formula and Roots Modulo pq

3.2 The RSA Public Key Cryptosystem

3.3 Implementation and Security Issues

3.4 Primality Testing

3.4.1 The Distribution of the Set of Primes

3.4.2 Primality Proofs Versus Probabilistic Tests

3.5 Pollard's p-1 Factorization Algorithm

3.6 Factorization via Difference of Squares

3.7 Smooth Numbers and Sieves

3.7.1 Smooth Numbers

3.7.2 The Quadratic Sieve

3.7.3 The Number Field Sieve

3.8 The Index Calculus and Discrete Logarithms

3.9 Quadratic Residues and Quadratic Reciprocity

3.10 Probabilistic Encryption

Exercises

4 Digital Signatures

4.1 What Is a Digital Signature?

4.2 RSA Digital Signatures

4.3 Elgamal Digital Signatures and DSA

Exercises

5 Combinatorics, Probability, and Information Theory

5.1 Basic Principles of Counting

5.1.1 Permutations

5.1.2 Combinations

5.1.3 The Binomial Theorem

5.2 The Vigenère Cipher

5.2.1 Cryptanalysis of the Vigenère Cipher: Theory

5.2.2 Cryptanalysis of the Vigenère Cipher: Practice

5.3 Probability Theory

5.3.1 Basic Concepts of Probability Theory

5.3.2 Bayes's Formula

5.3.3 Monte Carlo Algorithms

5.3.4 Random Variables

5.3.5 Expected Value

5.4 Collision Algorithms and Meet-in-the-Middle Attacks

5.4.1 The Birthday Paradox

5.4.2 A Collision Theorem

5.4.3 A Discrete Logarithm Collision Algorithm

5.5 Pollard's ρ Method

5.5.1 Abstract Formulation of Pollard's ρ Method

5.5.2 Discrete Logarithms via Pollard's ρ Method

5.6 Information Theory

5.6.1 Perfect Secrecy

5.6.2 Entropy

5.6.3 Redundancy and the Entropyof Natural Language

5.6.4 The Algebra of Secrecy Systems

5.7 Complexity Theory and P Versus NP

Exercises

6 Elliptic Curves and Cryptography

6.1 Elliptic Curves

6.2 Elliptic Curves over Finite Fields

6.3 The Elliptic Curve Discrete Logarithm Problem

6.3.1 The Double-and-Add Algorithm

6.3.2 How Hard Is the ECDLP?

6.4 Elliptic Curve Cryptography

6.4.1 Elliptic Diffie–Hellman Key Exchange

6.4.2 Elliptic Elgamal Public Key Cryptosystem

6.4.3 Elliptic Curve Signatures

6.5 The Evolution of Public Key Cryptography

6.6 Lenstra's Elliptic Curve Factorization Algorithm

6.7 Elliptic Curves over F2 and over F2k

6.8 Bilinear Pairings on Elliptic Curves

6.8.1 Points of Finite Order on Elliptic Curves

6.8.2 Rational Functions and Divisors on Elliptic Curves

6.8.3 The Weil Pairing

6.8.4 An Efficient Algorithm to Compute the Weil Pairing

6.8.5 The Tate Pairing

6.9 The Weil Pairing over Fields of Prime Power Order

6.9.1 Embedding Degree and the MOV Algorithm

6.9.2 Distortion Maps and a Modified Weil Pairing

6.9.3 A Distortion Map on y2=x3+x

6.10 Applications of the Weil Pairing

6.10.1 Tripartite Diffie–Hellman Key Exchange

6.10.2 ID-Based Public Key Cryptosystems

Exercises

7 Lattices and Cryptography

7.1 A Congruential Public Key Cryptosystem

7.2 Subset-Sum Problems and Knapsack Cryptosystems

7.3 A Brief Review of Vector Spaces

7.4 Lattices: Basic Definitions and Properties

7.5 Short Vectors in Lattices

7.5.1 The Shortest and the Closest Vector Problems

7.5.2 Hermite's Theorem and Minkowski's Theorem

7.5.3 The Gaussian Heuristic

7.6 Babai's Algorithm

7.7 Cryptosystems Based on Hard Lattice Problems

7.8 The GGH Public Key Cryptosystem

7.9 Convolution Polynomial Rings

7.10 The NTRU Public Key Cryptosystem

7.10.1 NTRUEncrypt

7.10.2 Mathematical Problems for NTRUEncrypt

7.11 NTRUEncrypt as a Lattice Cryptosystem

7.11.1 The NTRU Lattice

7.11.2 Quantifying the Security of an NTRU Lattice

7.12 Lattice-Based Digital Signature Schemes

7.12.1 The GGH Digital Signature Scheme

7.12.2 Transcript Analysis

7.12.3 Rejection Sampling

7.12.4 Rejection Sampling Applied to an Abstract Signature Scheme

7.12.5 The NTRU Modular Lattice Signature Scheme

7.13 Lattice Reduction Algorithms

7.13.1 Gaussian Lattice Reduction in Dimension 2

7.13.2 The LLL Lattice Reduction Algorithm

7.13.3 Using LLL to Solve apprCVP

7.13.4 Generalizations of LLL

7.14 Applications of LLL to Cryptanalysis

7.14.1 Congruential Cryptosystems

7.14.2 Applying LLL to Knapsacks

7.14.3 Applying LLL to GGH

7.14.4 Applying LLL to NTRU

Exercises

8 Additional Topics in Cryptography

8.1 Hash Functions

8.2 Random Numbers and Pseudorandom Number

8.3 Zero-Knowledge Proofs

8.4 Secret Sharing Schemes

8.5 Identification Schemes

8.6 Padding Schemes and the Random Oracle Model

8.7 Building Protocols from Cryptographic Primitives

8.8 Blind Digital Signatures, Digital Cash, and Bitcoin

8.9 Homomorphic Encryption

8.10 Hyperelliptic Curve Cryptography

8.11 Quantum Computing

8.12 Modern Symmetric Cryptosystems: DES and AES

List of Notation

References

Index

Undergraduate Texts in Mathematics Je reyHo stein JillPipher Joseph H.Silverman An Introduction to Mathematical Cryptography Second Edition

Undergraduate Texts in Mathematics

Undergraduate Texts in Mathematics Series Editors: Sheldon Axler San Francisco State University, San Francisco, CA, USA Kenneth Ribet University of California, Berkeley, CA, USA Advisory Board: Colin Adams, Williams College, Williamstown, MA, USA Alejandro Adem, University of British Columbia, Vancouver, BC, Canada Ruth Charney, Brandeis University, Waltham, MA, USA Irene M. Gamba, The University of Texas at Austin, Austin, TX, USA Roger E. Howe, Yale University, New Haven, CT, USA David Jerison, Massachusetts Institute of Technology, Cambridge, MA, USA Jeffrey C. Lagarias, University of Michigan, Ann Arbor, MI, USA Jill Pipher, Brown University, Providence, RI, USA Fadil Santosa, University of Minnesota, Minneapolis, MN, USA Amie Wilkinson, University of Chicago, Chicago, IL, USA Undergraduate Texts in Mathematics are generally aimed at third- and fourth- year undergraduate mathematics students at North American universities. These texts strive to provide students and teachers with new perspectives and novel approaches. The books include motivation that guides the reader to an appreciation of interre- lations among different aspects of the subject. They feature examples that illustrate key concepts as well as exercises that strengthen understanding. More information about this series at http://www.springer.com/series/666

Jeffrey Hoffstein • Jill Pipher Joseph H. Silverman An Introduction to Mathematical Cryptography Second Edition 123

Jeffrey Hoffstein Department of Mathematics Brown University Providence, RI, USA Joseph H. Silverman Department of Mathematics Brown University Providence, RI, USA Jill Pipher Department of Mathematics Brown University Providence, RI, USA ISSN 0172-6056 ISBN 978-1-4939-1710-5 DOI 10.1007/978-1-4939-1711-2 Springer New York Heidelberg Dordrecht London ISSN 2197-5604 (electronic) ISBN 978-1-4939-1711-2 (eBook) Library of Congress Control Number: 2014946354 © Springer Science+Business Media New York 2008, 2014 This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, speciﬁcally the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microﬁlms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. Exempted from this legal reservation are brief excerpts in connection with reviews or scholarly analysis or material supplied speciﬁcally for the purpose of being entered and executed on a computer system, for exclusive use by the purchaser of the work. Duplication of this pub- lication or parts thereof is permitted only under the provisions of the Copyright Law of the Publisher’s location, in its current version, and permission for use must always be obtained from Springer. Permis- sions for use may be obtained through RightsLink at the Copyright Clearance Center. Violations are liable to prosecution under the respective Copyright Law. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a speciﬁc statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. While the advice and information in this book are believed to be true and accurate at the date of publica- tion, neither the authors nor the editors nor the publisher can accept any legal responsibility for any errors or omissions that may be made. The publisher makes no warranty, express or implied, with respect to the material contained herein. Printed on acid-free paper Springer is part of Springer Science+Business Media (www.springer.com)

Preface The creation of public key cryptography by Diﬃe and Hellman in 1976 and the subsequent invention of the RSA public key cryptosystem by Rivest, Shamir, and Adleman in 1978 are watershed events in the long history of secret com- munications. It is hard to overestimate the importance of public key cryp- tosystems and their associated digital signature schemes in the modern world of computers and the Internet. This book provides an introduction to the theory of public key cryptography and to the mathematical ideas underlying that theory. Public key cryptography draws on many areas of mathematics, including number theory, abstract algebra, probability, and information theory. Each of these topics is introduced and developed in suﬃcient detail so that this book provides a self-contained course for the beginning student. The only prerequisite is a ﬁrst course in linear algebra. On the other hand, students with stronger mathematical backgrounds can move directly to cryptographic applications and still have time for advanced topics such as elliptic curve pairings and lattice-reduction algorithms. Among the many facets of modern cryptography, this book chooses to con- centrate primarily on public key cryptosystems and digital signature schemes. This allows for an in-depth development of the necessary mathematics re- quired for both the construction of these schemes and an analysis of their security. The reader who masters the material in this book will not only be well prepared for further study in cryptography, but will have acquired a real understanding of the underlying mathematical principles on which modern cryptography is based. Topics covered in this book include Diﬃe–Hellman key exchange, discrete logarithm based cryptosystems, the RSA cryptosystem, primality testing, fac- torization algorithms, digital signatures, probability theory, information the- ory, collision algorithms, elliptic curves, elliptic curve cryptography, pairing- based cryptography, lattices, lattice-based cryptography, and the NTRU cryp- tosystem. A ﬁnal chapter very brieﬂy describes some of the many other aspects of modern cryptography (hash functions, pseudorandom number generators, v

vi Preface zero-knowledge proofs, digital cash, AES, etc.) and serves to point the reader toward areas for further study. Electronic Resources: The interested reader will ﬁnd additional material and a list of errata on the Mathematical Cryptography home page: www.math.brown.edu/~jhs/MathCryptoHome.html This web page includes many of the numerical exercises in the book, allowing the reader to cut and paste them into other programs, rather than having to retype them. No book is ever free from error or incapable of being improved. We would be delighted to receive comments, good or bad, and corrections from our readers. You can send mail to us at mathcrypto@math.brown.edu Acknowledgments: We, the authors, would like the thank the following individuals for test-driving this book and for the many corrections and helpful suggestions that they and their students provided: Liat Berdugo, Alexander Collins, Samuel Dickman, Michael Gartner, Nicholas Howgrave-Graham, Su- Ion Ih, Saeja Kim, Yuji Kosugi, Yesem Kurt, Michelle Manes, Victor Miller, David Singer, William Whyte. In addition, we would like to thank the many students at Brown University who took Math 158 and helped us improve the exposition of this book. Acknowledgments for the Second Edition: We would like to thank the following individuals for corrections and suggestions that have been incorporated into the second edition: Stefanos Aivazidis, Nicole Andre, John B. Baena, Carlo Beenakker, Robert Bond, Reinier Broker, Camp- bell Hewett, Rebecca Constantine, Stephen Constantine, Christopher Davis, Maria Fox, Steven Galbraith, Motahhareh Gharahi, David Hartz, Jeremy Huddleston, Calvin Jongsma, Maya Kaczorowski, Yamamoto Kato, Jonathan Katz, Chan-Ho Kim, Ariella Kirsch, Martin M. Lauridsen, Kelly McNeilly, Ryo Masuda, Shahab Mirzadeh, Kenneth Ribet, Jeremy Roach, Hemlal Sahum, Ghassan Sarkis, Frederick Schmitt, Christine Schwartz, Wei Shen, David Singer, Michael Soltys, David Spies, Bruce Stephens, Paulo Tanimoto, Patrick Vogt, Ralph Wernsdorf, Sebastian Welsch, Ralph Wernsdorf, Edward White, Pomona College Math 113 (Spring 2009), University of California at Berkeley Math 116 (Spring 2009, 2010). Providence, USA Jeﬀrey Hoﬀstein Jill Pipher Joseph H. Silverman

Contents Preface Introduction v xiii 1 An Introduction to Cryptography 1.1 Simple Substitution Ciphers . . . . . . . . . . . . . . . . . . . . 1.1.1 Cryptanalysis of Simple Substitution Ciphers . . . . . . 1 1 4 . . . . . . . . . . . 10 1.2 Divisibility and Greatest Common Divisors 1.3 Modular Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . 19 1.3.1 Modular Arithmetic and Shift Ciphers . . . . . . . . . . 23 1.3.2 The Fast Powering Algorithm . . . . . . . . . . . . . . . 24 1.4 Prime Numbers, Unique Factorization, and Finite Fields . . . . 26 1.5 Powers and Primitive Roots in Finite Fields . . . . . . . . . . . 29 1.6 Cryptography Before the Computer Age . . . . . . . . . . . . 34 1.7 Symmetric and Asymmetric Ciphers . . . . . . . . . . . . . . . 37 Symmetric Ciphers . . . . . . . . . . . . . . . . . . . . . 37 1.7.1 1.7.2 Encoding Schemes . . . . . . . . . . . . . . . . . . . . . 39 Symmetric Encryption of Encoded Blocks . . . . . . . . 40 1.7.3 1.7.4 Examples of Symmetric Ciphers . . . . . . . . . . . . . 41 1.7.5 Random Bit Sequences and Symmetric Ciphers . . . . . 44 1.7.6 Asymmetric Ciphers Make a First Appearance . . . . . 46 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 Exercises 2 Discrete Logarithms and Diﬃe–Hellman 61 2.1 The Birth of Public Key Cryptography . . . . . . . . . . . . . 61 2.2 The Discrete Logarithm Problem . . . . . . . . . . . . . . . . . 64 2.3 Diﬃe–Hellman Key Exchange . . . . . . . . . . . . . . . . . . . 67 2.4 The Elgamal Public Key Cryptosystem . . . . . . . . . . . . . 70 2.5 An Overview of the Theory of Groups . . . . . . . . . . . . . . 74 2.6 How Hard Is the Discrete Logarithm Problem? . . . . . . . . . 77 2.7 A Collision Algorithm for the DLP . . . . . . . . . . . . . . . 81 vii

分享到：

赞收藏

资料库

密码学英文教材An Introduction to Mathematical Cryptography.pdf

相关推荐

安全技术

热门标签

最新资料