Signature with recovery problem

[Shane Hopcroft]

Using RSA, I would like to sign a message with a private key, distribute the signed/encoded message as a single string and recover the message from the signature using the public key during the verification process.

I have found lots of examples of how to verify the signature if the message is known (i.e. distributed alongside the signature), but this is not what I want to do. Even the code snippets on the Wiki like "RSA Probabilistic Signature Scheme with Recovery (Filters)" seem to assume that the message is known at the point of verification.

Wei has posted an example on the FAQ that almost does what I want, but unfortunately it doesn't use filters.

Is there any way to do what I want using Crypto++ filters?

[Hoppy]

Perhaps some more information is needed:

Here is a snippet showing verification and recovery, taken from
http://www.cryptopp.com/wiki/SignatureVerificationFilter:
<blockquote>
// Verify and Recover
RSASS<PSSR, SHA1>::Verifier verifier(publicKey);

StringSource(message+signature, true,
new SignatureVerificationFilter(
verifier,
new StringSink(recovered),
THROW_EXCEPTION | PUT_MESSAGE
) // SignatureVerificationFilter
); // StringSource
</blockquote>

Note that "message+signature" is passed to StringSource as the first
parameter. I can't see how this verification can be made to work
without already knowing the message (i.e. just passing in "signature"
as the first parameter). If I am correct and this can't be done then
doesn't that mean that it is impossible to perform true RSA-PSSR using
Filters (and the information on the wiki should be updated) - or have
I misunderstood something?

Thanks in advance for your help.
Shane.

[Hoppy]

I received an email in response to this post which contained the
following:
> ...you cannot recover the message itself from the signature, only the hash value.

My understanding was that there were two types of algorithms that
could be used to sign a message with RSA: Signature Scheme with
Appendix (SSA) and [Probabilistic] Signature Scheme with Recovery
(PSSR).

SSA works exactly as you describe - a hash of the original message is
signed, and this hash is sent along with the message as an appendix to
the signature, and is verified at the other end.

In PSSR the original message is interleaved into the signature. PSSR
schemes do not require the original message for verification since it
is available in the signature.

I was eventually able to get PSSR working using the method shown here
http://www.cryptopp.com/fom-serve/cache/96.html. Unfortunately, the
code is not very elegant. I would much rather be able to use Crypto+
+'s filter/pipelining system, which is quite neat.

There is information on the web that indicates you can perform PSSR
using the Crypto++ filter/pipelining system. For example, the
following pages have examples of PSSR with filters:
http://www.cryptopp.com/wiki/SignatureVerificationFilter
http://www.cryptopp.com/wiki/RSA_Signature_Schemes

However, while these examples ~do~ allow me to recover the message
from the signature, they require me to have the original message
before I can perform the recovery, which totally defeats the purpose.

If no-one replies to correct me I will assume I am right and remove
the material on the Wiki so no-one else wastes their time.

[Jeffrey Walton]

On Jan 16, 11:47 pm, Hoppy <shanehopcr...@hotmail.com> wrote:
> I received an email in response to this post which contained the
> following:
>
> > ...you cannot recover the message itself from the signature, only the hash value.
>
> My understanding was that there were two types of algorithms that
> could be used to sign a message with RSA: Signature Scheme with
> Appendix (SSA) and [Probabilistic] Signature Scheme with Recovery
> (PSSR).
>
> SSA works exactly as you describe - a hash of the original message is
> signed, and this hash is sent along with the message as an appendix to
> the signature, and is verified at the other end.
>
> In PSSR the original message is interleaved into the signature. PSSR
> schemes do not require the original message for verification since it
> is available in the signature.
>
> I was eventually able to get PSSR working using the method shown here
> http://www.cryptopp.com/fom-serve/cache/96.html. Unfortunately, the
> code is not very elegant. I would much rather be able to use Crypto+
> +'s filter/pipelining system, which is quite neat.
>

Also see validate2.cpp, near line 130.

[Jeffrey Walton]

On Jan 16, 11:47 pm, Hoppy <shanehopcr...@hotmail.com> wrote:

[SNIP]

>
> However, while these examples ~do~ allow me to recover the message
> from the signature, they require me to have the original message
> before I can perform the recovery, which totally defeats the purpose.
>
> If no-one replies to correct me I will assume I am right and remove
> the material on the Wiki so no-one else wastes their time.

StringSource(message, true,

new SignerFilter(rng, signer,

new StringSink(signature),

true // bool putMessage
<===========
) // SignerFilter

); // StringSource

...

StringSource(signature, true,

new SignatureVerificationFilter(

verifier,

new StringSink(recovered),

SignatureVerificationFilter::THROW_EXCEPTION |

SignatureVerificationFilter::PUT_MESSAGE