Instructor Contact and General Information

  
Instructor: Luís Finotti
Office: Ayres Hall 251
e-mail: lfinotti@utk.edu
Office Hours: By appointment only, in person or with Zoom
Textbook: L. Finotti A Practical and Computational Introduction to Mathematical Cryptography, 2025. (Freely available.)
Prerequisites: None.
Class Meeting Time: TuTh 12:55-2:10 via Zoom.
Exams: No exams.
Grade: Simply your HW (computer projects) grade.
See here for letter grade ranges.
 

Back to the TOP.

Course Information

Course Description

This course introduces the basic mathematical ideas, implementations, and vulnerabilities of methods to keep sensitive data safe against malicious attacks, and to authenticate electronic documents publicly available.

We will discuss the methods of encryption and digital signature in detail, describe the mathematical ideas behind them, implement these methods, work on concrete examples, discuss possible security concerns and vulnerabilities, including discussions and implementations of the most efficient known methods of attack.

Although we will discuss mathematical concepts in order to describe the methods and why they are considered safe against malicious attacks, our approach will mostly computational, and we will introduce computer tools that we will perform the all computations involved.

Textbook

We will closely follow the book A Practical And Computational Introduction to Mathematical Cryptography by L. Finotti. The book also contains the homework sets for our course.

The book is free and available online. You are also able to download the Jupyter notebooks used in each chapter to test the code used. (Note that you will need to have Sage and the JupyterLab Myst Extension installed to run these.)

Learning Objectives and Outcomes

Upon completing this course, students should:

We also expect that the course will foster some mathematical and programming development. Students with a stronger mathematical background should appreciate the challenges of implementing computational methods, and student with a stronger programming background should appreciate how mathematical ideas can yield great gains in computational performance.

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. and elliptic curve cryptography and digital signature.

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. and related computational problems.

Schedule

Here is an approximate breakdown for each 3-credit hours/week, (subject to change):

  1. General introduction, Introduction to Cryptography, and start of Introduction to Python, Sage, and Jupyter Notebooks.
  2. Continue with Introduction to Python, Sage, and Jupyter Notebooks.
  3. Number Theory.
  4. Modular Arithmetic. Homework 1 due.
  5. Powers in $\mathbb{Z}/m\mathbb{Z}$.
  6. Discrete Logs, Diffie-Hellman Key Exchange, and the ElGamal Cryptosystem and Computing Discrete Logs. Homework 2 due.
  7. The Chinese Remainder Theorem and Generalized Bezout’s Lemma, Improvements on Computations of Discrete Logs. Homework 3 due.
  8. The RSA Cryptosystem, Primality Testing. Homework 4 due.
  9. Factorization, start Square Roots Modulo $m$. Homework 5 due.
  10. Continue Square Roots Modulo $m$. Homework 6 due.
  11. Quadratic Sieve and Index Calculus. Homework 7 due.
  12. Digital Signatures and start Elliptic Curves. Homework 8 due.
  13. Continue Elliptic Curves. Homework 9 due.
  14. Catch up, final remarks, examples, Q&A. Homework 10 due.

Prerequisites

We will assume no background in programming and math above high school algebra. We will introduce the basic programming and mathematical skills necessary during the course. But experience in programming, especially in Python, and mathematical maturity could certainly make the learning curve less steep.

Homework

In the homework you will implement and test methods for cryptography, digital signatures, and related mathematical problems. You will code the corresponding routines using Sage.

Each homework consists of a Jupyter notebooks containing four or five problems in which you will write code related to the material covered. Most of the problems in a set contains testing routines that allow you to check if your code is working.

If you followed all the instructions of the assignment, and your code passes the tests, you should get full credit (or close) for the problem. But read the instructions carefully, as there are requirements and limitations on what you are allowed to use in some of the problems. Failing to comply with the instructions might make your problem void (i.e., you will get no credit for it), even if it passes all tests.

Although the homework sets are already available at the book site, these will also be distributed, collected, and returned (graded) directly in Canvas.

Assessments and Grades

Your grade will be based on the ten homework sets only. There are no exams or other projects.

