Description:
Elliptic curves is a new emerging class of public key cryptosystems that may successfully compete in the future with the current monopoly of the RSA cryptosystem. The security of most elliptic curve cryptosystems is based upon the difficulty of solving a discrete logarithm problem in a group of points on the elliptic curve. If the elliptic curve is chosen correctly, the best known algorithm for finding the discrete logarithm is of exponential difficulty. The security of RSA is based on the difficulty of factoring large integers, a problem for which quite efficient subexponential algorithms (such as Number Field Sieve) have been developed (see project CS-3). As a result, the cryptographic keys may be significantly shorter for elliptic curve cryptosystems compared to RSA, which results in faster and more compact implementations. The other advantage of using elliptic curves for constructing cryptosystems is that each user may (but does not need to) choose his/her own curve. If this is the case, reconstructing the private key of one user, does not provide any information that could be used to reconstruct the private key of another user. According to the current knowledge, choosing an appropriate elliptic curve is equivalent to calculating the number of points on the elliptic curve, and checking whether this number has a large prime divisor. Only in this case, a discrete logarithm problem in a group of points on the elliptic curve has exponential complexity. Several methods have been devised for choosing an appropriate elliptic curve. The anex to the IEEE 1363 standard lists three of them: counting number of points on a randomly chosen curve using Schoof's algorithm, constructing the curve using the Weil theorem, and constructing the curve using the method of complex multiplication. Your task is to either perform a comparative analysis of the last two methods, or to prepare a detailed specification of the Schoof's algorithm, and try to estimate its running time.
Literature:
Description:
Elliptic curves for cryptographic applications may be constructed over fields GF(p), where p is a large prime, and GF(2^m) where m is some integer. Additionally, the operations in the field GF(2^m), addition, multiplication, division, and remainder, can be defined in various ways, leading to equivalent (isomorphic) fields. Choosing these operations affects the efficiency and complexity of the hardware and software implementations of elliptic curve cryptosystems. Two ways of defining GF(2^m) given in the IEEE P1363 standard use so called polynomial and optimal normal bases. Choice of any of these bases leads to hardware implementation that is more efficient than hardware implementation of operations in GF(p). Your task is to analyze and compare architectures used to implement multiplication and inversion in the fields GF(2^m) with polynomial and optimal normal bases, and estimate the running times for these operations.
Literature: