arminstraub.com

# Spring 2017: Cryptography (Math 481/581)

## Overview

 Instructor Dr. Armin Straub ILB 313 straub@southalabama.edu (251) 460-7262 (please use e-mail whenever possible) Office hours MW, 9:05-1:15pm, or by appointment Lecture MWF, 1:25-2:15pm, in ILB 465. Midterm exams The tentative dates for our two midterm exams are: Wednesday, February 22 Wednesday, April 5 Final exam Wednesday, May 3 — 1:00-3:00pm Text Introduction to Cryptography with Coding Theory by Wade Trappe and Lawrence C. Washington (Prentice Hall, 2nd Ed., 2006) Online grades USAonline 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, lots of 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.

After most classes, homework is assigned and posted below. This homework will not be collected; instead, it helps you prepare for the quizzes (which will usually be similar to the assigned homework) and our exams.

Date Sketch Homework
01/09 lecture01.pdf finish Example 6 and do Example 7; also review any topic discussed today which you don't recall fully
01/11 lecture02.pdf do Examples 9 and 10; also check out Example 13 as a bonus challenge
send me an email before Friday if you can crack the message
01/13 lecture03.pdf do Examples 16, 19 and 22; also check out Example 23 as a bonus challenge
send me an email before Wednesday if you crack the code
01/18 lecture04.pdf do Examples 29, 31 and 32; also check out Example 30 as a bonus challenge
send me an email before Friday if you can solve the bonus
01/20 lecture05.pdf do Example 42; prepare for Wednesday quiz
the quiz will have three problems: inverting modulo n (generalized Euclidean algorithm), computing powers modulo n (Euler's theorem, followed by binary exponentiation), expressing numbers in different bases
01/23 lecture06.pdf review basic number theory for quiz; also check out Example 43 as a bonus challenge
send me an email before next Monday if you can solve the bonus
01/25 lecture07.pdf do Example 55; also check out Example 54 as a bonus challenge
send me an email before next Monday if you can solve the bonus
01/27 lecture08.pdf do Examples 58, 59 and 60
01/30 lecture09.pdf do Examples 62 and 64
02/01 lecture10.pdf do Example 69; prepare for Friday quiz
The quiz will be similar to Example 64 (probably using 4 instead of 3 bits).
02/03 lecture11.pdf check out Example 72 as a bonus challenge
send me an email before next Wednesday if you can solve the bonus
02/06 lecture12.pdf do Examples 79 and 80; check out Example 76 as a bonus challenge
send me an email before next Wednesday if you can solve the bonus
02/08 lecture13.pdf do Examples 86, 88 and 89
We will have a quiz on Monday covering the Chinese remainder theorem. More details Friday.
02/10 lecture14.pdf do Example 91; finish Example 96
The quiz on Monday will be similar to Examples 80,86,89.
02/13 lecture15.pdf do Example 99; finish Example 98; think about Example 100; review quiz
02/15 lecture16.pdf do Examples 102 and 103; start preparing for our first midterm exam next Wednesday:
midterm01-practice-lecture.pdf (these are problems we discussed in class)
02/17 lecture17.pdf do Example 108; continue preparing for the midterm:
midterm01-practice.pdf, midterm01-practice-solution.pdf
02/20 review get ready for the midterm!
02/24 lecture18.pdf review the midterm (solutions posted below); check out Example 114 as a bonus challenge
send me an email before next Friday if you can solve the bonus
02/27 lecture19.pdf finish Example 117; check out Example 116 as a bonus challenge; enjoy Mardi Gras!
send me an email before next week Wednesday if you can solve the bonus
03/01 lecture20.pdf read through Chapter 4.4 of our book to check out all details of DES
03/03 lecture21.pdf do Examples 122 and 126
03/06 lecture22.pdf think about a project and let me know your choice!
03/08 lecture23.pdf do Example 138
03/10 lecture24.pdf enjoy Spring break!
03/20 lecture25.pdf do Examples 142, 143 and 144
03/22 lecture26.pdf do Examples 146 and 148
03/24 lecture27.pdf do Example 155; start working on your project
The quiz on Monday will be similar to Examples 147 and 148.
03/27 lecture28.pdf do Examples 158, 159 and 160
03/29 lecture29.pdf do Examples 162 and 165; start preparing for our first midterm exam next Wednesday:
midterm02-practice-lecture.pdf (these are problems we discussed in class)
03/31 lecture30.pdf continue preparing for the midterm:
midterm02-practice.pdf, midterm02-practice-solution.pdf
04/03 review get ready for the midterm!
04/07 lecture31.pdf review the midterm (solutions posted below); do Example 172
04/10 lecture32.pdf do Examples 177 and 181
04/12 lecture33.pdf do Examples 183, 184
04/14 lecture34.pdf Happy Easter!
Don't forget that the project is due next Friday, April 21.
04/17 lecture35.pdf do Examples 195 and 196; review Examples 190 and 192
04/19 lecture36.pdf do Example 201
04/21 lecture37.pdf turn in project!
04/24 lecture38.pdf start preparing for the final exam:
final-practice.pdf, final-practice-solution.pdf
04/26 lecture39.pdf continue preparing for the final
04/28 review get ready for the final!

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

An easy way to use Sage more seriously is https://cocalc.com. This free cloud service does not require you to make an account or to install anything: after choosing Use CoCalc Anonymously, select View Your CoCalc Projects... (at the bottom of the page), create a project (choose any name for it), followed by New and Sage worksheet and start computing. (To save your work for later, you can create a free account.)

## Exams and practice material

There will be two in-class midterm exams and a comprehensive final exam. Notes, books, calculators or computers are not allowed during any of the exams.

Our tentative exam schedule is:

• Midterm Exam 1: Wednesday, February 22
• Midterm Exam 2: Wednesday, April 5
• Final Exam: Wednesday, May 3 — 1:00-3:00pm

## 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 3-4 pages per student)
• 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.
• Let me know by the end of the week after spring break which topic you choose for your project.
• You may work on a project in groups of up to three students. (Attach a brief statement describing who contributed in what way.)
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 ("basic computational" means suitable for someone with limited background in programming):
• (computational) Obtain letter frequencies (especially trigrams and such) from different sources (books, newspaper articles, forum posts, etc.), and investigate if you can (more or less automatically) distinguish, say, different languages or maybe even individual authors. The focus is up to you.
• (mathematical) Discuss results on the periods of LFSRs in the spirit of what is hinted at in Example 66.
• (computational) Implement a pseudorandom generator by combining several LFSRs (similar to CSS). Investigate statistical properties (for instance, do bits and bit pairs appear equally likely), periods and such.
• (mathematical) Discuss for which n there exists a primitive root modulo n.
• (basic computational) Compute and investigate the number of Fermat liars.
• (basic computational, basic mathematical) Investigate the number of twin primes and describe some of the developments (there is a mix of heuristic expectations and recent proved advances).
• (story telling) Describe the idea behind a cryptocurrency such as Bitcoin.
• (basic computational) Implement and test the Fermat and Miller-Rabin primality tests.
• (basic computational) Implement the Blum-Blum-Shub PRG and use it to securely encrypt messages.
• (mathematical) Discuss Carmichael numbers.
• (mathematical) Discuss finite fields and their classification.
• (basic computational) Discuss the weak keys in DES, and illustrate them with explicit examples.
• (story telling) Describe P versus NP.
You are also very welcome to come up with your own ideas for a project. Free style options include:
• Introduce and implement your favorite cipher (you can also use someone else's implementation). Then verify its functionality, and do some basic statistical tests.
• Introduce your favorite mathematical concept (groups, graphs, etc.), theorem or problem. Then demonstrate how Sage can be used to work with that concept, provide evidence for the theorem, or better understand the problem.
Please talk to me early if you are considering a free style option, so I can give you a green light.