From: smb@research.att.com

To: “J. Michael Diehl” <mdiehl@triton.unm.edu>

Message Hash: dbb05bc0e71fdcf6a3d106ed4e54718386590d07c19a5bca25fa83edeb8d2258

Message ID: <9306052135.AA26361@toad.com>

Reply To: *N/A*

UTC Datetime: 1993-06-05 21:35:14 UTC

Raw Date: Sat, 5 Jun 93 14:35:14 PDT

```
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
```

Return to June 1993

Return to “smb@research.att.com”

1993-06-05 (Sat, 5 Jun 93 14:35:14 PDT) - Re: Dig. Cash Question. -

*smb@research.att.com*