CSCI3381-Cryptography

Spring, 2017


General Course Information
Course Content
Required Background
Software
Textbooks

Required Work Grading Detailed Course Schedule


General Course Information


Instructor:
Howard Straubing
Computer Science Department
251 St. Mary's South
tel.:617-552-3977
e-mail: straubin@cs.bc.edu
Office Hours MW2-4.

Teaching Assistants:

Emily Lu
e-mail: luem@bc.edu
Office Hours:
 Friday 11-12, Fulton 460
Nick Barker
e-mail:barkernc@bc.edu
Office Hours TBA


The class meets Tuesday and Thursday at 12:00-1:15 in Fulton 250.


Course Contents

When you log onto a secure web site, for example to pay a bill from your bank account, you need to be assured of certain things:
Behind the scenes, an extraordinary series of computations takes place to ensure that these security requirements are met. This course is about how all that works.

The practice of disguising the content of a message so that it can be read only by the intended recipient dates back to antiquity.  Scientific treatises on cryptography were written as early as the 9th century AD, and there has always been a strong interest in its military and diplomatic applications. The emergence of the computer revolutionized cryptography:  On one hand, the ability of computers to rapidly search a very large space of possible keys required the creation of more secure cryptographic systems. On the other hand, as  electronic fund transfers, e-mail, databases of confidential personal information and the Web came into use, cryptography was transformed from a tool for spies, diplomats and generals to something used by the public at large. Today we are all consumers of cryptography on a daily basis.

Cryptography is also very much in the news, and is at the center of continuing controversies over policy around surveillance, privacy, and law enforcement: You have surely seen news stories about the security of electronic voting systems, the digital currency Bitcoin, the dramatic revelations leaked by NSA analyst Edward Snowden in 2013 concerning government surveillance, and the struggle between the FBI and the Apple Corporation over encrypted data on an iPhone belonging to the perpetrators of San Bernardino terrorist attack in 2015.

The science behind all this involves some sophisticated ideas from both mathematics and computer science. We will begin the course with a look at some classical cryptographic systems that were in use before the advent of computers, then study modern stream ciphers and block ciphers, both the general principles behind their construction and use, and some details about widely-used systems : the Data Encryption Standard (DES) and Advanced Encryption Standard (AES).  These are  symmetric  systems in which the parties share some secret information (a key) used for both encryption and decryption.  Cryptography was profoundly changed by the invention, in the late 1970's, of asymmetric, or public-key cryptosystems, in which the two parties do not need to share a secret in order to communicate securely.  We will study public-key cryptosystems like RSA and Diffie-Hellman, cryptographic hash functions, and schemes for digital signatures.  We'll finish the course looking at some real-world cryptographic protocols (for example, SSL), proposals for electronic elections and digital cash (e.g., Bitcoin), and some different ideas for the construction of cryptosystems (quantum cryptography). A detailed list of topics (which will be refined considerably as the semester progresses) appears at the bottom of this web page.


 


Required Background

CSCI3381 is intended for upper-division Computer Science majors, and for upper-division Mathematics majors with the appropriate programming background.  This is very much an applied cryptography course, in the sense that we will (mostly) concentrate on systems in actual use, how they are deployed, and what their vulnerabilities are. But there is still a strong theoretical component:  you need to understand  the mathematics on which real cryptographic systems are based, as well as the formal definitions of security requirements. Thus there is a rather stringent prerequisite background in both computer science and mathematics.

In mathematics, we will use standard abstract notation and terminology concerning sets, functions and relations;  some basic combinatorics and probability; and some basic number theory; and you will need to be able to follow, and in some instances write, a proof.  The probability is 'baby' probability, but the number theory gets more involved.  I intend to introduce what we need from both these areas from scratch, but it will go fast, and it is really helpful to have seen it before.

What this means is that CSCI2243:Logic and Computation for CS majors, or MATH2216 :Introduction to Abstract Mathematics for Math majors, is essential.  For the CS majors, CSCI2244: Randomness and Computation is helpful, likewise in Mathematics,  MATH4426: Probability and MATH4430: Number Theory, but certainly not essential.

