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, 2013Note: 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.