第1页 / 共519页
第2页 / 共519页
第3页 / 共519页
第4页 / 共519页
第5页 / 共519页
第6页 / 共519页
第7页 / 共519页
第8页 / 共519页
Mathematics of Public Key Cryptography.pdf
Mathematics of Public Key Cryptography fm.pdf
www.math.auckland.ac.nz
Mathematics of Public Key Cryptography
Mathematics of Public Key Cryptography
Mathematics of Public Key Cryptography
Version 1.0
June 21, 2011
Steven Galbraith
This webpage contains some draft chapters of an advanced mathematics textbook. The book is now
finished. It will be published Cambridge University Press in early 2012. This is the long version of the book.
The published version will be somewhat shorter. Please note that this book is still in the process of being
written and that any aspects are subject to change at any time. Hence, you should assume that page
numbers, section numbers, theorem numbers etc will change and that some of the contents may disappear.
Hopefully, there are relatively few errors in the book, but it would be absurdly optimistic to suppose there
are none. I hope that, with your help, some of these errors can be removed. One reason for putting this
material on the web is that I want to receive feedback on the book. Please send me an email
(s.galbraith@math.auckland.ac.nz) if you find anything which is incorrect, poorly explained or misleading. All
such contributions will be acknowledged.
Sample Chapters
Table of contents
Acknowledgements (your name could be here!)
1. Introduction
Part I: Background
2. Basic Algorithms
3. Hash Functions
Part II: Algebraic Groups
4. Introduction to Algebraic Groups
5. Varieties
6. Tori, LUC and XTR
7. Curves and Divisor Class Groups
8. Rational Maps on Curves and Divisors
9. Elliptic Curves
10. Hyperelliptic Curves
Part III: Exponentiation, Factoring and Discrete Logarithms
11. Basic Algorithms for Algebraic Groups
12. Primality Testing and Integer Factorisation using algebraic groups
13. Basic Discrete Logarithm Algorithms
14. Factoring and Discrete Logarithms Using Pseudorandom Walks
15. Factoring and Discrete Logarithms in Subexponential Time
Part IV: Lattices
16. Lattices
17. Lattice Reduction
18. Algorithms for the Closest and Shortest Vector Problem
19. Coppersmith's Method and Other Applications
19a. Cryptosystems Based on Lattices (Will not appear in published version of book)
http://www.math.auckland.ac.nz/~sgal018/crypto-book/crypto-book.html[2011/10/4 15:20:56]
Mathematics of Public Key Cryptography
Part V: Cryptography Related to Discrete Logarithms
20. The Diffie-Hellman Problem and Cryptographic Applications
21. Results on the Diffie-Hellman Problem
22. Digital Signatures Based on Discrete Logarithms
23. Public Key Encryption Based on Discrete Logarithms
Part VI: Cryptography Related to Integer Factorisation
24. The RSA and Rabin Cryptosystems
Part VII: Advanced Topics in Elliptic and Hyperelliptic Curves
25. Isogenies
26. Pairings
Appendices
A. Background Mathematics
B. Hints and Solutions to Exercises
References
Index
http://www.math.auckland.ac.nz/~sgal018/crypto-book/crypto-book.html[2011/10/4 15:20:56]
Contents
1 Introduction
1.1 Public Key Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 The Textbook RSA Cryptosystem . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Formal Definition of Public Key Cryptography . . . . . . . . . . . . . . . . . . . . .
Security of Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Security of Signatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.1
1.3.2
I Background
2 Basic Algorithmic Number Theory
2.2
2.1 Algorithms and Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1 Randomised Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Success Probability of a Randomised Algorithm . . . . . . . . . . . . . . . . .
2.1.2
2.1.3 Reductions
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.4 Random Self-Reducibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Integer Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1 Faster Integer Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Euclid’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4 Computing Legendre and Jacobi Symbols . . . . . . . . . . . . . . . . . . . . . . . .
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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.11 Arithmetic in Finite Fields
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.12 Factoring Polynomials over Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . .
2.13 Hensel Lifting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.14 Algorithms in Finite Fields
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.14.1 Constructing Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.14.2 Solving Quadratic Equations in Finite Fields
. . . . . . . . . . . . . . . . . .
2.14.3 Isomorphisms Between Finite Fields . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
2.15.1 Sets of Exponentials of Products . . . . . . . . . . . . . . . . . . . . . . . . .
2.15.2 Computing the Order of a Group Element . . . . . . . . . . . . . . . . . . . .
2.15.3 Computing Primitive Roots . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.16 Fast Evaluation of Polynomials at Multiple Points
. . . . . . . . . . . . . . . . . . .
2.17 Pseudorandom Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.18 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.15 Computing Orders of Elements and Primitive Roots
25
26
26
28
29
30
33
35
35
37
38
39
40
41
42
44
46
48
49
50
51
53
55
56
57
59
60
60
60
61
62
63
64
65
65
66
66
3
4
CONTENTS
3 Hash Functions and MACs
3.1 Security Properties of Hash Functions
. . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Birthday Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Message Authentication Codes
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
4.1
4.2 Examples of Algebraic Groups
4.3 Algebraic Group Quotients
4.4 Algebraic Groups over Rings
Informal Definition of an Algebraic Group . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5 Varieties
5.1 Affine algebraic sets
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Projective Algebraic Sets
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3
Irreducibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4 Function Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5 Rational Maps and Morphisms
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.6 Dimension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.7 Weil Restriction of Scalars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
69
69
70
70
71
71
71
72
73
75
75
76
77
77
79
79
83
87
89
91
95
95
6 Tori, LUC and XTR
99
99
6.1 Cyclotomic Subgroups of Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 Algebraic Tori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
6.3 The Group Gq,2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
6.3.1 The Torus T2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
6.3.2 Lucas Sequences
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
6.4 The Group Gq,6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
6.4.1 The Torus T6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
6.4.2 XTR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
6.5 Further Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
6.6 Algebraic Tori over Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
7 Curves and Divisor Class Groups
111
7.1 Non-Singular Varieties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
7.2 Weierstrass Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
7.3 Uniformizers on Curves
7.4 Valuation at a Point on a Curve
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
7.5 Valuations and Points on Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
7.6 Divisors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
7.7 Principal Divisors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
7.8 Divisor Class Group . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
7.9 Elliptic Curves
CONTENTS
5
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 Riemann-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 law . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
9.2 Morphisms Between Elliptic Curves
. . . . . . . . . . . . . . . . . . . . . . . . . . . 149
9.3
Isomorphisms of Elliptic Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
9.4 Automorphisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
9.5 Twists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
Isogenies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
9.6
9.7 The Invariant Differential
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
9.8 Multiplication by n and Division Polynomials . . . . . . . . . . . . . . . . . . . . . . 160
9.9 Endomorphism Structure
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
9.10 Frobenius map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
9.10.1 Complex Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
9.10.2 Counting Points on Elliptic Curves . . . . . . . . . . . . . . . . . . . . . . . . 167
9.11 Supersingular Elliptic Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
9.12 Alternative Models for Elliptic Curves . . . . . . . . . . . . . . . . . . . . . . . . . . 170
9.12.1 Montgomery Model
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
9.12.2 Edwards Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
9.12.3 Jacobi Quartic Model
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
9.13 Statistics of Elliptic Curves over Finite Fields . . . . . . . . . . . . . . . . . . . . . . 176
9.14 Elliptic Curves over Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
10 Hyperelliptic Curves
179
10.1 Non-Singular Models for Hyperelliptic Curves . . . . . . . . . . . . . . . . . . . . . . 180
10.1.1 Projective Models for Hyperelliptic Curves
. . . . . . . . . . . . . . . . . . . 182
10.1.2 Uniformizers on Hyperelliptic Curves . . . . . . . . . . . . . . . . . . . . . . . 184
10.1.3 The Genus of a Hyperelliptic Curve
. . . . . . . . . . . . . . . . . . . . . . . 185
10.2 Isomorphisms, Automorphisms and Twists . . . . . . . . . . . . . . . . . . . . . . . . 186
. . . . . . . . . . . . . . . . . . . . 188
10.3 Effective Affine Divisors on Hyperelliptic Curves
10.3.1 Mumford Representation of Semi-Reduced Divisors . . . . . . . . . . . . . . . 189
10.3.2 Addition and Semi-Reduction of Divisors in Mumford Representation . . . . 191
10.3.3 Reduction 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
. . . . . . . . . . . . . . . . 195
10.4.2 Addition of Divisor Classes on Split Models . . . . . . . . . . . . . . . . . . . 196
10.5 Jacobians, Abelian Varieties and Isogenies . . . . . . . . . . . . . . . . . . . . . . . . 200
10.6 Elements of Order n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
10.7 Hyperelliptic Curves Over Finite Fields
. . . . . . . . . . . . . . . . . . . . . . . . . 204
10.8 Endomorphisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
10.9 Supersingular Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
6
CONTENTS
III 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-w Non-Adjacent Form . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
11.1.3 Further Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
11.2 Multi-exponentiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
11.3 Efficient Exponentiation in Specific Algebraic Groups
. . . . . . . . . . . . . . . . . 217
11.3.1 Alternative Basic Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
11.3.2 Frobenius Expansions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
11.3.3 GLV Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
11.4 Sampling from Algebraic Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
11.4.1 Sampling from Tori
. . . . . . . . . . . . . . . . . . . . . . . . . . 226
11.4.2 Sampling from Elliptic Curves
11.4.3 Hashing to Algebraic Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
11.4.4 Hashing from Algebraic Groups . . . . . . . . . . . . . . . . . . . . . . . . . . 229
11.5 Determining Elliptic Curve Group Structure . . . . . . . . . . . . . . . . . . . . . . . 229
11.6 Testing Subgroup Membership . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
11.7 Elliptic Curve Point Compression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
12 Primality and Factoring using Algebraic Groups
233
12.1 Primality Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
12.1.1 Fermat Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
12.1.2 The Miller-Rabin Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
12.1.3 Primality Proving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
12.2 Generating Random Primes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
12.3 The p − 1 Factoring Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
12.4 Elliptic Curve Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
12.5 Pollard-Strassen Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
12.2.1 Primality Certificates
13 Basic Discrete Logarithm Algorithms
241
13.1 Exhaustive Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
13.2 The Pohlig-Hellman Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
13.3 Baby-Step-Giant-Step (BSGS) Method . . . . . . . . . . . . . . . . . . . . . . . . . . 244
13.4 Lower Bounds on the 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 Weight DLP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
13.7 Low Hamming Weight Product Exponents . . . . . . . . . . . . . . . . . . . . . . . . 252
13.8 Wagner’s Generalised Birthday Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 252
14 Psuedorandom Walks
255
14.1 Birthday Paradox . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
14.2 The Pollard Rho Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
14.2.1 The Pseudorandom Walk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
14.2.2 Pollard Rho Using Floyd Cycle Finding . . . . . . . . . . . . . . . . . . . . . 258
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 . . . . . . . . . . . . . . . . . . . 264
14.3 Distributed Pollard Rho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
CONTENTS
7
14.3.1 The Algorithm and its Heuristic Analysis . . . . . . . . . . . . . . . . . . . . 265
14.4 Using Equivalence Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
14.4.1 Examples of Equivalence Classes . . . . . . . . . . . . . . . . . . . . . . . . . 268
14.4.2 Dealing with Cycles
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
14.4.3 Practical Experience with the Distributed Rho Algorithm . . . . . . . . . . . 270
14.5 The Kangaroo Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
14.5.1 The Pseudorandom Walk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
14.5.2 The Kangaroo Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
14.5.3 Heuristic Analysis of the Kangaroo Method . . . . . . . . . . . . . . . . . . . 273
14.5.4 Comparison with the Rho Algorithm . . . . . . . . . . . . . . . . . . . . . . . 274
14.5.5 Using Inversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
14.5.6 Towards a Rigorous Analysis of the Kangaroo Method . . . . . . . . . . . . . 275
14.6 Distributed Kangaroo Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
14.6.1 Van Oorschot and Wiener Version . . . . . . . . . . . . . . . . . . . . . . . . 277
14.6.2 Pollard Version . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
14.6.3 Comparison of the Two Versions . . . . . . . . . . . . . . . . . . . . . . . . . 280
14.7 The Gaudry-Schost Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
14.7.1 Two-Dimensional Discrete Logarithm Problem . . . . . . . . . . . . . . . . . 281
14.7.2 Interval DLP using Equivalence Classes . . . . . . . . . . . . . . . . . . . . . 283
. . . . . . . . . . . . . . . . . . . . . . . 283
14.8.1 The Low Hamming Weight DLP . . . . . . . . . . . . . . . . . . . . . . . . . 284
14.9 Pollard Rho Factoring Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285
14.10Pollard Kangaroo Factoring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286
14.8 Parallel Collision Search in Other Contexts
15 Subexponential Algorithms
287
15.1 Smooth Integers
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
15.2 Factoring using Random Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
15.2.1 Complexity of the Random Squares Algorithm . . . . . . . . . . . . . . . . . 290
15.2.2 The Quadratic Sieve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292
15.2.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
15.3 Elliptic Curve Method Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
15.4 The Number Field Sieve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
15.5 Index Calculus in Finite Fields
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
15.5.1 Rigorous Subexponential Discrete Logarithms Modulo p . . . . . . . . . . . . 297
15.5.2 Heuristic Algorithms for Discrete Logarithms Modulo p . . . . . . . . . . . . 299
15.5.3 Discrete Logarithms in Small Characteristic . . . . . . . . . . . . . . . . . . . 299
15.5.4 Coppersmith’s Algorithm for the DLP in F∗
2n . . . . . . . . . . . . . . . . . . 301
15.5.5 The Joux-Lercier Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
15.5.6 Number Field Sieve for the DLP . . . . . . . . . . . . . . . . . . . . . . . . . 304
15.5.7 Discrete Logarithms for all Finite Fields . . . . . . . . . . . . . . . . . . . . . 304
. . . . . . . . . . . . . . . . . . . . . . 304
15.6.1 Index Calculus on Hyperelliptic Curves
. . . . . . . . . . . . . . . . . . . . . 305
15.6.2 The Algorithm of Adleman, De Marrais and Huang . . . . . . . . . . . . . . 306
15.6.3 Gaudry’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
15.7 Weil Descent
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
15.8 Elliptic Curves over Extension Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
15.8.1 Semaev’s Summation Polynomials
. . . . . . . . . . . . . . . . . . . . . . . . 308
15.8.2 Gaudry’s Variant of Semaev’s Method . . . . . . . . . . . . . . . . . . . . . . 309
15.8.3 Diem’s Algorithm for the ECDLP . . . . . . . . . . . . . . . . . . . . . . . . 310
15.9 Further Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
15.9.1 Diem’s Algorithm for Plane Curves of Low Degree . . . . . . . . . . . . . . . 310
15.9.2 The Algorithm of Enge-Gaudry-Thom´e and Diem . . . . . . . . . . . . . . . 311
15.9.3 Index Calculus for General Elliptic Curves . . . . . . . . . . . . . . . . . . . . 311
15.6 Discrete Logarithms on Hyperelliptic Curves
8
IV Lattices
CONTENTS
313
16 Lattices
315
16.1 Basic Notions on Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
16.2 The Hermite and Minkowski Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
16.3 Computational Problems in Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
17 Lattice Basis Reduction
323
17.1 Lattice Basis Reduction in Two Dimensions . . . . . . . . . . . . . . . . . . . . . . . 323
17.1.1 Connection Between Lagrange-Gauss Reduction and Euclid’s Algorithm . . . 326
17.2 LLL-Reduced Lattice Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
17.3 The Gram-Schmidt Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330
17.4 The LLL Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
17.5 Complexity of LLL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
17.6 Variants of the LLL Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
18 Close and Short Vectors
339
18.1 Babai’s Nearest Plane Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
18.2 Babai’s Rounding Technique
18.3 The Embedding Technique
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346
18.4 Enumerating all Short Vectors
18.4.1 Enumeration of Closest Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . 348
18.5 Korkine-Zolotarev Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349
19 Coppersmith’s Method and Related Applications
19.1 Modular Univariate Polynomials
351
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351
19.1.1 First Steps to Coppersmith’s Method . . . . . . . . . . . . . . . . . . . . . . 351
19.1.2 The Full Coppersmith Method . . . . . . . . . . . . . . . . . . . . . . . . . . 354
19.2 Multivariate Modular Polynomial Equations . . . . . . . . . . . . . . . . . . . . . . . 356
19.3 Bivariate Integer Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356
19.4 Some Applications of Coppersmith’s method . . . . . . . . . . . . . . . . . . . . . . 359
19.4.1 Fixed Padding Schemes in RSA . . . . . . . . . . . . . . . . . . . . . . . . . . 359
19.4.2 Factoring N = pq with Partial Knowledge of p . . . . . . . . . . . . . . . . . 360
19.4.3 Factoring prq . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361
19.4.4 Chinese Remaindering with Errors . . . . . . . . . . . . . . . . . . . . . . . . 362
19.5 Simultaneous Diophantine Approximation . . . . . . . . . . . . . . . . . . . . . . . . 364
19.6 Approximate Integer Greatest Common Divisors
. . . . . . . . . . . . . . . . . . . . 365
19.7 Learning with Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366
19.8 Further Applications of Lattice Reduction . . . . . . . . . . . . . . . . . . . . . . . . 367
19.9 Goldreich-Goldwasser-Halevi Cryptosystem . . . . . . . . . . . . . . . . . . . . . . . 369
19.10Cryptanalysis of GGH Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371
19.11GGH Signatures
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373
19.12NTRU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374
19.13Knapsack Cryptosystems
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375
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 . . . . . . . . . . . . . . . . . . . . . . . . . . . 385
20.2 Key Exchange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386
20.2.1 Diffie-Hellman Key Exchange . . . . . . . . . . . . . . . . . . . . . . . . . . . 386
20.2.2 Burmester-Desmedt Key Exchange . . . . . . . . . . . . . . . . . . . . . . . . 387
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
