arminstraub.com

# Spring 2024: Cryptography (Math 481/581)

## Overview

 Instructor Dr. Armin Straub MSPB 313 straub@southalabama.edu (251) 460-7262 (please use e-mail whenever possible) Office hours MWF, 9-11am, or by appointment Lecture MWF, 1:25-2:15pm, in MSPB 370 Midterm exams The tentative dates for our two midterm exams are: Friday, February 16 Friday, March 29 Final exam Wednesday, May 1 — 1:00pm-3:00pm Online grades Homework Scores Exams: USAonline (Canvas) Syllabus syllabus.pdf

## Lecture sketches and homework

To help you study for this class, I am posting lecture sketches. These are not a substitute for your personal lecture notes or coming to class (for instance, some details and motivation are not included in the sketches). I hope that they are useful to you for revisiting the material and for preparing for exams.

Date Sketch Homework
01/08 lecture01.pdf Homework Set 1: Problems 1-7 (due 1/22)
01/10 lecture02.pdf Homework Set 1: Problems 8-10 (due 1/22)
01/12 lecture03.pdf Homework Set 1: Problems 11-12 (due 1/22)
01/17 lecture04.pdf Homework Set 2: Problems 1-3 (due 1/29)
01/19 lecture05.pdf Homework Set 2: Problems 4-7 (due 1/29)
01/22 lecture06.pdf Homework Set 2: Problems 8-9 (due 1/29)
01/24 lecture07.pdf Homework Set 3: Problems 1-3 (due 2/5)
01/26 lecture08.pdf Homework Set 3: Problem 4 (due 2/5)
01/29 lecture09.pdf Homework Set 3: Problems 5-6 (due 2/5)
01/31 lecture10.pdf Homework Set 4: Problems 1-2 (due 2/12)
02/02 lecture11.pdf Homework Set 4: Problems 3-4 (due 2/12)
02/05 lecture12.pdf Homework Set 4: Problems 5-9 (due 2/12)
02/07 lecture13.pdf Homework Set 5: Problem 1 (due 2/19)
02/09 lecture14.pdf Homework Set 5: Problem 2 (due 2/19)
02/12 lecture15.pdf Homework Set 5: Problems 3-4 (due 2/19)
02/14 review get ready for the midterm exam on 2/16 (Friday)
exam practice problems (as well as solutions) are posted below
02/19 lecture16.pdf Homework Set 6: Problem 1 (due 3/11)
02/21 lecture17.pdf Homework Set 6: Problems 2-3 (due 3/11)
02/23 lecture18.pdf Homework Set 6: Problem 4 (due 3/11)
02/26 lecture19.pdf Homework Set 6: Problems 5-6 (due 3/11)
02/28 lecture20.pdf Homework Set 7: Problems 1-2 (due 3/18)
homework07-example-problems.pdf
03/01 lecture21.pdf Homework Set 7: Problems 3-4 (due 3/18)
homework07-example-problems.pdf
03/11 lecture22.pdf Homework Set 7: Problems 5-8 (due 3/18)
homework07-example-problems.pdf
03/13 lecture23.pdf Homework Set 8: Problems 1-2 (due 3/25)
homework08-example-problems.pdf
03/15 lecture24.pdf Homework Set 8: Problems 3-4 (due 3/25)
homework08-example-problems.pdf
03/18 lecture25.pdf Homework Set 8: Problems 5-7 (due 3/25)
homework08-example-problems.pdf
03/20 lecture26.pdf Homework Set 9: Problems 1-3 (due 3/29)
homework09-example-problems.pdf
03/22 lecture27.pdf Homework Set 9: Problems 4-9 (due 3/29)
homework09-example-problems.pdf
03/25 lecture28.pdf work through exam practice problems
03/27 review get ready for the midterm exam on 3/29 (Friday)
exam practice problems (as well as solutions) are posted below
04/01 lecture29.pdf work through Example 183
04/03 lecture30.pdf Homework Set 10: Problem 1 (due 4/15)
homework10-example-problems.pdf
04/05 lecture31.pdf work through Example 206
04/08 lecture32.pdf Homework Set 10: Problems 2-3 (due 4/15)
homework10-example-problems.pdf
04/12 lecture33.pdf Homework Set 11: Problem 1 (due 4/22)
homework11-example-problems.pdf
04/15 lecture34.pdf work through Examples 220, 221
04/17 lecture35.pdf Homework Set 11: Problems 2-5 (due 4/24)
homework11-example-problems.pdf
04/19 lecture36.pdf finish all homework
04/22 lecture37.pdf start preparing for the final exam
exam practice problems (as well as solutions) are posted below
04/24 review get ready for the final exam on 5/1 (Wednesday)
04/26 review retake old midterm exams
lectures-all.pdf (all lecture sketches in one big file)
Overview of all homework problems

• Homework problems are posted for each unit. Homework is submitted online, and you have an unlimited number of attempts. Only the best score is used for your grade.

