Introduction to Cryptography ─ With Mathematical Foundations in Computer Implementations

From the exciting history of its development in ancient times to the present day, Introduction to Cryptography with Mathematical Foundations and Computer Implementations provides a focused tour of the central concepts of cryptography. Rather than present an encyclopedic treatment of topics in cryptography, it delineates cryptographic concepts in chronological order, developing the mathematics as needed.

Written in an engaging yet rigorous style, each chapter introduces important concepts with clear definitions and theorems. Numerous examples explain key points while figures and tables help illustrate more difficult or subtle concepts. Each chapter is punctuated with "Exercises for the Reader;" complete solutions for these are included in an appendix. Carefully crafted exercise sets are also provided at the end of each chapter, and detailed solutions to most odd-numbered exercises can be found in a designated appendix. The computer implementation section at the end of every chapter guides students through the process of writing their own programs. A supporting website provides an extensive set of sample programs as well as downloadable platform-independent applet pages for some core programs and algorithms.

As the reliance on cryptography by business, government, and industry continues and new technologies for transferring data become available, cryptography plays a permanent, important role in day-to-day operations. This self-contained sophomore-level text traces the evolution of the field, from its origins through present-day cryptosystems, including public key cryptography and elliptic curve cryptography.

Alexander Stanoyevitch is a professor at California State University-Dominguez Hills. He completed his doctorate in mathematical analysis at the University of Michigan, Ann Arbor, and has held academic positions at the University of Hawaii and the University of Guam. Dr. Stanoyevitch has taught many upper-level classes to mathematics and computer science students, has published several articles in leading mathematical journals, and has been an invited speaker at numerous lectures and conferences in the United States, Europe, and Asia. His research interests include areas of both pure and applied mathematics.

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(28) in Particular
Binary Operations
Rings
Fields
Zp[X] = the Polynomials with Coefficients in Zp
Addition and Multiplication of Polynomials in Zp[X]
Vector Representation of Polynomials
Zp[X] Is a Ring
Divisibility in Zp[X]
The Division Algorithm for Zp[X]
Congruencies in Zp[X] Modulo a Fixed Polynomial
Building Finite Fields from Zp[X]
The Fields GF(24) and GF(28)
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 Zp
The Variety of Sizes of Modular Elliptic Curves
The Addition Operation for Elliptic Curves over Zp
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

Exercises and Computer Implementations appear at the end of each chapter.