General Course Information

Instructor:
Howard Straubing
Computer Science Department
571 Maloney Hall
tel.:617-552-3977
e-mail: straubin@cs.bc.edu
Office Hours: Monday, Wednesday 2:30-4:30.

The class will meet Tuesday and Thursday at noon in Fulton 210. I will be absent on Tuesday, October 28 and Thursday, October 30.  A midterm will be scheduled for one of those two days, and class canceled on the other.

---

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:

• Is your communication private? An eavesdropper should not be able to determine what information you and the bank are exchanging.
• Does the website you are communicating with really belong to the bank?  No one should be able to successfully impersonate the bank.
• Are you you? No one should be able to impersonate you and gain access to your account information, or make payments from your account.
• Are the messages you and the bank receive from each other the same ones that were sent?  No one should be able to alter the messages in transit without this being detected.

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. As the scenario above indicates, today we are all consumers of cryptography on a daily basis.

Cryptography is also very much in the news. You may have run across news stories about the security of electronic voting systems, or about the digital currency Bitcoin. And the recent dramatic revelations by NSA analyst Edward Snowden concerning government surveillance moved stories about cryptographic protection of data to the front pages.

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 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, cryptographic hash functions, schemes for digital signatures, and zero-knowledge identification schemes.  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

This course is typically taken by both Computer Science and Mathematics majors, and I have tried to design it so that it is accessible to students with a variety of backgrounds.  What this means in principle is that the course has no prerequisites, and can be taken by anyone with decent mathematical skills.  What it really means in practice is this:

• The ideal background for a Computer Science major taking CSCI3381:  CS243 (Logic and Computation), CS244 (Randomness and Computation), CS101 (Computer Science 1).
• The ideal  background for a Mathematics major taking CSCI3381: MT216 (Introduction to Abstract Mathematics) and some exposure to computer programming.  MT426 (Probability) and MT430 (Number Theory) are relevant, but certainly not essential.

Don't be discouraged if your background doesn't match these ideals, but come talk to me if you have any concerns.  (It will take me some time to get used to our new course numbering system at Boston College; I suppose MT430 is now MATH4430...)

---

Software

We will use the programming language Python in this course.  I made this choice because

• It's what we teach in CS101, so most of the Computer Science students have seen it.
• Compared to other programming languages, it's relatively easy to learn, so students whose only previous programming background is in some other language should be able to pick up enough Python quickly.
  
• Modern cryptographic methods depend critically on exact arithmetic performed with integers that are hundreds of decimal digits long. Python has built-in support for arithmetic with integers this large.
• It's free.

On the other hand, the code examples that come with the textbook are all in other languages (but I will provide many examples on this website).  A more serious problem is that Python is very slow in comparison to languages like C and Java, which places some practical limits on what you can do in programming assignments.

---

Textbooks

The course textbook is Introduction to Cryptography, with Coding Theory, by Wade Trappe and Lawrence Washington.  We will ignore the coding theory part, but cover material (not all of it!) from Chapters 1, 2, 4-14, and 19, with frequent trips to Chapter 3 for mathematical reference.  I very much like the writing style in the book, as well as the selection of topics.  My one quibble, apart from the price, is my feeling that the outlook of the book is not as modern as I would like, particularly in the more computer science-y aspects.  In particular, the approach to presenting algorithms and discussing their running time is a little too informal for my tastes, and there is little or nothing about the very important connections between computational complexity theory and the security of cryptographic algorithms. I will try to close these gaps in the lectures and with additional readings posted on this site.

My own bedtime reading is another textbook:  An Introduction to Modern Cryptography by Katz and Lindell. I did not think it appropriate as a textbook for this course, but I have found it a great source of information and insights.

---

Required Work

Problem Sets

There will be approximately nine homework assignments during the semester.  Assignments will involve both paper-and-pencil, and writing some Python code---initially just a record of calculations. 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, which is the new replacement for the Blackboard Vista system. I am also experimenting with a Discussion page on Canvas, in which I invite you to submit your questions and comments about the course.

Exams

There will an in-class midterm exam, on either Tuesday, October 28, or Thursday, October 30.

Projects

During the semester, I will post descriptions of more substantial optional project assignments.  These will involve both programming and carefully-explained analysis.   Each one is the equivalent in effort to 2-3 weekly problem sets.  You may submit these any time during the semester for extra credit, or to substitute for several problem assignments or completion of the take-home final.  In some instances, I will allow you to work on these in pairs, but you need to discuss this with me first.

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.

 In the case of a take-home exam, there is to be no discussion of the exam among the students during the period from the distribution of the exam until they have all been submitted. 

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.

