Re: Algorithm questions

[Hal Finney <[e-mail]>]

Tim Dierks, <[e-mail]>, writes, regarding elliptic curves:
> Specifically, are you just reserving an identifier (which seems pretty
> useless to me; it shouldn't be reserved until its specified), or are you
> indending to provide all the necessary info to allow implementation?

It sounds like it would be best to wait until the algorithm is
implemented.  Personally I don't see much value in assigning identifiers
for which there is no implementation, unless we are sure that one is
coming soon.

> I have the same problem with the existing specification for ElGamal: it's
> not detailed enough to be complete. Here is the entire description of the
> ElGamal encryption system from draft-ietf-openpgp-formats-00.txt:
>
> >    Algorithm Specific Fields for Elgamal encryption:
> >    - MPI of DSA value g**k.
> >    - MPI of DSA value m * y**k.
>
> There's no discussion of how to generate k, and this description isn't
> detailed enough to expect any but true initiates into the secrets to be
> able to implement it. There's no mention of mod p, for example, let alone
> the arcana of key generation or how to decrypt this packet.

You're right, those expressions should have "mod p" added to them.
The description of RSA on the previous line should have "mod n" added.
(This is in section 5.1.)

We should add a reference to ElGamal's original paper, which according
to Bruce Schneier's _Applied_Cryptography_ is:

T. ElGamal, "A Public-Key Cryptosystem and a Signature Scheme Based on
Discrete Logarithms," IEEE Transactions on Information Theory, v. IT-31,
n. 4, 1985, pp. 469-472.

According to this reference, k is simply a random number mod p-1.
Bruce states that it needs to be relatively prime to p-1, but this was
not in the original paper and I don't think it is necessary.

Providing the ElGamal reference should be sufficient for implementors.
The only PGP specific part is the format of m, which is documented in
the spec.

Hal