Your grade will be the average of the grades for each homework set, with the lowest score dropped.

Sage and Cocalc

We will use Sage for coding. Sage is a free and open source software for mathematics, and particularly strong in number theory, so quite suitable for our course.

Sage is built on top of Python, but provide many mathematical tools that make it more suitable for our course. It can be installed directly, at not cost, in most computers.

If you do not want or are unable to install Sage in your personal computer, you can still run it Cocalc. It has free, but limited accounts, that allows you to run Sage on your browser. There are low cost accounts that are more capable, although a free account should suffice.

Additional Bibliography

The following books are resources are not requires, but might be helpful and can provide more details in many of the topics covered

  1. J. Hoffstein, J. Pipher, J. H. Silverman. An Introduction to Mathematical Cryptography, 2nd edition, Springer, 2014. This is an excellent book covering all we cover here and more. Our textbook borrowed a lot from it.
  2. W. Trappe and L. C. Washington, Introduction to Cryptography with Coding Theory, 2nd Ed., 2006, Pearson. Another good book!
  3. W. Stein, Elementary Number Theory. (Freely available.) This is more of traditional number theory book, but was written by the creator of Sage, and has many computations using it. It does show the RSA cryptosystem, though, and serves as a very good (and free) reference to elementary number theory and some of the more theoretical aspects we will use.
  4. V. Shoup, A Computational Introduction to Number Theory and Algebra, 2nd Edition, Cambridge, 2008. A freely available book that has many algorithms for number theory.
Back to the TOP.

Course Tools

Sage

Sage is a (free) open-source math software. It was started by William Stein and was built on top of many other open-source software, such as GP/Pari, Maxima, GAP, R, and many more. Its intent is to offer an open-source alternative to commercial math software, such as Mathematica, Maple, Matlab and Magma.

Since Stein is a number theorist, Sage is particular strong in number theory (the main mathematical field used in cryptography), and it’s the most suitable to our course. Moreover, it’s free and it can be used directly in Cocalc, which we will use for HW. So, students don’t even have to download it (although it might be a good idea). In fact, Cocalc was originally named “SageMathCloud”, i.e., it was built to run Sage on the cloud.

Moreover, Sage is built on top of Python, and so it has the same syntax and can load the numerous Python libraries.

Cocalc

Cocalc, originally called “SageMathCloud”, is an online computing environment. You will only need it if you do not want (or are not able) to install Sage in your own computer! It was first created to use Sage (and its components) online, without the need of installation, and allowing users to share and collaborate. It has expanded considerably since then, and today it can be even used for course management, as we will use here.

It can also be used for Python (including using Jupyter Lab), for producing text documents with LaTeX or Markdown.

You can use Cocalc for free, although it might be a bit slow. It should not be a problem as your work should not be very resource intensive. But, if you feel it is too slow, you can either install Sage in your personal computer (it’s free and open-source) or pay for a course license.

Ed (Discussion Board)

We will use Ed for online discussions. The advantage of Ed (over other discussion boards) is that it allows us (or simply me) to use math symbols efficiently and with good looking results (unlike Canvas) and to post (and run!) formatted code. It also allows anonymous posts (also unlike Canvas).

To enter math, you can use LaTeX code. (See the section on LaTeX below.) Even if you don’t take advantage of this, I can use it making it easier for you to read the answers.

It also allows us to enter code in Code Blocks and Snippets Snippets. (See the Quick Start Guide.) With Snippets we can even run the code, using both Sage and (pure) Python. Please use code blocks whenever entering code!

You can access Ed through here: https://edstem.org/us/courses/81370/admin/discussion. (There is also a link at the “Navigation” section on the top of this page and on the Links section.)

To keep things organized, I’ve set up a few different categories for our discussions:

I urge you to use Ed often for discussions! (This is specially true for Feedback!) If you are ever thinking of sending me an e-mail, think first if it could be posted there. That way my answer might help others that have the same questions as you and will be always available to all. (Of course, if it is something personal (such as your grades), you should e-mail me instead.)

