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:
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:
- 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. 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
- It's what we teach in CSCI1101, 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.
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.
|
|
|
