Discrete logs 1

[Hal Finney <hal@rain.org>]

"Even adders can multiply using log tables..."

PGP is moving to discrete log based cryptography.  It will still
support RSA, but people will be encouraged to generate discrete log
keys.  It will use RSA to encrypt to people with RSA keys, and
discrete log crypto to encrypt to people with discrete log keys.

Many discrete log cryptosystems will be patent free after next year.
It may be that they will become more popular over the next few years
for that reason.  RSA has several more years before its patents
expire.

Most people are not as familiar with the math behind discrete logs as
they are with RSA.  The general idea of the difficulty of factoring is
pretty easy to understand.  It's much easier to multiply two large
primes together than to figure out what the primes were just by
looking at the result.  Discrete logs require a little more
explanation.

First I am going to write a little bit about the lore of logarithms.
I think today a lot of people don't know what they are.  When I was a
boy, in the 1960's, computers and even calculators were not widely
available.  Yet engineers in many fields needed to perform
calculations.  Reaction rates, material strengths, friction, current
flow, all such calculations require multiplication and division of
numbers with several significant digits.  The choices were basically
to multiply it out the long way, which was slow, error-prone, and
wasteful because it generates twice as many digits as you need; use a
slide rule, which usually only gets you two or three digits of
accuracy; or to use log tables, which could get you four or five, or
sometimes even more, accurate digits.

The logarithm of a number is the power that you have to raise some
specified base (usually 10 for these purposes) to in order to get that
number.  The logarithm of 100 base 10 is 2 because 10**2 = 100.  The
log of 1000 is 3.  For numbers not powers of 10, the logarithm has
fractional parts.  The logarithm of 20 is about 1.3, for example.  To
multiply two numbers, you find their logs and add them, and then turn
the result back into a number.  To divide, subtract the logs.  So most
of the work is just in looking up what the logs are using published
tables.

Actually we do use logs in a crude form in much of cryptography.  Any
time you say that the product of two 512 bit numbers is 1024 bits what
you mean is that the log base two of the smaller numbers is about 512,
and so the log base two of their product is 512+512 or 1024.

By the time I was in high school calculators were becoming fairly
widespread, but we still learned how to use log tables to do
multiplication and division.  Whole books were published containing
nothing but tables of the logarithms of numbers.  You can still find
these sometimes in used book stores.  There were lots of tricks to
using these tables which we had to learn.  Logarithms of numbers less
than 1 are negative, but the trick was to treat them as the sum of a
positive fractional part and a negative integer, so for example the
log of .2 was treated as +.3 - 1.  This made it easier to look up the
values.  And there were special sub-tables within the tables to help
with interpolating, looking up log values between the entries in the
table.  Using these you could get more accuracy in your answers.  All
this was part of the craft of working engineers and scientists of the
time.

It's hard for people today, raised on throwaway and even virtual
calculators, to understand the sense of power that came from using
logs for calculations.  Until we learned these advanced techniques the
only accurate alternatives were the terribly tedious hand methods.
Being able to get results by adding up a few numbers from a book was
an amazing improvement.

The discrete logs used in crypto have very different mathematical
properties than regular logarithms, but I thought this bit of history
would spark some memories in old-timers and give a new perspective for
younger people.

Hal