Filter
Top Products
Chapter 3 Cryptography 65
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 g
k
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