Undergraduate Texts in Mathematics - download.e …

1 Undergraduate Texts in MathematicsEditorsS. RibetUndergraduate Texts in MathematicsAbbott:Understanding : Mathematics : A Concise History in :The Heritage of in :Introduction to Analytic Number :Basic :Groups and :Linear Algebra Done Right. Second :Limits: A New Approach to Real :Complex Analysis. Second :Linear Algebra ThroughGeometry. Second :Computing the Continuous DiscretelyBerberian:A First Course in Real :Conics and Cubics: A Concrete Introduction toAlgebraic Curves. Second `emaud:An Introduction to Probabilistic :Factorization and Primality :Second Year in :Mathematical Introduction to LinearProgramming and Game :Mathematical Analysis: An :Introduction to Cryptography. Rooij:Topological Spaces: FromDistance to :The Geometry of Spacetime: AnIntroduction to Special and General Brunt:The Lebesgue Stieltjes Integral:A Practical :A Course in Modern Geometries.

2 :A Field Guide to AlgebraChilds:A Concrete Introduction to Higher :Elementary Probability Theory:With Stochastic Processes and an Introduction toMathematical Finance. Fourth Shea:Ideals, Varieties, and :Basic Concepts of Algebraic :Difference Equations. FromRabbits to ChaosCurtis:Linear Algebra: An Introductory :Reading, Writing, and Proving:A Closer Look at :The Joy of Sets: Fundamentalsof-Contemporary Set Theory. Second :General :Why Math?Ebbinghaus/Flum/Thomas:Mathematical :Measure, Topology, and Fractal :An Introduction to Difference s/Sur anyi:Topics in the Theory of :Practical Analysis on One :An Accompaniment to Higher :Inside :The Fundamental Theoryof :Intermediate Real :Calculus Two: Linear andNonlinear Functions. Second :Functions of Several Variables. :Combinatorial Optimization :Optimization Techniques: An :Methods of :An Introduction to Wavelets Through :Complex :A Course in Calculus and RealAnalysisGordon:Discrete :Analysis by Its in :Finite-Dimensional Vector Spaces.

3 :Naive Set ammerlin/Hoffmann:Numerical in :Combinatorics andGraph :Geometry: Euclid and :Introduction to Calculus and ClassicalAnalysis. Second :Mathematical Reflections:In a Room with Many :Mathematical Vistas: Froma Room with Many :An Introduction toMathematical :Elementary Stability and BifurcationTheory. Second Edition.(continued after index)Jeffrey HoffsteinJill PipherJoseph H. SilvermanAn Introduction toMathematical Cryptography123 Jeffrey HoffsteinJill PipherDepartment of MathematicsDepartment of MathematicsBrown UniversityBrown University151 Thayer Thayer , RI 02912 Providence, RI H. SilvermanDepartment of MathematicsBrown University151 Thayer , RI BoardS. RibetMathematics DepartmentDepartment of MathematicsSan Francisco State UniversityUniversity of CaliforniaSan Francisco, CA 94132at BerkeleyUSAB erkeley, CA 978-0-387-77993-5e-ISBN: 978-0-387-77994-2 DOI: of Congress Control Number: 2008923038 Mathematics Subject Classification (2000): 94A60, 11T71, 14G50, 68P25c 2008 Springer Science+Business Media, LLCAll rights reserved.

4 This work may not be translated or copied in whole or in part without the writtenpermission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York, NY10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connec-tion with any form of information storage and retrieval, electronic adaptation, computer software, or bysimilar or dissimilar methodology now known or hereafter developed is use in this publication of trade names, trademarks, service marks, and similar terms, even if they arenot identified as such, is not to be taken as an expression of opinion as to whether or not they are subjectto proprietary on acid-free creation of public key cryptography by Diffie and Hellman in 1976 and thesubsequent 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.

5 It is hard to overestimate the importance of public key cryp-tosystems and their associated digital signature schemes in the modern worldof computers and the Internet. This book provides an introduction to thetheory of public key cryptography and to the mathematical ideas underlyingthat key cryptography draws on many areas of Mathematics , includingnumber theory, abstract algebra, probability, and information theory. Eachof these topics is introduced and developed in sufficient detail so that thisbook provides a self-contained course for the beginning student. The onlyprerequisite is a first course in linear algebra. On the other hand, studentswith stronger mathematical backgrounds can move directly to cryptographicapplications and still have time for advanced topics such as elliptic curvepairings and lattice-reduction the many facets of modern cryptography, this book chooses to con-centrate primarily on public key cryptosystems and digital signature allows for an in-depth development of the necessary Mathematics re-quired for both the construction of these schemes and an analysis of theirsecurity.

6 The reader who masters the material in this book will not only bewell prepared for further study in cryptography, but will have acquired a realunderstanding of the underlying mathematical principles on which moderncryptography is covered in this book include Diffie Hellman key exchange, discretelogarithm based cryptosystems, the RSA cryptosystem, primality testing, fac-torization algorithms, probability theory, information theory, collision algo-rithms, elliptic curves, elliptic curve cryptography, pairing-based cryptogra-phy, lattices, lattice-based cryptography, the NTRU cryptosystem, and digi-tal signatures. A final chapter very briefly describes some of the many otheraspects of modern cryptography (hash functions, pseudorandom number gen-erators, zero-knowledge proofs, digital cash, AES,.. ) and serves to point thereader toward areas for further Resources: The interested reader will find additional materialand a list of errata on the Mathematical Cryptography home ~ web page includes many of the numerical exercises in the book, allowingthe reader to cut and paste them into other programs, rather than having toretype book is ever free from error or incapable of being improved.

7 We wouldbe delighted to receive comments, good or bad, and corrections from ourreaders. You can send mail to us We, the authors, would like the thank the followingindividuals for test-driving this book and for the many corrections and helpfulsuggestions that they and their students provided: Liat Berdugo, AlexanderCollins, 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 manystudents at Brown University who took Math 158 and helped us improve theexposition of this An Introduction to Simple substitution ciphers .. Divisibility and greatest common Modulararithmetic .. Prime numbers, unique factorization, and finite Powers and primitive roots in finite Cryptography before the computer Symmetric and asymmetric 36 Exercises.

8 472 Discrete Logarithms and Diffie The birth of public key The discrete logarithm Diffie Hellman key exchange .. The ElGamal public key Anoverviewofthetheoryofgroups .. How hard is the discrete logarithm problem?.. A collision algorithm for the The Chinese remainder The Pohlig Hellman algorithm .. Rings, quotients, polynomials, and finite 92 Exercises ..1053 Integer Factorization and Euler s formula and roots TheRSApublickeycryptosystem .. Implementation and security Primality Pollard sp 1factorization Factorization via difference of Smoothnumbersandsieves .. The index calculus and discrete Quadratic residues and quadratic Probabilistic ..1764 Combinatorics, Probability, and Information Basicprinciplesofcounting .. The Vigen`ere Probability Collision algorithms and meet-in-the-middle Pollard s Information Complexity Theory.