---

---

Grading

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

---

Detailed Course Schedule

Date	Topic	Handouts and Readings	Problem Sets and Projects
September 2	Basic terminology surrounding symmetric cryptosystems. Classical Cryptosystems. Demonstration of Python code.	Alice and Bob Kerckhoffs' Principle Python code for Caesar Cipher Lecture 1:  What cryptography does; symmetric encryption	Assignment 0--Install the software
September 9	Classical Cryptosystems,	Lecture 2:  Classical cryptosystems Python notebook illustrating cryptanalysis of Vigenere cipher. Python code from the Vigenere notebook. Python code for encryption and decryption with autokey cipher (for use in Assignment 1). Extract from 'The Gold Bug', by Edgar Allen Poe, describing cryptanalysis of a monoalphabetic substitution cipher.	Assignment 1, due September 12. File containing the ciphertexts for Assignment 1. Solutions Project Topic: Automated Cryptanalysis of Monoalphabetic Substitution Cipher
September 16	One-time pad, Stream Ciphers.	Lecture 3: One-time pad, perfect secrecy, and less-than-perfect secrecy Lecture 4: Binary encoding; stream ciphers Python code for converting between different representations of binary data. Python notebook illustrating these routines.	Assignment 2, due September 24 Texts accompanying Assignment 2 Solutions A Python implementation of the PRNG in Java. The LFSR for the last problem. Project Topic:  Cryptanalysis of Stream Ciphers
September 18	Modern Block Ciphers: DES, AES, modes of operation.	Lecture 5: Block Ciphers Python implementation of baby block cipher. Demo of ECB and CBC encryption of a bitmapped image.	Assignment 3, due October 3. Solutions to the written problems Solutions to the computer problems Ciphertexts accompanying Assignment 3. ECB, CBC and CTR modes for baby block cipher. Project Topic:  Padding Oracle Attack on CBC mode. Project Topic: Linear Cryptanalysis of Baby Block Cipher
September 30	Basic number theory	Lecture 6: Number Theory Python implementation of Euclid's algorithm and Miller-Rabin Primality Test	Assignment 4, due Ocober 15. Solutions to written problems Solutions to computer problems Modulus-ciphertext pairs for the RSA Problem In-class exercise on RSA. Project Topic: AKS Algorithm; Efficient, Deterministic Primality Testing
October 7	Public-key cryptosystems.  RSA.	Two classic papers from the origins of Public-key Cryptography: Diffie and Hellman, 'New Directions in Cryptography' Rivest, Shamir and Adelman, 'A Method for Obtaining Digital Signatures and Public-key Cryptography' (and the first appearance of Alice and Bob in the scientific literature). Lecture 7: Public Key Cryptography and RSA Recent research on weak RSA keys found on the Internet.  Easy reading and a scandalous result!	Assignment 5, due October 24 Data for Assignment 5 Solutions to the written problems Solutions to the computer problems Project Topic:  Bleichenbacher Padding Oracle Attack on RSA
October 16	Public-key cryptosystems continued. Primitive Elements, Discrete Logs, and Diffie-Hellman key agreement.	Lecture 8:  Discrete Logs, Diffie-Hellman, and ElGamal Public-key encryption.	Assignment 6, due Tuesday, November 11 The data for Assignment 6 Solutions
October 30	Midterm		The midterm from 2012 (note:  this was a MWF class, so the students had only 50 minutes to complete it.) Solutions to the 2012 test.  (Don't look at these until you've tried to work the problems.) This year's midterm with solutions.
November 6	Cryptographic hash functions and message authentication codes.	Lecture 9: Hash Functions and Message Authentication Article on password cracking	Assignment 7: Due November 21 Solutions: code, discussion
November 13	Digital Signatures	Lecture 10: Digital Signatures
November 18	Applications: TLS--secure internet connections Bitcoin--digital cash Zero-knowledge protocols	Lecture 11: Demo of the start of a secure Web session. 'MD5 considered harmful today'--Description of how collisions in the MD5 hash function were used to create a forged server certificate and thus launch a man-in-the-middle attack	Assignment 8: Due December 11 My 'certificate' (ASCII text file) Public-key parameters of the signing authority, and the signature on my certificate (ASCII text file--the values are given in decimal) Code containing both the good and bad signature verification algorithms.
December 2	Quantum Cryptography and Quantum Computing
Take-home final exam			Parameters for the final exam problems