Most problems have a random component (which allows you to continue practicing throughout the semester without putting your scores at risk).

• Aim to complete the problems well before the posted due date.

A 15% penalty applies if homework is submitted late.

• Collect a bonus point for each mathematical typo you find in the lecture notes (that is not yet fixed online), or by reporting mistakes in the homework system. Each bonus point is worth 1% towards a midterm exam.

The homework system is written by myself in the hope that you find it beneficial. Please help make it as useful as possible by letting me know about any issues!

## Sage

For more involved calculations, we will explore the open-source free computer algebra system Sage.

If you just want to run a handful quick computations (without saving your work), you can use the text box below.

A convenient way to use Sage more seriously is https://cocalc.com. This free cloud service does not require you to install anything, and you can access your files and computations from any computer as long as you have internet. To do computations, once you are logged in and inside a project, you will need to create a "Sage notebook" as a new file.

Here are some other things to try:

• The following is our naive implememtation of the Blum-Blum-Shub pseudorandom generator based on the 1024 bit number from the RSA Factoring Challenge (of course, if needed for cryptographic purposes, we would need to be more careful about how to generate the seed itself):
N = Integer("135066410865995223349603216278805969938881475605667027524485143851\
526510604859533833940287150571909441798207282164471551373680419703\
964191743046496589274256239341020864383202110372958725762358509643\
110564073501508187510676594629205563685529475213500852879416377328\
533906109750544334999811150056977236890927563")
seed = randint(2,N-2)
y = seed; prg = []
for i in [1..25]:
y = power_mod(y, 2, N)
prg.append(y % 2)
prg

• The following illustrates how to make a simple plot using Sage. Here, we are plotting the number of primes against the estimate from the prime number theorem:
plot([prime_pi(x), x/ln(x)], 2, 200)

• To illustrate that Fermat liars are rare, we determine all numbers up to 5000, for which 2 is a Fermat liar:
[ n for n in [1..5000] if not is_prime(n) and power_mod(2, n-1, n) == 1 ]

• Sage knows about finite fields. For instance, we can compute inverses as follows (this solves Example 140(b) in Lecture 21):
x = var('x')
F.<x> = GF(2^8, modulus=x^8+x^4+x^3+x+1)
(x^3+1).inverse()

• Sage is excellent at computations with elliptic curves. For instance, on the elliptic curve \$ y^2 = x^3-x+9 \$ we can add the points \$ (0,3) \$ and \$ (1,-3) \$ as follows (see Example 222 in Lecture 35):
E = EllipticCurve([-1,9])
E(0,3) + E(1,-3)

## Projects

If you take this class for graduate credit, you need to complete a project. The idea is to gain additional insight into a topic that you are particularly interested in. Some suggestions for projects are listed further below.

• The outcome of the project should be a short paper (about 5 pages)
• in which you introduce the topic, and then
• describe how you explored the topic.
Here, exploring can mean (but is not limited to)
• computations or visualizations you did in, say, Sage,
• working out representative examples, or
• combining different sources to get an overall picture.

Each project should have either a computational part (this is a great chance to play with Sage!) or have a more mathematical component. Here are some ideas:

• NIST currently has approved 14 block cipher modes, including ECB and CBC that we discussed in class. Pick one of the other modes, such as Counter Mode (CTR), describe it and provide examples.
• Compute and investigate the number of Fermat liars and/or strong liars. For instance, a theoretical result states that at most a quarter of the residues can be strong liars. What proportions do you observe numerically?
• Using frequency analysis (letters, digrams, trigrams and such), can you (more or less automatically) distinguish, say, different languages or maybe even individual authors. This would be a computational project. The exact focus is up to you.
• What are the periods of LFSRs and LCGs? When are they maximal? Discuss mathematical results in the spirit of what is hinted at in the lecture notes.
• When we say that a pseudorandom generator should have good statistical properties, what exactly do we mean? What tests do people apply in practice to evaluate pseudorandom generators?
• Go into more detail on the prime number theorem. How is it related to the Riemann zeta function and the Riemann hypothesis? (This is advanced math!) What goes into its proof? Explore it numerically.
• Discuss finite fields and their classification. This would be a more mathematical project and should include proving basic results on finite fields.
• Describe the main ideas involved in finding the first collision found for SHA-1
• Introduce RSA-OAEP, which is RSA in randomized form with padding.
• Discuss Lucas pseudoprimes, which are described in the 1980 paper by Baillie and Wagstaff. You could either include mathematical details, such as proofs, or implement the corresponding primality test and experimentally analyze the failure rate.
• With quantum computers on the horizon, research a post-quantum cryptographic scheme like lattice-based cryptography or code-based cryptography. You could focus on describing the math and/or experiment with a library.
You are also very welcome to come up with your own ideas for a project. Please talk to me early with about your choice of project, so I can give you a green light.