Applications of Elliptic Curves in Public Key Cryptography
Basque Center for Applied Mathematics and Universidad del Pais Vasco / Euskal Herriko Unibertsitatea, Bilbao, May 2011
The most popular public key
cryptosystems are based on the problem of factorization of large
integers and discrete logarithm problem in finite groups, in
particular in the multiplicative group of finite field and the
group of points on elliptic curve over finite field. Elliptic curves
are of special interest since they at present alow much shorter keys,
for the same level of security, compared with cryptosystems based
on factorization or discrete logarithm problem in finite fields.
In this course we will briefly mentioned basic properties of
elliptic curves over the rationals, and then concentrate on important algorithms
for elliptic curves over finite fields. We will discuss efficient implementation
of point addition and multiplication (in different coordinates),
with special emphasis on fields of characteristic 2, which are important for applications in cryptography.
Algorithms for point counting and elliptic curve discrete logarithm problem will be described.
We intend to show how to use programs and program packages specialized for work with elliptic curves.
Factorization and primality testing and proving are very important topics
for security of public key cryptosystems. Namely, the starting point in the construction
of almost all public key cryptosystems is the choice of one or more large (secret or public) prime numbers.
We will describe algorithms for factorization and primality proving which use elliptic curves.
Public Key Cryptography
Elliptic curves over the rationals
Elliptic curves over finite fields
Implementation of operations
Algorithms for determining the group order
Elliptic Curve Cryptosystems
Comparing elliptic curve with other types of cryptography