Course Overview
This course covers the main concepts and principles of Cryptography with the main emphasis on Public Key Cryptography. It begins with the review of integers and a thorough coverage of Group Theory fundamentals followed by the RSA and ElGamal ciphers. Oblivious Transfer Protocols, Zero Knowledge Proofs, Peseudorandom Numbers and Random Number Generators along with various factorization attacks will also be covered. Key management issues, cryptosecurity, authentication procedures and confidentiality is discussed. Hash algorithms are covered. There will be programming assignments to code the Euclidean Algorithm, the Fast Exponentiation Algorithm, the Primitive Root Search Algorithm, the Baby-step Giant-step Algorithm, the Index Calculus Algorithm, the Miller- Rabin Test, the Noar-Reingold Random Number Generator, the Blum-Blum-Shub Random Number Generator and the Pollard's p-1 method.

Prerequisites
MET CS 248, Discrete Mathematics and CS 566, Analysis of Algorithms

Learning Objectives
By the end of this course, the student will learn:
1. Several symmetric ciphers, including DES and triple DES
2. Asymmetric ciphers, the RSA and ElGamal as well as Diffie-Helman key exchange protocol
3. Key management, cryptosecurity, authentication and confidentiality
4. Algorithms to compute the Discrete Logarithm in cyclic groups, the Baby-step Giant-step Algorithm and the Index Calculus Algorithm.
5. SHA-1, MD5 and HMAC hash algorithms
6. Oblivious transfer protocols
7. Various random number generators
8. Probabilistic algorithms to check the primality of numbers
9. Factorization attacks: Pollard'sRho Method, Pollard's p-1 Method, Dixon Algorithm, Non-Sieving Quadratic Sieve


Methods of Instruction
This a lecture based course with several programming assignments
. Lectures that are typically used for presenting new material; a variety of teaching approaches are used in the lectures, including traditional problem solving on the blackboard, PowerPoint slide presentations, video, interactive learning with Personal Response Systems;
. Discussions of exercises, homework and reviews for exam and projects

Evaluation and Grading
Lecture material should be reviewed before the next class since any questions on old material will be addressed only at the beginning of class. The reading assignments in the textbook should be done before the material is covered in lecture, and then reviewed afterwards. All assignments must be legible, well formatted, on time and complete.
Homework assignments will be made in class and will be due the following class.

There will be two exams. If any grading criteria event will be missed it will be the responsibility of the student to arrange with the professor a mutually agreeable schedule for completion of work.

Grades will be based on:
· Class participation and homework 30%
· Midterm 35%
· Final Exam 35%


