ECE 720 Topic 2 - Fall 2013

ECE 720 Topic 2 - Cryptographic Computations

Instructor

Name: M. Anwar Hasan
Office location: CPH 3606A
Office hour: 2:30-3:30pm Wednesday or by appointment
Contact: email or phone: ext. 37543

Lecture times, building and room number

4:00-5:20 pm, Wednesday and Thursday; EIT 3151. (Note: The first lecture is on Wednesday, Sept 11, 2013.)

Course description

Finite fields. Computing in finite fields using standard and non-standard bases, and related high performance algorithms and architectures for cryptographic applications. Side channel analysis attack resistant computations.

Course objectives

At the end of the course you should be able to:

  • Construct a multi-dimensional finite or Galois field and represent its elements with commonly used bases such as polynomial and normal bases
  • Describe algorithms of various complexities for field arithmetic
  • Devise hardware architectures of various space and time complexities for field arithmetic Describe algorithms of various engineering trade-offs for exponentiation and elliptic curve point multiplication used in RSA and ECC
  • Have a good understanding of side channel analysis attack resistant computations

Course prerequisite

Bachelor degree in EE/CE/CS or equivalent, or instructor's permission

Text and references

  • Text: There is no required text for this course. Copies of lecture slides will be available.
  • References:
    • Hankerson, Menezes and Vanstone, Guide to Elliptic Curve Cryptography (Chapters 2, 3 and 5)
    • Menezes, van Oorschot and Vanstone, Handbook of Applied Cryptography (Chapters 2 and 14)
    • Lin and Costello, Introduction to Error Control Coding (Chapters 2 and 6)
    • McEliece, Finite Fields for Computer Scientists and Engineers (Chapters 2 and 8)
    • Selected articles from IEEE Trans. on Computers and CHES proceedings.

Course topics

Finite fields-- Introduction to finite fields and their important properties. Applications to cryptography. Prime and extension fields. Basis of representation. Conversion of bases.

Algorithms and architectures using standard representations-- Formulation of generalized finite field multiplication and optimization using field defining polynomials. Quadratic and sub-quadratic complexity multiplication algorithms. Digit level computations. Speed- ups using sub-field computations and look-up tables. Architectures for embedded and resource constrained systems. Systolic architectures. Multiplicative inversion using the almost inversion algorithm, solving equations over subfields, and using the extended Euclidean algorithm with polynomial updating up to the exact precision.

Computations using non-standard bases-- Normal basis multiplication architectures and their optimization using Gaussian type bases. Computations using redundant representations and subfields. Arithmetic algorithms using dual and triangular bases. Case study of a finite field coprocessor.

Digital signature generation-- Exponentiation based digital signature generation and its optimization using signed digits and window methods. Scalar multiplication for elliptic curve based digital signatures. Complex radix number systems and its application to scalar multiplication on anomalous binary curves. Timing and power analysis attack resistant computations.

Evaluation

The course grade will be based on assignments, a project and a final examination which will be held during the Official Examination Schedule. The breakdown is as follows:
Assignments: 20%
Project: 30%
Final exam: 50%

Requirement for auditing the course

A student taking the course for audit is required to neither write the final exam nor do a project. For successful auditing, the student however must obtain a combined score of 50% or more in the assignments.

Assignments

After two weeks of classes, one assignment will be given approximately every alternate week. There will be five assignments in total. The deadline of an assignment is one week after its first distribution. Penalties for late submission will be 5% per day.

Project

The project mark will be based a proposal, an oral presentation, the work you accomplish and a report. Project guidelines will be available later.

  • Important dates:

    Proposal due: 4:00pm, Monday, November 4, 2013
    Oral presentation: 4:00pm, Thursday, November 28, 2013
    Report due: 4:00pm Thursday, December 19, 2013

    Note: Proposal and report must be submitted both in hard-copies and as electronic pdf files via email.

  • Evaluation:

    Proposal: 15%
    Oral presentation: 15%
    Work accomplished: 40%
    Report: 30%

    Note: Penalties for late submission of your proposal and report will be 5% per day.

Academic integrity, Grievance, Discipline, Appeals and Note for students with disabilities

See http://www.uwaterloo.ca/accountability/documents/courseoutlinestmts.pdf The text for this website is listed below:

Academic Integrity: In order to maintain a culture of academic integrity, members of the University of Waterloo community are expected to promote honesty, trust, fairness, respect and responsibility. [Check www.uwaterloo.ca/academicintegrity/ for more information.]

Grievance: A student who believes that a decision affecting some aspect of his/her university life has been unfair or unreasonable may have grounds for initiating a grievance. Read Policy 70, Student Petitions and Grievances, Section 4, http://www.adm.uwaterloo.ca/infosec/Policies/policy70.htm. When in doubt please be certain to contact the department’s administrative assistant who will provide further assistance.

Discipline: A student is expected to know what constitutes academic integrity to avoid committing academic offenses and to take responsibility for his/her actions. A student who is unsure whether an action constitutes an offense, or who needs help in learning how to avoid offenses (e.g., plagiarism, cheating) or about “rules” for group work/collaboration should seek guidance from the course professor, academic advisor, or the undergraduate associate dean. For information on categories of offenses and types of penalties, students should refer to Policy 71, Student Discipline, http://www.adm.uwaterloo.ca/infosec/Policies/policy71.htm. For typical penalties check Guidelines for the Assessment of Penalties, http://www.adm.uwaterloo.ca/infosec/guidelines/penaltyguidelines.htm.

Appeals: A decision made or penalty imposed under Policy 70, Student Petitions and Grievances (other than a petition) or Policy 71, Student Discipline may be appealed if there is a ground. A student who believes he/she has a ground for an appeal should refer to Policy 72, Student Appeals, http://www.adm.uwaterloo.ca/infosec/Policies/policy72.htm.

Note for students with disabilities: The Office for Persons with Disabilities (OPD), located in Needles Hall, Room 1132, collaborates with all academic departments to arrange appropriate accommodations for students with disabilities without compromising the academic integrity of the curriculum. If you require academic accommodations to lessen the impact of your disability, please register with the OPD at the beginning of each academic term.