**An Overview of the Subject **

Basic Concepts

Functions

One-to-One and Onto Functions, Bijections

Inverse Functions

Substitution Ciphers

Attacks on Cryptosystems

The Vigenère Cipher

The Playfair Cipher

The One-Time Pad, Perfect Secrecy

**Divisibility and Modular Arithmetic **

Divisibility

Primes

Greatest Common Divisors and Relatively Prime Integers

The Division Algorithm

The Euclidean Algorithm

Modular Arithmetic and Congruencies

Modular Integer Systems

Modular Inverses

Extended Euclidean Algorithm

Solving Linear Congruencies

The Chinese Remainder Theorem

**The Evolution of Codemaking until the Computer Era**

Ancient Codes

Formal Definition of a Cryptosystem

Affine Ciphers

Steganography

Nulls

Homophones

Composition of Functions

Tabular Form Notation for Permutations

The Enigma Machines

Cycles (Cyclic Permutations)

Dissection of the Enigma Machine into Permutations

Special Properties of All Enigma Machines

**Matrices and the Hill Cryptosystem**

The Anatomy of a Matrix

Matrix Addition, Subtraction, and Scalar Multiplication

Matrix Multiplication

Preview of the Fact That Matrix Multiplication Is Associative

Matrix Arithmetic

Definition of an Invertible (Square) Matrix

The Determinant of a Square Matrix

Inverses of 2×2 Matrices

The Transpose of a Matrix

Modular Integer Matrices

The Classical Adjoint (for Matrix Inversions)

The Hill Cryptosystem

**The Evolution of Codebreaking until the Computer Era**

Frequency Analysis Attacks

The Demise of the Vigenère Cipher

The Index of Coincidence

Expected Values of the Index of Coincidence

How Enigmas Were Attacked

Invariance of Cycle Decomposition Form

**Representation and Arithmetic of Integers in Different Bases**

Representation of Integers in Different Bases

Hex(adecimal) and Binary Expansions

Arithmetic with Large Integers

Fast Modular Exponentiation

**Block Cryptosystems and the Data Encryption Standard (DES) **

The Evolution of Computers into Cryptosystems

DES Is Adopted to Fulfill an Important Need

The XOR Operation

Feistel Cryptosystems

A Scaled-Down Version of DES

DES

The Fall of DES

Triple DES

Modes of Operation for Block Cryptosystems

**Some Number Theory and Algorithms**

The Prime Number Theorem

Fermat’s Little Theorem

The Euler Phi Function

Euler’s Theorem

Modular Orders of Invertible Modular Integers

Primitive Roots

Order of Powers Formula

Prime Number Generation

Fermat’s Primality Test

Carmichael Numbers

The Miller–Rabin Test

The Miller–Rabin Test with a Factoring Enhancement

The Pollard *p* – 1 Factoring Algorithm

**Public Key Cryptography **

An Informal Analogy for a Public Key Cryptosystem

The Quest for Secure Electronic Key Exchange

One-Way Functions

Review of the Discrete Logarithm Problem

The Diffie–Hellman Key Exchange

The Quest for a Complete Public Key Cryptosystem

The RSA Cryptosystem

Digital Signatures and Authentication

The El Gamal Cryptosystem

Digital Signatures with El Gamal

Knapsack Problems

The Merkle–Hellman Knapsack Cryptosystem

Government Controls on Cryptography

A Security Guarantee for RSA

**Finite Fields in General and ***GF*(2^{8}) in Particular

Binary Operations

Rings

Fields

Z_{p}[*X*] = the Polynomials with Coefficients in Z_{p}

Addition and Multiplication of Polynomials in Z_{p}[*X*]

Vector Representation of Polynomials

Z_{p}[*X*] Is a Ring

Divisibility in Z_{p}[*X*]

The Division Algorithm for Z_{p}[*X*]

Congruencies in Z_{p}[*X*] Modulo a Fixed Polynomial

Building Finite Fields from Z_{p}[*X*]

The Fields *GF*(2^{4}) and *GF*(2^{8})

The Euclidean Algorithm for Polynomials

**The Advanced Encryption Standard (AES) Protocol**

An Open Call for a Replacement to DES

Nibbles

A Scaled-Down Version of AES

Decryption in the Scaled-Down Version of AES

AES

Byte Representation and Arithmetic

The AES Encryption Algorithm

The AES Decryption Algorithm

Security of the AES

**Elliptic Curve Cryptography**

Elliptic Curves over the Real Numbers

The Addition Operation for Elliptic Curves

Groups

Elliptic Curves over Z_{p}

The Variety of Sizes of Modular Elliptic Curves

The Addition Operation for Elliptic Curves over Z_{p}

The Discrete Logarithm Problem on Modular Elliptic Curves

An Elliptic Curve Version of the Diffie–Hellman Key Exchange

Fast Integer Multiplication of Points on Modular Elliptic Curves

Representing Plaintexts on Modular Elliptic Curves

An Elliptic Curve Version of the El Gamal Cryptosystem

A Factoring Algorithm Based on Elliptic Curves

**Appendix A: Sets and Basic Counting Principles**

Appendix B: Randomness and Probability

Appendix C: Solutions to All Exercises for the Reader

Appendix D: Answers and Brief Solutions to Selected Odd-Numbered Exercises

Appendix E: Suggestions for Further Reading

**References**