Fundamentals of Cryptography: Introducing Mathematical and Algorithmic Foundations (Undergraduate Topics in Computer Science)

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