About this Book

About this Book#

Table of Contents#

Chapters

Endmatter

Introduction#

This book is an introduction to the main mathematical and computational ideas in cryptography. It is heavily based on selected sections of An Introduction to Mathematical Cryptography, by Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman, which is an excellent introduction to mathematical cryptography. In fact, we strongly recommend the more mathematically inclined readers to use that book in addition to (or perhaps even instead of) this present one. This book does not go nearly as deep in the math, but focus more in computations and applications. For example, we might just give computational evidence that some mathematical statement is true, rather than giving an actual proof. We do prove the easier statements, though, and although these could be skipped by the reader with less interest in the mathematics, we urge them to at least try read them, even if only superficially enough to have a general idea of why the statement is true.

This book was written to serve as a text book for CYBR 201 - Introduction to Cryptography and Data Protection at the University of Tennessee, which the author proposed and developed.

Goal#

The main goal of this book is to introduce the mathematical ideas behind cryptosystems and digital signature methods, but with a very practical and computational approach and with minimal prerequisites in mathematics. By following this book, the reader should be able to understand the underlying mathematical problems on which the security of cryptosystems and digital signatures are based, and the computational challenges associated to them.

We hope that by following this book, the more mathematically inclined, but with less experience with coding, should realize the difficulties of finding efficient methods for computations of even the most basic mathematical objects. Finding these methods requires a shift on how we think about mathematical problems.

On the other hand, the more computationally inclined readers, but with less mathematical background, should realize that mathematical insights quite often yield much greater gains than any clever coding.

Those who are just starting with both the math and programming at this level will hopefully appreciate the important relation between the two approaches in a very practical and concrete setting.

This way, we hope that all these groups should benefit from this book.

Topics#

The main goal it to cover the following applications:

  1. Diffie-Hellman Key Exchange,

  2. the ElGamal Cryptosystem,

  3. the RSA Cryptosystem,

  4. the RSA, ElGamal, DSA digital signatures,

  5. elliptic curve cryptography and digital signature,

  6. and the Advanced Encryption Standard (AES).

We will also discuss the main methods of attack to these, by discussing efficient methods for factorization and computing discrete logs, such as:

  1. Collision (Shank’s Baby-Step/Giant-Step Algorithm) (for computing discrete logs),

  2. the Pohlig-Hellman Algorithm (for computing discrete logs),

  3. Index Calculus (for computing discrete logs in \(\mathbb{F}_p^{\times}\)),

  4. Pollard’s \(p-1\) factorization algorithm,

  5. Factorization via Difference of Squares,

  6. the Quadratic Sieve.

To properly cover this topics, we need to cover some basic Number Theory, including:

  1. Long Division,

  2. Prime Numbers,

  3. Greatest Common Divisor, including the Euclidean Algorithm and Extended Euclidean Algorithm,

  4. Fundamental Theorem of Arithmetic,

  5. Congruences,

  6. Integers Modulo \(m\) and its units,

  7. Euler's Theorem and Fermat's Little Theorem,

  8. the Chinese Remainder Theorem,

  9. Primality Testing (including the Miller-Rabin Probabilistic Test),

  10. Quadratic Reciprocity,

  11. Square Roots Modulo \(m\),

  12. Elliptic Curves,

  13. Finite Fields,

  14. and related computational problems.

We will also have a very practical approach when covering this theory. Although we will provide proofs to the simpler results, we often will just demonstrate statements with some concrete computations. Concrete examples will also be provided to illustrate the statements. Moreover, the computations will always be done with the help of Sage. Hence, although our goal is to illustrate the importance of mathematics in cryptography, we do not require any higher-level background in mathematics.

We will also give a brief introduction to the basic tools of Python and Sage necessary for the course.

Computations#

There is a large focus on computations, since the challenges involved in creating and breaking cryptosystems are computational in nature. Therefore we will focus on computational methods in Number Theory, the main mathematical background for the cryptosystems introduced here. We will discuss many methods and algorithms, but always with a practical goal.

We will not assume any previous background in Number Theory, but we will introduce the needed results as we progress.

Sage#

We will use Sage as the main programming language for our examples. Sage is based on Python, which is a simple and yet powerful programming language, often taught as a first programming language. Sage uses the same syntax as Python, so it should be easy for those who already know Python to use Sage, while been a suitable introduction to programming as well.

Sage adds a lot more mathematical functionality to Python out of the box, making the implementation and testing of the methods in this book a lot easier, when compared to plain Python.

As with Python, Sage if free and open source. It can be installed directly in the users computer or used online with Cocalc.

We will not assume that the reader has any previous experience with coding, and introduce the necessary background in the text. But experience with coding, especially in Python, would certainly benefit the reader.

Homework#

We suggest the reader complete the corresponding homework assignments. These implement methods and algorithms described in the text, and therefore are computational (rather than purely mathematical) in nature. The goal is to reinforce the ideas introduced and allow the reader to experience the difficulties and efficiency differences between different methods.

These are available as Jupyter Notebooks that should be run using Sage as the kernel. These notebooks will not work with pure Python!

Most routines that the reader will implement are available in Sage already, and in fact these will be used to test the reader’s code in the homework. But, again, the goal is not to have the final product/tool, it is to understand how these methods work, what they involve, what is the math behind it, and to see in them working in practice.

Hopefully the homework give the reader practice with coding, with a particular care about efficiency.

Source Notebooks#

The source Jupyter notebooks from each chapter used to create this book can be downloaded directly from the official site https://luisfinotti.org/pcimc/. Just click on the Download icon on the top of the page and choose .ipynb.

Important: To be able to run this properly, a Sage kernel must be used. And, for the notebook to be displayed correctly, the JupyterLab MyST Extension must be installed in the system.

Unfortunately, the links to different notebooks will not work.

Corrections#

Please send any typos, corrections (mathematical or grammatical), problems, and suggestions to luis@luisfinotti.org.

About the Author#

Luís Finotti received his B.Sci. and M.Sci. in Mathematics from the Universidade de São Paulo in Brazil, and his Ph.D. in 2001 from the University of Texas at Austin, studying with Felipe Voloch and specializing in Number Theory.

He had post-doctoral appointments at the University of California Santa Barbara and the Ohio State University. He has been at the University of Tennesse Knoxville since 2006.

His research interests include liftings of algebraic curves and varieties, specially elliptic and hyperelliptic curves, Witt vectors, local and \(p\)-adic fields, and related computational problems and applications.

Acknowledgments#

The book An Introduction to Mathematical Cryptography, by Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman, was the main resource for this book, along with class notes from the author on a course based in that book.

This book was produced using Jupyter notebooks and Jupyter Book. MyST Markdown (and LaTeX) were used to type and render the text. The computations were done with Sage.

This book was written during a semester in which the College of Emerging and Collaborative Studies at the University of Tennessee reduced the author’s teaching load, allowing the writing of this book. The teaching reduction was given so the author could develop the new course CYBR 201 - Introduction to Cryptography and Data Protection, and although writing the book was not a requirement, the extra time allowed the author to do it. Therefore, the author would like to thank the University of Tennessee, the College of Emerging and Collaborative Studies , and UT’s Math Department for their support.

Contents