CS 292F Elliptic Curve Cryptography

CS 292F Elliptic Curve Cryptography

Department of Computer Science
University of California Santa Barbara
http://koclab.cs.ucsb.edu/teaching/ecc

Announcements

  • Instructor: Professor Çetin Kaya Koç         → Koç is pronounced as "Coach"  

  • Schedule and Classroom: Tuesday and Thursday 3:00-4:50pm; Phelps 2510
  • Office Hours: Wednesday 4:00-6:00pm
  • Office: HFH 1119

  • Check the class website and Piazza page for CS292F once a day   ←
  • The grades: ..   →   The "Code" is equal to the perm number mod 997 for the regular UCSB students and the last 3 character of the perm number for the Extension Students.

Project Paper or Presentations

The participating students are expected to write a short (3-5 pages) paper or create a short (15-20 slides) presentation on a certain aspect of elliptic curve cryptography, particularly covering most recent algorithmic, security or implementation related developments. The paper or presentation is to be written in LaTeX2e. The project reports or presentations are graded as: 20% for a well written abstract, 40% for the difficulty of the subject, and 40% for the presentation. Here are some well-written samples:

2015 Fall Abstracts and Projects

Homework Assignments

There will be 4 homework assignments. Please upload an electronic copy via the Dropbox link provided. Electronic copy of your homework can be in Text or PDF. You could also scan/pdf your handwritten work; however, do not send (low-resolution or small) phone-camera images.

Weekly Course Plan

Course and project related papers are (will be) here: eccPapers

Course presentations and weekly slides are (will be) here: docx   ←

  • Week 01: Numbers, Groups, Fields
    01numbers.pdf, 02groups.pdf, 03fields.pdf
  • Week 02: Public Key Cryptography
    04primes.pdf, 05pkc.pdf, 06rsarabin.pdf, 07sqrt.pdf, 08dlog.pdf
  • Week 03: Diffie-Hellman and Discrete Logarithm
    08dlog.pdf
  • Week 04: ECC Fundamentals
    09ecc.pdf, 13eccalgs.pdf
  • Week 05: Edwards Curves
    10edwards.pdf
  • Week 06: ECC Fundamentals and GF(2^k) Arithmetic
    11ecgf2k.pdf, 12normal.pdf
  • Week 07: ECC HW and SW
    15ecchwsw.pdf
  • Week 08: Koblitz Curves
  • Week 09: Project Presentations
  • Week 10: Project Presentations

Conferences, Proceedings, Journals, & Archives

Description

Public-key cryptography was conceived in 1976 by Whitfield Diffie and Martin Hellman. The first practical realization followed in 1977 when Ron Rivest, Adi Shamir and Len Adleman proposed their now well-known RSA cryptosystem, in which security is based on the intractability of the integer factorization problem. Elliptic curve cryptography (ECC) was discovered in 1985 by Neal Koblitz and Victor Miller. Elliptic curve cryptographic schemes are public-key mechanisms that provide the same functionality as RSA schemes. However, their security is based on the hardness of a different problem, namely the elliptic curve discrete logarithm problem (ECDLP). Currently the best algorithms known to solve the ECDLP have fully exponential running time, in contrast to the subexponential-time algorithms known for the integer factorization problem. This means that a desired security level can be attained with significantly smaller keys in elliptic curve systems than is possible with their RSA counterparts. For example, it is generally accepted that a 160-bit elliptic curve key provides the same level of security as a 1024-bit RSA key. The advantages that can be gained from smaller key sizes include speed and efficient use of power, bandwidth, and storage.

This course is designed for computer science, computer engineering, electrical engineering, and mathematics students interested in understanding, designing, developing, analyzing, and validating elliptic cryptographic algorithms and protocols. The course is targeted to a diverse audience, and generally assumes no more than an undergraduate degree in computer science, electrical or computer engineering, or mathematics.

Topics

  • Numbers, Groups, and Fields: Number systems, sets, GCD, primes, CRT. Groups, rings, fields, and finite fields. Finite fields of p, 2^k and p^k elements. Representations of field elements. Polynomial, normal and optimal normal bases. Exponentiation and discrete logarithms.
  • Elliptic Curve Arithmetic: Weierstrass and Edwards equations. Group law, group order, and group structure. Isomorphism classes. Projective coordinates. Point multiplication. Koblitz curves and Frobenius map.
  • Elliptic Curve Cryptographic Protocols: The elliptic curve discrete logarithm problem. Pohlig-Hellman, Pollard's rho, index-calculus, and isomorphism attacks. Signature schemes: ECDSA and EC-KCDSA. Public-key encryption: ECIES and PSEC. Key establishment: EC-DH, ECMQV. Elliptic curve deterministic RNGs: EC-LCG, EC-Power, EC-Naor-Reingold.
  • Software and Hardware Realizations: Integer and floating-point arithmetic. Algorithms for performing addition, multiplication, and inversion. Hardware and software methods for realizing finite field operations. Montgomery multiplication in GF(p) and GF(2^k). Secure implementations against side-channel attacks.

Books

                                       

Grading

  • 4 Homework Assignments: 60 %
  • Project Paper or Presentation: 40 %

Prerequisites

This class is open to all graduate students. Undergraduate students should contact the instructor.

Academic Integrity at UCSB   ←

Dr. Çetin Kaya Koç