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

所需积分/C币:12 2019-01-03 22:17:50 5.68MB PDF

密码学英文教材An Introduction to Mathematical Cryptography,讲得很好
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, ML, 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 Moreinformationaboutthisseriesathttp://www.springer.com/series/666 Jeffrey Hoffstein. Jill Pipher Joseph h. silverman An Introduction to mathematical Cryptography Second edition ②sp pringer Jeffrey hoffstein Jill Pipher Department of Mathematics Department of Mathematics Brown University Brown University Providence. rl usa Providence. RL. USA Joseph h. silverman Department of Mathematics Brown University Providence. Rl. usa ISSN0172-6056 issn 2197-5604(electronic) ISBN978-1-4939-1710-5 ISBN978-1-4939-1711-2( eBook) DOI10.1007978-1-4939-1711-2 Springer New York Heidelberg Dordrecht London Library of Congress Control Number: 2014946354 C 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, specifically the rights of translation, reprinting, reuse of illustrations, recitation broadcasting, reproduction on microfilms 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 specifically 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 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 specific 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 SpringerispartofSpringerScience+businessMedia(www.springer.com) Preface The creation of public key cryptography by Diffie 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 sufficient detail so that this book provides a self-contained course for the beginning student. The only prerequisite is a first 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 Diffie-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 final chapter very briefly describes some of the many other aspects of modern cryptography(hash functions, pseudorandom number generators Preface zero-knowledge proofs, digital cash, AES, etc. and serves to point the reader toward areas for further stud Electronic Resources: The interested reader will find 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 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 Jeffrey Hoffstein Jill pipher Joseph h. silverman Contents Preface Introduction 1 An Introduction to Cryptography 1.1 Simple substitution Ciphers 1 1.1.1 Cryptanalysis of Simple Substitution Ciphers 4 1.2 Divisibility and greatest Common Divisors 10 1.3 Modular Arithmetic 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 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 1.7.1 Symmetric Ciphers 37 1.7.2 Encoding Schemes 1.7.3 Symmetric Encryption of Encoded Blocks 40 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 Exercises 47 2 Discrete Logarithms and Diffie-Hellman 61 2.1 The Birth of Public Key Cryptography 61 2.2 The Discrete Logarithm Problem 64 2.3 Diffie-Hellman Key Exchange 67 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? ....74 2.7 A Collision Algorithm for the DLP Contents 2. 8 The Chinese Remainder Theorem 2.8.1 Solving Congruences with Composite Moduli 86 2.9 The Pohlig-Hellman algorithm ....88 2.10 Rings, Quotients, Polynomials, and Finite Fields 2.10.1 An Overview of the Theory of Rings 95 2.10.2 Divisibility and Quotient Rings 96 2.10.3 Polynomial Rings and the Euclidean Algorithm .98 2. 10.4 Polynomial Ring Quotients and Finite Fields 102 Exercises 107 3 Integer Factorization and RSA 117 3.1 Eulers Formula and Roots Modulo pq ..117 3.2 The RSA Public Key Cryptosystem 123 3.3 Implementation and Security Issues 126 3.4 Primality Testing 128 3.4.1 The Distribution of the set of primes 133 3.4.2 Primality proofs Versus Probabilistic Tests .136 3.5 Pollard,s p-1 Factorization Algorithm .137 3.6 Factorization via Difference of squares ..141 3.7 Smooth Numbers and sieves 150 3.7.1 Smooth Numbers ....150 3.7.2 The Quadratic Sieve 155 3.7.3 The number field sieve 162 3.8 The Index Calculus and Discrete Logarithms 166 3.9 Quadratic Residues and Quadratic Reciprocity ..169 3.10 Probabilistic Encryption 177 Exercises 180 4 Digital Signatures 193 4.1 What Is a Digital Signature? 193 4.2 RSA Digital Signatures 196 4.3 Elgamal digital signatures and dsa ....198 Exercises 203 5 Combinatorics, Probability, and Information Theory 207 5.1 Basic Principles of Counting 208 5.1.1 Permutations ....210 5.1.2 Combinations 211 5.1.3 The Binomial Theorem 213 5.2 The Vigenere Cipher 214 5.2.1 Cryptanalysis of the Vigenere Cipher: Theory 218 5.2.2 Cryptanalysis of the vigenere Cipher: Practice 223 5.3 Probability Theory 228 5.3.1 Basic Concepts of Probability Theory 228 Contents 5.3. 2 Bayes' s Formula 233 5.3.3 Monte Carlo Algorithms ....236 5.3.4 Random variables 238 5.3.5 Expected value 244 5.4 Collision Algorithms and Meet-in-the-Middle Attacks 246 5.4.1 The Birthday paradox ..246 5.4.2 A Collision Theorem 247 5.4.3 A Discrete Logarithm Collision Algorithm 250 5.5 Pollard's p Method 253 5.5.1 Abstract Formulation of Pollards p Method 254 5.5.2 Discrete Logarithms via Pollards p Method....... 259 5.6 Information Theory 263 5.6.1 Perfect Secrecy 263 5.6.2 Entropy 269 5.6.3 Redundancy and the Entropy of Natural language 5.6.4 The Algebra of Secrecy Systems ..277 5.7 Complexity Theory and p Versus Np ....278 Exercises .282 6 Elliptic Curves and Cryptography 299 6.1 Elliptic curves 299 6.2 Elliptic Curves over Finite Fields 306 6.3 The Elliptic Curve Discrete Logarithm Problem ..310 6.3.1 The Double-and-Add algorithm 312 6.3.2 How Hard Is the ECDLP? 315 6.4 Elliptic Curve Cryptography 316 6.4.1 Elliptic Diffie-Hellman Key Exchange 316 6.4.2 Elliptic Elgamal Public Key Cryptosystem 319 6.4.3 Elliptic Curve Signatures .321 6.5 The Evolution of Public Key Cryptography .321 6.6 Lenstra's Elliptic Curve Factorization algorithm 324 6.7 Elliptic Curves over F2 and over F2k 329 6.8 Bilinear Pairings on Elliptic curves 336 6.8.1 Points of Finite Order on Elliptic Curves 337 6.8.2 Rational Functions and Divisors on Elliptic Curves... 338 6.8.3 The Weil Pairing 340 6.8.4 An Efficient Algorithm to Compute the Weil Pairing.. 343 6.8.5 The Tate Pairing 346 6.9 The Weil Pairing over Fields of Prime Power Order .347 6.9.1 Embedding Degree and the MOv algorithm ..347 6.9.2 Distortion Maps and a Modified Weil Pairing ..350 6.9.3 A Distortion Map on +a ....352

...展开详情

评论 下载该资源后可以进行评论 1

V+ 完美!好书,上课终于不那么懵逼了
2019-07-03
回复
img
qq_41824755

关注 私信 TA的资源

上传资源赚积分,得勋章
相关内容推荐