In computer science, you need to be a fairly proficient programmer. If you took CSCI1101 (Computer Science 1) and performed well in it, then you should be okay.  If you took Computer Science 1 in some language other than Python, then you will have to start learning Python:  I have provided some links to tutorials below.  Homework assignment 1 (not 0!)  should give you a good sense of the level of programming skills that are expected.  You should also be familiar with some very basic computer science concepts like binary and hexadecimal notation for integers---if you haven't seen these, you can pick them up very quickly.

Software

We will use the programming language Python in this course.  I made this choice because
The current version of Python is Python 3.something, but we will use Python 2.7, which is still in wide circulation, and will remain so for at least another four years.  The two languages are NOT compatible, so Python 2.7 code will not run correctly under Python 3, or vice-versa, without significant modification.


Textbooks

  There is no required textbook for the course.  I will post notes for every lecture, or every couple of lectures, usually the day of or the day after the lecture itself.  (I like to wait until after the class to take account of issues that arise during class time.)

I am recommending, but not requiring, An Introduction to Modern Cryptography by Katz and Lindell. If you are interested in having something to read, there will be copies of the 2nd edition at the bookstore, but you can probably get yourself a copy of the first edition online for cheaper.  I very much like the approach of this book, but some parts of it make for rather difficult reading, and I will order the topics somewhat differently.

There is a very good series of lectures, available on YouTube, from an online course given by Dan Boneh of Stanford University.  This is worth checking out.

A draft of A Graduate Course in Applied Cryptography, by Boneh and Shoup, is available for free on the Web. As the title indicates, the general level of the textbook is more advanced than our course, but you will still find much of it very useful.

Required Work

Problem Sets

There will be approximately seven homework assignments during the semester.  Assignments will involve both paper-and-pencil problems, and writing Python code. Assignments will be posted on this web site, along with lecture notes and additional reading.  I will make an effort to post solutions to assignments in a timely fashion.  For this reason (and others) late homework assignments will not be accepted.

You will submit your assignments through Canvas.   Assignments must be typed, either using the LaTeX typesetting system (harder to learn, but well worth the effort) or the Equation Editor in Microsoft Word (trivial to learn).  I prefer that you convert your Word documents to PDF format before submitting. In .py files containing Python code, the name of the file, the names of your main functions as well as the number and order of the arguments to these functions, will be rigidly prescribed in order to facilitate grading.  Precise instructions will be given with each assignment.

Quizzes

This semester, I will experiment with frequent brief quizzes, given at the beginning of the class period, perhaps one every week.  These will be very simple quizzes, usually just a single question.  This is a ploy to force you to keep up with the material and attend class.

Exams

There will two in-class midterms
. There is no final exam.

Projects

There will be a final project due at the end of the semester. Throughout the semester, I will post descriptions of suggested project topics.  In most cases, each project will  involve both programming and carefully-explained analysis.   The projects are meant to be worked on in groups of 2 or 3.

Academic Integrity

While I encourage you to discuss homework problems both among yourselves and with me, when it comes  to finally sitting down and preparing the completed assignment, you are required to work alone.  Thus it is acceptable to learn from another student the general idea for writing program code to perform a particular task, or the technique for solving a mathematical problem, but unacceptable to  take an extended piece of code written by another person and incorporate it into your submitted assignment as your own work.   If you have any uncertainty about the application of this policy, please check with me.

Failure to comply with these guidelines will be considered a violation of academic integrity. Please make sure that you are familiar with the University policies on academic integrity, which are posted at  http://www.bc.edu/content/bc/offices/stserv/academic/integrity.html


Services for Students with Disabilities

If you are a student with a documented disability seeking reasonable accommodations in this course, please contact Kathy Duggan, (617) 552-8093, dugganka@bc.edu, at the Connors Family Learning Center regarding learning disabilities and ADHD, or Paulette Durrett, (617) 552-3470, paulette.durrett@bc.edu, in the Disability Services Office regarding all other types of disabilities, including temporary disabilities. Advance notice and appropriate documentation are required for accommodations.

Eyes Front!

My colleague Bob Muller calls this policy the 'laptop-free classroom'.

A successful class requires your attention, engagement, and participation.  You need to be prepared to ask and answer questions during the lectures, and to attend to the questions and answers of your fellow students and of the instructor.  That screen open to your e-mail or Facebook page distracts not only you, but the students sitting behind you. For this reason, open laptops are not permitted in the classroom, unless they are part of some planned activity for which your computer is required.

