Encryption Project

ICMS

Page:

APPLICATIONS OF THE DISCRETE LOG PROBLEM

The Discrete Log problem (DLP)

If b and a are known real numbers and it is also known that b is some power (say, x) of a, then logarithms can be used to find x in an efficient manner. The corresponding problem in additive (i.e., abelian) groups is: given P and kP (P added to itself k times), find the integer k. This is much more difficult. There is no one-step operation like "taking logarithms" that we can use to get the solution. So we may know P and kP and yet not be able to find k in a reasonable amount of time. This is called the Discrete Log Problem for abelian groups. We could always repeatedly subtract P from kP till we got O. But if k is large, this will take us a very long time. Several important cryptosystems are based on the difficulty of solving the DLP over finite abelian groups. The solution is even tougher if the underlying group arises from an elliptic curve over a finite field.

On comparing the computer time taken by the best known algorithms for solving the DLP in a standard group (whose elements have "size" N) and the group (with elements of size n) of points of an elliptic curve over a finite field, we find that the same level of security is offered when

n » 4.9 N ^1/3 (log (N log(2)))^2/3

Some comparisions are given in the following table:

N	400	800	1200	1600	2000
n	114	156	186	210	231

Thus elliptic curve cryptosystems offer more security for less computer effort.

Diffie-Hellman key exchange

Diffie-Hellman key exchange exploits the DLP to allow two people (call them A and B) to generate a secret key for use in some cryptosystem. A large finite abelian group Z and an element G in it are public information. A and B generate random integers a and b which are known only to them. A transmits aG to B and B transmits bG to A. Now A multiplies bG by a to get a(bG). B multiplies aG by b to get the same. A and B have arrived at a secret key abG without explicitly transmitting it to each other! Any eavesdropper now knows aG, bG and G, but can neither find the value of a nor of b (because of the DLP) and so cannot find abG.

The El-Gamal Public Key cryptosystem

This system is the basis of the Pretty Good Privacy (PGP) software. It uses finite abelian groups but is particularly suited for use with elliptic curves over large finite fields. The procedure is:

Public Knowledge a point P on an elliptic curve C .

Users secret key a large integer n. User publishes nP

A wants to send B(public key bP) a message M. He

Generates a large random integer c,
Finds cP and c(bP).
Transmits the pair cP, M + c(bP)

B multiplies cP by his secret integer b to get b(cP) and subtracts that from M + c(bP) to get M.

Any eavesdropper now knows bP and cP but cannot find c (again, because of the DLP). There is no way for him to find c(bP) or M. The system is secure.

Try it out on the computer display!