🚀 go-pugleaf

The Dr Dobbs article claims that LUC is stronger than RSA.  In fact we now
have "proof" of that claim, in the sense that we have worked out a way
(actually refined an old way - we're well aware that this type of attack is
well known) to forge RSA signatures, using just public information.  The
basic method is to factorise a message just before it's signed (i.e. after
the hashing algorithm has been applied), then recover the signatures of the
prime factors by using an elimination method on factorised random messages.
 Unfortunately with a 512 bit key it all takes too many lifetimes to be
feasible in "general", but it becomes at least capable of consideration if
:
* The message is hashed to a short (eg 128-bit) block.
* Either the number 3 is used as the RSA encryption exponent,
* Or there is a Notary Public you can use which signs things that are
obtained from the message in a predictable way (eg hashing or addition of
time stamp).

The interesting thing is that hashing is no protection whatsoever - it
makes things simpler for the first stage (in practice, by reducing the size
of the message to factorise), and it doesn't stop the Notary Public attack
because the thing which the N.P. signs is obtained predictably from the
message sent to it.

Because factorising LUC signatures does not get you anywhere (the
signatures of the factors are no use at all), LUC can continue to be used
with short signature blocks, exponent 3, and simple Notary Publics.