From: smb@research.att.com
Date: Sat, 5 Jun 93 14:35:14 PDT
To: "J. Michael Diehl" <mdiehl@triton.unm.edu>
Subject: Re: Dig. Cash Question.
Message-ID: <9306052135.AA26361@toad.com>
MIME-Version: 1.0
Content-Type: text/plain


	I'm reading the paper that was announced on this list about
	Digital Cash last week.  It was writen by Stefan Brands.  I
	think I have a strong Math background, but I don't know what is
	meant by a "descrete log" in a group G.  I understand what a
	group is.  I just don't know what properties an element, a,
	would have if it were the log sub p of e.  Can someone help
	me.  Otherwise, this is a very interesting article.  Thanx in
	advance.

You might want to fix your mailer; according to the strict letter of
RFC822, human-readable names shouldn't contain periods unless quoted....

Anyway -- suppose that in some group, you know that a^n=b, where a
and b are members of the group, and n is an integer.  a^n indicates
the group operation iterated n times.  The discrete log problem is
recovering n, given ``a'' and a^n=b.

In some groups, this is a very hard problem.  The group most commonly
used in cryptography is the field GF(p), i.e., the field of integers
modulo p, where p is some large number, preferably a prime, and ``a''
is a ``primitive root'' of the field.  The problem is thus to find
n, given ``a'' and a^n modulo p.  Other instances of discrete log
are useful as well; NeXT, for example, uses the same basic equation
in a field over some family of elliptic curves.  Their much-ballyhooed
invention was to find a set of such curves for which the exponentiation
operation can be performed very efficiently.

Oddly enough, solving discrete log in GF(p) seems to be vaguely akin
to factoring.  p doesn't have to be a prime, but you can use smaller
numbers if it is.  Early attempts used 2^n, since that makes the
modulus operation trivial, but if you do that, you need such a large
n that it doesn't pay.  For p a prime, 512 bits is probably secure now,
though possibly not against NSA.  1024 bits is likely to be secure
forever, barring major theoretical breakthroughs.


		--Steve Bellovin