Seth Schoen's Hard to Verify Signatures

Jack Lloyd lloyd at randombit.net
Wed Sep 8 13:06:47 PDT 2004


On Wed, Sep 08, 2004 at 12:44:39PM -0700, Major Variola (ret) wrote:
[...]
> In an RSA cryptosystem the public exponent is typically low, often
> 3 or 65537 (for efficiency reasons only a few bits are set; the other
> constraint is that your message, raised to that power, wraps in your
> modulus, which makes 65537 a little better).  The private exponent
> is big.
> 
> Therefore, traditional encryption is "fast", and decryption is slow;
> the reverse is that signing is slow, verifying a signature is fast.
> This can be used to achieve Seth's required "fast to make, slow
> to verify".  To achieve the required "user-controllable", the user
> gets to set the number of bits in the modulus.  One might have
> to use extraordinarily long moduli (making 4Kbits look puny), depending
> on the time-scale of "slow" and "fast", but so what, primes are free :-)
> 
> and might even be re-used.
> 
> If this passes group-muster pass it on..

Can't be too short, less than about a third the size of the modulus you start
running into problems [*], which, with the sizes you're suggesting (you would
need, what, a 100K+ bit key to do this?) would make signature generation pretty
slow too.

Easier to do standard RSA and then encrypt the whole thing with a 64 or 80 bit
symmetric key.

[*] http://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf

-Jack





More information about the cypherpunks-legacy mailing list