Preface
Exercises
Acknowledgements
Contents
1 Introduction
1.1 History
1.2 Introduction
1.3 Why Is Cryptography Used?
1.4 Modes of Encryption
1.5 Modes of Attack
1.6 How Many Seconds in a Year?
1.7 Kerckhoffs' Principle
1.8 Exercises
2 Simple Ciphers
2.1 Substitution Ciphers
2.1.1 Caesar Ciphers
2.1.2 Random Substitutions
2.1.3 Vigenère as an Example of Polyalphabetic Substitutions
2.2 Language Characteristics and Patterns
2.2.1 Letter Frequency
2.2.2 Word Boundaries
2.2.3 Cribbing
2.2.4 Entropy
2.3 Transposition Ciphers
2.3.1 Columnar Transpositions
2.3.2 Double Transposition
2.4 Playfair
2.5 ADFGX
2.6 Cryptanalysis
2.6.1 Breaking a Substitution Cipher
2.6.2 Breaking a Transposition Cipher
2.7 The Vernam One-Time Pad
2.8 Exercises
2.8.1 Cipher Text for Substitution Cipher Problems (3) and (4)
3 Divisibility, Congruences, and Modular Arithmetic
3.1 Divisibility
3.2 The Euclidean Algorithm
3.2.1 The Naive Euclidean Algorithm
3.2.2 The Extended Euclidean Algorithm
3.2.3 The Binary Euclidean Algorithm
3.2.4 The Subtract-Three-Times Euclidean Algorithm
3.2.5 GCDs of Large Integers
3.3 Primes
3.4 Congruences
3.5 The Euler Totient
3.6 Fermat's Little Theorem
3.7 Exponentiation
3.8 Matrix Reduction
3.9 Exercises
4 Groups, Rings, Fields
4.1 Groups
4.2 Rings
4.3 Fields
4.4 Examples and Expansions
4.4.1 Arithmetic Modulo Prime Numbers
4.4.2 Arithmetic Modulo Composite Numbers
4.4.3 Finite Fields of Characteristic 2
4.5 Exercises
5 Square Roots and Quadratic Symbols
5.1 Square Roots
5.1.1 Examples
5.2 Characters on Groups
5.3 Legendre Symbols
5.4 Quadratic Reciprocity
5.5 Jacobi Symbols
5.6 Extended Law of Quadratic Reciprocity
5.7 Exercises
6 Finite Fields of Characteristic 2
6.1 Polynomials with Coefficients mod 2
6.1.1 An Example
6.2 Linear Feedback Shift Registers
6.3 The General Theory
6.4 Normal Bases
6.5 Exercises
7 Elliptic Curves
7.1 Basics
7.1.1 Straight Lines and Intersections
7.1.2 Tangent Lines
7.1.3 Formulas
7.1.4 The Mordell-Weil Group
7.2 Observation
7.3 Projective Coordinates and Jacobian Coordinates
7.4 An Example of a Curve with Many Points
7.5 Curves Modulo a Prime p
7.6 Hasse's Theorem
7.7 Exercises
8 Mathematics, Computing, and Arithmetic
8.1 Mersenne Primes
8.1.1 Introduction
8.1.2 Theory
8.1.3 Implementation
8.1.4 Summary: Feasibility
8.1.5 Fermat Numbers
8.1.6 The Arithmetic Trick Is Important
8.2 Multiprecise Arithmetic and the Fast Fourier Transform
8.2.1 Multiprecise Arithmetic
8.2.2 Background of the FFT
8.2.3 Polynomial Multiplication
8.2.4 Complex Numbers as Needed for Fourier Transforms
8.2.5 The Fourier Transform
8.2.6 The Cooley–Tukey Fast Fourier Transform
8.2.7 An Example
8.2.8 The FFT Butterfly
8.3 Montgomery Multiplication
8.3.1 The Computational Advantage
8.4 Arithmetic in General
8.5 Exercises
9 Modern Symmetric Ciphers—DES and AES
9.1 History
9.1.1 Criticism and Controversy
9.2 The Advanced Encryption Standard
9.3 The AES Algorithm
9.3.1 Polynomial Preliminaries: The Galois Field GF(28)
9.3.2 Byte Organization
9.4 The Structure of AES
9.4.1 The Outer Structure of the Rounds
9.4.2 General Code Details
9.4.3 KeyExpansion
9.4.4 SubBytes
9.4.5 ShiftRows
9.4.6 MixColumns
9.4.7 AddRoundKey
9.5 Implementation Issues
9.5.1 Software Implementations
9.5.2 Hardware Implementations
9.6 Security
9.7 Exercises
10 Asymmetric Ciphers—RSA and Others
10.1 History
10.2 RSA Public-Key Encryption
10.2.1 The Basic RSA Algorithm
10.3 Implementation
10.3.1 An Example
10.4 How Hard Is It to Break RSA?
10.5 Other Groups
10.6 Exercises
11 How to Factor a Number
11.1 Pollard rho
11.2 Pollard p-1
11.2.1 The General Metaphysics of p-1
11.2.2 Step Two of p-1
11.3 CFRAC
11.3.1 Continued Fractions
11.3.2 The CFRAC Algorithm
11.3.3 Example
11.3.4 Computation
11.4 Factoring with Elliptic Curves
11.5 Exercises
12 How to Factor More Effectively
12.1 Shortcomings of CFRAC
12.2 The Quadratic Sieve
12.2.1 The Algorithm
12.2.2 The Crucial Reasons for Success and Improvement over CFRAC
12.3 Once More Unto the Breach
12.4 The Multiple Polynomial Quadratic Sieve
12.4.1 Yet One More Advantage
12.5 The Number Field Sieve
12.6 Exercises
13 Cycles, Randomness, Discrete Logarithms, and Key Exchange
13.1 Introduction
13.2 The Discrete Logarithm Problem
13.3 Difficult Discrete Log Problems
13.4 Cycles
13.5 Cocks-Ellis-Williamson/Diffie-Hellman Key Exchange
13.5.1 The Key Exchange Algorithm
13.6 The Index Calculus
13.6.1 Our Example
13.6.2 Smooth Relations
13.6.3 Matrix Reduction
13.6.4 Individual Logarithms
13.6.5 Asymptotics
13.7 Key Exchange with Elliptic Curves
13.8 Key Exchange in Other Groups
13.9 How Hard Is the Discrete Logarithm Problem?
13.10 Exercises
14 Elliptic Curve Cryptography
14.1 Introduction
14.1.1 Jacobian Coordinates
14.2 Elliptic Curve Discrete Logarithms
14.3 Elliptic Curve Cryptography
14.4 The Cost of Elliptic Curve Operations
14.4.1 Doubling a Point
14.4.2 Left-to-Right ``Exponentiation''
14.5 The NIST Recommendations
14.6 Attacks on Elliptic Curves
14.6.1 Pohlig-Hellman Attacks
14.6.2 Pollard Rho Attacks
14.6.3 Pollard Rho for Curves
14.6.4 Pollard Rho in Parallel
14.7 A Comparison of Complexities
14.8 Exercises
15 Lattice-Based Cryptography and NTRU
15.1 Quantum Computing
15.2 Lattices: An Introduction
15.3 Hard Lattice Problems
15.4 NTRU
15.5 The NTRU Cryptosystem
15.5.1 Parameters
15.5.2 Creating Keys
15.5.3 Encrypting a Message
15.5.4 Decrypting a Message
15.5.5 Why This Works
15.5.6 Preventing Errors in Decryption
15.6 Lattice Attacks on NTRU
15.7 The Mathematics of the Lattice Reduction Attack
15.7.1 Other Attacks on NTRU
15.7.2 Lattice Reduction
15.8 NTRU Parameter Choices
15.9 Exercises
16 Homomorphic Encryption
16.1 Introduction
16.2 Somewhat Homomorphic Encryption
16.3 Fully Homomorphic Encryption
16.4 Ideal Lattices
16.5 Learning with Errors
16.6 Security, and Homomorphic Evaluation of Functions
16.7 An Apologetic Summary
A An Actual World War I Cipher
A.1 Introduction
A.2 The Message
A.3 Language Determination
A.4 An Initial Blocking
A.5 Cribbing the Sequence
A.6 Putting It All Together
A.7 Further Guessing
A.8 Continuing the Sequence
A.9 Putting Together the Final Message
B AES Code
B.1 Introduction
B.2 A Revised Appendix B.2
B.3 A Revised Appendix B.3
B.4 A Revised Appendix C
B.4.1 AES Functions
B.4.2 AES Main Program
B.4.3 AES Input/Output Utilities
Index