RSA Security 5.2.2 manual Elliptic Curve Cryptography, Multiple-Party Key Agreement

Cryptography Overview

Security

The security of Diffie-Hellman key agreement relies on the difficulty of computing nth roots modulo a prime number. It takes very little time to exponentiate a number modulo a prime, but it takes a great deal of time to compute its roots. This problem in modular arithmetic is called the discrete logarithm problem. (Recall that, in the real numbers, if you can compute the logarithm of a number, you can easily compute all of its roots.) The RSA Laboratories publication, Frequently Asked Questions About Today’s Cryptography, states, “The best discrete log problems have expected running times similar to that of the best factoring algorithms.” That is, the time it takes to compute discrete logs modulo a prime of a certain length is approximately equivalent to the time it takes to factor a number of that same length. See “The RSA Algorithm” on page 51 for a discussion of factoring.

Multiple-Party Key Agreement

The previous protocol can be extended to more than two parties. For a multiple-party agreement, each individual chooses a private value, then uses the collection of public values from other parties to generate a common secret key.

Elliptic Curve Cryptography

Elliptic curves are mathematical constructs that have been studied by mathematicians for over 100 years. The application of elliptic curves to cryptosystems is more recent; in 1985, Neal Koblitz and Victor Miller independently devised a public-key system using a group of points on an elliptic curve.

The core of elliptic curve cryptosystems rests on the difficulty of a particular type of calculation. For some public-key algorithms, such as Diffie-Hellman key agreement, the security is based in part on the fact that given a modulus n, a number g, and gk mod n, it is difficult to determine k. This is called the discrete logarithm problem. Elliptic curve cryptosystems rest on a similar problem: given an elliptic curve E and two points on the curve, P and Q, such that Q = k · P for some number k, it is difficult to determine k. This is called the elliptic curve discrete logarithm problem. (See the next subsection, Elliptic Curve Parameters, for a discussion of these terms.) Many algorithms that are based on the discrete logarithm problem can be translated to analogous algorithms based on the elliptic curve discrete log problem.

Elliptic curves can be used for a variety of public-key cryptosystems. Crypto-C supports the following elliptic curve features:

•Generation of elliptic curve parameters

•Elliptic curve key pair generation

C h a p t e r 3 C r y p t o g r a p h y 6 5