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.