1st Edition

# Introduction to Cryptography with Mathematical Foundations and 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.

**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 PrinciplesAppendix B: Randomness and ProbabilityAppendix C: Solutions to All Exercises for the ReaderAppendix D: Answers and Brief Solutions to Selected Odd-Numbered ExercisesAppendix E: Suggestions for Further Reading**

**References**

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

### Biography

**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.

This book is a very comprehensible introduction to cryptography. It will be very suitable for undergraduate students. There is adequate material in the book for teaching one or two courses on cryptography. The author has provided many mathematically oriented as well as computer-based exercises. I strongly recommend this book as an introductory book on cryptography for undergraduates.

—IACR Book Reviews, April 2011… a particularly good entry in a crowded field. … As someone who has taught cryptography courses in the past, I was particularly impressed with the scaled-down versions of DES and AES that the author describes … . Stanoyevitch’s writing style is clear and engaging, and the book has many examples illustrating the mathematical concepts throughout. … One of the many smart decisions that the author made was to also include many computer implementations and exercises at the end of each chapter. … It is also worth noting that he has many MATLAB implementations on his website. … It is clear that Stanoyevitch designed this book to be used by students and that he has taught this type of student many times before. The book feels carefully structured in a way that builds nicely … it is definitely a solid choice and will be on the short list of books that I would recommend to a student wanting to learn about the field.

—MAA Reviews, May 2011I perused the structure, the writing, the pedagogical approach/layout: I can recognize a labor of pedagogical love when I see one. Certainly, the colloquial but still rigorous approach makes the concepts accessible, and the worked out solutions for the student, the much-needed and appreciated chapter on finite fields, and the division of problems into theory and programming are sensible. But it is the little thoughtful touches that make the book truly shine: the position of the notation index right on the front cover; the historical excursions as mental relief to keep students’ interest peaked; judicious use of accessible examples plus step-by-step worked out math to illustrate concepts; and whitespace in the margin for notes, the text layout with breathing room to offset the inevitable terseness of mathematical cryptology. It is apparent that Prof. Stanoyevitch put a lot of pedagogical and intellectual effort into making a

textbook— a book aimed at students that makes life easier for the instructor. In addition, the book’s companion site features short MATLAB m-files and applets for quick demos. The Index of Algorithms is useful. In short, this is a very well done, thoughtful introduction to cryptography.

—Daniel Bilar, Department of Computer Science, University of New Orleans, Louisiana, USA