Note that you can post anonymously. (Just be careful to check the proper box!) But please don’t post anonymously if you don’t feel compelled to, as it would help me to know you, individually, much better.

Students can (and should!) reply to and comment on posts on Ed. Discussion is encouraged here!

Also, please don’t forget to choose the appropriate category for your question. And make sure to choose between Question and Post.

When replying/commenting/contributing to a discussion, please do so in the appropriate place. If it is an answer to the question, use the Answer area. If you have a comment, question, or suggestion, you can use the Comment area.

You can also use Ed for Private Posts, by checking the corresponding box. Posts marked as private will be only viewed by the student who posted and me. Only use this what you have to ask cannot be shared with all, e.g., if you are sharing something from your HW. Otherwise, don’t make it private, as other students might have the same questions as you.

You should receive an invitation to join our class in Ed via your “@vols.utk.edu” e-mail address before classes start. If you don’t, you can sign up here: https://edstem.org/us/join/6ZAMAz. If you’ve register with a different e-mail (e.g., @tennessee.edu) you do not need to register again, but you can consolidate your different e-mails (like @vols.utk.edu and @tennessee.edu) in Ed, so that it knows it is the same person. (Only if you want to! It is recommended but not required as long as you have access to our course there!) Just click on the Account icon on the top right of Ed, select Emails, and then Add email address.

Back to the TOP.

Course Policies

Homework Policy

The due dates for the homework will be available in Canvas.

Late homework will incur a penalty of 10% per day, unless a valid excuse is provided.

Assignments are individual! You can work with someone else and ask for help, but you should be able to understand the ideas and write your own code!

Also, it should go without saying that you cannot copy code you find in the internet or use AI. It is usually easy to spot these and you will be penalized for doing it!

If you are having difficulty, please just ask me (or a colleague) for hints/help.

Why can’t I use AI if I will (probably) use it in real life?

Artificial Intelligence (AI) can be a very useful tool and I encourage its use in many instances. But the goals here are to:

These are important skills that you will not acquire if you do not do the work.

After you acquire these skills, you can use AI to make your life easier, as by then you will be able to catch its mistakes and improve on it! If you never lean the skills, you will have to rely on the results, which can often be incorrect!

Communications and E-Mail Policy

I will contact students and post announcements through Canvas. You should set up notifications in Canvas to be sent to you immediately. Check this page to set your notifications. Set notifications for Announcements to “right away”! (Basically: click on the the profile button on left, under UT’s “T”, then click “Notifications”. Click on the check mark ("notify me right away") for Announcements.)

Also, make sure to check your email often, at least twice a day (morning and evening). I will always assume that you’ve read my messages and announcements within 24 hours, and failing to do so is not an excuse to not follow any directions given in on those.

Conduct

All students should be familiar with Hilltopics’ Students Code of Conduct and maintain their Academic Integrity: from Hilltopics Academics:

Integrity

Study, preparation, and presentation should involve at all times the student’s own work, unless it has been clearly specified that work is to be a team effort. Academic honesty requires that the student present their own work in all academic projects, including tests, papers, homework, and class presentation. When incorporating the work of other scholars and writers into a project, the student must accurately cite the source of that work. For additional information see the applicable catalog or the UT Libraries site. See also the Student Code of Conduct and Honor Statement (below).

All students should follow the Honor Statement (also from Hilltopics Academics):

Honor Statement

"An essential feature of the University of Tennessee, Knoxville, is a commitment to maintaining an atmosphere of intellectual integrity and academic honesty. As a student of the university, I pledge that I will neither knowingly give nor receive any inappropriate assistance in academic work, thus affirming my own personal commitment to honor and integrity."

We are in a honor system in this course!

Disabilities

Students with disabilities that need special accommodations should contact the Student Disability Services and bring me the appropriate letter/forms.

Discrimination and Harassment

For Discrimination and Harassment, please visit the Office of Equity and Diversity.

Campus Syllabus

Please, see also the Campus Syllabus.

Homework Policy