Academic Honesty
The course is governed by the Academic Conduct Committee policies regarding plagiarism (any attempt to represent the work of another person as one's own). This includes copying (even with modifications) of a program or segment of code. You can discuss general ideas with other people, but the work you submit must be your own. Collaboration is not permitted.

Instructor Information
Instructor: Dr. Anatoly Temkin
Assistant Professor,
Graduate Student Academic Advisor
Computer Science Department, Metropolitan College,
Boston University
808 Commonwealth Ave, Room 250,
Boston, MA 02215
Office: 617-353-2566
Home: 617-277-0494
Email: mailto:temkin@bu.edu

Lab
MET College operates four pc laboratories as a resource for our students and faculty. The laboratories include 64 PC's running Windows 2000, Linux or UNIX. Each lab has a LaserJet networked printer, scanner and LCD projector. The computer labs hours are:

Fall and Spring Semester: Daily: 10:00am to 11:00pm
Summer Term: Mon-Thu: 4:00 to 10:00pm, Fri-Sun: 12:00 to 6:00pm

Labs are closed during all holidays, intersession and spring break. Please note that lab rooms get reserved for classes during certain hours.

View lab reservation calendar.

All labs have the following software: Adobe Acrobat 5.0, Photoshop 5.0, MS Office2000 Pro, IE 6.0, WS-FTP, McAfee VirusScan.

Lab 1 (Room 264)

13 Pentium 1,6GHz, 512MB RAM PCs

SW: VisualStudio.NET, Oracle 9i, Erwin 4.0, SPSS v.11

Lab 2 (Room 265)

Telecom lab has 2 UNIX, 10 LINUX, 7 Windows2000 machines.
v Lab 3 (Room 266)

17 Pentium 933MHz, 512MB RAM PCs

SW: Oracle9i, Front Page 2000, Project2002, Macromedia StudioMX.

Lab 4 (Room 267)
v 17 Pentium 1.7GHz, 512MB RAM PCs

SW: FrontPage2000, Project2002, SAS, Oracle 9i, Macromedia StudioMX, Micros Fidelio

Homework

• Assignment 1
  p.111, # 7,8,9,11,14,16
  
• Assignment 2
  p.118, # 1,2,3,4,5,6
  
• Assignment 3
  p.121, # 1,8,9
  
• Assignment 4
  p.123, # 1 to 10; p.126, # 1
  
• Assignment 5
  p.135, #1,2,3,4,9,10,14,15
  
• Assignment 6
  Write a C++ or Java code for the Euclidean Algorithm
  
• Assignment 7
  Write a C++ or Java code that will find a couple of integers, x and y, for given integers m and n, such that xm +yn will yield the smallest positive number.
  
• Assignment 8
  p.267, #1,3,4,5,6
  
• Assignment 9
  p.268, #3,4,5,6,7
  
• Assignment 10
  p.271, #2,3 vp.275, #1,2,10; 12.5.01, 12.5.06
  
• Assignment 11
  Write a C++ or Java code for the Exponentiation Algorithm
  
• Assignment 12
  Write a C++ or Java code for a Primitive Root Search Algorithm
  
• Assignment 13
  Write a C++ or Java code for a Baby-step Giant-step Algorithm
  
• Assignment 14
  Have an example of the Diffie-Hellman Key Exchange Protocol, assuming it takes place in Z p , where p = 9511
  
• Assignment 15
  10.2.02, 10.2.03, 10.2.06,10.2.08
• Assignment 16
  13.1.01, 13.2.02, 13.2.03, 13.3.01, 13.3.07, 13.8.01, 12.6.01, 12.6.07, 12.6.03, 12.7.01, 12.7.02, 12.7.03 and an additional exercise: Solve
  
• Assignment 17
  Have an example of the Oblivious Transfer Protocol (factorization based), where p = 31 and q = 103 Have an example of the Oblivious Transfer Protocol (discrete log based), where p = 103. 15.5.01, 15.5.03, 15.5.05, 15.5.06, 15.5.09, 15.5.10, 15.5.14. Also, evaluate a) ( 46/111 ), b)( 37/112 ) , c) ( 113/2462 ) 16.2.01, 16.6.01, 16.6.02
  
• Assignment 18
  Write a C++ or Java code for the Miller- Rabin Test P. 335, #21.3.02, 21.3.03, 21.3.04;
  P. 336, # 21.4.01, 21.4.03
  
• Assignment 19
  Write a C++ or Java code for the Noar-Reingold Random Number Generator Write a C++ or Java code for the Blum-Blum-Shub Random Number Generator
  
• Assignment 20
  24.1.01, 24.1.02, 24.1.03
  24.2.02, 24.2.03
  Write a C++ or Java code for the Pollard's p-1 method

References
Required Text Paul Garrett: Making, Breaking Codes: An Introduction to Cryptology
Prentice Hall, ISBN#:0-13-030369-0

 

Schedule

Lecture 1

Lecture 2 Lecture 3 Lecture 4> Lecture 5 Lecture 6 Lecture 7 Lecture 8 Lecture 9 Lecture 10 Lecture 11 Lecture 12 Lecture 13 Lecture 14 Lecture 15
Final Exam