Re: [openpgp] Deriving an OpenPGP secret key from a human readable seed

["brian m. carlson" <[e-mail]>]

On 2019-10-19 at 03:40:03, Phillip Hallam-Baker wrote:
> Someone just said we need a spec. Here is a spec:
> https://www.ietf.org/id/draft-hallambaker-mesh-udf-07.txt
> 
> It is in the new format which is intended to be read as HTML. Until the
> tools catch up, you can read it here:
> http://mathmesh.com/Documents/draft-hallambaker-mesh-udf.html

This doesn't specify any method of primality testing which means
different implementations can produce different values[0] (and is
therefore not deterministic), unless you literally interpret the text
"smallest prime integer" as requiring an actual prime.  That could be
implemented by using the Miller test instead of Miller-Rabin, but that
would be much, much slower.

In this particular case, the approach to invalid keys (where p and q are
unsuitable) is "try again with a different seed", which is probably okay
in terms of RSA, because the number of retries necessary will be low.

It also doesn't specify DSA keys, which, while uncommon, are still a
part of the spec.  The "try again" approach will probably be a little
more difficult here.

> The draft does not specify the value of e which it should but I am pretty
> sure we have standardized on 65537. I see no reference to p being greater
> than q and it is a mystery to me why we would care when the RSA parameters
> are the modulus and the private exponent d. Knowledge of p and q is only
> used to determine d, they are not req

The OpenPGP secret key contains u, the multiplicative inverse of p mod
q, which is used along with p and q for the Chinese Remainder Theorem.
RFC 4880 specifically mentions that p must be less than q, which is
required for u to exist.  (This is backwards from most other specs,
which require the opposite and define u as the multiplicative inverse of
q mod p.)

It is, of course, possible to retain only n and d and eat the
performance penalty, but that would not produce a valid OpenPGP secret
key.

[0] Yes, people should pick a suitable number of iterations for
primality testing, but there are people that pick 1 iteration for
PBKDF2, which is a demonstration of why we can't have nice things.  We
actually have to tell people how to write things in an interoperable
and secure way.
-- 
brian m. carlson: Houston, Texas, US
OpenPGP: https://keybase.io/bk2204