From: ghsvax!hal@uunet.UU.NET (Hal Finney)
Date: Fri, 4 Dec 92 09:55:49 PST
To: cypherpunks@toad.com
Subject: PGP questions
Message-ID: <9212041752.AA17033@nano.noname>
MIME-Version: 1.0
Content-Type: text/plain


It's probably good to discuss how PGP works here, for educational
purposes, but I would expect people to get the source code if they
really are interested.  I can give some pointers here to answers to
some of the questions people have asked.

Steve Witham asks several questions.  I think the crypto glossary
which Tim posted a couple of weeks ago tells how RSA works, so I won't
reiterate that here.  Steve, if you didn't get it, maybe Tim could
send it to you.

PGP's signature algorithm creates an MD5 message digest of the
message, then signs that digest by raising it to the secret exponent
"d", mod "n".  MD5 is a public-domain message digest algorithm created
by RSA Data Security, Inc, which breaks messages into blocks of 64
bytes as input and produces a 16-byte (128-bit) digest.  PGP then pads
this 16-byte number to be about the size of n, and does the
exponentiation.

PGP does not do its decryption/signature exponentiation by actually
raising the number to the power of d mod n, but by doing a
mathematically equivalent operation involving two exponentiations, one
mod p and one mod q.  Since p and q are half the length of n, and
exponentiation takes roughly the third power of the number of bits in
the modulus, this reduces the amount of time by a factor of 4.

The random number generator has several different modes, and I can
only suggest looking at random.c.

The data-compression algorithm is not really relevant but is based on
zip.  The binary-ascii translator is also not important but is a
variant on the PEM standard.

Steve asks a lot of questions about the speed of different versions.
Maybe asking on alt.security.pgp would produce some representative
values.  I'm not sure whether anyone has a database with all these
numbers.

I understand that PGP 2.1 may have a faster version of the Upton
modmult.  Preliminary timings suggest that it's still slightly slower
than the Merritt modmult on the Sparc, but if Merritt really is
unreliable (I haven't heard about this) then switching to Upton will
not involve much of a penalty.  PGP is very fast on Sparcs anyway and
I don't think making it 10% slower would matter.

Profiling indicates that yes, during the RSA encryption phase, most of
the time is spent in modmult.  An interpreter could be built to do a
modular exponentiation using a C implementation of modmult and it
would be about as fast.  However, that still leaves the generation of
the random session key, padding it with random numbers so that it is
suitable for RSA operations, converting the RSA-encrypted session key
into a format suitable for writing to a file, doing the IDEA
encryption, wrapping this all up with control information so that it
can be decrypted, looking up key information from a key ring file or
some other data file (possibly decrypting it on the fly), converting
to ASCII, etc.  All these are part of an encryption/decryption cycle
and can't really be skipped.

Hal
74076.1041@compuserve.com