Homework assigned, graded, and collected in Canvas. You will download Jupyter notebooks in which you will code various tasks related to the course, and then upload the completed notebook back in Canvas. The due dates are posted on Canvas’s calendar, but are still subject to change.

The HW will consist mostly of computations. You will likely code some routines to perform some task, and then run some tests. The official language for the course will be Sage.

Most HW problems will contain some code to test the routines you wrote. Successfully running this tests will, in most cases, give you full score, unless you are breaking some rules, like using a built in function you are not allowed to use, for instance. I will also look for any other errors that might escape the tests, but in most cases, you should get full credit (usually 4 points per problem).

If your code fails to pass the test, but I cannot spot the error, you will lose only 0.5 out of 4 (unless I have any other reason to deduce points). If you do care to know what is actually wrong with it, let me know and I can spend some more time figuring it out.

In the other cases your grade will depend on how far you were from the correct solution.

Your course grade will be simply your HW grade.

Assignments are individual! You can work with someone else and ask for help, but you should be able to understand the ideas and write your own code!

The use of AI is not allowed in this course! Of course, AI can be helpful and is a great tool, but the goal of this course is for you to understand the concepts and algorithms. Once you learn those, you will be able to evaluate and improve code that AI provides you.

Similarly, you cannot just copy code you find in the internet. It is usually easy to spot these and you will be penalized for doing it! If you are having a hard time, ask me (or a colleague) for help instead.

Back to the TOP.

Conduct

All students should be familiar with Hilltopics’ Students Code of Conduct and maintain their Academic Integrity: from Hilltopics Academics:

Integrity

Study, preparation, and presentation should involve at all times the student’s own work, unless it has been clearly specified that work is to be a team effort. Academic honesty requires that the student present their own work in all academic projects, including tests, papers, homework, and class presentation. When incorporating the work of other scholars and writers into a project, the student must accurately cite the source of that work. For additional information see the applicable catalog or the UT Libraries site. See also the Student Code of Conduct and Honor Statement (below).

All students should follow the Honor Statement (also from Hilltopics Academics):

Honor Statement

"An essential feature of the University of Tennessee, Knoxville, is a commitment to maintaining an atmosphere of intellectual integrity and academic honesty. As a student of the university, I pledge that I will neither knowingly give nor receive any inappropriate assistance in academic work, thus affirming my own personal commitment to honor and integrity."

You should also be familiar with the Classroom Behavior Expectations.

We are in a honor system in this course!

 

Disabilities

Students with disabilities that need special accommodations should contact the Student Disability Services and bring me the appropriate letter/forms.

 

Reporting Student Concerns

To report conduct violations, academic misconduct, accessibility barriers, among others, visit Reporting Student Concerns (Dean of Students).

Campus Syllabus

Please, see also the Campus Syllabus.

 

Back to the TOP.

LaTeX

This is not necessary to our class! I leave it here in case someone wants to learn how type math, for instance to type their HW. But again, you can ignore this section if you want to.

LaTeX is the most used software to produce mathematics texts. It is quite powerful and the final result is, when properly used, outstanding! Virtually all professional math text you will ever see is done with LaTeX, or one of its variants.

LaTeX is freely available for all platforms.

The problem is that it has a steep learning curve at first, but after the first difficulties are overcome, it is not bad at all.

One of the first difficulties one encounters is that it is not WYSIWYG ("what you see is what you get"). It resembles a programming language: you first type some code and then this code is processed to produce a nice document (a non-editable PDF file, for example). Thus, one has to learn how to “code” in LaTeX, but this brings many benefits.

I recommend that anyone with any serious interest in producing math texts to learn it! On the other hand, I don’t expect all of you to do so. But note that there are processors that can make it “easier” to create LaTeX documents, by making it “point-and-click” and (somewhat) WYSIWYG.

Here are some that you can use online (no need to install anything and files are available online, but need to register):

The first one, Cocalc, is more than just for LaTeX, as you can also run Sage, which can do computations with the objects we will study in this course.

If you want to install LaTeX in your computer (so that you don’t need an Internet connection), check here.

A few resources:

Back to the TOP.
Back to the TOP.

Handouts

Back to the TOP.