MathematicsofPublicKeyCryptography

Cryptography

5星 · 超过95%的资源需积分: 11 210 浏览量更新于2023-03-16 评论 3 收藏 4.73MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

Mathematics of Public Key Cryptography

http://www.math.auckland.ac.nz/~sgal018/crypto-book/crypto-book.html[2011/10/4 15:20:56]

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)

Contents

1 Introduction 25

1.1 Public Key Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

1.2 The Textbook RSA Cryptosystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

1.3 Formal Deﬁnition of Public Key Cryptography . . . . . . . . . . . . . . . . . . . . . 28

1.3.1 Security of Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

1.3.2 Security of Signatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

I Background 33

2 Basic Algorithmic Numbe r Theory 35

2.1 Algorithms and Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.1.1 Randomised Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

2.1.2 Success Probability of a Randomised Algorithm . . . . . . . . . . . . . . . . . 38

2.1.3 Reductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

2.1.4 Random Self-Reducibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

2.2 Integer Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

2.2.1 Faster Integer Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

2.3 Euclid’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

2.4 Computing Legendre and Jacobi Symbols . . . . . . . . . . . . . . . . . . . . . . . . 46

2.5 Modular Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

2.6 Chinese Remainder Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

2.7 Linear Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

2.8 Modular Exponentiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

2.9 Square Ro ots Modulo p . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

2.10 Polynomial Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

2.11 Arithmetic in Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 6

2.12 Factoring Polynomials over Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . . 57

2.13 Hensel Lifting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

2.14 Algorithms in Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

2.14.1 Constructing Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

2.14.2 Solving Quadratic Equations in Finite Fields . . . . . . . . . . . . . . . . . . 60

2.14.3 Isomorphisms Between Finite Fields . . . . . . . . . . . . . . . . . . . . . . . 6 1

2.15 Computing Orders of Elements and Primitive Roots . . . . . . . . . . . . . . . . . . 62

2.15.1 Sets of Exponentials of Products . . . . . . . . . . . . . . . . . . . . . . . . . 63

2.15.2 Computing the Order of a Group Element . . . . . . . . . . . . . . . . . . . . 64

2.15.3 Computing Primitive Roots . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

2.16 Fast Evaluation of Polynomials at Multiple Points . . . . . . . . . . . . . . . . . . . 65

2.17 Pseudorandom Generatio n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

2.18 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

4 CONTENTS

3 Hash Functions and MACs 69

3.1 Security P rope rties of Hash Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 69

3.2 Birthday Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

3.3 Message Authentication Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

3.4 Constructions of Hash Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

3.5 Number-Theoretic Hash Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

3.6 Full Domain Hash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

3.7 Random Oracle Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

II Algebraic Groups 73

4 Preliminary Remarks on Algebraic Groups 75

4.1 Informal Deﬁnition of an Algebraic Group . . . . . . . . . . . . . . . . . . . . . . . . 75

4.2 Examples of Algebraic Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

4.3 Algebraic Group Quotients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

4.4 Algebraic Groups over Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

5 Varieties 79

5.1 Aﬃne algebra ic sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

5.2 Projective Algebraic Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

5.3 Irreducibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

5.4 Function Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

5.5 Rational Maps and Morphisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

5.6 Dimension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

5.7 Weil Restriction of Scalars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

6 Tori, LUC and XTR 99

6.1 Cyclotomic Subgroups of Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . . . 99

6.2 Algebraic Tori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 01

6.3 The Group G

q,2

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

6.3.1 The Tor us T

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

6.3.2 Lucas Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

6.4 The Group G

q,6

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

6.4.1 The Tor us T

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

6.4.2 XTR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

6.5 Further Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

6.6 Algebraic Tori over Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

7 Curves and Divisor C lass Groups 111

7.1 Non-Singular Varieties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

7.2 Weierstrass Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

7.3 Uniformizers on Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

7.4 Valuation a t 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

7.9 Elliptic Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

CONTENTS 5

8 Rational Maps on Curves and Diviso rs 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 Diﬀerentials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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

9.6 Isogenies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153

9.7 The Invariant Diﬀerential . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 Sup e rsingular 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 Q uartic 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

10.3 Eﬀective Aﬃne Divisors on Hyperelliptic Curves . . . . . . . . . . . . . . . . . . . . 188

10.3.1 Mumford Representation of Semi-Reduced Divisors . . . . . . . . . . . . . . . 189

10.3.2 Addition and Semi-Reduction of Divisors in Mumfor d 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 Ramiﬁed 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 7

10.9 Sup e rsingular Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207

剩余518页未读，继续阅读

longcpp

2017-10-14

很好的密码学基础材料

独孤过儿

粉丝: 588
资源: 38

会员权益专享

Mathematics of Public Key Cryptography

评论4

会员权益专享

最新资源

Mathematics of Public Key Cryptography

评论4

Pearls of discrete mathematics

annals of mathematics怎么样？

Mathematics in Computing

给初学者看的神经网络的数学基础 A Beginner's Guide to the Mathematics of Neural Networks

handbook of mathematics

Mastering Technical Mathematics 2nd Edition

Introduction to Methods of Applied Mathematics

handbook of discrete and combinatorial mathematics

handbook of mathematics for engineers and engineering students pdf

Investment Mathematics

Handbook of Biomedical Image Analysis(医学图像处理手册) - Volume I Segmentation Models Part A

OpenGL Mathematics

Introduction to Linear Algebra 5th Gilbert Strang

MIT Press - Mathematics For Computer Science.pdf

ct重建算法的文献推荐

Mathematics for Machine Learning【Marc Peter Deisenroth】

会员权益专享

最新资源