[cryptography] What's the state of the art in factorization?

[Francois Grieu]

 On 23/04/2010 11:57, Paul Crowley wrote:
>>> [2] http://www.cs.umd.edu/~jkatz/papers/dh-sigs-full.pdf
>
> My preferred signature scheme is the second, DDH-based one in the
> linked paper, since it produces shorter signatures - are there any
> proposals which improve on that?
There is RSA or Rabin using a signature scheme with message recovery.
With a public modulus of n bits, and a hash of h bits, signing a message
adds only h bits, as long as
- the message to sign is at least (n-h) bits and
- you do not care about spending a few modular multiplication to recover
some (n-h) bits of the message [where few is 17, 2 or 1 for popular
public exponents e of 65537, 3, 2]

This is standardized by ISO/IEC 9796-2 (which add a few bits of overhead
to h, like 16 when n is a multiple of 8).
It is used (with a deprecated and not-quite-perfect option set of
ISO/IEC 9796-2) in many applications where size matters, in particular
EMV Smart Cards, and the European Digital Tachograph.

With e=2 and the newer (randomized) schemes of ISO/IEC 9796-2, you get
security provably related to factoring or breaking the hash.


  François Grieu

[I suddenly got a batch of old messages, and wonder what is the
appropriate list address]

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com