Determining the algorithm used to generate a digital signature

I have a string "abcd pqrs". This string is digitally signed with an X.509 certificate (with its private key) and it produces a signature.

From the signed string, is it possible to find out what hashing algorithm was used?

Also, does the signed data always contain the certificate or the public key used to sign the data? If it does, how can I extract the certificate from the signed data?

The only information I have is that it's signed by an X.509 certificate.

This is the problem I am trying to solve:

I have an opaque tool which takes an X.509 certificate, the corresponding private key and "data to be signed", and gives me signed data. I have no information about what kind of hashing/signing algorithm it uses, I have no information about whether it produces a detached or attached output.

Basically, I want to verify the signature and the data — but before I do that, I need to have some info about it. I have access to original unsigned data.

-
I'd try throwing some kind of ASN1 parser at the signature. –  CodesInChaos Jan 1 '13 at 16:23
Maybe include the signature as hex or as ASN.1 dump (openssl asn1parse -dump) in the question. If ASN.1 dump produces an error include the size and the hexadecimal data. –  owlstead Jan 3 '13 at 21:23
If it is the same size as the modulus of the public key in the certificate (or private key) then you can be almost certain that it uses PKCS#1 v2.1, using either PKCS#1 v1.5 padding or PSS. You can simply do a raw RSA operation using the public key to see the padding inside, or you can try both algorithms and see which one verifies. It would be nice if you reacted on comments. –  owlstead Jan 5 '13 at 18:54