Mathematics of Public Key Cryptography

【实例简介】
Public key cryptography is a major interdisciplinary subject with many real-world applications, such as digital signatures. A strong background in the mathematics underlying public key cryptography is essential for a deep understanding of the subject, and this book provides exactly that for students
Co nten ts 1 Introduction 25 1.1 Public Key Cryptography 1.2 The Textbook RSA Cryptosystem 1.3 ForMal Definition of Public Key Cryptography 28 1.3. 1 Security of encryptie 29 1.3.2 Security of Signatures I Background 35 2 Basic Algorithmic Number Theory 35 2.1 Algorithms and Complexity 1. 1 RandoMised Algorithins 2.1.2 Success Probability of a Randomised Algorithm 2.1.3 Reductions 39 2. 1. 4 Random Self-reducibility 40 2.2 Integer Operations 41 2.2. 1 Faster Integer Multiplication 2.3 Euclid's algorithm 2.4 Computing Legendre and Jacobi Symbols .46 2.5 Modular Arithmetic 2.6 Chinese Remainder Theorem 2.7 Linear Algebra 2.8 Modular exponentiation 2.9 Square Roots Modulo p 2.10 Polynomial Arithmetic 5 2.11 Arithmetic in Finite Fields 36 2.12 Factoring Polynomials over Finite Fields 2.13 Hensel liftin 9 2.14 AlgorithIns in Finite Fields 60 2. 14.1 Constructing Finitc Ficlds 60 2.14.2 Solving Quadratic Equations in Finite Fields 60 2. 14.3 Isomorphisms Between Finite Fields 2.15C ting orders of fl its and primitive root 62 2.15.1 Sets of Exponentials of Products 2.15.2 Computing the Ordcr of a Group elc 2.15.3C ting Primitive roots 2.16 Fast Evaluation of Polynomials at Multiple Points 2.17 Pseudorange 66 2.18 Summary 66 CONTENTS 3 Hash Functions and macs 69 3.1 Security Properties of Hash Function 3.2 Birthday Attack 70 3.3 Message Authentication Code 3.4 Constructions of hash functions 3.5 Number-Theoretic Hash Functions 3.6 Full Domain hash 3. 7 RandoM Oracle model II Algebraic Groups 4 Preliminary Remarks on Algebraic Groups of an Alge 4.2 Examples of algebraic groups 76 Algebraic Group quotients 77 4.4 Algebraic Groups over Rings 77 5 Varieties 79 5.1 Affine algebraic sets ..,,79 5.2 Projective Algebraic Sets 87 5.5 Rational Maps and Morphisms’· 5.4 Function Fields 9 5. 6 Dimension 5.7 Weil Restriction of scalars 6 Tori, luc and xtR 99 6.1 Cyclotomic Subgroups of Finitc Ficlds 99 6.2Al T 101 6.3 The Group Gig. 2 102 6.3.1 The torus 6.3.2 Lucas Sequences 104 6.4 6.4.1 The torus 番潘 105 6.4.2XTR. ,.107 6.5 Further Remarks 6.6 Algebraic Tori over Rings 109 7 Curves anld Divisor Class Groups 111 7.1 Non-Singular varieties 7.2 Wcicrstrass Equations 115 7.3 UnliforIiizers on Curves 7. 4 Valuation at a point on a curve 7.5 Valuations and points on curvcs 120 7.6 Divisors 120 7.7 Principal Divisors 121 7. 8 Divisor Class group 124 7.9 Elliptic Curves 125 CONTENTS 8 Rational Maps on Curves and Divisors 129 8.1 Rational Maps of Curves and the Degree 129 8.2 Extensions of valuations 131 8.3 Maps on Divisor Classes 134 8.4 RieImaIlll-Roch Spaces 137 8.5 Derivations and Differentials 138 8. 6 Genus zero curves 143 8. 7 Riemann-Roch Theorem and hurwitz Genus Formula 144 9 Elliptic curves 147 9.1 Group Ia 9.2 Morphisms Between Elliptic C. 149 9.3 Isomorph of elliptic c 150 9.4 Automorphisms 151 9.5Tv 152 153 9.7 The Invariant Differential 158 9.8 Multiplication by n and Division Polynomials 160 9.9 Endo hism structu 161 9.10 Frot 163 9.10.1 Complex Multiplication 9.10.2 Counting Points on Elliptic Curves 167 9.11 Supersingular Elliptic CU Lr ves 167 9 12 Alternative Models for Elliptic Curves 170 9. 12.1 Montgomery Model 9. 12.2 Edwards model 173 9.12.3 Jacobi Quartic Model 175 9.13 Statistics of F. lliptic Curves over Finite Fields 176 9. 14 Elliptic Curves ovcr Rings 177 0 Hyperelliptic Curves 179 10. 1 Non-Singular Models for llyperelliptic Curves 180 10.1.1 Projective Models for Hyperelliptic Curves 182 10.1.2 CniforInizers Oll Hyperelliptic Curves 184 10.1.3 The Genus of a llyperelliptic Curve 10.2 Isomorphisms, Automorphisms and Twists 186 10.3 Effective Affine Divisors on Hyperelliptic Curves 188 10.3.1 Munford Representation of Selnli-Reduced Divisors 189 10.3.2 Addition and Semi-Reduction of Divisors in Mumford represent ation 191 10.3.3 Rcduction of Divisors in Mumford Representation 192 10.4 Addition in the Divisor Class group 195 10.4.1 Addition of Divisor Classes on Ramified models 10.4.2 Addition of Divisor Classes on Split models 10.5 Jacobians. Abelian varieties and isogenies 200 10.6 Elements of Order n 10.7 Hyperelliptic Curves Over Finite Fields 10.8 Endomorphisms .207 10.9 Supersingular Curves 207 CONTENTS Lll Exponentiation, Factoring and Discrete Logarithms 209 11 Basic Algorithms for Algebraic Groups 211 11.1 Efficient Exponentiation Using Signed Exponents 212 11. 1.1 Non-Adjacent Form 212 11.1.2 Width-2 Non-Adjacent Form 214 1.1.3 Further methods 11.2 Multi-exponentiation 216 11.3 Efficient Exponentiation in Specific Algebraic Groups 217 11.3.1 Altcrnativc Basic Opcrations .217 11.3.2 Frobenius expansions 218 1.3.3 GLV Met hod 223 11.4 Sampling from Algebraic Groups 225 11.1.1 Sampling from tori g 11.4.2 Sampling from Elliptic Curves 226 1.4.3 Hashing to Algebraic grou 11.4.4 Lashing from Algebraic Groups 11.3 Determining Elliptic Curve Group structure 229 11.6 Testing Subgroup membership 11.7 Elliptic Curve Point Compression 2 Primality and Factoring using Algebraic groups 233 2. 1 Primality Testing 233 12.1.1 Format tcst 234 12.1.2 The Miller-Rabin Test 234 12. 1.3 Primality Proving 235 12.2 Generating Randoin Priines 235 12.2.1 Primality Certificates 6 12. 3 The p-1 Factoring Method 236 12.4 Elliptic Curve Method 2:38 12.J Pollard-Strassen Method 39 13 Basic Discrete Logarithm Algorithms 241 13.1 Exhaustive Search 242 13.2 The Pohlig-HellIman Method 242 13. 3 Baby-Step-Giant-Step(BSGS) Method 244 13. Lower bounds on thc dlp 246 13.4.1 Shoup's Model for Generic Algorithms 247 13.4.2 Maurer's Model for Generic Algorithms 247 13.4.3 The Lower Bound 248 13.5 Generalised Discrete Logarithm Problems 249 13.6 Low Hamming wcight DLP 250 13.7 Low Hamming Weight Product Exponents 13.8 Wagner's generalised Birthday algorithm 252 4 Psuedorandom walks 255 14.1 Birthday Paradox 14.2 The Pollard rho method 237 14.2.1 The Pseudorandom walk 14.2.2 Pollard Rho Using Floyd Cycle Finding 14.2.3 Other Cycle Finding Methods 261 14.2.4 Distinguished Points and Pollard Rho 262 14.2.5 Towards a Rigorous Analysis of Pollard rho 14.3 Distributed Pollard rho 265 CONTENTS 14.3.1 The Algorithm and its Heuristic Analvsis 265 14.4 Using Equivalence Classes 267 14.4.1 Examples of Equivalence Classes 14.4.2 Dealing with Cycles 14.4.3 Practical Experience with the Distributed Rho Algorithm 269 270 14.5 The Kangaroo Mcthod .271 14.5.1 The pseudorandom walk 271 14.5.2 The Kangaroo Algorithm 272 4.5.3 Heuristic Analysis of the Kangaroo Method 14.5.4 Comparison with the Rho Algorithm 274 5.5 Lsing 14.5.6 Towards a Rigorous Analysis of the Kangaroo Method 275 14.6 Distributed Kangaroo Algorithm 277 14.6.1 Van Oorschot and wicncr Vcrsion 277 14.6. 2 Pollard version 79 14.6.3 Comparison of the two Versions 280 14. 7 The Gaudry-Schost Algorithm 14.7. 1 Two-Dimensional Discrete Logarithm Problem 14.7.2 Interval DLP using Equivalence Classes 283 14.8 Parallel Collision Search in Other Contexts 283 14.8.1 The Low Hamming Weight DLP 14.9 Pollard Rho Factoring Mcthod 14. 10Pollard Kangaroo Factoring 286 15 Subexponential algorithms 287 15.1 Smooth integers 15.2 Factoring using Random Squares 289 15.2.1 Complexity of the Random Squares Algorithm 290 15.2.2 Thc Quadratic Sieve 15.2.3 Summary 293 15. 3 Elliptic curve method revisited 294 15. 4 The Nuinber Field Sieve 295 15.5 Index Calculus in Finite Fields 296 5.1 Rigorous Subexponential Discrete Logarithms Modulo p 15.5. 2 Ileuristic Algorithms for Discrete Logarithms Modulo p 299 15.5.3 Discrete LogarithMs in SImall Characteristic 299 15.5.4 Coppersmith's Algorithm for the DLP in F>n 15.5.5 The oux-Lercier Algorithm 203 15.5.6 Number Field Sieve for the dlh 04 15.5.7 Discrete LogarithMs for all Finite Fields 15.6 Discrete Logarithms on Hyperelliptic Curves 304 15.6.1 Index Calculus on Hyperelliptic Curves 15.6.2 The Algorithm of Adleman, De Marrais and Huang 10.6.3 Gaudry's algorithm 306 15.7 Weil Descent 15.8 Elliptic Curves over Extension Ficld 308 15.8.1 Semaev's Summation Polynomials 08 15.8.2 Gaudry's Variant of SeInlaev's Method 15.8. 3 Diem's Algorithm for the ECDLP 10 15.9 Further Rcsults ..,,310 15.9.1 Diem's Algorithm for Plane Curves of Low Degree 310 15.9.2 The Algorithm of Enge-Gaudry-Thome and Dier 311 15.9.3 Index Calculus for General Elliptic Curves 311 CONTENTS IV Lattices 313 16 Lattices 315 16.1 Basic notions on lattices 317 16.2 The hermite and minkowski boulds 16.3 Computational Problems in Lattices 321 17 Lattice Basis reduction 323 17.1 Lattice Basis Reduction il Two dimensions 323 17.1.1 Connection Between Lagrange-Gauss Reduction and Euclids algorithm . ..326 17.2 LLL-Rcduccd Lattice Bascs 327 17.3 The Gram-Schmidt Algorithm 330 17. 4 The lll alec 17.5 Complexity of Lll 35 17.6 Variants of the LLL algorith 337 ⊥8Clo nd short vecte 339 18. 1 Babai's nearest Plane method ,339 18.2 Babai's Rounding te 43 18.3 The Embedding Technique 345 18.4 Enumerating all short Vectors ..,,346 18. 4.1 Enumeration of Closest vectors 18.5 Korkinc-Zolotarcy Bascs 349 19 Coppersmith's Method and Related Applications 351 19. 1 Modular Univariate Polyioillials 351 19.1.1 First Steps to Coppersmiths Method 19. 1.2 The Full Coppersmith Mcthod .354 19.2 Multivariate Modular Polynomial equations 356 19.3 Bivariate Integer polynomials 19.4 Some applications of Coppersmith's method 359 9.4.1 Fixed Padding Schemes in RSA 339 19.1.2 Factoring N= pq with Partial Knowledge of p 360 19. 4.3 Factoring p 19.4.4 Chinesc rcmaindcring with errors 19.5 Simultaneous diophantine approximation 64 19.6 Approximate Integer Greatest Common Divisors 19. 7 Learning with Errors 19.8 Further Applications of Lattice ReductiOn ...367 19.9 Goldreich-Goldwasser-Halevi Cryptosystem 19.10Cryptanalysis of GGH Encryption Syster 369 19.11GGH Signatures 373 19. 12NTRU 2374 19. 13Knapsack Cryptosystems 19 13.1 Public Key Encryption Using Knapsacks 376 19. 13.2 Cryptanalysis of Knapsack Cryptosystems .,.377 V Cryptography Related to Discrete Logarithms 383 20 Diffie-Hellman Cryptography 385 20. 1 The Discrete Logarithm Assumption 20.2 Key Exchange 86 20.2.1 Diffie-Hellman Key exchange 386 20.2.2 Burmester-Desmedt Key exchange CONTENTS 20. 2.3 Key Derivation Functions 387 20.3 Textbook Elgamal Encryption 388 20.4 Security of Textbook Elgamal Encryption 289 20.4.1 OWE Against Passive Attacks 2390 20.4.2 OWF Security Under cca Attacks 390 20.4.3 Semantic Security Under Passive Attacks 391 20.5 Security of Diffie-Hellimlall Key Exchange 392 20.6 Efficiency of Discrete Logarithm Cryptography 21 The Ditfie-Hellman problem 395 21.1 Variants of the diffie-Hellman problem 21.2 Lower Bound on the Complexity of CDH for Generic Algorithms 21.3 Random Self-Reducibility and Self-Correction of CDH .399 21. 4 The den boer and maurer reductions 21.4.1 Implicit Representations 401 21. 4.2 The den boer reduction 21.4.3 The maurer reduction 21.5 Algorithms for Static Diffie-llellman 408 21.6 Hard Bits of discrete logarithms 21.6.1 Hard Bits for DLP in Algebraic Group Quotients .,,413 21.7 Bit Security of Diffie-Helly 414 21.7.1 Thc hidden Numbcr problom 415 21.72 hard Bits for cdh Modulo a prime 417 21 7.3 Hard Bits for CDH in Other groups 418 21.8 Further Topics 419 22 Digital Signatures Based on Discrete Logarithms 421 22.1 Schnorr Signatures 421 22.1. 1 The Schnorr Identification Scheme 421 22.1.2 Schnorr Signature 424 22. 1.3 Security of Schnorr Signatures 2.1. 4 Efliciency Considerations for Schnorr Signatures 22.2 Other Public Key Signature Schemes 426 22.2.1 Elgamal Signatures in Prime Order Subgroups 426 22.2.2 DSA .,.428 22.2. 3 Signatures secure in the Standard model ,,,,,429 22.3 Lattice Attacks on signatures 番潘 431 22.4 Other Signature Functionalities 23 Encryption from Discrctc Logarithms 435 23. 1 CCA Secure Elgamal Encryption 番潘 23.1.1 The KEM/DEM Paradigm 436 23.12 Proof of Security in the Random Oracle Model 437 23.2 Cramer-Shoup Encryption 439 23.3 Other Encryption Functionalities .,,442 23.3.1 Homomorphic Encryption 442 23.3.2 Identity-Based Encryption VI Cryptography Related to Integer Factorisation 445 24 The RSA and Rabin Cryptosystems 447 24. 1 The Textbook RSA Cryptosystem 447 24.1.1 EHlicient Iimplementation of rsa 24.1.2 Variants of RSA CONTENTS 24. 1.3 Security of Textbook rSA 450 24.2 The Textbook rabin Cryptosystem 433 24.2.1 Redundancy Schemes for Unique Decryption 43 24.2.2 Variants of rabin 24. 2.3 Security of Text hook Rabin 456 24.2. 4 Other Computational Problems Related to Factoring 4.3 HolllOInorphic Encryption 24.4 Algebraic Attacks on Textbook RSa and Ra.bin 461 24. 4.1 The hastad Attack .,.461 24.4.2 Algebraic Attack 461 24.4.3 Dcsmcdt-Odlyzko Attack 461 24.4. 4 Related Message Attacks 462 24. 4.5 Fixed Pattern RSA Signature Forgery 462 24.4.6 Two Attacks by blcichenbachcr 464 24.5 Attacks on RSa Paraneters .465 24.5.1 Wiener Attack on Small Private Exponent RSA ,,,465 24.5.2 Small CrT Private Exponents .466 24.5. 3 Large Common Factor of p-l and g-1 467 24.6 Digital Signatures Based on RSA and Rabin 468 24.6.1 Full Domain hash 24.6.2 Secure Rabin-Williams Signatures in the Random Oracle Model 4.6.3 Other Signature and Identification Schemes 24.7 Public Key Encryption Based on RSA and rabin 24.7. 1 Padding Schemes for RSA and Rabin 24.7.2OAEP,, 473 24.7.3 Rabin-SAEP 473 24.7.4 Further Topics 477 Vii Advanced Topics in Elliptic and Hyperelliptic Curves 479 25 Isogenies of Elliptic Curves 481 25 1 Isogenies and Kernels 481 25.1.1 velu's formulae 25.2 Isogonics from j-invariants 487 25.2.1 Elkies' Algorithirl 489 25.2.2 Stark' s a 491 25. 2.3 The Small Characteristic Case 25.3 Isogeny Graphs of Elliptic Curves over Finite Fields 492 25.3.1 Ordinary Isogeny Graph 493 25. 3.2 Expander Graphs and ramanujan graphs 495 253.3 Supersingular Isogeny Graph 496 25. 4 The Structurc of the Ordinary Isogeny graph .497 25.4.1 Isogeny Volcanoes .497 25.4.2 Kohel's Algorithm(Ordinary Case) 499 25.5 Constructing Isogenies Between Elliptic Curves 500 25.5.1 The Galbraith algorithm 01 25.5.2 The Galbraith-Hess-Smart Algorithm 5.6 Relating Discrete Logs 503 【实例截图】
【核心代码】