9 2625 Elliptic Curves and Elliptic Elliptic curves over finite fields .. The elliptic curve discrete logarithm Elliptic curve cryptography .. The evolution of public key Lenstra s elliptic curve factorization Elliptic curves overF2and Bilinear pairings on elliptic Applications of the Weil pairing ..334 Exercises ..3396 Lattices and A congruential public key Subset-sum problems and knapsack Abriefreviewofvectorspaces .. Lattices: Basic definitions and Short vectors in Babai s Cryptosystems based on hard lattice Convolution polynomial rings .. The NTRU public key NTRU as a lattice Lattice reduction algorithms .. Applications of LLL to ..422 Contentsix7 Digital What is a digital signature? .. RSA digital ElGamal digital signatures and GGH lattice-based digital NTRU digital.

10 4588 Additional Topics in Hash Random numbers and pseudorandom number Zero-knowledgeproofs .. Secret sharing Identification Paddingschemesandtherandomoraclemodel .. Building protocols from cryptographic Hyperelliptic curve Modern symmetric cryptosystems: DES and of Notation489 References493 Index501 IntroductionA Principal Goal of (Public Key) Cryptographyis to allow two people to exchange confidential information,even if they have never met and can communicate only viaa channel that is being monitored by an security of communications and commerce in a digital age relies on themodern incarnation of the ancient art of codes and ciphers. Underlying thebirth of modern cryptography is a great deal of fascinating Mathematics ,some of which has been developed for cryptographic applications, but muchof which is taken from the classical mathematical canon.