You say you're taking notes on that laptop instead of shopping on Amazon? You should be aware that (a) it is very difficult to take notes for this class on a computer, given the large number of mathematical symbols, formulas and diagrams that we use; and (b) taking notes by hand is better for you.  It is acceptable to take notes on a tablet computer with a stylus.

And that goes double for your phone.



Grading

To be eligible for  a passing grade in this course, you must complete at least 60% of the assignments, as well as the project, in a satisfactory manner. Your grade will then be computed from your performance on assignments, quizzes, midterms and projects. and final exam.  The assignments will account for about 30% of the grade, the project for 30%, and the midterms and quizzes for about 40%.  (These ratios are subject to minor adjustments, hence all the "abouts".)


Detailed Course Schedule


Date
Topic
Handouts and Readings

Problem Sets and Projects

Week 1: January 17-19
What cryptography does.

The setting of symmetric encryption.

Classical cryptosystems.
Alice and Bob

conversions.py (Python  functions for converting between different representations of byte sequences.)

caesar.py (The Caesar cipher, together with a statistical cryptanalysis.)

Cryptanalysis of Vigenere cipher (Python notebook).

Lecture Notes 1

Lecture Notes 2

A tutorial for learning Python (if your programming experience is in another language).

Another Python tutorial
Assignment 0:  due January 19 at midnight.

Assignment 1: due January 27 at midnight.

Ciphertexts for Assignment 1:
ciphertext1.txt
ciphertext2.txt
MSWordXOR1.doc
MSWordXOR2.doc
MSWordXOR6.doc
MSWordXOR8.doc
MSWordXOR9.doc

Week 2: January 24-26
Perfect secrecy and the one-time pad.

Random number generators and stream ciphers.
Lecture Notes 3

Lecture Notes 4

An implementation of the RC4 stream cipher.

A Python implementation of the random number generator in Java.
Assignment 2, due Wednesday, February 9 at 11:59PM.

Base64-encoded ciphertexts for the assignment.
HW2_6a_ciphertext.txt
HW2_6b_ciphertext.txt
HW2_7_ciphertext.txt

Grading script for assignment 2.  Make sure your .py file is placed inside a zipped folder, then run do_it(),
Week 3: January 31-February 2
Stream ciphers continued.

Block ciphers from the high level: modes of operation.

Lecture Notes 5

Code for block cipher encryption of bit-mapped images (requires pycrypto or pycryptodome).

The test image used in the demo

The test image encrypted with DES in ECB mode.
Assignment 3, due February 21.

Code for querying the website with the dictionary challenge.
Weeks 4-5 February 7-February 16
Block ciphers from the low level: internal design.

Theoretical foundations:  Is cryptography possible? OWF, PRG, PRF and PRP
The printed text from Quiz 3.

Review questions for midterm

Solutions to 2012 midterm

Solutions to 2014 midterm

Week 6: February 21-February 23 First exam

Number theory.

Euclid's algorithm and modular exponentiation by repeated squaring, along with some other useful number theoretic functions(Python code)
Assignment 4, due March 14.

Big numbers for Assignment 4.
Week 7: February 28-March 2 More number theory. Public-key cryptosystems. (RSA and Diffie-Hellman.)


  Spring Break


Week 8: March 14-March 16
Public-key cryptosystems continued.
The classic papers on public-key cryptography:

New Directions in Cryptography, by Diffie and Hellman

A Method for Obtaining Digital Signatures and Public-key Cryptography, by Rivest, Shamir, and Adleman
Assignment 5, due March 27.

Ciphertexts and parameters for Assignment 5.
Week 9: March 21-March 23
Public-key cryptosystems continued.


Week 10: March 28-March 30 Cryptographic hash functions and message authentication codes.

Assignment 6, due April 5.
Week 11: April 4-April 6 Digital signatures.

Project Information
Week 12: April 11 (April 13 is Easter break)
Second exam.


Week 13: April 18-April 20
Applications: SSL, Bitcoin.
SSL demo (done a few years ago---the Target website I used has changed from using RSA for key-sharing to Elliptic Curve cryptography and the version I gave in class used a different site ).

Inspiration for the SSL demo came from this blog post.

The original description of Bitcoin, by 'Satoshi Nakamoto'

Week 14: April 25-April 27
Big ideas: fully homomorphic encryption, quantum computing, quantum cryptography.


Week 15: May 2-May 4
Project presentations.